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:
- 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.
- 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.
- 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.
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.
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