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

Thank you for your insightful comments and questions. We are happy to further improve our manuscript based on your suggestions.

(W1) Workload and Baselines

Thank you for the feedback. In addition to synthetic data, we evaluate KVFlow using dataset and agentic workflows derived from the PEER [3] paper in Section 4.2, which is a framework used widely in production. These workflows are semantically meaningful and simulate realistic agent coordination patterns.

Workflows that are either fully deterministic or contain a limited number of branches are still common in current applications [1, 2, 3]. To further strengthen generalizability, we now include a 10-stage branching workflow, where agents are randomly selected at each stage from partially overlapping prompt groups. All configurations other than the branching pattern follow those in the paper.

Speedups over SGLang for branched workflows with Qwen2.5-32B on an H100

Regarding baselines, in addition to SGLang and its hierarchical cache extension, we now include the vLLM baseline, which organizes KV cache into blocks and adopts LRU-based block eviction policy. The results are shown in the following table. vLLM is slightly faster than SGLang in our experiments, but KVFlow still consistently outperforms both. Since KVFlow is built on top of SGLang with HiCache, comparing against SGLang better reflects the impact of our proposed optimizations. Our approach is general and can also be applied to vLLM or other LLM serving frameworks.

Speedups over SGLang for sequential workflows with Qwen2.5-32B on an H100

[1] Hong, Sirui, et al. "MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework."
[2] Qian, Chen, et al. "ChatDev: Communicative Agents for Software Development."
[3] Wang, Yiying, et al. "PEER: Expertizing domain-specific tasks with a multi-agent framework and tuning methods."

(W2) Title Clarification

We apologize for the confusion. The term "KVFlow" in our title means KV cache management for agentic workFlow. We are open to refining the title to improve clarity.

(Q1) Overhead Analysis

Thanks for the question. The runtime CPU overhead introduced by KVFlow is minimal. First, even when the entire graph is very large, we only need to consider agents within a certain step (e.g., 5) of current activated agents. Second, SGLang’s zero-overhead batch scheduler [4] allows the scheduling logic on CPU to be overlapped with GPU execution, effectively hiding the associated runtime CPU cost. We observe negligible CPU overhead in our measurements. We will add this discussion in Sec 4 in the next version.

[4] SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs.

(Q2) Dynamic Workflow

Thanks for the question. KVFlow is designed for workflows where the structure is known or can be inferred at runtime. KVFlow can handle dynamic workflows as long as the execution order of agents within a certain future window can be predicted at the current step. In such cases, KVFlow adaptively updates the steps-to-execution values at runtime and continues to make informed eviction and prefetching decisions. However, in cases where the workflow is highly unpredictable, KVFlow cannot anticipate future agent calls. In such scenarios, it falls back to HiCache’s LRU eviction and reactive cache loading. We will discuss this limitation in a dedicated section in our next version.

Thank you for your insightful comments and questions. We are happy to further improve our manuscript based on your suggestions.

(Q1) Highly Non-Deterministic Workflows

Thank you for the question. KVFlow is designed for structured agentic workflows where the execution path can be reasonably estimated. KVFlow can handle dynamic workflows as long as the execution order of agents within a certain future window can be predicted at the current step. In such cases, KVFlow adaptively updates the steps-to-execution values at runtime and continues to make informed eviction and prefetching decisions. In highly non-deterministic workflows, KVFlow gracefully falls back to default HiCache behavior by setting equal priority for all agent cache and disabling prefetching. We will clarify this in a distinct limitation section.

Workflows that are either fully deterministic or contain a limited number of branches are still common in current applications [1, 2, 3]. We extend the evaluation with a 10-stage dynamic workflow with branches, and the results are shown in the belowing table, where all configurations other than the branching pattern follow those in the paper.

Speedups over SGLang for branched workflows with Qwen2.5-32B on an H100

[1] Hong, Sirui, et al. "MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework."
[2] Qian, Chen, et al. "ChatDev: Communicative Agents for Software Development."
[3] Wang, Yiying, et al. "PEER: Expertizing domain-specific tasks with a multi-agent framework and tuning methods."

(Q2) Fixed/Dynamic Prompt Detection

Thank you for the question. KVFlow allows users to manually specify the end position of fixed prompts based on application logic, or alternatively use a heuristic strategy. Specifically, we mark segments that are repeatedly reused by the same agent across invocations as fixed. Each agent can have multiple fixed prompts, forming a tree structure under shared prefixes. To avoid stale entries, KVFlow supports an adaptive mechanism that automatically removes fixed prompt nodes if they have not been reused beyond a threshold period.

When the segmentation is partially incorrect, KVFlow still performs well without correctness issues. This case is analogous to workflows with a limited number of branches, as shown in the previous table, where KVFlow prefetches all candidate nodes and therefore achieves similar performance. In the extreme case where all fixed prompts are misclassified, KVFlow falls back to HiCache’s reactive cache loading or performs recomputation without performance degradation. We will add this discussion in Sec 3.3.

