技術概要：FibQuant - ランダムアクセス KV キャッシュ圧縮のための汎用ベクトル量子化

1. 問題定義

自己回帰型トランスフォーマーにおける長文脈推論は、主にキー・バリュー（KV）キャッシュに起因するメモリ帯域幅と容量の制約により、ますます制限されるようになっている。キャッシュサイズは、文脈長、バッチサイズ、レイヤー数、ヘッド数に比例して線形に増大し、かつ各デコーディングステップでアクセスされなければならない。

既存の圧縮手法は、ランダムアクセスという重要なシステム制約に直面している。展開可能なキャッシュコーデックは、任意のトークンのキーまたは値を単純なアドレス算術を通じて独立して復号化できるよう、固定アドレスに表現を格納しなければならない。この制約は、可変長符号化や文脈依存表現を排除し、固定レート量子化の使用を強制する。

現在の最先端ランダムアクセスコーデック、例えばTURBOQUANTは、「正規化–回転–量子化」というアプローチを採用している：

1. ベクトルのノルムを格納する。
2. 共有されたランダム直交（Haar）回転を適用する。
3. 回転された各座標をスカラー Lloyd–Max テーブルを用いて独立に量子化する。

このインターフェースは汎用的かつランダムアクセス可能であるが、本論文は幾何学的に最適ではないと主張している。ベクトルが正規化され Haar 回転された後、$k$個の連続する座標のブロックは、独立したスカラー周辺分布の積を形成しない。代わりに、それは単位球上の球面ベータ源を形成する。スカラーコーデックは座標を独立とみなし、回転されたブロックに内在する幾何学的構造（半径方向および角度方向の相関）を捨象する。さらに、スカラー手法は座標あたり 1 ビット未満で効果的に動作することが困難であり、現在の汎用かつ較正不要なコーデックが機能しない「1 ビット未満のギャップ」を生み出している。

2. 手法：FibQuant

FibQuantは、スカラー手法と同じ「正規化–回転」インターフェースを維持しつつ、スカラー座標テーブルを共有された半径–角度ベクトルコードブックに置き換える、汎用固定レートベクトル量子化を提案する。

2.1 標準源

著者らは、正規化–Haar 回転インターフェースが、元の KV データ分布に関わらず、普遍的な源分布を誘導することを証明している。

• 正規化： スケールを除去する。
• Haar 回転： 向きを除去する。
• 結果： 回転された単位ベクトルは、球面 $S^{d-1}$ 上で Haar 一様分布に従う。したがって、任意の $k$ 個の連続する座標のブロックは、単位球 $B^k$ 上の特定の球面ベータ密度 $f_{d,k}$ に従う。
• 示唆： 源分布が入力に依存しない不変であるため、単一のオフラインコードブックですべてのレイヤー、ヘッド、プロンプト、モデルにサービスを提供できる。

2.2 コードブック構築

FibQuant コードブックは、球面ベータ源に一致するように構築され、3 つのコンポーネントを組み合わせる：

1. 半径 ($r_n$)： ベネット–ゲルショ・コンパンディング則を用いて、球面ベータ源の半径方向密度に一致させる。$k=2$ の場合、これはベータ量子化半径を含む閉形式解をもたらす。
2. 方向 ($u_n$)： 均一な角度パッキングを確保するために、準一様球面点集合を用いて近似する：
   • $k=2$：平面フィボナッチ螺旋（ゴールデン量子化）。
   • $k=3$：フィボナッチ球。
   • $k \ge 4$：ロバーツ–クローネッカー低不一致数列。
3. 洗練： マルチリスタートLloyd–Maxアルゴリズムにより、特定の有限コードブックサイズ $N$ に対する平均二乗誤差（MSE）を最小化するため、決定論的初期化を洗練する。

2.3 エンコーディングとデコーディング

• エンコーダ： ノルム $\nu = \|x\|_2$ を計算し、単位ベクトル $\Pi x / \nu$ を回転させ、それをサイズ $k$ の $d/k$ 個のブロックに分割し、共有コードブックに対して最近傍コードワード検索を実行する。
• デコーダ： コードワードを取得し、ブロックを再構成し、ブロックを連結し、逆回転を適用し、ノルムでスケーリングする。
• レート： ビットレートは $b = (\log_2 N) / k$ ビット/座標である。$N$ と $k$ を変化させることで、FibQuant は高密度レート軸を実現し、可変長アドレス指定なしに分数ビットおよび 1 ビット未満の動作点を実現する。

