# CrossBeam: Learning to Search in Bottom-Up Program Synthesis

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 20 Mar 2022.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [A Survey of Machine Learning for Big Code and Naturalness](https://mlsanity.com/paper/1709.06182/) (2017)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (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)
- [SmBoP: Semi-autoregressive Bottom-up Semantic Parsing](https://mlsanity.com/paper/2010.12412/) (2020)
- [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)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Learning to Search Better Than Your Teacher](https://mlsanity.com/paper/1502.02206/) (2015)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Turning 30: New Ideas in Inductive Logic Programming](https://mlsanity.com/paper/2002.11002/) (2020)
- [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)
- [Incremental Sampling Without Replacement for Sequence Models](https://mlsanity.com/paper/2002.09067/) (2020)
- [Just-in-Time Learning for Bottom-Up Enumerative Synthesis](https://mlsanity.com/paper/2010.08663/) (2020)
- [Latent Programmer: Discrete Latent Codes for Program Synthesis](https://mlsanity.com/paper/2012.00377/) (2020)
- [Learning to Represent Programs with Property Signatures](https://mlsanity.com/paper/2002.09030/) (2020)
- [The Three Pillars of Machine Programming](https://mlsanity.com/paper/1803.07244/) (2018)
- [FrAngel: Component-Based Synthesis with Control Structures](https://mlsanity.com/paper/1811.05175/) (2018)
- [Learning Beam Search Policies via Imitation Learning](https://mlsanity.com/paper/1811.00512/) (2018)
- [Predicate Invention by Learning From Failures](https://mlsanity.com/paper/2104.14426/) (2021)
- [An Empirical Investigation of Beam-Aware Training in Supertagging](https://mlsanity.com/paper/2010.04980/) (2020)

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

- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Clover: Closed-Loop Verifiable Code Generation](https://mlsanity.com/paper/2310.17807/) (2023)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (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)
- [From Perception to Programs: Regularize, Overparameterize, and Amortize](https://mlsanity.com/paper/2206.05922/) (2022)
- [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)
- [Relational decomposition for program synthesis](https://mlsanity.com/paper/2408.12212/) (2024)
- [Learning big logical rules by joining small rules](https://mlsanity.com/paper/2401.16215/) (2024)
- [Relational program synthesis with numerical reasoning](https://mlsanity.com/paper/2210.00764/) (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)
- [NESTER: An Adaptive Neurosymbolic Method for Causal Effect Estimation](https://mlsanity.com/paper/2211.04370/) (2022)
- [Herb.jl: A Unifying Program Synthesis Library](https://mlsanity.com/paper/2510.09726/) (2025)
- [Codoku: Renewable Program-Reasoning Challenges for Frontier Coding Agents](https://mlsanity.com/paper/2609.34661/) (2026)

## Abstract (arXiv)

Many approaches to program synthesis perform a search within an enormous space of programs to find one that satisfies a given specification. Prior works have used neural models to guide combinatorial search algorithms, but such approaches still explore a huge portion of the search space and quickly become intractable as the size of the desired program increases. To tame the search space blowup, we propose training a neural model to learn a hands-on search policy for bottom-up synthesis, instead of relying on a combinatorial search algorithm. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs, taking into account the search history and partial program executions. Motivated by work in structured prediction on learning to search, CrossBeam is trained on-policy using data extracted from its own bottom-up searches on training tasks. We evaluate CrossBeam in two very different domains, string manipulation and logic programming. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.