🤖 machine learning

Quotient Tree Arithmetic: Deferred-Division Computation with Bounded Symbolic Depth and Cross-Subtree Cancellation

This paper introduces Quotient Tree Arithmetic (QTA), a computational framework that represents values as deferred quotient pairs to achieve exact rational arithmetic, bounded symbolic depth, and cross-subtree cancellation, thereby significantly reducing numerical errors and memory overhead in machine learning training while connecting algebraic localization theory with hardware-native IEEE arithmetic.

Original authors: Gregory Magarshak

Published 2026-07-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Gregory Magarshak

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 measure the world with a ruler that has a tiny, invisible flaw. For decades, scientists and computer programmers have used a standard measuring tool called "floating-point arithmetic" to do math on computers. It's incredibly fast and works for almost everything, from calculating rocket trajectories to training the AI that recommends your next favorite song. But it has a famous, annoying glitch: it can't handle certain simple numbers perfectly. If you ask a computer to add 0.1 and 0.2, it doesn't give you exactly 0.3; it gives you 0.30000000000000004. It's like trying to cut a pizza into perfect slices with a dull knife; eventually, the crumbs add up, and your slices aren't equal. This tiny error can cause big problems, like an AI getting confused because its internal calculations drift apart, or a financial system losing track of a penny.

To fix this, people usually use special "decimal" tools that are slower, or they use "symbolic" math that is super accurate but incredibly heavy and slow, like trying to carry a library in your backpack just to buy a coffee. The big question has always been: Can we get the speed of the fast, flawed ruler and the perfect accuracy of the heavy, slow one at the same time? This is the puzzle a new paper by Gregory Magarshak tries to solve. He proposes a clever trick that turns the computer's standard math into a system of perfect fractions, keeping the speed of the hardware while eliminating the tiny errors that usually creep in.

The paper introduces a system called Rational Pair Arithmetic (RPA). Instead of storing a number like 0.3 as a single, slightly messy decimal, the computer stores it as a pair of whole numbers: a numerator (3) and a denominator (10). Think of it like keeping a recipe as "3 cups of flour divided by 10" instead of writing down "0.3 cups." The magic happens because modern computers are actually very good at handling whole numbers perfectly, as long as they aren't too huge. The paper points out that computers can handle any whole number up to about 9 quadrillion ( $9 \times 10^{15}$ ) without making a single mistake. Since most real-world measurements (like money, GPS coordinates, or scientific data) fit comfortably inside this huge range, the computer can do all its math using these perfect whole-number pairs.

The system works by delaying the final division. When you add or multiply these pairs, the computer just does the math on the top and bottom numbers separately, keeping the fraction "un-simplified" until it absolutely has to show you the decimal result. To keep the numbers from getting too big and messy, the system has a "cleanup" step. Imagine you have a fraction like 6/10; the cleanup step instantly simplifies it to 3/5 by dividing both by their greatest common factor. The paper suggests that computer chips should have a special, super-fast button to do this cleanup instantly, making the whole process nearly as fast as the standard, flawed math.

Even cooler, the paper shows that these pairs can be stacked inside each other, like Russian nesting dolls. You can have a fraction where the top or bottom is itself another fraction. This creates a "tree" of math that the computer can hold in its memory without calculating the final answer right away. This is a game-changer for deep learning (the kind of AI that powers self-driving cars and chatbots). In these AI systems, a common problem is the "vanishing gradient," where the math gets so tiny after many layers of calculation that it effectively disappears, causing the AI to stop learning. The paper proves that because this new system uses exact whole numbers, the math can never accidentally shrink to zero unless it is truly zero. It's like having a ladder that never loses a rung, no matter how high you climb.

The authors also show that this method makes computer results perfectly predictable. Right now, if you run the same AI training on two different types of graphics cards, you might get slightly different results because of how they handle rounding errors. With this new system, if you follow the same steps, you get the exact same answer every time, on any machine. The paper doesn't claim this is a magic fix for everything; it admits that for extremely long chains of multiplication without the "cleanup" step, the numbers could get too big for the computer to handle. But for most practical uses, it suggests a way to make scientific computing and AI training exact, stable, and reproducible without sacrificing too much speed. It's a proposal to upgrade the very foundation of how computers do math, turning a system that guesses into one that knows.

Technical Summary: Quotient Tree Arithmetic (QTA)

Problem Statement

Floating-point arithmetic (IEEE 754), while the standard for scientific computing and machine learning for decades, suffers from fundamental limitations:

Inexact Representation: Common decimal values (e.g., 0.1) cannot be represented exactly, leading to errors like $0.1 + 0.2 \neq 0.3$ .
Underflow and Vanishing Gradients: Tiny values round to zero, causing the vanishing gradient problem in deep neural networks where gradient products collapse to zero.
Non-Determinism: Results vary across hardware, compiler versions, and operand ordering due to rounding modes and fused multiply-add (FMA) availability.
Comparison Heuristics: Equality checks require arbitrary $\epsilon$ -tolerances, which are unreliable.

Existing remedies, such as arbitrary-precision libraries (GMP, Decimal), impose severe performance costs, while quantization (INT8, FP8) sacrifices precision and introduces systematic errors.

Methodology

The paper proposes Rational Pair Arithmetic (RPA) and its extension, Quotient Tree Arithmetic (QTA), as a unified framework for exact and near-exact computation.

