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: -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@ estimator used to evaluate sampled code.
Specifications, sketches and CEGIS
The problem has the quantifier shape , and that shape sets its complexity. With Boolean holes, Boolean inputs and a propositional specification, a sketch is literally a 2QBF instance , and every 2QBF instance is such a sketch, so finite sketch synthesis is -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.
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 into alternating 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 independent draws , labeled by an unknown target in a class of programs, and write . A consistent learner returns any that fits all examples, as bottom-up enumeration does.
Fix and a threshold . If , each example agrees with with probability below , so
Choose so that this failure probability is :
The Kraft inequality for prefix-free codes, , lets a union bound cover every program at once. ∎
A synthesizer returns a 30-bit program consistent with random examples. With , how many examples does the Occam bound need to guarantee error at most 10%?
Show the answer
238
. 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 there are 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 over programs for task , and best-first enumeration reaches the solution within 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:
| Phase | What it does |
|---|---|
| Wake | For each task , search for programs with high , guided by a recognition network ; keep a small beam . |
| Abstraction sleep | Refactor the programs in the beams, enumerating rewrites with version spaces, and add to the library the routines that most increase the objective below. |
| Dream sleep | Train on replays (tasks with their found programs) and fantasies (programs sampled from and run to make new tasks). |
Shorter solutions are also cheaper to find: a solution of description length bits has and is reached within 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).
Under DreamCoder's objective, when does adding a routine to the library pay off?
- Whenever appears in at least one solution
- When the total shortening of solutions that use exceeds the description length adds to the library
- When makes the grammar larger, since a larger grammar can express more programs
- When was proposed by the recognition network
Show the answer
B. When the total shortening of solutions that use exceeds the description length adds to the library
The objective adds , which falls as the library grows, to the log-probabilities of the solutions, which rise when shortens them. 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 and keep those that pass tests. Evaluation then needs pass@, the chance that at least one of samples is correct. Estimating it naively from a few samples is biased, so Chen et al. (2021) draw samples per problem, count the correct ones, and use an unbiased estimator.
Given correct among samples, a uniformly random -subset contains no correct sample with probability . Define
A random -subset of i.i.d. samples is itself i.i.d. samples, so averaging over gives exactly the probability that fresh samples are all wrong:
The plug-in is biased low, because is convex and Jensen's inequality gives . With , , :
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 : finite sketches are 2QBF and -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 iterations.
- Occam bound: with probability , a consistent program of bits has error at most . 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 , compression and faster search are the same thing.
- Language models make synthesis a matter of sampling and filtering; pass@ needs the unbiased estimator , 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.
Why is synthesizing a finite sketch from a propositional specification -complete rather than NP-complete?
- Because the sketch may contain loops
- Because its form is holes inputs: one quantifier alternation, exactly 2QBF
- Because SAT solvers are incomplete
- Because the specification must be converted to CNF first
Show the answer
B. Because its form is holes inputs: one quantifier alternation, exactly 2QBF
A solution must work for all inputs, so the problem is . Checking one candidate is already coNP-complete, and 2QBF encodes directly as a sketch with Boolean holes.
Why can CEGIS never receive the same counterexample twice?
- The verifier remembers its earlier answers
- Counterexamples are drawn at random without replacement
- The synthesizer deletes the inputs it has seen
- 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 on , so any input on which the new candidate fails lies outside . That is why grows every iteration, and CEGIS stops within iterations on a finite domain.
For one problem, samples are drawn and is correct. What is the unbiased estimate of pass@5?
Show the answer
C.
: half of all 5-subsets of the 10 samples contain the correct one. The plug-in is biased low.
In the Occam bound , what happens to the guaranteed error of a consistent program if its description length doubles from 40 to 80 bits, with and fixed?
- It roughly doubles
- It is unchanged, because the program is still consistent
- It roughly squares
- It halves, because longer programs are more expressive
Show the answer
A. It roughly doubles
The bound is linear in , and is small next to , 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).