Learning to Combine Per-Example Solutions for Neural Program Synthesis

Disha Shrivastava, Hugo Larochelle, Daniel Tarlow

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.

Introduction

Program synthesis—the "holy grail" of software engineering where a computer writes its own code based on input-output (IO) examples—is notoriously difficult due to the astronomically large search space of possible programs. Most current "neural-guided" systems, such as DeepCoder or PCCoder, attempt to find a program that satisfies all provided IO examples simultaneously. This approach is often inefficient, as it misses the valuable "cues" hidden in partial solutions that might satisfy only a subset of the constraints.

In contrast, human programmers often iterate, writing code that passes a few unit tests before refining it to handle the rest. This paper formalizes this intuition through N-PEPS (Neural Per-Example Program Synthesis), a framework that decomposes the synthesis task into finding per-example (PE) solutions and then merging them into a global program.

Methodology: The N-PEPS Framework

The N-PEPS system operates in two distinct phases:

  1. Per-Example (PE) Searches: The system performs rapid searches to find programs that satisfy only one specific IO example. These are significantly easier to locate than a global solution.
  2. The Cross Aggregator (CA): This core module uses a multi-head attention mechanism to intelligently combine fragments from PE solutions.
Overview of the N-PEPS architecture, illustrating the two-stage process of finding per-example solutions and aggregating them via the Cross Aggregator.

Crucially, the CA does not merely analyze the syntax of PE solutions. Instead, it examines execution states. By executing the PE programs and the partial global program, the model uses the resulting data states to determine which PE solution is most relevant to the next step of the global synthesis. This allows the model to "attend" to the most promising logic across different partial solutions.

Experimental Setup

The researchers evaluated N-PEPS using a Domain-Specific Language (DSL) for list and integer operations (e.g., SORT, FILTER, MAP). Two experimental settings were used:

  • E1: 105,036 training programs with lengths up to 4 lines.
  • E2: 189,328 training programs with lengths up to 12 lines, testing generalization up to 14 lines.

Results and Key Insights

N-PEPS significantly outperformed the state-of-the-art baseline, PCCoder, across multiple metrics. In the E1 task, N-PEPS achieved an 87.07% success rate, compared to PCCoder’s 77.75%.

Performance metrics including success ratio tables, time-to-solution plots, and attention score visualizations for N-PEPS and baselines.

Key findings include:

  • Efficiency: N-PEPS finds solutions much faster than baselines. It reaches a 60% success rate in under 1 second, while PCCoder requires nearly 4 seconds to reach the same threshold.
  • Generalization: The Cross Aggregator is not a simple copy-paste mechanism. It can generate new operators not present in any PE solution by recognizing that the "intent" of a PE solution is close to a different, more appropriate operator in the embedding space.
  • Scaling: As program complexity increased in the E2 setting, N-PEPS maintained its lead, demonstrating superior handling of large search spaces under tight time budgets (5-second timeouts).

Conclusion and Future Work

N-PEPS demonstrates that leveraging per-example solutions through execution-aware attention is a powerful strategy for program synthesis. While currently limited to a DSL without loops or complex conditionals, the framework provides a foundation for more sophisticated synthesis tasks. Future work includes extending the approach to languages like Karel and parallelizing the PE search phase to further reduce synthesis time.

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. The code, data and trained models for our work can be found at https://github.com/shrivastavadisha/N-PEPS.
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