mlsanityData to 14 Oct 2026

ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis

arXiv 2307.13883 ↗First posted 26 Jul 2023cs.LG cs.PLcited by 17

Not on the map. Why?

Abstract (arXiv)

When writing programs, people have the ability to tackle a new complex task by decomposing it into smaller and more familiar subtasks. While it is difficult to measure whether neural program synthesis methods have similar capabilities, we can measure whether they compositionally generalize, that is, whether a model that has been trained on the simpler subtasks is subsequently able to solve more complex tasks. In this paper, we characterize several different forms of compositional generalization that are desirable in program synthesis, forming a meta-benchmark which we use to create generalization tasks for two popular datasets, RobustFill and DeepCoder. We then propose ExeDec, a novel decomposition-based synthesis strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step. When used with Transformer models trained from scratch, ExeDec has better synthesis performance and greatly improved compositional generalization ability compared to baselines. Finally, we use our benchmarks to demonstrate that LLMs struggle to compositionally generalize when asked to do programming-by-example in a few-shot setting, but an ExeDec-style prompting approach can improve the generalization ability and overall performance.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 54 of its 78 references that are in the map. First posted on arXiv 26 Jul 2023.

Builds on

54 of 78 references.

References · 54

  1. 2017Attention Is All You Needcited by 60,361
  2. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  4. 2021Program Synthesis with Large Language Modelscited by 3,637
  5. 2014Sequence to Sequence Learning with Neural Networkscited by 2,986
  6. 2022Competition-Level Code Generation with AlphaCodecited by 1,462
  7. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,407
  8. 2018Self-Attention with Relative Position Representationscited by 1,120
  9. 2019Measuring Compositional Generalization: A Comprehensive Method on Realistic Datacited by 284
  10. 2020COGS: A Compositional Generalization Challenge Based on Semantic Interpretationcited by 263
  11. 2023Planning with Large Language Models for Code Generationcited by 182
  12. 2020Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Basescited by 171
38 more
  1. 2020DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learningcited by 161
  2. 2019Good-Enough Compositional Data Augmentationcited by 158
  3. 2016DeepCoder: Learning to Write Programscited by 149
  4. 2020Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?cited by 147
  5. 2018Improving Text-to-SQL Evaluation Methodologycited by 135
  6. 2017RobustFill: Neural Program Learning under Noisy I/Ocited by 126
  7. 2021The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformerscited by 117
  8. 2014Learning to Executecited by 106
  9. 2019Compositional generalization through meta sequence-to-sequence learningcited by 99
  10. 2020Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architecturescited by 95
  11. 2022Compositional Semantic Parsing with Large Language Modelscited by 95
  12. 2019Write, Execute, Assess: Program Synthesis with a REPLcited by 93
  13. 2016Neuro-Symbolic Program Synthesiscited by 84
  14. 2018Leveraging Grammar and Reinforcement Learning for Neural Program Synthesiscited by 84
  15. 2020Compositional Generalization via Neural-Symbolic Stack Machinescited by 80
  16. 2020Span-based Semantic Parsing for Compositional Generalizationcited by 77
  17. 2021Making Transformers Solve Compositional Taskscited by 72
  18. 2020Learning to Recombine and Resample Data for Compositional Generalizationcited by 65
  19. 2019CLOSURE: Assessing Systematic Generalization of CLEVR Modelscited by 63
  20. 2021Meta-Learning to Compositionally Generalizecited by 62
  21. 2019Compositional generalization in a deep seq2seq model by separating syntax and semanticscited by 56
  22. 2021Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representationscited by 55
  23. 2020Compositional Generalization by Learning Analytical Expressionscited by 53
  24. 2019Compositional Generalization for Primitive Substitutionscited by 48
  25. 2021Improving Compositional Generalization with Latent Structure and Data Augmentationcited by 46
  26. 2019Learning to Infer Program Sketchescited by 44
  27. 2020Meta-Learning for Domain Generalization in Semantic Parsingcited by 41
  28. 2021Learning to Synthesize Data for Semantic Parsingcited by 41
  29. 2020Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networkscited by 35
  30. 2021Latent Execution for Neural Program Synthesiscited by 35
  31. 2020BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Explorationcited by 30
  32. 2020TF-Coder: Program Synthesis for Tensor Manipulationscited by 27
  33. 2021Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalizationcited by 27
  34. 2018Automatic Program Synthesis of Long Programs with a Learned Garbage Collectorcited by 24
  35. 2020Just-in-Time Learning for Bottom-Up Enumerative Synthesiscited by 18
  36. 2020Latent Programmer: Discrete Latent Codes for Program Synthesiscited by 18
  37. 2022CrossBeam: Learning to Search in Bottom-Up Program Synthesiscited by 18
  38. 2020Learning to Represent Programs with Property Signaturescited by 16

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 8; 2025: 6; 2026: 3.

17 papers.

Sort:

By area:

  1. 2024NExT: Teaching Large Language Models to Reason about Code Executioncited by 63
  2. 2024Top Leaderboard Ranking = Top Coding Proficiency, Always? EvoEval: Evolving Coding Benchmarks via LLMcited by 40
  3. 2024Is Programming by Example solved by LLMs?cited by 27
  4. 2024EVOR: Evolving Retrieval for Code Generationcited by 22
  5. 2024Case2Code: Scalable Synthetic Data for Code Generationcited by 13
  6. 2024FactorSim: Generative Simulation via Factorized Representationcited by 10
  7. 2026Gradient-Based Program Synthesis with Neurally Interpreted Languagescited by 5
  8. 2025Programming by Examples Meets Historical Linguistics: A Large Language Model Based Approach to Sound Law Inductioncited by 3
  9. 2024Can Large Language Models Code Like a Linguist?: A Case Study in Low Resource Sound Law Inductioncited by 2
  10. 2025Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Modelcited by 2
  11. 2025Out-of-Distribution Generalization in the ARC-AGI Domain: Comparing Execution-Guided Neural Program Synthesis and Test-Time Fine-Tuningcited by 2
  12. 2025Diverse In-Context Example Selection After Decomposing Programs and Aligned Utterances Improves Semantic Parsingcited by 1
5 more
  1. 2025Beyond Either-Or Reasoning: Transduction and Induction as Cooperative Problem-Solving Paradigmscited by 1
  2. 2024Compositional Models for Estimating Causal Effectscited by 0
  3. 2025A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Conditioncited by 0
  4. 2026A Small-Scale System for Autoregressive Program Synthesis Enabling Controlled Experimentationcited by 0
  5. 2026Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquercited by 0