Scaling Neural Program Synthesis with Distribution-based Search
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.
Code (1)
Tasks
Program SynthesisSimilar Papers 제목 키워드 기반
Beyond the Training Distribution: Mapping Generalization Boundaries in Neural Program Synthesis
Large-scale transformers achieve impressive results on program synthesis benchmarks, yet their true generalization capabilities remain obscured by data contamination and opaque training corpora. To rigorously assess whet…
Program SynthesisIterative Genetic Improvement: Scaling Stochastic Program Synthesis
Program synthesis aims to {\it automatically} find programs from an underlying programming language that satisfy a given specification. While this has the potential to revolutionize computing, how to search over the vast…
Program SynthesisSearching Latent Program Spaces
Program synthesis methods aim to automatically generate programs restricted to a language that can explain a given specification of input-output pairs. While purely symbolic approaches suffer from a combinatorial search …
ARCProgram inductionProgram SynthesisTest-time AdaptationNeural Program Synthesis with a Differentiable Fixer
We present a new program synthesis approach that combines an encoder-decoder based synthesis architecture with a differentiable program fixer. Our approach is inspired from the fact that human developers seldom get their…
DecoderProgram SynthesisOptimal Neural Program Synthesis from Multimodal Specifications
Multimodal program synthesis, which leverages different types of user input to synthesize a desired program, is an attractive way to scale program synthesis to challenging settings; however, it requires integrating noisy…
Program Synthesisvalid