キャッシュエビクション（キャッシュエビクション）
キャッシュの容量が上限に達した際に、保存済みのエントリを淘汰して新しいエントリのための空間を確保するアルゴリズム。LLMのKVキャッシュやセマンティックキャッシュにおいて、限られたGPUメモリやストレージを効率的に管理するために不可欠な技術である。
キャッシュエビクションとは
キャッシュエビクション（Cache Eviction）は、キャッシュの容量制限に達した際に、既存のエントリを選択的に削除（淘汰）して新しいデータを格納するための仕組みである。LLMの推論最適化においては、GPUメモリ上のKVキャッシュ管理とアプリケーションレベルのレスポンスキャッシュ管理の両方で重要な役割を果たす。
キャッシュは有限のリソース（VRAM、RAM、ディスク）上に構築されるため、全てのデータを永続的に保持することはできない。エビクションポリシーの選択は、キャッシュのヒット率、メモリ効率、推論品質に直接影響する。
主要なエビクションアルゴリズム
LRU（Least Recently Used）
最も長い間参照されなかったエントリを優先的に削除する。実装が簡単で予測可能な動作をするため、最も広く採用されているポリシーである。Redis、Memcached、ほとんどのWebキャッシュがLRUをデフォルトとしている。
長所: 時間的局所性（最近使ったものは近い将来も使う）を活用できる 短所: 頻度を考慮しないため、頻繁にアクセスされるが一時的にアクセスが途切れたエントリが削除される
LFU（Least Frequently Used）
アクセス頻度が最も低いエントリを優先的に削除する。長期的な人気度を反映するため、アクセスパターンに偏りがある場合にLRUより高いヒット率を実現する。
長所: 頻繁に使われるエントリを確実に保持できる 短所: 過去に人気があったが現在は不要なエントリが残り続ける（キャッシュ汚染）。頻度カウンタのメモリオーバーヘッドもある
W-TinyLFU
LFUの改良版で、Caffeine（Java）やRedis 7.0以降で採用されている。Windowフェーズ（短期のLRU）とMainフェーズ（長期のLFU）を組み合わせ、Count-Min Sketchで頻度を効率的に推定する。LRUとLFUの長所を併せ持ち、多くのワークロードで最高のヒット率を実現する。
FIFO（First In, First Out）
最も古いエントリを優先的に削除するシンプルなポリシー。アクセスパターンを追跡する必要がなく、実装コストが最小である。TTLベースの期限切れと組み合わせて使われることが多い。
LLM KVキャッシュにおけるエビクション
StreamingLLM
MITとMeta AIが提案した手法で、KVキャッシュの先頭数トークン（Attention Sink）と直近のウィンドウのみを保持する。中間のKVキャッシュを捨てることで、無限長のストリーミング推論を固定メモリで実現する。
| 保持戦略 | メモリ使用量 | 品質影響 | 用途 |
|---|---|---|---|
| 全保持 | O(n) | なし | 短い入力 |
| Sliding Window | O(W) | 長距離依存喪失 | 固定長入力 |
| StreamingLLM | O(S+W) | 軽微 | 無限ストリーミング |
| H2O（Heavy-Hitter Oracle） | O(k) | 軽微 | 長文推論 |
H2O（Heavy-Hitter Oracle）
アテンションスコアの累積値に基づいて、重要度の高いトークンのKVキャッシュを優先的に保持する手法。全トークンのうち5-10%のHeavy Hitter（高頻度にアテンションされるトークン）が生成品質の大部分を決定するという観察に基づく。KVキャッシュサイズを80-90%削減しても品質劣化が最小限に抑えられる。
Scissorhands
アテンションパターンの分析に基づき、将来的にアテンションされる可能性が低いトークンのKVキャッシュを早期に削除する予測的エビクション手法。H2Oの改良版として位置付けられ、より精度の高い重要度推定を行う。
セマンティックキャッシュにおけるエビクション
アプリケーションレベルのセマンティックキャッシュ（GPTCache、LangChain等）では、以下の複合的なエビクション戦略が使われる。
- TTL + LRU: 一定時間経過で期限切れ、かつ容量上限時はLRUで淘汰
- 重要度スコアベース: ヒット回数、レスポンス生成コスト、ユーザー満足度スコアの加重平均で優先度を決定
- ベクトル密度ベース: 類似するキャッシュエントリが密集している領域から優先的に削除し、キャッシュの多様性を維持する
エビクションポリシーの選択指針
| ワークロード特性 | 推奨ポリシー | 理由 |
|---|---|---|
| 時間的局所性が強い（チャット） | LRU | 最近の会話が最も重要 |
| アクセス偏りが大きい（FAQ） | W-TinyLFU | 人気クエリを確実に保持 |
| ストリーミング推論 | StreamingLLM | 固定メモリで無限長対応 |
| 長文ドキュメント処理 | H2O | 重要トークンを選択的に保持 |
| TTL管理中心 | FIFO + TTL | シンプルで予測可能 |
FAQ
KVキャッシュのエビクションで推論品質は劣化しますか？
エビクション手法によって異なる。H2Oは重要トークンを選択的に保持するため、KVキャッシュを80%削減しても perplexity の増加は1-2%程度に抑えられる。一方、単純なSliding Windowは長距離依存関係を完全に喪失するため、要約タスクなどでは顕著な品質劣化が生じる。タスク特性に応じた手法の選択が重要である。
RedisのエビクションポリシーはLLMキャッシュに適していますか？
Redisは maxmemory-policy 設定で6種のエビクションポリシー（volatile-lru, allkeys-lru, volatile-lfu, allkeys-lfu, volatile-random, noeviction）を選択できる。LLMのセマンティックキャッシュには allkeys-lfu が推奨される。FAQやテンプレート型クエリが多いワークロードでは頻繁にヒットするエントリを確実に保持でき、ヒット率が向上する。
エビクションのオーバーヘッドは無視できますか？
アプリケーションレベルのエビクション（Redis、Memcached）は数マイクロ秒のオーバーヘッドであり、LLM推論の数百ミリ秒〜数秒に比べて完全に無視できる。KVキャッシュレベルのエビクション（H2O、StreamingLLM）はアテンションスコアの計算が必要だが、削減されるメモリとスループット向上の効果がオーバーヘッドを大幅に上回る。