acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
LLM Serving, KV Cache, Agent

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_taS2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes RR-Evict, an eviction algorithm that evicts the tail of each trajectory in a round-robin manner to achieve lower tail TTFT. In comparison with LRU that may evict the whole trajectory, the experiments show that RR-Evict can reduce P99 TTFT by up to 75.4% and P99 uncached prompt tokens to 65.7%.

Critical strengths
  • The proposed policy is simple to implement and does not require predictions of future request arrivals or tool execution latency.
  • Addresses a practical problem in agentic LLM serving. Conventional LRU eviction may lead to high tail TTFT.
  • Good implementation brings good evaluation results.
Critical weaknesses
  • Limited novelty and technical contribution. The core idea of RR-Evict is straightforward, and is to reduce the workload of the long-tail tasks.
  • The round-robin policy ignores workload heterogeneity. The policy treats idle agent trajectories uniformly, without considering their request arrival frequencies or expected time until the next invocation. Neither does the author consider the non-linear different prefill cost when the length is different. The analytical model is also weak to this.
  • Insufficient evaluation. The evaluation does not reveal: (1) whether it has a impact on the average TTFT statistically, which may happen since the concurrency of prefill may drop; (2) omit other implementations such as T-LRU [1], ECE [2], Continnum [3], or Random Attention [4] (which may be considered as concurrent work); (3) the performance of recency tiering; (4) different model types, especially the models that involve linear attentions or GDN, such as Qwen 3.8, Kimi K3 and GLM-5.3 Flash; (5) the performance of RR-Evict in cases of context compactation.

[1] W. Zhang, Y. Li, et al. Tail-Optimized Caching for LLM Inference. NeurIPS 25.

[2] Y. Ren, L. Chen, et al. Transcending Cost-Quality Tradeoff in Agent Serving via Session-Awareness. NeurIPS 25.

[3] H. Li, R. He, et al. Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live. Arxiv 25.

[4] H. Wang, J. Qiu, et al. Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning. Arxiv 26.

Questions for authors
  1. How's the RR-Evict's performance compared to other algorithms listed in the Weaknesses ([1-4]) under your current setting?
  2. Can you please evaluate how recency-tiering works with the cases where no explicit stop notification exist? And can you please study how RR-Evict performs in its current form when context compactation happens?
  3. How sensitive is RR-Evict to heterogeneous request arrival frequencies? If some agents resume frequently while others remain idle for long periods, does uniform eviction still improve tail TTFT?
  4. What is the overhead of RR-Evict? How robust are the results to eviction chunk size and memory pressure? The evaluation uses 1024-token eviction chunks. How sensitive are the results to this choice? If possible, I suggest the authors also evaluate other models as detailed in the Weakness 3.
Reviewer_ph6HOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces RR-Evict algorithm, a prefix-cache eviction method for multi-turn LLM agents.

  1. The paper's motivation is that LRU can repeatedly evict cache nodes from the same agent, causing large prefill costs when that agent returns. While the RR-Evict algorithm removes small chunks from different idle agents in round-robin order to preserve more reusable prefixes.
  2. The method is implemented in SGLang and evaluated on conversational and coding-agent workloads, showing up to a 75.4% reduction in P99 TTFT compared with LRU.
Critical strengths
  1. The paper discusses a meaningful problem in agentic LLM serving. The paper is easy to read and follow the idea.

  2. The method is simple which is good and has no other dependencies. The experiments in SGLang show meaningful improvements in tail latency in two types of agent workloads.

