LRU is harder to beat than the KV-cache papers suggest

I replayed 68,266 requests from 393 real Claude Code sessions and 23,608 Mooncake requests through a prefix-cache simulator, tried to beat the production baseline three different ways, and failed. Along the way a widely-cited number came out about half as large on independent data.

Everything here reproduces from a cold checkout with make setup data repro.

---

Contents

• What I built
• Validation: reproducing Mooncake's published curve
• 1. Agent sessions are idle more than published
• 2. The waste isn't where everyone is looking
• 3. The 5-minute TTL isn't the binding constraint
• 4. Three ways to beat LRU, three failures
• 5. The harness bug that makes Belady lose to LRU
• What I think this means
• Limitations
• Reproduce it

---

Cross-request KV prefix caching is the largest practical lever in agentic LLM serving. It's why your coding agent's fiftieth turn costs a fraction of its first. Every serving stack has one — vLLM's automatic prefix caching, SGLang's RadixAttention, LMCache, Mooncake Store — and all of them evict with LRU.

There's a large, fast-growing literature arguing LRU is the wrong policy for agentic workloads, because agent sessions go idle and LRU can't tell a paused session from a dead one. The argument is intuitive. I believed it, and built a simulator to exploit it.

It didn't work, and why it didn't work turned out to be more interesting than the policy would have been.

What I built

A block-granular, discrete-event simulator of a cross-request prefix cache. Three properties that matter, and that quick implementations tend to get wrong:

Hits are prefix-contiguous. A hit is the longest resident prefix of the block chain, not a set intersection. Miss one block at depth 3 and everything after it is unusable even if it's still resident.

The radix structure constrains eviction. A block with resident children isn't evictable. So the baseline is LRU over radix leaves, which is what SGLang and vLLM actually implement. Beating naive flat LRU would be a strawman.

The in-flight chain must be pinned. See finding 5.

Traces are real, not synthetic:

Validation: reproducing Mooncake's published curve

Before trusting anything, I reproduced Mooncake's published hit-rate-vs-capacity table on Mooncake's own released trace, with their stated policy.

The shape reproduces exactly, including the saturation point they describe in prose ("1,000 to 50,000 blocks boosts the cache hit ratio from 30% to 50%; further capacity increases show minimal improvement").

There is a systematic +4–6pp offset I could not explain. I tested five metric definitions — block denominator, token denominator, dropping the partial tail block, per-request averaging — and none closes it. The infinite-cache case is policy-free, a pure property of the trace, so the discrepancy is definitional or a trace-version mismatch, not a replay bug.

Publishing it unresolved rather than tuning until it matches. If you know why, please open an issue.

Incidental finding: flat block LRU and radix-leaf-restricted LRU differ by 0.02pp on this workload. The leaf restriction both major engines implement buys essentially nothing here.

Reproduce: make validate

1. Agent sessions are idle more than published

sessions=393  requests=68266

session span (h):   p50=1.84  p90=28.36  max=254.8
inter-req gap (s):  p50=2.1   p90=51.1   p99=3426.3   max=491922   (5.7 days)
   gaps >   60s: 9.5%
   gaps >  300s: 3.3%
   gaps > 3600s: 1.0%
input tokens:       p50=88768  p90=204288  max=255808
output tokens:      p50=376    p90=1845
requests/session:   p50=70     max=3551

DUTY CYCLE (fraction of wall-clock actually executing):
   p25=3.4%   p50=13.9%   p75=33.9%
   sessions executing <50% of lifetime: 85.5%

The most-cited characterization of agentic serving reports a 20% median duty cycle and 70% of sessions below 50%. On this independent trace it's 13.9% and 85.5% — the premise is more extreme than published, not less.

Note the shape: gaps are bimodal. A median of 2.1 seconds (tight tool loops) with a heavy tail out to days.

Reproduce: make characterize

2. The waste isn't where everyone is looking

This is the finding that changed my mind.

A frequently-cited figure holds that evictions account for 31.5% of aggregate agentic inference cost, driven by a 5-minute provider TTL colliding with 1–10 minute idle gaps. That number motivated my entire approach.

So before optimizing for it, I measured it — policy-independently. Replay the trace, and bucket every request's recomputed tokens by the idle gap that preceded it:

Requests arriving after a gap longer than the 5-minute TTL account for 17.5% of recompute. Requests arriving within 10 seconds account for 33.1%.

The dominant source of cache misses in real agentic serving is not sessions idling past a TTL. It's tight two-second tool loops whose 88k-token working sets exceed cache capacity.

That's a capacity problem, not a liveness-prediction problem. And with a p50 gap of 2.1 seconds, almost every session is "about to return" — so a liveness estimator has essentially nothing to discriminate on.

Reproduce: make gap

3. The 5-minute TTL isn't the binding constraint

TTL-300s produced byte-identical results to LRU-leaf in every single run.

Under capacity pressure LRU always evicts before the timer fires. The TTL never binds.

4. Three ways to beat LRU, three failures

