# Scaling Neural Program Synthesis with Distribution-based Search

arXiv: https://arxiv.org/abs/2110.12485 · HTML: https://mlsanity.com/paper/2110.12485/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 15 of 15)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples](https://mlsanity.com/paper/1804.01186/) (2018)
- [TF-Coder: Program Synthesis for Tensor Manipulations](https://mlsanity.com/paper/2003.09040/) (2020)
- [Program Synthesis using Conflict-Driven Learning](https://mlsanity.com/paper/1711.08029/) (2017)
- [Automatic Program Synthesis of Long Programs with a Learned Garbage Collector](https://mlsanity.com/paper/1809.04682/) (2018)
- [Incremental Sampling Without Replacement for Sequence Models](https://mlsanity.com/paper/2002.09067/) (2020)
- [Neural Program Search: Solving Programming Tasks from Description and Examples](https://mlsanity.com/paper/1802.04335/) (2018)
- [Data Generation for Neural Programming by Example](https://mlsanity.com/paper/1911.02624/) (2019)

## Built on by (most cited first, 6 of 6)

- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Towards Efficient Neurally-Guided Program Induction for ARC-AGI](https://mlsanity.com/paper/2411.17708/) (2024)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)
- [Synthesizing Visual Concepts as Vision-Language Programs](https://mlsanity.com/paper/2511.18964/) (2025)
- [NeuroSynt: A Neuro-symbolic Portfolio Solver for Reactive Synthesis](https://mlsanity.com/paper/2401.12131/) (2024)
- [Playing ZendoWorld: Challenging AI Agents on Active Visual Concept Induction](https://mlsanity.com/paper/2607.08233/) (2026)

## Abstract (arXiv)

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.