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.
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%.
Agentic applications generate multi-turn sequences of LLM requests, with each new turn extending the context accumulated from prior interactions and tool calls. Prefix caching reuses the KV cache of earlier turns and avoids redundant prefill, but routing every turn to its cache-affine instance can create severe local q...
Lan-Cheng Zou, Bo-Wen Li, Wei Mao et al.· 0 citations
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.
Long-running agents repeatedly call an LLM while retaining most of their document window, evicting old documents, and appending new ones. These rolling updates break exact prefix caching and motivate non-prefix KV-cache reuse with selective recomputation. We show that persistent KV-cache reuse with selective recomputat...
Tiffany Gu, An-Nie Guan, Man-Shu Huang et al.· 0 citations
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
A Task-Oriented Prefix-Aware Scheduler that jointly decides which agent prefixes to keep in the cache and which requests to schedule for execution and scores candidate post-decision states by trading off the expected reduction in each task's longest remaining service path against the near-term benefit of downstream pre...
Hongqiu Ni, Han Tian, Chi Zhang et al.· 3 citations
Results show that separating reusable schema encoding from selective resource access substantially reduces agentic inference costs with limited effectiveness loss.
Yichu Fang, Si-Tong Wei, Hao-Zhe Hu et al.· 3 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.