The tolerance that buys no agreement

Every reader of a stopping test is a race has the same response, and it is the right response to have: if the runs disagree, converge further. The disagreement looks like the tail end of an answer that was not finished, and finishing it should remove it.

It does not, and the measurement is unambiguous.

The bars fall by 1.5·10⁶ across the sweep, which is the tolerance doing exactly what a tolerance is for: the worst run at 10⁻¹² is six orders more accurate than the best run at 10⁻⁶. The ratio between the top and the bottom of each bar is 1.34, 1.48, 1.71, 1.17 — no trend, and certainly no convergence towards one.

Why the intuition is wrong #

The intuition treats the disagreement as a residue: two runs are near the answer, one is slightly nearer, and running longer takes both closer to the truth and therefore closer to each other. That picture is right for a method converging to a fixed point in exact arithmetic and wrong here for a reason that is one line.

The disagreement is not a distance from the answer. It is a distance between two trajectories that are both converging, and it is proportional to wherever they are. Two runs at 10⁻⁶ differ by about a third of 10⁻⁶; the same two runs at 10⁻¹² differ by about a fifth of 10⁻¹². The ratio is what stays fixed, because the mechanism producing it — a reduction disagreeing by κ_sum·u relative — is relative rather than absolute.

So converging further does buy something real: the absolute disagreement falls by six orders, exactly as the accuracy does. If a caller’s requirement is stated in absolute terms — the two machines must agree to 10⁻⁸ — tightening the tolerance meets it. If it is stated in relative terms, or as a bitwise comparison, no tolerance ever meets it.

That distinction is the practical content of this essay and it is worth stating as a rule: tightening a tolerance moves a disagreement, it does not remove one.

The same statement about precision #

The identical argument applies to the other knob people reach for, and it is worth making explicit because the knob is this site’s founding one.

Where the disagreement comes from derives the size of the run-to-run variation as κu times a constant. It carries exactly one factor of u. So doubling the precision divides the disagreement by 2⁵³ — an enormous improvement in absolute terms — and leaves the ratio between two runs exactly where it was, and leaves the count of distinct answers exactly where it was.

A bitwise regression test fails as reliably at quadruple precision as at double. The answers are closer together; there are still many of them; and the test that asks whether they are equal gets the same answer.

This is the same shape as accuracy and agreement are different properties: every instrument that improves accuracy improves the absolute disagreement in proportion, and none of them touches the property that two runs return different bits.

Reading the four ratios, and then not reading them #

The four numbers are 1.34, 1.48, 1.71 and 1.17, and they are not monotone. That is worth an explanation rather than an average, and the explanation turns out to be about the statistic rather than about the problem.

Seven runs is a small sample of a quantity that is itself a spread, and the largest-over-smallest of seven draws is the worst estimator available for it: a range grows with the sample by construction. More partition counts cannot lower the maximum or raise the minimum, so the four ratios are partly a measurement of how many partitions were swept. Widening the same sweep from seven partition counts to thirty, on the identical problem, moves them to 1.91, 1.50, 1.73 and 1.83.

That is not the four numbers being wrong. It is the four numbers being a property of the figure as much as of the arithmetic, which makes them a bad thing to draw a conclusion from — and the conclusion they were drawn for is the essay’s central one.

Sweeping the problem size shows the same instability in the same statistic, which is the confirmation.

The ratios move by a factor of fourteen with the size and the accuracy gain does not. At n = 80, 120 and 300 the errors fall by 5.4·10⁶, 5.2·10⁵ and 8.7·10⁵ times — all within a factor of ten of each other — while the four run-to-run ratios go from 1.04–14.83 at n = 80 to 1.06–3.36 at 120 and 1.11–1.38 at 300.

A ratio of 14.83 at n = 80 and 1.18 at n = 120, for the same tolerance, is the clearest possible demonstration that the statistic is unstable — the two problems differ by fifty per cent in size and the reported disagreement by a factor of twelve. Nothing about the arithmetic changed that much. So the essay’s central claim survives, and the number that carries it must not be a range: at every size and every tolerance the band falls without closing, and that is visible in all three figures while none of the twelve individual ratios means anything on its own.

The same claim under a statistic that does not do that #

The coefficient of variation — standard deviation over mean — has no such dependence on sample size. Over thirty partition counts:

              tolerance   mean forward error   relative spread
n = 200         10⁻⁶          9.62·10⁻⁷            0.210
                10⁻⁸          8.35·10⁻⁹            0.175
                10⁻¹⁰         8.23·10⁻¹¹           0.256
                10⁻¹²         1.02·10⁻¹²           0.262

