The fifth author

Three errors and one number is this field’s inventory. It sets out four authors of a wrong answer, the first two from the identity this site is built on and the second two from the fields that came after:

Every one of those four is a statement about one computation: this answer, and how far it is from the truth, and whose fault the distance is.

There is a fifth, it does not fit the table’s shape, and the way it does not fit is the point of this essay.

The measurement #

One vector of 4,096 binary64 numbers. One summation algorithm. One precision. Twenty-six ways of dividing the work across workers, which is what a parallel reduction is.

Twenty-one distinct answers.

Now apply the four columns. The problem’s conditioning is one number and it is the same for all twenty-six. Each run’s backward error is at the rounding level — every one of them is the exact sum of a vector within a rounding of the given one, which is the definition the exact answer to a nearby problem sets out. Nothing was reformulated: a sum is a sum. Nothing was approximated: no function was replaced, no degree chosen, no target set named.

Four authors, all silent, and twenty-one answers.

What the fifth author is #

The implementation. Not the algorithm — the algorithm is fixed and is the same in every run — but the choices a machine makes about how to execute it: how many pieces a reduction is divided into, where the cuts fall, whether a multiply-add was fused, which kernel a length selected.

Set beside the other four it is different in every column:

The last row is the one that makes it a fifth term rather than a special case of one of the others. Conditioning, backward error, reformulation and approximation are all quantities attached to a single computation and its single answer. The implementation’s contribution has no meaning for one run: a single answer is exactly as correct as the identity says it is, and the fifth author appears only when a second run exists to disagree with it.

Where it goes in the identity #

The identity, as it stood after the two newest fields:

forward error  ⪅  ‖g − r‖  +  κ(linearised) × backward error.

The fifth term does not go in it, and saying why is more useful than forcing it.

Every term above bounds the distance between one computed answer and the truth. The fifth quantity bounds the distance between two computed answers, and the two statements have different subjects. What can be said, and is measured in a bound every answer satisfies, is a companion inequality:

|answer(machine A) − answer(machine B)|  ≈  0.25 · κₛᵤₘ · u,

where κ_sum is the summation condition number of the reductions involved — a quantity computable in one pass over the caller’s own data and absent from every library’s output. The 0.25 in it is a mean, and how much of a mean is the next section.

Two cautions on that constant before it is carried anywhere. The 0.25 is a mean over one vector length as well as over its orderings: across lengths from 256 to 8,192 the same ratio runs between 0.049 and 0.258, a factor of five. And the room the classical bound leaves is not a fixed 7,932 — that is the figure at 2,048 terms, and across the same lengths it runs from 2,008 to 1.5·10⁵. Both numbers are properties of a vector rather than of the identity, which is the ordinary condition of a constant in front of a κ.

Two statements, then, rather than one. The identity says how wrong an answer may be. The companion says how much two answers may differ. The second is not implied by the first, because the first is satisfied by both answers with room to spare — between three and five orders of it, depending on the length — and a bound covering both cannot separate them.

The identity’s own terms are worth seeing move, because one of them moves the wrong way.

The backward error falls by six while the forward error rises past one. Across n = 10, 12, 14, 16, 18 and 20 the backward error runs 2.3·10⁻¹⁷, 1.8·10⁻¹⁷, 5·10⁻¹⁸, 7.4·10⁻¹⁸, 3.9·10⁻¹⁸ and 3.9·10⁻¹⁸ while the forward error runs 2.7·10⁻⁴, 0.02, 19, 3.1, 35 and 7.1, with κ climbing from 1.6·10¹³ to 4.9·10¹⁸.

That is the identity holding while every term in it misleads separately. The only factor that tracks the damage is κ, and κ is the one term of the three that no computation produces as a by-product — which is the same shape as the fifth author itself: the quantity that would have told the caller something is the quantity nothing prints.

The quarter is a mean, and the scatter around it is a factor of six #

A constant in a companion inequality deserves the same scepticism the identity’s own terms get, so it was measured across data rather than on one vector. Twelve cancelling vectors at each of seven lengths, all at κ_sum = 10⁶, all reduced across the same seven partitionings, with the ratio spread ⁄ (κ_sum · u) recorded for each:

Two things come out of that table and the first is a correction.

The averaged constant does not depend on the length. Fitted in the log, the mean has a slope of −0.105 in n and the median −0.041, which is flat over six doublings. That matters because the single vector this site’s own gate reads gives −0.41 over the same range — 0.86 at n = 128 falling to 0.12 at 4,096 — and a check built on it concluded that the constant falls with the length of the reduction. It does not. The trend was the seed, and the gate’s wording has been changed to say what it actually measures.

