The most suspicious bug report in numerical software is the one that says:

same input, same code, different total

The code is usually innocent in the narrow sense. It read the same bytes. It used the same formula. It added the same values.

What changed was the schedule.

A vector got split across a different number of worker threads. A database aggregate chose a different hash-table iteration order. A GPU reduction used a different tree. A compiler vectorized a loop. A linear algebra library changed its tiling. The mathematical sum did not change, but the parenthesized expression did.

For real numbers, that distinction is cosmetic:

((a + b) + c) == (a + (b + c))

For floating-point numbers, it is a contract negotiation.

(2^53 + 1) - 2^53 == 0
2^53 + (1 - 2^53) == 1

In JavaScript’s binary64 arithmetic, 2^53 is exactly representable, 1 is exactly representable, and -2^53 is exactly representable. The problem is not that the inputs are strange decimals. The problem is that the spacing between representable numbers around 2^53 is two. The lonely 1 has nowhere to land when it is added to the huge partial sum.

That is the whole essay in miniature:

summation = values + accumulator + schedule

The Standard Gives You Rounds, Not Associativity

IEEE 754 gives modern software an extraordinary gift: arithmetic operations have specified formats, rounding rules, exceptional values, and a shared language for binary and decimal floating point.1 Goldberg’s classic tutorial remains the best doorway into the practical consequences: floating point is finite, most real results must be rounded, and those rounding decisions matter to systems builders.2

But the standard does not turn rounded addition into real addition.

For ordinary finite values, a + b and b + a usually round to the same thing. So addition is effectively commutative. Associativity is the one that breaks:

(a + b) + c
a + (b + c)

Those are two different floating-point programs. Each + rounds before the next one starts. If the first program rounds away a small term, the second program does not get to ask for it back.

That is why a reduction tree is not just a performance detail. It is a numerical method.

A Small Failure Notebook

The lab below makes the schedule visible. It generates integer-valued inputs that are exactly representable as binary64 numbers, then compares several ways to add them:

  • left fold, the usual sum += x;
  • pairwise, a balanced binary tree over the selected schedule;
  • Kahan, a compensated sum with one correction variable;
  • Neumaier, a compensated variant that handles large incoming terms more carefully;
  • sort by magnitude, a small-first ordering;
  • parallel shards, contiguous chunks summed separately and then reduced.

The reference is an exact BigInt ledger of the generated integer inputs. That is not a general exact-sum implementation for arbitrary floats. It is a controlled test bench where the mathematical answer is known.

Deterministic browser experiment. Inputs are integers chosen to be exactly representable as JavaScript binary64 numbers. The exact reference is a BigInt ledger of those generated inputs, so the experiment isolates summation error from decimal parsing or measurement noise.

The first scenario is the cleanest:

[2^53, 1, 1, ..., 1, -2^53]

The exact sum is the number of ones. The left fold returns zero at the default setting because every one is added while the accumulator is sitting at 2^53. The balanced tree, Kahan, Neumaier, and the small-first schedule all recover the answer.

That is the friendly failure.

Now switch to hostile triples. The input repeats:

[2^53, 1, -2^53]

At 32 groups, the exact sum is 32. The lab audit sees:

left fold      0
pairwise      32
Kahan         42
Neumaier      32
small-first   32
4 shards      0

That line is the antidote to a lot of cargo-cult numerics. Kahan summation is a real and useful algorithm, going back to Kahan’s 1965 note on reducing truncation errors.3 But one compensation variable is still a finite state machine being driven by a particular schedule. It is not exact arithmetic.

The mixed ledger scenario is less theatrical and more like production. It mixes positive and negative powers of two with small integer debits and credits. The exact answer is modest, but 40 deterministic shuffles can produce several answers. Nothing random is happening inside addition. The order changed, so the rounding history changed.

Why Pairwise Often Looks Boring

Pairwise summation is the plainest useful fix: add nearby subranges first, then add their results. It shortens the long dependency chain of a left fold and tends to reduce error growth. It also maps naturally onto parallel machines.

But pairwise summation does not make floating-point addition associative. It chooses a tree.

That tree may be better than a left fold. It may also be different from the tree chosen by a thread pool, a GPU warp, a database engine, or a BLAS library. If a system promises only “some parallel reduction,” then the numerical result is under-specified.

Higham’s 1993 paper is still the sober reference here. It analyzes several summation methods and compares them with both rounding-error analysis and experiments. The useful conclusion is not “one method wins.” The useful conclusion is that summation has methods.4

That sounds too simple until a model metric changes in the third decimal place because an upstream job changed its partition count.

Compensation Is An Error Ledger

Kahan’s idea is to keep a tiny side account. If adding x to sum loses a low-order piece, store an estimate of that lost piece in c and subtract it from the next input:

y = x - c
t = sum + y
c = (t - sum) - y
sum = t

That is not the only compensated scheme. Neumaier’s variant updates the compensation depending on which of sum and x has larger magnitude. Ogita, Rump, and Oishi later developed accurate summation and dot-product algorithms using error-free transformations, with results comparable to higher working precision while staying in the same nominal precision.5

