Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.28870 · 3 citations · 77 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 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.

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

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.