Skip to content

KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflows

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

KVFlow replaces the LRU eviction policy in LLM serving systems with a workflow-aware KV cache manager that uses an Agent Step Graph to predict which agents will execute next and prioritize their cache retention. It also adds proactive CPU→GPU prefetching of KV tensors overlapped with current-agent generation. Against SGLang with hierarchical radix cache, KVFlow achieves up to 1.83× speedup for single workflows and 2.19× for concurrent workflows.

Problem

Existing LLM serving systems use Least Recently Used (LRU) eviction for prefix KV caches, which is oblivious to future agent execution order. In cyclic or structured multi-agent workflows, agents that are idle-but-imminent (e.g., an Expresser agent two steps away) get evicted just before reuse, triggering expensive KV recomputation or CPU→GPU reload stalls that degrade end-to-end workflow latency.

Method

Agent Step Graph (ASG): Each agent invocation is a node; edges encode dependencies. Each node carries a steps-to-execution value computed via step aggregation functions — \(\max(\cdot)+1\) for synchronization barriers (AND semantics), \(\min(\cdot)+1\) for conditional branches (OR semantics). This gives a single integer per agent estimating temporal proximity to activation.

Workflow-Aware Eviction: Instead of LRU, KVFlow assigns eviction priority equal to the agent's steps-to-execution to the last KV node of that agent's fixed prompt, then propagates the priority upward through the radix tree (taking the \(\min\) at shared nodes so a shared prefix is retained as long as any near-future agent needs it). Dynamic suffixes always receive the highest (most evictable) priority. Eviction proceeds as a max-heap over leaf nodes.

Overlapped KV Prefetching: Using the ASG, KVFlow asynchronously loads the fixed-prompt KV of the next-step agent(s) from CPU to GPU in background threads while the current agent executes on the GPU. Because model forward passes occupy GPU↔CPU bandwidth differently from PCIe KV transfers (and PCIe supports full-duplex), these overlap without contention. A status-aware scheduler tracks each cache node's state (in-GPU / backup-in-CPU / loading / offloading) and skips agents whose cache is still loading, scheduling other ready agents (from the same or concurrent workflows) instead.

Prompt Segmentation: Fixed vs. dynamic prompt boundary is identified either via an explicit API marker or a heuristic tracking cache-hit history.

Key Contributions

  • Identifies LRU eviction as a structural mismatch for agentic workflows where future invocation order is predictable.
  • Agent Step Graph abstraction supporting sequential, conditional-branch, and synchronization-barrier dependency patterns with unified steps-to-execution computation.
  • Fine-grained KV node-level eviction policy derived from ASG, handling shared prefix trees across multiple agents and concurrent workflows.
  • Fully overlapped proactive KV prefetching combined with status-aware scheduling to eliminate cache-miss stalls without blocking generation.
  • Prototype implemented on SGLang v0.4.4; architecture is portable to vLLM (block-level granularity) and other frameworks.

Results

  • Single workflow (branches=1), Qwen2.5-32B on H100: Up to 1.83× speedup over SGLang w/ HiCache (hierarchical radix cache + LRU); e.g., under 4096/32/32 token config, 1.24× over HiCache, 1.42× over GPU-only SGLang.
  • Single workflow (branches=2, moderately dynamic): Comparable speedup profile; gains persist because branch candidates are all prefetched within a predefined limit.
  • Concurrent workflows: Up to 2.19× speedup over SGLang w/ HiCache.
  • KVFlow consistently dominates both SGLang (GPU-only, recompute on miss) and SGLang w/ HiCache (CPU backup, layer-pipelined load) across all tested prompt configurations.
  • As output token count grows, relative gain diminishes because decoding latency dominates over prefill/cache-load time.
  • SGLang w/ HiCache can degrade vs. GPU-only SGLang at large context on H100 (e.g., 8192/32/32) due to suboptimal pipeline scheduling — KVFlow avoids this by full overlap.

Limitations

  • Requires that future agent execution order be predictable at least one step ahead; highly unpredictable or fully autonomous workflows see no benefit (falls back to LRU silently).
  • Steps-to-execution values must be supplied to the serving backend at request time, coupling the harness orchestration layer to the inference server's eviction logic.
  • Evaluation is on a single H100 with Qwen2.5-32B; multi-GPU or heterogeneous memory hierarchies (e.g., NVMe as tertiary cache) are not studied.
  • Prompt segmentation heuristic (cache-hit history) may be inaccurate for variable-length fixed prompts or during early warm-up.
  • Text truncated before multi-workflow concurrency results are fully presented.

Relevance to Harnesses / Meta-Harnesses

KVFlow directly addresses the serving infrastructure that multi-agent harnesses sit atop: any meta-harness (e.g., MetaGPT, LangGraph-style orchestrators) that dispatches agents to an LLM backend benefits from this without application-level changes, as long as it can expose its execution graph. The Agent Step Graph is itself a formalization of harness topology — the same dependency structure that a meta-harness uses for scheduling is here reused to drive cache policy, suggesting that harness runtimes should treat execution graphs as first-class artifacts shared with the serving layer. For harness designers, this implies that exposing step-order metadata through the request API (rather than treating each LLM call as stateless) is a low-cost, high-return optimization surface.