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

arXiv: https://arxiv.org/abs/2609.28870 · HTML: https://mlsanity.com/paper/2609.28870/

## Key facts

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

## Placed in

- LLM reasoning

## Builds on (most cited first, 24 of 24)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [Jamba: A Hybrid Transformer-Mamba Language Model](https://mlsanity.com/paper/2403.19887/) (2024)
- [Reducing Transformer Key-Value Cache Size with Cross-Layer Attention](https://mlsanity.com/paper/2405.12981/) (2024)
- [LMCache: An Efficient KV Cache Layer for Enterprise-Scale LLM Inference](https://mlsanity.com/paper/2510.09665/) (2025)
- [Mixture-of-Experts Meets Instruction Tuning:A Winning Combination for Large Language Models](https://mlsanity.com/paper/2305.14705/) (2023)
- [KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflows](https://mlsanity.com/paper/2507.07400/) (2025)
- [Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live](https://mlsanity.com/paper/2511.02230/) (2025)
- [Long-Horizon-Terminal-Bench: Testing the Limits of Agents on Long-Horizon Terminal Tasks with Dense Reward-Based Grading](https://mlsanity.com/paper/2607.08964/) (2026)
- [AgencyBench: Benchmarking the Frontiers of Autonomous Agents in 1M-Token Real-World Contexts](https://mlsanity.com/paper/2601.11044/) (2026)
- [Strata: Hierarchical Context Caching for Long Context Language Model Serving](https://mlsanity.com/paper/2508.18572/) (2025)
- [State of AI: An Empirical 100 Trillion Token Study with OpenRouter](https://mlsanity.com/paper/2601.10088/) (2026)
- [TraceLab: Characterizing Coding Agent Workloads for LLM Serving](https://mlsanity.com/paper/2606.30560/) (2026)
- [AutoLab: Can Frontier Models Solve Long-Horizon Auto Research and Engineering Tasks?](https://mlsanity.com/paper/2606.05080/) (2026)
- [Agentic Coding in the Wild: Characterizing GitHub Copilot Traces at Production Scale](https://mlsanity.com/paper/2608.00101/) (2026)
- [EVICPRESS: Joint KV-Cache Compression and Eviction for Efficient LLM Serving](https://mlsanity.com/paper/2512.14946/) (2025)
- [CacheWise: Understanding Workloads and Optimizing KVCache Management for Efficiently Serving LLM Coding Agents](https://mlsanity.com/paper/2606.16824/) (2026)
- [Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches](https://mlsanity.com/paper/2605.18825/) (2026)
- [Multi-Segment Attention: Enabling Efficient KV-Cache Management for Faster Large Language Model Serving](https://mlsanity.com/paper/2606.02964/) (2026)
- [SMetric: Rethink LLM Scheduling for Serving Agents with Balanced Session-centric Scheduling](https://mlsanity.com/paper/2607.08565/) (2026)
- [PTStore (Prefix Tensor Store): Distributed Prefix Caching and Replication for High Throughput Inference Serving](https://mlsanity.com/paper/2607.22648/) (2026)

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