🔢 mathematics

A Second-Moment Theory for Floating-Point Reduction Trees

This paper develops a second-moment theory for floating-point reduction trees by deriving an exact mean-square error recurrence and a tree-dependent kernel to characterize how summation error varies with partial-sum order, enabling the identification of optimal tree topologies and schedules for both centered and non-centered inputs across various precision formats.

Original authors: Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal

Published 2026-07-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to count a massive pile of coins, but you are doing it with a very specific, slightly clumsy rule: every time you add two numbers together, you have to round the result to fit in a tiny box. If the number is too big for the box, you have to chop off the extra bits. This is how computers handle math with "floating-point" numbers. They are incredibly fast, but they aren't perfect; they introduce tiny, invisible errors every time they calculate.

Now, imagine you have a million coins to count. You could add them one by one in a long line (a "sequential" approach), or you could have a team of people pair up, add their coins, then pair up again, and so on (a "tree" approach). In the real world, the order in which you add things usually doesn't matter for the final total. But in the digital world, because of those tiny rounding errors, the order does matter. A long line of additions might end up with a different total than a tree of pairings, even if you are adding the exact same coins. Scientists have long known that the "worst-case" scenario for these errors exists, but they haven't had a good way to predict what happens on average with random numbers. It's like knowing a car could crash in a storm, but not knowing how likely it is to skid on a sunny day.

This paper, titled "A Second-Moment Theory for Floating-Point Reduction Trees," steps into that gap. The authors, a team from Oak Ridge National Laboratory, have developed a new mathematical "map" to predict exactly how much error will accumulate based on the shape of the tree you use to add numbers. They treat the rounding errors not as random chaos, but as a pattern that can be measured and predicted.

Here is the core of their discovery: They found that the total error depends on two main things: the "shape" of your addition tree and the "personality" of the numbers you are adding.

First, they introduced a concept called the "common-ancestor kernel." Imagine your addition tree as a family tree. If you pick two specific coins (leaves) in the pile, the "common ancestors" are the people (nodes) in the tree who had to add those two coins together at some point. The authors proved that the total error is basically a count of how many times every pair of coins shares a common ancestor in the tree. If two coins are added together early in the process and then that result is added to many other things, they share many ancestors, and the error grows. If they are added late, they share fewer.

Second, they realized that the "personality" of the numbers changes the game. If the numbers you are adding are "centered" (meaning they have a mix of positive and negative values that cancel each other out, like a crowd of people pushing left and right), the error depends mostly on the total depth of the tree. But if the numbers are "non-centered" (like a pile of only positive coins, or a crowd all pushing right), the error depends on the size of the sub-groups. A tree that is perfect for a mix of positive and negative numbers might be terrible for a pile of only positive numbers.

The authors tested their theory by running millions of simulations on computers using different types of numbers (from standard high-precision to very low-precision formats used in modern AI). They found that their new model is surprisingly accurate. It correctly predicts which tree shape will give the smallest error for a given type of data. For example, they confirmed that for a standard mix of numbers, a "balanced" tree (where everyone pairs up evenly) is usually the best. But for a pile of only positive numbers, a "two-stage" tree (where you add small groups first, then add the group totals) is often the winner, scaling the error much better than a simple line or a balanced tree.

They also looked at how this applies to massive matrix multiplications (the kind of math that powers neural networks and 3D graphics). They showed that the same "ancestor counting" logic applies there too, allowing them to predict errors in complex calculations with high precision.

However, the paper is careful to note where their map stops working. In very low-precision formats (like the tiny numbers used in some AI chips), if you are adding only positive numbers, the errors can get stuck. This is called "stagnation," where adding a small number to a big number does nothing because the small number is too tiny to register. In these specific cases, the model's predictions break down because the errors stop behaving like random noise and start behaving like a stubborn bias.

In short, this paper doesn't just tell us that rounding errors happen; it gives us a precise formula to calculate how much they will happen based on the structure of our math and the type of data we are using. It suggests that by choosing the right "tree" shape for the job—whether it's a balanced tree for mixed data or a blocked tree for positive data—we can significantly reduce the noise in our calculations without needing to change the hardware. It turns a vague fear of "accumulating errors" into a manageable, predictable engineering problem.

Technical Summary: A Second-Moment Theory for Floating-Point Reduction Trees

Problem Statement

Standard worst-case forward-error bounds for floating-point summation, such as $|\hat{s} - s| \le \gamma_{k-1} \sum |p_i|$ , are independent of the reduction tree topology. While these bounds provide safety guarantees, they fail to distinguish between different tree structures (e.g., sequential, pairwise, blocked) when inputs are random. Consequently, they cannot predict which topology minimizes the typical error (mean-square error, MSE) for a given dataset. The paper addresses the need for a model that captures how the "reduction geometry"—the specific order of pairwise additions—interacts with input statistics to determine error accumulation.

Methodology

The authors develop a second-moment theory that moves beyond worst-case analysis by modeling the accumulation of rounding errors as a stochastic process dependent on the tree structure.

1. Exact Conditional Recurrence

The analysis begins with conditionally unbiased rounding (e.g., stochastic rounding). By conditioning on the information available just before a node is rounded (the $\sigma$ -algebra $\mathcal{F}^-_v$ ), the authors derive an exact recurrence for the accumulated error variance. This recurrence separates the inherited error from the local rounding error, showing that the cross-terms vanish in expectation. The local variance is shown to depend on the pre-rounding operand value $x_v$ .

