What a regression test can ask for

Everything so far has been a measurement of a phenomenon. This is the essay that has to be actionable, because a phenomenon whose only consequence is that a test suite fails intermittently has one question attached to it: what should the test say instead?

The answer is a number and it has two sides.

The band is 3.2·10⁻¹², which is the floor: a tolerance below it fails on a correct build. The smallest defect whose nearest run clears the band is one part in 10¹², at 4.6·10⁻¹². So the tolerance has to sit between 3.2·10⁻¹² and 4.6·10⁻¹², which is a window a factor of 1.42 wide.

Why both sides matter #

A tolerance is usually chosen from one side. Somebody observes the variation, rounds up generously, and types 10⁻⁸. That satisfies the lower bound and ignores the upper one, and the upper one is where the test’s value is.

This site has a name for the discipline of choosing between two sides, and it is machinery rather than advice — the same discipline no rule reaches the oracle applies to a regularisation parameter, where a number has to be chosen from the data and every published rule is a heuristic. bracket(noise, failure, tol) from the shared verification kit refuses a tolerance that is not strictly between the measured noise floor and the smallest real failure — because below the noise the test fires on correct work, and above the failure it accepts the thing it exists to catch. It is the same object the regularisation field uses for a parameter choice, applied to a test threshold.

Applied here, the two arguments are:

• the noise is the run-to-run variation, 3.2·10⁻¹², measured by running the same computation on six partitionings;
• the smallest real failure is the answer movement caused by the smallest defect worth catching, which has to be decided and then measured.

A tolerance of 10⁻⁸ passes the first test and fails the second by four orders: every defect up to about one part in 10⁸ in a matrix entry sails through it. That is not a hypothetical class of defect. A unit conversion applied twice, a coefficient read from a file at single precision, a boundary condition scaled by 1 + 10⁻⁹ — all of them land there.

Why the defect clouds are clouds #

The detail that makes the measurement honest, and that a first attempt gets wrong.

The natural experiment is: solve once with the defect, solve once without, compare. That measures a difference which is partly the defect and partly the machine, and at small δ it is almost entirely the machine — so the answer is noise and the experiment says nothing.

What the figure does instead is run both the correct and the defective problem on all six partitionings, and ask whether the two clouds separate. A defect is detectable exactly when its nearest run is further from the reference than the furthest honest run — anything less and a test that fires has fired on a machine rather than on a bug.

That is the same comparison a regression suite makes without knowing it. The stored answer was produced by one machine; the new answer comes from another; and the question is whether the difference is explicable by the machine alone. Making both clouds explicit turns an unanswerable question into a measurement.

Reading the rows #

Below the band, at δ = 10⁻¹⁵, 10⁻¹⁴ and 10⁻¹³: the defective runs’ nearest is 1.0·10⁻¹², 1.4·10⁻¹² and 1.5·10⁻¹² — all inside the band. The clouds overlap. These defects are invisible to any test that does not also fail on correct builds.

At and above 10⁻¹²: 4.6·10⁻¹², 4.3·10⁻¹¹, 4.3·10⁻¹⁰, and so on by decades. The response is linear in δ, at about 4.3 times δ, which is the amplification of this problem — smaller than its condition number of 10⁴ because a single entry’s perturbation is not the worst-case direction.

Two features are worth naming.

The response is linear and the floor is not. Above the band the answer movement is 4.3δ, exactly proportional. Below it, the measured movement stops falling and sits at about 10⁻¹²: that is the machine, not the defect, and it is why the smallest catchable defect is where the two curves cross rather than where the defect becomes small.

The window is narrow. A factor of 1.42 between the largest tolerance that fails on nothing correct and the smallest that catches the first defect above the floor. A tolerance chosen by rounding to a decade lands outside it in one direction or the other.

What the floor is, in backward-error terms #

The most useful reading of the band is not its value but its interpretation, and it is the site’s own vocabulary applied to a machine.

The band is 3.2·10⁻¹² and the amplification is 4.3, so the machine’s variation is equivalent to a perturbation of the data of about 7.5·10⁻¹³ — a few thousand times the unit roundoff, which is what several hundred amplified roundings in a 674-step solve comes to.

So: the machine’s nondeterminism is a backward error. It is not a new kind of thing. It is a perturbation of the problem, of a size that can be measured and predicted, arriving from the implementation rather than from the data — which is exactly the position the fifth author argues it should be given in the identity.

And that reframing is what makes the tolerance choosable. A regression test cannot detect a defect smaller than the backward error the implementation already commits, for the same reason no algorithm can distinguish two problems that differ by less than its own backward error. The window’s lower edge is not a nuisance; it is the same bound the whole subject is built on, showing up in a test suite.

