# Program Synthesis with Best-First Bottom-Up Search

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 6 Oct 2023.

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

- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [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)
- [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)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [TF-Coder: Program Synthesis for Tensor Manipulations](https://mlsanity.com/paper/2003.09040/) (2020)
- [Automatic Program Synthesis of Long Programs with a Learned Garbage Collector](https://mlsanity.com/paper/1809.04682/) (2018)
- [Just-in-Time Learning for Bottom-Up Enumerative Synthesis](https://mlsanity.com/paper/2010.08663/) (2020)
- [Learning to Represent Programs with Property Signatures](https://mlsanity.com/paper/2002.09030/) (2020)
- [Synthetic Datasets for Neural Program Synthesis](https://mlsanity.com/paper/1912.12345/) (2019)
- [Program Synthesis using Abstraction Refinement](https://mlsanity.com/paper/1710.07740/) (2017)
- [Scaling Neural Program Synthesis with Distribution-based Search](https://mlsanity.com/paper/2110.12485/) (2021)
- [SyGuS-Comp 2016: Results and Analysis](https://mlsanity.com/paper/1611.07627/) (2016)

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

- [Relational decomposition for program synthesis](https://mlsanity.com/paper/2408.12212/) (2024)
- [Gradient-Based Program Synthesis with Neurally Interpreted Languages](https://mlsanity.com/paper/2604.18907/) (2026)
- [Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces](https://mlsanity.com/paper/2410.12166/) (2024)
- [Herb.jl: A Unifying Program Synthesis Library](https://mlsanity.com/paper/2510.09726/) (2025)
- [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025)
- [Narcissus: Program Synthesis Using Context-Aware LLM Approximations](https://mlsanity.com/paper/2608.25657/) (2026)
- [Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search](https://mlsanity.com/paper/2609.24025/) (2026)

## Abstract (arXiv)

Cost-guided bottom-up search (BUS) algorithms use a cost function to guide the search to solve program synthesis tasks. In this paper, we show that current state-of-the-art cost-guided BUS algorithms suffer from a common problem: they can lose useful information given by the model and fail to perform the search in a best-first order according to a cost function. We introduce a novel best-first bottom-up search algorithm, which we call Bee Search, that does not suffer information loss and is able to perform cost-guided bottom-up synthesis in a best-first manner. Importantly, Bee Search performs best-first search with respect to the generation of programs, i.e., it does not even create in memory programs that are more expensive than the solution program. It attains best-first ordering with respect to generation by performing a search in an abstract space of program costs. We also introduce a new cost function that better uses the information provided by an existing cost model. Empirical results on string manipulation and bit-vector tasks show that Bee Search can outperform existing cost-guided BUS approaches when employing more complex domain-specific languages (DSLs); Bee Search and previous approaches perform equally well with simpler DSLs. Furthermore, our new cost function with Bee Search outperforms previous cost functions on string manipulation tasks.