💻 computer science

Accurate Residues for Floating-Point Debugging

This paper presents a novel approach to floating-point debugging that significantly improves the accuracy of residue computation by refining error-free transformations and introducing a "residue override" technique to handle complex numerical issues, thereby eliminating or substantially reducing false reports across diverse scientific and numerical benchmarks while maintaining high efficiency.

Original authors: Yumeng He, Pavel Panchekha

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yumeng He, Pavel Panchekha

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 a chef trying to bake a perfect cake. You have a recipe that uses exact measurements (like "1/3 cup of sugar"), but your kitchen tools are a bit clunky. You only have measuring cups that can hold whole numbers or simple fractions. When you try to measure "1/3," you have to round it to "0.33." That tiny difference seems harmless, but if you bake a thousand cakes, that tiny error adds up, and the final cake might be a disaster.

In the world of computers, this is called floating-point arithmetic. Computers use "clunky" tools to do math with real numbers, and tiny rounding errors happen constantly.

The Problem: The "Blind" Debugger

For a long time, programmers have used debuggers (tools that watch code while it runs) to find these errors. Think of a debugger as a food critic tasting the cake at every step to see if the sugar measurement was off.

However, existing critics had a dilemma:

The Slow, Perfect Critic: This critic uses a super-precise scale (high-precision math) to taste every ingredient. They never miss an error, but they are so slow that the cake is cold by the time they finish tasting.
The Fast, Clumsy Critic: This critic uses a quick, rough estimate. They are very fast, but they often shout "Error!" when there isn't one (false alarms) or miss real errors entirely (false negatives).

The paper introduces a new tool called RePo (Residue Override). It aims to be the Fast Critic who learns to be Perfect.

The Solution: Two Superpowers

RePo improves the "Fast Critic" in two clever ways.

1. The "Double-Check" (Better Math)

First, RePo gets much better at doing the math itself.

The Old Way: Imagine the critic just guessing the error. "Oh, that looks like a rounding error." Sometimes they guess wrong.
The RePo Way: RePo uses a special trick called Error-Free Transformations. Think of this as a magic trick where the critic calculates the exact difference between the "ideal" measurement and the "clunky" measurement using the same tools the computer uses, but in a very clever order.
The Result: They fixed tiny bugs in the math formulas (like a typo in a recipe) and added rules for tricky situations (like when a computer rounds a number to an integer). This alone made the tool much more accurate, stopping most of the false alarms.

2. The "Residue Override" (The Time-Travel Trick)

Even with better math, RePo hit a wall called Absorption.

The Analogy of the Vanishing Act:
Imagine you are trying to hear a whisper (a tiny error) in a room where a jet engine is roaring (a huge error).

The Problem: The jet engine is so loud that it completely "absorbs" the whisper. You can't hear the whisper while the engine is running.
The Twist: Later in the recipe, the jet engine turns off, and suddenly the whisper becomes the only sound. But because you missed the whisper earlier, you can't trace where it came from. You have a "ghost" error that you can't explain.

In computer terms, sometimes a huge rounding error swallows up a tiny one. Later, the huge error cancels itself out, and the tiny error (which was hidden) suddenly becomes important. A single run of the program can't see both the "loud" error and the "hidden" error at the same time.

The Fix: The "Silence and Swap" Technique
RePo solves this by running the program three times (or a few times) like a time-traveling detective:

Run 1 (The Normal Run): The program runs normally. RePo sees the "loud" errors but misses the "hidden" whispers because they got absorbed.
Run 2 (The Silence Run): RePo goes back in time and silences the loud errors (pretends they are zero). Now, the "whispers" are no longer drowned out! RePo can finally hear and record them.
Run 3 (The Override Run): RePo runs the program normally again, but this time, it swaps the bad data from Run 1 with the good data from Run 2. It patches the "loud" errors with the correct "whisper" data it found in the silence.

By stitching these different runs together, RePo creates a "patchwork" view of the program where every single error is visible, even the ones that usually hide.

The Results: A Happy Ending

The authors tested this on 169 difficult math problems (like those found in engineering textbooks).

Before: Old tools missed errors or cried wolf constantly.
After: RePo fixed almost all the errors.
Speed: It only needed to run the program a few extra times (on average, about 3.6 times total) to get the perfect result. This is a tiny price to pay compared to the "Slow Critic" who takes 100 times longer.

Summary

RePo is like a detective who realizes that sometimes you can't see everything in one glance. So, they run the scene three times: once normally, once with the loud distractions turned off, and once where they combine the clues from both. The result is a debugging tool that is fast, accurate, and rarely makes mistakes, helping programmers bake perfect digital cakes without the fear of hidden errors ruining the recipe.

1. Problem Statement

Floating-point arithmetic is prone to subtle numerical errors (e.g., cancellation, absorption) that can lead to catastrophic failures in scientific computing. Floating-point debuggers are tools designed to detect these issues at runtime by estimating residues—the difference between the actual floating-point value computed by a program and the ideal value computed with infinite precision (real numbers).

Existing debugging approaches face a fundamental trade-off between accuracy and efficiency:

High-Precision Methods (e.g., MPFR, Herbgrind): Use arbitrary-precision arithmetic to compute ideal values. They are highly accurate but incur massive runtime overhead (often $100\times$ or more), making them impractical for large-scale applications.
Error-Free Transformation (EFT) Methods (e.g., EFTSanitizer): Use clever sequences of machine-precision operations to estimate rounding errors. They are fast (low overhead) but suffer from high rates of false positives (unnecessary warnings) and false negatives (missed errors) due to inaccuracies in their residue formulas and a phenomenon the authors term absorption.

The core problem addressed by this paper is how to achieve the accuracy of high-precision methods while maintaining the efficiency of machine-precision methods, specifically by eliminating false reports caused by formulaic inaccuracies and the absorption phenomenon.

2. Methodology: RePo

The authors propose RePo, a floating-point debugger that improves upon EFT-based approaches through two main innovations:

A. Refined Residue Computation (Accuracy without Overhead)

RePo splits residue computation into two steps: rounding error estimation and residue function evaluation. The authors identified and corrected specific inaccuracies in the state-of-the-art EFTSanitizer:

Accurate Rounding Error Estimation:
- Casts: Instruments type casts (e.g., double to float) by casting back to the original type and subtracting, leveraging Sterbenz's lemma for exactness.
- Rounding Tricks: Detects specific patterns used in standard math libraries (e.g., (x + c) - c for rounding to integers) and correctly sets their rounding error to zero, preventing false alarms in trigonometric functions.
Accurate Residue Functions:
- Bug Fixes: Corrected typos in the subtraction and division residue formulas used by EFTSanitizer.
- Higher-Order Terms: Restored the $e_x e_y$ term in multiplication residue functions. Previous tools dropped this term, causing total loss of error tracking when both inputs suffered from cancellation (resulting in zero values).
- Absolute Value & Square Root: Refined formulas to handle cases where small residues are rounded away by larger operands.

B. Residue Override (Solving Absorption)

The authors identified a fundamental limitation of single-execution EFT debuggers called Absorption.

The Phenomenon: In complex computations, a residue $e_i$ might be dominated by a large rounding error $\mu_{large}$ , causing a tiny but critical rounding error $\mu_{small}$ to be "absorbed" (rounded away). Later, if $e_i$ is used in a cancellation (e.g., $e_i - e_j$ ), the large error $\mu_{large}$ might cancel out, leaving the result dependent entirely on the previously absorbed $\mu_{small}$ . Since $\mu_{small}$ was lost in the first step, the final result is inaccurate.
The Solution: RePo introduces Residue Override, a technique that uses multiple executions to resolve absorption:
1. Detection: The debugger monitors residue computations. If a residue is near zero (indicating cancellation) but the condition number suggests a hidden large error, it flags an absorption.
2. Silencing & Probing: In a subsequent execution, RePo silences (sets to zero) the dominant rounding errors responsible for the absorption. This allows the smaller, previously absorbed errors to be computed accurately.
3. Override: In a final execution, the dominant errors are re-enabled, but the inaccurate residues are overridden with the accurate values measured during the "silenced" run.
Complex Scenarios: The algorithm handles multi-term absorption (silencing multiple pairs of operations iteratively) and multiple independent absorptions (parallelizing silencing for different parts of the program) by tracking the largest and second-largest error contributors for every residue.

3. Key Contributions

Refined Machine-Precision Residues: Demonstrated that correcting rounding error estimation and residue function formulas (specifically for casts, rounding tricks, and higher-order error terms) drastically reduces false reports in standard scientific benchmarks.
Identification of Absorption: Formally defined "absorption" as a fundamental limitation of single-execution machine-precision debugging where large errors mask small ones, preventing accurate measurement of cancellation effects.
Residue Override Technique: Proposed a novel multi-execution framework that detects absorption, silences dominant errors to probe hidden values, and overrides results to achieve high accuracy without high-precision arithmetic.
Comprehensive Evaluation: Validated the approach on 44 large scientific workloads and 169 standard numerical benchmarks (including complex elementary functions like sin and exp).

4. Results

The evaluation compared RePo against EFTSanitizer (bug-fixed), QD (quad-double), and MPFR (ground truth).

Scientific Benchmarks (44 programs):
- EFTSanitizer produced false reports on 14 benchmarks.
- RePo (without residue override) eliminated false reports on 10 of these and substantially reduced them on the remaining 3.
- RePo produced 38 $\times$ fewer false reports than EFTSanitizer overall.
Numerical Analysis Benchmarks (169 programs):
- Focused on 34 benchmarks where the initial run produced false reports.
- Residue Override was triggered on 29 of these.
- It reduced false reports on 25 benchmarks (86.2%), with 8 achieving perfect results (zero false reports).
- On average, only 3.6 re-executions were required per benchmark (7.1 for the difficult subset with initial false reports).
Performance Overhead:
- RePo is slower than EFTSanitizer due to tracking overhead but significantly faster than QD and MPFR.
- It occupies a "sweet spot" in the speed-accuracy spectrum: substantially more accurate than EFTSanitizer and QD, but with much lower overhead than MPFR.

5. Significance

This paper demonstrates that high-precision shadow execution is not strictly necessary for accurate floating-point debugging. By combining mathematically rigorous residue formulas with a targeted, multi-execution strategy to handle absorption, RePo achieves near-perfect accuracy on complex numerical workloads with manageable runtime overhead.

The work shifts the paradigm from "compute everything with high precision" to "compute efficiently and intelligently override when precision limits are hit." This makes robust numerical debugging feasible for large-scale scientific software where high-precision tools are too slow to be practical.