I implemented a policy with three separable, independently ablatable components:

• H — hazard-based P(session returns) replacing recency. Online Bayesian estimator over observed inter-turn gaps and continuation rates. No oracle: it only ever sees completed observations.
• C — physically-modelled recompute cost. Prefill cost at position i is a linear term plus an attention term proportional to i, so recomputing the tail of a 100k-token chain is far more expensive per byte than it looks.
• G — coherent session-granularity eviction. Instead of taking the N globally-oldest leaves (which may truncate 50 different chains), sacrifice one session's private tail.

Hit rate, 40 AgentX sessions, 4,751 requests:

Effective recompute cost versus LRU-leaf (negative is worse):

Monotone negative. Every component made it worse, and the one I was most confident in — coherent eviction — was the worst.

Given finding 2, this is exactly what should have happened. I was optimizing for a signal carrying 17.5% of the waste, using a predictor that can't discriminate at a 2.1-second median gap.

Reproduce: make ablation

5. The harness bug that makes Belady lose to LRU

In my first run, Belady — an offline oracle — lost to LRU. That's not a result, that's a broken harness, and it's worth publishing because I expect it to be common.

The cause: inserting a long chain into a near-full cache lets a policy evict the very prefix it is currently building. LRU is accidentally immune because just-inserted blocks have the newest timestamp. Every non-recency policy cannibalises itself. Real engines prevent this with refcount pins; a from-scratch simulator usually doesn't.

If you build one of these, make your first test "does Belady beat LRU?" If it doesn't, you have this bug, and every policy comparison you run will be silently wrong in LRU's favour.

Two other implementation notes:

• Only the deepest hit block can ever be a leaf, so touch() need only update that one block. An O(chain length) walk becomes O(1) — which matters at AgentX's 1,387-block median.
• Score eviction candidates by sampling k least-recently-used leaves rather than scanning the cache. This is what production caches do anyway, so it's realism, not a shortcut.

What I think this means

The agentic KV-cache problem has been framed as a liveness problem. On this data it's a capacity problem. The interesting question isn't "will this session come back?" — it's "how do I fit 88k-token working sets for N concurrent sessions running tight tool loops?" Those point at different answers: the first at TTL policy and survival prediction, the second at compression, tiering, admission control, and working-set-aware scheduling.

LRU-leaf is a stronger baseline than the literature treats it as. I couldn't beat it with three independent mechanisms on real traces. Meanwhile several published alternatives are evaluated against degraded ports of their competitors — two separate papers benchmark against Continuum with its adaptive TTL replaced by a fixed 2s or 0.3s pin, which disables the thing that makes it work. This null result suggests those margins are softer than they read.

Validate against a published curve before trusting your own numbers. Doing that surfaced a discrepancy I still can't explain, and it's the only reason I trust anything else here.

Limitations

• This is simulation. It models cache policy faithfully and GPU execution not at all. Valid for "what should I keep in cache"; not valid for throughput, latency, or SLO attainment.
• AgentX block hashes are session-local, so they're namespaced per session. That models zero cross-session sharing — conservative, but it means shared system prompts across users are invisible here. Mooncake's hashes are global but its trace is one dense hour with no idle structure.
• AgentX session arrival times are synthesised (uniform over a window), because the trace stores session-relative timestamps only.
• 393 sessions and one hour of Mooncake is not the world. The 17.5% figure is one independent measurement against one published 31.5%. That supports "does not replicate here," not "the number is wrong."
• I'm not claiming the liveness literature is worthless. I'm claiming that on this workload the lever it targets is about half as large as advertised, and the residual is elsewhere.

Reproduce it

git clone https://github.com/<you>/agentic-kv-cache && cd agentic-kv-cache
make setup      # venv
make data       # ~1.1 GB of traces (Apache-2.0), then flattens AgentX to a pickle
make repro      # all four experiments, writes results/

Individually:

make validate      # Mooncake reproduction        -> results/01_validate.txt
make characterize  # AgentX duty cycle and gaps   -> results/02_characterize.txt
make gap           # recompute by idle gap        -> results/03_gap.txt
make ablation      # policy ablation              -> results/04_ablation.txt

The simulator is pure stdlib Python; numpy is only used by helper scripts. Committed outputs in results/ let you check the tables without downloading anything.

Open questions

If you can answer any of these, please open an issue — I'd genuinely like to know:

1. Why the +4–6pp Mooncake offset? Policy-free at infinite cache, so it should be explicable by metric definition alone, and five definitions don't close it.
2. Is there a workload where liveness-aware eviction beats radix-leaf LRU? Plausibly one with much longer median gaps than 2.1s — human-in-the-loop approval flows, perhaps.
3. Does the 33%-from-sub-10-second-gaps result hold on other agentic traces? If it does, a good chunk of this subfield is aimed at the wrong term.

Credits

Traces: Mooncake (Moonshot AI, FAST'25) and the AgentX corpus (SemiAnalysis), both Apache-2.0. This work is independent of and unaffiliated with either.

MIT licensed.