Reducing Failing Inputs to a Minimal Counterexample

A property-based test generates an input, checks that some invariant holds, and repeats. When a failing input is found, the value that caused the failure is whatever the generator happened to produce: an object with nineteen fields, three of them empty, one containing a thousand-element list. Reporting that is technically correct and practically useless, because the reader has to determine which of the nineteen fields and which of the thousand elements matter. Shrinking is the second half of the tool, and it is a search that runs the test many more times in order to hand back the smallest input that still fails.

The counterexample is a search problem

The property is a predicate over inputs: it returns pass or fail for a given value. A generator samples from the input space; the tester looks for a sample where the predicate fails. Once one is found, a second search begins over the inputs that fail, with a preference order that says one input is better than another when it is structurally smaller.

Formally, shrinking needs two things: a well-founded ordering on inputs, so that repeated improvement terminates, and a decision procedure for whether a candidate still fails the predicate, which is the test itself. Every candidate costs a full re-execution, so the number of candidates the shrinker tries is the currency it spends. The typical loop is greedy: propose candidates in a fixed order, accept the first that still fails, restart the proposal sequence from the new input, and stop when no candidate fails. The result is not provably minimal — greedy search can get stuck in a local minimum where no single-step reduction preserves the failure — but it is usually small enough to read, and the fixed proposal order keeps the result reproducible.

The termination argument is what makes the ordering matter. Reducing an integer by one is well-founded because positive integers can only be reduced finitely often, while reducing it by a random smaller amount might not decrease at all. A generator whose values can be transformed in cycles, such as one that swaps two elements, must either avoid such transformations or bound the number of iterations, or the shrinker will loop.

Reduction must be per-type, and structural first

A generic shrinker cannot do much with an arbitrary value, so the reduction rules come from the generator. Each type knows how to propose smaller versions of itself, and composite generators combine the rules of their components.

For an integer, the natural sequence is a binary search toward zero: try zero, then half, then the value minus one, each time halving the gap. That costs a logarithmic number of attempts rather than the value itself. For a collection, the first proposals remove large contiguous blocks, then single elements, then shrink an element while leaving the rest in place; removing before shrinking is deliberate, because a shorter collection makes every subsequent element-reduction cheaper to interpret. For a record, proposals set each field to a shrunk value in turn. For a choice between two alternatives, the proposal switches to the other alternative, which is essential: a failure that only occurs when the generator picked a particular branch cannot be shrunk at all unless the branch choice itself is a shrinkable value.

The interaction that makes structural shrinking produce legible counterexamples is the order in which reductions are tried. Removing elements first tends to eliminate irrelevant ones, and only afterwards does the shrinker polish the remaining ones. A shrinker that instead reduces elements first can spend its budget making a large collection’s contents minimal while the collection itself is still large and mostly irrelevant.

def shrink(items, fails):
    """Greedy block-removal shrinker: repeatedly drop the largest block
    whose removal still fails. O(n log n) attempts for n elements."""
    best = list(items)
    block = max(1, len(best) // 2)
    while block >= 1:
        i = 0
        while i < len(best):
            candidate = best[:i] + best[i + block:]
            if candidate != best and fails(candidate):
                best = candidate          # accept, keep the same block size
            else:
                i += block                # nothing to gain here, move on
        block //= 2
    return best

The block halving is the practical trick that keeps the attempt count near logarithmic in the number of elements for the common case where the failure is caused by a few adjacent items.

The failure predicate has to be deterministic

Every accepted reduction relies on the assumption that a candidate which failed once will fail again. If the test is not deterministic, the shrinker accepts spurious reductions: the candidate failed for an unrelated reason, the shrinker moves there, and the final reported counterexample may not fail at all when replayed. That makes determinism a precondition for shrinking rather than a nice property of the suite.

The sources of non-determinism are the usual ones: an unseeded random generator, a real clock, iteration over an unordered collection, and concurrency. Seeding from the input itself rather than from the process is the strong form of the fix — the same generated input produces the same run every time, so the shrinker’s re-executions are comparable, which is the same reasoning Deterministic Time and Randomness in Test Suites applies to the suite as a whole. Where the property genuinely cannot be made deterministic, a shrinker has to require repeated agreement before accepting a candidate, or the accepted reductions have to be verified by replay at the end.

A second requirement is failure identity. Suppose the tester considers any exception a failure. During shrinking, a candidate might raise a different exception because the reduced input reaches a different code path. Accepting that as progress replaces an informative counterexample with a confusing one. Implementations therefore compare the failure signature — usually the exception type and the location it was raised from — and reject candidates whose failure differs from the original. The consequence is that the reported minimum is minimal with respect to this failure, which is the only sensible interpretation, and a property that fails in several unrelated ways yields several counterexamples when the generator is run repeatedly.

Delta debugging and its monotonicity assumption

Shrinking a set of independent decisions rather than a structured value is a simpler problem, and the standard algorithm comes from debugging rather than from testing. Given a set of changes whose union causes a failure, and a test that says whether a subset still fails, ddmin partitions the set and tries complements: it discards large subsets that are not needed, then narrows. The algorithm’s worst case is quadratic in the number of items, and it terminates with a set of changes that is minimal in the sense that removing any single element eliminates the failure, subject to one assumption.

That assumption is monotonicity with respect to the failure: if a subset fails, every superset should fail. In a real program this does not hold. Adding a statement can mask a failure, initialise a variable that was previously uninitialised, or take a different branch. When the assumption is violated, ddmin can return a set that is not actually minimal, or can fail to shrink at all, because every complement it tries happens to suppress the failure. Practical implementations widen the search (considering subsets as well as complements) or report the best result found rather than claiming minimality. The same non-monotonicity afflicts property shrinking: a smaller input may take a different path and not fail, which is exactly why the greedy loop accepts local minima instead of searching for a global one.

Case files, budgets, and the database of failures

Two engineering details decide whether shrinking pays for itself in a suite that runs many properties.

The first is a time budget. The initial search may run a thousand cases in a few seconds, and the shrink loop then runs the test again for every candidate, so a property over a large structure can spend far longer shrinking than generating. Implementations expose a deadline and a maximum number of attempts, and a shrink interrupted by a budget reports its best value so far rather than nothing. The budget should be generous enough to reach a small counterexample for the failure classes that occur; a counterexample of three elements that requires twenty attempts to reach is cheap, while an exhaustive descent into a hundred-element structure may not be.

The second is persistence. A failing example is worth retrying before the next generation round, because a regression that reintroduces an old bug should fail immediately and reproducibly rather than after a random search. Testers that keep a directory of previously failing examples, keyed by the property and its parameters and replayed first on every run, turn random search into a regression suite for exactly the inputs that have proved interesting. That database is also the bridge to ordinary tests: the smallest counterexample found by shrinking is a value a developer can paste into a table-driven test, which is where the useful ones end up. Handing a small counterexample to a conventional test is also the moment the property suite’s work becomes visible to the rest of the tooling, since the table-driven test has a stable identifier that Test Discovery, Collection Order, and Import Side Effects can select and schedule individually.