n = 320         10⁻⁶          4.55·10⁻⁷            0.102
                10⁻⁸          4.05·10⁻⁹            0.096
                10⁻¹⁰         4.67·10⁻¹¹           0.194
                10⁻¹²         4.93·10⁻¹³           0.101

The mean error falls by nine hundred thousand and the relative spread moves by a factor of 1.5 and 2.0, with no trend and — the part that matters — no fall at the tight end. On the larger problem the tightest tolerance’s spread is 0.101 against the loosest tolerance’s 0.102, which is as flat as this kind of measurement gets.

That is a much stronger version of the essay’s claim than the four ratios support. A residue would shrink; the relative spread does not move at all across six orders of accuracy, and it does so under a statistic whose value is not an artefact of the sweep.

At n = 80 the same sweep gives ratios of 1.12, 4.89, 22.02 and 1.82 — a much wider scatter, and the relative spreads there run 0.034, 0.155, 0.865 and 0.136. The cause is visible in the mean errors rather than in the reductions: at 10⁻¹⁰ the runs land at 2.8·10⁻¹², thirty-six times past what was asked for, so the stopping test is firing in a region where the residual curve has already fallen away and where exactly it fires is very sensitive. The larger problems land within 20% of their requested tolerance at every setting and do not show it. That is a caveat about small problems and a stopping test, not about the mechanism this essay is describing.

Why the wrong statistic was easy to reach for #

It is worth naming the pull, because the same shape appears wherever this site reports a spread. A range is the number a reader wants: the best and the worst run differed by this much is a sentence about two actual computations, and a standard deviation is a sentence about a distribution nobody observed. The bars in the figure are bars precisely because a range is drawable and a moment is not.

What that trade costs is comparability. Two bars drawn from different numbers of runs are not measuring the same thing, and the figure’s own slider changes the problem size without changing the partition list — so the four ratios are comparable across the sweep by luck rather than by construction. The repair is not to stop drawing the range. It is to draw the range and state the sample it came from, and to make any claim about a trend on a statistic that does not move when the sample does.

That is the general form, and it is the same discipline the ratcheted gates on this site apply to a site-wide average: a number computed from a varying population is a number that changes when the population does, and reading a trend out of it reads the population.

The iteration counts do the same thing #

The figure plots forward errors, and the iteration counts underneath it tell the same story from a direction that is easier to act on.

At a tolerance of 10⁻⁶ the seven runs take 436 to 447 steps — six distinct counts, a spread of 2.5%. At 10⁻⁸: 558 to 572, six distinct, 2.5%. At 10⁻¹⁰: 676 to 690, six distinct, 2.1%. At 10⁻¹²: 800 to 803, four distinct, 0.4%.

Two readings, and the second is the more interesting.

The spread is roughly a fixed fraction of the work, not a fixed number of steps. That is the same relative-versus-absolute point the forward errors make: the disagreement scales with wherever the computation is rather than sitting at a fixed level.

And it narrows at the tightest tolerance, which is the one place the sweep shows something the simple story does not predict. At 10⁻¹² the method is close to the floor its arithmetic allows, the residual curve is flattening, and a flattening curve crosses a horizontal line over a narrower range of steps than a steeply falling one. So the step count becomes more reproducible while the answers stay a factor apart — the two quantities decouple, and a reader who was watching only the iteration count would conclude, wrongly, that convergence had fixed something.

That decoupling is worth carrying. An iteration count agreeing is not the answers agreeing, and of the two it is the cheaper one to observe and the less informative.

What a requirement should say #

The practical residue, since somebody has to write the acceptance criterion.

A bitwise requirement is meetable and expensive. It needs order-independent reductions everywhere in the computation that reaches the compared quantity, and what determinism costs prices it at 1% to 122% of a solve depending on how cheap the matrix is. It is worth asking for when a verdict is downstream. It is not achieved by any tolerance.

A relative requirement is meetable and nearly free, and the number is κu. Two runs agree to within 10⁻¹⁰ relative is a statement the arithmetic can support if the reductions involved have κ_sum below about 10⁶, and cannot if they do not. Computing κ is one pass; the vector that hides it is how to know which reductions to compute it for.

An absolute requirement is meetable by tightening the tolerance, which is the one case where the instinct this essay is arguing against is right. If the requirement is that two runs agree to 10⁻⁸ absolute and the current disagreement is 10⁻⁷, converging two orders further meets it.

Three requirements, three different answers, and the mistake is to state one and act as though it were another.

Where the instinct does come from #

It is worth taking the instinct seriously rather than only refuting it, because there is a class of computation in which it is exactly right.

