# LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 42 references that are in the map.
- First posted on arXiv 3 Jun 2023.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [A Survey of Machine Learning for Big Code and Naturalness](https://mlsanity.com/paper/1709.06182/) (2017)
- [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)
- [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)
- [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)
- [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)
- [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)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [An Empirical Investigation of Beam-Aware Training in Supertagging](https://mlsanity.com/paper/2010.04980/) (2020)

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

- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model](https://mlsanity.com/paper/2503.08738/) (2025)
- [Beyond Either-Or Reasoning: Transduction and Induction as Cooperative Problem-Solving Paradigms](https://mlsanity.com/paper/2505.14744/) (2025)
- [Bayesian Inverse Physics for Neuro-Symbolic Robot Learning](https://mlsanity.com/paper/2506.08756/) (2025)
- [Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer](https://mlsanity.com/paper/2608.03461/) (2026)

## Abstract (arXiv)

Search is an important technique in program synthesis that allows for adaptive strategies such as focusing on particular search directions based on execution results. Several prior works have demonstrated that neural models are effective at guiding program synthesis searches. However, a common drawback of those approaches is the inability to handle iterative loops, higher-order functions, or lambda functions, thus limiting prior neural searches from synthesizing longer and more general programs. We address this gap by designing a search algorithm called LambdaBeam that can construct arbitrary lambda functions that compose operations within a given DSL. We create semantic vector representations of the execution behavior of the lambda functions and train a neural policy network to choose which lambdas to construct during search, and pass them as arguments to higher-order functions to perform looping computations. Our experiments show that LambdaBeam outperforms neural, symbolic, and LLM-based techniques in an integer list manipulation domain.