Research map / Large language models / Agents, code and math
HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns a task-specific PCFG from LLM samples (including ungrammatical ones in non-strict mode) and uses it to weight bottom-up program synthesis across ARC, tensor, and string PBE domains.
Problem
LLMs fail to produce fully correct programs in unfamiliar DSLs, while combinatorial program synthesis scales poorly; LLMs cannot easily guide bottom-up search because bottom-up search relies on context-free factorization.
Approach
Approximate an LLM's conditional distribution over programs for a given task with a context-free PCFG learned by maximum likelihood from LLM completions (including ungrammatical ones via operator-terminal counting), and use its weights to guide bottom-up search.
Key results
- HySynth solves 58% of 299 tasks overall, vs 40% for unguided search and 6% for LLM sampling alone.
- On the Tensor domain, GPT-4o-guided HySynth solves 96% of tasks while direct GPT-4o sampling solves none.
- On Arc, a 4x search-space reduction (450K to 220K programs) for the motivating example, solved in about one minute with LLM guidance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| guide bottom-up synthesis with a task-specific PCFG learned from GPT-4o completions | HySynth · 299 PBE tasks (Arc, String, Tensor) | tasks solved: 40% -> 58% | Helped |
| guide synthesis with a PCFG and search rather than use LLM samples directly | HySynth · 299 PBE tasks (Arc, String, Tensor) | tasks solved: 6% -> 58% | Helped |
| use LLM samples directly without search (ablation) | HySynth · Tensor | tasks solved | Hurt |
| replace the weighted PCFG with a binary PCFG that excludes components absent from the LLM samples (ablation) | HySynth · Arc and Tensor | tasks solved | Hurt |
| use 10 instead of 100 GPT-4o samples to learn the PCFG (ablation) | HySynth · String | tasks solved: 9 fewer problems | Hurt |
| vary the number of GPT-4o samples used to learn the PCFG (ablation) | HySynth · Arc and Tensor | tasks solved: 2 problems each | Mixed |
| use strict mode, discarding syntactically invalid completions, rather than non-strict mode (ablation) | HySynth-Arc · Arc | tasks solved: 58 tasks in either mode | No clear effect |
| use a context-free LLM surrogate to guide synthesis | HySynth-Tensor · Tensor | benchmark solved: 96% | Helped |
| use the custom bottom-up divide-and-conquer synthesizer instead of Arga | HySynth-Arc · Object-Arc | tasks solved | Helped |
| use LLM-derived weights to guide search rather than uniform weights | HySynth · Arc motivating example | programs enumerated: 450K -> 220K | Helped |
| use LLM-derived weights to guide search rather than uniform weights | HySynth · Arc motivating example | speedup: 4x speedup | Helped |
| use non-strict mode to incorporate syntactically invalid completions | HySynth · Arc and String | completions available for PCFG learning: 78.4%; 37.5% | Helped |
Surprising findings
- Direct GPT-4o sampling solves no Tensor tasks, yet it provides excellent guidance for search there.
- Ungrammatical LLM completions are useful: non-strict mode matches strict mode given the same number of completions.
Limitations
- Requires implementing a synthesizer for each DSL.
- Costly LLM sampling compared to purely symbolic approaches.
- Guidance is only as good as the LLM completions; irrelevant operators can slow search below unguided search.
Experimental setup
Datasets: Object-Arc (Arga test set) TFCoder tensor tasks SyGuS/Probe string tasks
Benchmarks: Object-Arc (160 tasks) TFCoder tensor tasks (69 tasks) SyGuS/Probe string tasks (70 tasks)
Metrics: number of tasks solved time to solution percentage of syntactically valid completions
Baselines: Arga TFCoder Probe unguided search binary surrogate direct LLM sampling
Builds on: bottom-up search TFCoder Probe Arga divide-and-conquer synthesis
Closest papers by meaning
- REASONING COMPILER: LLM-Guided Optimizations for Efficient Model Serving (NeurIPS 2025 · similarity 0.90)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.89)
- Online Prompt Selection for Program Synthesis (AAAI 2025 · similarity 0.89)
- Once Upon an Input: Reasoning via Per-Instance Program Synthesis (NeurIPS 2025 · similarity 0.88)
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis (ICLR 2024 · similarity 0.88)
- Skip a Layer or Loop It? Learning Program-of-Layers in LLMs (ICML 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.