🤖 AI

Learning Agent Execution for KV-Cache Management in Agentic Serving

This paper introduces CacheScout, an agent-aware KV-cache runtime that learns online agent execution transitions to proactively manage cache eviction and prefetching, significantly improving hit rates and reducing latency for multi-agent LLM serving without requiring predefined workflow graphs.

Original authors: Rui Zhang, Chaeeun Kim, Shaoting Feng, Kuntai Du, Yuhan Liu, Yi Zhong, Cheng-Wei Ching, Junchen Jiang, Liting Hu

Published 2026-08-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Rui Zhang, Chaeeun Kim, Shaoting Feng, Kuntai Du, Yuhan Liu, Yi Zhong, Cheng-Wei Ching, Junchen Jiang, Liting Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern world of artificial intelligence, a new way of building smart assistants has taken hold. Instead of asking a single, all-knowing computer brain to solve a complex problem in one go, developers now break tasks down into a team of specialized digital workers. Imagine a travel planner that first asks one agent to find flights, then hands the job to another agent to book hotels, and finally passes it to a third to locate restaurants. Each of these agents is a large language model, a type of software that predicts the next word in a sentence based on patterns it has learned. To do this, the software must hold a vast amount of information in its short-term memory, known as a key-value cache. This memory acts like a workspace where the model keeps the rules of the game, the definitions of the tools it can use, and the examples of how to behave. Every time a new agent joins the conversation, it brings its own set of instructions and examples, creating a large chunk of data that the system must process before it can start answering the user's specific question.

The challenge arises because these digital teams are dynamic. The first agent might finish its job, and the system might immediately switch to a completely different agent, or it might loop back to the first one later. Current computer systems that run these AI teams manage their memory reactively. They keep the most recently used information and discard the older stuff to make room for new requests. This works well for simple conversations, but in a multi-agent team, it creates a frustrating inefficiency. The system often throws away the fixed instructions and examples for an agent just because that agent hasn't spoken in the last few seconds, even though that same agent is likely to be called again in the very next step. When the agent returns, the system has to re-read and re-process all those instructions from scratch, wasting time and computing power. This cycle of discarding and re-learning slows down the entire operation, making the AI feel sluggish and expensive to run.

Researchers at the University of California, Santa Cruz, and other institutions have developed a new approach to solve this problem, calling it CacheScout. Instead of simply watching what has happened in the past, this system learns to anticipate what will happen next. It treats the flow of the conversation not as a random series of events, but as a pattern of transitions between different workers. By observing how often a travel agent is followed by a hotel agent, or how a coding agent might switch to a review agent, the system builds a mental map of the workflow as it runs. It does not need a pre-written script or a map provided by the developers; it learns these connections on the fly, updating its understanding with every single request it processes.

The core of this new system is a lightweight layer that sits between the AI agents and the computer hardware. When an agent finishes its task, this layer looks at the history of the conversation and predicts which agent is most likely to speak next. If the system is confident about the next step, it takes two specific actions to speed things up. First, when it needs to clear out old data to make space, it refuses to delete the instructions for the agent that is predicted to return soon, even if that agent hasn't spoken in a while. It protects these valuable chunks of memory based on their future importance rather than their past usage. Second, while the system is waiting for the next request, it quietly and invisibly prepares the memory for that predicted agent. It loads the necessary instructions into the fast memory before the user even asks for them, so that when the agent finally starts working, it can begin immediately without delay.

The researchers tested this system on real-world tasks, including planning trips, solving math problems, and writing software code. They found that by remembering the patterns of agent behavior, the system could keep the right information in memory much more often than before. In their tests, the rate at which the system successfully reused existing memory jumped by ten to eighteen percentage points. This improvement translated directly into speed. The time it took for the first word of an answer to appear dropped by as much as forty-five percent, and the overall time to complete a single turn of the conversation fell by nearly forty percent. The system also handled more requests at once, increasing the total number of tasks it could finish per second by up to fifty-seven percent.

Crucially, the researchers showed that this approach works even when the workflow is not fixed. In many modern applications, the next step is decided by the AI itself in real time, meaning the path can change unpredictably. The new system adapts to this fluidity, learning the most common paths as they happen and adjusting its predictions accordingly. It also proved effective with much larger and more complex AI models, maintaining its speed advantages even when the memory requirements were significantly higher. The system achieves all of this without slowing down the computer or requiring complex new hardware; it simply adds a small amount of intelligence to the memory management process, turning a passive storage system into an active participant that knows what is coming next.

The findings suggest that the future of efficient AI serving lies in understanding the context of the work, not just the data itself. By recognizing that a travel agent is likely to be followed by a hotel agent, the system stops treating every moment as a fresh start and begins to see the conversation as a continuous journey. This shift from reacting to the past to preparing for the future allows these digital teams to work much faster and more efficiently, removing the bottlenecks that have slowed down the deployment of complex AI applications. The result is a system that feels more responsive and capable, capable of handling the intricate, multi-step tasks that define the next generation of artificial intelligence services.

Technical Summary: Learning Agent Execution for KV-Cache Management in Agentic Serving

Problem Statement

