Automatic Verification of Floating-Point Accumulation Networks

David K. Zhang, Alex Aiken · 2025

Read Automatic Verification of Floating-Point Accumulation Networks by David K. Zhang, Alex Aiken (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18791.txt.

Introduction

David Zhang and Alex Aiken present in 2025 an automatic checker for the small summation networks at the heart of accurate floating point arithmetic. These networks power tricks like compensated summation, which claw back precision lost to rounding. They are notoriously hard to analyze, and at least one published error bound for a widely used network later proved wrong.

Their method builds machine checked proofs of correctness traits, with error bounds tight to the last bit. A new abstraction tracks each number's sign, exponent, and the runs of zeros and ones in its digits. With that lens, a program can verify what humans miss. Verified bounds matter wherever money, physics, or flight depends on sums of many numbers.

Catalog record

CREATORDavid K. Zhang, Alex Aiken
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-18791

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Automatic Verification of Floating-Point Accumulation Networks David K. Zhang, Alex Aiken Abstract Floating-point accumulation networks (FPANs) are key building blocks used in many floating-point algorithms, including compensated summation and double-double arithmetic. FPANs are notoriously difficult to analyze, and algorithms using FPANs are often published without rigorous correctness proofs. In fact, on at least one occasion, a published error bound for a widely used FPAN was later found to be incorrect. In this paper, we present an automatic procedure that produces computer-verified proofs of several FPAN correctness properties, including error bounds that are tight to the nearest bit. Our approach is underpinned by a novel floating-point abstraction that models the sign, exponent, and number of leading and trailing zeros and ones in the mantissa of each number flowing through an FPAN. We also present a new FPAN for double-double addition that is faster and more accurate than the previous best known algorithm. 1 Introduction Many scientific and mathematical problems demand calculations that exceed the native precision limits of floating-point hardware (typically IEEE 64-bit or Intel x87 80-bit). To address this need, numerical programmers turn to compensated algorithms , such as Kahan–Babuška–Neumaier summation [ 37 , 5 , 49 ] , and floating-point expansions [ 53 ] , such as double-double and quad-double arithmetic [ 21 , 33 ] . These techniques enable a processor to execute floating-point operations with double, quadruple, or even higher multiples of its native precision. They are widely adopted in dense [ 42 ] and sparse [ 26 ] numerical linear algebra, high-precision quadrature [ 8 ] , robust computational geometry [ 58 ] , fluid dynamics [ 6 , 32 ] , quantum chemistry [ 29 , 30 ] , correctly rounded transcendental functions [ 19 , 59 ] , and the discovery of new mathematical identities [ 9 ] . All of these techniques are based on common building blocks known as error-free transformations [ 52 ] , which are floating-point algorithms that exactly compute their own rounding errors. For example, the Møller–Knuth \operatorname{\mathsf{TwoSum}} algorithm [ 48 , 39 ] takes a pair of floating-point numbers (x,y) and computes both their rounded sum s\coloneqq x\oplus y and the exact rounding error e\coloneqq(x+y)-(x\oplus y) incurred in that sum. Here, \oplus denotes rounded floating-point addition, while + denotes true mathematical addition. Although the \operatorname{\mathsf{TwoSum}} algorithm has been extensively studied, proven correct by both pen-and-paper [ 39 , 11 ] and formal methods [ 12 , 47 ] , issues arise when multiple \operatorname{\mathsf{TwoSum}} operations are combined to accumulate three or more floating-point values. Multiple rounding error terms can interact in subtle and unexpected ways, significantly affecting the precision of the overall result when terms that are incorrectly assumed to be negligible are discarded. x_{0} z_{0} y_{0} z_{1} x_{1} y_{1} x_{0} z_{0} y_{0} z_{1} x_{1} y_{1} Figure 1: Network diagram of the ddadd algorithm due to Li et al. (left) and madd , our new double-double addition algorithm (right). This graphical FPAN notation will be explained in detail in Section 3 . In 2017, Joldes, Muller, and Popescu [ 35 ] discovered an error of this type in the ddadd algorithm designed by Li et al. for the XBLAS extended-precision linear algebra library [ 42 ] . Li et al. originally claimed that ddadd computes sums with relative error bounded by 2\cdot 2^{-106}=2\bm{\mathsf{u}}^{2} when executed in IEEE binary64 (double precision) arithmetic, where \bm{\mathsf{u}}=2^{-53} denotes the unit roundoff. Joldes, Muller, and Popescu refuted this claim by identifying a class of inputs in which two discarded error terms interfere constructively, producing a relative error of 2.25\cdot 2^{-106}=2.25\bm{\mathsf{u}}^{2} in the final sum. While this weakened bound does not invalidate the usefulness of XBLAS, it demonstrates that even expert numerical analysts can make subtle mistakes in the analysis of rounding errors. The ddadd algorithm is a prototypical example of a floating-point accumulation network (FPAN) — a term we introduce to describe a branch-free linear sequence of floating-point sum and \operatorname{\mathsf{TwoSum}} operations. Although this class of algorithms, to our knowledge, has never been explicitly named in the floating-point literature, FPANs pervade floating-point algorithms and occur in every single paper referenced in this introduction, along with dozens of software packages [ 27 , 54 , 19 , 59 , 33 , 43 , 25 , 36 , 57 , 62 , 7 ] . In addition to their obvious uses for high-precision addition and subtraction, FPANs also occur as subroutines in multiplication, divison, and square root algorithms [ 38 , 33 ] , which in turn are used to implement transcendental functions, including the exponential, logarithm, and trigonometric functions, in many standard libraries [ 19 , 59 , 54 ] . In this paper, we present an automatic procedure for proving several FPAN correctness properties, including error bounds and nonoverlapping invariants. Our key technical insight is a one-sided reduction from a correctness property P of an FPAN F to a satisfiability problem S_{P,F} in quantifier-free Presburger arithmetic ( QF_LIA ). Here, one-sidedness means that if S_{P,F} is unsatisfiable, then P(F) provably holds, but if S_{P,F} is satisfiable, then P(F) may or may not hold. In all cases we have tested, we find that the satisfiability of S_{P,F} is far easier for SMT solvers to determine than direct verification of P(F) in a floating-point theory ( QF_FP ). Our reduced problems S_{P,F} can be solved in less than one second, while direct P(F) verifiers fail to terminate after multiple days of runtime. Using our procedure, we discover and prove the correctness of a new algorithm for double-double addition — the same problem that ddadd solves — with strictly smaller relative error and lower circuit depth. Thus, our algorithm, named madd (for “More Accurate Double-Double addition,” shown in Figure 1 ) is both faster and more accurate than the previous best known algorithm for this task. We expect our automatic decision procedure to enable additional novel algorithms to be found by computer search in future work. Our reduction strategy uses a novel abstraction of floating-point arithmetic that does not consider the full bitwise representation of a floating-point number x , but tracks only its sign s_{x} , exponent e_{x} , and the number of leading and trailing zeros and ones in its mantissa (\mathsf{nlz}_{x},\mathsf{nlo}_{x},\mathsf{ntz}_{x},\mathsf{nto}_{x}) . Using this reduced representation, we construct abstract overapproximations of the floating-point sum and \operatorname{\mathsf{TwoSum}} operations, expressed as linear inequalities in the variables (s_{x},e_{x},\mathsf{nlz}_{x},\mathsf{nlo}_{x},\mathsf{ntz}_{x},\mathsf{nto}_{x}) . Although we lose completeness by passing to an overapproximation, we show that our abstraction is nonetheless precise enough to prove best-possible error bounds, tight to the nearest bit, for several FPANs of practical interest, including ddadd and madd . Moreover, we use floating-point SMT solvers to directly verify the soundness of our abstraction. In summary, this paper makes the following contributions: 1. We define floating-point accumulation networks ( FPANs ) and show that FPANs occur in many widely used floating-point algorithms. 2. We give a procedure for reducing correctness properties P of an FPAN F to satisfiability problems S_{P,F} in quantifier-free Presburger arithmetic. Our strategy uses a novel formally verified abstraction of floating-point arithmetic that may be of independent interest. 3. We empirically demonstrate that S_{P,F} is far easier for modern SMT solvers to reason about than

Read the complete text