技術概要：CachePrune

問題定義

大規模言語モデル（LLM）は、推論を高速化するためにキー・バリュー（KV）キャッシュに依存しており、現代のサービングシステムは、冗長な計算とメモリ使用量を削減するため、異なるユーザー間で KV キャッシュを共有することが多い。しかし、制限のないユーザー間共有は、重大なサイドチャネル脆弱性を引き起こす。攻撃者は特定のトークン系列でシステムをプローブすることができ、システムがキャッシュされた KV エントリを再利用した場合（遅延の減少やスケジューリングの優先度を通じて検出可能）、攻撃者は被害者のプロンプトにそれらのトークンが存在することを推測でき、潜在的に機密入力情報を再構築できる。

現在の防御策は、漏洩を防ぐためにユーザー間共有を完全に無効化するのが一般的である。この「すべてか無か」のアプローチは、過度に粗粒度である。実際には、ユーザープロンプトには、システム指示、公開テンプレート、RAG パイプライン内の検索された文章など、プライバシーと無関係な内容が大量に含まれており、機密トークン（PII など）は通常、入力全体の微小な割合（例：ユーザー入力の約 2.3%）を占める。共有をすべて無効化することは、大幅な効率向上の機会を犠牲にする。さらに、既存の細粒度共有メカニズム（CacheBlend、CacheCraft など）は、固定されたチャンクレベル（例：512 トークン）で動作する。単一の機密トークンがチャンク内に含まれる場合、そのチャンク全体を破棄しなければならないため、再利用可能なコンテンツの大幅な損失を招く。

手法：CachePrune

著者は、非機密 KV エントリの微細粒度、トークンレベルの再利用を可能にするプライバシー意識型の KV キャッシュ共有メカニズムであるCachePruneを提案する。このシステムは、プライバシーと無関係なセグメントのみを選択的に共有することで、プライバシーと効率性の間のトレードオフを打破するように設計されている。

システムアーキテクチャ

CachePrune は、vLLM などの既存フレームワークの上に 5 つのコアコンポーネントを統合する：

1. 感度検出器（Sensitivity Detector）: プラグ可能なインターフェース（ユーザー定義ルール、正規表現、Presidio などの分類器をサポート）であり、プロンプト内の機密トークンを識別し、二値の感度マスクを生成する。
2. KV アノテータ（KV Annotator）: 推論後に、このモジュールはアテンションスコア行列を分析し、非機密トークンから再利用可能なセグメントを導き出す。内部アテンションが外部アテンションを上回る「自己文脈化された」セグメントを特定する。
3. KV 検索器（KV Retriever）: 応答を生成する前に、このモジュールはローリングハッシュベースのアルゴリズムを使用して、受信したリクエストの非機密トークンに一致するセグメントを KV プール内で検索する。
4. LLM エンジン: 生成品質を維持するために、欠落した KV エントリを計算し、再利用されたセグメント内の特定のトークンを再計算することで、推論を完了する。
5. KV プール: 再利用可能な KV セグメントを格納・インデックス化し、そのライフサイクルとエビクションを管理する。

主要なアルゴリズム的解決策

このシステムは、2 つの主要な課題に対処する：

1. 再利用可能な KV セグメントの効率的な導出（課題 1）

• 問題: トークンレベルでの再利用性を決定するには、任意の部分文字列に対してアテンション依存関係を評価する必要がある。アテンション行列に対してすべての部分文字列をチェックする単純なアプローチは、$O(n^4)$ の計算複雑性をもたらし、実行不可能である。
• 解決策: CachePrune は、アテンションスコア行列に対して**総和面積テーブル（積分画像）**アルゴリズムを採用する。これにより、$O(n^2)$ の前処理ステップの後、任意の候補部分文字列に対する内部アテンションと外部アテンションの合計を $O(1)$ の時間で計算できる。これにより、最適な再利用可能セグメントを見つける全体の計算複雑性が $O(n^2)$ に削減される。
• 再計算戦略: 再利用可能なセグメント内では、高い外部アテンション（外部文脈への依存）を持つトークンは、出力品質を維持するために再計算のためにマークされる。

