LRUはKVキャッシュの論文が示唆するよりも打ち負かすのが難しい

LRUはKVキャッシュの論文が示唆するよりも打ち負かすのが難しい

私は68,266件のリクエスト（393件の実際のClaude Codeセッション）と23,608件のMooncakeリクエストをプレフィックスキャッシュシミュレータで再生し、プロダクションベースラインを3つの異なる方法で打ち負かそうとしましたが、失敗しました。興味深いのはその理由です。容量のプレッシャー下では、ほとんどの再計算はTTL（Time To Live）を過ぎたセッションのアイドル状態からではなく、数秒間隔のツール呼び出しループから発生しており、TTLは一度も発火しませんでした。

ここにあるすべては、make setup data reproでコールドチェックアウトから再現可能です。

---

目次

• 私が構築したもの
• 検証：Mooncakeの公開カーブの再現
• 1. エージェントセッションは公開されているよりもアイドル状態が多い
• 2. 容量のプレッシャー下では、無駄は予想していた場所にはない
• 3. 5分間のTTLは容量のプレッシャー下で一度も発火しなかった
• 4. LRUを打ち負かす3つの方法、3つの失敗
• 5. BeladyをLRUに負けさせるハーネスバグ
• これが意味すること
• 制限事項
• 再現方法

---

クロスリクエストKVプレフィックスキャッシュは、エージェントLLMサービングにおいて最も実用的なレバーです。それが、あなたのコーディングエージェントの50回目のターンが最初のターンのわずかなコストで済む理由です。すべてのサービングスタックにはそれがあり、vLLMの自動プレフィックスキャッシュ、SGLangのRadixAttention、LMCache、Mooncake Storeなどがありますが、それらはすべてデフォルトでLRUでエビクトします。（SGLangは--radix-eviction-policyの背後でLFU、SLRU、Priorityなども提供していますが、LRUがデフォルトで出荷されています。）

LRUがエージェントワークロードにとって間違ったポリシーであると主張する、大規模で急速に成長している文献があります。なぜなら、エージェントセッションはアイドル状態になり、LRUは一時停止したセッションとデッドなセッションを区別できないからです。この議論は直感的です。私もそれを信じ、それを悪用するためのシミュレータを構築しました。

それは機能しませんでした。そして、それが機能しなかった理由は、ポリシーそのものよりも興味深いことが判明しました。

私が構築したもの

ブロック粒度の離散イベントシミュレータで、クロスリクエストプレフィックスキャッシュを扱います。重要な3つのプロパティがあり、迅速な実装ではしばしば誤解されがちです。

ヒットはプレフィックス連続であること。 ヒットとは、ブロックチェーンの最も長く存在するプレフィックスであり、セットの共通部分ではありません。深さ3で1つのブロックをミスすると、それがまだ存在していても、それ以降のすべてが使用不能になります。

ラディックス構造がエビクションを制約する。 存在する子を持つブロックはエビクトできません。したがって、ベースラインはラディックスリーフ上のLRUであり、SGLangとvLLMが実際に実装しているものです。単純なフラットLRUを打ち負かすことは、ストローマン（弱い議論）になるでしょう。

インフライトチェーンはピン留めされる必要がある。 発見5を参照してください。

トレースは合成ではなく、実際のものであることを示します。

検証：Mooncakeの公開カーブの再現

何も信頼する前に、Mooncake自身の公開トレースと、彼らが述べたポリシーを使用して、Mooncakeの公開ヒット率対容量テーブルを再現しました。

形状は、彼らが文章で説明している飽和点（「1,000から50,000ブロックでキャッシュヒット率が30%から50%に向上します。それ以上の容量増加はわずかな改善しか示しません」）を含め、正確に再現されました。

説明できなかった体系的な+4〜6ppのオフセットがあります。 5つのメトリック定義（ブロック分母、トークン分母、部分的な末尾ブロックの削除、リクエストごとの平均）をテストしましたが、どれもそれを説明できませんでした。無限キャッシュケースはポリシーフリーで、トレースの純粋なプロパティであるため、不一致は定義上の問題か、トレースバージョンの不一致であり、再生バグではありません。

