Random data can create confidence without creating much evidence. A million inputs drawn from the same comfortable distribution may never reach the narrow structure on which a wrong proof fails. The count is large; the investigation is shallow.
Good generator design begins with the opposite question: what assumption am I trying to disprove? The answer determines the structure, scale, and variation of the data.
Start with a failure hypothesis
Before writing a generator, name the incorrect behavior it should expose. Examples include assuming strict rather than non-strict order, forgetting that a structure may be disconnected, using a locally attractive choice that blocks a later optimum, relying on values being distinct, overflowing an intermediate expression, or passing only because random instances are easy.
The hypothesis should be specific enough to predict an outcome: this solution family should fail on inputs with this property, for this reason. If the generator cannot be connected to such a statement, it is probably generating volume rather than evidence.
Construct a small witness first
Before scaling a family, find the smallest case that demonstrates the failure. Small witnesses are easier to inspect, explain, preserve, and minimize. They also separate conceptual errors from performance failures: if a solution fails on six elements, the problem is not time complexity.
The witness becomes the seed of a family. Vary the irrelevant details while preserving the structure that makes the wrong reasoning fail. This tests whether the weakness is general without obscuring the causal feature.
Separate shape from scale
Structural tests and stress tests answer different questions. Shape tests ask whether the algorithm is correct: chains, stars, repeated blocks, nested intervals, alternating values, degenerate geometry, disconnected components, or carefully aligned ties. Scale tests ask whether a correct idea is implemented within the promised time and memory limits.
Do not assume that a maximum-sized random instance serves both purposes. It may be computationally large but structurally ordinary. Build small adversarial shapes and large performance families separately, then combine them only when their interaction matters.
Generate in the coordinates of the proof
A generator is strongest when its parameters correspond to claims in the correctness argument. If the proof depends on component size, depth, number of value groups, overlap pattern, or distance between critical events, expose those as generator parameters. Sweep across the boundaries where the proof changes case.
This turns the proof into a coverage plan. Every lemma suggests a family; every special case suggests a boundary; every phrase such as “without loss of generality” suggests a symmetry worth checking.
Use randomness to explore a designed space
Randomness is valuable after the space has been shaped deliberately. Choose a structural family first, then randomize within it: shuffle labels, vary sizes, perturb noncritical values, or compose independently generated pieces. This preserves the property under investigation while widening the sample.
Uniform sampling is rarely neutral. It heavily favors some structures and makes others nearly impossible. If rare structures matter, sample the structural parameter explicitly rather than hoping an unconstrained generator discovers it.
Keep every failure reproducible
Record the seed, generator version, parameters, and exact command for every produced case. A failure that cannot be regenerated is a rumor. Reproducibility lets another judge inspect the cause, lets continuous integration preserve the evidence, and lets a later change show whether the same risk has returned.
When randomized differential testing finds a disagreement, minimize the case while preserving the disagreement. The minimized witness belongs in the permanent regression suite; the original seed remains useful provenance.
Compare independent oracles
For small instances, a slow brute-force solver is often the most valuable companion to a generator. Compare the intended solution against an independently written oracle across exhaustive or randomized small cases. The two programs should not share the same shortcuts, data structures, or derivation.
Metamorphic checks help when a direct oracle is difficult. Apply a transformation that should preserve or predictably change the answer—renaming vertices, permuting an unordered collection, adding an irrelevant component, scaling values when the statement allows it—and verify that the output changes as expected.
Test the generator too
A generator is production code for the contest package. Assert its own invariants. Send every output through the validator. Check that requested sizes and structural properties actually occur. Confirm that boundary modes reach the intended limits and that supposedly distinct families are not duplicates with different names.
Also test composition. Individually valid fragments can create an invalid whole through duplicated identifiers, inconsistent counts, disconnected metadata, or values that cross a global constraint.
Build a portfolio, not one universal generator
A reliable package usually needs several focused families:
- Minimal cases for empty-looking, singleton, and smallest legal structures.
- Boundary cases just below, at, and just above meaningful thresholds.
- Constructed witnesses for each named misconception in the failure catalogue.
- Structured random families that vary a proof-relevant shape without losing it.
- Small differential cases checked against an independent brute-force oracle.
- Scale families for time, memory, recursion depth, and numeric range.
- Interaction cases where two individually understood risks occur together.
Know what the evidence proves
Passing generated tests does not prove correctness. It shows that the solution survived a documented set of attempts to falsify it. That distinction is healthy: proofs, independent solutions, validators, generators, and human review contribute different kinds of evidence.
The generator has done useful work when each family has a named purpose, each known wrong solution is rejected for an understood reason, unexpected disagreements become reproducible regressions, and another judge can inspect the map from risk to evidence.