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