Accelerating search-based program synthesis using learned probabilistic models
By Woosuk Lee, Kihong Heo, Rajeev Alur, Mayur Naik. 2018
126 citations recorded by the source corpus.
A key challenge in program synthesis concerns how to efficiently search for the desired program in the space of possible programs. We propose a general approach to accelerate search-based program synthesis by biasing the search towards likely programs. Our approach targets a standard formulation, syntax-guided synthesis (SyGuS), by extending the grammar of possible programs with a probabilistic model dictating the likelihood of each program. We develop a weighted search algorithm to efficiently enumerate programs in order of their likelihood. We also propose a method based on transfer learning that enables to effectively learn a powerful model, called probabilistic higher-order grammar, from known solutions in a domain. We have implemented our approach in a tool called Euphony and evaluate it on SyGuS benchmark problems from a variety of domains. We show that Euphony can learn good models using easily obtainable solutions, and achieves significant performance gains over existing general-purpose as well as domain-specific synthesizers.
Subfields: Artificial Intelligence, Information Systems, Software, Natural Language Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Charles Sutton
- Rishabh Singh
- Augustus Odena
- Sergey Levine
- Ion Stoica
- Koushik Sen
- Kensen Shi
- David Bieber
In Information Systems
- Rishabh Singh
- Charles Sutton
- Koushik Sen
- David Bieber
- Kensen Shi
- Augustus Odena
- Rohan Bavishi
- Ion Stoica
In Software
- Koushik Sen
- Rishabh Singh
- Charles Sutton
- David Bieber
- Caroline Lemieux
- Augustus Odena
- Rohan Bavishi
- Suresh Parthasarathy
In Natural Language Processing
- Charles Sutton
- Koushik Sen
- Rishabh Singh
- Augustus Odena
- David Bieber
- Rohan Bavishi
- Kensen Shi
- Ion Stoica
Citations in the corpus
- Large Language Models Are Human-Level Prompt Engineers (2022, methodology): “Using inference models is a standard practice to speed up the search by restricting the search space to a limited space of possible expressions (Menon et al., 2013; Lee et al., 2018; Devlin et al., 2017; Ellis et al., 2021).”
- Jigsaw: Large Language Models meet Program Synthesis (2021, methodology): “The literature on using machine learning for program synthesis is vast [8, 17, 18, 21, 22, 25, 28, 35, 41] and we restrict to works which are closest to Jigsaw (synthesizing code for large APIs using large models and multi-modal specifications).”
- BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration (2020, methodology): “Previous work has also considered using learning within syntax guided search over programs (Yin & Neubig, 2017; Lee et al., 2018), but because these methods are top-down, it is much more difficult to guide them by execution information.”
- This paper is included in the Proceedings of the 2022 USENIX Annual Technical Conference. (unknown): “We refer to syntax-guided synthesis [36, 37], a common approach in program synthesis that finds the desired program by searching the program space described by a grammar.”
- AutoPandas: neural-backed generators for program synthesis (2019, background): “This is in contrast to the use of probabilistic models in past work such as that of Lee et al. [2018] and Devlin et al. [2017] where these models are trained over the full language.”