CacheFlow: Efficient LLM Serving with 3D-Parallel KV Cache Restoration
Sean Nian, Jiahao Fang, Qilong Feng, Zhiyu Wu, Fan Lai, [0.5em] University of Illinois Urbana-Champaign · 2026
Read CacheFlow: Efficient LLM Serving with 3D-Parallel KV Cache Restoration by Sean Nian, Jiahao Fang, Qilong Feng, Zhiyu Wu, Fan Lai, [0.5em] University of Illinois Urbana-Champaign (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25080.txt.
Introduction
Nian and five colleagues present CacheFlow, fast LLM serving via KV cache restoration. Existing methods choose either recomputation of cached states or loading them from storage. They overlook parallelism within models and contention across requests. CacheFlow rethinks restoration as parallel work across tokens, layers and GPUs. It unifies restoration across tokens and layers as a staircase split, with boundary activations enabling joint work. A batch-aware planner decides what to recompute and what to load. Across dense and hybrid models, CacheFlow cuts restoration latency by about 2 to 3 times.
Catalog record
| CREATOR | Sean Nian, Jiahao Fang, Qilong Feng, Zhiyu Wu, Fan Lai, [0.5em] University of Illinois Urbana-Champaign |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32965 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25080
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CacheFlow: Efficient LLM Serving with 3D-Parallel KV Cache Restoration Sean Nian, Jiahao Fang, Qilong Feng, Zhiyu Wu, Fan Lai, [0.5em] University of Illinois Urbana-Champaign Abstract KV cache restoration has emerged as a dominant bottleneck in serving long-context LLM workloads, including multi-turn conversations, retrieval-augmented generation, and agentic pipelines. Existing approaches treat restoration as a per-request tradeoff between recomputation and I/O transfer, recomputing KV states from scratch or offloading them from external storage (e.g., CPU memory or remote machines). However, existing advances fail to exploit parallelism across tokens, layers, and distributed deployments, and critically ignore resource contention under batched serving. We present CacheFlow, a KV cache restoration framework that rethinks cache restoration as a multi-dimensional parallel execution problem. CacheFlow introduces a unified 3D parallelism abstraction across tokens, layers, and GPUs, enabling fine-grained overlap of recomputation and I/O along the structural dependencies of transformer inference. At the core of CacheFlow is a batch-aware two-pointer scheduler that jointly optimizes compute and I/O allocation across requests by prioritizing operations with the highest marginal reduction in recomputation cost. Our evaluations show that CacheFlow reduces Time-To-First-Token (TTFT) by 10%–62% over existing advances across diverse models, workloads, and hardware. 1 Introduction The rapid adoption of Large Language Models (LLMs) in interactive and agentic applications has driven a fundamental shift toward long-context inference. Modern workloads, including multi-turn conversations ( 5 ) , retrieval-augmented generation (RAG) ( 15 ; 18 ) , and tool-augmented agents ( 20 ) , rely heavily on reusing previously processed context. As a result, efficiently restoring the Key-Value (KV) cache, the intermediate latent representation of prior context, has become a first-class efficiency challenge, as KV cache restoration directly determines Time-To-First-Token (TTFT), a critical latency metric for user-facing systems ( 17 ; 18 ) . Despite its latency-critical role, KV cache restoration remains fundamentally inefficient, incurring many seconds of latency for long-context requests. Existing advances expose a coarse-grained dichotomy: they either rely on prefill recomputation ( 1 ; 13 ; 10 ) , which regenerates KV cache from plaintext at high computational cost, or perform I/O-based restoration by offloading KV cache from external memory (e.g., CPU memory, SSD, or remote nodes ( 14 ) ), which is constrained by bandwidth. While recent hybrid approaches ( 7 ; 17 ; 4 ) partially overlap computation and I/O, they remain fundamentally request-centric and fail to capture two key properties of modern LLM serving (§ 2 ). First, KV cache recomputation cost scales superlinearly: due to the quadratic complexity of attention, later tokens incur disproportionately higher cost, making naive recomputation inefficient for long contexts. This effect is exacerbated by workload heterogeneity, where requests span a wide spectrum of lengths to restore, from short system prompts to long multi-turn contexts. Second, production LLM serving is inherently batched and distributed across multiple GPUs, where compute and I/O resources are shared across requests. This introduces resource contention and straggler effects, rendering per-request optimization insufficient for maximizing overall efficiency. In this paper, we introduce CacheFlow, a serving system that rethinks KV cache restoration as a multi-dimensional parallel execution problem. Our key insight is that restoration is not a monolithic operation, but can be decomposed into fine-grained units that expose three complementary forms of parallelism: (i) Token-level parallelism : overlapping recomputation of earlier tokens with I/O transfer of later tokens, exploiting the causal dependency across tokens; (ii) Layer-level parallelism : pipelining recomputation of lower layers with transfer of higher-layer KV cache, leveraging the execution dependency of model layers; (iii) Multi-GPU parallelism : enabling concurrent restoration across GPUs, allowing each GPU to reconstruct the KV cache of its local model shard while preserving global correctness. Each exposes structured dependencies that can be exploited for parallel execution. This leads to a unified view: KV cache restoration is a multi-dimensional scheduling problem that requires jointly optimizing computation and I/O across requests and GPUs . However, realizing this vision introduces three fundamental challenges (§ 3 ). First, at the request level, determining the optimal composition of parallelism requires carefully balancing heterogeneous costs across tokens, as well as the interplay between compute and I/O capabilities. Second, at the multi-GPU level, enabling parallel restoration requires managing inter-device dependencies to preserve correctness while maximizing concurrency. Third, at the batch level, concurrent restoration across multiple requests introduces severe resource contention and straggler effects, requiring coordinated scheduling. Contributions. To address these challenges, we make the following contributions: • A new formulation of KV cache restoration as a multi-dimensional scheduling problem. We identify the interplay between quadratic recomputation cost and shared resource contention, and show that optimal restoration corresponds to balancing compute and I/O via a harmonic-mean bound (§ 3.1 ). • A novel 3D-parallel KV cache restoration framework. We introduce a unified execution model that orchestrates token-, layer-, and GPU-level parallelism via a novel batch-aware two-pointer scheduling strategy, enabling fine-grained overlap of recomputation and transfer. For distributed deployments, we introduce a lightweight state abstraction where each GPU stores boundary hidden states for concurrent restoration (§ 3.2 -§ 3.3 ). • End-to-end system and evaluations. We implement CacheFlow atop existing serving stacks, vLLM ( 1 ) and LMCache ( 14 ) , seamlessly supporting existing LLM applications. We evaluate it across diverse models (Qwen3-8B, Qwen3-30B-A3B, and Llama-3.1-8B), realistic chatbot and agentic pipeline workloads, and hardware conditions. CacheFlow reduces TTFT by 10%–62% over existing advances (§ 4 ). 2 Background and Motivation LLM serving consists of two sequential stages: a prefill stage that processes the input context and produces the first output token, and a decode stage that autoregressively generates subsequent tokens ( 21 ) . During prefill, the model materializes the KV cache, intermediate representations of each token at every attention layer, which are retained in GPU memory to enable efficient reuse during decoding to avoid recomputation. KV cache as a first-order resource bottleneck. For a transformer with L layers, H attention heads, and per-head dimension d , serving a request of length N requires storing 2\times L\times H\times d\times N elements in the KV cache. This linear scaling with respect to sequence length. With rapidly increasing context sizes in modern workloads, the KV cache becomes a dominant consumer of GPU memory. Figure 1(a) shows that real-world workloads, including multi-turn chatbots and AI-assisted coding and tool-call agents, can reach over 20,000 tokens per request. This corresponds to KV cache sizes of 2.8 GB for models such as Qwen3-8B, 9.7 GB for Llama-3.1-405B for a single request, and even larger for reasoning-oriented models such as DeepSeek-R1. These requirements far exceed the memory capacity of a single GPU, forcing systems to either offload KV cache to lower tiers ( 14 ; 17 ) or discard and recompute it on demand ( 1 ; 21 ) . KV cache restoration becomes a key latency bottleneck. Restoring KV cache is on the critical path of prefill and directly determines Time-To-First-Token (TTFT), a key latency metric for interactive applications. However, existing strategies incur substantial latency. As shown in Figure 1 , recomputation can take over 1.2–1.5 seconds for long contexts on modern GPUs, far exceeding typical latency targets ( \sim 200 ms). In contrast, I/O-based restoration can be faster under ideal conditions (e.g., 80 Gbps), but is highly sensitive to bandwidth; under realistic conditions (e.g., 10 Gbps, typical disk