Floating-point addition is not associative. In half precision, grouping 0.5, 512, and 512.5 one way can produce 1025 while another grouping produces 1024. Parallel libraries exploit that freedom to vectorize and split reductions. Their API may promise a sum or matrix multiplication without specifying which partial values meet first.
That missing order becomes a reproducibility problem when software moves between CPUs, BLAS backends, GPU generations, or compilers. Source inspection is insufficient for proprietary hardware and optimized binaries, while runtime traces can be difficult to interpret for parallel fused operations. Microsoft Research’s FPRev treats the implementation as a black box and infers its accumulation tree only from numerical outputs[1].
The tool does not seek a more accurate answer. It reveals the exact evaluation structure needed to reproduce an existing answer or compare two implementations. A developer can turn an undocumented behavior into a testable specification before migrating safety-critical, scientific, database, or machine-learning code.
Cancellation reveals where two leaves meet
Consider a reduction of (n) values. FPRev fills the input with ones, replaces position (i) with a large positive value (M), and position (j) with (-M). The magnitude is chosen so adding ordinary ones to either large value leaves it unchanged. When (M) and (-M) finally meet, they cancel, and only the ones added after that point survive in the output.
The surviving integer reveals how many leaves lie below the lowest common ancestor of positions (i) and (j). Repeating the test for selected pairs provides distances within the hidden reduction tree. A basic algorithm can enumerate all pairs and build the tree from the bottom. FPRev avoids redundant probes by recursively solving only the subtrees that remain ambiguous.
This is a numerical side channel without a security target. Rounding behavior leaks structural information about the sequence of operations. It works through a public API and requires neither binary instrumentation nor performance counters. Because the probe observes behavior, compiler transformations and hardware scheduling are included in the result.
A deterministic implementation is required. If the same input uses a different reduction tree on repeated runs, one inferred tree cannot describe it. FPRev is therefore a diagnostic for fixed orders, not a proof that a runtime with nondeterministic atomics will return stable bits.
Multi-term fusion changes the tree model
Ordinary addition and fused multiply-add can be represented by a binary tree. Matrix accelerators can align and truncate several terms, then accumulate them in one fused operation. A node needs more than two children to represent that behavior. FPRev extends its construction to distinguish whether a recovered subtree is a sibling of the current node or its multiway parent.
The paper reports a lower bound of Ω((n t(n))) and upper bound of (O(n^2 t(n))), where (t(n)) is the cost of the operation under test. The basic method is Θ((n^2 t(n))), and brute-force enumeration grows exponentially. Actual efficiency depends on tree shape because some structures expose large subtrees with few probes.
Low-precision formats constrain the crafted values. FP8 may not have enough dynamic range for one (M) to mask a long list of ones, and a float32 accumulator cannot exactly represent every large integer. The modified algorithm replaces ones with smaller exactly representable terms and compresses completed subtrees. These mitigations preserve the cancellation relation but must be validated for each arithmetic format.
What NumPy and PyTorch disclose through outputs
FPRev tested NumPy 1.26 on Intel Xeon E5-2690 v4, AMD EPYC 7V13, and Intel Xeon Silver 4210. Single-precision sum used the same order across the three CPUs. Below eight values it was sequential. From 8 through 128 values, it used eight lanes with stride-eight partial sums and a pairwise combination; larger inputs increased parallelism.
Other NumPy operations were not equivalent across those CPUs because dot products and matrix operations depended on BLAS implementations. For an 8-by-8 matrix-vector case, two tested 24-vCore CPUs used two-way accumulation for the 32 products of each output, while the 40-vCore Intel system accumulated sequentially. The library name alone therefore does not specify numerical behavior.
PyTorch 2.3 showed the same distinction on NVIDIA V100, A100, and H100 GPUs. Its single-precision sum had an identical revealed order across the tested devices, but BLAS-backed operations differed. For half-precision Tensor Core matrix multiplication, the revealed trees had fan-ins of five on V100, nine on A100, and seventeen on H100. Those structures match 4+1, 8+1, and 16+1-term fused accumulation associated with Volta, Ampere, and Hopper.
“Safe for reproducibility” in the paper means equivalent across the tested hardware and versions. It is not an API guarantee for future releases, different shapes, other data types, or distributed collectives. A production qualification should store the revealed tree with library, driver, compiler, device, operation, shape, and dtype metadata.
Efficiency makes regression testing plausible
For 16 summands, brute force could exceed 24 hours while BasicFPRev and FPRev completed in less than 0.01 second. At 8,192 summands, BasicFPRev took more than 100 seconds and FPRev about one second. The improvement turns a research probe into something that can run across a hardware and software compatibility matrix.
For (n=256) on the tested NumPy system, FPRev was 13.0 times faster than BasicFPRev for dot product, 32.3 times for matrix-vector multiplication, and 82.1 times for matrix multiplication. More expensive operations magnify avoided probes. Tests stopped increasing (n) once execution exceeded one second and each point was averaged over ten runs, so these are tool-runtime comparisons rather than application speedups.
The output can serve as a regression artifact. A vendor update that changes an optimized kernel may preserve conventional tolerances while changing bitwise results. Comparing trees reveals the structural change before a downstream application discovers it. When equivalence is required, a new backend can reproduce the old tree; when only bounded error matters, the tree helps explain why differences appear.
A useful qualification record therefore contains both the inferred structure and the probe conditions. The chosen masking magnitude, input length, tensor dimensions, arithmetic type, warm-up policy, and repetition count determine what was actually observed. Storing only a diagram makes a later mismatch ambiguous: the kernel may have changed, or the test may have selected a different dispatch path. The record should also retain ordinary accuracy metrics, since a structural difference can be harmless within the application’s error budget while an unchanged tree can still conceal a different rounding mode.
Order is only one part of numerical behavior
FPRev does not fully specify an arithmetic implementation. Rounding mode, intermediate precision, denormal handling, contraction, and overflow also affect results. The authors propose additional crafted experiments for Tensor Core accumulator precision and rounding. A matching tree with different node arithmetic can still produce different bits.
Distributed reductions add another layer. The local kernel may be deterministic while AllReduce chooses a topology based on rank count, message size, or runtime state. FPRev can inspect a predetermined collective order, but a dynamic communication library needs repeated tests across configurations. Network nondeterminism may produce a distribution of trees rather than one tree.
Reproducing an old order can also sacrifice performance. A tree optimized for one SIMD width or Tensor Core generation may underuse another device. Engineering must decide whether bitwise identity, numerical tolerance, or peak throughput is the real contract. FPRev supplies evidence for that decision; it does not choose the trade.
This distinction suggests three deployment gates. Bitwise-sensitive checkpoints require the same tree and node arithmetic. Numerically tolerant inference can accept a changed tree after task-level accuracy and worst-case error tests. Exploratory workloads may record the change without blocking release. Separating these gates prevents a diagnostic result from becoming an automatic veto, while still making silent kernel substitution visible to the owners of models, simulations, and databases.
The reusable insight is that black-box numerical testing can recover implementation structure. Carefully selected values transform a rounding difference into a query about ancestry, and an efficient recursive algorithm turns those queries into a tree. For heterogeneous AI and HPC systems, that tree is a missing interface between a mathematical operation and the hardware-specific program that actually evaluates it.
Source and copyright notice
This article is an editorial analysis by Silicon & Systems. It restates the algorithm, case studies, and limitations in our own words. No source sentence, table, or figure is reproduced; the figure was created for this article. FPRev is open sourced, and the paper is available from the USENIX ATC 2025 presentation page. Copyright remains with the authors, 2025.