Three tests, and what each is worth #

A bitwise test. Fails on a correct build the first time the machine is busy, unless every reduction reaching the compared quantity is order-independent. Worth having when that work has been done and worthless before it, and the failure mode of adopting it early is that it gets disabled and never re-enabled.

A relative test at a measured tolerance. What this essay’s window is about, and the reason the tolerance that buys no agreement matters here: a relative band is the one form of requirement that tightening the solver’s own tolerance does not help with and does not hurt. It catches defects above one part in 10¹² on this problem, it never fails on a correct build, and it requires the measurement — six runs at different partitionings, once, when the test is written.

A test on a derived invariant instead of on the answer. Often the best of the three and it is worth saying so. A solve’s residual, an eigenvalue’s residual, a factorisation’s reconstruction error: these are quantities whose magnitude is stable even when their digits are not, so a test asserting ‖b − Ax‖/‖b‖ < 10⁻¹⁰ passes on every machine and catches any defect that breaks the mathematics. It does not catch a defect that changes the problem — a wrong coefficient gives a small residual for the wrong system, which is a backward stable answer to a problem nobody asked — so it is complementary to the second rather than a replacement.

The practical recommendation is the second and third together: assert an invariant that must hold, and compare the answer against a measured tolerance. The first is for computations that have paid for it.

Where the defect was put, and whether that matters #

One entry of the matrix, at a fixed position, perturbed by a relative δ. Three questions a careful reader will have about that choice.

Does the position matter? Yes, by a factor of a few. A perturbation to an entry the solution is insensitive to moves the answer less, and one aligned with the smallest singular direction moves it more. The amplification measured here, 4.3, is a middling value for this matrix; the worst case is its condition number, 10⁴, and the best is nearly zero. So the smallest catchable defect is a property of where the defect is as well as how large it is, and the honest statement is that the figure measures one representative position rather than a bound.

Does the kind matter? Less than expected. A defect in the right-hand side, in a preconditioner, or in a boundary condition all end up as a perturbation of the problem the solver was given, and the answer moves by the amplification times the perturbation. What does not fit that description is a defect in the algorithm — a wrong loop bound, a missing orthogonalisation — and those are usually enormous and caught by everything.

Does the problem’s conditioning matter? It moves both edges together, which is the useful part. A worse-conditioned problem amplifies the machine’s roundings and a defect by the same factor, so the band and the smallest catchable defect rise in step and the ratio — the room to choose a tolerance in — is roughly preserved. That is why the window is quoted as a factor rather than as a number.

What moves the window #

Sweeping the problem size confirms half of the obvious expectation and refutes the other half.

Both edges do move together, and the ratio is not the stable one. At n = 80, 100, 150 and 220 the band runs 6.66·10⁻¹², 9.01·10⁻¹², 3.24·10⁻¹² and 1.88·10⁻¹¹ while the smallest catchable defect runs 10⁻¹³, 10⁻¹¹, 10⁻¹² and 10⁻¹⁰ — dipping together at n = 150 and rising together at 220, which is the shared-amplification claim behaving. But the window they leave runs 1.04, 3.24, 1.42 and 7.07, a factor of 6.8 across the sweep, against the band’s factor of 5.8.

So the room to choose a tolerance is the least predictable of the three, not the most. That is worth having the right way round, because it decides what a test author can carry between problems. The band can be estimated from the size to within a factor of six; the window cannot be estimated at all, and at n = 80 it is 1.04 — a tolerance chosen anywhere in it is within four per cent of failing on a correct build and of missing the defect. The measurement has to be repeated per problem, and the reason is not that the edges are unpredictable but that their ratio is more volatile than either of them.

What genuinely widens the window is making the reductions order-independent — the sum that cannot be wrong’s three operations an element. The band goes to zero, the lower edge disappears, and any defect that changes the answer at all becomes visible. That is the strongest argument in this field for spending the three operations an element, and it is an argument about testability rather than about accuracy: a computation with a bitwise-stable reduction can have a test that catches a defect of one part in 10¹⁶.

Where this leaves a test suite #

Four things to do, in the order they cost.

Measure the band, once. Run the computation at six partition counts and record the spread. It is an afternoon, it produces the number every other decision needs, and it is currently nobody’s job.

Write the tolerance from the measurement, with a factor of two of headroom above the band and a note saying what it was measured against. A tolerance with a provenance survives the next person; one typed as 10⁻⁸ does not, and gets loosened again the next time it fails.

