Accuracy and agreement are different properties

Here is a sentence that sounds like a tautology and is false:

A more accurate computation is a more reproducible one.

It is false in both directions, and the measurements that show it are on one figure. On a vector with a summation condition number of 10⁶:

• the ordinary eight-piece reduction is wrong by 2.7·10⁻¹¹ and returns 72 distinct answers over four hundred permutations;
• one-pass pre-rounded summation is wrong by 2.3·10⁻⁷ — four orders worse — and returns one.

The reproducible policy is the less accurate one, on the same data, at the same precision, at three operations an element instead of one.

The two-by-two #

Set the two properties against each other and every box has an occupant except one.

The bottom-left corner is the one that matters. Kahan’s loop is the most accurate policy per operation on the figure and it is not reproducible — 119 distinct answers over four hundred permutations, against a plain loop’s 303. Improving the accuracy by four orders of magnitude improved the count of answers by a factor of two and a half, and a factor of two and a half is not progress towards one.

The top-right corner is the mirror image and is the one that surprises people who have just been told that reproducibility is worth having. One-pass pre-rounding is deliberately less accurate: it throws away the low bits of every addend so that no partial sum can round. The discarded bits are the accuracy. It is buying agreement with them.

And the empty corner — cheap, accurate, order-independent — is empty for the reason what determinism costs sets out: the cheapness of the plain loop is its freedom to round wherever the arithmetic lands.

Why the two get conflated #

The conflation has a specific and forgivable source. In the ordinary situation — a well-conditioned sum, positive terms, κ near one — the two properties really do move together, because there is almost no rounding for the order to change. Every policy is accurate and every policy agrees to the last bit or two. A practitioner whose experience is that situation has never seen the two come apart, and generalises correctly from everything they have observed.

They come apart when the sum cancels, which is exactly the case the vector that hides it shows is the case a program makes decisions from. So the two properties are indistinguishable on the reductions nobody cares about and independent on the ones that matter.

Backward stability does not decide it either #

There is a second conflation and it is subtler, because the vocabulary that produces it is this site’s own.

The exact answer to a nearby problem sets out the standard by which every algorithm here is judged: a computation is good if its answer is exact for data within a rounding of what it was given. Every policy on the hero figure is backward stable by that standard. So is every one of the twenty-six answers in the same program, twice. Backward stability is a statement about each run separately and says nothing whatever about a set of them.

That is worth pausing on because it is the deepest reason this field needed to exist. The site spent nineteen fields building a vocabulary in which good means backward stable, and there is a property a computation can have or lack which that vocabulary cannot express — not because it is subtle, but because it is a property of a set of computations and every term in the vocabulary is a property of one.

The nearest thing the literature has is the observation that a backward stable algorithm’s answer is determined only up to a perturbation of the data, so two implementations may differ by that much. True, and it is an upper bound rather than a description: it says the answers lie within a rounding of each other in data terms, which is κu in answer terms — the same number a bound every answer satisfies measures at 0.25κu — and it says nothing about whether they will differ, by how much on this data, or whether it can be prevented.

What each property is worth, separately #

Since they are independent, they have to be bought separately and justified separately.

Accuracy is worth buying when the value is used. A residual that goes into a bound, an inner product whose magnitude is the answer, a norm reported to a reader. The right instruments are compensation and, if the cost allows, exact accumulation, and the trade is well understood.

Agreement is worth buying when the value is compared. A stopping test, a rank threshold, a definiteness sign, a regression check. The right instrument is an order-independent policy, and the accuracy it delivers is almost beside the point provided it clears the threshold by a comfortable margin.

The second sentence is the useful one because it inverts the usual reasoning. For a verdict, an inaccurate reproducible answer is better than an accurate irreproducible one — provided the accuracy clears the threshold. The policy to buy there is the cheap one that this essay’s figure puts in the top-right corner and that an accuracy-focused reading would reject out of hand.

The proviso is not a formality #

A rank threshold at σ₁·10⁻¹⁴ sounds like the case that does not care about accuracy. On the problem this site keeps drawing — a Gram matrix of a 60 × 14 matrix with a geometrically decaying spectrum — it cares a great deal:

The truth, from an SVD of the matrix itself, is 13.

