PaperlayerView exact revision on arXiv

Source-linked AI summary

RR-Evict: Fine-Grained Prefix Cache Eviction beyond LRU for Agentic LLM Serving

Zaifeng Pan, Chris Wu, Zhengding Hu, Xinwei Qiang, Zhongkai Yu, Yufei Ding

arXiv:2609.32278v2cs.DC

TL;DR

Long-horizon agents synchronize cache recency across private histories, so LRU can concentrate eviction and leave returning agents with costly recomputation. RR-EVICT distributes tail-chunk reclamation across idle trajectories; in tested workloads, it reduces P99 TTFT by up to 75.4% and P99 uncached prompt tokens by up to 65.7% versus LRU.

  • Problem

    Growing context and concurrency create GPU cache pressure, while synchronized recency in agent histories can make LRU concentrate eviction on a few trajectories.

    Source: §1 · p. 1, §3.1 · p. 4

  • Method

    RR-EVICT reclaims tail chunks from idle agent trajectories in round-robin order, preserving partial cached prefixes across agents.

    Source: §1 · p. 2

  • Results

    P99 TTFT falls by up to 75.4% and P99 uncached prompt tokens by up to 65.7% with RR-EVICT versus LRU.

    Source: §1 · p. 2

  • Takeaways & Limitations

    When capacity remains for idle state, returning agents can reuse partial histories and recompute only missing suffixes without predicting future execution.

    Source: §1 · p. 2

    Direct round-robin can retain completed trajectories’ cached prefixes through many eviction rounds, wasting memory that could benefit live agents.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

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

1 INTRODUCTION

Long-horizon agents create growing cache demand, while synchronized recency can concentrate LRU eviction on a few agents and produce tail-latency spikes. RR-EVICT spreads eviction across idle trajectories to retain partial histories, and the evaluated workloads show lower tail metrics than LRU.

1 INTRODUCTION

  • Synchronized accesses refresh an agent’s surviving cache path together, giving its private nodes nearly identical recency and leading LRU to concentrate cache loss on a few trajectories.A fully evicted agent may then recompute nearly its entire history, causing severe TTFT spikes despite reuse for most other requests.Source: §1 · p. 2
  • RR-EVICT reclaims tail chunks from idle agents in round-robin order, preserving valid cached prefixes while distributing memory reclamation across histories.The approach is intended to retain partial histories for more agents and avoid predicting future arrivals or tool latency.Source: §1 · p. 2
  • P99 TTFT falls by up to 75.4% and P99 uncached prompt tokens by up to 65.7% with RR-EVICT versus LRU.The evaluation covers conversational and coding-agent workloads in colocated and prefill–decode-disaggregated configurations.Source: §1 · p. 2
  • The paper identifies recency synchronization as the reason node-level LRU can concentrate eviction and produce large tail-TTFT outliers in long-horizon agent workloads.It characterizes when preserving partial prefixes can reduce tail recomputation.Source: §1 · p. 2
  • The evaluation reports improvements over both LRU and completion-aware LRU across tested configurations.Comparisons with completion-aware LRU isolate the additional benefit of distributing eviction across live histories.Source: §1 · p. 2

2 BACKGROUND

Agent requests are stateful and intermittent: each turn builds on an evolving context, with tool execution or user feedback between requests. Prefix caching reuses the matching history, while the shared cache pool must accommodate private histories across concurrent agents.

Multi-turn agent workloads

  • An agent turn reasons over the current context and produces a response or tool call; tool execution or waiting for user feedback can separate turns.The returned observation is appended to the next request along with the preceding history, so context grows while retaining most prior tokens.Source: §2 · p. 3

Prefix caching for multi-turn agents

  • Prefix caching retains KV tensors across requests and reuses them when a later request begins with the same token sequence, reducing prefill to newly appended tokens.Longer prefix-cache hits avoid more recomputation and reduce TTFT.Source: §2 · p. 3
  • Serving systems share a cache pool for reusable KV tensors, but growing private histories and concurrent-agent demand can exceed GPU memory capacity.The eviction policy determines how much history remains reusable when agents resume and thus affects next-turn prefill latency.Source: §2 · p. 3

3 RR-EVICT: FINE-GRAINED PREFIX-CACHE EVICTION

The section explains why synchronized recency makes LRU concentrate cache loss on individual idle agents, then presents RR-EVICT’s round-robin tail eviction. Its analysis compares recomputation distributions and identifies when distributing eviction can improve tail latency.

3.1 INEFFICIENCY OF LRU EVICTION

  • Synchronized access refreshes an agent’s private cache nodes together, so successive LRU evictions can remove most or all of one idle agent’s history.On return, that agent must prefill nearly its entire history, creating a TTFT spike even when aggregate cache hit rate remains high.Source: §3.1 · p. 4

3.2 RR-EVICT: ROUND-ROBIN TAIL EVICTION

  • RR-EVICT orders eligible idle trajectories round-robin and reclaims one tail chunk per trajectory, preserving a contiguous cached prefix when capacity permits.A chunk may be a whole leaf or a suffix within one; the process continues until the requested memory is released.Source: §3.2 · p. 4
  • When completion signals are unavailable, recency tiering combines cross-tier LRU ordering with round-robin eviction within tiers, but the evaluation does not test tiering.With completion signals, the backend can instead immediately release a completed trajectory’s unshared cache.Source: §3.2 · p. 5