2. The Constant- $\nu$ Model

To create a tractable model for deterministic round-to-nearest (where errors are not strictly conditionally unbiased), the authors introduce a "constant- $\nu$ " approximation. They replace the operand-dependent local variance with a homogeneous model $\psi_v(x) = \nu u^2 x^2$ , where $\nu$ is a dimensionless coefficient calibrated empirically. This simplifies the recurrence to a form where the total expected squared error is proportional to the sum of squared exact partial sums: $\sum_v q_v^2$ .

3. The Common-Ancestor Kernel ( $K_T$ )

The core theoretical contribution is the representation of the sum of squared partial sums as a quadratic form:
$\sum_{v \in \text{int}(T)} q_v^2 = p^\top K_T p$
Here, $K_T$ is the common-ancestor kernel, a $k \times k$ matrix where the entry $(K_T)_{ij}$ counts the number of internal nodes that are ancestors to both leaves $i$ and $j$ . This matrix encodes the reduction geometry.

4. I.i.d. Compression and Tree Statistics

For independent and identically distributed (i.i.d.) inputs with mean $\mu$ and variance $\tau^2$ , the expectation of the quadratic form collapses into two scalar tree statistics:
$\mathbb{E}[\text{MSE}] \propto \tau^2 \Lambda_1(T) + \mu^2 \Lambda_2(T)$

$\Lambda_1(T)$ : The sum of leaf depths (total external path length). This governs error for centered inputs ( $\mu=0$ ).
$\Lambda_2(T)$ : The sum of squared internal subtree sizes. This governs error for non-centered inputs ( $\mu \neq 0$ ).

5. Extension to GEMM

The theory is extended to General Matrix-Matrix Multiplication (GEMM). The expected squared Frobenius error is shown to be a contraction of the kernel $K_T$ with a matrix $G$ formed from the Hadamard product of the operand Gram matrices ( $G = (A^\top A) \circ (BB^\top)$ ).

Key Contributions

Theoretical Optimization

The paper derives optimal tree topologies for different regimes:

Centered Inputs: Balanced trees minimize $\Lambda_1$ , while sequential trees maximize it. The optimal exponent for RMS error is $1/2$ for pairwise trees.
Non-Centered Inputs: The optimal topology shifts. For fixed-stage hierarchies, the authors derive a "doubling-gap schedule" where stage ratios halve successively ( $r_\ell \propto 2^{-\ell}$ ) to minimize $\Lambda_2$ .
Heterogeneous Variances: For independent centered inputs with unequal variances, the optimal tree structure corresponds to Huffman coding, minimizing the variance-weighted external path length.
Blocking: For two-stage sequential blocking, the optimal block size scales as $b \propto \sqrt{k}$ for centered inputs (yielding an RMS exponent of $3/4$ ), but requires different scaling for non-centered inputs.

Empirical Validation

The authors validate the constant- $\nu$ model across multiple precisions (binary64, binary32, software-emulated binary16, and bfloat16) and input types:

Topology Ordering: The model correctly predicts the ordering of RMS errors among sequential, blocked, and pairwise trees.
Calibration: An independently calibrated $\nu \approx 0.19$ for binary64 round-to-nearest allows the model to predict absolute MSE within 3% for GEMM and correctly captures the scaling laws for various tree families.
Stagnation Limits: The study identifies a failure regime in low-precision (binary16/bfloat16) positive sums where "stagnation" (adding a small number to a large one without change) causes bias to dominate, breaking the constant- $\nu$ approximation.

Results

Scaling Laws: The paper confirms that for centered inputs, pairwise summation scales as $O(\sqrt{\log k})$ , blocked summation with $b \propto \sqrt{k}$ scales as $O(k^{3/4})$ , and sequential summation scales as $O(k)$ .
Non-Centered Regime: For inputs with non-zero means (e.g., softmax denominators, squared norms), the error is dominated by $\Lambda_2$ . The optimal "doubling-gap" schedule yields a different scaling behavior than the geometric schedule optimal for centered inputs.
Correlated Inputs: For AR(1) correlated inputs, the full kernel contraction $\langle K_T, M \rangle$ is required; the i.i.d. approximation fails significantly as correlation increases.
Library Validation: The model successfully predicts the error scaling of a reconstructed NumPy np.sum tree, capturing the specific "bend" in error growth caused by its multi-scale hierarchy (sequential accumulation within small blocks, recursive halving for larger blocks).

Significance and Claims

The paper claims to provide a second-moment theory that bridges the gap between worst-case bounds and practical error behavior. Its significance lies in:

Geometry Awareness: It explicitly quantifies how the reduction tree structure (geometry) interacts with input statistics, a factor ignored by standard bounds.
Predictive Power: It offers a workflow (Table 1) to predict the RMS error of a specific implementation given its tree structure and input distribution, validated across a wide range of precisions and architectures.
Optimization Guidance: It provides concrete criteria for choosing reduction schedules (e.g., block sizes, stage ratios) based on whether the data is centered or non-centered, and whether variances are homogeneous.
Limitations: The authors modestly note that the model relies on the assumption $h(T)u^2 \ll 1$ and may fail in low-precision regimes where stagnation and systematic bias dominate the error, as observed in their binary16/bfloat16 experiments. The constant- $\nu$ is an empirical calibration, not a universal arithmetic constant.

The work establishes that for random inputs, the "typical" error is governed by the tree's shared ancestry structure, allowing for the design of numerically stable reduction trees tailored to specific data characteristics.