Lune

OOPSLA2020Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers26

  1. Is Programming by Example Solved by LLMs?Wen-Ding Li, Kevin EllisNeurIPS 2024 · 45 citations
  2. 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
  3. CrossBeam: Learning to Search in Bottom-Up Program SynthesisKensen Shi, Hanjun Dai, Kevin Ellis, Charles SuttonICLR 2022 · 28 citations
  4. Latent Programmer: Discrete Latent Codes for Program SynthesisJoey Hong, David Dohan, Rishabh Singh, Charles Sutton et al.ICML 2021 · 25 citations
  5. 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

  1. Program Synthesis Using Deduction-Guided Reinforcement LearningYanju Chen, Chenglong Wang, Osbert Bastani, Isil Dillig et al.CAV 2020 · 30 citations

Related papers

  1. Combining the top-down propagation and bottom-up enumeration for inductive program synthesisWoosuk LeePOPL 2021 · 34 citations
  2. BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided ExplorationAugustus Odena, Kensen Shi, David Bieber, Rishabh Singh et al.ICLR 2021 · 60 citations
  3. Guiding Enumerative Program Synthesis with Large Language ModelsYixuan Li, Julian Parsert, Elizabeth PolgreenCAV 2024 · 19 citations
  4. Reinforcement Learning and Data-Generation for Syntax-Guided SynthesisJulian Parsert, Elizabeth PolgreenAAAI 2024 · 7 citations
  5. Inductive Program Synthesis via Iterative Forward-Backward Abstract InterpretationYongho Yoon, Woosuk Lee, Kwangkeun YiPLDI 2023 · 15 citations
Dusk over the sea between two cliffs drawn in fine vertical lines