3.3 ANALYTICAL COMPARISON OF LRU AND RR-EVICT

  • The analysis assumes equal-sized private prefixes, no cross-agent sharing, and a fluid estimate of active trajectories; deployments must account for bursts in the active set.The stated useful capacity regime is n_a < m < n.Source: §3.3 · pp. 5–6
  • E[Xπ] = q for both policies, but LRU assigns full recomputation to a fraction q of returning agents while ideal round-robin spreads it equally.When prefill latency is approximately proportional to uncached prefix length, round-robin reduces the worst-case old-prefix recomputation component from 1 to q; it does not improve every quantile.Source: §3.3 · p. 6
  • RR-EVICT is most useful between active-demand capacity and full capacity, where active contexts fit but concentrated LRU misses can still affect the tail.As capacity approaches either boundary, meaningful idle-state retention vanishes or full-prefix misses under LRU become too rare to affect a fixed tail percentile.Source: §3.3 · p. 6

4 EVALUATION

The evaluation replays conversational and coding-agent workloads against LRU variants and finds lower tail metrics with RR-EVICT across colocated and PD-disaggregated configurations. Trace and request-level analyses identify when idle-state eviction is needed and connect cache misses with TTFT tails.

Experimental setup

  • Experiments replay recorded traces while varying admitted-agent concurrency, comparing LRU, completion-aware LRU, and RR-EVICT with 1,024-token eviction chunks.The evaluation uses Qwen3-Coder-30B-A3B-Instruct on 222 τ 2-bench trajectories and Qwen3-8B on SWE-bench; reported metrics are P99 TTFT and P99 uncached prompt tokens.Source: §4 · pp. 6–7

Results

  • P99 TTFT and P99 uncached prompt tokens fall by up to 75.4% and 65.7% on τ 2-bench, and 60.7% and 60.8% on SWE-bench, versus LRU.Figure 3 covers conversational workloads across concurrency levels; Figure 6 covers Qwen3-8B on SWE-bench under 1P3D disaggregation.Source: Figure 3 · p. 7, §4 · pp. 7, 9, Figure 6 · p. 8

Trace-level memory pressure

  • At concurrency 80, active KV demand fits capacity while active plus live-idle demand exceeds it, requiring eviction from live idle trajectories.This is the regime in which RR-EVICT can spread losses across idle trajectories rather than fully evicting a few histories.Source: Figure 4 · p. 7, §4 · pp. 7–8

Uncached-token and TTFT distributions

  • At concurrency 80, RR-EVICT shortens the extreme uncached-token tail and shifts the TTFT tail lower, with a more pronounced TTFT improvement.The passage says this larger shift is consistent with avoiding exceptionally long prefills that would otherwise cause head-of-line blocking and additional queueing; some long misses remain.Source: §4 · p. 8, Figure 5 · p. 8

PD-disaggregated coding agents

  • On SWE-bench, RR-EVICT reduces P99 TTFT and P99 uncached tokens by up to 60.5% and 56.2%, respectively, versus LRU + Completion Signals across evaluated concurrency levels.Source: Figure 6 · p. 8, §4 · p. 9

5 RELATED WORK

Prior work addresses general serving efficiency and agent execution structure, but the paper identifies agentic KV-cache management as a distinct focus. RR-EVICT distributes cache loss without workflow graphs or tool-duration predictors.

LLM serving systems

  • General serving work optimizes scheduling, execution, and KV management, while cache systems address fragmentation, prefix sharing, cross-turn retention, or storage capacity.The section contrasts these systems with long-running agents whose private histories grow across interactions.Source: §5 · p. 9

Agent serving systems

  • Agent-serving systems optimize workflow execution, scheduling, prefill overlap, overload control, or self-evolution, but do not specifically optimize KV-cache management for agentic workloads.Source: §5 · p. 9
  • Some cache-retention approaches rely on tool-duration estimates or application information, whereas RR-EVICT distributes cache loss across idle agents without those signals.The passage notes that such signals may be unavailable or inaccurate in practice.Source: §5 · p. 9

6 CONCLUSION AND DISCUSSION

The paper concludes that synchronized cache accesses make LRU eviction concentrate on a few agents, while RR-EVICT spreads tail eviction across idle agents. Its evaluation remains limited to short idle intervals and GPU-resident prefix caches.

Conclusion

  • Across tested colocated and PD-disaggregated workloads, RR-EVICT reduces P99 TTFT by up to 75.4% and P99 uncached prompt tokens by up to 65.7% relative to LRU.The conclusion identifies the useful regime as one where active contexts fit but all live histories do not.Source: §6 · p. 9

Limitations

  • The evaluation covers relatively short idle intervals and prefix caches resident in GPU HBM, leaving longer waits and CPU-memory or SSD spill for future evaluation.Future work would account for KV transfer and reload costs.Source: §6 · p. 9

AI USE STATEMENT

The authors report using generative AI tools for language editing, document organization, code implementation, and plotting scripts.

AI use statement

  • The authors state that they designed the method and experiments, produced the measurements, verified the claims, and take responsibility for the manuscript.Source: AI USE STATEMENT · p. 10

Related papers

Loading 2609.32278v2…