🤖 machine learning

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

本論文は、値を遅延された商のペアとして表現することで、厳密な有理演算、限定された記号的深さ、および部分木を跨ぐ相殺を実現し、代数的な局所化理論とハードウェアネイティブなIEEE算術を結びつけることで、機械学習のトレーニングにおける数値誤差とメモリオーバーヘッドを大幅に削減する計算フレームワークである商木算術（Quotient Tree Arithmetic: QTA）を導入する。

原著者： 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が内部計算のズレによって混乱したり、金融システムが1ペニーの行方を見失ったりといった、大きな問題を引き起こす可能性があります。

これを解決するために、人々は通常、より低速な「十進数」ツールを使用するか、あるいは非常に正確ですが極めて重くて遅い「記号的」数学を使用します。それは、コーヒーを買いに行くためだけに、バックパックに図書館を詰め込んで運ぼうとするようなものです。大きな疑問はこうです。「速くて欠陥のある定規のスピードと、重くて遅い完璧な定規の正確さを、同時に手に入れることはできるのか？」というパズルです。グレゴリー・マガルシャクによる新しい論文は、この問題を解決しようとしています。彼は、コンピュータの標準的な数学を完璧な分数のシステムへと変える巧妙なトリックを提案しており、ハードウェアのスピードを維持しながら、通常入り込んでしまう微小な誤差を排除しようとしています。

この論文は、**有理数ペア演算（Rational Pair Arithmetic: RPA）**と呼ばれるシステムを紹介しています。0.3のような数値を、一つの少し乱れた小数として保存する代わりに、コンピュータはそれを分子（3）と分母（10）という一対の整数として保存します。これは、レシピを「0.3カップ」と書くのではなく、「10分の3カップ」として保持するようなものです。魔法は、現代のコンピュータが、数字が大きすぎない限り、整数を完璧に扱うのが非常に得意であるという点にあります。論文は、コンピュータは間違いを一度も犯すことなく、約9000兆（ $9 \times 10^{15}$ ）までの整数を扱えることを指摘しています。現実世界のほとんどの測定値（お金、GPS座標、科学データなど）はこの巨大な範囲内に余裕を持って収まるため、コンピュータはこれらの完璧な整数のペアを使用してすべての計算を行うことができます。

このシステムは、最終的な割り算を遅延させることで機能します。これらのペアを加算または乗算するとき、コンピュータは分数の「未簡略化」された状態を保ったまま、分子と分母に対して個別に計算を行います。数字が大きくなりすぎて乱雑になるのを防ぐために、システムには「クリーンアップ」ステップがあります。例えば、6/10という分数がある場合、クリーンアップステップは両方を最大公約数で割ることにより、即座に3/5へと簡略化します。論文は、コンピュータチップがこのクリーンアップを即座に行うための特別な超高速ボタンを備えるべきであり、それによってプロセス全体を標準的な欠陥のある数学とほぼ同等の速度にできると示唆しています。

さらに素晴らしいことに、この論文は、これらのペアがロシアのマトリョーシカ人形のように、互いの中に積み重ねられることを示しています。分子または分母自体が別の分数であるような構造を作ることができるのです。これは、コンピュータが最終的な答えをすぐに計算することなく、メモリ内に保持できる「計算の木」を作り出します。これは、ディープラーニング（自動運転車やチャットボットを動かすAIの基盤となる技術）にとってゲームチェンジャーとなります。これらのAIシステムにおける一般的な問題は、「勾配消失」です。これは、多くの層の計算を経て計算が非常に小さくなり、実質的に消失してしまう現象で、AIの学習を停止させてしまいます。論文は、この新しいシステムは正確な整数を使用しているため、真にゼロでない限り、数学的に偶然ゼロに縮小することはないと証明しています。それは、どれほど高く登っても決して段が失われることのない梯子のようです。