Every policy is wrong, including the exact one. The reproducible policies agree on 11 and the accurate ones agree on 11, and the answer is 13 — so agreement here is agreement on a wrong verdict, and accuracy in the summation does not reach the verdict at all. Pre-rounding’s singular values are thirty-one times less accurate than exact accumulation’s and both return the same integer.

The reason is that the error is committed before any policy applies. Forming AᵀA squares the conditioning, so the small singular values arrive at the eigensolver already wrong by two to four orders, and no choice about how to add up sixty products can undo it.

So the two-by-two stands and this example under it does not. What it shows is a third property that dominates both: whether the quantity being thresholded is resolvable at the working precision. Buying agreement for a verdict is right advice; buying it for this verdict buys a reproducible 11 where the answer is 13, and the repair is not a summation policy — it is not forming the Gram matrix.

That third property deserves a name because it is what makes the other two worth arguing about. Call it resolvability: whether the quantity a decision reads is above the noise the computation carries. It is not accuracy — a quantity can be computed to the last bit and still be below the noise of the object it came from, which is what a squared condition number does. And it is not agreement — several policies can agree on a quantity that means nothing, which is what the table above shows five of them doing.

The ordering that follows is worth carrying because it is the reverse of the order in which the three are usually addressed. Resolvability first: if the quantity is below the noise, no policy helps and the repair is upstream, in how the quantity was formed. Agreement second: once the quantity is resolvable, an order-independent policy makes the verdict a property of the problem. Accuracy last: it matters when the value is read rather than compared, and for a verdict it is the cheapest of the three to give up.

The essay’s own recommendation is the middle line of that, and the reason it needed a proviso is that the first line was missing.

The corner that is empty, and whether it has to be #

A reader who accepts the table will ask whether the empty corner is empty by necessity or by accident. The honest answer is: by necessity in software, and not in hardware.

In software the argument is short. A reduction that is order-independent must produce, from each prefix of the terms, something that later additions cannot round differently — which means either every intermediate is exact (accumulate exactly, and pay for the state) or every intermediate is representable by construction (pre-round, and pay for the arithmetic that snaps them). There is no third mechanism, and both cost more than one add.

In hardware the picture is different, and it is the one place where the trade could disappear. A fixed-point accumulator wide enough to hold every binary64 product — Kulisch’s proposal, about 4,288 bits — makes an exact dot product a single instruction sequence with no rounding in the interior at all, at which point the exact policy costs one add per element and the whole of this essay’s table collapses to one row. That register has been proposed repeatedly, is in no mainstream processor, and its absence is the reason the trade exists.

Which is worth stating precisely because it locates the constraint. The empty corner is not a theorem about arithmetic. It is a consequence of the accumulator being 53 bits wide, and a machine with a wide enough accumulator would have accuracy and agreement together for the price of neither.

And the price of the corner that is occupied is not fixed — it grows with the conditioning.

The reproducible policy’s error tracks κ exactly and the best achievable does not move. At κ = 10², 10⁴, 10⁶ and 10⁸ the cheapest reproducible answer is 1.91·10⁻¹¹, 2.14·10⁻⁹, 2.29·10⁻⁷ and 2.29·10⁻⁵ — a hundredfold per hundredfold, exactly proportional — while the most accurate policy sits at 10⁻¹⁷ at every one of them.

So the gap between the two corners widens from six orders to twelve. That changes what the table means for a caller: at κ = 100 the choice between the accurate policy and the reproducible one costs six digits, which many applications can spend; at κ = 10⁸ it costs twelve, which is the whole of a double. The trade is not a fixed premium paid for reproducibility — it is a premium that scales with the problem, and the empty corner therefore matters most on exactly the problems where reproducibility is most often demanded, because a badly conditioned solve is the one whose results people compare across machines.

A third property, named so it is not conflated too #

There is a third thing the word reproducible is sometimes made to carry, and it belongs to a different part of the subject.

Stability under perturbation of the data — that a small change to the input produces a small change to the output — is the condition number, and this site has nineteen fields about it. It is not what this field means. Two machines given identical data return different answers here; no perturbation of the input is involved and the condition number of the underlying problem is the same for both.

The three are genuinely distinct and each has its own instrument:

