In counterexample-guided inductive synthesis (CEGIS), an inductive synthesizer proposes a candidate program based on given test cases. The verifier then checks if the candidate is correct. What happens if the verifier finds the candidate is incorrect?
Think about your answer, then reveal below.
Model answer: The verifier finds a counterexample — an input where the candidate's output disagrees with the specification. This counterexample is added to the test set and provided back to the inductive synthesizer. The synthesizer then finds a new candidate that passes ALL tests (the old ones plus the new counterexample). This loop repeats until either the synthesizer finds a program that passes verification, or the problem is determined to be unsolvable within the grammar.
CEGIS is a form of learning from counterexamples. The inductive step (synthesize from tests) is cheap; the deductive step (verify against the full specification) is expensive. By interleaving them, CEGIS avoids expensive verification on many candidate programs. Each counterexample rules out a class of programs, accelerating convergence. This strategy has been remarkably effective in practice: tools like FlashFill (Microsoft Excel) and modern fuzzing harnesses use CEGIS-like ideas to generate programs from examples.
Question 2 Short Answer
Syntax-guided synthesis (SyGuS) constrains the program space using a context-free grammar. Why is this grammar restriction necessary rather than searching over all possible programs?
Think about your answer, then reveal below.
Model answer: The space of all possible programs is infinite and unstructured. A grammar reduces the search space to a finite (or tractable) subset of programs with a particular form. For example, the grammar 'E ::= c | x | E + E | E * E' limits candidates to polynomial expressions. Without such structure, even simple synthesis problems become intractable because the search space is too large and the solver has no guidance about which program forms are relevant. The grammar encodes domain knowledge about what kind of solution is appropriate.
This is the key insight making SyGuS practical: the grammar is not a limitation but an opportunity for the user to express prior knowledge about the solution. If you're synthesizing a bit-vector manipulation routine, you use a grammar with bitwise operations; if you're synthesizing an invariant, you use a grammar of inequalities and boolean combinations. The grammar guides both search efficiency (smaller space) and relevance (more likely to find a good solution). Many synthesis tools ask: what grammar did the user intend? and use the grammar to focus the search.
Question 3 Multiple Choice
A synthesizer generates a program `y = 2*x` as a candidate for the specification 'compute the double of x.' The verifier checks this candidate by attempting to prove ∀x. (2*x satisfies the spec). If the specification is defined as 'y equals 2*x exactly', what does the verifier do?
AThe verifier asks the user if the candidate is correct
BThe verifier checks a few concrete test inputs
CThe verifier uses an SMT solver to prove ∀x. (2*x = 2*x), which is a tautology, so the candidate is verified correct
DThe verifier returns to the synthesizer to generate a different candidate
The specification 'y = 2*x exactly' translates to a logical formula that the candidate must satisfy for all inputs. The SMT solver checks if ∀x. (candidate(x) = 2*x) is valid — i.e., does the formula hold for all x? For the candidate `y = 2*x`, this is tautologically true, so the solver immediately confirms correctness. The key is that formal synthesis uses automated reasoning (SMT solvers, theorem provers) for the verification step, not random testing, giving formal guarantees of correctness.
Question 4 Short Answer
Component-based synthesis constructs programs by composing existing library functions rather than generating them from scratch. What role does formal specification play in component-based synthesis?
Think about your answer, then reveal below.
Model answer: Component-based synthesis uses the formal specification to search over compositions of library functions. Given a library of components (e.g., list operations: map, filter, reduce), the synthesizer searches for combinations of these components whose composed behavior satisfies the specification. An SMT solver checks if a particular composition meets the spec, and the search explores the space of compositions (typically much smaller than the space of all programs). The formal specification guides which compositions are valid.
Component-based synthesis is practical when a rich library of pre-verified components exists. Rather than verifying each synthesized program from scratch, you verify that the composition correctly combines pre-verified components. This is analogous to component-based software engineering: build systems from trusted parts. Tools like Myth (UC Berkeley) synthesize programs from library functions and specifications, useful for automating repetitive tasks like list manipulation. The power of formal methods here is that the specification can be rich (temporal properties, quantitative properties) and the solver guarantees the synthesized composition satisfies it.