The KV-Cache Papers Said LRU Was Wrong. 393 Claude Code Sessions Disagree.

TL;DR

A pseudonymous engineer published agentic-kv-cache, a from-scratch prefix-cache simulator that replays 68,266 requests from 393 real Claude Code sessions plus 23,608 requests from Moonshot's Mooncake trace. They built three mechanisms designed to beat the least-recently-used eviction every serving engine ships by default, and all three lost at every cache size tested. The useful part is the diagnosis: under capacity pressure, 33.1% of recomputed tokens follow an idle gap of under ten seconds, only 17.5% follow a gap longer than the five-minute TTL the literature targets, and a 300-second TTL policy produced byte-identical results to LRU in every run.

The premise the author set out to exploit

Cross-request prefix caching is why a coding agent's later turns cost a fraction of a cold prompt. vLLM's automatic prefix caching, SGLang's RadixAttention, LMCache and Mooncake Store all evict least-recently-used by default. SGLang exposes lfu, slru and priority behind --radix-eviction-policy, but lru is the shipped default.

A growing stack of papers argues that recency is the wrong signal for agents, because sessions go idle while a tool runs or a human thinks, and LRU cannot tell a paused session from a dead one. AgentSysBench, published in August from 24-hour production traces, reports that the median session executes for only 20% of its lifetime, that 70% of sessions execute for less than half of theirs, and that evictions caused by a five-minute provider TTL account for 55.9% of cache-create tokens and 31.5% of aggregate cost across 35,037 coding-agent sessions. Continuum, whose authors include Ion Stoica and Joseph Gonzalez, pins KV cache around tool calls with an adaptive time-to-live and reports up to 8.18x better job completion time on a real SWE-agent workload against vanilla vLLM.

The author read that literature, believed it, and wrote a simulator to cash in on the idle-session signal. In their words, it didn't work, and why it didn't work turned out to be more interesting than the policy would have been.

A simulator that respects the radix tree

The README calls out three properties naive simulators skip. Hits are prefix-contiguous, so one missing block at depth three makes everything after it unusable even if it is still resident. Eviction is constrained by the radix structure: a block with resident children cannot go, so the honest baseline is LRU over radix leaves, which is what SGLang and vLLM actually implement. And the chain currently being inserted must be pinned, for a reason covered below.

The main trace is AgentX, the corpus SemiAnalysis released for its InferenceX benchmark: 393 opt-in Claude Code sessions with all prompt text stripped, leaving per-request token counts and 64-token block hashes that still reconstruct prefix reuse, Apache-2.0 on Hugging Face. The median request carries 88,768 input tokens and the median session has 70 requests. The second source is the trace bundle from Moonshot's Mooncake paper, Best Paper at FAST '25: 23,608 tool-and-agent requests with 512-token block hashes.

Before trusting its own numbers, the repo reproduces Table 1 of the Mooncake paper, which reports LRU hit rate against capacity on Moonshot's own trace: 30% at 1,000 blocks, 40% at 10,000, 50% at 50,000 and 51% at 100,000. The replay reproduces that shape exactly, including the saturation point, but sits four to six points high everywhere. Five metric definitions failed to close the gap, and the author published it unresolved rather than tuning until it matched.

Incidentally, flat block LRU and radix-leaf LRU differ by 0.02 points here, so the leaf restriction both engines implement buys essentially nothing.

Where the recompute actually comes from

The idle-session premise checked out, and then some. Median duty cycle on AgentX was 13.9% against the published 20%, and 85.5% of sessions executed for less than half their lifetime against 70%. But the gaps are bimodal: a 2.1-second median between requests with a tail out to 5.7 days, and only 3.3% of gaps exceed the 300 seconds a provider TTL cares about.

The measurement that changed the author's mind: replay the trace with a 40,000-block cache and bucket every recomputed token by the idle gap before its request, independent of any policy.

The dominant source of misses is tight two-second tool loops whose 88k-token working sets do not fit. That is a capacity problem, and a liveness predictor has nothing to work with when the median session is 2.1 seconds from its next request: almost everyone is "about to return." The cleanest proof is that a TTL-300s policy was byte-identical to LRU-leaf in every run at every cache size, because LRU always evicted before the timer expired.

Think of two parking garages. In the first, cars get towed after five minutes unattended, and the lever is predicting who is walking back. In the second, the garage is simply full, and no amount of predicting who returns creates a space. The published eviction-cost work lives in the first garage. This simulator, with 40,000 blocks against a working set of roughly 10.7 million tokens, lives in the second.

The README is careful to say this does not contradict AgentSysBench's 31.5% figure: that number counts eviction-caused cache-create tokens against the total bill in a TTL-bound provider cache, where nearly every eviction is gap-driven by construction. A provider cache like Anthropic's has effectively unlimited per-customer capacity and a five-minute timer. Both numbers can be right. They just tell you to optimize different things.

Three policies, three losses

The author's policy had three separable components. H replaces recency with an online, no-oracle estimate of the probability a session returns, learned from observed inter-turn gaps. C models recompute cost physically, with an attention term proportional to position, so the tail of a 100k-token chain costs far more per byte than it looks. G evicts one session's private tail at a time instead of truncating fifty chains by taking the globally oldest leaves. The ablation ran on 40 AgentX sessions and 4,751 requests at 8,000, 20,000 and 50,000 blocks.