Assert an invariant beside it. ‖b − Ax‖ ≤ tol·‖b‖, ‖QᵀQ − I‖ ≤ n·u, ‖A − LU‖ ≤ n·u·‖A‖: these hold on every machine, catch defects the answer comparison cannot, and are the site’s own habit applied to a test suite rather than to a figure. It is the same reason every figure here carries a residual badge — a small residual is not a small error is why that is not sufficient, and it is still necessary.

And record what the machine was. Thread count, library version, and — if it can be reached — the partitioning. The field’s three causes are a reduction, a compilation and a version, and a failure report that carries all three is diagnosable. One that carries none is a report that the answer changed.

Two failures this does not cover #

The window is measured on a computation whose answer is a vector of real numbers, and two common situations do not fit that shape at all.

A verdict. If what is compared is an integer — a rank, an iteration count, a definiteness flag — there is no tolerance to choose, because there is no notion of nearly the same integer. A test on a rank either accepts both 11 and 12 or it does not, and if it does it has stopped testing the thing. A rank that depends on the thread count is the measurement; the only repairs are to make the reduction order-independent or to test the spectrum rather than the count.

A trajectory. If what is compared is a sequence — a convergence history, a set of iterates, a log — the machine’s variation appears at every step and the comparison has as many chances to fail as there are steps. A test asserting that a residual history matches a stored one will fail; a test asserting an invariant of the history will not. The second is an invariant and the first is a comparison, which is the third row of the table above with the stakes raised.

Which invariant, and what it buys, is worth measuring, because the obvious choice is half wrong and the trade is larger than it looks. Conjugate gradients on a 12×12 grid Laplacian with the matrix–vector product summed in p blocks, p from 1 to 64:

• Seven partitions, seven distinct residual histories. The stored comparison fails on a correct build, exactly as described.
• The step count is 42 at every partition. That invariant is stable.
• But the residual is not monotone. It rises at one of the forty-two steps, by a factor of 1.48 — conjugate gradients minimises the A-norm of the error, and the 2-norm of the residual is free to increase. A test asserting monotone decrease fails on a correct run, which is precisely the failure this section exists to avoid.
• And the stable invariant catches almost nothing:

The step count moves only at a defect of 10⁻³ — nine orders above the 10⁻¹² the table above gives as the comparison’s floor. So the two are not catching the same defects. One is sensitive and unusable; the other is stable and blunt, and the trade between them costs nine orders of sensitivity.

That does not overturn the advice, which is still the only workable one. It fixes both halves: assert the step count with a generous bound, and do not assert monotone decrease — and know that the suite’s real sensitivity is then 10⁻³ rather than 10⁻¹².

The monotonicity half is worth one more sentence, because the mistake in it is a substantive one rather than a slip. Conjugate gradients does have a monotone quantity, and it is not the one a solver prints: the A-norm of the error falls at every step by construction, and the residual norm does not. So the invariant a reader would reach for exists, is genuinely monotone, and is unavailable — computing it needs the answer. A test can assert something true about a quantity it cannot see, or something false about the quantity it has, and the recommendation as usually stated quietly swaps one for the other.

That is the same trap as the rest of this field in miniature. The property that would make a good test is a property of the object; what the test can reach is a property of the report, and the two agree only when somebody has checked that they do.

Both are instances of one rule: compare something whose value is determined, not something whose digits are. The number of steps is not determined, and neither is the twelfth digit of an answer; the fact that a residual fell below a tolerance is, and so is the fact that a factorisation reconstructs.

The unflattering summary #

Stated plainly, because the field’s other essays have been descriptive and this one is not.

A regression test on a numerical answer, on a machine with more than one worker, cannot detect a defect smaller than the backward error the implementation commits — which is the exact answer to a nearby problem’s standard, read as a limit on testing rather than as a guarantee about an algorithm — which on an ordinary solve is a few thousand roundings, or about 10⁻¹² relative. Below that, a wrong coefficient and a busy afternoon are indistinguishable, and no threshold separates them.

The number is not small enough to be reassuring and not large enough to be a crisis. It says: a test suite comparing answers can catch a wrong sign, a wrong formula, a wrong index and a coefficient wrong in its twelfth digit, and it cannot catch a coefficient wrong in its fifteenth. A suite comparing invariants of a trajectory — which is what the section above recommends, and what a sequence forces — stops nine orders earlier, at the fourth digit. Whether that matters is a question about the application, and it is a question that can now be asked with a number in it.

One line #

The machine’s own variation is a backward error of measurable size, so a regression test can catch any defect larger than it and none smaller, and the number is worth measuring once rather than guessing every time the suite goes red.