How does counterexample-guided inductive synthesis (CEGIS) differ from exhaustive enumerative search?
ACEGIS only works for hardware, while enumerative search works for software
BCEGIS iterates between a synthesizer that proposes candidates from a finite set of examples and a verifier that checks candidates against the full specification, using counterexamples from failed checks to refine future proposals. Enumerative search tries all programs of increasing size and checks each against the full specification directly
CCEGIS is less precise than enumerative search
DEnumerative search uses machine learning while CEGIS uses logic
CEGIS has two phases per iteration: the synthesizer finds a program consistent with the current set of examples (a smaller, easier problem than meeting the full spec), and the verifier checks the candidate against the complete specification. If the candidate fails, the verifier produces a counterexample that is added to the example set, and the synthesizer tries again. This is typically much faster than enumerating all programs because the synthesizer solves a smaller problem (satisfy known examples) and the verifier prunes the search space with targeted counterexamples.
Question 2 True / False
Program synthesis from input-output examples alone risks overfitting — producing a program that works on the given examples but fails on unseen inputs.
TTrue
FFalse
Answer: True
With only examples as specification, there are infinitely many programs consistent with any finite set of examples (e.g., a lookup table that returns the right output for each example and garbage otherwise). Synthesis tools mitigate this by searching for the simplest program (Occam's razor via bounded search) or by combining examples with additional constraints (types, templates, or partial logical specs). CEGIS addresses this by using a verifier with access to the full specification to check proposed solutions against all inputs, not just the examples.
Question 3 Short Answer
Explain how program synthesis relates to program verification, and why synthesis is sometimes described as 'the inverse of verification.'
Think about your answer, then reveal below.
Model answer: Verification asks: given a program P and specification S, does P satisfy S? Synthesis asks: given a specification S, find a program P that satisfies S. Synthesis inverts the relationship — the program is the unknown. Many synthesis techniques use verification as a subroutine: CEGIS proposes a candidate program and then VERIFIES it against the specification. If verification fails (counterexample), the synthesis loop refines its search. The two problems are deeply connected — advances in verification (SMT solving, model checking) directly enable more powerful synthesis.
This connection is why formal methods expertise is prerequisite to understanding synthesis. The specification languages (temporal logic, pre/postconditions, types with refinements) come from verification. The checking algorithms (SMT solving, model checking) come from verification. Synthesis adds the search component: how to efficiently explore the space of programs to find one that passes verification. The SyGuS (Syntax-Guided Synthesis) framework formalizes this by combining a logical specification with a syntactic grammar constraining the search space.