(Q3) Large-Scale Agent Step Graph

Thank you for the question. The overhead of maintaining the Agent Step Graph and updating steps-to-execution values is minimal. This is because we only need to consider agents within a certain step (e.g., 5) of current activated agents even when the entire graph is very large. The CPU overhead introduced by the scheduling of KVFlow can be hidden with GPU generation, thanks to SGLang's zero-overhead batch scheduler [4] design. We will add this dicussion in Sec 3.3.

[4] SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs.

Statistical Analysis

Thank you for pointing this out. We now include standard deviations for key performance metrics across multiple runs. In all reported cases, KVFlow consistently outperforms baselines with low variance, confirming the stability of our results.

Speedups over SGLang for sequential workflows with Qwen2.5-32B on an H100

InferCept Baseline

Thank you for the comment. InferCept focuses on memory management during intra-agent interceptions such as tool calls, whereas KVFlow addresses prefix caching across agents by leveraging inter-agent execution patterns. These two approaches target different layers of the execution stack and are orthogonal in design. In fact, they could be combined: KVFlow’s eviction and prefetching mechanisms can manage inactive agents, while InferCept’s eviction policy can optimize memory usage within active, intercepted agents. We will clarify this distinction and potential complementarity in the related work section.

Besides, we now include the vLLM baseline, which organizes KV cache into blocks and adopts LRU-based block eviction policy. Our experiments show that KVFlow outperforms it consistently. vLLM is slightly faster than SGLang in our experiments, but KVFlow still consistently outperforms both. Since KVFlow is built on top of SGLang with HiCache, comparing against SGLang better reflects the impact of our proposed optimizations. Our approach is general and can also be applied to vLLM or other LLM serving frameworks.

Thank you for your insightful comments and questions. We are happy to further improve our manuscript based on your suggestions.

(W1) & (Q3) Statistical Analysis in Evaluation

Thank you for the suggestion. We report the speedups with standard deviations in the table below. The results show that KVFlow delivers highly stable performance improvements. We will revise Section 4 to include these results.

Speedups over SGLang for sequential workflows with Qwen2.5-32B on an H100

(W2) & (Q2) Pseudocode

Thank you for the suggestion. We will include pseudocode for both the eviction priority assignment and the eviction procedure in our next version. When a new agent request arrives with its Agent Step Graph (ASG) information, KVFlow updates the eviction priority of each cache node as follows:

def PriorityAssign:
    for step, agent in ASG:
        node = agent.last_fixed_prompt_node  # Last node of the agent's fixed prompt
        while node != root:
            node.counter[step] += 1
            node.eviction_priority = min(node.eviction_priority, step)
            node = node.parent

When the system needs to evict cache nodes on the GPU to free memory (e.g., during prefill, decode, or prefetch), it proceeds from the leaf nodes in the cache tree based on their priorities:

def Evict:
    leaves = get_leaf_nodes(tree_cache)
    heapify(leaves) # Construct max heap based on eviction priority
    while free_gpu_memory < required:
        node = heappop(leaves)
        free_gpu_memory += evict(node)
        if node.parent becomes a leaf after eviction:
            heappush(leaves, node.parent)

For the prefetch distance hyperparameter, we use a value of 1 in our experiments, which is already good enough to hide data transfer. This value can be adjusted at runtime for different agents based on their workloads.

(Q1) Dynamic Workflows

Thank you for the comment. Our primary focus is on structured agentic workflows where future agent invocations can be estimated. KVFlow can handle dynamic workflows as long as the execution order of agents within a certain future window can be predicted at the current step. In such cases, KVFlow adaptively updates the steps-to-execution values at runtime and continues to make informed eviction and prefetching decisions.

We extend the evaluation with a 10-stage dynamic workflow, where each stage randomly selects one agent from two branches with partially shared prefixes. The results are shown in the following table, where all configurations other than the branching pattern follow those in the paper.

Speedups over SGLang for branched workflows with Qwen2.5-32B on an H100

Workflows that are either fully deterministic or contain a limited number of branches are still common in current applications [1, 2, 3]. In highly unpredictable workflows where future execution cannot be inferred, KVFlow does not offer performance gains. In such cases, the system gracefully falls back to the default HiCache behavior by setting equal priority for all agent cache and disabling prefetching, without introducing additional overhead or correctness issues. We will include this discussion in a dedicated Limitations section.

[1] Hong, Sirui, et al. "MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework."
[2] Qian, Chen, et al. "ChatDev: Communicative Agents for Software Development."
[3] Wang, Yiying, et al. "PEER: Expertizing domain-specific tasks with a multi-agent framework and tuning methods."

(Q4) Overhead Analysis

