技術要約：フラクタルKVキャッシュ・アーカイブ

問題提起

トランスフォーマー言語モデルを長文脈でサービングする課題は、計算量主導からメモリ主導の課題へと移行している。自己回帰的なアテンションに必要なKey-Value（KV）キャッシュは、コンテキスト長に対して線形に増大し、しばしばモデルの重みを凌駕してバッチサイズを制約する。既存のソリューションは、損失を伴う圧縮（量子化、エビクション、オフローディング）に焦点を当てているが、本論文は、よりダウンストリームにある、しばしば暗黙的な問いに対処するものである：ベクトル量子化によってKV状態がシンボルストリームへと削減された後、そのストリームをどのように保存すべきか？

著者らは、ストレージ層は単なる不活性なブロブ（塊）ではなく、成長するキャッシュの特定のアクセスパターンをサポートできる能動的なコンポーネントであるべきだと主張している。具体的には、O(1)の償却追加（append）（新しいトークンが到着した際）およびO(1)のランダムアクセス（過去の位置を呼び出す際）をサポートし、さらにインプレース（in-place）での検索といった追加機能を提供できることが求められる。

メソドロジー

1. ストレージ・プリミティブ：収縮反復写像符号

本論文では、量子化されたKVインデックスのシリアライゼーション層として、損失のない収縮反復写像符号（具体的には、カオス・ゲーム表現およびユニバーサル・シーケンス・マップの一般化）を使用することを提案している。

• メカニズム: サイズ $N$ のアルファベット上のシンボル列を、2D平面上の点の軌跡へと写像する。正 $N$ 角形が固定され、各頂点は一つのシンボルに対応する。各シンボル $c_k$ は、現在の点 $p_{k-1}$ を、収縮 $p_k = V(c_k) + r(p_{k-1} - V(c_k))$ を通じて新しい点 $p_k$ へと写像する（ここで $r$ は収縮比である）。
• 特性:
  • 損失なし（Lossless）: 収縮比 $r$ が十分に小さく、各シンボルの「セル」が互いに素であることを保証できる場合、この写像は可逆的である。
  • 効率性: エンコーディングは線形時間で行われる。デコーディングは、最も近いアンカーポイントから必要なスパンのみを再構成することで、任意のポジションへのランダムアクセスを可能にする。
  • 自己相似性: 到達可能な点の集合は、フラクタル・アトラクタ（例：$N=3$ の場合のシェルピンスキー・ガスケット）を形成する。
• 実装: 逆変換における浮動小数点誤差の増幅を軽減するため、コーデックは固定長の一定スパンごとに一点を保持し、アンカー付き後方探索を用いてスパンを再構成する。

2. 量子化戦略

著者らは、このアーカイブに供給される最適な量子化スキームを決定するために、GPT-2 (124M) および 1024トークンのコンテキストを用いた制御実験を行った。

• 正確なウィンドウ（Exact Window）: パフォーマンスを維持するため、小さな正確なウィンドウ（4つの「アテンション・シンク」トークン + 直近の32トークン）を保持する。残りのコンテキストはアーカイブされる。
• 量子化のバリエーション:
  • Pooled vs. Per-Head: 全てのアテンションヘッドで共有される単一のコードブックと、ヘッドごとの個別コードブックを比較する。
  • 残差ベクトル量子化（RVQ）: ベクトルを $s$ 個のコードブックからのインデックスの和として保存する。
  • Key/Valueの非対称性: Keys（K）とValues（V）を量子化することによる、パープレキシティへの影響の違いを調査する。

3. インプレース検索

本論文は、反復写像符号の幾何学的特性を利用している。すなわち、共通の長さ $s$ のサフィックス（接尾辞）を共有する点は、空間的に近い（距離 $\approx 2r^s$）。これにより、周囲のテキストをデコードすることなく、保存された2Dベクトルに対する近似的な部分文字列クエリを、近傍探索を通じて直接実行することが可能となる。

主な結果

1. コーデックの性能

フラクタル・コーデックは、モデルに依存しない高性能なストレージ・プリミティブとして機能する：

