GitHub - gauravapiscean/agentic-kv-cache: Reproducing agentic KV-cache policy claims on real traces. 68k requests from 393 Claude Code sessions. LRU is harder to beat than the 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 What I built Validation: reproducing Mooncake's published curve 1. Agent sessions are idle more than published 2. Under capacity pressure, the waste isn't where I expected 3. The 5-minute TTL never fired under capacity pressure 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 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. 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: trace requests block size hash scope source SemiAnalysis AgentX 68,266 across 393 Claude Code sessions 64 tok session-local HF (Apache-2.0) Mooncake mooncake_trace / toolagent 23,608 512 tok global GitHub (Apache-2.0) Mooncake conversation 12,031 512 tok global same 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. cache (blocks) 1k 10k 30k 50k 100k ∞ published (LRU) 0.30 0.40 0.48 0.50 0.51 0.51 measured (radix-leaf LRU) 0.341 0.460 0.537 0.551 0.552 0.553 measured (flat block LRU) 0.340 0.460 0.537 0.551 0.552 0.553 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. Under capacity pressure, the waste isn't where I expected This is the finding that changed my mind. AgentSysBench (arXiv:2608.15127) reports that "cache evictions contribute 55.9% of the total cache-create tokens and account for 31.5% of aggregate monetary cost," driven by a 5-minute provider TTL colliding with 1–10 minute idle gaps. That motivated my entire approach. So before optimizing for it, I measured where recompute comes from — policy-independently. Replay the trace, and bucket every request's recomputed tokens by the idle gap that preceded it: gap before request requests share of all recompute tokens <10 s 10,069 33.1% 10–60 s 912 7.0% 1–5 min 701 20.5% 5–30 min 236 8.6% 30–60 min 50 3.0% >1 h 123 5.8% Requests arriving after a gap longer than 5 minutes account for 17.5% of recompute. Requests arriving within 10 seconds account for 33.1%. The dominant source of cache misses here is tight two-second tool loops whose 88k-token working sets exceed cache capacity — a capacity problem, not a liveness-prediction problem. 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. ⚠ This does not contradict the 31.5% figure — read this before citing either The two numbers measure different things in different regimes, and I initially framed this as a contradiction. It isn't. AgentSysBench this repo numerator eviction-caused cache-create tokens, priced at $6.25/M recomputed prefill tokens after a >5min gap denominator total bill (incl. cache reads and output tokens) all recompute tokens regime TTL-bound — a provider cache where per-customer capacity is effectively unlimited and entries die on a timer capacity-bound — 40,000 blocks against a ~10.7M-token working set In a TTL-bound cache, essentially all evictions are gap-driven by construction. My setup never enters that regime — which finding 3 demonstrates directly, since TTL-300s was byte-identical to LRU-leaf in every run. Both results can be entirely correct. The claim here is narrower and it is this: when capacity binds, it dominates the TTL, and the recompute it causes looks nothing like the idle-session story. If you are provisioning cache capacity, that changes what you optimise. If you are reasoning about provider TTLs, the 31.5% figure is the relevant one, not this. Reproduce: make gap 3. The 5-minute TTL never fired under capacity pressure TTL-300s produced byte-identical results to LRU-leaf in every single run. LRU always evicted before the timer expired, so the TTL never became the binding constraint at any cache size I tested. This is also the cleanest evidence that these runs sit in a capacity-bound regime rather than the TTL-bound one a provider cache operates in. 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: cache (blocks) LRU-leaf TTL-300s LFU-leaf +H +HC +HCG 8,000 83.48% 83.48% 63.61% 82.89% 71.77% 68.63% 20,000 93.92% 93.92% 69.96% 93.61% 84.86% 78.89% 50,000 95.76% 95.76% 79.58% 95.68% 94.45% 91.40% Effective recompute cost versus LRU-leaf (negative is worse): cache LFU-leaf +H +HC +HCG 8,000 −129.7% −3.2% −38.9% −81.0% 20,000 −434.3% −4.5% −90.4% −207.8% 50,000 −447.1% −1.0% −15.4% −66.8% 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.