解決しないまま公開します。理由をご存知の方は、イシューを開いてください。

付随的な発見： このワークロードでは、フラットブロックLRUとラディックスリーフ制限LRUの違いは0.02ppです。主要な両エンジンが実装しているリーフ制限は、ここでは実質的に何も購入しません。

再現：make validate

1. エージェントセッションは公開されているよりもアイドル状態が多い

sessions=393  requests=68266

session span (h):   p50=1.84  p90=28.36  max=254.8
inter-req gap (s):  p50=2.1   p90=51.1   p99=3426.3   max=491922   (5.7 days)
   gaps >   60s: 9.5%
   gaps >  300s: 3.3%
   gaps > 3600s: 1.0%
input tokens:       p50=88768  p90=204288  max=255808
output tokens:      p50=376    p90=1845
requests/session:   p50=70     max=3551

DUTY CYCLE (fraction of wall-clock actually executing):
   p25=3.4%   p50=13.9%   p75=33.9%
   sessions executing <50% of lifetime: 85.5%

エージェントサービングで最も引用される特徴は、中央値20%のデューティサイクルと、50%未満で実行されるセッションが70%であると報告しています。この独立したトレースでは、それは13.9%と85.5%であり、前提は少ないどころか、より極端です。

形状に注意してください：ギャップは二峰性です。中央値2.1秒（タイトなツールループ）と、数日間に及ぶヘビーテールがあります。

再現：make characterize

2. 容量のプレッシャー下では、無駄は予想していた場所にはない

これが私の考えを変えた発見です。

AgentSysBench (arXiv:2608.15127) は、「キャッシュエビクションが総キャッシュ作成トークンの55.9%を占め、総金銭的コストの31.5%を占めている」と報告しており、これは5分間のプロバイダーTTLと1〜10分間のアイドルギャップの衝突によって引き起こされています。それが私の全体的なアプローチの動機となりました。

そこで、それを最適化する前に、再計算がどこから来るかを測定しました。これはポリシーに依存しません。トレースを再生し、各リクエストの再計算トークンを、その前にあったアイドルギャップでバケット分けします。

5分を超えるギャップの後に到着するリクエストは、再計算の17.5%を占めます。10秒以内に到着するリクエストは、33.1%を占めます。

キャッシュミスの主な原因は、キャッシュ容量を超える88kトークンのワーキングセットを持つ、タイトな2秒間のツールループであり、これは容量の問題であり、ライブネス予測の問題ではありません。中央値ギャップが2.1秒であるため、ほとんどすべてのセッションが「すぐに戻ってくる」状態であり、ライブネス推定器は区別するものがほとんどありません。

⚠️ これは31.5%の数値を矛盾するものではありません — どちらかを引用する前に読んでください

この2つの数値は異なるものを異なるレジームで測定しており、私は当初これを矛盾として提示しました。しかし、そうではありません。

	AgentSysBench	このリポジトリ
被 numerator	エビクションによって引き起こされたキャッシュ作成トークン（6.25ドル/Mで価格設定）	5分を超えるギャップの後に再計算されたプリフィルドトークン
分母	総請求額（キャッシュ読み取りと出力トークンを含む）	全再計算トークン
レジーム	TTLバウンド — 各顧客の容量が実質的に無制限で、エントリがタイマーで期限切れになるプロバイダーキャッシュ	容量バウンド — 約1070万トークンのワーキングセットに対する40,000ブロック

TTLバウンドキャッシュでは、構築により、ほぼすべてのエビクションがギャップ駆動です。私のセットアップは決してそのレジームに入りません — これは発見3が直接示しているように、TTL-300sはすべての実行でLRU-leafとバイト単位で同一でした。

両方の結果は完全に正しい可能性があります。 ここでの主張はより狭く、それは次のとおりです。容量がバインドするとき、それはTTLを支配し、それが引き起こす再計算はアイドルセッションのストーリーとは似ていません。 キャッシュ容量をプロビジョニングしている場合、最適化するものが変わります。プロバイダーTTLについて推論している場合、31.5%の数値が関連性があり、これではありません。

