実は強敵？LRUはKVキャッシュ関連の論文が主張するほど甘くない件

近年のKVキャッシュに関する研究論文では、LRU（Least Recently Used）アルゴリズムが最適解ではないかのように語られることが多いですが、実際のエンジニアリングの現場で検証してみると、そう簡単には打ち負かせない奥深さがあります。既存の論文が提示する理論値と、現実のシステム運用におけるパフォーマンスのギャップについて議論が必要です。

リポジトリのリンクはこちら: https://github.com/gauravapiscean/agentic-kv-cache (https://github.com/gauravapiscean/agentic-kv-cache)

うまくいかなかった。そして、なぜうまくいかなかったのかという理由が、本来のポリシーの結果よりも興味深いものだった。

まさにClaudeらしい言い回しだね。

皮肉はさておき、AIエージェントのおかげで、こうした実験を行って結果を公開するコストが十分に下がったのは嬉しいことだよ。おかげで「何も見つからなかった」という報告もようやく共有されるようになったし、これは非常に有益だね。

LLM関連のほとんどのケースにおいて、LRUは理想的な戦略に見える。この分野のすべては「直近への偏り（recency bias）」が重要だからね。この文脈では、それは問題ではなく「機能」だと考えてるよ。

長期間実行されるタスクについてエージェントに修正情報を与えるとき、一番してほしくないのは、それが新しい情報だからといって統計的に補正をかけようとすることだ。古い情報を押しのけて、新しい情報を最優先してほしいんだ。

これはほとんど読むに堪えない。肝心の「論文」がどこにも参照されていないから、否定されている主張が正しいかどうかも評価できない。TTLの話全体も全く関係ないように思えるし。このREADMEには書かれていない、十分に研究されたアドミッションポリシーやエビクションポリシーが山ほどあるのに。なぜわざわざこれを読んでいるのか、全く理解できないな。

少しイライラするのは、今回のようなLLMによるアブレーション調査では、過去の研究に対する考察や、これがベストな手法であるという証明が全く欠けている点だ。何も分からず、ただレバーを引いて何か結果が出たとして、それがベストなのか？ もっとうまくやれる余地は？ 制約は何なのか？

一人の研究者として、数千万ドルもかけて大規模な力まかせの探索を行うことはできない。限られたサブスクリプションの中でやりくりせざるを得ないから、問題に対する膨大な解決策の海をほんの少ししか覗けないんだ。だから、Claudeにオートリサーチループを実行させて要約させるだけでは価値がゼロなんだよ。LRUキャッシュの欠点やトレードオフが何なのか、どう解決すべきなのかが見えてこないからね。

状況は変わっても、計算機科学における2大難問は変わらない。キャッシュの無効化、名前付け、そしてオフバイワンエラーだ。

私はネオクラウドで推論の研究をしているけれど、あくまで個人の見解として書くよ。

経済性と、その結果として推論に投入できるツールは、規模によって変わるんだ。
あえて「乱暴な」例を挙げると、GB300のような構成ならGPU同士はNVLinkで超高速に通信できる。カードがKVキャッシュをDRAM、さらにディスクへとオフロードしても、今回のようなツールを多用するエージェントのワークロードなら「十分高速」に動作するんだ。

つまり、高いスケールと適切なシナリオさえあれば、KVキャッシュのTTLをかなり適当に設定しても、SLAやトークンエコノミクスを十分に満たせるということだ。

これまでずっとレイテンシに敏感なLLMシステムを構築してきたけど、ping-pong方式のオーバーラップさせた非同期コンテキスト構築のような、プリフィル（pre-fill）を考慮したメカニズムを多用するようになった。対話型システムにおいて、最悪のケースは稀であっても問題になるからね。

おもちゃレベルの簡略版はここにある:
https://github.com/chaboud/goulash (https://github.com/chaboud/goulash)

変異率（時間的なシャノン符号化に近い考え方）の検討もそこに含めている（RoPEフレンドリーな構造で）。これは休暇中のプロジェクトで仕事ではないけれど、もっと大きなモデルでも同じ原則が適用できるよ。

パート4の表を見ると、KVキャッシュのサイズがもっと大きければ、一部のポリシーがLRUを追い抜き始めていたように見えるね。

選ばれたキャッシュサイズの範囲は、冒頭のMoonshotの数字に基づくなら妥当なんだろうけど、テストしたすべてのKVキャッシュサイズが小さすぎて5分間のエビクションが一度も発生しなかったという結果が出た時点で、その選択を再評価すべきだったはずだよ。