第2話. TANREN — 20年の古典キャッシュに、本番トレースの「未来」で 11勝1敗

実トレース（Twitter）の holdout 区間 4 万リクエストを再生。左が定番の LRU、右が進化した方策です。ヒット率 84.3% → 86.6%（+2.3pt）、ミスを 932 回削減。画面の「待ち時間」はミス 1 回 = 2 秒と仮定した説明用のシミュレーションです（ヒット/ミス自体は実測）。

本記事は TANREN 連載の第2話です。プロジェクト全体像はこちら、第1話（Atari Pong）はこちら。今回のテーマはゲームではなく、本番インフラの課題であるキャッシュ追い出しです。

TANREN を 30 秒で

TANREN は、LLM の「重み」を莫大なコストをかけて学習させる代わりに、追加学習なしの安価な LLM に候補コードを書かせ、そのプログラムを自動採点しながら「進化」させていく仕組みです。大規模計算が数億フレームの学習の末に到達した水準に、手元の PC 1台・数日間の探索・数ドルの API 代で迫ることを目指しています。

第1話では、この仕組みが Atari Pong の理論上限（40 試合すべて 21–0）に到達しました。ただ、ゲームは条件のきれいな実験場です。当然、次の疑問が残ります——実務の問題でも通用するのか？

課題: キャッシュ追い出し — 20 年研究されてきた分野

サーバは、よく使うデータをキャッシュ（手元の高速な置き場）に置くことで速く応答します。キャッシュが満杯になったときどのデータを捨てるかが性能を左右し、この「捨て方」のアルゴリズムには 20 年かけて磨かれてきた定番があります——ARC（2003）、LIRS（2002）、W-TinyLFU（2017）。いずれも多くの後続研究に打ち勝ち、いまも使われ続けているものです。

この課題を選んだ理由は 2 つあります。

採点が完全に決定論的 — トレース（アクセス記録）を再生してヒット数を数えるだけで優劣が決まります。審判の主観や曖昧さが入りません。
LLM 推論に直結する — vLLM の prefix cache は既定で LRU を使います。キャッシュミス 1 回は KV キャッシュの再計算（prefill）1 回に相当するため、「捨て方」の改善はそのまま推論サーバの応答性能の改善につながります。

進化させる対象は、priority(now, keys, last_access, freq, insert_time) -> scores という 1 つの Python 関数です。キャッシュの各スロットにスコアを付け、スコアが最小のものを追い出します。LRU も LFU もこの形式なら 1 行で書けるので、進化の出発点には素朴な LRU を置きました。

評価データは合成ベンチマークではなく、Twitter の本番キャッシュトレース（2020 年・匿名化済み・CC-BY-4.0）です。性質の異なる 3 つのクラスタ（少数の常連キーに集中するもの・ワーキングセットが巨大なもの・その中間）を使いました。

公正に評価するための時間分割

この種の実験でいちばん起きやすい問題は、トレースへの過適合——そのデータだけで良い成績が出るように最適化されてしまうこと——です。対策として、評価はすべて時間で区切って行いました。

訓練は過去の区間で行う。
選抜（最終候補の選択）は中間の区間で行う。訓練で最強だった個体をそのまま採用しません。
判定は、進化の過程で一度も見せていない未来の区間だけで行う。

過適合した方策は未来の区間で勝てないため、この設計なら自動的にふるい落とされます。

最初の結果: 近い未来では勝ったが、遠い未来では負けた

最初の実トレース進化（real1）の結果です。進化が見ていない直後の未来区間（3 クラスタ合計・約 30 万リクエスト・容量 1,000 スロット）では、進化した方策がすべての定番アルゴリズムを上回りました。

近未来 holdout の合計ヒット数（3クラスタ・約30万リクエスト・容量1,000）

LFU

107,158

W-TinyLFU

127,773

LIRS

130,640

LRU（vLLM 等の既定）

131,857

ARC（最強古典）

133,853

進化方策

136,791

Belady（理論上限）

170,688

Belady は「未来のアクセスを知っている」前提のオフライン最適で、どのオンライン方策も到達できない参照値です。進化方策は ARC に +2.2%、LIRS に +4.7%、W-TinyLFU に +7.1%。

