# BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2020.

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

- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Reasoning Like Program Executors](https://mlsanity.com/paper/2201.11473/) (2022)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Opening the AI black box: program synthesis via mechanistic interpretability](https://mlsanity.com/paper/2402.05110/) (2024)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [Pix2Code: Learning to Compose Neural Visual Concepts as Programs](https://mlsanity.com/paper/2402.08280/) (2024)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis](https://mlsanity.com/paper/2405.15880/) (2024)
- [Patterns Over Principles: The Fragility of Inductive Reasoning in LLMs under Noisy Observations](https://mlsanity.com/paper/2502.16169/) (2025)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [Hierarchical Neural Program Synthesis](https://mlsanity.com/paper/2303.06018/) (2023)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)
- [Compositional Generalization and Decomposition in Neural Program Synthesis](https://mlsanity.com/paper/2204.03758/) (2022)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [Gradient-Based Program Synthesis with Neurally Interpreted Languages](https://mlsanity.com/paper/2604.18907/) (2026)
- [CORNET: Learning Table Formatting Rules By Example](https://mlsanity.com/paper/2208.06032/) (2022)
- [Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis](https://mlsanity.com/paper/2307.09564/) (2023)
- [Legal Rule Induction: Towards Generalizable Principle Discovery from Analogous Judicial Precedents](https://mlsanity.com/paper/2505.14104/) (2025)
- [Neural Program Synthesis with Query](https://mlsanity.com/paper/2205.07857/) (2022)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces](https://mlsanity.com/paper/2410.12166/) (2024)
- [Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model](https://mlsanity.com/paper/2503.08738/) (2025)
- [ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis](https://mlsanity.com/paper/2605.05485/) (2026)
- [Iterative Genetic Improvement: Scaling Stochastic Program Synthesis](https://mlsanity.com/paper/2202.13040/) (2022)
- [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025)
- [Structural Grid Descriptors Predict Within-Task Solver Success on ARC-AGI](https://mlsanity.com/paper/2606.09026/) (2026)
- [Narcissus: Program Synthesis Using Context-Aware LLM Approximations](https://mlsanity.com/paper/2608.25657/) (2026)

## Abstract (arXiv)

Program synthesis is challenging largely because of the difficulty of search in a large space of programs. Human programmers routinely tackle the task of writing complex programs by writing sub-programs and then analyzing their intermediate results to compose them in appropriate ways. Motivated by this intuition, we present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This is a powerful combination because of several emergent properties. First, in bottom-up search, intermediate programs can be executed, providing semantic information to the neural network. Second, given the concrete values from those executions, we can exploit rich features based on recent work on property signatures. Finally, bottom-up search allows the system substantial flexibility in what order to generate the solution, allowing the synthesizer to build up a program from multiple smaller sub-programs. Overall, our empirical evaluation finds that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches. We demonstrate the effectiveness of our technique on two datasets, one from the SyGuS competition and one of our own creation.