• エンコーディング: 0.68 µs/char（線形時間）。
• ランダムアクセス: 1M文字のドキュメントに対し、ルックアップあたり311 µs。
• 追加（Append）: 1トークンあたり平均175 µs（償却）。

2. 量子化に関する知見（GPT-2, 1024トークン）

• Per-Headの優位性: ヘッドごとのコードブックは、等しいビット予算において、プールド（共有）コードブックよりも大幅に優れた性能を示す。Per-head RVQ（深度2）は、Pooled RVQのパープレキシティ増加率が +29.2% であるのに対し、これを +15.0% に抑える。
• Key/Valueの非対称性: Keysを量子化することは、Valuesを量子化することと比較して、パープレキシティに対して約4倍強力なダメージを与える。
  • Valuesのみ量子化（Keysは正確）: +4.0% パープレキシティ。
  • Keysのみ量子化（Valuesは正確）: +14.5% パープレキシティ。
  • これにより、Keysはアテンションのルーティングを決定し（高感度）、Valuesは平均化される（誤差減衰）という性質が確認された。
• 最適なハイブリッド・スキーム: Keysにより多くのビットを割り当て（4段階のRVQ）、Valuesに少ないビットを割り当てる（2段階のRVQ）ことで、最良のトレードオフが得られる：
  • 圧縮率: fp16キャッシュに対して 36倍 の削減。
  • パープレキシティのコスト: +11.2%（特にアーカイブが支配的となるコンテキストの「後半部分」では +16.6%）。
  • ストレージ: 1025 bytes/token。

3. 検索能力

• 完全な想起（Exact Recall）: 保存された点間の距離を閾値判定することで、長さ $\ell$ の一致するサフィックスを持つすべてのポジションを 1.00 の再現率（Recall） で回収できる。
• 精度（Precision）: 数値精度によって制御される。倍精度インデックスは 0.89–1.00 の精度を達成し、単精度は粗いフィルタとして機能する。
• 効率性: 2D空間における10万ポジションへの総当たり近傍探索は、1クエリあたり約0.9 ms で完了する。
• デコーディング: マッチしたベクトルから、マッチしたコンテキストを後方に向かってデコードする。

意義と主張

本論文は、以下の3つの主要な貢献を主張しており、これによってコードブックの幾何学やベクトル・ストレージ・エンジンに焦点を当てた同時期の研究（例：FibQuant, RetroInfer）と差別化を図っている：

1. 統一されたアーカイブ形式: 収縮反復写像符号を、損失のないストア、ランダムアクセス可能なデコーダ、そしてインプレース検索インデックスを同時に備えた実用的なKVアーカイブとして位置づけている。この、ストレージと検索を単一の表現の中に統合したことが、新規の貢献として提示されている。
2. 量子化に関する洞察: Key/Valueの非対称性を具体的なパープレキシティ・予算として定量化し、ビット非対称なハイブリッド・スキーム（Keysに4倍のビット、Valuesに2倍のビット）が、長文脈圧縮における最適解であることを示した。
3. 検索可能なメモリ: アーカイブがサフィックス・マッチングを直接サポートしていることを示し、フルキャッシュを実体化することなく、モデルが関連する過去のコンテキストを特定できる「検索拡張型デコーディング」を可能にした。

著者による限界の承認

• スケール: 実験はGPT-2 (124M) および単一の1024トークン・コンテキストに限定されている。より大きなモデルでの結果は未検証である（ただし、量子化に対してより寛容である可能性が高い）。
• コードブックの学習: コードブックはコーパスごとに学習されており、データ間で償却（共通化）されていない。
• 検索の範囲: 検索は厳密にはシーケンス構造のマッチング（サフィックス）であり、埋め込み（embedding）に基づく意味的な検索ではない。
• 圧縮率: フラクタル・コーデックの生の圧縮率は標準的なバイトパッカーと同程度である。その利点は、純粋なサイズ削減ではなく、アクセスパターン（ランダムアクセスおよび検索）にある。
• ベンチマーク: 本論文は、特定のコードブック設計に対するベンチマークを行っておらず、これらの量子化手法をこのストレージ形式と組み合わせることが今後の課題であるとしている。