1. Rational Pair Arithmetic (RPA)

The core insight relies on the IEEE 754 Integer Exactness Window: IEEE 754 double-precision floats represent all integers in the range $(-2^{53}, 2^{53})$ exactly.

Representation: Real-valued quantities are stored as ordered pairs $(n, d)$ of IEEE doubles, treated strictly as integers. The value is $n/d$ , evaluated lazily.
Arithmetic: Operations are performed on the integer components:
- $(a, b) + (c, d) = (ad + bc, bd)$
- $(a, b) \times (c, d) = (ac, bd)$
- Comparison is performed via cross-multiplication ($ad < bc$).
Exactness: As long as $|n|, |d| < 2^{53}$ , all arithmetic is exact without multi-precision libraries. This covers practical domains like currency (up to $\approx \$ 90$ billion in cents) and scientific measurements.

2. The Cleanup Operation

To prevent numerator and denominator magnitudes from growing unbounded (which would exceed the $2^{53}$ window), the system employs a Cleanup operation:

Mechanism: Divide both $n$ and $d$ by $\gcd(|n|, |d|)$ .
Hardware Proposal: The paper proposes a new SIMD instruction, RatCleanup, to perform vectorized GCD reduction, making RPA competitive with single-precision floats in throughput.
Tracked Cancellation: For structured computations (e.g., fixed denominators in currency), the compiler can cancel factors without a full GCD algorithm, reducing overhead to $O(1)$ .

3. Quotient Tree Arithmetic (Nested RPA)

The framework extends to Nested Rational Pairs, where numerators or denominators can themselves be rational pairs, forming a symbolic expression tree.

Deferred Evaluation: Expressions are maintained as trees. Evaluation (flattening to a single pair) is deferred until a concrete floating-point result is explicitly requested.
Bounded Depth: Theorem 4.2 proves that tree depth grows by at most 1 per arithmetic operation ( $O(m)$ total size for $m$ operations), avoiding the combinatorial explosion ( $O(2^m)$ ) seen in generic symbolic algebra systems.
Cross-Cancellation: Theorem 4.3 establishes that common factors appearing in both the numerator and denominator subtrees can be cancelled symbolically before any division occurs. This applies even to transcendental values (e.g., $e^x$ ) if they are reference-equal.

Key Contributions

Formal Definition of RPA: Exploiting the IEEE integer exactness window to create a fixed-width, hardware-accelerated rational type.
The Cleanup Primitive: A proposed hardware instruction (RatCleanup) and theoretical proof that it maintains values within the exactness window, ensuring exactness indefinitely.
Nested Rational Pair Algebra: A formal treatment of symbolic nesting with proofs of bounded depth growth, flattening in $O(k)$ steps, and cross-cancellation theorems.
Stability Theorems:
- Deferred Stability: Deferred evaluation reduces rounding error from $O(m)$ ULPs (eager evaluation) to $O(1)$ ULPs.
- Vanishing Gradient Impossibility (Theorem 8.1): Under RPA with cleanup, a product of non-zero rational pairs is structurally impossible to be zero. This eliminates arithmetic underflow in deep network gradients.
Cross-Hardware Determinism: Given a fixed computation order, RPA results are independent of hardware rounding modes, FMA availability, or driver versions.

Results and Claims

The paper provides theoretical proofs and analytical estimates rather than empirical benchmarks:

Throughput: Analytical estimates suggest flat RPA is $\sim 5\text{--}18\times$ slower than FP32 (depending on the operation and cleanup cost) but comparable to FP64. With the proposed RatCleanup instruction, the overhead is manageable for high-precision applications.
Gradient Stability: The structural impossibility of vanishing gradients allows for the theoretical feasibility of very deep "plain" networks (hundreds of layers) without skip connections or gating mechanisms, provided the arithmetic remains within the exactness window.
Exact Convergence: Convergence criteria can be defined as exact equality ( $L_t = L_{t-1}$ ) rather than heuristic thresholds ( $|L_t - L_{t-1}| < \epsilon$ ).
Bandwidth Efficiency: By treating computation as a symbolic phase (tree construction and cancellation) followed by a numeric phase (materialization), QTA reduces memory traffic. Shared subtrees (e.g., weights) are loaded once, and symbolic cancellations eliminate intermediate memory writes.

Significance

The paper positions QTA not merely as a number format but as a computational substrate that decouples symbolic manipulation from numeric evaluation.

Structural Intelligence: It argues that modern AI systems pay a "worst-case cost" for every query. QTA introduces a layer of structural intelligence that exploits algebraic properties (cancellation, deferred division) to reduce the actual computation required, similar to how caching or sparse attention works but with exact guarantees.
Safety and Certification: For safety-critical domains (autonomous vehicles, medical AI), the ability to provide certified derivatives (exact proofs of stationarity) and reproducible training is a paradigm shift from probabilistic heuristics.
Hardware Independence: It offers a path to deterministic scientific computing, eliminating the "bit-rot" of results across different GPU generations or CUDA versions.

The authors conclude that while RPA trades raw throughput for exactness, this trade-off is essential for scientific computing and safety-critical machine learning, where the cost of error is higher than the cost of computation. The proposed RatCleanup instruction is identified as the key enabler to make this framework practical on existing hardware architectures.