# Just-in-Time Learning for Bottom-Up Enumerative Synthesis

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

## Key facts

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

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

- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [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)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [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)
- [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)
- [Can You Improve My Code? Optimizing Programs with Local Search](https://mlsanity.com/paper/2307.05603/) (2023)
- [Modelling Program Spaces in Program Synthesis with Constraints](https://mlsanity.com/paper/2508.00005/) (2025)
- [Herb.jl: A Unifying Program Synthesis Library](https://mlsanity.com/paper/2510.09726/) (2025)
- [Neuro-Symbolic Regex Synthesis Framework via Neural Example Splitting](https://mlsanity.com/paper/2205.11258/) (2022)
- [mlirSynth: Automatic, Retargetable Program Raising in Multi-Level IR using Program Synthesis](https://mlsanity.com/paper/2310.04196/) (2023)
- [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025)
- [Narcissus: Program Synthesis Using Context-Aware LLM Approximations](https://mlsanity.com/paper/2608.25657/) (2026)

## Abstract (arXiv)

A key challenge in program synthesis is the astronomical size of the search space the synthesizer has to explore. In response to this challenge, recent work proposed to guide synthesis using learned probabilistic models. Obtaining such a model, however, might be infeasible for a problem domain where no high-quality training data is available. In this work we introduce an alternative approach to guided program synthesis: instead of training a model ahead of time we show how to bootstrap one just in time, during synthesis, by learning from partial solutions encountered along the way. To make the best use of the model, we also propose a new program enumeration algorithm we dub guided bottom-up search, which extends the efficient bottom-up search with guidance from probabilistic models. We implement this approach in a tool called Probe, which targets problems in the popular syntax-guided synthesis (SyGuS) format. We evaluate Probe on benchmarks from the literature and show that it achieves significant performance gains both over unguided bottom-up search and over a state-of-the-art probability-guided synthesizer, which had been trained on a corpus of existing solutions. Moreover, we show that these performance gains do not come at the cost of solution quality: programs generated by Probe are only slightly more verbose than the shortest solutions and perform no unnecessary case-splitting.