🤖 machine learning

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches

本論文は、多キューアーキテクチャとオンライン学習を通じて異なるトークン種類の再利用価値のばらつきを活用し、手動パラメータ調整の必要性を排除しながら大規模言語モデルのサービング効率を大幅に向上させるセマンティック適応型プレフィックスキャッシュエビクションポリシーである SAECache を紹介する。

原著者： Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

公開日 2026-05-20

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたが毎日何百万人もの顧客にサービスを提供する、非常に忙しい高級コーヒーショップ（大規模言語モデル、または LLM）を運営していると想像してください。コーヒーを素早く淹れるために、すでに始めた注文の事前準備済みの材料と指示を保管する特別な「記憶の棚」（GPU メモリ）を持っています。これを「プレフィックスキャッシング」と呼びます。

新しい顧客が、以前の注文と 90% 同一のラテを注文した場合、新しい豆を挽いたり、新しい牛乳を蒸したりする必要はありません。棚から事前準備済みのベースを取り出すだけです。これにより、一口目（最初のトークン）がほぼ瞬時に表示されます。

しかし、あなたの棚は非常に小さく、すべての事前準備済みのベースを永久に保管することはできません。最終的には、新しい注文のスペースを作るために、いくつかのものを捨てなければなりません。これが「エビクションポリシー」です。

問題点：「万能型」の誤り

長らく、コーヒーショップの管理者は単純なルールを使用していました。「最も古いアイテムを最初に捨てる」というものです（これは LRU ポリシーです）。

この論文は、棚にあるすべてのアイテムが同等の価値を持つわけではないため、これは悪い考えであると主張しています。

システムプロンプト： すべての顧客が目にする「標準メニュー」を想像してください。それは決して変わりません。誰もがそれを注文するため、信じられないほど価値があります。
思考の連鎖： ラテをなぜ欲しいのかについての、ある顧客の散らかった内的な独白を想像してください。これはその一人の人物と、その瞬間に固有のものです。次の顧客にとって、ほとんど役に立つことはありません。

古いルールは、「標準メニュー」と「散らかった独白」を全く同じように扱いました。独白がメニューよりもわずかに新しい場合、古いルールは独言のためにメニューを捨てます。これは災害です。次の顧客はすぐにメニューを必要としますが、独言は彼らにとって無用だからです。

解決策：SAECache（賢い管理者）

著者たちは SAECache という新しいシステムを作成しました。これは、アイテムが最後に触れた「時期」だけでなく、アイテムが実際に「何か」を見る賢い管理者のようなものです。

これがどのように機能するか、簡単な比喩を使って説明します。

1. 4 つの専門的な箱（マルチキューアーキテクチャ）

1 つの大きな棚ではなく、SAECache は棚をそれぞれ独自のルールを持つ 4 つの明確な箱に整理します。

「ゴミ」箱： ほとんど再利用されないアイテム（散らかった独言や飲み物の最終工程など）を保持します。これらは最初に捨てられます。
「テンプレート」箱： 標準的な指示やシステムプロンプト（メニューなど）を保持します。これらは常に再利用されるため、非常に慎重に保管されます。
「チャット」箱： 人々が互いに話し合う会話を保持します。
「エージェント」箱： AI が作業（コーディングやツールの使用など）を行っている複雑なタスクを保持します。

2. 「価値スコア」（意味認識重み付け）

管理者は、どの箱が重要かを推測するだけではありません。学習します！

もし管理者が「システムプロンプト」を捨て、すぐに再びそれを求められた場合、システムは学習します。「おっと！価値のあるものを捨ててしまった。次はシステムプロンプトに高いスコアを与えるべきだ。」
もし「思考の連鎖」を捨て、誰もそれを求めない場合、学習します。「よくやった！あれはゴミだった。これからも低いスコアを与え続けるだろう。」

これは、人間が何をすべきかを指示する必要なく、管理者が顧客が実際に購入するものに基づいて棚を調整するのと同じように、自動的に起こります。

3. 「タイムマシン」（適応的タイミング）

システムは、人々がいつ戻ってくるかも学習します。

チャットセッションは、長い休憩（顧客がコーヒーブレイクを取るようなもの）があるかもしれません。
エージェントセッションは、非常に速く、慌ただしいかもしれません。
システムは、各タイプのセッションの特定の「鼓動」を学習します。チャットセッションが 10 分間戻ってこない場合、おそらく永久に去ったことを知っています。しかし、エージェントセッションが 10 秒間戻ってこない場合、単に考えているだけかもしれません。システムは、交通のリズムに合わせて、エビクションルールをリアルタイムで調整します。

結果：より速いコーヒー、より少ない無駄

この論文は、この新しい管理者を、古い「最も古いもの優先」ルールや、他の賢いけれど硬直したシステムと比較してテストしました。

