Learning to Combine Per-Example Solutions for Neural Program Synthesis

Disha Shrivastava, Hugo Larochelle, Daniel Tarlow

Overview

Instead of trying to write a program that satisfies every input-output example at once—a notoriously difficult "needle-in-a-haystack" problem—this research proposes N-PEPS (Neural Per-Example Program Synthesis). N-PEPS first finds simple programs that solve individual examples, and then uses a novel neural "Cross Aggregator" to intelligently stitch these partial solutions into a single, global program that works for all edge cases.

The Problem: The "All-or-Nothing" Bottleneck

Program synthesis is the "holy grail" of computer science: teaching a computer to write its own code based on a specification, such as a set of input-output pairs. However, the space of possible programs is virtually infinite. Current neural-guided systems typically try to find a "global solution" that satisfies all provided examples simultaneously.

The authors argue this approach is unnecessarily difficult. Imagine a human programmer: they often write a snippet that handles one test case, then another for a corner case, and finally merge those ideas. The challenge addressed here is how to automate this "divide and conquer" strategy using deep learning, specifically focusing on how to combine these "per-example" (PE) solutions when they might be contradictory or incomplete.

Methods: Divide, Conquer, and Aggregate

The authors introduce N-PEPS, which operates in two distinct stages:

  1. PE Searches: The system uses a standard neural-guided search to find programs that satisfy just one of the $N$ provided examples. Because the constraints are lower, these are much easier and faster to find than a global solution.
  2. Cross Aggregator (CA): This is the core innovation. It is a neural module based on a multi-head attention mechanism designed to synthesize the final code.
Architecture of N-PEPS showing the PE Searches and Cross Aggregator.

The Cross Aggregator works by comparing the "where we are now" (the Query: the current state of the global program being synthesized) with "what worked for individual cases" (the Keys: the execution states of the various PE solutions). It then extracts the actual code statements used in those PE solutions (the Values). By doing this, the CA learns to "attend" to the most relevant PE solution and suggest the next line of code for the global program.

Key Insights

  • Partial Success is a Strong Signal: Even if a program only solves one out of five examples, it likely contains "fragments" of the correct logic. N-PEPS treats these fragments as valuable hints rather than failures.
  • Execution-Guided Attention: The Cross Aggregator doesn't just look at the raw code of the PE solutions; it looks at the intermediate values (the state) produced when those programs run. This allows the model to understand why a certain line of code was useful in a specific context.

Key Results

The researchers evaluated their method using a Domain Specific Language (DSL) similar to the one used in the famous DeepCoder paper, testing across short programs (length up to 4) and long programs (length up to 12). To simulate realistic interactive tools (like Excel's FlashFill), they enforced a strict 5-second timeout.

Performance comparison showing N-PEPS outperforming baselines in success ratio and time efficiency.

N-PEPS significantly outperformed the state-of-the-art baseline (PCCoder) and several ablation models:

  • Overall Success Rate: On programs of length 4, N-PEPS achieved an 87.07% success rate, a substantial improvement over the 77.75% achieved by PCCoder.
  • Scaling to Complexity: On longer, more complex programs (length 12), N-PEPS maintained a success rate of ~22.7%, while the baseline dropped to ~19.7%.
  • Length Generalization: The model showed a superior ability to synthesize programs longer than those it was trained on (e.g., length 14), suggesting it learned fundamental logic rather than just memorizing structural patterns.

Limitations and Future Work

While highly effective, N-PEPS currently operates within a DSL that lacks loops and conditionals (if-then-else statements). Extending this architecture to more complex languages, like Karel, is a logical next step. Additionally, the system faces a "search budget trade-off": there is a delicate balance between spending time finding high-quality PE solutions versus leaving enough time to aggregate them into a global solution. Finally, as with all synthesis tools, generated code can contain bugs for unseen examples, necessitating caution in real-world deployment.

Summary updated

Abstract

The goal of program synthesis from examples is to find a computer program that is consistent with a given set of input-output examples. Most learning-based approaches try to find a program that satisfies all examples at once. Our work, by contrast, considers an approach that breaks the problem into two stages: (a) find programs that satisfy only one example, and (b) leverage these per-example solutions to yield a program that satisfies all examples. We introduce the Cross Aggregator neural network module based on a multi-head attention mechanism that learns to combine the cues present in these per-example solutions to synthesize a global solution. Evaluation across programs of different lengths and under two different experimental settings reveal that when given the same time budget, our technique significantly improves the success rate over PCCoder [Zohar et. al 2018] and other ablation baselines.
BibTeX
@inproceedings{shrivastava2021learning,
  author = {Disha Shrivastava and Hugo Larochelle and Daniel Tarlow},
  title = {{Learning to Combine Per-Example Solutions for Neural Program Synthesis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=BSlYk2hL20},
}
Figure