mlsanityData to 7 Oct 2026

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

arXiv 2609.28870 ↗First posted 24 Sep 2026cs.DC cs.LGcited by 0

New in LLM reasoning; no direction yet. LLM reasoning

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 80 references that are in the map. First posted on arXiv 24 Sep 2026.

Builds on

24 of 80 references.

References · 24

  1. 2025Qwen3 Technical Reportcited by 8,195
  2. 2020Scaling Laws for Neural Language Modelscited by 6,411
  3. 2023Mistral 7Bcited by 3,065
  4. 2024DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelcited by 1,093
  5. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 700
  6. 2024Jamba: A Hybrid Transformer-Mamba Language Modelcited by 390
  7. 2024Reducing Transformer Key-Value Cache Size with Cross-Layer Attentioncited by 122
  8. 2025LMCache: An Efficient KV Cache Layer for Enterprise-Scale LLM Inferencecited by 119
  9. 2023Mixture-of-Experts Meets Instruction Tuning:A Winning Combination for Large Language Modelscited by 65
  10. 2025KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflowscited by 56
  11. 2025Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Livecited by 43
  12. 2026AgencyBench: Benchmarking the Frontiers of Autonomous Agents in 1M-Token Real-World Contextscited by 26
12 more
  1. 2025Strata: Hierarchical Context Caching for Long Context Language Model Servingcited by 25
  2. 2026Long-Horizon-Terminal-Bench: Testing the Limits of Agents on Long-Horizon Terminal Tasks with Dense Reward-Based Gradingcited by 20
  3. 2026State of AI: An Empirical 100 Trillion Token Study with OpenRoutercited by 15
  4. 2026TraceLab: Characterizing Coding Agent Workloads for LLM Servingcited by 14
  5. 2026AutoLab: Can Frontier Models Solve Long-Horizon Auto Research and Engineering Tasks?cited by 11
  6. 2025EVICPRESS: Joint KV-Cache Compression and Eviction for Efficient LLM Servingcited by 9
  7. 2026Agentic Coding in the Wild: Characterizing GitHub Copilot Traces at Production Scalecited by 9
  8. 2026CacheWise: Understanding Workloads and Optimizing KVCache Management for Efficiently Serving LLM Coding Agentscited by 8
  9. 2026Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Cachescited by 3
  10. 2026Multi-Segment Attention: Enabling Efficient KV-Cache Management for Faster Large Language Model Servingcited by 2
  11. 2026SMetric: Rethink LLM Scheduling for Serving Agents with Balanced Session-centric Schedulingcited by 2
  12. 2026PTStore (Prefix Tensor Store): Distributed Prefix Caching and Replication for High Throughput Inference Servingcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Sparse Prefix Caching for Hybrid and Recurrent LLM Serving
  2. 2026PrefixBench-H100: Characterizing Prefix Reuse and Time-to-First-Token in H100 LLM Serving
  3. 2024Marconi: Prefix Caching for the Era of Hybrid LLMs
  4. 2026Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs
  5. 2025TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving
  6. 2026PEEK: Predictive Queue-Informed KV Cache Management for LLM Serving
  7. 2026Cache-Aware Prompt Compression:A Two-Tier Cost Model for LLM API Caching
  8. 2026CacheRoute: Planned Prefix-Affinity Routing for Large-Scale LLM Serving