Part 2. TANREN — 11 Wins to 1 Against Twenty Years of Cache Classics, on the Future of a Production Trace

Replaying 40,000 holdout requests from a real Twitter trace. Left: the standard LRU. Right: the evolved policy. Hit rate 84.3% → 86.6% (+2.3pt), 932 fewer misses. The “wait time” on screen is an illustrative simulation assuming one miss = 2 seconds (the hits and misses themselves are measured).

This is Part 2 of the TANREN series. The project overview is here, and Part 1 (Atari Pong) is here. This time the subject is not a game but a production infrastructure problem: cache eviction.

TANREN in 30 Seconds

TANREN does not train LLM weights at enormous cost. Instead, it asks a cheap, frozen LLM to write candidate code, then evolves those programs under an automated scorer. The goal is to approach results that large-scale compute reached through hundreds of millions of frames of training — using one desktop PC, a few days of search, and a few dollars of API cost.

In Part 1, this system reached the theoretical ceiling on Atari Pong (21–0 in all 40 games). But a game is a clean, controlled testbed, and the obvious question remains: does it work on a real problem?

The Problem: Cache Eviction — a Field Refined for Twenty Years

Servers respond quickly by keeping frequently used data in a cache. When the cache is full, which item you throw away determines performance — and for this eviction decision there are classic algorithms refined over two decades: ARC (2003), LIRS (2002), and W-TinyLFU (2017). Each has survived waves of would-be successors and is still in use today.

I picked this problem for two reasons.

1. Scoring is fully deterministic — replay an access trace and count the hits. Which policy is better is settled by arithmetic, with no room for a judge’s taste or ambiguity.
2. It maps directly onto LLM inference — vLLM’s prefix cache defaults to LRU, and every cache miss costs one prefill (a KV-cache recomputation). A better eviction policy translates directly into better serving performance.

What gets evolved is a single Python function, priority(now, keys, last_access, freq, insert_time) -> scores. It assigns a score to every cache slot, and the slot with the lowest score is evicted. Both LRU and LFU can be written in one line in this form, so evolution started from that naive LRU.

The evaluation data is not a synthetic benchmark: it is Twitter’s production cache traces (2020, anonymized, CC-BY-4.0). I used three clusters with different characteristics: one dominated by a small set of frequently repeated keys, one with a huge working set, and one in between.

Time Splits for a Fair Evaluation

The most common pitfall in this kind of experiment is overfitting to the trace — tuning a policy until it looks good on the exact data it was optimized against. To guard against that, every evaluation uses a time split:

• Training happens on past segments.
• Selection (choosing the final candidate) happens on a middle segment — the strongest individual from training is never adopted as-is.
• Judgment happens only on future segments the evolution has never seen.

Under this design, an overfitted policy eliminates itself: it simply cannot win on the future segments.

The First Result: Winning the Near Future, Losing the Far Future

Here is the outcome of the first evolution against real traces (real1). On a near-future holdout the evolution had never seen (three clusters, ~300k requests, 1,000 slots), the evolved policy beat every classic.

Ending the article here would have looked great. But when I retested on segments further away from the training period, the record was 3 wins and 5 losses (sign test p = 0.86 — not significant). The policy had specialized to the quirks of its particular time period. Traffic patterns drift over time, and a policy that wins in the near future but fails further out is of no use in production.

The Fix: Training on Two Windows Far Apart in Time

The fix was a change to the scoring. The training score became the sum over two windows far apart in time. Code that merely fits the quirks of one period loses points on the other window, so only code whose structure works in both periods survives. With this scoring in place, I re-ran the evolution for 40 generations and ~320 mutation calls.

flowchart LR
    A["Train<br/>0-50k + 300k-350k<br/>(sum over two distant windows)"] --> B["Select<br/>400k-450k<br/>(final candidate chosen on val)"]
    B --> C["Judge<br/>500k-700k<br/>(far-future holdout)"]
    C --> D["Robustness tests<br/>450-500k / 700-800k / 800k-1M<br/>x capacities 500/1000 x 2 clusters"]

On the far-future holdout, the evolved policy scored 262,359 hits against ARC’s 257,822 (+1.8%), and beat LIRS by +5.6%. I then ran a robustness test: 12 matchups over completely unused segments × 2 capacities × 2 clusters, each scored against whichever classic is strongest on that particular matchup. The result is the number in this article’s title:

11 wins / 1 loss — one-sided sign test p = 0.003

