# Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

arXiv: https://arxiv.org/abs/1805.04276 · HTML: https://mlsanity.com/paper/1805.04276/

## Key facts

- Cited by 84 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2018.

## Built on by (most cited first, 30 of 84)

- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedback](https://mlsanity.com/paper/2306.14898/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Learning Performance-Improving Code Edits](https://mlsanity.com/paper/2302.07867/) (2023)
- [Neural Production Systems: Learning Rule-Governed Visual Dynamics](https://mlsanity.com/paper/2103.01937/) (2021)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [From LSAT: The Progress and Challenges of Complex Reasoning](https://mlsanity.com/paper/2108.00648/) (2021)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutions](https://mlsanity.com/paper/2205.14318/) (2022)
- [Maximum Likelihood Reinforcement Learning](https://mlsanity.com/paper/2602.02710/) (2026)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [Emergent Representations of Program Semantics in Language Models Trained on Programs](https://mlsanity.com/paper/2305.11169/) (2023)
- [How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition](https://mlsanity.com/paper/2207.07730/) (2022)
- [Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation](https://mlsanity.com/paper/2305.00909/) (2023)
- [CodeIt: Self-Improving Language Models with Prioritized Hindsight Replay](https://mlsanity.com/paper/2402.04858/) (2024)
- [ProTo: Program-Guided Transformer for Program-Guided Tasks](https://mlsanity.com/paper/2110.00804/) (2021)
- [Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs](https://mlsanity.com/paper/2301.12950/) (2023)
- [Proximal Curriculum for Reinforcement Learning Agents](https://mlsanity.com/paper/2304.12877/) (2023)
- [Hybrid Reinforcement: When Reward Is Sparse, It's Better to Be Dense](https://mlsanity.com/paper/2510.07242/) (2025)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis](https://mlsanity.com/paper/2205.13728/) (2022)
- [Neural Task Synthesis for Visual Programming](https://mlsanity.com/paper/2305.18342/) (2023)
- [Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search](https://mlsanity.com/paper/2405.16450/) (2024)
- [Adaptive Scaffolding in Block-Based Programming via Synthesizing New Tasks as Pop Quizzes](https://mlsanity.com/paper/2303.16359/) (2023)
- [Guiding Enumerative Program Synthesis with Large Language Models](https://mlsanity.com/paper/2403.03997/) (2024)
- [Program Synthesis Guided Reinforcement Learning for Partially Observed Environments](https://mlsanity.com/paper/2102.11137/) (2021)

## Abstract (arXiv)

Program synthesis is the task of automatically generating a program consistent with a specification. Recent years have seen proposal of a number of neural approaches for program synthesis, many of which adopt a sequence generation paradigm similar to neural machine translation, in which sequence-to-sequence models are trained to maximize the likelihood of known reference programs. While achieving impressive results, this strategy has two key limitations. First, it ignores Program Aliasing: the fact that many different programs may satisfy a given specification (especially with incomplete specifications such as a few input-output examples). By maximizing the likelihood of only a single reference program, it penalizes many semantically correct programs, which can adversely affect the synthesizer performance. Second, this strategy overlooks the fact that programs have a strict syntax that can be efficiently checked. To address the first limitation, we perform reinforcement learning on top of a supervised model with an objective that explicitly maximizes the likelihood of generating semantically correct programs. For addressing the second limitation, we introduce a training procedure that directly maximizes the probability of generating syntactically correct programs that fulfill the specification. We show that our contributions lead to improved accuracy of the models, especially in cases where the training data is limited.