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

LRUはKVキャッシュの論文が示唆するよりも打ち負かすのが難しい 私は393件の実際のClaude Codeセッションと23,608件のMooncakeリクエストから得られた68,266件のリクエストをプレフィックスキャッシュシミュレータで再生し、プロダクションベースラインを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を参照してください。 トレースは実際のデータであり、合成データではありません。 |トレース|リクエスト|ブロックサイズ|ハッシュスコープ|ソース| |---|---|---|---|---| |SemiAnalysis AgentX|68,266 (393 Claude Codeセッション)|64トークン|セッションローカル|HF (Apache-2.0)| |Mooncake mooncake_trace / toolagent|23,608|512トークン|グローバル|GitHub (Apache-2.0)| |Mooncake conversation|12,031|512トークン|グローバル|同上| 検証：Mooncakeの公開カーブの再現 何も信頼する前に、私はMooncake自身の公開トレースと、彼らが述べたポリシーを使用して、Mooncakeの公開ヒット率対容量テーブルを再現しました。 |キャッシュ（ブロック）|1k|10k|30k|50k|100k|∞| |---|---|---|---|---|---|---| |公開（LRU）|0.30|0.40|0.48|0.50|0.51|0.51| |測定（ラジックスリーフLRU）|0.341|0.460|0.537|0.551|0.552|0.553| |測定（フラットブロックLRU）|0.340|0.460|0.537|0.551|0.552|0.553| 形状は正確に再現されており、彼らが文章で説明している飽和点（「1,000から50,000ブロックはキャッシュヒット率を30%から50%に向上させます。それ以上の容量増加はわずかな改善しか示しません」）も含まれています。説明できない+4～6パーセントポイントの系統的なオフセットがあります。私は5つのメトリック定義（ブロック分母、トークン分母、部分的なテールブロックのドロップ、リクエストごとの平均）をテストしましたが、どれもそれを解消しませんでした。 無限キャッシュケースはポリシーフリーであり、トレースの純粋なプロパティです。したがって、不一致は定義上の問題か、トレースバージョンの不一致であり、再生バグではありません。一致するまでチューニングするのではなく、未解決のまま公開します。もし理由をご存知でしたら、イシューを開いてください。 付随的な発見：このワークロードでは、フラットブロックLRUとラジックスリーフ制限付きLRUは0.02パーセントポイントしか差がありません。主要な両方のエンジンが実装しているリーフ制限は、ここでは実質的に何も購入しません。 再現：make validate 1. エージェントセッションは公開されているよりもアイドル状態が多い |セッション|リクエスト|セッション期間（h）|リクエスト間ギャップ（s）|ギャップ > 60s|ギャップ > 300s|ギャップ > 3600s| |---|---|---|---|---|---|---| |393|68266|p50=1.84, p90=28.36, max=254.8|p50=2.1, p90=51.1, p99=3426.3, max=491922 (5.7日)|9.5%|3.3%|1.0%| |入力トークン|出力トークン|リクエスト/セッション| |---|---|---| |p50=88768, p90=204288, max=255808|p50=376, p90=1845|p50=70, max=3551| |デューティサイクル（壁時計時間の実行中の割合）| |---|---| |p25=3.4%, p50=13.9%, p75=33.9%| |セッションの50%未満を実行している期間| |---|---| |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分間のアイドルギャップと衝突することによって引き起こされます。それが私の全体的なアプローチの動機となりました。 したがって、それを最適化する前に、再計算がどこから来るのかを測定しました — ポリシーに依存せずに。トレースを再生し、各リクエストの再計算されたトークンを、その前にあったアイドルギャップごとにバケット分けします。 |ギャップ前のリクエスト|リクエスト数|全再計算トークンに占める割合| |---|---|---| |<10秒|10,069|33.1%| |10～60秒|912|7.0%| |1～5分|701|20.5%| |5～30分|236|8.6%| |30～60分|50|3.0%| |>1時間|123|5.8%| 5分以上のギャップの後に到着するリクエストは、再計算の17.5%を占めます。10秒以内に到着するリクエストは、33.1%を占めます。ここでキャッシュミスの主な原因は、88kトークンのワーキングセットがキャッシュ容量を超えるタイトな2秒間のツールループです — これは容量の問題であり、ライブネス予測の問題ではありません。p50ギャップが2.1秒であるため、ほとんどすべてのセッションが「すぐに返ってくる」状態であり、ライブネス推定器には区別するものが実質的に何もありません。 ⚠️これは31.5%の数値を矛盾するものではありません — どちらかを引用する前にこれを読んでください。 2つの数値は異なるレジームで異なるものを測定しており、私は当初これを矛盾としてフレーム化しました。そうではありません。 |AgentSysBench（このリポジトリ）| |---|---| |分子：5分以上のギャップの後で再計算されたプリフィルトークンを$6.25/Mで価格設定したエビクションによるキャッシュ作成トークン| |分母：キャッシュ読み取りと出力トークンを含む総請求額| |レジーム：TTLバウンド — 顧客ごとの容量が実質的に無制限で、エントリがタイマーで期限切れになるプロバイダーキャッシュ| |この分析| |---|---| |分子：容量バウンド — 約10.7Mトークンのワーキングセットに対して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トークンチェーンのテールを再計算することは