再現：make gap

3. 5分間のTTLは容量のプレッシャー下で一度も発火しなかった

TTL-300sは、すべての実行でLRU-leafとバイト単位で同一の結果を生成しました。

LRUは常にタイマーが満了する前にエビクトしたため、テストしたどのキャッシュサイズでもTTLが制約条件になることはありませんでした。これはまた、これらの実行がプロバイダーキャッシュが動作するTTLバウンドレジームではなく、容量バウンドレジームにあることの最も明確な証拠です。

4. LRUを打ち負かす3つの方法、3つの失敗

3つの分離可能で独立して削除可能なコンポーネントを持つポリシーを実装しました。

• H — ハザードベースのP(セッションが戻る)で、新しさを置き換えます。観測されたターン間ギャップと継続率に基づくオンラインベイズ推定器。オラクルなし：完了した観測のみを参照します。
• C — 物理的にモデル化された再計算コスト。位置iでのプリフィルコストは、線形項とiに比例するアテンション項の合計であり、100kトークンチェーンの末尾を再計算することは、見た目よりもバイトあたりのコストがはるかに高くなります。
• G — 一貫したセッション単位のエビクション。グローバルで最も古いN個のリーフ（50個の異なるチェーンを切り取る可能性がある）を取る代わりに、1つのセッションのプライベートテールを犠牲にします。

ヒット率、40件のAgentXセッション、4,751件のリクエスト：

LRU-leafに対する実効再計算コスト（マイナスは悪い）:

単調にマイナス。すべてのコンポーネントが悪化させ、私が最も確信していた（一貫したエビクション）が最悪でした。

発見2を考慮すると、これはまさに起こるべきことでした。私は17.5%の無駄を運ぶ信号を最適化しようとしており、中央値ギャップ2.1秒で区別できない予測子を使用していました。

再現：make ablation

5. BeladyをLRUに負けさせるハーネスバグ

最初の実行では、Belady（オフラインオラクル）がLRUに負けました。これは結果ではなく、壊れたハーネスであり、一般的であると予想されるため、公開する価値があります。

原因：ほぼ満杯のキャッシュに長いチェーンを挿入すると、ポリシーが現在構築中のプレフィックス自体をエビクトすることができます。LRUは、挿入されたばかりのブロックが最新のタイムスタンプを持つため、偶然にも免除されます。LRU以外のすべてのポリシーは自己破壊します。実際のエンジンは参照カウントピンでこれを防ぎますが、ゼロから構築されたシミュレータは通常そうしません。

これらのうちの1つを構築する場合、最初のテストを「BeladyはLRUに勝つか？」にしてください。勝たない場合、このバグがあり、実行するすべてのポリシー比較は、LRUに有利に静かに間違ったものになります。

他の2つの実装ノート：

• 最も深いヒットブロックのみがリーフになる可能性があるため、touch()は1つのブロックのみを更新すればよい。O(チェーン長)のウォークはO(1)になります — AgentXの中央値1,387ブロックでは重要です。
• キャッシュ全体をスキャンするのではなく、k個の最も最近使用されていないリーフをサンプリングしてエビクション候補をスコアリングします。これはプロダクションキャッシュが実際に行っていることなので、近道ではなく現実的です。

これが意味すること

どの制約がバインドされるかによって、何を最適化すべきかが決まり、2つのレジームは反対のものを要求します。 キャッシュがTTLバウンドの場合、ライブネス予測と保持ポリシーがレバーであり、公開されたエビクションコストに関する作業が直接適用されます。容量バウンドの場合（これらの実行が位置するのはここです）、問題は「このセッションは戻ってくるか？」ではなく、「どうすればタイトなツールループでN個の同時セッションの88kトークンワーキングセットを収容できるか？」ということです。これは、圧縮、階層化、アドミッション制御、およびワーキングセットを意識したスケジューリングを示唆しており、中央値ギャップ2.1秒ではライブネス予測は実質的に何も扱うことができません。