A fixed-point iteration converging to a unique fixed point — a contraction, in the strict sense — forgets its history. Two runs that differ at step k are both within the contraction’s basin, and each subsequent step multiplies their difference by the contraction factor, so they converge to each other as well as to the answer. Run one long enough and two machines agree to the fixed point’s own accuracy, whatever they did on the way.

That is the picture the instinct comes from, and it describes a rate that is known in advance’s stationary methods exactly: a Jacobi iteration run to convergence returns the same answer from any starting vector and, near enough, from any arithmetic.

Conjugate gradients is not that. It is a direct method degraded by rounding rather than a contraction — its Krylov space is built from its own residuals, so two runs that differ build different subspaces and minimise over them, and there is no mechanism pulling the two trajectories together. An orthogonalisation nobody calls one is the essay about how far apart those subspaces get.

So the honest general rule is: the instinct is right for contractions and wrong for Krylov methods, which is unfortunate, because Krylov methods are what anybody solving a large system is running.

What is actually being paid for #

A closing observation about where the money goes, because the sweep is also a cost measurement.

Going from a tolerance of 10⁻⁶ to 10⁻¹² costs the method about 80% more iterations — 441 to 801 on this problem, since conjugate gradients converges at a rate set by √κ and the extra digits are linear in the step count. That is a real price and it buys six orders of accuracy.

Going from an ordinary reduction to a pre-rounded one costs 1% to 22% of a step depending on the matrix and buys bitwise agreement.

So the two interventions are not competing for the same budget and they do not buy the same thing. The expensive one buys accuracy. The cheap one buys agreement. A team that has spent 80% more iterations trying to make two machines agree has bought the wrong thing at ten times the price, which is the specific waste this essay exists to prevent.

What to do when the requirement is somebody else’s #

The awkward case, and the common one: the acceptance criterion was written before anybody knew about this, it says results must match to 10⁻¹², and it fails intermittently.

There are four honest responses and they are worth ranking.

Find out what the number is being compared with. A comparison against a stored answer is harder than a comparison against a second run — the stored answer was produced by one particular machine on one particular day, and matching it exactly requires reproducing that machine’s partitioning. A criterion phrased as any two runs agree is achievable with an order-independent reduction; one phrased as matches the reference requires the reference to have been produced the same way.

Measure the actual spread before renegotiating. Run the computation at several partition counts and report the observed ratio. On this problem it is 1.2 to 1.7 relative; on a problem whose reductions have κ = 10¹² it will be far larger. A number beats an argument, and the number is one afternoon’s work.

Then either widen the criterion to a relative band above the measured spread, or buy the bitwise property. Those are the only two, and which is right depends on whether anything downstream is a verdict. What a regression test can ask for measures how much room the first option leaves: on one problem the window between the machine’s own variation and the smallest defect worth catching is a factor of 1.42, which is not much.

And do not tighten the tolerance in the hope that it helps. It is the response that costs the most and delivers the least, and this essay is the measurement that says so. It is also the response that is hardest to argue against without one, because it appears to work: the failures become rarer, since a smaller absolute disagreement crosses a fixed absolute threshold less often, and a test that fails once a month instead of once a day reads as progress rather than as the same defect sampled less.

A note on the shape of the bars #

One detail of the figure repays attention. The bars do not merely fall — their tops fall by the same factor as their bottoms, which is what makes the ratio constant. If the disagreement had an absolute floor, the bars would stop shrinking at some level and the ratio would blow up as the accuracy improved past it.

There is no such floor within the range measured, and the reason is that everything in sight scales with u: the reductions’ disagreement, the residual at which the method stops, and the forward error it corresponds to. A floor would appear if the tolerance were pushed to where the residual is comparable with the arithmetic’s own noise, which for this problem is around 10⁻¹⁵ — past the range of the sweep, and past the range at which a stopping test means anything, which is what a tolerance actually obtains’s subject.

The three knobs, and what each one moves #

Since this field has now tested all three, a table is the honest summary. Each row is a knob a caller can turn, and the columns are what happens to the two properties that keep getting confused.

Only the last row changes the property in the last column, and it is the only row that does not improve the accuracy at all. That is the field’s whole shape in four lines: the instruments that make an answer better and the instrument that makes two answers the same are disjoint sets.

The third row is worth its own note because it is the one people actually do. Pinning the thread count removes one of the three sources in the same program, twice — the number of pieces — and leaves the other two, the split points a scheduler chooses and the order the partial sums arrive in. Measured, that takes the count of distinct answers down and not to one, which is exactly the outcome that sustains the belief that the problem is nearly fixed.

One line #

A tolerance decides how accurate an answer is and has no effect at all on how many answers there are, which are two properties the same word has been carrying for as long as anybody has been writing acceptance criteria.