Multi-agent Large Language Model (LLM) systems have become a dominant paradigm for AI services, where user requests are decomposed into sequences of specialized agents (e.g., planners, travel agents, coding agents). A critical characteristic of these workflows is the recurring fixed context (agent anchors) associated with each agent, which includes system prompts, tool definitions, and few-shot examples. This fixed context often constitutes 53–62% of all prompt tokens.

Existing LLM serving systems (e.g., vLLM, SGLang) manage KV-caches reactively using prefix caching and recency-based replacement policies (like LRU). These systems treat KV blocks as anonymous content-addressed objects. Consequently, when an agent executes a tool or waits for a planner's decision, its KV-cache blocks are evicted due to lack of recent access. When the same agent is invoked again later in the workflow, the system must recompute the fixed context from scratch. This reactive approach fails to exploit the high predictability of agent reuse, leading to substantial redundant computation and increased latency.

The core challenges identified are:

Semantic Gap: Serving engines know what content is cached but not which agent produced it or when it will be reused.
Dynamic Execution: Modern agent frameworks (e.g., AutoGen, LangGraph) often determine the next agent dynamically at runtime via LLM reasoning, making static workflow graphs or pre-declared execution paths unreliable or unavailable.
Latency Constraints: Cache eviction occurs on the serving critical path. Complex learning-based prediction models that require heavy feature extraction or inference are too slow for this context.

Methodology: CacheScout

The authors propose CacheScout, a lightweight, agent-aware KV-cache runtime layer that bridges agent frameworks and serving engines. Instead of modifying the serving engine's core or requiring offline training, CacheScout operates as an independent runtime that learns execution semantics online to guide cache eviction and prefetching.

Key Components

Transition Learner:
- Models agent execution as an online first-order Markov chain.
- Observes runtime dispatches by fingerprinting prompt prefixes to identify the current agent.
- Updates a transition counter ( $C_{ij}$ ) for every observed transition from agent $i$ to agent $j$ .
- Computes transition probabilities $P_{ij}$ without offline training or predefined graphs.
Survival-Probability Scorer:
- Determines which cached agent anchors to retain by estimating their survival probability (the likelihood of being reused within the next $K$ steps).
- Approximates this probability using a Breadth-First Search (BFS) on a sparse execution graph derived from the transition matrix (pruning low-confidence edges).
- Computes a survival score based on the hop distance from the current agent: anchors closer in the execution graph receive higher scores.
- Combines this score with a recency signal and the block's reconstruction cost (token count) to rank eviction candidates. The policy gracefully degrades to LRU when execution becomes unpredictable.
Background Prefetch Coordinator:
- Proactively warms up high-value agent anchors during idle periods between requests.
- Issues a lightweight "warmup request" containing only the predicted agent's reusable anchor (system prompt + tools) with max_tokens=1.
- This triggers the serving engine's standard prefill pipeline to reconstruct KV blocks off the critical path, ensuring they are ready before the actual request arrives.
- Includes an adaptive gating mechanism: Prefetching is only enabled when the execution predictability metric ( $R$ ) exceeds a threshold, preventing wasted GPU cycles on random workflows.

Key Contributions

Identification of a New Challenge: The paper highlights that existing reactive prefix caches cannot exploit future agent reuse in dynamic multi-agent workflows because they lack agent-level semantic awareness.
Agent-Aware Runtime Layer: The proposal of CacheScout, which decouples cache intelligence from the serving engine, enabling proactive management without modifying the underlying inference stack.
Online Learning & Prediction: The design of a system that learns execution transitions online via a lightweight Markov chain, eliminating the need for static workflow graphs or offline training.
Survival-Guided Eviction & Prefetch: The implementation of a scoring mechanism that prioritizes blocks based on predicted reuse probability and a background prefetching strategy that operates asynchronously.

Results

The authors implemented CacheScout on top of vLLM and evaluated it against vanilla vLLM and Continuum (a baseline using TTL-based pinning) across four real-world multi-agent workloads (GSM8K, MT-Bench, GAIA, SWE-bench) using Llama-3.1-8B-Instruct.

KV-Cache Hit Rate: Improved by 10–18 percentage points, reaching 81–85% across all workloads.
Latency:
- Reduced Mean Time-to-First-Token (TTFT) by 18–45%.
- Reduced Mean Per-Turn Latency by 29–38%.
Throughput: Increased peak throughput by up to 57%. Under the same latency budget, CacheScout sustained 1.7–12× the load of vanilla vLLM.
Scalability: The benefits generalized to larger models. On Qwen3-235B-A22B (235B parameters), CacheScout reduced TTFT by 33–54% and sustained 37% higher throughput.
Overhead: The runtime state is compact (<25 KB), and hot-path operations incur negligible overhead (microseconds), ensuring no impact on the serving critical path.

Significance

The paper claims that CacheScout demonstrates that incorporating agent execution semantics into KV-cache management is an effective and practical approach for efficient multi-agent LLM serving. By shifting from reactive, content-based caching to proactive, semantics-aware management, the system significantly reduces redundant prefill computation. The work establishes that execution structure in multi-agent systems is learnable online and predictable enough to drive cache decisions, even without static workflow definitions. This approach offers a path to significantly higher throughput and lower latency for complex, dynamic AI agent deployments.