著者らはまた、この手法によってコンピュータの結果が完全に予測可能になることも示しています。現在、同じAIのトレーニングを2種類の異なるグラフィックスカードで行った場合、丸め誤差の処理方法の違いにより、結果がわずかに異なることがあります。このシステムを用いれば、同じ手順に従う限り、どのマシンであっても常に全く同じ答えが得られます。論文は、これがすべてに対する魔法の解決策であると主張しているわけではありません。「クリーンアップ」ステップなしで極端に長い乗算の連鎖を行った場合、数字がコンピュータで扱えないほど大きくなる可能性があることを認めています。しかし、ほとんどの実用的な用途において、科学計算や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 double 型の整数の順序ペア $(n, d)$ として格納され、厳密に整数として扱われます。値は $n/d$ であり、遅延評価されます。
演算： 演算は整数成分に対して行われます：
- $(a, b) + (c, d) = (ad + bc, bd)$
- $(a, b) \times (c, d) = (ac, bd)$
- 比較は、たすき掛け（cross-multiplication）を用いて行われます ($ad < bc$)。
正確性： $|n|, |d| < 2^{53}$ である限り、多精度ライブラリを使用することなく、すべての演算は正確です。これは、通貨（約900億ドルまでのセント単位）や科学的測定などの実用的な領域をカバーしています。

2. クリーナップ操作

分子と分母の大きさが無制限に増大すること（これにより $2^{53}$ ウィンドウを超えること）を防ぐため、システムは クリーナップ (Cleanup) 操作を採用します。

メカニズム： $n$ と $d$ を $\gcd(|n|, |d|)$ で除算します。
ハードウェア提案： 本論文では、ベクトル化された GCD 簡約を実行するための新しい SIMD 命令 RatCleanup を提案しており、これにより 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）と、値が正確性を維持することを保証し、正確性を無限に維持する GCD 簡約の理論的証明。
入れ子状有理対代数： 入れ子状の記号的ネストの形式的扱い、および、深さの増大が限定的であること、および $O(k)$ ステップでの平坦化、および相互相殺定理の証明。
安定性定理：
- 遅延安定性： 遅延評価により、丸め誤差を $O(m)$ ULP（即時評価）から $O(1)$ ULP に低減します。
- 勾配消失の不可能性（定理 8.1）： クリーナップを伴う RPA の下では、非ゼロの有理対の積が構造的にゼロになることは不可能です。これにより、ディープネットワークにおける算術的なアンダーフローを排除します。
クロスハードウェア決定論： 固定された計算順序が与えられれば、RPA の結果はハードウェアの丸めモード、FMA の可用性、またはドライバーのバージョンに依存しません。

結果と主張

本論文は、経験的なベンチマークよりも、理論的な証明と分析的な推定を提供しています：

スループット： 分析的な推定によれば、フラットな RPA は（演算とクリーナップコストに応じて）FP32 より $\sim 5\text{--}18\times$ 遅いですが、FP64 には匹敵します。提案された RatCleanup 命令を用いることで、オーバーヘッドは管理可能なレベルになります。
勾配の安定性： 勾配消失の構造的不可能性により、スキップ接続やゲーティング機構がない「プレーン」な非常に深いネットワーク（数百層）の理論的な実現可能性を可能にします。
正確な収束： 収束基準は、ヒューリスティックな閾値（ $|L_t - L_{t-1}| < \epsilon$ ）ではなく、正確な等価性（ $L_t = L_{t-1}$ ）として定義できます。
帯域幅効率： 計算を記号フェーズ（ツリー構築と相殺）と数値フェーズ（実体化）に分けることで、QTA はメモリトラフィックを削減します。共有サブツリー（例：重み）は一度だけロードされ、記号的な相殺によって中間的なメモリ書き込みが排除されます。

重要性

本論文は、QTA を単なる数値形式としてではなく、記号的操作と数値評価を切り離す 計算基盤 (computational substrate) として位置付けています。

構造的インテリジェンス： 現代の AI システムは、あらゆるクエリに対して「ワーストケースのコスト」を支払っていると主張しています。QTA は、キャッシュやスパース・アテンションのように、実際の計算量を削減するために代数的な性質（相殺、遅延除算）を活用する、構造的インテリジェンスの層を導入します。
安全性と認証： 自動運転車や医療用 AI などの安全性が重視される領域において、確率的なヒューリスティックから、認定された微分（定常性の正確な証明）や再現可能なトレーニングを提供する能力へのパラダイムシフトをもたらします。
ハードウェア非依存性： 異なる GPU ジェネレーションや CUDA バージョン間での結果の「ビット腐敗」を排除し、決定論的な科学計算への道を提供します。

著者らは、RPA がスループットを犠牲にする一方で、正確性を追求することは、エラーのコストが計算のコストよりも高い科学計算や安全性が重要な機械学習において不可欠であると結論付けています。提案された RatCleanup 命令は、このフレームワークを既存のハードウェアアーキテクチャ上で実用的にするための鍵となる要素として特定されています。