技術要約：浮動小数点数のリダクションツリーにおける二次モーメント理論

問題提起

標準的な浮動小数点加算の最悪ケースの前方誤差界（例：$|\hat{s} - s| \le \gamma_{k-1} \sum |p_i|$）は、リダクションツリーのトポロジーに依存しない。これらの境界は安全性に関する保証を提供する一方で、入力がランダムである場合、異なるツリー構造（逐次、ペアワイズ、ブロック化など）を区別できない。その結果、どのトポロジーが与えられたデータセットに対して典型的な誤差（平均二乗誤差、MSE）を最小化するかを予測することができない。本論文は、「リダクションの幾何学（reduction geometry）」、すなわちペアワイズ加算の特定の順序が、入力の統計量とどのように相互作用して誤差の蓄積を決定するかを捉えるモデルの必要性に取り組んでいる。

手法

著者らは、誤差の蓄積を、ツリー構造に依存する確率過程としてモデル化することで、最悪ケース解析を超えた二次モーメント理論を展開している。

1. 正確な条件付き再帰

解析は、条件付きに不偏な丸め（例：確率的丸め）から始まる。丸めが行われる直前の情報（$\sigma$-代数 $\mathcal{F}^-_v$）に基づいて条件付けることで、著者らは蓄積される誤差分散の正確な再帰式を導出している。この再帰式は、継承された誤差と局所的な丸め誤差を分離し、クロス項の期待値が消滅することを示している。局所的な分散は、丸め前のオペランドの値 $x_v$ に依存することが示されている。

2. 定数-$\nu$ モデル

決定論的な丸め（round-to-nearest）において、誤差が厳密に条件付き不偏ではない状況下で、扱いやすいモデルを作成するために、著者らは「定数-$\nu$」近似を導入している。彼らは、オペランドに依存する局所分散を、経験的に較正された無次元係数 $\nu$ を用いた同次モデル $\psi_v(x) = \nu u^2 x^2$ に置き換えている。これにより、再帰式は全期待二乗誤差が平方部分和の総和 $\sum_v q_v^2$ に比例するという形式へと簡略化される。

3. 共通祖先カーネル ($K_T$)

本研究の核心となる理論的貢献は、平方部分和を以下の二次形式として表現することである：
$$\sum_{v \in \text{int}(T)} q_v^2 = p^\top K_T p$$
ここで、$K_T$ は 共通祖先カーネル（common-ancestor kernel） であり、$k \times k$ 行列であり、そのエントリー $(K_T)_{ij}$ は、葉 $i$ と葉 $j$ の両方の祖先である内部ノードの数をカウントする。この行列は、リダクションの幾何学をエンコードしている。

4. i.i.d. 圧縮とツリー統計量

独立かつ同一の分布（i.i.d.）に従う入力（平均 $\mu$、分散 $\tau^2$）について、二次形式の期待値は以下の2つのスカラー・ツリー統計量へと収束する：
$$\mathbb{E}[\text{MSE}] \propto \tau^2 \Lambda_1(T) + \mu^2 \Lambda_2(T)$$

• $\Lambda_1(T)$: 葉の深さの総和（全外部パス長）。これは、中心化された入力（$\mu=0$）における誤差を支配する。
• $\Lambda_2(T)$: 二乗された内部部分木のサイズの総和。これは、非中心化された入力（$\mu \neq 0$）における誤差を支配する。

5. GEMMへの拡張

本理論は、行列行列積（GEMM）へと拡張されている。期待されるフロベニウスノルム誤差の二乗は、オペランドのグラム行列のアダマール積によって形成される行列 $G$ と、カーネル $K_T$ との縮退（contraction）として示される（$G = (A^\top A) \circ (BB^\top)$）。

主な貢献

理論的最適化

本論文は、異なるレジームにおける最適なツリー・トポロジーを導出している：