私はライブネスのフレームワークを仮定して進みましたが、それは3つの失敗したポリシーを招きました。まずどちらのレジームにいるかを確認してからポリシーを選択すれば、すべてを節約できたでしょう。

LRU-leafは、文献が扱っているよりも強力なベースラインです。 実トレースで3つの独立したメカニズムでそれを打ち負かすことができませんでした。一方、いくつかの公開された代替案は、競合他社の劣化したポートに対して評価されています — 2つの別々の論文は、適応型TTLが固定の2秒または0.3秒ピンに置き換えられたContinuumに対してベンチマークしており、これはそれが機能するものを無効にします。このヌル結果は、それらのマージンが読んでいるよりもソフトであることを示唆しています。

自分の数値を信頼する前に、公開されたカーブに対して検証してください。 それを実行したことで、まだ説明できない不一致が明らかになりました。そして、それは私がここで他のすべてを信頼する唯一の理由です。

制限事項

• これらの実行は容量バウンドであり、TTLバウンドではありません。 約1070万トークンのワーキングセットに対して40,000ブロック。Anthropicのようなプロバイダーキャッシュはその逆です：顧客ごとの容量は実質的に無制限で、エントリは5分間のタイマーで期限切れになります。発見2と3は容量バウンドレジームを特徴づけ、TTLバウンドレジームについては何も述べていません。
• これはシミュレーションです。 キャッシュポリシーは忠実にモデル化しますが、GPU実行はモデル化しません。「キャッシュに何を保持すべきか」には有効ですが、スループット、レイテンシ、またはSLO達成には有効ではありません。
• AgentXブロックハッシュはセッションローカルであるため、セッションごとに名前空間が設定されています。これは、セッション間の共有を全くモデル化していません — 保守的ですが、ユーザー間の共有システムプロンプトはここでは見えません。Mooncakeのハッシュはグローバルですが、そのトレースはアイドル構造のない、高密度な1時間です。
• AgentXセッションの到着時刻は合成（ウィンドウ上の均一分布）です。なぜなら、トレースはセッション相対タイムスタンプのみを保存しているからです。
• 393セッションと1時間のMooncakeは、世界全体ではありません。
• ライブネス文献が間違っているとは主張していません。 容量バウンドキャッシュでは、それがターゲットとするレバーはほとんど作業がなく、どちらのレジームにいるかを確認することが、ポリシーを選択する前に来るべきだと主張しています。

再現方法

git clone https://github.com/<you>/agentic-kv-cache && cd agentic-kv-cache
make setup      # venv
make data       # ~1.1 GBのトレース（Apache-2.0）、その後AgentXをピクルにフラット化
make repro      # 全4つの実験、結果をresults/に書き込む

個別に：

make validate      # Mooncakeの再現        -> results/01_validate.txt
make characterize  # AgentXのデューティサイクルとギャップ   -> results/02_characterize.txt
make gap           # アイドルギャップごとの再計算        -> results/03_gap.txt
make ablation      # ポリシーのアブレーション            -> results/04_ablation.txt

シミュレータは純粋なstdlib Pythonです。numpyはヘルパースクリプトでのみ使用されます。コミットされた出力はresults/にあり、何もダウンロードせずにテーブルを確認できます。

未解決の質問

これらのいずれかに答えられる場合は、イシューを開いてください — 本当に知りたいです。

1. +4〜6ppのMooncakeオフセットの理由は何ですか？ 無限キャッシュでのポリシーフリーなので、メトリック定義だけで説明できるはずですが、5つの定義でもそれを埋められません。
2. ライブネスを意識したエビクションがラディックスリーフLRUを上回るワークロードはありますか？ おそらく、中央値ギャップが2.1秒よりもはるかに長いもの — 人間参加型の承認フローなど。
3. サブ10秒ギャップからの33%の結果は、他のエージェントトレースでも当てはまりますか？ もしそうなら、このサブフィールドの大部分は間違った用語をターゲットにしています。

クレジット

トレース：Mooncake (Moonshot AI, FAST'25) および AgentXコーパス (SemiAnalysis)、両方ともApache-2.0。この作業は、それらのいずれとも独立しており、提携していません。

MITライセンス。