Scaling Neural Program Synthesis with Distribution-Based Search

Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, Akarsh Nayan Potta

Introduction

Program synthesis—the automated generation of code from input-output (I/O) examples—is a fundamental challenge in computer science. The search space for programs is vast and grows exponentially, creating a "needle in a haystack" problem. Modern "neural-symbolic" systems address this by using a two-stage process: first, a neural network predicts the likelihood of various code structures; second, a symbolic search algorithm explores the program space based on these predictions. While much research focuses on improving neural predictions, the efficiency of the search algorithm itself is often overlooked. This paper introduces a formal framework for "distribution-based search" to optimize this second stage.

Methods and Framework

The authors propose a theoretical framework to evaluate search algorithms based on "loss," defined as the expected number of programs checked before finding the correct solution. Central to this framework are three technical innovations:

  1. HEAP SEARCH: A deterministic, bottom-up enumerative algorithm. Unlike traditional top-down $A^*$ search, HEAP SEARCH utilizes heaps and hash tables to generate programs in strictly non-increasing order of probability. Its bottom-up nature allows for caching and reusing sub-program evaluations, significantly reducing redundant computation.
  2. SQRT SAMPLING: A probabilistic approach based on a counter-intuitive mathematical proof. The authors demonstrate that to minimize the expected number of attempts when sampling, one should not sample directly from the predicted distribution $D$. Instead, sampling from a distribution proportional to the square root of those probabilities ($\sqrt{D}$) is "loss-optimal," preventing the search from becoming trapped in high-probability but incorrect subspaces.
  3. Grammar Splitter: To leverage parallel computing, the authors developed a "hill-climbing" algorithm that partitions a Context-Free Grammar (CFG) into $k$ disjoint, balanced sub-grammars. This allows multiple CPU cores to search unique subspaces simultaneously without overlap.
The neural-symbolic program synthesis pipeline, illustrating the flow from DSL and syntactic constraints to the final search algorithm.

Key Insights

A major contribution of this work is the formalization of search as a transformation of a probability distribution into a sequence of guesses. This perspective led to the "Square Root Rule," proving that naive sampling is mathematically inefficient. Furthermore, the shift from top-down to bottom-up search (HEAP SEARCH) avoids the repeated evaluation of identical logic, a common bottleneck in $A^*$ and BFS.

Results and Performance

The proposed methods were evaluated on synthetic PCFGs and real-world benchmarks like DeepCoder and DreamCoder.

  • Efficiency: On the DreamCoder dataset, HEAP SEARCH was found to be six times faster than $A^*$. It solved 97 out of 137 tasks within a fixed time budget, outperforming all baselines including BFS, Sort&Add, and Threshold.
  • Scaling: The Grammar Splitter achieved near-linear speedup. For instance, using 6 CPUs with HEAP SEARCH generated 7.6 times more programs than a 2-CPU configuration, demonstrating the method's ability to effectively utilize additional compute resources.
Cumulative probability of finding a solution over time for various search algorithms. Heap Search and SQRT Sampling significantly outperform traditional methods.

Conclusion and Future Work

While highly effective for CFG-based synthesis, the current framework has limitations. It is not yet directly applicable to autoregressive large language models (LLMs) that generate code token-by-token, though the principles of SQRT SAMPLING may be adaptable. Additionally, the memory overhead of HEAP SEARCH's bottom-up caching remains a consideration for future optimization. Nonetheless, this work provides a rigorous mathematical foundation for scaling program synthesis through optimized distribution-based search.

Summary updated

Abstract

We consider the problem of automatically constructing computer programs from input-output examples. We investigate how to augment probabilistic and neural program synthesis methods with new search algorithms, proposing a framework called distribution-based search. Within this framework, we introduce two new search algorithms: Heap Search, an enumerative method, and SQRT Sampling, a probabilistic method. We prove certain optimality guarantees for both methods, show how they integrate with probabilistic and neural techniques, and demonstrate how they can operate at scale across parallel compute environments. Collectively these findings offer theoretical and applied studies of search algorithms for program synthesis that integrate with recent developments in machine-learned program synthesizers.
BibTeX
@inproceedings{fijalkow2022scaling,
  author = {Nathanaël Fijalkow and Guillaume Lagarde and Théo Matricon and Kevin Ellis and Pierre Ohlmann and Akarsh Nayan Potta},
  title = {{Scaling Neural Program Synthesis with Distribution-Based Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20616},
}
Figure