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 is a workflow-aware KV cache management framework for LLM serving that replaces LRU eviction with a steps-to-execution priority scheme derived from an Agent Step Graph, and adds proactive CPU→GPU prefetching. It achieves up to 1.83× and 2.19× speedup over SGLang with hierarchical radix cache for single and concurrent multi-agent workflows, respectively.

Problem

Standard LRU-based KV cache eviction in LLM serving systems (SGLang, vLLM) is oblivious to agentic workflow execution order. In cyclic or graph-structured multi-agent workflows, agents with large fixed prompts are evicted shortly before their imminent reuse, causing frequent cache misses that force expensive recomputation or reactive CPU→GPU loading, degrading end-to-end latency.

Method

KVFlow introduces two complementary optimizations implemented on top of SGLang v0.4.4:

  1. Workflow-aware eviction via Agent Step Graph (ASG): Each agent is modeled as a node; edges encode dependencies. A per-node steps-to-execution value is computed via step aggregation functions (max for AND-join sync barriers, min for OR-join conditional branches). These values propagate upward through the tree-structured KV cache, assigning fine-grained eviction priorities at the cache-node level. Varying suffixes always get highest eviction priority; shared prefix nodes inherit the minimum (most conservative) priority from all downstream agents. At eviction time, a max-heap over leaf nodes orders evictions by priority.

  2. Fully overlapped KV prefetching with status-aware scheduling: Using the ASG, KVFlow proactively loads the next agent(s)' KV tensors from CPU to GPU in background threads while the current agent runs on GPU (PCIe full-duplex enables zero contention). A four-state status variable per cache node (in-GPU / backup-in-CPU / loading / offloading) lets the scheduler skip requests whose KV is still loading and prioritize others, eliminating GPU stalls from incomplete transfers.

Prompt segmentation into fixed vs. dynamic parts uses either explicit user-marked boundaries or a cache-hit-history heuristic. Client IDs disambiguate agent identities across concurrent independent workflows.

Key Contributions

  • Identification that LRU eviction is fundamentally mismatched to agentic workflows with predictable execution graphs.
  • Agent Step Graph abstraction supporting arbitrary topology (sequential, conditional branches, sync barriers) with compositional steps-to-execution computation.
  • Fine-grained tree-node-level eviction priority propagation, correctly handling shared prefix subtrees across multiple agents.
  • Fully overlapped proactive prefetching combined with status-aware scheduling that eliminates reactive-loading stalls.
  • Prototype in SGLang v0.4.4 with negligible overhead; design generalizes to vLLM block-level granularity.

Results

  • Single workflow, large prompts (Qwen2.5-32B, H100, 10-stage sequential): Up to 1.83× speedup over SGLang w/ HiCache (and 1.42× over GPU-only SGLang) at 4096/32/32 fixed/dynamic/output tokens.
  • Optimization breakdown on top of HiCache: Eviction alone → 1.11×; eviction + prefetching → 1.29×.
  • High-concurrency (multiple concurrent workflows): Up to 2.19× speedup over SGLang w/ HiCache; HiCache itself degrades to 0.57× of baseline SGLang at 1024 fixed tokens with 64 concurrent workflows.
  • Realistic PEER-style workflows (Qwen2.5-32B and Llama-3.1-8B): Up to 1.12× over SGLang, 1.08× over HiCache.
  • Gains increase with longer fixed prompts and decrease as output token length grows (decode latency dominates).

Limitations

  • Requires that future agent execution order be predictable within at least a short window; highly unpredictable workflows receive no benefit (graceful fallback to LRU).
  • Does not resolve KV storage fragmentation in SGLang, limiting PCIe bandwidth utilization.
  • Evaluated on a single H100; PCIe bandwidth characteristics (64 GB/s Gen5) may not generalize to all hardware configurations.
  • Gains diminish as output length grows relative to prefill, limiting benefit for long-generation tasks.

Relevance to Agentic AI / LLM Agents

KVFlow directly targets the serving-layer bottleneck that emerges specifically from structured multi-agent workflows — a problem invisible in single-agent or chatbot settings. As multi-agent systems with large, role-defining fixed prompts (e.g., MetaGPT, PEER, AutoGen) become standard deployment patterns, inference infrastructure must exploit workflow topology rather than treating requests as independent. KVFlow demonstrates that exposing agent execution graph semantics from the application layer to the serving backend unlocks substantial efficiency gains orthogonal to model-level optimizations (speculative decoding, sparse attention), pointing toward a broader principle of workflow-aware LLM serving as a first-class design target.