🤖 machine learning

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

本文介绍了商树算术（Quotient Tree Arithmetic, QTA），这是一种将数值表示为延迟商对的计算框架，旨在实现精确的有理数算术、有界的符号深度以及跨子树抵消，从而在连接代数局部化理论与硬件原生 IEEE 算术的同时，显著降低机器学习训练中的数值误差和内存开销。

原作者： Gregory Magarshak

发布于 2026-07-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Gregory Magarshak

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图用一把带有微小、隐形瑕疵的尺子来测量世界。几十年来，科学家和计算机程序员一直使用一种被称为“浮点运算”的标准测量工具来进行计算机数学计算。它速度极快，几乎适用于所有场景，从计算火箭轨道到训练推荐你下一首最爱歌曲的 AI。但它有一个著名的、令人恼火的小故障：它无法完美地处理某些简单的数字。如果你要求计算机计算 0.1 加 0.2，它给出的结果并不是精确的 0.3，而是 0.30000000000000004。这就像是用一把钝刀去把披萨切成完美的薄片；久而久之，碎屑会不断累积，导致你的每一片都不等大。这种微小的误差可能会导致大问题，比如 AI 因为内部计算产生偏差而变得混乱，或者金融系统丢失了一分钱的账目。

为了解决这个问题，人们通常使用特殊的“十进制”工具，但它们速度较慢；或者使用“符号化”数学，虽然极其精确，但极其沉重且缓慢，就像为了买杯咖啡而背着一整个图书馆一样。核心问题一直在于：我们能否同时获得快速、有瑕疵的尺子的速度，以及沉重、缓慢的精确工具的完美精度？这是一个由 Gregory Magarshak 撰写的论文试图解决的谜题。他提出了一个聪明的技巧，将计算机的标准数学转化为一个完美的比例系统，在保留硬件速度的同时，消除了通常会悄然出现的微小误差。

该论文引入了一种名为**有理数对算术（Rational Pair Arithmetic, RPA）**的系统。与其将像 0.3 这样的数字存储为一个单一的、略显混乱的十进制小数，不如让计算机将其存储为一对整数：一个分子（3）和一个分母（10）。这就像是将食谱记录为“3 杯面粉除以 10”，而不是写下“0.3 杯面粉”。神奇之处在于，现代计算机在处理整数方面非常出色，只要这些整数不是过于庞大。论文指出，计算机可以完美处理高达约 9 千万亿（ $9 \times 10^{15}$ ）的任何整数而不会出错。由于大多数现实世界的测量值（如金钱、GPS 坐标或科学数据）都能舒适地落在这一巨大范围内，计算机可以使用这些完美的整数对进行所有的数学运算。

该系统的工作原理是延迟最终的除法。当你对这些数对进行加法或乘法时，计算机只是分别对分子和分母进行计算，保持分数的“未简化”状态，直到绝对必要时才向你展示十进制结果。为了防止数字变得过大且杂乱，系统包含了一个“清理”步骤。想象一下，你有一个分数 6/10；清理步骤会通过除以它们的最大公约数，立即将其简化为 3/5。论文建议，计算机芯片应该有一个特殊的、超快速的按钮来即时完成这种清理工作，使整个过程几乎与标准的、有瑕疵的数学一样快。

更酷的是，论文展示了这些数对可以像俄罗斯套娃一样嵌套在一起。你可以拥有一个分子或分母本身又是另一个分数的比例。这创造了一个计算机可以在内存中持有的数学“树”，而无需立即计算出最终答案。这对于深度学习（即驱动自动驾驶汽车和聊天机器人的 AI 技术）来说是一个游戏规则的改变者。在这些 AI 系统中，一个常见的问题是“梯度消失”，即经过许多层计算后，数学数值变得如此微小，以至于实际上消失了，导致 AI 停止学习。论文证明，由于这个新系统使用的是精确的整数，数学运算绝不会在真正为零的情况下意外缩减为零。这就像拥有一把无论爬多高都永远不会丢失横档的梯子。

作者还表明，这种方法使计算机结果具有完美的预测性。目前，如果你在两种不同类型的图形卡上运行相同的 AI 训练，你可能会得到略有不同的结果，因为它们处理舍入误差的方式不同。有了这个新系统，如果你遵循相同的步骤，在任何机器上都能得到完全相同的答案。论文并未声称这是解决一切问题的万能药；它承认，对于没有“清理”步骤的极长乘法链，数字可能会变得太大而超出计算机的处理能力。但对于大多数实际用途，它提出了一种方法，让科学计算和 AI 训练变得精确、稳定且可复现，且不会牺牲太多速度。这不仅是在提议升级计算机进行数学运算的基础，更是要将一个“靠猜测”的系统转变为一个“知晓真相”的系统。

技术摘要：商树算术 (Quotient Tree Arithmetic, QTA)

问题陈述

浮点运算（IEEE 754）虽然作为科学计算和机器学习的标准已沿用数十年，但存在根本性的局限性：

表示不精确： 常见的十进制值（如 0.1）无法被精确表示，导致出现诸如 $0.1 + 0.2 \neq 0.3$ 的误差。
下溢与梯度消失： 微小的值会舍入为零，导致深度神经网络中梯度乘积塌缩为零的梯度消失问题。
非确定性： 由于舍入模式和融合乘加（FMA）可用性的差异，结果会随硬件、编译器版本和操作数顺序的不同而变化。
比较启发式方法： 等值检查需要依赖任意的 $\epsilon$ -容差，而这种方式是不可靠的。