• conditioning — how the answer moves when the data moves. Measured by κ of the problem.
• backward stability — how far the data would have to move to make this answer exact. Measured by the backward error.
• order-independence — whether two correct implementations return the same bits. Measured by a bitwise test over permutations, and by nothing else. It has no units, no bound and no estimator; it is the only property in this list that a number cannot carry, which is why it is reported as a property of the routine rather than of the answer.

The first two multiply to give the forward error, which is the identity the site is built on. The third is not in it. That is the observation the fifth author turns into a term.

The word that carries both, and what it costs #

English has one word doing both jobs and the ambiguity is not harmless.

Reliable is the word most often used, and a reader hears whichever property they already care about. A numerical analyst hears backward stability. A person maintaining a test suite hears bitwise agreement. A user who has just seen two answers hears this should not have happened. The three readings are compatible with the same sentence and lead to three different next actions — tighten the tolerance, pin the threads, file a bug — of which at most one is right.

The most expensive version of the confusion is a specific and common exchange. Two machines disagree; somebody proposes higher precision; the disagreement shrinks and does not go away; the conclusion drawn is that the problem is nearly solved and a little more precision will finish it.

It will not, and the reason is on this essay’s figure. Every quantity in the run-to-run variation carries exactly one factor of u — where the disagreement comes from derives it as κ·u times a constant — so doubling the precision divides the disagreement by 2⁵³ and leaves the count of distinct answers exactly where it was. The answers move closer together and there are still many of them. A bitwise test fails just as reliably at quadruple precision as at double, and the effort has bought accuracy that was not the problem.

The measurement that settles it is in this field’s tolerance essay rather than here, because it is easier to see with a tolerance than with a format: the ratio between the best and worst run is 1.34, 1.48, 1.71 and 1.17 as the tolerance falls through four orders of magnitude, which is the same statement about u wearing different clothes.

What to write in a specification #

The practical residue of all this is a sentence that a person can put in a document, and the field’s version has three clauses because the properties do.

This routine returns the exact sum of a vector within one rounding of the one supplied — that is backward stability, it is what the literature guarantees, and it is true of every policy here.

Its answer may differ between runs by about κu, where κ is Σ|xᵢ| ÷ |Σxᵢ| for the data supplied — that is the run-to-run variation, it is not in any specification this site has read, and it costs one pass to compute.

Under the reproducible option its answer is a function of the multiset of inputs — that is the third property, it is bitwise, and it is worth stating separately because it is the one a test suite depends on.

A specification with the first clause alone is what exists today, and it is why a reader who observes two machines disagreeing concludes that one of them is broken. All three clauses fit in three lines and only the second requires a measurement.

Where the site itself sits #

An uncomfortable question, asked because the site’s habit requires it: which of the two properties do this collection’s own figures have?

They are accurate — every number is checked against a second route, and against an exactly known answer wherever one exists. They are also bitwise identical between builds, which is a requirement rather than a happy accident: every generator draws from a seeded stream, and a figure whose bytes changed between two builds of the same source would show up as a content hash that moved and would fail the check that a rebuild reproduces the deploy.

But that reproducibility is bought the cheap way, by never dividing the work. Every figure here is computed in one process, in one thread, in one order. The site is in the bottom-left corner of this essay’s table — accurate, and order-dependent — and it never notices because nothing ever changes the order.

Which is exactly the position most numerical software is in until the day it is parallelised, and it is the reason the effect arrives as a surprise rather than as a known cost. The order-dependence was always there. What a machine with more than one worker does is reveal it, and the vocabulary in which the software was specified has no sentence for what was revealed.

What a reader should take from the empty corner #

Two things, and the second is the one that changes a decision.

The first is that there is no default to fall back on. A policy has to be chosen, and choosing not to choose is choosing the plain loop — which is right for most reductions and wrong for the ones a verdict is read from. The vector that hides it is how to tell which is which, in one pass over the data.

The second is that the choice is made per reduction rather than per program. A solver can compute its residual norm with an ordinary loop and its stopping test’s inner product with a pre-rounded one, and the two decisions are independent because the properties are. That is a much cheaper prescription than make the code reproducible, and it is available only once the two properties have been separated.

One line #

Accuracy is how close an answer is to the truth; agreement is whether two machines return the same bits; and this site’s fifty-three-bit accumulator makes them trade against each other, so a policy has to be chosen for one of them and the choice depends on whether the number is read or compared.