Efficient Synthesis with Probabilistic Constraints
By Samuel Drews, Aws Albarghouthi, Loris D'antoni. 2019
10 citations recorded by the source corpus.
We consider the problem of synthesizing a program given a probabilistic specification of its desired behavior. Specifically, we study the recent paradigm of distribution-guided inductive synthesis (DIGITS), which iteratively calls a synthesizer on finite sample sets from a given distribution. We make theoretical and algorithmic contributions: (i) We prove the surprising result that DIGITS only requires a polynomial number of synthesizer calls in the size of the sample set, despite its ostensibly exponential behavior. (ii) We present a property-directed version of DIGITS that further reduces the number of synthesizer calls, drastically improving synthesis performance on a range of benchmarks.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Software, Probabilistic & Bayesian Methods, Code Generation & Program Synthesis
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
- Pamela Mishkin
- Gretchen Krueger
- Miles Brundage
- Jianfeng Gao
- Mohit Bansal
- Percy Liang
- Luke S. Zettlemoyer
- Yejin Choi
In Computational Theory and Mathematics
In Probabilistic & Bayesian Methods
Citations in the corpus
- A Hazard Analysis Framework for Code Synthesis Large Language Models (2022, background): “Deriving from programming language synthesis techniques may lead the way on how this can be carried out [9, 12, 16, 18, 32].”