Source-linked AI summary
DeepCoder: Learning to Write Programs
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow
TL;DR
Programming-competition-style synthesis requires finding source programs from input-output examples. The paper trains neural networks to predict program properties and uses those predictions to guide existing search techniques. Experiments report order-of-magnitude speedups over non-augmented baselines and comparable RNN approaches, with solvable problems comparable to the simplest programming-competition problems.
Problem
Existing program-like neural networks do not generate human-readable source code, while differentiable-interpreter approaches solve each synthesis problem independently.
Method
The paper trains neural networks to predict program properties from input-output examples and integrates their predictions with enumerative and SMT-based search.
Results
Order-of-magnitude speedups over strong non-augmented baselines and a Recurrent Neural Network approach enable solving problems comparable to the simplest programming-competition problems.
Takeaways & Limitations
Neural guidance can improve the runtime of existing inductive program synthesis systems while retaining search over program space.
Takeaways & Limitations
The synthesized programs cover only the simplest competition problems, and the DSL cannot express many problems requiring dynamic programming, search, or more flexible constructs such as loops.
Abstract
from arXiv · showhide
We develop a first line of attack for solving programming competition-style problems from input-output examples using deep learning. The approach is to train a neural network to predict properties of the program that generated the outputs from the inputs. We use the neural network's predictions to augment search techniques from the programming languages community, including enumerative search and an SMT-based solver. Empirically, we show that our approach leads to an order of magnitude speedup over the strong non-augmented baselines and a Recurrent Neural Network approach, and that we are able to solve problems of difficulty comparable to the simplest problems on programming competition websites.
1 INTRODUCTION
The paper frames program synthesis from input-output examples as a setting where machine learning can guide, rather than replace, search-based techniques. Its framework combines learned program properties with existing synthesis methods and achieves substantial speedups on simple programming-competition-style problems.
- Existing program-like neural networks do not generate human-readable source code, motivating source-code induction from input-output examples.
- The approach learns to induce programs across problems and integrates neural architectures with search-based techniques instead of replacing search.
- Learning program-space guidance recasts inductive program synthesis as supervised prediction while retaining search over candidate programs.
- The framework defines a programming language expressive enough for real-world problems yet predictable from input-output examples, alongside models mapping examples to program properties.
- An order of magnitude speedup over standard program synthesis techniques makes the approach feasible for problems comparable to the simplest programming-competition problems.
2 BACKGROUND ON INDUCTIVE PROGRAM SYNTHESIS
Inductive program synthesis produces programs consistent with input-output examples, requiring both a search procedure and a way to rank multiple consistent programs. The background surveys DSLs and several search paradigms used to make this problem tractable.
- Inductive Program Synthesis asks for a program whose behavior is consistent with given input-output examples.
- An IPS system must search a defined program space and rank multiple programs that fit the examples, making DSL choice an important formulation decision.
- Domain Specific Languages (DSLs): Domain-specific languages restrict programming constructs to specialized domains, reducing the search-space complexity compared with full-featured languages.
- Search Techniques: Enumerative search generates grammar derivations and checks them against examples, often using type-based or logical pruning.
- Search Techniques: FlashMeta decomposes restricted-domain synthesis into subproblems, such as producing separate parts of an output string.
- Search Techniques: SMT-based systems encode DSL semantics and input-output relationships as constraints, then use specialized theory solvers to find satisfying program assignments.
- Search Techniques: Stochastic local search, including genetic algorithms, provides another strategy for exploring program spaces.
3 LEARNING INDUCTIVE PROGRAM SYNTHESIS (LIPS)
Learning Inductive Program Synthesis combines a DSL, generated training data, a model predicting program attributes from examples, and a search procedure guided by those predictions. The attribute distribution links machine learning to search by ordering candidate programs.
- LIPS consists of a DSL, data-generation procedure, machine-learning model, and search procedure guided by predicted program attributes.
- DSL and Attributes: The DSL must capture target problems while remaining restricted enough to limit search difficulty.
- DSL and Attributes: An attribute function maps DSL programs to finite vectors, and the model predicts q(a | E) from input-output examples to order the search.
- DSL and Attributes: More abstract attributes can improve performance compared with treating the entire program as the attribute.
- Data Generation: LIPS data generation pairs sampled DSL programs and their attributes with accompanying input-output examples, ideally at million-program scale.
- Machine Learning Model: The machine-learning model estimates a distribution over attributes conditioned on examples, using observed training attributes with a maximum-likelihood objective.
- Search: The search component interfaces with an existing solver and uses q(a | E) to guide its exploration of program space.
4 DEEPCODER
DeepCoder instantiates LIPS by predicting program attributes from input-output examples and using those predictions to guide search over a restricted DSL. Its search integration includes DFS, Sort and add enumeration, Sketch, and λ2, with a theoretical basis for ranking functions by marginal probabilities.
- Domain specific language and attributes: The DSL represents programs as sequences of function calls over singleton integers and integer arrays, with the final function's return value as output.The DSL includes first-order and higher-order functions and permits internal branching or looping within a linear sequence of calls.
- Data generation: The dataset is generated by enumerating DSL programs, pruning redundant or equivalent programs, and propagating output constraints backward to construct valid inputs.Equivalence may be overapproximated through identical behavior on selected inputs.
- Machine learning model: DeepCoder maps input-output examples to predictions of high-level functions, then uses those attributes to guide search rather than directly generating source code.The model uses an encoder-decoder architecture: the encoder maps examples to a latent vector, and the decoder predicts program attributes.
- Search: DFS orders candidate functions by predicted probabilities, while Sort and add incrementally expands an active function set and restarts search after failure.Sort and add can re-explore parts of the search space when the active set grows.
- Search: Sketch and λ2 incorporate the same predictions by restricting function-hole possibilities or selecting libraries according to the neural network's predicted functions.Sketch is SMT-based, whereas λ2 combines enumerative search with deduction.
- Theoretical analysis: Under a simplifying runtime assumption, adding functions in decreasing true marginal-probability order minimizes an upper bound on expected Sort and add runtime.The analysis treats function prediction as multi-label classification and uses Rank loss results to justify marginal-probability ranking.
5 EXPERIMENTS
Experiments evaluate DeepCoder on semantically disjoint program-synthesis tasks, comparing neural predictions with corpus-frequency priors and testing generalization across program lengths. The method produces substantial speedups in large search spaces, with gains depending on the search scheme and neural architecture.
- Experimental setup: Experiments use semantically disjoint test programs and compare neural-network-guided search with search using global function-incidence priors.The main evaluation records the time required to find programs consistent with five input-output examples.
- DeepCoder compared to baselines: T = 5 programs create a search space on the order of 10^10, and neural guidance yields significant speedups for DFS, Sort and add, and λ2 configurations.Only 100 programs are used in this experiment for computational efficiency, after checking that this does not significantly affect Table 1 results.
- DeepCoder compared to baselines: Sort and add without neural guidance exceeded the 10^4-second timeout in two cases, making the reported relative speedups crude lower bounds.The comparison uses prior probabilities of functions for the non-neural baseline.
- DeepCoder compared to baselines: Larger gains for Sort and add than DFS are hypothesized to reflect better alignment between predicting function presence anywhere and the Sort and add objective.DFS would benefit more from attributes informative about functions appearing early in a program.
- Generalization across program lengths: Across training and test lengths, Sort and add gains indicate that the neural networks generalize beyond the program lengths used for training.The search layer can correct for functions the neural network fails to predict.
- Alternative models: A GRU encoder performs almost as well as the feed-forward encoder but is more difficult to train, while an RNN decoder reaches comparable solutions only for T ≤ 2.The decoder approach is substantially harder to train than the independent binary classifiers.
6 RELATED WORK
Prior work uses machine learning to guide inductive program synthesis, but differs from DeepCoder in domain, scale, and how neural guidance integrates with search.
- Menon et al. learn from hand-coded clues in input-output examples to reweight productions in a probabilistic context-free grammar.
- DeepCoder differs by studying numerical and list programs and learning from a larger corpus of generated inductive program synthesis problems.
- Piech et al. learn joint embeddings of program states and programs for extending teacher feedback to similar programs in MOOCs.
- Alemi et al. and Loos et al. train neural components to select premises or guide intermediate proof search with automated theorem provers.
7 DISCUSSION AND FUTURE WORK
DeepCoder combines learned guidance with search to improve inductive program synthesis, while targeting simple competition-style programs and identifying important scope limitations and future extensions.
- Neural networks translate input-output cues into guidance over program-space search, improving a wide range of inductive program synthesis baselines by 1–3 orders of magnitude for many programs.
- The synthesized programs reach only the simplest programming-competition problems, while dynamic programming, search, and many richer solutions remain beyond the current system.
- The current DSL cannot express many problems and would require more primitives and flexible constructs, including loops.
- The system uses five input-output examples with relatively large integers, which may be more informative than typical smaller examples.
- Future work includes better source-code data generation and incorporating natural-language problem descriptions to reduce the information required from examples.
B EXPERIMENTAL RESULTS
The experiments compare several search procedures on held-out programs using computation-time plots, including tests where program length exceeds the neural network’s training length.
- The results section presents raw computation times for search procedures after earlier experiments showed speedups from the LIPS framework.
- Figure 5 compares DFS, enumerative Sort-and-add, λ2 and Sketch Sort-and-add, and Beam search on 500 held-out length-3 test programs.
- Beam-search steps arise because the considered beam size doubles until the 1000-second timeout.
- Figure 6 compares DFS, enumerative Sort-and-add, and λ2 Sort-and-add on 100 length-5 test programs.
- For the length-5 evaluation, the neural network was trained on programs of length 4.
C THE NEURAL NETWORK
The neural network encodes sets of input-output examples into a latent representation and decodes that representation into predictions about functions in the source program.
- Each input-output example is padded to maximum length L and represented with input and output types plus a special NULL value.
- Integers in the valid range −256 to 255 receive learned embeddings in E = 20 dimensions, including an embedding for NULL.
- The encoder concatenates type and value representations, processes them through H = 3 hidden layers of K = 256 sigmoid units, and averages example encodings.
- The decoder independently classifies each DSL function to predict whether it appears in the ground-truth source code.
- A two-dimensional developmental experiment learned embeddings representing magnitude, sign, and evenness of integers.
D DEPTH-FIRST SEARCH
Depth-first search enumerates candidate programs up to a maximum length, reuses prefix evaluations across examples, and can prioritize functions using neural-network predictions. The implementation explores roughly 3 × 10^6 programs per second.
- D DEPTH-FIRST SEARCH: DFS searches programs up to maximum length T by recursively filling instructions and their arguments before trying another first instruction.The search uses an optimized C++ implementation.
- D DEPTH-FIRST SEARCH: A candidate is a solution only if it matches all M = 5 input-output examples.Each candidate is evaluated on all examples and compared with the corresponding outputs.
- D DEPTH-FIRST SEARCH: Prefix-result caching reuses evaluations of program prefixes across candidate extensions, reducing repeated computation during search.
- D DEPTH-FIRST SEARCH: ∼3 × 10^6 programs per second is the approximate speed at which the implementation explores the search space.
- D DEPTH-FIRST SEARCH: DFS can order functions by their predicted neural-network probabilities, assigning higher-order functions the minimum probability of their constituent function and lambda.
E TRAINING LOSS FUNCTION
The paper frames component prediction as multilabel classification and uses marginal probabilities with rank loss to guide Sort and add search. Under the runtime model, lower rank loss bounds the search overhead, while the DSL supplies the candidate operations.
- E TRAINING LOSS FUNCTION: Program-component prediction is formulated as multilabel classification over C = 34 functions appearing in the program.
- E TRAINING LOSS FUNCTION: Hamming loss counts incorrect labels, Rank loss counts incorrectly ordered relevant–irrelevant pairs, and Subset Zero-One loss requires every label to be correct.
- E TRAINING LOSS FUNCTION: Bayes-optimal Hamming and Rank decisions can be computed from marginal probabilities, so label dependencies need not be modeled for these losses.
- E TRAINING LOSS FUNCTION: Negative cross entropy trains the neural network to estimate marginal probabilities, making it suitable for predictions optimized under Rank loss.
- E TRAINING LOSS FUNCTION: For a program of length T and active set size C_A, Sort and add runtime is bounded proportionally by C_A^T.
- E TRAINING LOSS FUNCTION: Rank loss upper-bounds the redundant functions added before success, so for constant T minimizing Rank loss minimizes the runtime upper bound.
- E TRAINING LOSS FUNCTION: The DSL includes first-order array operations and higher-order functions with integer, Boolean, and binary-integer lambdas.
G ANALYSIS OF TRAINED NEURAL NETWORKS
The trained network’s conditional confusion matrix measures false-positive predictions conditioned on ground-truth attributes. It reveals systematic confusion among related operations, common overpredictions, and lambda pairs with similar output behavior.
- G ANALYSIS OF TRAINED NEURAL NETWORKS: Each confusion-matrix entry averages the predicted probability of attribute j among programs containing attribute i but not attribute j.
- G ANALYSIS OF TRAINED NEURAL NETWORKS: Rows represent present ground-truth attributes, columns represent falsely predicted attributes, and reordered matrices expose blocks of difficult-to-distinguish instructions.
- G ANALYSIS OF TRAINED NEURAL NETWORKS: HEAD, LAST, ACCESS, MINIMUM, and MAXIMUM are especially confused because they each select a single array element.
- G ANALYSIS OF TRAINED NEURAL NETWORKS: FILTER, (>0), (<0), (%2==1), (%2==0), MIN, MAX, (+), (-), and ZIPWITH are predicted frequently regardless of the ground-truth program.
- G ANALYSIS OF TRAINED NEURAL NETWORKS: The network has difficulty distinguishing (+) from (-), (+1) from (-1), and (/2), (/3), and (/4).
- G ANALYSIS OF TRAINED NEURAL NETWORKS: Programs using (**2) are often mistaken for programs using (*), presumably because both can produce large output values.