When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
Yiyu Liu, Minlan Yu, Juncheng Yang
cs.DC · cs.LG
Quick verdict
Finds sophisticated eviction rarely beats LRU for LLM prefix caching; convincing trace study with real vLLM validation, but narrow traces.
Summary
The paper asks whether decades of cache-eviction research transfer to LLM prefix caching. Using two new production traces (FreeInference: 327.5K requests over 7 days; Chutes: 515.8K over 131 days), a custom C++ simulator that enforces request-level residency and was calibrated against vLLM, and capacity sweeps across HBM (24-120 GiB) and pool (0.25-12 TiB) regimes, the authors evaluate 14 algorithms. Nearly all - ARC, LHD, LeCaR, LRB, 3LCache, and prefix-specific Workload-aware and AsymCache - match or slightly trail LRU; LFU and W-TinyLFU collapse; Belady's optimum retains a large gap. The authors attribute this to session-bounded, short reuse intervals (median intra-session 8.2 s) that make recency dominant, while frequency tracks session progress rather than reuse timing. They further identify depth-dependent miss costs and heavy-tailed session footprints (top 10% of sessions hold 76.2% of KV bytes), and propose compute-aware eviction with partial-node granularity: on a real H200 vLLM replay this cuts average TTFT 19.9% and raises prefill throughput 18.8%. Findings generalize only partially across four Qwen Bailian traces and AgentX, where LRU needs more capacity before it catches up. Limitations: traces come from only two smaller public inference providers, artifacts are promised but not yet released, and simulator-vs-vLLM validation is not quantified.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Sophisticated eviction algorithms designed for traditional caches provide little to no benefit over LRU on production LLM prefix-cache traces, while frequency-based policies perform substantially worse.
- The structural reason is that prefix reuse is dominated by short, session-bounded reuse intervals (median intra-session gap 8.2 s), making recency unusually predictive while frequency only tracks session progress.
- Miss costs grow with block depth, so compute-aware eviction with partial-node granularity improves compute savings (+10.4 points over LRU at 24 GiB) and, on a real vLLM/H200 replay, cuts average TTFT 19.9% and raises prefill throughput 18.8%.
- Eviction granularity should match the memory tier: strictly block-level in constrained HBM, while session-level eviction becomes acceptable in large pools where the measured penalty vanishes (§5.3).
Strengths
Novel, high-fidelity measurement substrate
Two new production traces (327.5K and 515.8K requests, Table 1) with fine-grained 16-token cross-session block hashes - properties Table 3 shows no prior public trace combines - plus a custom C++ simulator enforcing the request-level residency constraint that standard simulators (libCacheSim) ignore, calibrated against native vLLM with up to 160x speedup (§3.1).
A structural explanation, not just a benchmark
§4 contrasts the prefix cache against Wikipedia CDN and CloudPhysics block traces: session-bounded lifetimes (median session 55 s, §4.1), concentrated reuse intervals (median intra-session 8.2 s, 99.7% under 22 min, §4.2), and frequency tracking session progress rather than reuse timing (flat Fig. 5a) jointly explain LRU's robustness and frequency policies' collapse.
Offline oracles turn design advice into a diagnosable decision
End-to-end validation on a real engine with fragmentation analysis
Honest scoping of generalization
Weaknesses
Narrow production sources
Artifacts promised, not available
RandomCompute is underspecified
Thin end-to-end evidence
Flagship technique is trace-dependent
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper asks a focused systems question: what eviction policy should LLM prefix caches use, and why? Its claims are threefold: (1) fourteen sophisticated policies (§3.2, Fig. 2) rarely beat LRU across HBM (24-120 GiB) and pool (0.25-12 TiB) regimes on two production traces; (2) the cause is structural - session-bounded block lifetimes (§4.1) and short, concentrated reuse intervals (median intra-session 8.2 s, §4.2) make recency dominant while frequency only tracks session progress (§4.3); (3) depth-dependent miss costs (§4.4) and heavy-tailed session footprints (top 10% of sessions hold 76.2% of KV bytes, §4.5) call for compute-aware partial eviction and tier-matched granularity (§5). Claims are consistently scoped and mostly supported by the presented evidence.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Why does simple LRU beat sophisticated cache eviction algorithms for LLM prefix caching?
Because most prefix reuse comes from successive requests within the same active session, arriving at a steady fast pace (median intra-session gap of 8.2 seconds in the studied traces). This makes recency an unusually reliable predictor of reuse, while frequency mostly just tracks how long a session has run. Cached blocks also die with their session (median session 55 seconds), so long-idle blocks are almost certainly dead weight. The paper finds ARC, LHD, LeCaR, LRB, 3LCache, and prefix-specific policies all roughly match or trail LRU, while LFU and W-TinyLFU perform far worse.
What is the compute-savings ratio in LLM prefix caching?
It is a cache metric that weights each cache hit by the computation it avoids, rather than counting all hits equally. Because attention cost grows with token position, recomputing a block deep in a prompt costs more than recomputing a shallow block, so two eviction policies with identical hit ratios can save very different amounts of prefill compute and TTFT. With a constant cost model the metric reduces to the ordinary hit ratio.
How much does compute-aware cache eviction improve LLM serving performance?
It depends on the workload. On the FreeInference trace at a 24 GiB cache, compute-aware eviction improved the compute-savings ratio by 10.4 percentage points over LRU. On a real vLLM deployment with Qwen3-Coder-30B on an H200 GPU (48 GiB cache), a partial-node variant cut average TTFT by 19.9% (1.04 s vs 1.29 s) and raised prefill throughput by 18.8%. However, the paper's own offline diagnostic shows the potential gain is at most 1.1 points on five of six studied traces, so operators should measure the gap before adopting it.
Are the paper's traces and simulator publicly available?
The authors state they will release the two production traces (FreeInference and Chutes) and their C++ prefix-cache simulator, but in the reviewed version no repository or link is provided yet. Two validation datasets used in the paper - the Qwen Bailian traces and the SemiAnalysis AgentX corpus - are already public, so partial replication is possible today.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure values are inferred from captions and in-text numbers; underlying curves could not be inspected directly.
- Some implementation details (e.g., RandomCompute sample size, ILP formulation specifics) may exist in portions of the paper not captured by text extraction.
- Artifact availability reflects the reviewed text only, which promises release; this may have changed since publication.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.