3. 主要な貢献

3.1 標準源の特定

本論文は（定理 1）、ノルム–Haar 回転インターフェースが、任意の非ゼロ入力分布を同じ球面ベータ周辺分布 $f_{d,k}$ にマッピングすることを証明している。これにより、共有オフラインコードブックが KV キャッシュ圧縮のための理論的に正しい汎用オブジェクトであることが確立される。

3.2 スカラー特化に対するベクトルの優位性

著者らは（定理 2）、最適な $k$-ベクトル符号が、一致したレートにおいてスカラー積特化（$k=1$）を厳密に凌駕することを証明している。高レート利得は 2 つのコンポーネントに分解される：

1. セル形状因子 ($\gamma_{cell}$)： ベクトル量子化セル（例：2 次元では六角形）は、長方形のスカラーセルよりも効率的である。
2. 密度一致因子 ($\gamma_{dens}$)： 結合球面ベータ密度に一致することは、スカラー周辺分布のみに一致することよりも優れている。

3.3 高密度レート軸

整数ビットレートに限定されるスカラー Lloyd–Max テーブルとは異なり、FibQuant は $b \in (0, \infty)$ の高密度レート集合を実現する。これにより、現在の汎用ランダムアクセスコーデックが機能しなくなる1 ビット未満の領域（例：$b \approx 0.19$）での動作が可能になる。

4. 実験結果

4.1 源符号化性能

標準的な球面ベータ源において、FibQuant はすべての整数レートでスカラー TURBOQUANT を厳密に凌駕している。また、整数レート間のギャップを埋め、スカラー手法では到達できない動作点を提供する。

4.2 KV キャッシュ圧縮（GPT-2 Small）

アテンション出力の余弦類似度を指標として、GPT-2 small の KV キャッシュで評価された：

• FibQuant は、0.99 の類似度で5 倍圧縮から、0.946 の類似度で34.1 倍圧縮までのメモリ–忠実度フロンティアを描く。
• 高圧縮比（>10 倍）において、FibQuant はレイヤーごとの較正を必要とする低ランク射影手法を上回り、忠実度を維持する唯一の汎用かつ較正不要な手法である。
• 論文は、完全ベクトル符号（$k=d$）が、すべてのビットを角度パッキングに費やすため、極端な圧縮において半ベクトル符号（$k=d/2$）よりも優れていると指摘している。これはアテンション内積と直接相関する。

4.3 エンドツーエンド言語モデル性能（TinyLlama-1.1B）

WikiText-103 のパープレキシティと HellaSwag の精度で評価された：

• $b=4$（4 倍圧縮）： FibQuant は fp16 ベースラインから 0.10 のパープレキシティの範囲内にあり、スカラー TURBOQUANT を上回る。
• $b=2$（8 倍圧縮）： FibQuant は 15.88 のパープレキシティを達成し、スカラー TURBOQUANT（56.72）およびトークンごとの INT 量子化（4450.5 に崩壊）を大幅に上回る。
• 分数レート： FibQuant は、スカラーコーデックでは利用できない中間動作点（例：$b=2.5, 3.5$）を提供し、まずキャッシュ予算を選択し、それに合わせてコーデックを調整することを可能にする。

5. 意義と主張

本論文は、ランダムアクセス制約が、しばしば工学的限界と見なされるものが、深い数学的帰結を持つと主張している。すなわち、データを特定の球面ベータ幾何学に強制するということである。この標準源を認識することで、FibQuant はスカラー量子化が手放している「形状および密度一致の利得」を回復する。

その意義は以下の点にある：

1. 汎用性： 単一のコードブックが、較正なしにすべてのモデル構成で機能する。
2. 1 ビット未満動作： スカラー手法が失敗する領域で高忠実度圧縮を可能にし、長文脈推論の実用可能なメモリ予算を実質的に拡大する。
3. システム互換性： 圧縮解除をアテンションカーネルと融合するために必要な固定アドレス・ランダムアクセスインターフェースを維持するため、既存のサービングフレームワークですぐに展開可能である。

著者らは、ランダムアクセスが優れた源符号化を排除するのではなく、むしろ符号化すべき源を正確に規定すると結論付けている。