Note the “strongest classic” column. On cluster001 it is W-TinyLFU; on cluster029 it is ARC. No single classic is the best choice across all the matchups — the right textbook answer changes with the character of the traffic. Meanwhile, one policy synthesized for this specific workload stays consistently ahead of whichever classic happens to be strongest. That, I believe, is the main value of synthesizing a policy for the environment at hand.

The Evolved Policy — 53 Readable Lines of Python

The final result is a 53-line priority() function (blank lines included). In essence, it combines ideas from the existing algorithms into a single scoring formula:

• Frequency decay — the longer since a key’s last access, the more its past popularity is discounted (addressing LFU’s main weakness).
• Hot-key protection — a bonus for keys that are both frequently and recently accessed.
• Cleaning out one-hit wonders — strong penalties for keys accessed only once and for the traces left by scans (achieving the effect of W-TinyLFU’s admission control using nothing but the eviction score).
• A grace period for newcomers — newly inserted keys are not evicted immediately, but become cheap to evict if their access count fails to grow.

The structure differs from ARC, LIRS, and W-TinyLFU alike — and it beat the strongest of them on 11 of the 12 matchups. The full code is in the repository below. You can read and audit it line by line, and if anything goes wrong, a one-line change rolls it back to LRU.

You Can Rerun This — Code and Verifiers Are Public

The champion code (the final selected policy) and the full verifier suite are public on GitHub: matu79go/tanren-champions

The verifier includes implementations of LRU / LFU / ARC / LIRS / W-TinyLFU / Belady. Once you download the traces, the 11-1 table above can be reproduced with a single command. The only dependency is Python 3.10+.

cd cache
# get cluster001, cluster029 from twitter/cache-trace
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

Before publishing, I confirmed that this output matches the original experiment logs down to the last digit of the hit counts. The Pong champion from Part 1 — the function that plays 21–0 from 128 bytes of RAM — is in the same repository, and run_pong.py replays all 40 shutouts on your own machine.

What This Means for LLM Inference

One cache miss corresponds to one prefill (a KV-cache recomputation). If vLLM’s default LRU prefix cache were swapped for this policy, the near-future holdout numbers correspond to 4,934 fewer prefills per 300k requests. Assuming a 31B-class model at roughly 1.5 seconds per 1K-token prefill, that is about 2.1 GPU-hours saved — a back-of-the-envelope estimate. Generating the policy cost $0.4 in API fees.

An honest note: the hit-rate difference is a few percentage points, so average response time does not improve dramatically. What actually happens is that a few thousand occasional slow responses — the recomputations on cache misses — disappear. The more users and prefixes that share the same memory, and the more frequent the evictions, the wider the gap becomes. Measured TTFT inside a live vLLM comes later in this series.

Experimental Safeguards — Keeping Self-Deception Out

1. Time-split train / val / holdout. Train on the past, select in the middle, judge on the future. An overfitted policy cannot win on the future segments and eliminates itself.
2. Selection on a validation set. The final candidate is chosen from the archive of all generations by its validation score — never the strongest individual from training as-is.
3. Implement the strongest baselines before comparing. Instead of stopping at a win over ARC, I implemented LIRS and W-TinyLFU and compared against them too. Each stronger baseline changed how the results looked.
4. The verifier is a pure program. It replays the trace and counts hits. No LLM acts as a judge, so there is no room for plausible-but-wrong scores to creep in.

Limitations

• The margins are a few percent. That is a meaningful difference in the cache literature, but not a dramatic one.
• Tested on three Twitter clusters only. A different workload requires re-evolution — which is also how this system is meant to be used: re-tailoring a policy for your own environment costs about $0.4.
• Capacity is slot-based (object sizes are ignored) — a simplified setting.
• All numbers come from simulation (trace replay). Measuring TTFT on live hardware is the next stage.

Cost

One re-evolution for this experiment took 40 generations, ~320 mutation calls, and ~2.5 hours on one desktop (GX10), at $0.4 in API fees (mutations by gemini-2.5-flash-lite; scoring is pure-Python CPU work). The baselines — ARC, LIRS, W-TinyLFU — each carry twenty years of research behind them. The practical use of this system is not to invent a new textbook algorithm, but to cheaply tailor a single policy that beats the textbook on your specific traffic.

Next in the series, we move from simulation to live hardware: the evolved policy is patched into a real vLLM and TTFT is measured. Back to the project overview.