Just-in-time learning for bottom-up enumerative synthesis
Shraddha Barke, Hila Peleg, Nadia Polikarpova
Abstract
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
26 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis cites CrossBeam: Learning to Search in Bottom-Up Program Synthesis
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis cites Latent Programmer: Discrete Latent Codes for Program Synthesis
- Is Programming by Example Solved by LLMs? cites CrossBeam: Learning to Search in Bottom-Up Program Synthesis
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis cites CrossBeam: Learning to Search in Bottom-Up Program Synthesis
- CrossBeam: Learning to Search in Bottom-Up Program Synthesis cites Latent Programmer: Discrete Latent Codes for Program Synthesis
Cited by top-tier papers26
- Is Programming by Example Solved by LLMs?Wen-Ding Li, Kevin EllisNeurIPS 2024 · 45 citations
- HYSYNTH: Context-Free LLM Approximation for Guiding Program SynthesisShraddha Barke, Emmanuel Anaya Gonzalez, Saketh Ram Kasibatla, Taylor Berg-Kirkpatrick et al.NeurIPS 2024 · 34 citations
- CrossBeam: Learning to Search in Bottom-Up Program SynthesisKensen Shi, Hanjun Dai, Kevin Ellis, Charles SuttonICLR 2022 · 28 citations
- Latent Programmer: Discrete Latent Codes for Program SynthesisJoey Hong, David Dohan, Rishabh Singh, Charles Sutton et al.ICML 2021 · 25 citations
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program SynthesisKensen Shi, Joey Hong, Yinlin Deng, Pengcheng Yin et al.ICLR 2024 · 21 citations
Builds on1
Related papers
- Combining the top-down propagation and bottom-up enumeration for inductive program synthesisWoosuk LeePOPL 2021 · 34 citations
- BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided ExplorationAugustus Odena, Kensen Shi, David Bieber, Rishabh Singh et al.ICLR 2021 · 60 citations
- Guiding Enumerative Program Synthesis with Large Language ModelsYixuan Li, Julian Parsert, Elizabeth PolgreenCAV 2024 · 19 citations
- Reinforcement Learning and Data-Generation for Syntax-Guided SynthesisJulian Parsert, Elizabeth PolgreenAAAI 2024 · 7 citations
- Inductive Program Synthesis via Iterative Forward-Backward Abstract InterpretationYongho Yoon, Woosuk Lee, Kwangkeun YiPLDI 2023 · 15 citations
