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

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. The interesting part is why: under capacity pressure, most recomputation comes from tool-calling loops seconds apart, not from sessions idling past a TTL — and the TTL never fires at all.

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

Contents

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 by default. (SGLang also ships LFU, SLRU, Priority and others behind --radix-eviction-policy ; LRU is the shipped default.)

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.

... continue reading