Rounding and cancellation

Two measurements, 1 and 0.99, each known only to within four thousandths, give a difference of 0.01. The two errors can point opposite ways, so the worst case adds them: $0.004+0.004=0.008$, which is eighty per cent of the answer [S:28:51]. Both inputs were good to better than one per cent, and the subtraction turned them into a result that is barely right at all.

Why does subtracting two correct numbers give a wrong answer? The subtraction is exact and the error was already present in the two numbers, so the small difference keeps the whole of their disagreement [S:28:51]. Each number arrived rounded, the two roundings need not point the same way, and the difference is small enough that neither rounding is diluted. !The damage a subtraction does is set by how many digits its operands share. Measured relative error climbs with the agreeing digits and stays under the ceiling of one rounding times the cancellation ratio. At the right of each curve the difference is exactly zero and the relative error is one: the machine has no digits left to be wrong with. The 64-bit curve meets the same wall about nine digits later, so a wider type buys agreement and not correctness. Status: re-simulated.

This is catastrophic cancellation: subtracting two nearly equal numbers that already carry error, so that the earlier error arrives in the answer at full size [S:28:51]. The error is not created by the minus sign, and deleting the subtraction is not available when the subtraction is the formula. The repair is always algebraic, rewriting the expression so that the cancellation happens somewhere harmless. Multiplying by a conjugate, the same expression with the sign of a square root flipped, factoring a square, writing a difference of squares as a product, or subtracting a common term are the usual moves. Each one changes the arithmetic without changing the mathematics.

One line of algebra predicts the damage. If each number carries a relative error of at most one unit roundoff, the largest relative error one rounding can cause, the difference carries an absolute error of about that size times the larger number. Each error is at most one rounding of its own number, and the larger number sets the larger of the two.

Its relative error is that quantity divided by the size of the difference. The multiplier is the cancellation ratio, the largest number divided by the answer, and it grows without limit as the two numbers agree in more leading digits. That ratio is computable from the inputs alone, which is what makes the failure predictable before the program runs.

Worked example. The 32-bit format carries twenty-four bits of precision, so above 16,777,216 the spacing between neighbouring numbers is 2 [S:114:220]. The step is $2^{e-23}$ inside the binade that starts at $2^e$, so at $e=24$ it is 2. That number is $2^{24}$, the first place where the format's step grows to two. The two candidates for the written value 16,777,217 are 16,777,216 and 16,777,218, one step each side of it, and the rule breaks the tie toward the even significand, so the stored value is 16,777,216; subtract the original number and the machine returns zero.

The first row returns zero for a difference that is one, a relative error of one hundred per cent. The second row returns two with no rounding at all, because 16,777,218 is already the even neighbour, and the failure is about spacing rather than size. Nothing in the subtraction is wrong: both subtractions are exact, and the lost digit was lost in the addition that came first. A library that offered a more accurate subtraction would change nothing here, because the subtraction had nothing to compute.

The same shape appears in longer formulas. A variance written as a mean of squares minus the square of a mean is unchanged when every value $x$ is replaced by $x+c$. Both terms of the difference grow like $c^2$, so the absolute error of the difference grows like the square of the shift. Rounding error compounds across many operations, and this is what that compounding looks like when the terms are large [S:66:72]. That is why a program can pass every test on small numbers and fail on large ones without a single line of code changing.

That pattern is common in machine learning, because a variance, the average squared distance of a set of values from their mean, is a mean of squares minus the square of a mean. When the values sit far from zero, both terms are large and their difference is small, so the computed variance loses most of its digits and can even come out negative. The formula is correct and the arithmetic is not, which is why the repair is a rewrite rather than a wider type.

The rule is a rule of thumb rather than a bound, a limit that provably holds, for sums of many terms, where the count of additions matters [S:66:72]. It also says nothing useful when the numbers are exactly representable, because then the subtraction is benign and introduces at most one rounding of its own. The dangerous case is not subtraction as such, but subtraction of results that were already approximate.

