CEGIS 2D: Counterexample-Guided Program Synthesis

Program synthesis turns a specification into working code by searching a space of candidate programs and checking each one against the spec — the loop at the heart of modern AI-assisted, correctness-first code generation. This 2D companion makes the loop concrete and finite across two linked panels: a candidate lattice on the left, showing every integer (a, b) program as a dot, and a function graph on the right, showing the currently proposed line f(x) = a·x + b against the domain the verifier probes. The hidden spec is one linear program the synthesizer cannot see directly; each round it proposes the first candidate consistent with every counterexample seen so far, the verifier scans the integer domain for a disagreement, and every counterexample found prunes the candidate lattice live — exactly like SMT-backed CEGIS tools (Sketch, Rosette) do over far richer program grammars — until the surviving candidate is provably equal to the hidden program.