Source-linked AI summary
Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, Pushmeet Kohli
TL;DR
Neural program synthesis must handle multiple semantically valid programs and strict syntax, shortcomings of single-reference supervised sequence generation. The paper combines reinforcement learning with syntax-aware modeling, reporting improved accuracy—particularly with limited training data—while noting limitations in its sampling-based objectives.
Problem
Single-reference supervised learning penalizes semantically correct alternative programs and overlooks efficiently checkable syntax constraints.
Method
The paper uses policy-gradient reinforcement learning to reward consistent programs and a jointly learned syntax model to prune invalid programs without requiring a formal grammar.
Results
The contributions improve program-synthesis performance, with reinforcement learning improving over pure supervision and syntax incorporation producing significant gains with limited training data.
Takeaways & Limitations
Optimizing correctness over any consistent program and incorporating syntax can improve neural program synthesis across large-data and limited-data settings, respectively.
Takeaways & Limitations
Sampling-based objectives may repeatedly sample the same programs, and an expected-correctness formulation assumes sampled correct programs can be identified while treating samples independently.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Neural program synthesis faces program aliasing and overlooked syntax constraints. The paper uses reinforcement learning and syntax-aware modeling to improve synthesis, especially with limited training data.
- Motivation: Program aliasing arises because multiple programs can satisfy a small set of input-output examples, while supervised learning targets only one reference program.Maximum-likelihood training can penalize semantically correct alternatives despite the true objective being to generate any consistent program.
- Contributions: Reinforcement learning directly encourages generation of any program consistent with the given examples instead of maximizing reference-program likelihood.The approach uses policy-gradient reinforcement learning to alter the optimization objective.
- Motivation: Sequence-generation methods often overlook strict program syntax, even though syntactically invalid token sequences can be efficiently identified and pruned.The paper treats syntax checking as an additional source of supervision.
- Contributions: The proposed neural architecture jointly conditions on syntactic and program correctness, implicitly learning the language syntax without a predefined grammar.It retains syntax-pruning benefits when an external syntax checker or formal grammar is unavailable.
- Evaluation: The approach is evaluated on Karel, an educational language with loops and conditionals, making it more complex than domains used in earlier neural synthesis work.The introduction reports improved performance in instances with limited training data.
2 RELATED WORK
Prior work spans rule-based, probabilistic, inductive-logic, differentiable, and neural program synthesis methods. The paper differs by optimizing correctness directly and learning grammar-related constraints over grammar terminals without requiring a formal grammar specification.
- Rule-based and statistical synthesis: Machine-learning approaches include Bayesian models, inductive logic programming, differentiable controllers, and neural systems that infer explicit program source code.These methods use examples or differentiable programming concepts to generate or model program behavior.
- Rule-based and statistical synthesis: Rule-based Programming By Example systems can succeed in practical settings but require complex, domain-expert-developed pruning rules and are difficult to extend.FlashFill is cited as a prominent example.
- Neural program synthesis: Explicitly modeling control flow can improve generalization, but some approaches must restart learning for each new program and therefore suit few-example on-the-fly synthesis poorly.Recent systems instead learn mappings from input-output embeddings to program information using large artificial datasets.
- Neural program synthesis: Earlier neural methods use supervised training to maximize likelihood of a single reference program, whereas this paper optimizes for generating any consistent program.The paper positions its objective relative to recent grammar-based and source-code-generating systems.
- Grammar-aware synthesis: Grammar-aware methods enforce syntactic correctness through production rules, while this approach operates directly over grammar terminals and can learn the grammar jointly without a formal specification.The comparison concerns how syntax information is represented and obtained.
3 PROBLEM OVERVIEW
The system maps input-output examples to token-sequence programs using shared LSTM decoders and pooled representations. At test time, beam search and execution filter hypotheses for syntax and consistency before selecting the most likely remaining program.
- 3.1 PROGRAM SYNTHESIS FORMULATION: The task assumes training samples containing sets of input-output states and programs that correctly implement the mappings.The synthesizer learns to produce a program from input-output examples and is evaluated using held-out test cases.
- 3.2 NEURAL PROGRAM SYNTHESIS ARCHITECTURE: Programs are represented as token sequences, and an LSTM predicts each next token from the previous token and an embedding of the input-output pair.One decoder is run per input-output pair with shared weights.
- 3.2 NEURAL PROGRAM SYNTHESIS ARCHITECTURE: Each input-output pair is jointly encoded by a CNN, while decoder hidden states are max-pooled before a Softmax produces the next-token distribution.The architecture runs one decoder for each example and combines their information through max pooling.
- 3.3 DECODING: Beam search generates likely programs, which execution filters by removing syntactically incorrect programs and those inconsistent with observed examples.The most likely program among the remaining hypotheses is returned.
- 3.2 NEURAL PROGRAM SYNTHESIS ARCHITECTURE: The syntax model generates a mask that modulates token predictions, incorporating syntactic constraints into decoding.This mechanism is shown as part of the model architecture.
4 OBJECTIVE FUNCTIONS
The paper replaces reference-program maximum likelihood with objectives that reward semantically correct programs and approximate them using likely beam-search candidates. This aligns training more closely with synthesis goals and testing while exposing tractability and sampling limitations.
- 4.1 MAXIMUM LIKELIHOOD OPTIMIZATION: Maximum likelihood penalizes correct programs that differ from the single reference, despite program synthesis accepting any specification-consistent program.This mismatch is called program aliasing.
- 4.2 OPTIMIZING EXPECTED CORRECTNESS: The proposed reward objective assigns probability to multiple candidate programs according to their sampled quality rather than only one reference.The reward can encode correctness, held-out-example generalization, conciseness, or runtime efficiency.
- 4.2 OPTIMIZING EXPECTED CORRECTNESS: Beam search retains the S most likely prefixes at each step, then uses completed sequences to construct a rescaled approximate distribution.All possible next tokens are considered for the retained candidates, while completed sequences are held out.
- 4.2 OPTIMIZING EXPECTED CORRECTNESS: Sampling from one model can repeatedly produce the same programs, especially after supervised pretraining, motivating a smaller-support approximation.The beam-search distribution contains only the S returned candidates.
- 4.2 OPTIMIZING EXPECTED CORRECTNESS: The beam-search approximation is tractable and better aligned with testing, but introduces bias relative to the original distribution.Its smaller support permits direct differentiation without a Monte Carlo gradient estimator.
- 4.2 OPTIMIZING EXPECTED CORRECTNESS: The bag-of-programs correctness formulation assumes that a correct sample can be identified and that C samples are independent, limiting its ideality.Partial specifications may leave incorrect programs consistent with the observed input-output pairs.
5 MODEL
The model enforces syntax either with a deterministic grammar-based mask or with a jointly learned syntax LSTM. Both approaches restrict generation toward valid program prefixes and candidates.
- 5 MODEL: A syntax checker masks tokens that cannot extend the current prefix, making syntactically correct generation a construction constraint.Invalid-token logits receive −inf before Softmax normalization.
- 5 MODEL: Syntax conditioning restricts beam search to useful candidates and ensures correctness optimization samples valid programs.Reducing the modeled space also makes the learning problem simpler.
- 5 MODEL: When a formal checker is unavailable, a syntax LSTM learns syntax jointly while conditioning only on program tokens.This separates syntax modeling from the input-output specification.
- 5 MODEL: The syntax LSTM adds negative exponential penalties to decoder logits for tokens it judges syntactically incorrect.The architecture can also receive an auxiliary loss preventing penalties on tokens in known valid reference programs.
6 EXPERIMENTS
Experiments on the Karel DSL compare supervised and reinforcement-learning objectives, beam-search variants, and handwritten or learned syntax modeling across full and limited datasets. RL improves generalization, while learned syntax is especially beneficial with limited data.
- 6.1 THE DOMAIN: KAREL: The evaluation uses Karel, a gridworld programming language with loops, conditionals, and input-output grid specifications.The dataset is synthetically generated from randomly sampled DSL programs and includes full and reduced 10,000-example settings.
- 6.2 RESULTS: RL consistently improves top-1 generalization accuracy over supervised maximum likelihood, directly addressing program aliasing.Top-1 generalization requires the most likely synthesized program to match behavior across all input-output examples, including a held-out example.
- 6.2 RESULTS: RL_beam improves over standard RL across all generalization levels, with further gains from beam diversity and penalties for long-running programs.RL_beam aligns the objective with beam-search decoding; RL_beam_div and RL_beam_div_opt encourage diverse, less redundant solutions.
- 6.2 RESULTS: RL methods show more dramatic improvements over MLE when little training data is available, indicating improved data efficiency.The reported procedure uses supervised training followed by reinforcement-learning fine-tuning.
- 6.2 RESULTS: On the small dataset, learned syntax significantly outperforms handwritten syntax and larger no-syntax models, whereas full-data gains from handwritten syntax are marginal.The larger decoder baseline controls for the extra parameters of the syntaxLSTM, and its performance does not explain the learned-syntax advantage.
- 6.2 RESULTS: Syntax masking materially affects correctness: removing the learned mask causes a precipitous drop in syntactic accuracy, while some mask errors can be recovered by decoder probabilities.The learned syntax model also captures program-distribution information, including the rarity of certain tokens and unlikely programs.
7 CONCLUSION
The paper presents reinforcement learning for generating any consistent program and syntax checking for pruning decoding; syntax improves results with limited training data, while reinforcement learning helps generalization on large datasets.
- The first contribution uses reinforcement learning to optimize generation of any consistent program.
- The second contribution incorporates syntax checking as an additional conditioning mechanism during decoding.
- Syntax incorporation leads to significant improvements when training data is limited.
A COMPUTING THE RICHER LOSS FUNCTION
The richer loss is computed from samples drawn from a beam-search distribution, using the best sampled reward and closed-form probability calculations.
- The method forms qθ by beam-searching over pθ and renormalizing the resulting S programs.
- It draws C independent samples from qθ and uses the best-performing sample's reward.
- For boolean rewards, the maximum reward is zero only when all C sampled programs receive zero reward.
- The probability of obtaining no correct program among C samples is derived from the per-sample incorrect-program probability.
- For general rewards, the derivation orders candidate rewards and computes probabilities for final rewards below or exactly at each level.
B KAREL LANGAGE SPECIFICATION
Figure 4 presents the domain-specific language used for Karel programs.
- The figure concerns a domain-specific language.
- The language is associated with Karel programs.
- The passage identifies this material as Figure 4.
C EXPERIMENTS HYPERPARAMETERS
The experiments encode grid states and input-output pairs for two LSTM decoders, combine model and syntax outputs for token prediction, and use specified optimization and search settings.
- Grid-word states are represented as 16 × 18 × 18 tensors, with 16 features per grid cell.
- The decoders are two-layer LSTMs with hidden size 256, while token embeddings also have dimension 256.
- Input-output pair activations are max-pooled, linearly mapped to 52 token scores, and combined with syntax-model outputs before SoftMax prediction.
- Training uses Adam with learning rate 10^-4, batch sizes 128 for supervised learning and 16 for reinforcement learning.
- Reinforce uses 100 rollouts per sample, beam-search methods use beam size 64, and bag-of-program losses use C = 5.