Program synthesis searches a space of candidate programs for one that provably satisfies a formal specification. Counterexample-guided inductive synthesis (CEGIS) alternates a synthesizer that proposes candidates with a verifier that either accepts one or returns a counterexample showing exactly how it failed โ the loop repeats until a candidate is verified or a budget runs out.
CEGIS loop:
x โ propose_candidate()
loop:
if Verify(x, Spec) == PASS: return x (correct-by-construction)
c โ counterexample from Verify(x, Spec)
x โ x โ ฮท ยท โd(x, Spec, c) + noise (refine using the counterexample)
Here: d(x, Spec) = r(x) โ S(ฮธ,ฯ) โ signed distance from a candidate's
radius r to the spec boundary S(ฮธ,ฯ) in its own direction (ฮธ,ฯ).
d โค 0 โ candidate lies inside the verified region โ PASS.
- Population โ how many candidate programs are searched in parallel each round.
- Search step ฮท โ how aggressively a guided candidate moves toward the specification boundary per iteration.
- Spec complexity โ reshapes the verified region from a simple sphere into a rugged, multi-lobed manifold, mimicking a specification with many interacting constraints.
- Refinement mode โ CEGIS guidance uses the counterexample (the signed distance) to steer each candidate; random search moves blindly, so it converges far slower on the same specification.
Real toolchains do exactly this with SMT solvers (Z3) or proof assistants (Coq, Isabelle, Lean) acting as the verifier, e.g. synthesizing a priority queue and checking the heap-property invariant on every candidate implementation.