技術的概要：自己回帰言語モデルにおける多項式コンテキスト切り捨て感度

1. 問題定義

本論文は、自己回帰言語モデル（LLM）におけるオンライン KV（キー・バリュー）キャッシュ圧縮の理論的限界に取り組む。コンテキスト長が増大するにつれ、KV キャッシュの線形な増大が推論における主要なボトルネックとなる。数多くの経験的圧縮方式（例：ヘビーハッターの排除、スライディングウィンドウ、アテンションシンク、量子化）が存在するが、オンライン圧縮問題に対して達成可能なものに関する定量的な理論的限界は欠如している。

核心的な問いは以下の通りである：コンテキストを圧縮する際、次のトークン分布において特定の歪みレベル（精度）を維持するために必要なメモリ（ウィンドウサイズ）はどれほどか？

古典的な情報理論はしばしば幾何学的混合（または $\rho$-混合）を仮定する。これは、遠い過去のトークンの影響が指数関数的に減衰する（$C\rho^w$）というものである。この仮定の下では、$\epsilon$-精度に対して $O(\log(1/\epsilon))$ のウィンドウサイズで十分である。しかし、この仮定は言語モデリングの設定から導出されたものではなく、訓練された LLM に対しては成り立たない可能性がある。

2. 手法と枠組み

2.1 逐次ワイナー・ジヴ定式化

著者らは、KV キャッシュ圧縮を逐次ワイナー・ジヴ源符号化問題として定式化する。

• 情報源: モデルによって生成されたトークンの系列 $X_{1:t-1}$。
• 符号器: 過去のトークンを圧縮符号 $\hat{C}_t$ に写像する因果的なオンライン符号器 $\phi_t$。
• 復号器側の側情報: 圧縮されていないモデルによって計算された次のステップのクエリベクトル $Q_t$ が、復号器における側情報として機能する。
• 目的: 与えられたレートに対して、期待 KL 発散 $E[D_{KL}(p_t \| \tilde{p}_t)]$ を最小化するように、$(\hat{C}_{\le t}, Q_t)$ から次のトークン分布 $\tilde{p}_t$ を再構成すること。

2.2 切り捨て感度の経験的characterization

幾何学的混合を仮定する代わりに、著者らは訓練されたモデルの切り捨て感度を経験的に測定する。感度 $d_{TV}^w$ を、完全コンテキストの次のトークン分布と、最も最近の $w$ トークンのみで条件付けられた分布との間の総変動（TV）距離として定義する：
$$d_{TV}^w := TV(p_\theta(\cdot | X_{1:t-1}), p_\theta(\cdot | X_{t-w:t-1}))$$

主要な経験的発見: 4 つのモデル（Qwen2.5-0.5B/1.5B/3B、SmolLM2-1.7B）と 2 つのドメイン（自然言語、コード）において、$d_{TV}^w$ の減衰は指数関数的減衰ではなくべき乗則に従うことが確認された：
$$d_{TV}^w \propto w^{-\alpha}$$

• 測定された指数：$\alpha_{\text{nat}} \approx 0.44$（自然言語）および $\alpha_{\text{code}} \approx 0.38$（コード）。
• べき乗則の適合は、外挿において指数関数的適合を大幅に上回る（log-RMSE の改善が 2–2.5$\times$）。
• この性質は、位置を保持するアブレーションを通じて、位置符号化のアーティファクトから自由であることが検証された。

3. 主要な貢献と理論的結果

$\alpha$-多項式切り捨て感度という経験的観察に基づき、本論文は以下の核心的結果を持つ情報理論的枠組みを開発する。

C1: 逐次ワイナー・ジヴの逆定理（下限）

著者らは、目標歪み $D$ を達成するために必要なレートに関する基本的な下限を確立する。任意の因果的オンライン方式に対して：
$$\liminf_{n \to \infty} E[R_n] \ge R^\star(D)$$
この限界は、特定の混合条件を仮定することなく、逐次ワイナー・ジヴ問題の構造のみに依存して成り立つ。

C2: 接尾辞のみの方針に対するウィンドウスケーリング

本論文は、接尾辞のみの方針（再構成が最も最近の $w$ トークンのみに依存する方式、例：スライディングウィンドウ）のメモリ要件を特徴づける。

• 上限: スライディングウィンドウ方式は、ウィンドウサイズ $w = O(\epsilon^{-1/\alpha})$ で TV 歪み $\epsilon$ を達成する。
• 下限（逆定理）: 追加の「両側ベイズリスク」条件（定義 4.4）の下では、任意の接尾辞のみの方針は $w = \Omega(\epsilon^{-1/\alpha})$ を必要とする。
• 結果: 接尾辞のみの方針におけるトークンあたりのメモリ要件は tight である：$\Theta(\epsilon^{-1/\alpha})$。
  • 幾何学的混合との対比: 幾何学的混合の下では、$w = O(\log(1/\epsilon))$ となる。$\alpha \approx 0.5$ の場合、ウィンドウサイズは多項式的にスケーリングする（例：$\epsilon=0.01$ に対して $w \sim 10^2$）。これは、展開された方式が幾何学的混合が予測するよりもはるかに大きなウィンドウを必要とする理由を説明する。

