# Efficient Bottom-Up Synthesis for Programs with Local Variables

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 46 references that are in the map.
- First posted on arXiv 7 Nov 2023.

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

- [Prompting GPT-3 To Be Reliable](https://mlsanity.com/paper/2210.09150/) (2022)
- [Program Synthesis using Abstraction Refinement](https://mlsanity.com/paper/1710.07740/) (2017)
- [Multi-modal Synthesis of Regular Expressions](https://mlsanity.com/paper/1908.03316/) (2019)
- [Web Question Answering with Neurosymbolic Program Synthesis](https://mlsanity.com/paper/2104.07162/) (2021)
- [Inductive Program Synthesis Over Noisy Data](https://mlsanity.com/paper/2009.10272/) (2020)
- [WebRobot: Web Robotic Process Automation using Interactive Programming-by-Demonstration](https://mlsanity.com/paper/2203.09993/) (2022)
- [DiLogics: Creating Web Automation Programs With Diverse Logics](https://mlsanity.com/paper/2308.05828/) (2023)
- [Synthesis of Data Completion Scripts using Finite Tree Automata](https://mlsanity.com/paper/1707.01469/) (2017)
- [Relational Program Synthesis](https://mlsanity.com/paper/1809.02283/) (2018)
- [Automated Migration of Hierarchical Data to Relational Tables using Programming-by-Example](https://mlsanity.com/paper/1711.04001/) (2017)
- [Learning Abstractions for Program Synthesis](https://mlsanity.com/paper/1804.04152/) (2018)
- [Bottom-up Synthesis of Recursive Functional Programs using Angelic Execution](https://mlsanity.com/paper/2107.06253/) (2021)
- [Searching Entangled Program Spaces](https://mlsanity.com/paper/2206.07828/) (2022)

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

- [LongProc: Benchmarking Long-Context Language Models on Long Procedural Generation](https://mlsanity.com/paper/2501.05414/) (2025)
- [HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis](https://mlsanity.com/paper/2405.15880/) (2024)
- [KV Cache Offloading for Context-Intensive Tasks](https://mlsanity.com/paper/2604.08426/) (2026)

## Abstract (arXiv)

We propose a new synthesis algorithm that can efficiently search programs with local variables (e.g., those introduced by lambdas). Prior bottom-up synthesis algorithms are not able to evaluate programs with free local variables, and therefore cannot effectively reduce the search space of such programs (e.g., using standard observational equivalence reduction techniques), making synthesis slow. Our algorithm can reduce the space of programs with local variables. The key idea, dubbed lifted interpretation, is to lift up the program interpretation process, from evaluating one program at a time to simultaneously evaluating all programs from a grammar. Lifted interpretation provides a mechanism to systematically enumerate all binding contexts for local variables, thereby enabling us to evaluate and reduce the space of programs with local variables. Our ideas are instantiated in the domain of web automation. The resulting tool, Arborist, can automate a significantly broader range of challenging tasks more efficiently than state-of-the-art techniques including WebRobot and Helena.