# Efficient Synthesis with Probabilistic Constraints

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2019.

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

- [A Hazard Analysis Framework for Code Synthesis Large Language Models](https://mlsanity.com/paper/2207.14157/) (2022)
- [Synthesizing Machine Learning Programs with PAC Guarantees via Statistical Sketching](https://mlsanity.com/paper/2110.05390/) (2021)

## Abstract (arXiv)

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.