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

The author of the agentic-kv-cache repository conducted an experiment replaying 68,266 requests from 393 actual Claude Code sessions, alongside 23,608 Mooncake requests, through a prefix-cache simulator. The goal was to outperform the production baseline using three different methods.

The result? Failure.

The most compelling discovery was why these attempts failed: when capacity is pressured, the bulk of recomputation is triggered by tool-calling loops occurring seconds apart, rather than sessions timing out due to a TTL (Time-to-Live)—in fact, the TTL rarely even triggers.

🛠️ Reproduction Steps

To replicate these findings from a fresh checkout, run:

• make setup
• make data
• make repro

---

The Core Problem: KV Prefix Caching

In the realm of agentic LLM serving, cross-request KV prefix caching is the most significant practical optimization. It is the reason why the 50th turn of a coding agent is significantly cheaper than the first.

Most modern serving stacks utilize this:

• vLLM: Automatic prefix caching.
• SGLang: RadixAttention (defaults to LRU, though supports LFU, SLRU, and Priority via --radix-eviction-policy).
• LMCache & Mooncake Store.

Despite the prevalence of Least Recently Used (LRU) as the default, a growing body of research suggests LRU is ill-suited for agents because it cannot distinguish between a session that is temporarily paused and one that is permanently dead.

---

🏗️ The Simulator Architecture

The author developed a discrete-event, block-granular simulator. To ensure accuracy, the simulator adheres to three critical properties that simpler implementations often overlook:

1. Prefix-Contiguity: A cache hit is defined as the longest resident prefix of the block chain.
2. The "Break" Rule: If a block at depth $d$ is missing, all subsequent blocks are unusable, even if they exist in the cache.
3. Radix-Leaf LRU: The baseline implements LRU over radix leaves, mirroring the actual behavior of vLLM and SGLang.

Visualizing Prefix-Contiguous Hits

Dataset Overview

---

📈 Validation: The Mooncake Curve

To validate the simulator, the author attempted to reproduce the hit-rate-vs-capacity table published by Mooncake.

Hit Rate Formula: $\text{Hit Rate} = \frac{\text{Resident Prefix Blocks}}{\text{Total Required Blocks}}$

Observations:

• The curve shape matches perfectly, confirming the saturation point between 1k and 50k blocks.
• The slight numerical discrepancy remains unresolved despite testing five different metric definitions; it is likely a trace-version mismatch rather than a bug.
• Radix-leaf restriction matters $\rightarrow$ The difference between flat block LRU and radix-leaf LRU was only 0.02pp, meaning the leaf restriction provides negligible benefit.

---

🕒 Agent Session Dynamics

The data suggests that agent sessions are even more "idle" than previously reported.

Claude Code Session Stats:

• Session Span: $p_{50} = 1.84\text{h}$, $p_{90} = 28.36\text{h}$, $\text{max} = 254.8\text{h}$.
• Inter-request Gap: $p_{50} = 2.1\text{s}$, $p_{90} = 51.1\text{s}$, $p_{99} = 3426.3\text{s}$.
• Gap Distribution:
  • $> 60\text{s}$: 9.5%
  • $> 300\text{s}$: 3.3%
  • $> 3600\text{s}$: 1.0%
• Token Volume: $p_{50} \text{ input} = 88,768$; $p_{90} \text{ input} = 204,288$.
• Duty Cycle (Actual execution time / Wall-clock time): $p_{25} = 3.4\%$, $p_{50} = 13.9\%$, $p_{75} = 33.9\%$.

While literature (e.g., AgentSysBench) claims a 20% median duty cycle, this trace shows a lower 13.9%, meaning the "idle session" problem is actually more extreme here.

---

🔍 Where the Waste Actually Is

The author investigated the source of recomputation to see if it aligned with the claims in AgentSysBench (arXiv:2608.15127):

"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.

By bucketing recomputed tokens by the preceding idle gap, the author found:

The Conclusion

Only 17.5% of recompute occurs after a gap longer than 5 minutes. The primary driver of cache misses is actually tight, two-second tool loops where the working set (approx. 88k tokens) simply exceeds the available cache capacity.

This is a capacity problem, not a liveness-prediction problem. Because the median gap is only 2.1 seconds, almost every session is "about to return," leaving a liveness estimator with nothing useful to predict.

# Summary of the finding
if gap < 10_seconds:
    cause = "Capacity Exhaustion" # Dominant
elif gap > 300_seconds:
    cause = "TTL/Liveness Issue"   # Minority