When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
AuthorsYiyu Liu, Minlan Yu, Juncheng Yang
AffiliationsHarvard University
For LLM prefix caches, simple recency may beat fancy eviction rules, especially when workloads follow predictable session patterns.
Key results
Processed tokens across the two production traces used to evaluate eviction policies.
RandomCompute result at 24 GiB on FreeInference Trace.
RandomCompute's improvement over LRU, reported as percentage points.
Partial-node compute-aware eviction versus LRU on Qwen3-Coder-30B.
Partial-node compute-aware eviction versus LRU on an NVIDIA H200.
What the paper found
This study tests whether cache policies designed for web and storage workloads transfer to LLM prefix reuse, evaluating 14 eviction algorithms on production traces containing more than 20B processed tokens. The surprising result is that simple Least Recently Used (LRU) remains competitive: requests within active sessions reuse prefixes at a steady pace, so recency predicts reuse better than frequency, which mostly reflects session progress. The authors identify two complications that hit ratio misses: recomputing deeper prefix blocks costs more, and a few sessions consume most cache space. Their proposed approach keeps LRU as the baseline, uses quick demotion such as S3-FIFO when one-hit prompts flood the cache, and adds compute-aware eviction when miss costs vary. On FreeInference Trace, RandomCompute reaches a 0.638 compute-savings ratio at 24 GiB, 10.4 percentage points above LRU; partial-node eviction reduces fragmentation. In an end-to-end test, partial-node compute-aware eviction with Qwen3-Coder-30B on an NVIDIA H200 cuts average time to first token by 19.9% and raises prefill throughput by 18.8% versus LRU. The paper’s practical guidance is tier-specific: use block-level eviction in constrained GPU memory, while session-level eviction can reduce metadata overhead in large memory pools. Its findings also generalize to a trace of Claude Code sessions.
Original abstract
Long-running LLM applications repeatedly send growing context, making prefix caching critical for reducing prefill cost. Yet prefix-cache behavior under agentic workloads remains poorly understood. We study production traces from two companies and evaluate 14 eviction algorithms across HBM-constrained and large memory-pool settings. Despite a large gap to Belady, sophisticated policies designed for traditional caches provide little benefit over LRU. The reason is structural: prefix reuse is dominated by the regular pacing of active sessions, making recency unusually predictive. Prefix caching nevertheless introduces new challenges, including heavy-tailed session footprints and highly variable miss costs as attention computation grows with sequence length. We introduce the compute-savings ratio and two offline oracles to quantify these effects. Our results show that effective prefix-cache management should retain recency as its foundation while selectively adding quick demotion for one-hit prefixes, compute-aware partial eviction for expensive misses, and capacity-dependent eviction granularity. We will release the traces and simulator to support future research.
Read the original paperMore in Efficient AI
Browse all 55 papers →Decoding Looped Transformers Better for (Almost) Free
Weihao Liu, Huangjie Zheng, Tianrong Chen, Rohit Dilip, Richard He Bai, Yizhu Jiao, Yuyang Wang, Ruixiang Zhang
LoopCD turns the partially computed states of looped Transformers into free guidance, improving accuracy while often cutting inference compute nearly in half.
Scaling Laws for Looped Mixture of Experts
Yanbei Chen, Anirudh Goyal, Raghuraman Krishnamoorthi
This work develops scaling laws that explain how looping and sparse experts can be combined to build more capable models with less training and inference compute.
Disaggregated Quantization: Specializing LLM Prefill and Decode
Andrei Panferov, Maximilian Kleinegger, Sweta Priyadarshi, Tijmen Blankevoort, Dan Alistarh
Disaggregated quantization gives LLM prefill and decode their own specialized weights and formats, improving low-bit accuracy while speeding up first-token generation.