# AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 27 May 2024.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Imitating Human Behaviour with Diffusion Models](https://mlsanity.com/paper/2301.10677/) (2023)
- [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [LILO: Learning Interpretable Libraries by Compressing and Documenting Code](https://mlsanity.com/paper/2310.19791/) (2023)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [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)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [ShapeCoder: Discovering Abstractions for Visual Programs from Unstructured Primitives](https://mlsanity.com/paper/2305.05661/) (2023)
- [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)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [Unraveling the ARC Puzzle: Mimicking Human Solutions with Object-Centric Decision Transformer](https://mlsanity.com/paper/2306.08204/) (2023)
- [Large Language Model (LLM) as a System of Multiple Expert Agents: An Approach to solve the Abstraction and Reasoning Corpus (ARC) Challenge](https://mlsanity.com/paper/2310.05146/) (2023)
- [FrAngel: Component-Based Synthesis with Control Structures](https://mlsanity.com/paper/1811.05175/) (2018)
- [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)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)

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

- [DISC: Dynamic Decomposition Improves LLM Inference Scaling](https://mlsanity.com/paper/2502.16706/) (2025)
- [Herb.jl: A Unifying Program Synthesis Library](https://mlsanity.com/paper/2510.09726/) (2025)

## Abstract (arXiv)

LambdaBeam is a state-of-the-art, execution-guided algorithm for program synthesis that utilizes higher-order functions, lambda functions, and iterative loops within a Domain-Specific Language (DSL). LambdaBeam generates each program from scratch but does not take advantage of the frequent recurrence of program blocks or subprograms commonly found in specific domains, such as loops for list traversal. To address this limitation, we introduce AbstractBeam: a novel program synthesis framework designed to enhance LambdaBeam by leveraging Library Learning. AbstractBeam identifies and integrates recurring program structures into the DSL, optimizing the synthesis process. Our experimental evaluations demonstrate that AbstractBeam statistically significantly (p < 0.05) outperforms LambdaBeam in the integer list manipulation domain. Beyond solving more tasks, AbstractBeam's program synthesis is also more efficient, requiring less time and fewer candidate programs to generate a solution. Furthermore, our findings indicate that Library Learning effectively enhances program synthesis in domains that are not explicitly designed to showcase its advantages, thereby highlighting the broader applicability of Library Learning.