A coin flip that fixes the average

The direction the error leans ends on a failure its own measurement could not describe. Below thirteen significand bits every rounding mode’s error grows linearly, and the fitted exponents go above one — 1.09 for round-to-nearest, 1.49 for rounding up — which is not what an accumulation of rounding errors does.

What has happened is that the sum has stopped.

Add a small number to a large one often enough and the small one stops arriving. Once the addend is below half an ulp of the running total, round-to-nearest returns the total unchanged — and it will go on doing so forever, because the total is not moving and neither is the ulp. The computation does not drift, does not degrade and does not warn. It stops.

At eight significand bits, a total near 256 has an ulp of 2, so half an ulp is 1, and adding 0.1 to it a thousand times leaves it at exactly 256. The true answer is 356.

The failure with no error bound #

Every bound on this site has the same shape: the computed answer is within something times the unit roundoff of the true one, or within something times u times a condition number. Stagnation does not fit any of them, and the reason is worth spelling out.

The stagnated total is not the result of accumulated error. It is the result of an operation that had no effect, repeated. Each individual addition is correctly rounded — 256 + 0.1 rounds to 256, because 256 is the nearer representable number and it is nearer by a wide margin — so every step satisfies the error bound for one addition, exactly. The bound for n additions, nu times the sum of the magnitudes, is also satisfied: 28% is well inside it at eight bits and a thousand terms.

So nothing is violated. What has gone wrong is that the bound was never a bound on anything useful here, and the honest measurement is a different one: how many times did the total change? Round-to-nearest: zero. Stochastic rounding, same data, same precision: forty-six.

That count is the measurement this essay reports, because it is the one that distinguishes a computation which is inaccurate from one which has stopped computing.

The threshold is arithmetic, not a regime #

The cliff is not gradual. Half an ulp of the running total is a specific number, and either side of it the behaviour is completely different.

At a total of 256 with eight significand bits, the spacing is 2⁸·2⁻⁷ = 2, and half of it is 1. An addend of 0.9 disappears entirely; an addend of 1.5 is added every time. That is checked both ways: the closed form is asserted against the observed threshold, and an addend at 1.5 times the threshold is asserted to keep moving the total.

Two consequences follow from having the number rather than the phenomenon.

It depends on the total, not on the data. As a sum grows its ulp grows, so a summation that starts fine can stagnate part-way through, at the point where the running total first exceeds 2·addend·2^p. Nothing about the addends changed.

It is a property of the significand alone. The exponent range does not appear. So bfloat16 and fp16, which the exponent-range essay separates by twenty-three decades, stagnate at different thresholds only because their significands differ — eight bits against eleven — and a format with an enormous range stagnates just as readily as a narrow one.

Three places it happens that are not contrived #

The experiment above is a small number added to a large one a thousand times, which reads as a constructed case. It is not; it is the shape of three ordinary computations.

A long reduction. Summing n values whose magnitudes are similar produces a running total that grows like n while the addends stay put, so the ratio between them is n and the stagnation condition is n > 2^(p+1). At eight significand bits that is 512 terms; at eleven it is 4,096; at bfloat16’s eight it is 512 again. Those are not large sums. This is why a reduction at low precision is performed in a wider accumulator on every piece of hardware that offers one, and why the mixed-precision field is about where the wide part goes.

A weight update. Add a small increment to a parameter, repeatedly, with the increment several orders of magnitude below the parameter. That is the same arithmetic with the roles named differently, and at eight significand bits an increment below a two-hundred-and-fifty-sixth of the weight never lands.

A time integration. Advance t by a fixed step for many steps. Once t exceeds 2^p times the step, t stops advancing — a loop counting to 10¹⁷ by ones in double precision does not terminate, which the ulp essay draws, and it is this failure with p = 53 rather than 8.

All three share the structure that makes stagnation invisible: the running quantity is plausible, its magnitude is right, and there is no residual to check it against. A sum has no equation it is supposed to satisfy.

What stochastic rounding does #

Round up with probability equal to the distance up, down otherwise. At 256 + 0.1 the exact sum is one twentieth of the way from 256 to 258, so the answer is 258 one time in twenty and 256 nineteen times in twenty.

The total therefore climbs in whole ulps at a twentieth of the rate, and it arrives. Measured over the same thousand additions with a fixed seed: forty-six movements, finishing at 348 against a true 356, a relative error of 2.2% where round-to-nearest’s is 28%.

Nothing here is subtle and it is worth saying what it is not. The stochastic mode does not represent 0.1 more accurately — it cannot, 0.1 is not representable and neither is 256.1. What it does is decline to discard the information, by converting a quantity too small to represent into a probability, which is representable at any precision.

That is why the mode appeared in hardware. The low-precision training loop is a sum of many small updates into a large weight, which is exactly this failure, and a weight that has stopped moving is a weight that has stopped learning.

What it costs, which is not nothing #

The honest accounting, and it is not the one a reader expects.

Removing the bias does not make the error smaller. It makes it a different error — with mean zero and a variance round-to-nearest does not have — so away from the stagnation regime, on an ordinary sum where both modes work, round-to-nearest wins.

Measured over sixty seeds at n = 300 and 24 significand bits, where nothing stagnates: stochastic rounding is the worse of the two on 39 of the 60 runs, and its root-mean-square error is 1.69 times round-to-nearest’s. Its mean signed error is 3.7·10⁻⁸ against an rms of 3.9·10⁻⁷, so the error does average towards zero over runs — which is the property being bought.