ここで記事を終えれば格好はつきました。しかし、訓練からさらに離れた時間帯で追試すると、結果は 3 勝 5 敗（符号検定 p = 0.86、有意差なし）でした。方策が「その時期のアクセスパターンの癖」に過剰に合わせてしまっていたのです。トラフィックの傾向は時間とともに変わります。近い未来で勝てても、離れた未来で通用しないのであれば、実務では使えません。

対策: 時間的に離れた 2 つの窓で訓練する

対策として、採点の方法を変えました。訓練の得点を、時間的に離れた 2 つの窓の合計にしたのです。こうすると、特定の時期の癖に合わせただけのコードは片方の窓で失点し、どちらの時期でも通用する構造を持つコードだけが生き残ります。この採点方式で、40 世代・約 320 回の変異を再進化させました。

flowchart LR
    A["訓練<br/>0〜5万 + 30〜35万<br/>(離れた2窓の合計で採点)"] --> B["選抜<br/>40〜45万<br/>(val で最終候補を選ぶ)"]
    B --> C["判定<br/>50〜70万<br/>(遠未来 holdout)"]
    C --> D["頑健性テスト<br/>45〜50万 / 70〜80万 / 80〜100万<br/>× 容量 500 / 1000 × 2クラスタ"]

遠い未来の判定区間では、進化方策が 262,359 ヒット、ARC が 257,822 ヒットで +1.8%、LIRS に対しては +5.6% でした。さらに、進化に一切使っていないセグメント × 2 容量 × 2 クラスタの計 12 設定で、設定ごとにその設定で最も成績の良い定番アルゴリズムと比較する頑健性テストを行いました。その結果が、タイトルの数字です。

11 勝 1 敗 — 片側符号検定 p = 0.003

設定（クラスタ / 未来セグメント / 容量）	進化方策 vs 最強古典	差
c001 / 45〜50万 / 500	36,371 vs LRU 35,193	+3.35%
c001 / 45〜50万 / 1000	43,562 vs W-TinyLFU 42,927	+1.48%
c001 / 70〜80万 / 500	71,111 vs W-TinyLFU 70,570	+0.77%
c001 / 70〜80万 / 1000	87,897 vs W-TinyLFU 87,035	+0.99%
c001 / 80〜100万 / 500	137,372 vs W-TinyLFU 138,293	−0.67%（負け）
c001 / 80〜100万 / 1000	171,236 vs W-TinyLFU 169,430	+1.07%
c029 / 45〜50万 / 500	20,095 vs ARC 19,828	+1.35%
c029 / 45〜50万 / 1000	22,023 vs ARC 21,981	+0.19%
c029 / 70〜80万 / 500	38,751 vs ARC 38,548	+0.53%
c029 / 70〜80万 / 1000	42,556 vs ARC 42,507	+0.12%
c029 / 80〜100万 / 500	22,762 vs ARC 22,534	+1.01%
c029 / 80〜100万 / 1000	24,997 vs ARC 24,908	+0.36%

この表で注目したいのは「最強古典」の列です。cluster001 では W-TinyLFU が、cluster029 では ARC が最強で、どの定番アルゴリズムも、単独では全設定で最良になれていません。トラフィックの性質によって最適解が入れ替わるなか、この環境向けに合成された 1 本の方策が一貫して上回っている——ここが、環境に合わせて方策を合成するアプローチのいちばんの価値だと考えています。

進化が到達したコード — 53 行の読める Python

最終的に残ったのは、空行込みで 53 行の priority() 関数です。内容を要約すると、既存アルゴリズムの考え方を 1 本のスコア式に組み合わせたものになっています。

頻度の減衰 — 最後のアクセスから時間が経つほど「過去の人気」を割り引く（LFU の弱点への対処）。
ホットキーの保護 — アクセス頻度が高く、かつ直近に使われたキーを優遇する。
使い捨てキーの掃除 — 一度しか使われず古くなったキーや、スキャンアクセスの痕跡に強いペナルティを与える（W-TinyLFU が入場制御で実現している効果を、追い出しスコアだけで表現）。
新入りの猶予期間 — 挿入直後はすぐに捨てず様子を見て、アクセスが伸びなければ優先的に追い出す。