The family resemblance is important:

do not pretend the low-order error vanished
carry some representation of it forward

Compensation buys accuracy. It may also complicate vectorization, parallelism, and reproducibility because the compensation state itself has an order. If you split a compensated sum into shards, each shard has its own correction history, and then those histories must be merged somehow.

There is no free lunch here. There are better receipts.

Reproducibility Is A Stronger Promise Than Accuracy

Accuracy asks:

is this answer close to the real sum?

Reproducibility asks:

will I get the same bits if the legal schedule changes?

Those are different promises.

You can have an accurate method that is not reproducible across thread counts. You can have a reproducible method that is not the most accurate available. Production systems often need both, but they should not be confused.

Demmel and Nguyen’s work on reproducible floating-point summation attacks this directly. Their ARITH 2013 presentation starts from the fact that floating-point operations are commutative but not associative, then defines reproducibility as bitwise-identical results across runs on the same input even when resources or reduction order differ.6 The later ReproBLAS project describes BLAS routines that guarantee reproducibility independent of processor count, data partitioning, and reduction order under explicit IEEE-style assumptions.7

The conceptual move is to stop treating the accumulator as a single floating point number. Use a binned accumulator, a superaccumulator, an error-free transformation pipeline, or another representation that makes the merge itself well-defined. Then the final rounded answer is extracted from that richer state.

This is why reproducible summation is a systems problem, not just a numerical analysis footnote. The answer depends on:

  • the format;
  • the rounding mode;
  • the accumulator state;
  • the partitioning;
  • the merge tree;
  • the final extraction rule.

If those are not specified, “sum” is not fully specified.

Places This Actually Bites

The obvious victims are scientific simulations and linear algebra. They are not the only ones.

A finance backtest summing P&L across fills can change when fills are grouped by venue, symbol, or worker shard. A database GROUP BY over floating-point measurements can change when the query plan changes. A training loop can report slightly different loss curves when gradient buckets are reduced in a different order. A game physics engine can drift when entity iteration order changes. A metrics pipeline can emit a different total after an autoscaler changes the number of reducers.

Most of those differences are small. Small is not the same as harmless.

Small nondeterminism is enough to make tests flaky, bisects confusing, cached artifacts invalid, and model comparisons suspicious. It is also enough to hide a large conditioning problem until an unlucky schedule exposes it.

When I see a production sum over floats, I want to know which promise it makes:

  • fast approximate, where small schedule differences are accepted;
  • stable approximate, where pairwise or compensated methods are used;
  • deterministic schedule, where the same tree is forced every time;
  • order-independent reproducible, where a richer accumulator is used;
  • exact then rounded, where the implementation pays for a full exact accumulator or equivalent method.

Those are different products. A codebase should not sell one while implementing another.

A Test I Would Add

Every shared summation primitive should have adversarial schedule tests.

Not only random data. Random data is too polite.

I would include:

[2^53, many 1s, -2^53]
repeat([2^53, 1, -2^53])
mixed signed powers of two plus small residues
sorted ascending by magnitude
sorted descending by magnitude
several deterministic shuffles
several shard counts

The test does not have to demand the same answer from every implementation. It has to make the chosen promise explicit. If the primitive is a fast approximate sum, record the observed envelope. If it is advertised as reproducible, change the schedule until you believe it.

The worst possible state is not “we chose speed.” Speed is a legitimate choice.

The worst state is:

we thought addition was just addition

It is not. A sum has a schedule.

Paper Trail

  1. IEEE, “754-2019 - IEEE Standard for Floating-Point Arithmetic”, IEEE Std 754-2019, July 2019. DOI metadata: BibBase. ↩

  2. David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic”, ACM Computing Surveys, 23(1), 1991. DOI: 10.1145/103162.103163. ↩

  3. William Kahan, “Pracniques: Further Remarks on Reducing Truncation Errors”, Communications of the ACM, 8(1), 1965. ↩

  4. Nicholas J. Higham, “The Accuracy of Floating Point Summation”, SIAM Journal on Scientific Computing, 14(4), 1993, pp. 783-799. Author PDF: high93s.pdf. ↩

  5. Takeshi Ogita, Siegfried M. Rump, and Shin’ichi Oishi, “Accurate Sum and Dot Product”, SIAM Journal on Scientific Computing, 26(6), 2005, pp. 1955-1988. Author PDF: OgRuOi05.pdf. ↩

  6. James Demmel and Hong Diep Nguyen, “Fast Reproducible Floating-Point Summation”, ARITH 2013, pp. 163-172. Slides: Fast_Sum.pdf. ↩

  7. ReproBLAS project page, “Reproducible Basic Linear Algebra Sub-programs”. See also Peter Ahrens, James Demmel, and Hong Diep Nguyen, “Algorithms for Efficient Reproducible Floating Point Summation”, ACM Transactions on Mathematical Software, 46(3), 2020. ↩