The formal statement. Let $x$ and $y$ be two real numbers, and let the machine hold them as $x(1+d_1)$ and $y(1+d_2)$, with each $d$ bounded by the unit roundoff $u=2^{-24}$ in binary32. Suppose the subtraction of those two stored values is computed exactly. Then the absolute error is at most $u(|x|+|y|)$, and the relative error is at most that quantity divided by $|x-y|$. The factor $(|x|+|y|)/|x-y|$ is the cancellation ratio. It is at most twice the core's version, which divided the larger operand by the difference.

The derivation. Expand the stored difference:

$$\text{stored difference}=(x-y)+(x{d}_1-y{d}_2)$$

The first term is the answer and the bracket is the error. Bound each product by $u$ times its operand and add the two bounds. Divide by the size of the true difference to turn an absolute bound into a relative one. Nothing else enters, so the ratio is exact for this model.

The step I omit is the claim that the subtraction itself is exact. It holds when the two operands lie within a factor of two of each other. Both then share an exponent or differ by one, and the difference of two twenty-four-bit significands at that scale fits in twenty-four bits. Outside that window the subtraction rounds once more. The absolute error is then at most $u(|x|+|y|)+u|x-y|$, hence at most $2u(|x|+|y|)$, and the relative error is at most $u\left(1+(|x|+|y|)/|x-y|\right)$. The sharper bound $u(|x|+|y|)/|x-y|$ holds only when the subtraction is exact, as the formal statement assumes.

The edge case. The ratio is computed from the size of the operands, not from the size of their error. When the operands are themselves results of long sums, each carries an error that grows with the number of additions, and the ratio multiplies that larger error. A naive sum of $n$ terms can carry error of order $n$ times one rounding [S:28:56]. A variance computed as a mean of squares minus a squared mean is the standard case, and it can come out negative. The one-rounding premise is what fails, not the ratio.

What the core hid. The core said the subtraction is exact. That is a theorem with a hypothesis, not a property of the minus sign. The hypothesis is that the two stored values lie within a factor of two of each other, and it is why the failure is about spacing rather than arithmetic.

Where the analogy breaks. "The error arrives at full size" suggests the error is carried in the digits. In the model above the error sits in the operands' last bits, and the subtraction does not move it. The leading digits of the answer are right, and its trailing digits are the operands' trailing digits. The result is not wrong in the way a wrong sum is wrong. It is right to fewer digits than the inputs were.

Original sources. The example you met is Example 2.4 in chapter 2 of Solomon [S:28:51], which also defines absolute and relative error. The same chapter separates forward from backward error and defines the condition number as the ratio of the two [S:28:54]. Goodfellow states the compounding case, where rounding error grows across many operations and makes a sound algorithm fail in practice [S:66:72].

An open question. How error accumulates across a long reduction is not settled for the formats now in use. A naive sum of $n$ terms carries error of order $n$ times one rounding, and compensated summation brings it to a term linear in $n$ but quadratic in the rounding [S:28:56][S:28:57]. Which of the two is acceptable at sixteen bits, for a reduction of the length a training step performs, has no agreed answer. Evidence that would settle it: the same reduction run against exact arithmetic at several lengths and in both formats, with the error measured rather than bounded. The measurement has to keep the summation order the hardware uses, because every bound here depends on that order. It also has to report the worst case across rows, since an average over a tensor hides the rows that lost every digit.

A frontier result. Compensated summation has moved from a textbook remedy to a training default. One systems course states that pure bfloat16 training is viable when the reductions use Kahan summation, and it budgets memory in bytes per parameter [S:100:76]. That is the trade Solomon describes, made at the scale of a model.

What to read next. Read sections 2.2 and 2.3 of Solomon for error classification, conditioning and the summation analysis [S:28:51][S:28:57]. Read chapter 4 of Goodfellow for the same failure inside a learning algorithm [S:66:72]. Then read the memory-planning section of the systems course to see the compensation priced against the optimizer state [S:100:76].