Thank you for the question. KVFlow introduces minimal runtime overhead. First, priority assignment and prefetch scheduling are handled on the CPU side. SGLang’s zero-overhead batch scheduler [4] allows these computations to be overlapped with GPU execution, effectively hiding the associated CPU cost. According to our profiling, we do not see CPU overhead that cannot be hidden by GPU computation. Second, prefetching does not interfere with LLM decoding, as token generation does not involve CPU–GPU data transfer over PCIe. This allows the transfer of prefetched KV to proceed in parallel with computation. Third, in cases where prefetched KV is ultimately not used, no PCIe bandwidth is wasted, since prefetching only takes place during active GPU computation. It also does not introduce additional memory overhead as the memory can be directly overwritten. If a cache miss occurs, the ongoing prefetch is safely preempted. While unused prefetching may incur additional energy consumption, our design prioritizes performance and responsiveness. We will clarify this discussion in Sec 4 in the next version.

[4] SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs.

Thank you for your insightful comments and questions. We are happy to further improve our manuscript based on your suggestions.

(W1) Evaluation Scope

Thank you for the suggestion. We extend the evaluation with a new 10-stage workflow, where each stage randomly selects one agent from two branches with partially shared prefixes. Other configurations are following the paper. This setup introduces moderate unpredictability while still preserving opportunities for prefetching. As shown in the table below, for Qwen2.5-32B on an H100, KVFlow achieves up to 1.459$\times$ and 1.935$\times$ speedups over SGLang and SGLang w/ HiCache, demonstrating its effectiveness under branched execution. Workflows that are either fully deterministic or contain a limited number of branches are still common in current applications [1, 2, 3]. While highly unpredictable workflows are outside our optimization scope, KVFlow can gracefully fall back to match that of HiCache by setting equal priority for all agent cache and disabling prefetching. We will add the results and discussion in Sec 4.

[1] Hong, Sirui, et al. "MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework."
[2] Qian, Chen, et al. "ChatDev: Communicative Agents for Software Development."
[3] Wang, Yiying, et al. "PEER: Expertizing domain-specific tasks with a multi-agent framework and tuning methods."

Speedups over SGLang for branched workflows with Qwen2.5-32B on an H100.

(W2) Generalizability to Other Frameworks

Thank you for the comment. KVFlow builds on general cache control and prefetching concepts and can be ported to other LLM serving systems. For instance, vLLM internally adopts automatic prefix caching and applies LRU at the block level. Our workflow-aware eviction logic can be applied at this block granularity by maintaining a priority score for each block, enabling anticipatory eviction and prefetching. We will add this discussion in Sec 3.3.

(W3) API Modification

KVFlow requires minimal extensions of traditional LLM call APIs. Specifically, we require (1) a client ID to distinguish requests from different workflows, and (2) the workflow information, including current activated agent name, and the steps-to-execution values for other agents. These inputs allow our runtime to assign priority scores for eviction and prefetching. We will add this illustration in Sec 3.3.

(W4) Clarification on LRU Baseline

Thank you for the comment, and we apologize for the confusion. Both SGLang and SGLang with HiCache adopt exact LRU eviction policies. The difference lies in how they handle evicted entries. SGLang stores KV cache only in GPU memory, so evicted entries must be recomputed when needed again. In contrast, HiCache backs up evicted entries to CPU memory, allowing them to be directly reloaded. We will revise Section 4.1 to clarify this distinction.

(W5) Optimization Ablation

Thank you for the suggestion. We performed a breakdown analysis of the two optimization components on top of SGLang with hierachical cache (HiCache). The table below compares the performance of using workflow-aware eviction alone with the combination of eviction and prefetching. Workflow-aware eviction alone provides an average speedup of 1.109$\times$ over HiCache, while enabling prefetching in addition to eviction further improves the speedup to 1.288$\times$.

Optimization breakdown for sequential workflows with Qwen2.5-32B on an H100

We also evaluated prefetching in isolation. However, in this case, the prefetched nodes frequently conflicted with those selected for eviction, leading to significant performance degradation. This indicates that prefetching must be combined with workflow-aware eviction in order to be effective. We will add these results and discussions in Sec 4.

(W6) Cache Management Integration

Thank you for the suggestion. To more clearly illustrate how KVFlow integrates with KV cache management, we will include pseudocode for both eviction priority assignment and the eviction procedure in the revised version. When a new agent request arrives with its Agent Step Graph (ASG) information, KVFlow updates the eviction priority of each cache node as follows:

def PriorityAssign:
    for step, agent in ASG:
        node = agent.last_fixed_prompt_node  # Last node of the agent's fixed prompt
        while node != root:
            node.counter[step] += 1
            node.eviction_priority = min(node.eviction_priority, step)
            node = node.parent

When the system needs to evict cache nodes on the GPU to free memory (e.g., during prefill, decode, or prefetch), it proceeds from the leaf nodes in the cache tree based on their priorities:

def Evict:
    leaves = get_leaf_nodes(tree_cache)
    heapify(leaves) # Construct max heap based on eviction priority
    while free_gpu_memory < required:
        node = heappop(leaves)
        free_gpu_memory += evict(node)
        if node.parent becomes a leaf after eviction:
            heappush(leaves, node.parent)