现有的补救措施，如任意精度库（GMP、Decimal），会带来严重的性能成本；而量化（INT8、FP8）则会牺牲精度并引入系统性误差。

方法论

本文提出了有理数对算术 (Rational Pair Arithmetic, RPA) 及其扩展——商树算术 (Quotient Tree Arithmetic, QTA)，作为一个用于精确及近精确计算的统一框架。

1. 有理数对算术 (RPA)

其核心洞察在于 IEEE 754 整数精确窗口：IEEE 754 双精度浮点数能精确表示范围在 $(-2^{53}, 2^{53})$ 内的所有整数。

表示： 实数值量被存储为两个 IEEE 双精度浮点数组成的有序对 $(n, d)$ ，并严格作为整数处理。其值为 $n/d$ ，采用惰性求值。
算术运算： 运算在整数分量上进行：
- $(a, b) + (c, d) = (ad + bc, bd)$
- $(a, b) \times (c, d) = (ac, bd)$
- 比较通过交叉相乘进行 ($ad < bc$)。
精确性： 只要 $|n|, |d| < 2^{53}$ ，所有运算都是精确的，无需多精度库。这涵盖了实际应用领域，如货币（最高可达约 900 亿美元的厘）和科学测量。

2. 清理操作 (The Cleanup Operation)

为了防止分子和分母的量级无限制增长（从而超出 $2^{53}$ 窗口），系统采用了清理 (Cleanup) 操作：

机制： 将 $n$ 和 $d$ 同时除以 $\gcd(|n|, |d|)$ 。
硬件提案： 本文提出了一种新的 SIMD 指令 RatCleanup，用于执行向量化 GCD 约简，使 RPA 在吞吐量上能与单精度浮点数竞争。
追踪抵消： 对于结构化计算（例如固定分母的货币计算），编译器可以无需完整的 GCD 算法即可实现因子的抵消，将开销降低至 $O(1)$ 。

3. 商树算术 (嵌套 RPA)

该框架扩展到了嵌套有理数对 (Nested Rational Pairs)，其中分子或分母本身可以是另一个有理数对，从而形成一个符号表达式树。

延迟求值： 表达式以树的形式维护。求值（将其展平为单个数对）被推迟到明确请求具体浮点结果时才进行。
有界深度： 定理 4.2 证明，树的深度在每次算术运算后最多增加 1（对于 $m$ 次运算，总大小为 $O(m)$ ），避免了通用符号代数系统中出现的组合爆炸问题 ( $O(2^m)$ )。
交叉抵消： 定理 4.3 确立了出现在分子和分母子树中的共同因子可以在任何除法发生之前进行符号抵消。即使对于超越值（如 $e^x$ ），如果它们是引用相等的，这一特性同样适用。

核心贡献

RPA 的形式化定义： 利用 IEEE 整数精确窗口创建一种硬件加速的有理数类型。
清理原语： 提出了一种硬件指令 (RatCleanup) 以及能够维持数值在精确窗口内的理论证明，确保了无限期的精确性。
嵌套有理数对代数： 对符号嵌套进行了形式化处理，并提供了关于深度增长有界性、 $O(k)$ 步展平以及交叉抵消定理的证明。
稳定性定理：
- 延迟稳定性： 延迟求值将舍入误差从 $O(m)$ ULPs（急切求值）降低到 $O(1)$ ULPs。
- 梯度消失不可能定理 (定理 8.1)： 在带有清理操作的 RPA 下，非零有理数对的乘积在结构上不可能为零。这消除了深度网络梯度中的算术下溢。
跨硬件确定性： 在给定的计算顺序下，RPA 的结果独立于硬件舍入模式、FMA 可用性或驱动程序版本。

结果与主张

本文提供的是理论证明和分析估计，而非经验基准测试：

吞吐量： 分析估计表明，平坦 RPA 比 FP32 慢约 $5\text{--}18\times$ （取决于运算和清理成本），但与 FP64 相当。通过提出的 RatCleanup 指令，其开销是可控的。
梯度稳定性： 梯度消失的结构性不可能，使得在不使用跳跃连接或门控机制的情况下，构建极深“纯”网络（数百层）在理论上是可行的。
精确收敛： 收敛准则可以定义为精确相等 ( $L_t = L_{t-1}$ )，而非启发式阈值 ( $|L_t - L_{t-1}| < \epsilon$ )。
带宽效率： 通过将计算视为符号阶段（树构建与抵消）与数值阶段（实例化）的结合，QTA 减少了内存流量。共享子树（如权重）被加载一次，且符号抵消消除了中间内存写入。

意义

本文将 QTA 定位为不仅仅是一种数值格式，而是一种计算基质 (Computational Substrate)，它将符号操作与数值求值解耦。

结构智能： 作者认为现代 AI 系统为每一次查询都支付了“最坏情况成本”。QTA 引入了一层结构智能，利用代数特性（抵消、延迟除法）来减少实际所需的计算，类似于缓存或稀疏注意力机制，但具有精确保证。
安全性与认证： 对于安全至上的领域（自动驾驶、医疗 AI），能够提供经过认证的导数（平稳性的精确证明）和可重复的训练，是从概率启发式向范式转变。
硬件无关性： 它为确定性科学计算提供了一条路径，消除了不同 GPU 代际或 CUDA 版本之间的“结果腐烂”问题。

作者总结道，虽然 RPA 以牺牲原始吞吐量来换取精确性，但对于科学计算和安全关键型机器学习而言，这种权衡是必要的，因为其误差成本远高于计算成本。所提出的 RatCleanup 指令被认为是使该框架在现有硬件架构上变得实用的关键。