Critical weaknesses
  1. The contribution of round-robin eviction is not well analyzed. RR-Evict uses 1,024-token eviction chunks, while the LRU baseline is described as evicting leaf nodes. It is unclear whether both methods use the same eviction granularity? Without a fine-grained LRU baseline, it is difficult to tell how much of the improvement comes from round-robin selection rather than smaller eviction chunks. Further experiments would help clarify where the improvements come from.

  2. The method is simple which is good, but the evaluation cannot tell if the method can be useful in broader real applications. Two problems: 1. The analysis assumes equal-sized agent histories and uniform reuse, while in real world, agents may differ greatly in context length and return frequency. 2. The experiments focus mainly on P99 under a limited set of concurrency settings. Since RR-Evict spreads cache eviction across more agents, it is useful to understand if the improved tail latency comes at the cost of higher average latency or lower throughput.

Questions for authors
  1. Do LRU and RR-Evict use the same eviction chunk size? If not, could you compare RR-Evict with a fine-grained LRU baseline using the same 1,024-token chunks?

  2. How does RR-Evict affect other metrics, like mean TTFT, median TTFT, and throughput? Does reducing P99 TTFT increase latency for typical requests?

  3. Does RR-Evict still perform well when agents have different context lengths and return frequencies? Could you also show how cache eviction is distributed across agents under LRU and RR-Evict?

Reviewer_5piTOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work studies the prefix-cache eviction strategy for long-horizon agent workflows. When the GPU memory is about to run out, the KV cache needs to be evicted. The naive way of doing it is to evict the KV from the least active agent, and when this agent comes back, it needs to re-prefill, which causes TTFT spike as observed. The proposed method, RR-Evict, groups idle leaves in radix cache and evict the tail chunks in a round-robin fashion until the context is no longer exploding the memory. In this case, the cache loss is spread out across all agents and therefore no substantial big TTFT spike appears when the least active agent needs to continue with a recomputation. With a fluid model, they show that round-robin lowers the worst case from a full prefix to a fraction of the full. Experiments are conducted in SGLang with replay recorded traces of tau2 bench and SWE-bench on Qwen3-8B under PD disaggregation. Relative to LRU strategy, RR-Evict reduces p99 TTFT by up to 75% and p99 uncached tokens by up to 65%.

Critical strengths
  1. The problem itself is a real problem and clearly explained. Synchronized recency turns node-level LRU in radix tree to agent-level eviction, which helps with the worst case TTFT spike.
  2. The policy is simple to implement and has been tested in SGLang with real agents and workflow (replay).
Critical weaknesses
  1. The paper focuses on reporting only the tail metrics and I do not see the mean cost. And the advantage of this compared to LRU, to my understanding, heavily depends on the actual case of agent execution. No fixed strategy (either round-robin or least-recency) can be the best under different agentic flow.
  2. The analysis assumes the case that recomputation is linear in the number of tokens. However, in real cases, agents might have context lengths that are so different from each other, and the cost for recomputing the tail will be drastically different based on the attention type.
  3. A simple cost-aware strategy might be a good baseline to compare with, where the cost model can be calculated based on the agent's model type, context length, latency, etc. This would be a good dynamic baseline. Even a random eviction might be a good one to include.
  4. The evaluation coverage is a bit limited:
  • Single model over three concurrency levels.
  • Chunk size fixed at 1024 tokens.
  • Consider other base cache types like HiCache, LMCache, Mooncake, etc, beyond HBM-resident caches.
  1. The main contribution is a simple eviction algorithm with a theory based on fluid model that focuses on one percentile argument. It stands as a good eviction strategy to a serving engine but does not seem to provide more insights to the general inference community.
Questions for authors
  1. What are the mean TTFT, total prefill tokens or FLOPs, and end-to-end throughput or task completion time for each policy in Figures 3 and 6? Does RR-Evict increase total recomputation?
  2. How does RR-Evict compare with other eviction strategies mentioned above like random eviction, per-agent proportional allocation, and context / cost aware strategies? I believe a more dynamic and agent-aware approach would be more insightful.
  3. How does RR-Evict perform without completion signals, using recency tiering as proposed in section 3.2, compared with plain LRU?
  4. How are leaves grouped into trajectories when agents share long prefixes, and how does the policy behave with forked or sub-agent trajectories?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.