Fine-grained cache eviction cuts delays in long task AI agents
RR-Evict: Fine-Grained Prefix Cache Eviction beyond LRU for Agentic LLM Serving
Distributed, Parallel, and Cluster Computing
Summary
AI systems that talk to users and use tools often keep a history of the entire conversation to work efficiently. But when many conversations happen at once, storing these histories takes up a lot of memory, leading to slowdowns. The paper shows that the common way to clear memory, which removes the oldest histories first, can cause some conversations to slow down a lot when restarted. The authors created a new method that spreads out memory clearing more evenly across conversations, letting more parts of each history stay ready to use and reducing slowdowns. Their method works without needing to guess future needs and cuts the worst delays in half or more.
What this means in practice
- •For cloud ai service operators: Reduce user wait times for AI agents handling multiple interactive tasks by better managing cached conversation histories.
- •For ai platform engineers: Improve efficiency of context reuse in multi-agent large language model serving systems with a scalable cache eviction policy.
Authors
Zaifeng Pan, Chris Wu, Zhengding Hu, Xinwei Qiang, Zhongkai Yu, Yufei Ding
Abstract
LLM-based agents execute long-horizon tasks through repeated model calls interleaved with tool execution and user interaction. As each call extends the history accumulated in previous turns, prefix caching avoids repeated prefill of the agent's entire context. However, the aggregate cache footprint grows with context length and concurrency, forcing serving systems to reclaim cached KV tensors. We identify recency synchronization: accesses to an agent's cached history refresh its cache nodes together, causing least recently used (LRU) eviction to concentrate on a few agents' private histories. When a fully evicted agent returns, it must recompute nearly its entire accumulated context, producing a large time-to-first-token (TTFT) outlier even if most other requests retain substantial cache reuse. We present RR-EVICT, a fine-grained prefix-cache eviction strategy that distributes reclamation across idle agent trajectories. RR-EVICT visits agents in round-robin order and evicts a tail chunk from each, preserving reusable prefixes for more agents when capacity remains for idle state. Returning agents can reuse these partial histories and recompute smaller missing suffixes. The policy requires no prediction of future arrivals or tool latency. We implement RR-EVICT in SGLang and evaluate conversational and coding-agent workloads under colocated and prefill-decode-disaggregated serving. Compared with LRU, RR-EVICT reduces P99 TTFT by up to 75.4% and P99 uncached prompt tokens by up to 65.7%.