Agentic lLM serving improves speed by better KV cache eviction

Rethinking KV Cache Eviction for Agentic LLM Serving

Distributed, Parallel, and Cluster Computing

Summary

Large language models use a key-value (KV) cache to remember past conversation tokens, but this cache can get full and slow down the system. Existing methods usually remove tokens from the end of the conversation history, which wastes time because recent tokens rely on all previous context for attention. The authors propose a new way to keep the end of the conversation intact and remove older tokens from the beginning instead. This approach, implemented in their system Penelope, reduces the delay before the first answer and overall response time by efficiently managing the cache on both GPUs and CPUs.

What this means in practice

  • For llm platform engineers: Optimize latency and throughput in serving conversational agents by preserving cache suffixes and evicting older history from the cache.
  • For cloud gpu infrastructure teams: Improve GPU-CPU memory management for large language models to reduce computing delays during multi-turn interactions.

Authors

Jiakun Fan, Han Meng, Yuxuan Xia, Hao Mark Chen, Dong Li, Dimitrios S. Nikolopoulos

Abstract

Key-value (KV) caches impose substantial memory pressure on large language model serving systems, requiring cache eviction when capacity is insufficient. Existing mechanisms typically evict KV from the ends of cached sequences to preserve prefix sharing across requests. However, agent workloads repeatedly reuse long histories across successive turns. Recomputing the KV cache for tokens near the end of a sequence is substantially more expensive than for earlier tokens because their attention computation involves longer histories. To address this problem, we propose preserving shared prefixes and evicting the KV cache from the beginning of the remaining history while retaining the cached suffix. We build Penelope around this strategy by co-designing the eviction policy, KV recomputation, and unified GPU-CPU cache management. Returning requests reuse the KV cache retained in GPU or CPU memory and recompute only missing segments while preserving reuse of the cached suffix. We implement Penelope in SGLang and evaluate it on three Qwen3 model sizes using real agent traces. Compared with SGLang, Penelope reduces mean time to first token by up to 60% and job completion time by up to 37% with a GPU-only cache, and by up to 76% and 60% with a two-tier GPU-CPU cache.