速度： 新しいシステムは、混雑した混合環境において、コーヒーの一口目を 1.4 倍から 2.7 倍 速く表示しました。
適応性： 古いシステムは、顧客の種類が変化したとき（例えば、おしゃべりする顧客ではなく、単一注文の顧客が急増した場合など）に破綻しました。新しいシステムは即座に適応しました。
効率性： 無駄なものを（散らかった独言など）溜め込まず、価値のあるもの（メニューなど）を安全に保つことで、「無駄な」メモリを大量に節約しました。

まとめ

要約すると、この論文はこう述べています。すべてのメモリブロックを同じように扱わないでください。 2 つのものが同じタイミングで触れられたからといって、それらが同等に有用であるとは限りません。コンピュータにデータの「意味」（これはメニューか？これは冗談か？これはツールか？）を理解させ、リアルタイムで自らの間違いから学習させることで、AI をはるかに高速かつ効率的にすることができます。

技術概要：SAECache – LLM プリフィックスキャッシュのための意味意識型エビクション

問題定義

大規模言語モデル（LLM）におけるプリフィックスキャッシュは、入力プリフィックスを共有するリクエストからキー・バリュー（KV）状態を再利用することで、推論レイテンシ（特に最初のトークンまでの時間、TTFT）を削減することを目的としています。しかし、プリフィックスキャッシュの有効性は、限られた GPU メモリによって厳しく制約されており、容量が満杯になった際に価値の低いブロックを破棄するためのエビクションポリシーが必要となります。

既存のエビクションポリシー（Least Recently Used: LRU や Least Frequently Used: LFU など）は、主にアクセス時刻や頻度の統計情報に依存しています。これらのトークン非依存のアプローチは、すべてのキャッシュされたブロックを均一に扱い、LLM ワークロードの 2 つの重要な次元を無視しています：

意味的異質性：異なるトークンタイプ（例：システムプロンプト対チェーン・オブ・スレッド推論）は、本質的な再利用率において著しく異なります。
ワークロードの変動性：再利用パターンは、単一ターンテンプレート付きリクエスト（構造的再利用）とマルチターン会話（セッションローカルな時間的再利用）の間で大きく異なり、ターン間隔は異なるアプリケーションタイプ（例：チャット対エージェントワークフロー）において固有の分布に従います。

著者らは、再発性が一致する場合でも、高価値のシステムプロンプトブロックと低価値のチェーン・オブ・スレッドブロックを同等に扱うことが、メモリ割り当ての最適化を阻害することを観察しました。さらに、固定パラメータのポリシーはワークロード構成が変化した際に失敗し、ワークロードの不一致により最大 2.7 倍のパフォーマンス低下を引き起こします。

手法：SAECache

これらの限界に対処するため、著者らはプリフィックスキャッシュのための意味適応型エビクションであるSAECacheを提案します。これは、トークンの意味構造とオンラインワークロード適応を統合するポリシーです。このシステムは、以下の 3 つの中核メカニズムを通じて動作します。

1. ルールベースのルーティングを備えたマルチキューアーキテクチャ

SAECache は、単一のグローバルキューではなく、支配的な再利用パターンに基づいて KV ブロックを 4 つの異なるキューにルーティングします：

Evict-First Queue（優先エビクションキュー）：デコードフェーズのトークンや再利用可能性の低いテンプレートなしのプリフィルブロックなど、低価値のブロックを格納します。これらは最初に排出されます。
Structural Queue（構造的キュー）：共有プロンプト構造（例：ツール使用テンプレート、プログラミング指示）に依存する単一ターンセッションからの KV ブロックを格納します。
Chat Queue（チャットキュー）：会話セッションからのマルチターンブロックを格納し、セッションローカルな時間的再利用をモデル化します。
Agentic Queue（エージェントキュー）：標準的なチャットとは異なるトークン内容とリクエスト間隔分布を示す、エージェント/ツール使用セッションからのマルチターンブロックを格納します。

軽量なマルチターンセッション予測器（サービングモデルの最終隠れ状態を再利用する 3 層 MLP）は、セッションの最初のリクエストの曖昧さを解決し、継続が予測される場合は適切なマルチターンキューへ、そうでない場合は構造的キューまたは Evict-First キューへルーティングします。

2. ローカル優先度スコアリング

各キュー内では、ブロックが複合指標 $P(b)$ に基づいてエビクションのスコア付けを受けます：
$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$

$\alpha_q$ （キュー重み）：特定キューの最近のヒット効率を反映する動的な重み。
$w_{\tau(b)}$ （トークンタイプ重み）：ブロックのトークンタイプ（例：システムプロンプト、ユーザークエリ、チェーン・オブ・スレッド）に固有の学習済み重み。
$p_q(b)$ （ローカル生存確率）：
- Chat/Agentic キューの場合：そのセッションタイプのターン間隔に適合させた対数正規分布の下での生存確率 $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ として計算されます。
- Structural キューの場合： $1 - (o_b / o_{max})^\gamma$ として計算されます。ここで、 $o_b$ はブロックオフセット、 $\gamma$ は学習済み減衰冪であり、プロンプトの初期ブロックを優先します。
$\Delta t_b$ ：ブロックの最終アクセスから経過した時間。

