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.
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
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.· ACM Transactions on Computer...· 0 citations
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
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.· Proceedings of the ACM on Ma...· 0 citations
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.· IEEE Transactions on Paralle...· 0 citations
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.· arXiv.org· 2 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
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.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026