Floating-Point Error Has a Phase Transition

01The evidence

• Work on numerical reproducibility at extreme scale documents that results depend on reduction order and concurrency, and that achieving reproducible accuracy is a distinct problem from achieving speed.IEEE, reproducibility at scale
• Runtime selection of reduction algorithms has been proposed to control accuracy, which implies the error is a property of the reduction structure rather than only of the arithmetic.IEEE Cluster, reduction algorithms

02The tension

Standard error analysis treats rounding as independent and predicts error growing as the square root of the number of terms. In practice, simulations either reproduce to many digits or diverge wildly, with little in between, and the divergence depends on the reduction tree.

03The theory

Rounding errors are not independent. At each level of a reduction tree, the error introduced depends on the magnitude difference between operands, and those magnitudes are correlated with the data. Below a critical depth the correlation is weak and errors cancel; above it, a subset of large-magnitude partial sums dominates and the error becomes systematic.

That is a percolation-like transition: once a connected path of large-magnitude partials exists, the error stops averaging out. The transition depth depends on the dynamic range of the data and on precision, and it is predictable from those two quantities.

The theory predicts that reordering a reduction below the threshold is harmless and above it changes the answer, which is exactly the practical experience that makes reproducibility hard. It also predicts that mixed precision shifts the threshold in a calculable way.

The practical consequence is a design rule: reductions should be structured to stay below the threshold, and the threshold should be computed from the data's dynamic range before the job is launched.

04What this is not

05Predictions

• P1Error should show a sharp increase beyond a critical reduction depth rather than smooth growth.
• P2Reordering below the threshold should be harmless, and above it should change results reproducibly.
• P3Lowering precision should move the threshold to shallower depth in a predictable way.

06What would refute it

Error that grows smoothly across depths, with no threshold, would return the problem to the random-walk account.

07What it would change

It would make reproducibility a design constraint computed in advance, and change how numerical libraries choose reduction strategies.