If you are running a multi-agent LLM system in production, your serving engine is almost certainly throwing away reusable context on every turn. The KV cache, which stores the computed attention keys and values for tokens already processed, is the single most expensive state in your inference stack. When an agent finishes a turn and waits for a tool call to return, the serving engine sees its cached blocks as old and quietly evicts them. Then the agent comes back, and the engine recomputes the entire system prompt, tool definitions, and few-shot examples from scratch.
Yandex Research has published a proposal and a working implementation called CacheScout that treats the KV cache as an agent runtime, learning which agent will execute next and keeping its context warm. The results are substantial: KV-cache hit rate rises by 10 to 18 percentage points, reaching 81 to 85 percent across four real-world workloads, mean time-to-first-token drops by 18 to 45 percent, and peak throughput increases by 19 to 57 percent compared to vanilla vLLM.
What did Yandex Research actually build?
Two papers came out of this work. The first, published as a blog post by Yandex Research, proposes the broader abstraction: an agent runtime layer that sits between the agent framework and the serving engine, exposing four primitives: observe, score, predict, and act. The idea is that neither the framework nor the engine should own cross-cutting agent metadata. Instead, a separate runtime tracks which agent is running, how agents transition into each other, and what that means for cache decisions.
The second paper, CacheScout on arXiv, is the concrete implementation. It builds on vLLM and adds three components:
- Transition learner: models agent execution as an online first-order Markov chain. For each request, it identifies the agent from the prompt-prefix fingerprint and updates a single transition counter. No offline training, no predefined workflow graph.
- Survival-probability scorer: estimates the probability that each cached anchor will be reused based on the learned transition matrix, then combines this with recency and reconstruction cost to rank eviction candidates. When the transition matrix is uncertain, the policy falls back toward LRU.
- Background prefetch: predicts the next agent from the same transition matrix and warms the corresponding anchor between requests, leaving the serving critical path untouched.
The entire runtime layer uses less than 20 KB of state per workload, which means the overhead is effectively invisible. The Markov model is simple enough to update in microseconds and small enough to fit in L1 cache. This is a lightweight statistical predictor that happens to capture the one thing LRU misses: which agent comes next.
The broader agent runtime paper maps nine policies onto the observe-score-predict-act framework, including KV caching across sessions, request batching, and agent-aware scheduling. CacheScout is the case study with the largest immediate cost lever, but the abstraction is designed to host more.
How much does agent-aware caching improve serving?
The numbers are the story here. On a six-agent supervisor framework running Llama-3.1-8B-Instruct across four representative multi-agent workloads (GAIA, GSM8K, SWE-bench, and a fourth workload), CacheScout delivered:
- KV-cache hit rate: 81 to 85 percent, up from 63 to 75 percent with vanilla vLLM. That is a 10 to 18 percentage point lift.
- Mean TTFT: down 18 to 45 percent. Median TTFT drops are even more telling: 231 to 114 ms on GAIA, 239 to 115 ms on GSM8K. P99 TTFT on SWE-bench drops from 711 to 342 ms, a 52 percent reduction at the tail.
- Mean per-turn latency: down 29 to 38 percent.
- Peak throughput: up 19 to 57 percent. Under the same mean-latency budget, CacheScout sustains 1.7x to 12x the arrival rate of vanilla vLLM, and 4.2x to 16x that of Continuum.
CacheScout delivers consistent TTFT reductions across workloads. The chart below shows the before-and-after for three of them.
The gap on SWE-bench is the most striking: a 369 ms reduction at the tail, which is the difference between a responsive agent and one that feels stuck.
The gains also scale to larger models. On Qwen3-235B-A22B, a 235-billion-parameter mixture-of-experts model, CacheScout reduces mean TTFT by 33 to 54 percent on SWE-bench and sustains 37 percent higher throughput. This matters because larger models have longer KV-cache reconstruction times, so the cost of a cache miss is higher. The bigger the model, the more it hurts to evict the wrong block.
For context on why this matters at the cluster level, Ability.ai reports that prefix-aware routing, a related technique that sends requests to the GPU pod already holding the cached context, can cut TTFT from roughly 3 seconds to under 1 second. Cached tokens can cost up to 10x less than fresh ones. If you are paying per-token for inference, losing your cache on every agent turn is burning money.
A separate and complementary approach, ReCache, achieves a 3.66x TTFT speedup by separating reusable schema from dynamic content and compressing the dynamic parts. The two approaches target the same problem from different angles: CacheScout makes eviction smarter, ReCache makes the cache itself smaller.
Why does LRU fail so badly for multi-agent workloads?
This is the core insight, and it is simpler than you might expect.
In a multi-agent system, each agent repeatedly executes a fixed context: system prompt, tool definitions, few-shot examples. This recurring prefix is called the agent anchor, and it accounts for 0.34 to 0.52 of every first-turn prompt. That means roughly a third to half of the tokens in your first turn are pure reusable state.
LRU eviction answers the wrong question for this workload. LRU asks: what was accessed least recently? The right question is: what will be accessed next? A program blocked on a tool call looks exactly like a dead program to LRU. Its KV blocks are the oldest in the pool because no request has touched them while the tool executes. But unlike a dead program, this agent is guaranteed to return. The moment it does, the serving engine has to recompute hundreds or thousands of tokens of system prompt and tool definitions.
CacheScout answers that question by learning the transition matrix between agents. If agent A usually calls agent B, and agent A just finished its turn, the survival-probability scorer keeps B's anchor warm even if nothing has touched it for several seconds.
The GitHub repository for a related project, AgentCache, puts it bluntly: agents blocked on tool calls have blocks that are the oldest in the pool, yet they are guaranteed to return. Any pure recency policy will evict them first.
Prefix caching alone also falls short. Prefix caching helps when the same prefix is reused, but it does not predict which prefix will be needed next. Without prediction, the cache fills with whatever was most recently used, and the agent that is about to execute finds its context evicted.
What does this change for your serving stack?
If you are running multi-agent workloads on vLLM today, the implications are direct.
- Your KV-cache hit rate is probably below 70 percent. If your agents use tool calls, the gap between turns gives LRU time to evict reusable context. You are paying for recomputation on every turn.
- Your TTFT is 30 to 50 percent higher than it needs to be. That is the cost of recomputing agent anchors. For user-facing agents, this is the difference between a snappy response and a visible loading spinner.
- Your throughput ceiling is lower than your hardware supports. Vanilla vLLM's throughput plateaus once the KV cache saturates, because every new request triggers evictions and recomputations. CacheScout keeps scaling because it wastes less time recomputing.
- Your cost per request is inflated. If cached tokens cost 10x less than fresh ones, and a third to half of your prompt is reusable, you are spending 3 to 5x more on those tokens than necessary.
The CacheScout design sits between the framework and the engine, so your agent framework code and your vLLM configuration stay the same. You add a layer. The runtime observes agent transitions from the framework side and issues cache decisions to the engine side.
For teams building on managed inference platforms, the question to ask your provider is whether they do prefix-aware routing and agent-aware eviction. If they only do LRU, you are overpaying.
This also connects to work on GPU scheduling order recovering throughput without new hardware. CacheScout is solving a related problem: it is reordering the cache rather than the requests, but the principle is the same. The hardware is capable of more than the default policy extracts from it. Similarly, declarative attention approaches that cut decoding tokens target the inference pipeline from a different angle, but the goal is shared: stop wasting compute on work you have already done.
Should you build this, wait for it, or ignore it?
The honest answer depends on your stack.
If you are on vLLM with a custom multi-agent framework, CacheScout is implementable today. The paper describes the implementation in enough detail to reproduce, and the runtime overhead is negligible. The Markov model is a few hundred bytes per workload. The prefetch logic runs off the critical path. It is a practical optimization with clear before-and-after numbers, not a research artifact waiting for someone to productize it.
If you are on a managed platform like OpenAI, Anthropic, or a cloud provider's inference service, you cannot control the KV-cache policy. But you can ask whether they do agent-aware caching, and you can structure your agent design to maximize prefix reuse. If your system prompt and tool definitions are identical across turns, the cache hit potential is high. If you change them every turn, no cache policy can help you.
If you are running single-agent workloads with no tool calls, this does not apply. The problem is specific to multi-turn, multi-agent systems where agents block on tool calls and then return.
The open questions are about generality. The paper evaluates four workloads on a six-agent supervisor framework. Real-world agent topologies can be more complex, with dozens of agents, dynamic routing, and human-in-the-loop interruptions. The first-order Markov assumption may not capture longer-range dependencies. The authors acknowledge this and note that the policy falls back toward LRU when predictions are uncertain, which is the right safety behavior.
The broader agent runtime abstraction, with its four primitives, is the more ambitious bet. If the observe-score-predict-act interface catches on, it could become a standard layer in the inference stack, the way vLLM became the standard serving engine. But that is a bigger architectural claim than the CacheScout numbers support today.
The cache is the runtime
The deepest insight in this work is the recognition that in multi-agent LLM systems, the KV cache is the runtime state of the agent program. Every agent's identity, context, and readiness to execute lives in those KV blocks. Managing that state with a recency heuristic is like managing a process scheduler with a stack overflow check: technically functional, strategically wrong. The teams that treat cache as runtime will outbuild the teams that treat it as a buffer. The numbers are already there. The question is whether you act on them before your competitors do.
Sources
- Yandex Research: The KV Cache as an Agent Runtime
- CacheScout: Learning Agent Execution for KV-Cache Management in Agentic Serving (arXiv)
- A Policy-Driven Runtime Layer for Agentic LLM Serving (arXiv)
- Ability.ai: KV Cache Routing for Agentic AI Infrastructure
- ReCache: Efficient KV Cache Reuse and Compression for Tool-Augmented LLM Agents (arXiv)
- AgentCache on GitHub
