Source-linked AI summary
KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflows
Zaifeng Pan, Ajjkumar Patel, Zhengding Hu, Yipeng Shen, Yue Guan, Wan-Lu Li, Lianhui Qin, Yida Wang, Yufei Ding
TL;DR
Agentic workflows benefit from prefix caching, but LRU eviction can discard KV caches shortly before agents reuse them. KVFlow predicts future execution with an Agent Step Graph, applies workflow-aware KV-node eviction, and overlaps prefetching with generation. It reports speedups of up to 1.83× for large-prompt single workflows and 2.19× for many concurrent workflows versus SGLang with hierarchical radix cache.
Problem
LRU-based KV eviction can discard caches shortly before their reuse in agentic workflows, causing cache misses and recomputation or swapping overhead.
Method
KVFlow computes steps-to-execution from an Agent Step Graph to guide KV-node eviction and proactively prefetch required tensors from CPU to GPU.
Results
1.83× and 2.19× speedups are achieved over SGLang with hierarchical radix cache for large-prompt single workflows and many concurrent workflows, respectively.
Takeaways & Limitations
KVFlow shows that workflow semantics can enable system-level serving optimizations for workflows with long prompts or high concurrency.
Takeaways & Limitations
Prefetching can still fail to hide transfer latency when agent execution is shorter than prefetch duration, especially under high-concurrency bandwidth contention.
Abstract
from arXiv · showhide
Large language model (LLM) based agentic workflows have become a popular paradigm for coordinating multiple specialized agents to solve complex tasks. To improve serving efficiency, existing LLM systems employ prefix caching to reuse key-value (KV) tensors corresponding to agents' fixed prompts, thereby avoiding redundant computation across repeated invocations. However, current systems typically evict KV caches using a Least Recently Used (LRU) policy, which fails to anticipate future agent usage and often discards KV caches shortly before their reuse. This leads to frequent cache misses and substantial recomputation or swapping overhead. We present KVFlow, a workflow-aware KV cache management framework tailored for agentic workloads. KVFlow abstracts the agent execution schedule as an Agent Step Graph and assigns each agent a steps-to-execution value that estimates its temporal proximity to future activation. These values guide a fine-grained eviction policy at the KV node level, allowing KVFlow to preserve entries likely to be reused and efficiently manage shared prefixes in tree-structured caches. Moreover, KVFlow introduces a fully overlapped KV prefetching mechanism, which proactively loads required tensors from CPU to GPU in background threads for agents scheduled in the next step, thereby avoiding cache miss stalls during generation. Compared to SGLang with hierarchical radix cache, KVFlow achieves up to 1.83$\times$ speedup for single workflows with large prompts, and up to 2.19$\times$ speedup for scenarios with many concurrent workflows.
1 Introduction
Agentic workflows repeatedly invoke specialized agents with fixed prompts, making prefix caching useful but exposing LRU eviction's inability to anticipate near-future reuse. KVFlow addresses this with workflow-aware eviction, prefetching, and reported speedups over SGLang.
- Agentic workflows coordinate specialized agents through repeated LLM invocations, which increases inference latency despite modularity and reusability.
- Prefix caching reuses KV tensors for fixed prompt tokens, which remain constant across agent iterations.
- LRU can evict an agent’s KV cache shortly before reuse, causing cache misses and increased prefill latency.
- KVFlow computes steps-to-execution values from an Agent Step Graph to anticipate when agents will run.
- KVFlow combines workflow-aware KV-node eviction with fully overlapped CPU-to-GPU prefetching to reduce cache-miss stalls.
- 1.83× and 2.19× speedups are achieved over SGLang with hierarchical radix cache for large-prompt single workflows and many concurrent workflows, respectively.
2 Background
Prefix caches organize reusable KV tensors in GPU-resident tree structures, while agentic workflows contain large fixed prompts whose cached KV can reduce prefill latency. GPU memory pressure arises from concurrency and long contexts.
- Prefix Caching in LLM Serving Systems: Prefix caching stores token segments and their KV tensors in a tree, matching and concatenating nodes to reconstruct cached prefixes.
- Prefix Caching in LLM Serving Systems: GPU memory exhaustion can result from many concurrent workflows or very large agent prompts, with KV cache size increasing with prefix length.
- Agentic Workflow: Agentic workflows organize multiple agents in execution graphs, with each agent using fixed and task-specific prompt components.
- Agentic Workflow: Caching fixed-prompt KV can reduce prefill latency because agent roles, instructions, and examples remain stable across workflow iterations.
3 Design of KVFlow
KVFlow uses workflow structure to prioritize KV eviction by future execution and proactively prefetch upcoming prefixes. Status-aware scheduling overlaps transfers with computation, while bandwidth contention can still stall generation.
- Workflow-Aware Eviction Policy: KVFlow replaces LRU with workflow-aware eviction based on predicted future agent usage.
- Agent Step Graph: The Agent Step Graph represents agent invocations and dependencies, using aggregation functions to compute earliest possible execution steps across branches and synchronization patterns.
- Workflow-Aware Eviction Policy: KVFlow assigns eviction priorities at cache-node level, retaining shared prefix nodes according to the least evictable child priority.
- Overlapped KV Prefetching: Reactive loading avoids recomputation but incurs CPU-to-GPU transfer latency, especially for long prefixes.
- Overlapped KV Prefetching: Proactive prefetching asynchronously loads predicted next-agent KV caches while the current agent executes, and branching workflows prefetch possible successors within a concurrency limit.
- Overlapped KV Prefetching: Prefetching can still leave generation blocked when agent execution is shorter than transfer time, especially under high-concurrency bandwidth contention.
- Overlapped KV Prefetching: Status-aware scheduling skips requests whose prefixes are still loading and prioritizes other ready requests to reduce GPU idle time.
- Overlapped KV Prefetching: Combining proactive prefetching with status-aware scheduling effectively eliminates cache misses and overlaps GPU computation with prefetching.
4 Evaluation
KVFlow is evaluated against SGLang and HiCache across single-workflow, high-concurrency, and realistic PEER-style workloads. It consistently improves performance, with larger gains when fixed prompts increase cache pressure and smaller gains when decoding dominates runtime.
- Evaluation setup: KVFlow is evaluated using microbenchmarks for single-workflow latency and multi-workflow execution under high concurrency.The experiments use Llama-3.1-8B on an A10G and Qwen2.5-32B on an H100, with SGLang and SGLang with HiCache as baselines.
- Single-workflow latency: 1.83× speedup over SGLang with HiCache is achieved under 8192/32/32 tokens on an A10G, while speedup over GPU-only SGLang reaches 2.91×.The 10-agent sequential workflow uses fixed, dynamic, and output token components, with large fixed prefixes forcing cache evictions.
- Performance trends: KVFlow’s relative gain diminishes as output tokens increase because decoding latency dominates total runtime.The paper identifies decoding optimizations as orthogonal and potentially co-applicable.
- Single-workflow latency: 1.48× average speedup is achieved at 8192 fixed tokens, compared with 1.28× at 4096 fixed tokens.The reported reason is higher cache-miss overhead as prefix length grows.
- High-concurrency performance: KVFlow consistently outperforms SGLang and HiCache under high concurrency, reaching up to 1.25× speedup across tested fixed-prompt and concurrency settings.The high-concurrency experiments use independent, non-sharing workflows on one H100 with dynamic and output lengths fixed at 256 tokens.
- High-concurrency performance: 2.19× performance gain over naive LRU-based HiCache is achieved through better overlap of PCIe transfers and GPU computation using workflow-aware eviction and proactive prefetching.Reactive cache misses can disrupt SGLang’s schedule-compute pipeline, while KVFlow proactively loads tensors for upcoming agents.
- Realistic workflow simulation: KVFlow achieves up to 1.12× and 1.08× speedups over SGLang and HiCache, respectively, on realistic PEER-style multi-agent applications.These workloads use four agents and Financial QA inputs, with variable generated prompts and moderate prompt sizes.
5 Related Work
Prior work improves LLM serving, agentic workflow construction, and request scheduling, but KVFlow targets workflow-aware prefix-cache management in the serving system. Its objective complements workflow schedulers that do not manage prefix caches.
- LLM Serving Optimizations: LLM serving research includes request scheduling, memory-fragmentation reduction, prefix-cache deduplication, and specialized caching strategies.Examples include continuous batching, PagedAttention, RadixAttention, and cost-based cache retention.
- Agentic Workflow Frameworks: Agentic workflow frameworks organize specialized agents and dependencies but generally rely on conventional LLM serving infrastructure for generation.Their abstractions support message passing, tool use, reasoning, concurrency, and graph-level transformations.
- Position of KVFlow: KVFlow leverages workflow structure to optimize backend prefix-cache efficiency, complementing agentic schedulers that do not address prefix-cache management.The paper distinguishes its serving-system focus from application-layer workflow construction and complementary request-scheduling work.
6 Conclusion
KVFlow improves LLM serving for agentic workflows by using workflow semantics to manage KV caches and proactively avoid cache-miss stalls.
- KVFlow abstracts agent execution as a Step Graph and computes steps-to-execution values to anticipate future agent usage.These values support workflow-aware cache management rather than relying solely on recent-access history.
- KVFlow adds fully overlapped KV prefetching to proactively eliminate cache-miss stalls.The mechanism complements workflow-aware cache management by improving serving efficiency during workflows with long prompts or high concurrency.