構造は ARC とも LIRS とも W-TinyLFU とも異なり、これが 12 設定中 11 で各設定の最強アルゴリズムを上回りました。コード全文は次節のリポジトリにあります。1 行ずつ読んで監査でき、問題があれば 1 行の変更で LRU に戻せます。

手元で再現できます — コードと検証器を公開

今回のチャンピオンコード（最終的に選ばれた方策）と検証器一式を、GitHub で公開しました: matu79go/tanren-champions

検証器には LRU / LFU / ARC / LIRS / W-TinyLFU / Belady の実装が含まれており、トレースを取得すれば、上の 11 勝 1 敗の表を次のコマンドでそのまま再現できます。依存は Python 3.10 以上のみです。

cd cache
# トレースは twitter/cache-trace から cluster001, cluster029 を取得
python3 eval_trace.py cluster001 cluster029 \
    --segments 450000:500000,700000:800000,800000:1000000 --caps 500,1000
# → total: 11 wins / 1 losses ... one-sided sign test p = 3.174e-03

公開前に、この出力が当時の実験ログとヒット数の 1 の位まで一致することを確認しています。第1話の Pong チャンピオン（RAM 128 バイトを入力に 21–0 を出す関数）と ALE 実行環境も同じリポジトリにあり、run_pong.py で 40 試合の完全試合を手元で確かめられます。

LLM 推論にあてはめると

キャッシュミス 1 回は prefill（KV キャッシュの再計算）1 回に相当します。vLLM の prefix cache の既定 LRU をこの方策に差し替えたと仮定すると、30 万リクエストあたり prefill が 4,934 回減ります。31B 級モデル・1K トークンの prefill を約 1.5 秒とすれば、GPU 時間でおよそ 2.1 時間の節約に相当します（机上の試算です）。この方策の生成にかかった API 代は $0.4 でした。

正直な注記もつけておきます。ヒット率の差は数ポイントなので、平均応答時間が劇的に縮むわけではありません。起きるのは「ミス時の再計算による、時々発生する遅い応答が数千回分なくなる」という種類の改善です。メモリに対して利用者やプレフィックスが多く、追い出しが頻発する環境ほど差は大きくなります。実機の vLLM に組み込んだ応答時間（TTFT）の実測は、この連載の後の回で扱います。

実験設計の工夫 — ごまかしが入らないように

時間分割（train / val / holdout）。 訓練は過去、選抜は中間、判定は未来の区間で行います。過適合した方策は未来区間で勝てず、自動的に落ちます。
検証セットによる選抜。 最終候補は、全世代のアーカイブから検証区間の成績で選びます。訓練で最強だった個体をそのまま使いません。
ベースラインは最強のものを実装してから比較。 ARC に勝った時点で満足せず、LIRS と W-TinyLFU も実装して比較しました。より強い比較対象を用意するたびに、結果の見え方は変わりました。
検証器は純粋なプログラム。 トレースを再生してヒット数を数えるだけです。LLM に採点させないので、もっともらしい誤り（幻覚）が採点に入り込む余地がありません。

限界も書いておきます

勝ち幅は数%です。 キャッシュ研究の文脈では意味のある差ですが、劇的な改善ではありません。
試したのは Twitter の 3 クラスタのみです。別のワークロードに適用するには再進化が必要です（逆に言えば、$0.4 でその環境専用の方策を作り直せることが、この仕組みの使い方でもあります）。
容量はスロット数ベース（オブジェクトサイズは無視）の簡易設定です。
数字はすべてトレース再生によるシミュレーションです。実機での TTFT 測定は次の段階です。

コスト

今回のキャッシュ実験は、再進化 1 回あたり 40 世代・変異約 320 回・GX10 1 台で約 2.5 時間・API 代 $0.4 でした（コードの変異には gemini-2.5-flash-lite を使用、採点は純 Python の CPU 処理）。比較相手の ARC / LIRS / W-TinyLFU には、それぞれ 20 年分の研究の蓄積があります。新しい定石を「発明」するのではなく、目の前のトラフィックに合わせて、定番を上回る 1 本を安価に仕立てる——それがこの仕組みの実務での使い方です。

連載の次回は、シミュレーションから実機に進みます。進化した方策を本物の vLLM に組み込み、TTFT を実測します。プロジェクト全体像に戻る。