Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Program Synthesis

Learning programs from examples and specifications.

In 2011 a feature that writes string programs from a single example shipped to millions of spreadsheet users. By the mid-2020s, language models were writing code from English. Both rest on the same three questions: what counts as a specification, how to search a space that grows doubly exponentially, and why a program that fits a few examples should work on the next input.

What you’ll learn

  • Define synthesis from examples, logical specifications and sketches, and place it in the complexity landscape: Σ2P\Sigma_2^{\mathsf P}-complete for finite sketches, undecidable in general.
  • Run counterexample-guided inductive synthesis (CEGIS) and prove its termination bound on finite domains.
  • Prove the Occam bound for consistent learners and use it to explain why short programs generalize, and why one or two examples need a strong prior.
  • Explain DreamCoder's library-learning objective and derive the unbiased pass@kk estimator used to evaluate sampled code.

Specifications, sketches and CEGIS

The problem has the quantifier shape ∃P ∀x φ\exists P\,\forall x\,\varphi, and that shape sets its complexity. With Boolean holes, Boolean inputs and a propositional specification, a sketch is literally a 2QBF instance ∃h ∀x ψ(h,x)\exists h\,\forall x\,\psi(h,x), and every 2QBF instance is such a sketch, so finite sketch synthesis is Σ2P\Sigma_2^{\mathsf P}-complete (2QBF's completeness is due to Stockmeyer and Wrathall, 1976). Over a Turing-complete language, even checking a candidate against a semantic specification is undecidable by Rice's theorem, so practical synthesizers restrict the language, the specification, or both.

text
function CEGIS(spec φ, language L) returns a program or FAIL
  E ← {}                                   // counterexample inputs so far
  loop
    P ← SYNTHESIZE(L, φ, E)                // an ∃ query: P meets φ on E
    if there is no such P then return FAIL // nothing in L fits even E
    x ← VERIFY(P, φ)                       // a ∀ query, via SAT on ¬φ(x, P(x))
    if there is no such x then return P    // P meets φ on every input
    E ← E ∪ {x}

Counterexample-guided inductive synthesis splits ∃∀\exists\forall into alternating ∃\exists queries, each answered by a SAT or SMT solver. Solar-Lezama's Sketch system (2006, 2008) made the loop standard; in practice a handful of counterexamples usually suffices.

Why short programs generalize

A PBE user cares about the inputs they have not shown. Model the examples as mm independent draws xi∼Dx_i\sim\mathcal D, labeled by an unknown target in a class H\mathcal H of programs, and write err(h)=Pr⁡x∼D[h(x)≠f(x)]\mathrm{err}(h)=\Pr_{x\sim\mathcal D}[h(x)\ne f(x)]. A consistent learner returns any h∈Hh\in\mathcal H that fits all mm examples, as bottom-up enumeration does.

DerivationProof
  1. Pr⁡[h consistent with all m examples] ≤ (1−εh)m ≤ e−εhm\Pr\big[h\ \text{consistent with all } m\ \text{examples}\big]\ \le\ (1-\varepsilon_h)^m\ \le\ e^{-\varepsilon_hm}

    Fix hh and a threshold εh\varepsilon_h. If err(h)>εh\mathrm{err}(h)>\varepsilon_h, each example agrees with hh with probability below 1−εh1-\varepsilon_h, so

  2. e−εhm=δ 2−ℓ(h)⟺εh=ℓ(h)ln⁡2+ln⁡(1/δ)me^{-\varepsilon_hm}=\delta\,2^{-\ell(h)}\quad\Longleftrightarrow\quad\varepsilon_h=\frac{\ell(h)\ln2+\ln(1/\delta)}{m}

    Choose εh\varepsilon_h so that this failure probability is δh=δ 2−ℓ(h)\delta_h=\delta\,2^{-\ell(h)}:

  3. Pr⁡[∃h: h consistent and err(h)>εh] ≤ ∑hδ 2−ℓ(h) ≤ δ\Pr\big[\exists h:\ h\ \text{consistent and }\mathrm{err}(h)>\varepsilon_h\big]\ \le\ \sum_h\delta\,2^{-\ell(h)}\ \le\ \delta

    The Kraft inequality for prefix-free codes, ∑h2−ℓ(h)≤1\sum_h2^{-\ell(h)}\le1, lets a union bound cover every program at once. ∎

Predict before you look

A synthesizer returns a 30-bit program consistent with mm random examples. With δ=0.05\delta=0.05, how many examples does the Occam bound need to guarantee error at most 10%?

Show the answer

238

m≥(30ln⁡2+ln⁡20)/0.1=(20.8+3.0)/0.1≈238m\ge(30\ln2+\ln20)/0.1=(20.8+3.0)/0.1\approx238. Two examples, the usual PBE budget, guarantee nothing, which is why FlashFill-style systems lean on ranking: a prior over what users usually mean does the work that missing examples cannot.

The bound also explains the design of PBE systems. A version space (Mitchell, 1982) is the set of hypotheses consistent with the examples so far. Version-space algebras (Lau et al., 2003) build it from unions, products and transforms of smaller spaces, and FlashFill's string DSL makes it a DAG over output positions: for an output of length nn there are O(n2)\order{n^2} edges, each labeled by the set of constant or substring expressions that produce that slice. Intersecting two examples' DAGs is a product construction, and ranking the survivors amounts to choosing short, likely programs, so the prior is what turns a version space into a generalizing answer.

Learning to search: DreamCoder

Neural guidance gives a probability q(ρ∣x)q(\rho\mid x) over programs for task xx, and best-first enumeration reaches the solution ρ∗\rho^* within 1/q(ρ∗∣x)1/q(\rho^*\mid x) candidates (Hidden Layer). DeepCoder (Balog et al., 2017) predicted which DSL functions appear; RobustFill (Devlin et al., 2017) decoded programs token by token with attention over the examples. DreamCoder (Ellis et al., 2021) also learns the language itself, by wake–sleep alternation:

PhaseWhat it does
WakeFor each task xx, search for programs ρ\rho with high p(x∣ρ) p(ρ∣L)p(x\mid\rho)\,p(\rho\mid L), guided by a recognition network Q(ρ∣x)Q(\rho\mid x); keep a small beam BxB_x.
Abstraction sleepRefactor the programs in the beams, enumerating rewrites with version spaces, and add to the library LL the routines that most increase the objective below.
Dream sleepTrain QQ on replays (tasks with their found programs) and fantasies (programs sampled from LL and run to make new tasks).
L⋆=arg max⁡L [log⁡p(L)+∑xlog⁡∑ρ∈Bxp(x∣ρ) p(ρ∣L)]L^\star=\argmax_L\ \Big[\log p(L)+\sum_{x}\log\sum_{\rho\in B_x}p(x\mid\rho)\,p(\rho\mid L)\Big]
A Bayesian, minimum-description-length objective: −log⁡p(L)-\log p(L) charges for library size, and −log⁡p(ρ∣L)-\log p(\rho\mid L) is the length of each solution under a probabilistic grammar over LL. A routine is worth adding if it shortens many solutions by more than it costs.

Shorter solutions are also cheaper to find: a solution of description length ℓ\ell bits has q(ρ∗)=2−ℓq(\rho^*)=2^{-\ell} and is reached within 2ℓ2^{\ell} candidates, so compression and search speed are the same quantity. Starting from a few primitives, DreamCoder built libraries for list processing, text editing, regular expressions, LOGO graphics, block towers and symbolic regression; its authors report that it rediscovered the basics of functional programming, vector algebra and classical physics, including Newton's and Coulomb's laws. Faster refactoring algorithms have since made library learning cheaper (Stitch; Bowers et al., 2023).

Check your understanding

Under DreamCoder's objective, when does adding a routine ff to the library pay off?

  1. Whenever ff appears in at least one solution
  2. When the total shortening of solutions that use ff exceeds the description length ff adds to the library
  3. When ff makes the grammar larger, since a larger grammar can express more programs
  4. When ff was proposed by the recognition network
Show the answer

B. When the total shortening of solutions that use ff exceeds the description length ff adds to the library

The objective adds log⁡p(L)\log p(L), which falls as the library grows, to the log-probabilities of the solutions, which rise when ff shortens them. ff is worth adding when the second gain beats the first cost, typically when it is reused across many tasks.

Language models as synthesizers

Language models trained on code turn synthesis into sampling: draw candidates from pθ(program∣description)p_\theta(\text{program}\mid\text{description}) and keep those that pass tests. Evaluation then needs pass@kk, the chance that at least one of kk samples is correct. Estimating it naively from a few samples is biased, so Chen et al. (2021) draw n≥kn\ge k samples per problem, count the cc correct ones, and use an unbiased estimator.

DerivationAn unbiased pass@k estimator
  1. pass@k^=1−(n−ck)/(nk)\widehat{\text{pass@}k}=1-\binom{n-c}{k}\Big/\binom nk

    Given cc correct among nn samples, a uniformly random kk-subset contains no correct sample with probability (n−ck)/(nk)\binom{n-c}{k}/\binom nk. Define

  2. E[(n−ck)/(nk)]=(1−p)k⟹E[pass@k^]=1−(1−p)k\E\Big[\binom{n-c}{k}\Big/\binom nk\Big]=(1-p)^k\qquad\Longrightarrow\qquad\E\big[\widehat{\text{pass@}k}\big]=1-(1-p)^k

    A random kk-subset of nn i.i.d. samples is itself kk i.i.d. samples, so averaging over cc gives exactly the probability that kk fresh samples are all wrong:

  3. pass@5^=1−(175)(205)≈0.601,1−(1−320)5≈0.556\widehat{\text{pass@}5}=1-\frac{\binom{17}{5}}{\binom{20}{5}}\approx0.601,\qquad 1-\big(1-\tfrac3{20}\big)^5\approx0.556

    The plug-in 1−(1−c/n)k1-(1-c/n)^k is biased low, because x↦(1−x)kx\mapsto(1-x)^k is convex and Jensen's inequality gives E[(1−p^)k]≥(1−p)k\E[(1-\hat p)^k]\ge(1-p)^k. With n=20n=20, c=3c=3, k=5k=5:

Scale turns sample-and-filter into a strong method. AlphaCode (Li et al., 2022) sampled up to millions of programs per competition problem, discarded those failing the example tests (the vast majority), clustered the survivors by their behavior on generated inputs, and submitted one program from each of the ten largest clusters; in simulated Codeforces contests it ranked on average in the top 54% of participants. FunSearch (Romera-Paredes et al., 2024) put a language model inside an evolutionary loop with an automatic evaluator and found cap sets in dimension 8 larger than any previously known (512 versus 496). In both, the symbolic half (tests, evaluators) is what certifies a candidate.

Key takeaways

  • Synthesis has the shape ∃P ∀x φ\exists P\,\forall x\,\varphi: finite sketches are 2QBF and Σ2P\Sigma_2^{\mathsf P}-complete, and over Turing-complete languages even verification is undecidable.
  • CEGIS alternates synthesis on a growing set of counterexamples with verification; on finite domains it is correct and stops within min⁡(∣L∣,∣X∣)+1\min(|\mathcal L|,|X|)+1 iterations.
  • Occam bound: with probability 1−δ1-\delta, a consistent program of ℓ\ell bits has error at most (ℓln⁡2+ln⁡(1/δ))/m(\ell\ln2+\ln(1/\delta))/m. Short programs generalize, and one or two examples need a strong prior.
  • DreamCoder learns libraries that compress solutions under an MDL objective; since search cost is about 1/q(ρ∗)1/q(\rho^*), compression and faster search are the same thing.
  • Language models make synthesis a matter of sampling and filtering; pass@kk needs the unbiased estimator 1−(n−ck)/(nk)1-\binom{n-c}{k}/\binom nk, and tests or evaluators supply the guarantees.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is synthesizing a finite sketch from a propositional specification Σ2P\Sigma_2^{\mathsf P}-complete rather than NP-complete?

  1. Because the sketch may contain loops
  2. Because its form is ∃\exists holes ∀\forall inputs: one quantifier alternation, exactly 2QBF
  3. Because SAT solvers are incomplete
  4. Because the specification must be converted to CNF first
Show the answer

B. Because its form is ∃\exists holes ∀\forall inputs: one quantifier alternation, exactly 2QBF

A solution must work for all inputs, so the problem is ∃h ∀x ψ(h,x)\exists h\,\forall x\,\psi(h,x). Checking one candidate is already coNP-complete, and 2QBF encodes directly as a sketch with Boolean holes.

Question 2

Why can CEGIS never receive the same counterexample twice?

  1. The verifier remembers its earlier answers
  2. Counterexamples are drawn at random without replacement
  3. The synthesizer deletes the inputs it has seen
  4. Every new candidate is required to meet the specification on all counterexamples collected so far
Show the answer

D. Every new candidate is required to meet the specification on all counterexamples collected so far

SYNTHESIZE only proposes programs that meet φ\varphi on EE, so any input on which the new candidate fails lies outside EE. That is why EE grows every iteration, and CEGIS stops within ∣X∣+1|X|+1 iterations on a finite domain.

Question 3

For one problem, n=10n=10 samples are drawn and c=1c=1 is correct. What is the unbiased estimate of pass@5?

  1. 0.100.10
  2. 1−0.95≈0.411-0.9^5\approx0.41
  3. 0.50.5
  4. 11
Show the answer

C. 0.50.5

1−(95)/(105)=1−126/252=0.51-\binom95/\binom{10}5=1-126/252=0.5: half of all 5-subsets of the 10 samples contain the correct one. The plug-in 1−0.95≈0.411-0.9^5\approx0.41 is biased low.

Question 4

In the Occam bound err(h)≤(ℓ(h)ln⁡2+ln⁡(1/δ))/m\mathrm{err}(h)\le\big(\ell(h)\ln2+\ln(1/\delta)\big)/m, what happens to the guaranteed error of a consistent program if its description length doubles from 40 to 80 bits, with mm and δ\delta fixed?

  1. It roughly doubles
  2. It is unchanged, because the program is still consistent
  3. It roughly squares
  4. It halves, because longer programs are more expressive
Show the answer

A. It roughly doubles

The bound is linear in ℓ(h)\ell(h), and ln⁡(1/δ)\ln(1/\delta) is small next to 40ln⁡2≈2840\ln2\approx28, so the guarantee roughly doubles. Fitting the data with a longer program is weaker evidence that it will generalize.

Further reading

  • A. Solar-Lezama, Program Synthesis by Sketching, PhD thesis, University of California, Berkeley (2008).
  • A. Blumer, A. Ehrenfeucht, D. Haussler & M. K. Warmuth, "Occam's razor," Information Processing Letters 24(6), 377–380 (1987).
  • K. Ellis et al., "DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning," PLDI (2021).
  • M. Chen et al., "Evaluating large language models trained on code," arXiv:2107.03374 (2021).
  • S. Gulwani, O. Polozov & R. Singh, "Program synthesis," Foundations and Trends in Programming Languages 4(1–2) (2017).