2. 可変長セグメントの効率的な検索（課題 2）

• 問題: 固定サイズのチャンクとは異なり、トークンレベルの共有は可変長のセグメントを生成する。単一トークンのシフトが整列を崩すため、直接ハッシュルックアップは失敗し、検索は単純な検索では $O(n \times m)$ の計算複雑性を持つ部分文字列包含問題となる。
• 解決策: システムはローリングハッシュベースの検索アルゴリズムを使用する。
  • プレフィックスフィルタリング: キャッシュされたセグメントの最初の 128 トークンのハッシュを事前に計算する。受信したリクエストはスライドウィンドウでスキャンされ、$O(n)$ の時間で潜在的な一致を検出する。
  • 完全検証: 候補は、トークンごとの比較なしに正確性を保証するために、高速なプレフィックスハッシュチェックに続いて、暗号学的ハッシュ（SHA-256）検証を受ける。

主要な貢献

1. 実用的な微細粒度共有システムの初例: CachePrune は、機密エントリをブロックしつつ非機密エントリを再利用することで、プライバシーと効率性のトレードオフを実質的に打破する、トークンレベルでの選択的 KV キャッシュ共有を可能にする最初のシステムである。
2. アルゴリズム的革新: 本論文は、効率的なセグメント導出のための総和面積テーブルを使用する適応型アルゴリズムと、可変長検索のためのローリングハッシュメカニズムを導入し、固定チャンクアプローチの限界を克服する。
3. 包括的な評価: 著者は vLLM 上で CachePrune を実装し、3 つのデータセット（QASPER、NarrativeQA、QMSum）と複数のモデル（Mistral-7B、Qwen2.5）で評価を行った。

結果

評価により、CachePrune はプライバシーや生成品質を損なうことなく、大幅な効率向上を達成することが示された：

• プライバシー:
  • 直接漏洩: 機密とマークされたトークンは、再利用ベースのサイドチャネルを通じて回復できない（正確な回復率 0%）。
  • 文脈的漏洩: 非機密トークンからの機密コンテンツの推測は限定的なままである（SOTA 攻撃下で、正確な回復率 2.2%、意味的回復率 6.4%）。
  • 不完全な検出: システムは検出エラーに対して堅牢である。偽陰性は直接漏洩を増加させるが、偽陽性は文脈的漏洩を保守的に減少させる。
• 効率性:
  • TTFT の削減: CachePrune は、共有なしのベースラインと比較して、最初のトークンまでの時間（TTFT）を最大4.5 倍削減する。
  • ヒット率: KV キャッシュの再利用率は最大**94.57%**に達する。
  • 微細粒度の利点: プライバシー制約がなくても、CachePrune のトークンレベル共有は、最先端の固定チャンク方式（CacheCraft、CacheBlend、EPIC）と比較して、キャッシュヒット率を**44%**向上させる。
• 品質: 生成品質（F1 スコアと ROUGE-L で測定）は、完全な再計算と比較して同等であり、無視できる程度の乖離しか見られない。

意義と主張

本論文は、CachePrune がマルチテナント環境における安全な LLM サービングのための実用的な基盤を提供すると主張している。固定サイズのチャンキングを超えて進むことで、システムプロンプトや公開データなどのプライバシーと無関係なコンテンツの再利用可能性を最大化しつつ、機密ユーザー入力を厳密に分離する。著者は、彼らのアプローチが新しいプライバシー検出メカニズムを必要とするのではなく、既存のメカニズムと統合して、安全かつ高性能な推論のための統一インターフェースを提供することを強調している。この研究は、微細粒度の KV 管理が単に実行可能であるだけでなく、現代の LLM インフラにおけるプライバシーと効率性の競合する要求のバランスを取るために不可欠であることを浮き彫りにしている。