Source-linked AI summary
Learning Agent Execution for KV-Cache Management in Agentic Serving
Rui Zhang, Chaeeun Kim, Shaoting Feng, Kuntai Du, Yuhan Liu, Yi Zhong, Cheng-Wei Ching, Junchen Jiang, Liting Hu
TL;DR
Reactive KV-cache management can miss reusable contexts in multi-agent LLM serving. CacheScout learns agent execution transitions online to guide eviction and prefetching, improving cache reuse and serving performance across representative workloads.
Problem
Existing prefix caches and replacement policies lack agent-level execution semantics needed to identify and protect contexts likely to be reused.
Method
CacheScout learns agent transitions online and uses predicted future execution to guide KV-cache eviction and proactive prefetching without modifying the serving stack.
Results
18–45% lower mean TTFT across four representative workloads, alongside 29–38% lower mean per-turn latency and 19–57% higher peak throughput.
Takeaways & Limitations
Incorporating agent execution semantics into KV-cache management is an effective and practical approach for efficient multi-agent LLM serving.
Takeaways & Limitations
Cache eviction predictions must be extremely fast because eviction occurs on the serving hot path, where millisecond-scale inference can outweigh saved prefill computation.
Abstract
from arXiv · showhide
Multi-agent LLM systems have emerged as an important deployment paradigm for AI services, where each user request is decomposed into a sequence of specialized agents. Across these workflows, every agent repeatedly executes a fixed context consisting of system prompts, tool definitions, and few-shot examples, creating substantial opportunities for KV-cache reuse. Existing LLM serving systems, however, manage KV-cache reactively using prefix caching and recency-based replacement, causing reusable agent contexts to be evicted before their next invocation and forcing repeated recomputation. We present CacheScout, an agent-aware KV-cache runtime layer for multi-agent LLM serving. The key insight is that future KV-cache reuse is governed by agent execution semantics rather than cache recency alone. CacheScout captures these semantics by learning agent execution transitions online, without requiring predefined workflow graphs or offline training, and uses the learned execution model to guide both cache eviction and proactive prefetching while leaving the serving critical path unchanged. We implement CacheScout on top of vLLM. Across representative real-world multi-agent workloads, CacheScout improves KV-cache hit rate by 10-18 percentage points, reduces mean TTFT by 18-45%, lowers mean per-turn latency by 29-38%, and increases peak throughput by up to 57%. These benefits also generalize to larger models, reducing TTFT by up to 54% while sustaining 37% higher throughput.
1 Introduction
Multi-agent LLM serving repeatedly encounters reusable agent contexts, but reactive, recency-based KV-cache management can evict them before reuse. CacheScout learns runtime agent transitions to enable lightweight, agent-aware eviction and prefetching, improving cache efficiency and serving performance.
- Motivation: Multi-agent applications decompose user requests into subtasks handled by specialized agents that collaborate through runtime workflows.Examples include software engineering assistants, enterprise knowledge assistants, and deep research agents.
- Motivation: Repeated agent invocations reuse fixed contexts containing system prompts, tool definitions, skills, and examples, creating substantial KV-cache reuse opportunities.The travel-planning example repeatedly invokes a Travel Agent with the same fixed context.
- The problem: Reactive prefix caching and recency-based replacement can evict an agent’s reusable KV blocks before its next invocation, forcing prefix recomputation.Serving engines track accessed anonymous blocks but cannot identify which agent owns or will reuse them.
- Our solution: CacheScout observes runtime agent execution, learns transitions online, and uses predicted future agents to guide KV-cache eviction and prefetching without predefined workflow graphs or offline training.Its design includes an online first-order Markov transition learner and survival-probability-based eviction.
- Summary of results: 10–18 percentage points higher KV-cache hit rate, 18–45% lower mean TTFT, 29–38% lower mean per-turn latency, and 19–57% higher peak throughput are achieved on four workloads atop vLLM.The evaluation uses a six-agent supervisor framework with Llama-3.1-8B-Instruct and compares CacheScout against vanilla vLLM and Continuum.
2 Motivation and Challenges
Multi-agent workflows create concentrated KV-cache reuse in recurring agent anchors, but reactive, content-based caches lack the semantic and execution knowledge needed to preserve and prefetch them. Runtime coordination is sufficiently structured for lightweight online prediction, yet its variability and serving-critical-path constraints rule out static graphs and heavyweight learning.
- Challenge #1: Semantic gap between agents and KV blocks: Existing prefix caches react to requests and replace content-addressed KV blocks using past accesses, without knowing the producing agent or likely future invocation.This semantic gap prevents cache management from exploiting agent-level reuse opportunities before reuse occurs.
- Reuse concentration: 43–60% of every prompt remains recurring agent-anchor content even a dozen turns into a session, making anchors the highest-value KV blocks to protect.Agent anchors are reused more frequently than session-specific history and occupy a large fraction of each prompt.
- Execution predictability: 57–86% is the demonstrated predictability range: conditioning on the current agent explains 57% of next-agent uncertainty, while online successor counting reaches 76–86% top-1 accuracy within 50 dispatches.The online predictor requires no offline training and supports proactive cache management.
- Challenge #2: Dynamic execution without a static graph: R = 1.0, 0.78, and 0.57 characterize Pipeline, Debate, and SelectorGroupChat, showing that runtime coordination behavior—not the framework alone—determines execution structure.Because transition matrices vary across coordination topologies, transition models must be learned online rather than specified offline.
- Challenge #3: Prediction under serving-system constraints: Cache eviction occurs on the serving critical path whenever GPU memory is constrained, so prediction must meet production latency budgets without heavyweight feature extraction, inference, or retraining.This constraint motivates lightweight runtime execution modeling.
3 Design
CacheScout adds an independent KV-cache runtime layer that learns agent execution transitions online and uses them to guide cache retention and proactive preparation. It preserves existing agent-framework and serving-engine responsibilities while influencing cache management through lightweight metadata.
- Runtime architecture: CacheScout separates cache intelligence into a runtime layer that learns agent interactions, predicts likely next agents, and translates predictions into cache decisions.The layer sits between the agent framework and serving engine rather than embedding agent semantics into either component.
- Transition learning: The Transition Learner models execution as an online first-order Markov chain, adapting to dynamic routing without predefined workflow graphs or offline training.Each dispatch updates one counter and one transition-matrix row, giving constant update cost and bounded state.
- Transition learning: CacheScout uses local transitions because cache management needs to anticipate the next scheduling decision rather than predict an entire workflow trace.The learned next-agent distribution is obtained from the current agent’s transition-matrix row.
- Survival scoring: CacheScout approximates near-future anchor reuse by pruning low-confidence transitions and using BFS hop distance in the sparse execution graph as a survival proxy.Anchors expected to be revisited sooner receive higher survival scores.
- Survival scoring: Each KV block’s eviction score combines predicted survival, recency decay, and reconstruction cost, with lower-scoring blocks evicted first.The multiplicative score represents expected prefill work lost when evicting a block.
- Background prefetching: The Background Prefetch Coordinator proactively warms high-value agent anchors during idle periods, completing CacheScout’s learned retention-and-prefetch loop.Prefetching addresses anchors that were evicted or have not yet been constructed.
4 Implementation
CacheScout is implemented as a lightweight vLLM runtime layer that connects execution-aware cache management through four primitives and online execution data structures. It integrates with the existing serving pipeline, adding limited hooks without changing core kernels or allocators.
- Runtime layer: CacheScout adds approximately 2,300 lines of runtime logic and an 800-line patch on top of vLLM v0.11’s V1 engine.The runtime exposes ObserveTouch(), Predict(), ScoreBlock(), and Warmup().
- Runtime hooks: Prefix matching fingerprints each request from its own prefix block hashes, allowing fingerprint changes to signal agent dispatches without framework cooperation.ObserveTouch() updates transition statistics and the block-to-agent mapping at dispatch time.
- Runtime state: Four runtime data structures total under 25 KB: an online transition matrix, sparse execution graph, hop-distance table, and block-to-agent mapping.Transition counts update incrementally, while graph and hop-distance data refresh only when the current agent changes; eviction performs one cached score evaluation.
- Pipeline integration: CacheScout reuses vLLM’s execution pipeline without modifying attention kernels, memory allocators, schedulers, or block hashing.Background warmup uses a standard inference request, integration reuses LMCache and CPU offloading, and enablement is controlled by one environment variable.
5 Evaluation
Across four dynamically routed multi-agent workloads, CacheScout improves KV-cache reuse and serving performance over vanilla vLLM, with predictive eviction providing the primary gains and prefetch adding workload-dependent benefits. These improvements generalize to larger models and varying cache capacities while incurring negligible coordinator memory overhead.
- Overall effectiveness: CacheScout improves KV-cache hit rate by 10–18 percentage points and reduces mean TTFT by 18–45% across four representative workloads.The workloads use a common six-agent supervisor framework with dynamic LLM-selected routing.
- Overall effectiveness: CacheScout reduces mean per-turn latency by 29–38% and increases peak throughput by 19–57% across all four workloads.Its throughput advantage continues under load after vanilla vLLM saturates its KV-cache.
- Component ablation: Predictive eviction alone increases KV-cache hit rate by 18–22 percentage points, while background prefetch alone adds at most one percentage point.Combined execution-aware eviction and warmup further reduce GAIA per-turn latency by 28% over eviction alone, from 347 to 251 ms.
- Model scale: On the 235B-parameter Qwen3 model, CacheScout improves KV-cache hit rate by 7–13 percentage points and reduces mean TTFT by 33–54%.On SWE-bench, mean per-turn latency falls by 26–36%, while throughput rises from 5.2 to 7.2 turns/s (+37%).
- Robustness: CacheScout maintains an 86–87% KV-cache hit rate as GPU cache capacity varies from 100 to 200 blocks, compared with vanilla vLLM’s 64.4–76.6%.Budgets below the workload’s approximately 93-block maximum request footprint are excluded because they cannot admit every request.
- Robustness and overhead: Disabling the adaptive prefetch gate increases per-turn latency by up to 22% at small cache sizes, whereas coordinator state remains below 25 KB with 24 agents.The gate prevents unnecessary warmup from competing with foreground inference, and coordinator state converges quickly as execution history accumulates.
6 Related Work
Prior agent-aware KV-cache systems use developer annotations, framework-provided execution graphs, or trained predictors to anticipate reuse. CacheScout instead learns per-workload execution transitions online and targets agent-level reuse across session boundaries, complementing per-block KV-cache optimizations.
- DAG-aware KV-cache management: DAG-aware systems such as KVFlow, SAGA, Parrot, and PBKV anticipate agent memory access using declared graphs, annotations, or trained prediction.These approaches depend on developer or framework-provided workflow structure, and PBKV uses a neural predictor trained offline.
- DAG-aware KV-cache management: CacheScout learns the per-workload transition matrix online without requiring a deploy-time-declared graph.This addresses workflows where a static DAG cannot be constructed beforehand.
- KV-cache retention across execution stalls: Other systems retain session KV during external function calls to avoid eviction and re-prefill when tools return.Retention may depend on predicted call duration or the request’s memory footprint during the call.
- Faster agent serving: Agent-serving research accelerates structured workflows through grammar-constrained generation or parallelization that reduces token-by-token autoregressive decoding.These methods target individual-agent latency rather than CacheScout’s execution-aware KV-cache management.
- Other KV-cache optimizations: CacheScout complements optimizations for approximate sharing, lossy reuse, compression, routing, and paged attention by targeting agent-level reuse across session boundaries.The paper characterizes this target as orthogonal to per-block KV-cache optimizations.
7 Conclusion
CacheScout improves KV-cache reuse in multi-agent LLM serving by learning agent execution semantics online. This enables predictive cache management without predefined workflow graphs, offline training, or serving-critical-path modifications.
- Conclusion: CacheScout is an agent-aware KV-cache runtime layer that improves cache reuse by leveraging agent execution semantics.It targets multi-agent LLM serving.
- Conclusion: CacheScout learns agent execution transitions online to enable predictive cache management without predefined workflow graphs or offline training.The approach also avoids modifications to the serving critical path.
- Conclusion: Experiments on representative real-world multi-agent workloads show that CacheScout substantially improves KV-cache hit rate and reduces TTFT and end-to-end latency.