The scatter across data is real and it is large. At n = 4,096 the ratio runs from 0.087 to 0.559 over twelve vectors drawn from one family at one conditioning: a factor of six and a half, on inputs that differ in nothing a caller could see. Every length shows at least a factor of two and a half. So 0.25 is a fair central value — every mean in the table sits between 0.15 and 0.26 — and it is not a value: a caller predicting their own machine disagreement from 0.25 κ_sum u should expect to be within a factor of three, not within a few per cent.

Which is worth stating without apology, because it does not weaken the argument this essay is making. The point of the companion inequality is that the fifth author’s contribution has a computable size where every instrument in the subject reports zero. Going from no estimate at all to within a factor of three is most of the distance; going from a factor of three to a few per cent would be a refinement of something already useful. And the imprecision is in the right direction for its purpose — a tolerance set from 0.25 κ_sum u with a factor of ten of headroom is still orders below the defect any regression test is trying to catch.

There is one more reading in the table and it belongs to the essay’s own argument about what a fifth author is. Every other term in the identity has a value for a given computation: a condition number, a backward error, an approximation error, each of them a number that exists whether or not anybody looks. This one does not. The 0.25 is a statistic over an ensemble of runs, and the ensemble is over data as well as over partitionings — which is why it scatters by a factor of six on inputs that share a conditioning. That is not a defect in the estimate. It is the fifth author’s own character showing up in the constant that describes it: a quantity about a set of computations cannot have a per-computation value, and asking for two per cent is asking a statistic to behave like a property.

assertTheQuarterIsAMeanAndNotAValue holds the flatness in n, the steeper single-seed slope beside it, the factor of six at one length, the factor of two and a half at every length, and the range the means fall in. It is the fifth author measured on itself: a constant that looked stable because it had been read once.

It is a backward error, and that is the reframing that helps #

The most useful thing the field found is that the fifth author is not a new kind of quantity after all, once it is measured in the right units.

What a regression test can ask for measures the run-to-run variation on a solve at 3.2·10⁻¹² and the problem’s amplification at 4.3, so the machine’s disagreement is equivalent to a perturbation of the data of about 7.5·10⁻¹³ — a few thousand unit roundoffs, which is what several hundred amplified roundings in a 674-step iteration comes to.

So the fifth author perturbs the problem, exactly as a backward error does, and differs from the second author in one respect: the second is a property of the algorithm and is the same on every machine, while the fifth is drawn afresh from the implementation on every run.

That reframing pays for itself twice.

It says the magnitude is predictable. A backward error has a size, and this one’s is κ_sum·u.

And it says what a test can ask for. No procedure can distinguish two problems that differ by less than the backward error committed on them, so no regression test can catch a defect smaller than the implementation’s own perturbation. That is not a limitation of testing; it is the subject’s central bound, appearing in a place nobody expected it.

Three implementations, three mechanisms #

The fifth author is one term in the inventory and three distinguishable mechanisms underneath it, and a diagnosis needs to know which.

The partitioning of a reduction. How many pieces, and where the cuts fall. Varies between machines, between runs on one machine with a work-stealing scheduler, and with an environment variable. It is the field’s main subject, its size is κ_sum·u, and it has a clean repair: the sum that cannot be wrong, at three operations an element.

Expression contraction. Whether a multiply-add was fused, decided at compile time from source that says nothing about it. One rounding wide, and enough to compute a determinant of one as zero. Repaired by writing the fused form explicitly, or by forbidding the contraction — and, measured over two hundred matrices, neither form is the correct one: a matrix that is definite on one machine finds the unfused build right seventeen times out of twenty-six.

Algorithm selection. Which kernel a size selected, which is a constant in a library’s source. Has no repair at the call site at all, and is the one that survives after everything else has been made deterministic.

The three are independent, they compose, and they are repaired by three different actions — a summation policy, a compiler flag, a pinned version. A diagnosis that names the fifth author without naming which of the three is a diagnosis that cannot be acted on.

The five, as a diagnostic #

The practical use of an inventory is a sequence of questions, and the fifth adds one. Three errors and one number ends with four; here they are with the fifth, in the order worth asking them.

Was the problem sensitive? Its condition number. Rules out the answer most people reach for first.

Was the algorithm unstable? Its backward error against the object it factorised.

Was something reformulated? If a quadratic became a pencil or a least-squares problem became a normal-equations solve, the reformulated object’s conditioning is a third quantity.

Was anything approximated? If a function was replaced before the arithmetic began, the approximation error is a term in front of everything and is usually the largest.