The pattern holds at every size. At 8,000 blocks LRU-leaf hit 83.48% and the full +HCG policy 68.63%; at 50,000 blocks the gap narrows to 95.76% against 91.40%, and hazard-only gets within 0.08 points. Measured as effective recompute cost, +HCG was 81% worse than LRU at 8,000 blocks, 208% worse at 20,000 and 67% worse at 50,000. LFU, the alternative a serving engine already ships, was 130% to 447% worse. The author's summary: monotone negative, every component made it worse, and the one they were most confident in, session-coherent eviction, was the worst. The policy was optimizing a signal carrying 17.5% of the waste with a predictor that cannot discriminate at a 2.1-second median gap.

The oracle that lost to LRU

Finding five is the one every reader building their own cache simulator should copy. In the author's first run, Belady, the offline oracle that knows the future and is provably optimal for a plain cache, lost to LRU. Oracles are not supposed to lose; that is the whole job description. The cause was a harness bug: inserting a long chain into a nearly full cache let the policy evict the very prefix it was in the middle of building. LRU is accidentally immune, because just-inserted blocks carry the newest timestamp. Every non-recency policy cannibalizes itself. Real engines prevent this with reference-count pins; a from-scratch simulator usually does not.

It is a moving crew clearing floor space for a couch by carrying out the half of the couch that is already in the room. The README's advice is blunt: make your first test "does Belady beat LRU?" and if it does not, every comparison you run afterward is silently wrong in LRU's favor.

What the thread pushed back on

The repo drew 108 points on Hacker News, where the argument was less about the numbers than about how they were produced. Several commenters found the README's cadence unmistakably model-written, and others argued the target metrics looked chosen by an LLM rather than a researcher. One reader noted that the papers being refuted are never cited by name, so the claims cannot be evaluated. That criticism has teeth: the README asserts that two separate papers benchmark Continuum with its adaptive TTL replaced by a fixed 2-second or 0.3-second pin, which would disable the thing that makes it work, but it does not say which papers. Treat that as the author's unverified claim.

The sharpest technical objection: the +H curve nearly catches LRU at 50,000 blocks, so why stop the sweep there, when the whole tested range is one where the five-minute TTL never fires? The author's limitations section concedes most of this in advance: simulation only with no GPU execution modeled, session-local hashes that make cross-user sharing of system prompts invisible, synthesized arrival times, and 393 sessions plus one hour of Mooncake is not the world.

What to do with it

Establish which constraint binds before choosing a policy, because the two regimes want opposite things. Self-hosting with a fixed KV budget puts you in the capacity-bound regime, where the levers are compression, tiering, admission control and working-set-aware scheduling. Calling a provider API puts you in the TTL-bound one, where the game is keeping sessions warm: Anthropic's docs measure the five-minute lifetime from the start of the request that touches the cache, so a four-minute streamed response leaves about a minute for the follow-up, and the one-hour TTL costs 2x base input on writes instead of 1.25x.

The upstream engines are working the same traces. An open SGLang pull request from August adds a tail-optimized LRU variant tested against the same SemiAnalysis corpus and reports p99 inter-token latency down 43.9% at concurrency 32 with the prefix hit rate unchanged around 96%. Read next to this repo, the productive direction on agentic traces looks like trimming latency tails around LRU, not replacing it.

Everything reproduces from a cold checkout with make setup data repro, which pulls about 1.1 GB of Apache-2.0 traces into a pure standard-library Python simulator; result files are committed so you can check the tables without downloading. The repo is MIT licensed, two commits old, and had 22 stars at the time of writing. The author's standing question is whether the sub-10-second result holds on other agentic traces. If it does, a good chunk of a subfield is aimed at the wrong term.

Key Takeaways

• LRU over radix leaves went unbeaten. Three mechanisms and LFU all lost at 8,000, 20,000 and 50,000 blocks on real Claude Code traces; the full policy was 67% to 208% worse on effective recompute cost.
• Under capacity pressure, waste hides in tight loops. 33.1% of recomputed tokens followed a gap under ten seconds; only 17.5% followed a gap past the five-minute TTL, and a TTL-300s policy was byte-identical to LRU in every run.
• Two regimes, opposite levers. Capacity-bound caches want compression, tiering and admission control; TTL-bound provider caches want liveness and retention work. AgentSysBench's 31.5% figure is right for the second and irrelevant to the first.
• Run Belady first. If an offline oracle loses to LRU in your simulator, you have an unpinned in-flight chain, and every comparison is silently biased toward LRU.
• Validate, then read the caveats. The replay matches the shape of Mooncake's published curve but sits 4 to 6 points high, the README names no opposing papers, and Hacker News suspects a model wrote it.

Sources: agentic-kv-cache README, Hacker News thread, SemiAnalysis AgentX methodology, AgentX trace on Hugging Face, Mooncake FAST '25 trace release, Mooncake paper, AgentSysBench, Continuum, vLLM prefix caching design, SGLang server arguments, SGLang T-LRU pull request, Anthropic prompt caching docs