• 中心化された入力: バランスの取れたツリーは $\Lambda_1$ を最小化し、逐次的なツリーは $\Lambda_1$ を最大化する。RMS誤差の最適指数は、ペアワイズ・ツリーにおいて $1/2$ である。
• 非中心化された入力: 最適なトポロジーは変化する。固定ステージの階層構造において、著者らは、$\Lambda_2$ を最小化するためにステージ比が連続的に半分になる（$r_\ell \propto 2^{-\ell}$）「倍々ギャップ・スケジュール（doubling-gap schedule）」を導出している。
• 不均一な分散: 分散が異なる独立した中心化入力の場合、最適なツリー構造はハフマン符号化に対応し、分散重み付きの外部パス長を最小化する。
• ブロッキング: 2段階の逐次ブロッキングにおいて、中心化された入力に対する最適なブロックサイズは $b \propto \sqrt{k}$ とスケールする（これにより RMS 指数は $3/4$ となる）が、非中心化された入力には異なるスケーリングが必要となる。

実証的検証

著者らは、複数の精度（binary64, binary32, ソフトウェア・エミュレートされたbinary16, およびbfloat16）および入力タイプにわたって、定数-$\nu$ モデルを検証している：

• トポロジーの順序付け: モデルは、逐次、ブロック化、およびペアワイズ・ツリー間のRMS誤差の順序を正しく予測する。
• 較正: binary64 の round-to-nearest に対して独立に較正された $\nu \approx 0.19$ を用いることで、モデルは GEMM において絶対 MSE を 3% 以内の精度で予測でき、様々なツリー・ファミリーのスケール則を正しく捉えることができる。
• 停滞限界: 本研究は、低精度（binary16/bfloat16）の正の和における「停滞（stagnation）」（小さな数を大きな数に加えても変化しない現象）により、バイアスが支配的となり、定数-$\nu$ 近似が崩れる失敗レジームを特定している。

結果

• スケーリング則: 本論文は、中心化された入力に対して、ペアワイズ加算は $O(\sqrt{\log k})$、ブロック加算（$b \propto \sqrt{k}$）は $O(k^{3/4})$、逐次加算は $O(k)$ とスケールすることを裏付けている。
• 非中心化レジーム: 非ゼロの平均を持つ入力（例：softmax の分母、平方和など）の場合、誤差は $\Lambda_2$ によって支配される。最適な「倍々ギャップ」スケジュールは、中心化された入力に最適な幾何学的スケジュールとは異なるスケーリング挙動をもたらす。
• 相関のある入力: AR(1) 相関を持つ入力については、完全なカーネル縮退 $\langle K_T, M \rangle$ が必要であり、i.i.d. 近似は相関が増大するにつれて著しく失敗する。
• ライブラリの検証: モデルは、再構成された NumPy の np.sum ツリーの誤差スケーリングを正確に予測し、そのマルチスケール階層（小さなブロック内での逐次的蓄積、および大規模な場合の再帰的半減）によって引き起こされる誤差成長の特有の「曲がり」を捉えることに成功している。

意義と主張

本論文は、最悪ケースの境界と実用的な誤差挙動の間の溝を埋める二次モーメント理論を提供することを主張している。その意義は以下の点にある：

1. 幾何学的認識: 標準的な境界が無視している、リダクションツリーの構造（幾何学）が入力統計量とどのように相互作用するかを明示的に定量化している。
2. 予測能力: 特定のツリー構造と入力分布が与えられたときに、特定の実装の RMS 誤差を予測するためのワークフロー（表1）を提供しており、これは幅広い精度とアーキテクチャにわたって検証されている。
3. 最適化の指針: データが中心化されているか非中心化されているか、あるいは分散が均質であるかに基づいて、最適なリダクション・スケジュール（例：ブロックサイズ、ステージ比）を選択するための具体的な基準を提供する。
4. 限界: 著者らは、モデルが $h(T)u^2 \ll 1$ という仮定に依存しており、binary16/bfloat16 の実験で見られたように、停滞や系統的なバイアスが誤差の支配的要因となる低精度レジームでは失敗する可能性があることを謙虚に述べている。定数-$\nu$ は、普遍的な算術定数ではなく、経験的な較正値である。

本研究は、ランダムな入力に対しては、「典型的な」誤差はツリーの共通祖先構造によって支配されることを確立しており、これにより、特定のデータ特性に合わせた数値的に安定したリダクションツリーの設計が可能となる。