In pure mathematics, addition is associative: $(a + b) + c$ will always equal $a + (b + c)$. However, when these same equations are executed on modern computer hardware using floating-point arithmetic, this fundamental guarantee vanishes.
Because computers represent real numbers using a finite number of bits, they must round the results of arithmetic operations. This rounding introduces tiny errors. Crucially, because the magnitude of the rounding error depends on the magnitudes of the numbers being added, changing the sequence of operations alters how these errors accumulate.
As parallel and distributed computing architectures become the default for large-scale workloads—such as deep learning, database queries, and physical simulations—this lack of associativity introduces a profound challenge: numerical non-determinism.
The Core Intuition: Why Order Matters
To understand why floating-point arithmetic is non-associative, imagine a hypothetical decimal system that can only retain three significant digits.
Suppose we want to compute the sum of three numbers: $100$, $0.4$, and $0.4$.
-
Scenario A: $(100 + 0.4) + 0.4$ First, we compute $100 + 0.4 = 100.4$. Because our system only keeps three significant digits, this value is rounded back to $100$. Next, we add the second $0.4$: $100 + 0.4 = 100.4$, which again rounds to $100$.
-
Scenario B: $100 + (0.4 + 0.4)$ First, we aggregate the small numbers: $0.4 + 0.4 = 0.8$. Next, we add this to the large number: $100 + 0.8 = 100.8$. When rounded to three significant digits, this yields $101$.
Despite starting with identical inputs, the two evaluation paths yield different results.
In modern high-performance computing environments, this phenomenon is amplified across millions of concurrent operations. When a GPU or a programmable network switch executes a parallel reduction (such as summing a gradient vector), it schedules operations dynamically based on thread availability or packet arrival times to maximize throughput, as noted by De Sensi et al.. Because this scheduling is inherently asynchronous and non-deterministic, the reduction tree changes from run to run. As a result, a fixed model processing a fixed input can produce divergent bit-level outputs across different runs, hardware backends, or batch sizes (Schlögl et al.).
The Soundness Gap: Exploiting Numerical Jitter
For many years, these microscopic variations were dismissed as harmless background noise. However, recent research demonstrates that floating-point non-associativity can fundamentally undermine the safety guarantees and reliability of software systems.
Consider formal neural network verification. Verifiers are designed to mathematically prove that a neural network is robust against perturbations. However, standard verifiers typically operate under the idealized assumption that arithmetic operations are associative and follow a fixed precision.
Szász et al. exposed a critical "soundness gap" resulting from this assumption. By exploiting floating-point non-associativity and hardware-specific precision differences, the authors constructed "deployment-sensitive backdoors." These are network configurations where an input satisfies safety proofs in the verifier's idealized mathematical model but triggers malicious behavior when executed on actual hardware due to altered operation ordering.
Similarly, Möller et al. introduced Chimera examples—adversarial inputs engineered to amplify the microscopic differences between mathematically equivalent linear algebra backends (such as Intel MKL and Nvidia CUDA). A single model can be forced to produce conflicting high-level predictions for the exact same input simply by switching the underlying hardware library.
Idealized Math (Associative) --> [Input] --> Matrix Multiply --> [Prediction: Cat]
Actual Hardware (Dynamic GPU) --> [Input] --> Reordered Sums --> [Prediction: Dog]
This hardware-level jitter is significant enough to shift samples across a model's decision boundary without any external data perturbation, creating a silent source of vulnerability (Shanmugavelu et al.; Zombori et al.).
Systemic Instability across Domains
The downstream effects of non-associativity extend far beyond adversarial exploits, impacting everyday applications in machine learning and data management.
Large Language Model Inference
Even when setting the sampling temperature to zero (greedy decoding), Large Language Models (LLMs) can produce wildly divergent responses across different hardware configurations or batch sizes. As Yuan et al. demonstrated, parallel reduction operations in attention layers change their execution order based on available hardware resources. The resulting rounding errors accumulate across layers, eventually shifting the logits enough to flip token selections during generation. For complex reasoning models, a single altered token early in the generation chain can derail the entire logical path.
Relational Databases
In relational database management systems (RDBMSs), relational algebra dictates that aggregations (like SUM or GROUP BY) operate over unordered collections. This theoretical framework assumes that the underlying math is associative. However, because floating-point addition is not associative, executing the same query over parallel threads or differently ordered rows can yield inconsistent bit-level results (Müller et al.). To maintain formal correctness in verified compilers, developers are forced to explicitly isolate these numerical axioms to prevent hardware-level floating-point behavior from invalidating broader logical proofs (Benzaken et al.).
Physical Simulations
In scientific computing, the lack of associativity causes numerical drift that breaks fundamental physical laws within simulations. For instance, standard fluid dynamics simulations cannot be run backward to recover their exact initial state because the accumulation of rounding errors destroys time-reversibility (Kincl et al.).
Strategies for Restoring Determinism
To combat the challenges of non-associativity, researchers have developed several techniques designed to restore bit-level reproducibility and minimize error propagation.
1. Fixed Reduction Trees
The most direct way to ensure reproducibility in parallel environments is to enforce a strict, unchangeable sequence of operations. By implementing a fixed reduction tree structure for global sums, software packages like Pigeons.jl ensure that numerical consistency is maintained regardless of changes to the underlying parallel execution schedule or thread count (Biron-Lattes et al.).
2. Hybrid Precision Accumulation
Rather than forcing a rigid execution order, another approach absorbs rounding errors by performing critical aggregations in higher precision formats. For example, the LayerCast approach proposed by Yuan et al. stores model weights in lower precision formats (like BF16) to save memory but performs accumulation steps in FP32. This ensures that varying operation orders across different hardware configurations still yield identical token selections.
3. Error-Free Transformations
In database systems where enforcing a rigid row order destroys parallel performance, researchers utilize error-free transformations (EFTs). Müller et al. introduced a SIMD-optimized "summation buffer" data structure that tracks both the primary sum and the associated rounding errors. This approach achieves bit-reproducible aggregation independent of row order or parallel execution strategy, while simultaneously improving overall numerical accuracy.
4. Automated Error Analysis
Finally, instead of manually debugging numerical drift, new programming languages are emerging to analyze stability automatically. The language Bean, developed by Kellison et al., integrates a linear type system with a graded coeffect system to automatically derive sound backward error bounds for numerical programs, allowing developers to mathematically verify the stability of their algorithms before deployment.
Key Foundational Work
PCCM2: A GCM adapted for scalable parallel computers (1994) — contributed 1 concept elements to this direction.
A floating-point library for integer processors (2004) — contributed 1 concept elements to this direction.