So the trade is:

and neither line dominates. The exponents from the previous essay are 0.47 and 0.50, so the two grow at the same rate; what differs is the constant, and it is worse for the stochastic mode.

There is a second cost, which this site’s simulation makes visible in a way hardware hides: stochastic rounding needs randomness. Every operation consumes a random draw, which in hardware is a small linear-feedback generator on the rounding path and in software is a real cost. It also makes the computation non-reproducible — the same program on the same data returns different answers — unless the generator is seeded, which is why every figure here is drawn from a fixed stream.

The site’s arithmetic refuses to run a stochastic context without a random source rather than falling back to round-to-nearest, and that refusal is asserted. A stochastic rounding that had quietly stopped being stochastic would produce entirely plausible numbers and would falsify every claim in this essay at once.

How the count behaves as the addend shrinks #

One more measurement, because it says what the mode’s guarantee actually is.

The stochastic total’s expected value after n additions is exactly the true total, whatever the addend: each step adds the addend in expectation, by construction. What varies is the variance, and therefore how close any one run lands.

Each step is a Bernoulli draw scaled by one ulp, so after n steps the standard deviation of the total is about ulp·√(np(1−p)) with p the fractional position of the addend in its interval. At the parameters here — ulp 2, n = 1,000, p = 0.05 — that is about 13.8, against a total displacement of 100. So a single run should land within roughly 14 of the truth, and the measured run lands 8 short of it.

Two things follow. The error of a stochastic run scales like √n where the quantity being accumulated scales like n, so the relative error improves as the sum gets longer — the opposite of every other failure mode in this field. And the smaller the addend relative to the ulp, the smaller p is and the smaller the variance, so the mode gets more reliable exactly where round-to-nearest gets less: at p = 0.05 the standard deviation is 13.8, and at p = 0.5, where round-to-nearest is at its most accurate, it is 31.6.

That crossover is the cleanest statement of when to reach for the mode. It is not a better rounding; it is a rounding whose error is largest where the alternative’s is smallest.

Where it does not help #

Stochastic rounding is not a general improvement and the boundary is easy to state.

It helps where the information being lost is systematically in one direction and would otherwise be discarded entirely: an accumulation of small increments into a large total, a reduction at low precision, a weight update. There the loss is a bias and the mode removes it.

It does not help where the error is already unbiased, which is most computations at reasonable precision — there it adds variance for nothing, at the measured cost of 1.69 times the rms error.

And it does not help with cancellation. Subtracting two nearly equal numbers destroys the leading digits of the answer, and the essay about it shows what is left; the digits were lost long before the subtraction, and no rounding mode recovers them because none of them is what threw the information away.

Reproducibility, which is a real objection #

The mode’s cost that gets least attention is not arithmetic at all.

A stochastic rounding makes the same program on the same data return different answers on different runs. That breaks a property most numerical software is built on and most testing depends on: a regression test that compares against a stored result has nothing to compare against, a bug report that says “it returned 348” cannot be reproduced, and a computation split across machines does not agree with itself.

The usual answer is to seed the generator, which recovers reproducibility for a fixed number of processors and loses it again the moment the work is divided differently — the draws are consumed in a different order. That is the same problem the order essay has with summation, arriving through the random stream instead of through the additions, and it is worse: a reordered sum gives a different answer within the error bound, and a reordered stream gives a different sequence of roundings whose only guarantee is in expectation.

Every figure on this page is drawn from a fixed stream for exactly this reason, and it is worth naming as a choice rather than leaving as an implementation detail. The claim being illustrated is about a distribution; the picture is one draw from it, and a reader is entitled to know that a different seed would give a different staircase reaching the same place.

What is asserted, and what refuses #

The total never moves: zero changes in a thousand additions, and a final value equal to the starting one to the bit.

The threshold is where the closed form puts it: half an ulp of 256 at eight bits is exactly 1, checked against the observed behaviour, and an addend at 1.5 times it is asserted to keep arriving — so the threshold is a threshold rather than a description of one experiment.

Stochastic rounding keeps moving: more than twenty changes over the same thousand additions, and a relative error more than ten times smaller.

And it is worse on a single run, asserted in three parts: the worse of the two on most of sixty runs, a larger root-mean-square error, and a mean that still averages towards zero. A phase that reported only the first two of those would be reporting a mode nobody would use.

The claim that a stalled sum is approximately correct is refused. assertThat(relError < 0.05) on the stagnated run is fed to rejects(); it reports 28%.

And a stochastic context with no random source is refused, which is the check that keeps the mode from silently becoming the default one.

What is left #

Compensated summation, which the order essay already measures and which solves the same problem deterministically: Kahan’s algorithm carries the part the total could not hold and puts it back on the next step, so it does not stagnate either. It costs four operations an addend rather than one, and it needs no randomness and no seed. Which of the two to reach for is a real question and this phase does not answer it.

Stochastic rounding inside a decomposition rather than inside a sum. Every claim here is about accumulation; what it does to an elimination or an orthogonalisation at low precision is a different measurement and would need the whole of matrix.js run through a stochastic context, which is possible with the machinery this phase built and is not done.

The randomness itself. The mode’s guarantee is an expectation over draws, and a hardware generator that is cheap enough to sit on the rounding path is not a good generator. What a poor source costs the unbiasedness is a real question, and nothing here measures it — every figure uses a well-tested stream, which is the favourable case and is not what silicon has room for.