Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.28870 · 4 citations · 79 references
Computer Science

TL;DR

This work studies production traces from two companies and evaluates 14 eviction algorithms across HBM-constrained and large memory-pool settings to show that effective prefix-cache management should retain recency as its foundation while selectively adding quick demotion for one-hit prefixes.

Abstract

Long-running LLM applications and autonomous agents repeatedly send growing context, making prefix caching critical for reducing prefill cost. This raises a fundamental question: do decades of traditional cache-management techniques transfer directly to agentic and conversational LLM serving? We analyze production traces comprising over 20 billion processed tokens and evaluate 14 eviction algorithms across capacity-constrained HBM and large memory-pool settings. We find that simple Least Recently Used (LRU) is surprisingly robust, offering competitive performance against sophisticated traditional policies, though substantial headroom to Belady's optimum remains. The reason is structural: prefix reuse is dominated by the steady pacing of active sessions, making recency an unusually strong predictor for eviction. Nevertheless, prefix caching diverges from traditional workloads in ways that recency ignores, notably the prevalence of single-turn requests, extreme session footprint skew, and highly non-uniform miss costs because attention computation scales with token depth. To close the gap to optimality, we establish several design principles for prefix-cache management: keeping recency as the baseline while incorporating quick demotion to filter one-hit prompts, compute-aware eviction to prioritize expensive misses, and capacity-adaptive eviction granularity. Our traces and simulator are publicly available.

View source

Similar papers

#artificial intelligence Preprint Oct 2026

AvoKV-E: Payload-Aware KV Cache Eviction for Long Reasoning

AvoKV-E is introduced, a training-free eviction policy that first delays eligibility for recent states and then ranks eligible entries using candidate-normalized read pressure, key redundancy, and value-payload potential, which shows that long-reasoning KV eviction should preserve not only keys that are likely to be re...

Han Yu, Wen-Hui Zhu, Xi-Wen Chen et al. · 0 citations
Open access Aug 2026

Rethinking Cache Eviction: Low-Overhead and Precise Learning-based Design

Caches reduce latency and network traffic, and cache performance largely depends on the eviction policy. Eviction effectiveness is typically measured by byte and object miss ratios. Although learning-based eviction policies can reduce misses, their high computational overhead limits practical deployment. This work pres...

Qian Wang, Chang Xu, Wenbin Zhou et al. · 0 citations
Preprint Aug 2026

Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders

The cross-encoder study shows that thresholds do not transfer between embedding models, and LFU is the strongest simple default in this protocol; deployment decisions should first establish answer validity and then test sub-point policy differences with exact search.

Y. Kulkarni, Shubham Harkare, A. Babu · 0 citations
Open access Sep 2026

Buoy: Efficient and Effective Cache Replacement for Prefix Caching

Modern large language model (LLM) systems widely employ prefix caching to enable key-value (KV) cache reuse across different queries to minimize inference costs. At the heart of prefix caching is the replacement algorithm, which is crucial for managing limited cache space across the GPU–CPU memory hierarchy. However, t...

Liangshaowei Wang, Ran-Jun Jia, Kai Wang et al. · 0 citations

FairCache: Demystifying Cache-Induced Unfairness in Multi-Tenant Large Language Model Serving

Large language models (LLMs) increasingly rely on context caching to enhance serving efficiency. However, this optimization inadvertently compromises fairness in multi-tenant LLM serving systems. Existing fair schedulers, which account only for compute resources, are unable to handle the multi-dimensional resource dema...

Zhuo-Yan Bai, Bin Gao, Fei Xu et al. · 0 citations
Sep 2026

RR-Evict: Fine-Grained Prefix Cache Eviction beyond LRU for Agentic LLM Serving

This work presents RR-EVICT, a fine-grained prefix-cache eviction strategy that distributes reclamation across idle agent trajectories, and implements RR-EVICT in SGLang and evaluates conversational and coding-agent workloads under colocated and prefill-decode-disaggregated serving.

Zai-Feng Pan, Chris Wu, Zheng-Ding Hu et al. · 2 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.