Research map / Large language models / Agents, code and math
ExeDec: Execution Decomposition for Compositional Generalization in Neural 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.
Introduces a meta-benchmark of five compositional generalization tasks for program synthesis, instantiates it on RobustFill and DeepCoder, and proposes ExeDec, a subgoal-predicting step-by-step decomposition synthesizer that outperforms Transformer baselines and improves few-shot LLM generalization.
Problem
Neural program synthesizers often fail to compositionally generalize, e.g., to longer programs or to new combinations of API concepts seen separately in training; there is no systematic benchmark for this in programming by example.
Approach
ExeDec decomposes synthesis in the execution space: a SubgoalModel predicts the next intermediate execution state for each I/O example, a SynthesizerModel generates the subprogram achieving that subgoal, and execution updates the specification in a beam search.
Key results
- On RobustFill, ExeDec achieves about +44% higher average compositional generalization than the Transformer baseline, and about +18% on DeepCoder (4.4x higher success rate per the paper's discussion).
- Compared with the no-subgoal ablation, ExeDec averages +7% on RobustFill and +5% on DeepCoder in compositional generalization.
- In few-shot PaLM 2 experiments on DeepCoder-Pythonic, the ExeDec-style prompting solves 40% to 75% more tasks than the next-best approach across settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| decompose synthesis into steps and predict execution subgoals before synthesizing each subprogram | Transformer program synthesizers · RobustFill compositional generalization | accuracy: +44% | Helped |
| decompose synthesis into steps and predict execution subgoals before synthesizing each subprogram | Transformer program synthesizers · DeepCoder compositional generalization | accuracy: +18% | Helped |
| add execution subgoal prediction (ablation) | no-subgoal step-by-step synthesis · RobustFill compositional generalization | accuracy: +7% | Helped |
| add execution subgoal prediction (ablation) | no-subgoal step-by-step synthesis · DeepCoder compositional generalization | accuracy: +5% | Helped |
| add execution subgoal prediction (ablation) | no-subgoal step-by-step synthesis · DeepCoder training distribution | accuracy | Hurt |
| add execution subgoal prediction (ablation) | no-subgoal step-by-step synthesis · DeepCoder length generalization | accuracy | Hurt |
| reduce model size to ExeDec-Small (ablation) | ExeDec · RobustFill and DeepCoder generalization tasks | accuracy: 1.4% worse on average and up to 3% worse on any individual generalization task | Hurt |
| increase beam size from 1 to 10 | ExeDec · RobustFill and DeepCoder | accuracy | Helped |
| use ExeDec-style prompting with execution subgoals | PaLM 2 Unicorn · DeepCoder-Pythonic, generalization average | solved tasks | Helped |
| represent DeepCoder programs in Pythonic form | ExeDec-style prompting · DeepCoder to DeepCoder-Pythonic | solved tasks | Helped |
Surprising findings
- The Transformer baseline gets the best no-generalization accuracy on DeepCoder at beam size 1 (50.7%), above ExeDec (39.1%), though ExeDec wins on generalization.
- The no-subgoal ablation is slightly better than ExeDec on DeepCoder's training distribution and on LengthGen.
Limitations
- Requires a training dataset with ground-truth line-by-line decompositions, which may not reflect natural decompositions.
- Line-by-line decomposition may not match how programmers think in larger hierarchical chunks.
- SubgoalModel predicts tokenized object values, which may not scale to complex objects.
Experimental setup
Datasets: RobustFill DeepCoder
Benchmarks: RobustFill compositional generalization splits DeepCoder compositional generalization splits DeepCoder-Pythonic
Metrics: end-to-end test accuracy solved tasks out of 200 single-step accuracy
Baselines: Transformer baseline no-subgoal ablation Latent Programmer PaLM 2 Unicorn baseline prompting Ablation-style prompting
Builds on: Latent Programmer Transformer SCAN COGS Aligned Relative Attention
Closest papers by meaning
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.88)
- Limits of Transformer Language Models on Learning to Compose Algorithms (NeurIPS 2024 · similarity 0.86)
- Task Generalization with Autoregressive Compositional Structure: Can Learning from $D$ Tasks Generalize to $D^T$ Tasks? (ICML 2025 · similarity 0.86)
- Scaling can lead to compositional generalization (NeurIPS 2025 · similarity 0.86)
- CraftFactory: A Conditioned Control Policy Benchmark for Compositional Generalization (AAAI 2025 · similarity 0.86)
- When does compositional structure yield compositional generalization? A kernel theory. (ICLR 2025 · similarity 0.85)
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.