3. 完全適応型オンライン学習

SAECache は、キャッシュヒット/ミス統計に基づく統一的なフィードバックループを介してすべてのパラメータをオンラインで更新することで、手動チューニングを排除します：

トークンタイプ重み：「エビクション後のミス」率と全体のヒット率に基づき、指数移動平均（EMA）で更新されます。
対数正規パラメータ（ $\mu, \sigma$ ）：チャットおよびエージェントキューの観測されたアクセス間隔に対して最大尤度推定（MLE）を用いてオンライン推定されます。
位置減衰冪（ $\gamma$ ）：構造的キューにおけるブロック位置とヒット率の相関から学習されます。
キュー重み（ $\alpha_q$ ）：各キューのヒットトークン数と割り当てられた容量の比率に基づき、温度パラメータでスケーリングされて更新されます。

主な貢献

実証的特徴付け：トークンタイプ間（システムプロンプトで 92.3% 対チェーン・オブ・スレッドで 2.2%）でトークン再利用が最大 756 倍変動すること、およびターン間隔が単純な指数減衰ではなくセッション固有の対数正規分布に従うことを明らかにする体系的な研究。
SAECache ポリシー：異質な再利用メカニズム（構造的対時間的）を分離し、トークンタイプに固有の優先度を割り当てる、意味意識型のマルチキューエビクションポリシー。
オンライン適応：手動介入なしでタイミング分布、位置減衰、重み付けパラメータを自動的に調整し、変化するワークロード構成に適応する学習フレームワーク。
包括的評価：実世界のデータセット（ShareGPT、LMSys、Chatbot-Arena）における広範な実験により、異質なワークロード全体での堅牢性を実証。

実験結果

NVIDIA A40 GPU 上の Qwen2.5-1.5B-Instruct を用いた vLLM 実装で評価され、SAECache は LRU（生産環境のベースライン）および Learned Prefix Caching（LPC）と比較されました。

TTFT の改善：SAECache は、異質なワークロード全体で、生産環境スタイルのベースラインに対してTTFT を 1.4 倍から 2.7 倍改善しました。
キャッシュヒット率：SAECache は一貫して最高のキャッシュヒット率を達成し、すべてのテスト構成において最も強力なベースライン（LRU または LPC）に対して4.8～5.9 パーセントポイント改善しました。
ワークロード不一致への耐性：固定パラメータの代替案は、ワークロード構成がトレーニング痕跡から逸脱した場合、TTFT が最大2.7 倍劣化しました。SAECache はパラメータをオンラインで適応させることで、安定したパフォーマンスを維持しました。
アブレーション研究：
- トークンタイプ意識型重み付けは、追加で**23%**の改善に寄与しました。
- 適応型キュー重み付けは、**39%**という最大の改善をもたらしました。
- 対数正規タイミングと位置減衰学習は、それぞれ追加で 14% と 12% の改善を提供しました。
オーバーヘッド：マルチターンセッション予測器は非常に効率的で、パラメータ数が約 100 万（LPC の埋め込みモデルは 1 億 1800 万）のみであり、推論スループットは 8.8 倍高いです。

意義と主張

本論文は、プリフィックスキャッシュのエビクションは、再発性や頻度統計が類似している場合でも、すべてのキャッシュされたブロックを均一に扱うべきではないと主張しています。著者らは、トークンの意味、プロンプト構造、セッションタイプが、既存のポリシーが捉え損なう再利用の根本的な駆動因子であると述べています。

SAECache の意義は、以下の点にあります：

静的ヒューリスティックポリシーと、LLM サービングの動的で意味的な現実との間のギャップを埋めること。
手動チューニングを排除し、再トレーニングやパラメータ調整なしでワークロードのシフト（例：チャット中心からツール使用中心へのトラフィック）に対してシステムを堅牢にすること。
高粒度で意味意識型のエビクションが、特に高いキャッシュ圧力と異質なリクエストパターンを有する環境において、効率的な LLM サービングのための重要な設計選択であることを実証すること。

著者らは、SAECache がマルチターンおよび混合ワークロードで優れている一方で、そのオーバーヘッドは、高いヒット率の恩恵が管理コストを完全に相殺しない単一ターン中心の領域（例：Chatbot-Arena）ではパフォーマンスをわずかに低下させる可能性があると指摘しています。これは、ワークロード特性に合わせてスケーリングできる適応型戦略の必要性を浮き彫りにしています。