And: does the answer change when nothing does? Run it again with a different thread count. If the answer moves, the fifth author is present, its size is κ_sum·u, and no amount of care in the other four will remove it.

The fifth question is the only one of the five that is answered by running the computation again rather than by computing a quantity, which is a fair description of how different it is.

Why it took nineteen fields to reach #

The same question three errors and one number asks about the third and fourth authors, and the answer here is different from both.

The third and fourth were found by sweeping a parameter that was supposed to be free — a change of units that is exact, a target set that changes no eigenvalue — and watching something move. That technique needs a parameter, and the fifth author has none: there is no argument to a computation that says how many workers to use, and nothing in a program’s text mentions it.

What found this one instead was running the same thing twice, which is not a technique anybody applies to a deterministic program. A numerical analyst measures an error against a truth. A software engineer runs a test once and records whether it passed. Neither of those workflows has a step at which one computation is executed several ways and the answers compared with each other rather than with anything external — which is exactly the measurement every figure in this field is.

The instrument is trivial and it is not in either tradition’s toolkit. That is the whole reason a site with nineteen fields of error analysis had no term for a quantity that is present in every parallel program running today.

What it costs to have missed it #

Two costs, and the second is the expensive one.

A misattributed diagnosis. A team that sees two machines disagree and has only four authors available will assign it to one of them: the problem must be ill conditioned, or the library must have a bug, or the data must have changed. All three are investigable, none is the cause, and the investigation ends without an explanation — which is where floating point is non-deterministic enters as folklore, correct and useless because it comes without a number.

And a test suite that is quietly disabled. A regression test that demands more agreement than the arithmetic can supply fails on correct builds, and a test that fails on correct builds is a test people stop believing and then stop running. The defect that arrives afterwards is caught by nothing. That sequence is the most damaging consequence of the missing term, and it is entirely preventable by measuring the band once.

What the four authors do to the fifth #

The five are not a list of alternatives; they compose, and two of the compositions are worth naming because they are where the field’s numbers get large.

Conditioning amplifies it. The fifth author perturbs the problem by about κ_sum·u in the reductions and the problem’s condition number amplifies that perturbation into the answer, exactly as it amplifies a backward error. So a badly conditioned problem has a larger disagreement for the same reason it has a larger error, and a stopping test is a race measures both together: at κ = 100 every partitioning takes the same 21 steps, and at κ = 10⁴ they take between 674 and 690.

A chaotic algorithm amplifies it further. Conjugate gradients builds its search directions from its own residuals, so two runs that differ at step three build different subspaces from step four onward. The perturbation is 10⁻¹³ and the trajectories separate over hundreds of steps into a difference of sixteen iterations. That amplification belongs to the algorithm rather than to the problem, which means the second author and the fifth interact in a way the identity’s product form does not capture.

The honest statement, then, is that the fifth author’s contribution is κ_sum·u and its effect is that times whatever the problem and the method amplify it by — which is the same two-factor structure the site was built on, applied to a perturbation nobody chose.

What the fifth author is not #

Three exclusions, because a term this broad attracts things that belong elsewhere.

It is not the conditioning. Two machines are handed identical data. Nothing is perturbed on the way in; the perturbation is committed by the execution.

It is not randomness in the algorithm. A randomised method draws from a seed the program owns and can record, so its variation is reproducible by construction — a bound that holds with probability is where this site keeps that vocabulary, and the difference is that a seed is written down.

And it is not a bug. Every run is correct. The whole difficulty is that correctness, as the subject defines it, is a property each of the twenty-one answers has.

What a library would have to change #

The inventory is only worth extending if the extension implies an action, so: five things, none of them research.

Return κ_sum beside a reduction. One pass, no estimator, and it turns the answers might disagree into a number.

Return the partitioning. One integer, known to the runtime and to nobody else, and enough to reproduce a result rather than merely to observe that it cannot be.

Document the cutoffs. Which kernel a size selects is already in the source; saying it affects results costs a line.

Offer an order-independent mode. Three operations an element for the cheap version, and the literature for it is decades old.

And say all three sentences in the specification rather than only the first — that the answer is the exact result for nearby data, that two runs may differ by about κ_sum·u, and that the reproducible mode makes the answer a function of the inputs alone.

Every one of those is available today. What was missing was a reason to think of them as one thing, which is what a name for the fifth author is for.

The one line #

Four authors describe how far one answer is from the truth. The fifth describes how far two answers are from each other, it is a backward error the implementation commits rather than the algorithm, it is 0.25κ_sum·u, and every instrument this site has built reports zero for it.