C3: 明示的な達成可能性方式

著者らは、理論的限界を達成する明示的なブロックマルコフランダム符号化方式を提案する。

• ウィンドウサイズ: $w_n = \lceil n^{1/(\alpha+1)} \rceil$。
• 収束: この方式は、目標からの歪みを $O(n^{-\alpha/(\alpha+1)})$ の範囲で達成する。
• レート収束:
  • 期待値において、レートは指数 $\alpha/(\alpha+1)$ で収束する。
  • 高確率において、追加の仮定なしに指数は $\alpha/(2(\alpha+1))$ となる。
  • 追加の仮定（前方共分散減衰、加法的傾斜情報）の下では、高確率の指数は逆定理と一致する（$\alpha/(\alpha+1)$）。

C4: シンク＋最近トークン排除の帰結

本論文は、人気のある「シンク＋最近トークン」排除戦略（アテンションシンク＋最近のトークンを保持する）を分析する。

• 結果: $\alpha$-多項式感度の下では、KL 歪みギャップは $O(k^{-2\alpha})$ として減衰する。ここで $k$ は予算である。
• メカニズム: 指数の倍増（$\alpha$ ではなく $2\alpha$）は、有界フロア領域における KL 発散と TV 距離の間の局所的な二次関係（$KL \le C \cdot TV^2$）に起因するものであり、ピンカースの不等式によるものではない。
• 経験的検証: 測定された KL 指数（自然言語で $\alpha_{KL} \approx 1.04$、コードで $0.74$）は、TV 指数（それぞれ $0.44$と$0.38$）の約 2 倍であり、理論的予測を確認している。

4. 経験的結果

本論文は、Qwen2.5（0.5B、1.5B、3B）および SmolLM2（1.7B）上で枠組みを検証する。

1. 多項式減衰: 全モデルおよび全ドメインにおいて、TV 減衰に対するべき乗則の適合は、指数関数的適合を上回る。
2. 指数の一貫性: 比 $\alpha_{KL} / \alpha_{TV}$ は、予測された因子 2 を一貫して囲む（観測された比：1.93 から 2.38）。
3. 方針の劣化: 最近性に基づく方針（スライディングウィンドウ、シンク＋最近トークン）は、等しい予算におけるランダムなトークン保持と比較して、歪みを約2 桁抑制する。
4. ドメインの違い: 自然言語はコード（$\alpha \approx 0.38$）よりも速い切り捨て感度の減衰（$\alpha \approx 0.44$）を示し、コードはスコープやインポートなどの長距離構造的依存関係をより強く保持することを示唆している。
5. 頑健性: べき乗則は、典型的な 4k の展開範囲を遥かに超えるウィンドウサイズ $w=8192$ まで成立し、位置符号化のアーティファクトに対して頑健である。

5. 意義と主張

本論文は、以下の意義を主張する。

• 理論的基盤: 検証されていない幾何学的混合仮定に代わり、LLM の経験的に観測された多項式切り捨て感度に基づいた、KV キャッシュ圧縮に対する初の定量的レート歪み特徴付けを提供する。
• 経験的実践の説明: 多項式スケーリング則（$\Theta(\epsilon^{-1/\alpha})$）は、展開されたシステム（例：$w=4096$ の Mistral や StreamingLLM）が、幾何学的混合が示唆するよりもはるかに大きなウィンドウを必要とする理由を説明する。
• 接尾辞のみの方針の最適性: 接尾辞のみの方針のクラスに対して、メモリスケーリングが tight であることを確立する。より複雑な再帰的または伝播要約がこのスケーリングを上回るかどうかは、未解決の問題である。
• 「シンク＋最近」の検証: シンク＋最近排除のパフォーマンスに対する理論的根拠を提供し、観測された $k^{-2\alpha}$ 減衰を、基礎となる多項式感度および局所的な二次 KL-TV 関係と結びつける。

著者らが認める限界:

• 計算制約により、分析はパラメータ数 3B 以下のモデルに限定されており、より大きなモデル（7B–8B）は将来の課題として残されている。
• tight な高確率限界に必要な「両側ベイズリスク」条件および前方減衰仮説は、切り捨て感度のみからは導かれないため、追加の仮定として扱われる。
• 枠組みは標準的なトランスフォーマーアーキテクチャを仮定しており、状態空間モデル（例：Mamba）は分析されていない。
• 本論文は、指数 $\alpha$ をアーキテクチャパラメータから導出するものではなく、経験的に測定するものとは主張していない。

要約すると、本論文は、多項式コンテキスト切り捨て感度が訓練された LLM の根本的な性質であり、メモリとレートのトレードオフを決定づけるものであると論じている。これにより、高精度な圧縮には多項式的にスケーリングするウィンドウが必要となり、最近性に基づく排除戦略の有効性に対する理論的基盤が提供される。