Counterexample Search¶
Method — instantiates Inductive Validity Extension
Actively searches for a case, input, stage, or transition that breaks the claimed extension and forces revision of the propagation rule.
Most validation tries to confirm a claim; Counterexample Search tries to kill it. Given an assertion that some property holds all the way across an extension — "this optimization is always safe," "this rule works for every case" — the method spends its effort constructing the single case where it does not hold. It is adversarial by design: a claim that survives a serious, motivated attempt to break it earns confidence precisely because the attempt failed, and a claim that falls to the first probe is cheaper to have killed now than at scale later. Its defining move is asymmetry — one genuine counterexample refutes a universal claim outright, whereas no number of confirming cases ever proves it — so the method invests entirely in the refuting side of the ledger.
Example¶
A compiler team has written an optimization pass that rewrites x * 2 and similar arithmetic into cheaper shift-and-add sequences. It passes the existing test suite, so the proposal is to enable it for all integer code. Counterexample Search treats "all integer code" as the extension to be broken, not trusted. The team does not add more happy-path tests; they hunt for the input class most likely to violate the pass's hidden assumption — that arithmetic never overflows. They construct a program near the maximum representable integer, where x * 2 overflows to a defined wrapped value but the rewritten shift produces a different wrapped value.
The pass compiles it, and the two programs disagree. That single divergent program is the counterexample: it refutes "always safe" cleanly. The outcome is not a scrapped pass but a narrowed one — the team records the exact condition under which the rewrite is unsound, restricts the pass to ranges provably free of overflow, and files the overflow assumption as something to watch if the integer width ever changes. The claim that ships is smaller, and true.
How it works¶
- Target the claim, not the code. State the universal being attacked ("holds for every input in this class") sharply enough that a single case can falsify it.
- Go where the assumption is thinnest. Direct the search at boundaries, scale shifts, unusual inputs, and transition points — the places the archetype's failure modes cluster — rather than sampling uniformly.
- Construct, don't stumble. Build the adversarial case deliberately (hand-crafted edge input, worst-case ordering, a context the base case never saw), reasoning backwards from what would have to be true for the claim to fail.
- On a hit, narrow rather than discard. A found counterexample marks a boundary: restrict the extension to exclude it, and log the violated assumption as a drift signal to monitor.
- On a miss, report the coverage. "We attacked overflow, aliasing, and concurrency and found nothing" is the actual evidence produced — its worth is exactly as large as the attack was serious.
Tuning parameters¶
- Adversary strength — from a quick "what would break this?" brainstorm to a funded red-team or SMT solver. Stronger adversaries find deeper counterexamples but cost more; match it to the stakes of a late failure.
- Search direction — boundary-first, scale-first, or context-shift-first. Aiming at the likeliest fault region finds breaks faster but can miss a fault you did not anticipate.
- Stopping rule — how long to keep attacking before declaring the claim provisionally survived. Stop too early and the survival is meaningless; too late and you burn effort on a robust claim.
- Narrowing granularity — how tightly to carve the extension boundary around a found counterexample. A tight cut preserves more of the claim but risks re-breaking near the new edge.
When it helps, and when it misleads¶
Its strength is that it is the archetype's antidote to proof theatre — validation that tests only confirming cases and calls the resulting glow "rigor." A serious counterexample search cannot be passed by cherry-picking; it either finds the break or certifies that a motivated search did not, which is the only confirming evidence a universal claim can honestly earn. It is at its best on claims whose failure is catastrophic and whose edge conditions are enumerable. The discipline draws directly on Popper's falsifiability[n1]: a claim earns standing by surviving attempts to refute it, not by accumulating agreeable examples.
Its failure mode is that absence of a found counterexample is not proof of absence — a search that never targeted the true fault region will report a clean bill that is merely a measure of its own blind spots. It also tempts a team to over-narrow, carving the extension boundary so tightly around each break that the surviving claim is too small to be useful. The guarding discipline is to state, honestly, what was attacked and how hard, so that "no counterexample found" is read as a bounded result rather than a guarantee.
How it implements the components¶
counterexample_check— this method is the counterexample check, executed as a deliberate constructive attack rather than a passive review.extension_boundary— each counterexample found (or region left unattacked) becomes an explicit edge of where confidence stops.assumption_drift_signal— a violated assumption is logged as a condition to watch, so the same break is caught if the environment shifts back into it.
It does not construct the positive argument — base_case, step_transition_rule, propagation_rule, proof_obligation_register — that establishes why validity carries forward; that is Induction Proof's job. The two are mirror images: Induction Proof builds the deductive case that the propagation rule holds; Counterexample Search tries to break it. Induction Proof owns propagation_rule; this method attacks it.
Related¶
- Instantiates: Inductive Validity Extension — supplies the refutation half of the archetype, bounding claims the positive machinery would otherwise over-extend.
- Sibling mechanisms: Induction Proof · Property-Based Testing · Invariant Propagation Test · Recursive Decomposition Check · Recursive Process Validation · Scalable Policy Rule Audit · Staged Rollout Validation · Training Progression Validation
Editorial Notes¶
Form Classification¶
Form family: Experiment, Test & Rehearsal
Rationale: Counterexample Search operates as a bounded trial, probe, simulation, or rehearsal that generates evidence from performance because it actively searches for a case, input, stage, or transition that breaks the claimed extension and forces revision of the propagation rule.
Independent corroboration: The frozen evidence defines Counterexample Search as 'Actively searches for a case, input, stage, or transition that breaks the claimed extension and forces revision of the propagation rule', so its operative form is Experiment, Test & Rehearsal.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Philosophy
Origin pattern: Convergent development
Present-day reach: Universal
Rationale: Philosophical refutation, mathematical proof practice, and computer verification each cohered deliberate searches for a case that defeats a general claim.
Related originating lineages:
- Computer Science & Software Engineering — Formal verification and property-based testing operationalized automated searches for inputs that violate a claimed invariant.
- Mathematics — Proof practice supplied deliberate construction and search for cases that refute universal statements or conjectures.
Review resolution: The disagreement is best resolved as genuine convergence among logic, mathematics, and formal computing rather than by treating computer science as later applicability only.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Karl Popper's criterion that a claim is scientific only insofar as it is falsifiable — exposed to tests that could refute it. Counterexample Search operationalizes the criterion: it manufactures the potential refutation instead of waiting for one to arrive. ↩