KVStream: Adaptive Parallel Storage Management for KV Caching in Large-Scale LLM Serving

1 Introduction

• For evaluated workloads, unique KV working sets exceed GPU and host budgets: 14B models span 0.5–1 TB, while 110B reaches about 2 TB.The 14B working set is 3.3–7.2× the GPU KV budget; at 110B it is up to 6.3× a node’s host-memory KV cache.Source: §1 · p. 1
• Existing connectors read matched chunks serially and without overlap, while remote PFS bandwidth remains idle and storage-backed retrieval can dominate step time.Source: §1 · p. 2
• KVStream casts retrieval over heterogeneous tiers as aggregate-bandwidth scheduling, and its adaptive completion-driven routing reaches within 5% of the bound.Source: §1 · p. 2
• KVStream batches step-level reads, defers writes behind the forward pass, replicates chunks across tiers, and lets each free tier claim the next unread chunks.Source: §1 · p. 2
• The model predicts that static NVMe:PFS splits incur a penalty as tier bandwidths deviate and relates TTFT to arrival order and rate, host memory, and input and output lengths.Source: §1 · p. 2
• Across four models, six datasets, and up to 128 GPUs, KVStream achieves up to 1.49× higher offline throughput than LMCache and up to 6.1× lower mean TTFT under bursty arrivals.Source: §1 · p. 2
• Benefits erode when small working sets or sparse reuse remove storage from the critical path; replication doubles writes and can slow iterations if they cannot drain behind the forward pass.Source: §1 · pp. 2–3

2 Background and Problem Formulation

• Connectors retrieve matched cached chunks from the fastest tier holding them, while storage-backed caching trades recomputation for I/O.Chunks may be on the GPU, in host memory, or only on storage; storage-only chunks are read into host memory and then copied to the GPU.Source: §2 · p. 3
• Read reduction methods shrink prefix size, faster backends accelerate a tier, and reuse-aware schedulers keep shared prefixes hot; these approaches do not read one step’s prefixes from several tiers at once.Reordering can suit offline batches, but online serving must respect arrival order; better eviction helps when the working set between reuses is not much larger than memory.Source: §2 · p. 3
• An inference step’s wall-clock time comprises prefix retrieval, the forward pass, and persistence of newly generated KV.Every participating tensor-parallel GPU needs the batch’s matched chunks before the synchronous step can begin.Source: §2 · p. 4
• Offline serving is governed by total step time, while online TTFT includes queueing behind prior work and the request’s prefill step.A long step also delays requests queued behind it.Source: §2 · p. 4
• The storage engine must accelerate scheduler-selected batches despite unknown chunks and fluctuating device bandwidth, without reordering requests.Read bandwidth varies with writes, competing tensor-parallel ranks, and other jobs.Source: §2 · p. 4

3 Gap Analysis and Observations

• A seven-request 70B step spends 4.7 s retrieving because LMCache completes each request’s reads and copies before starting the next request.Storage reads per request take 600–1300 ms; the sequential pipeline keeps I/O queues shallow and interconnects idle.Source: §3 · p. 4
• 80–88% of LMCache processing time is retrieval across model sizes; at larger models, LMCache finishes up to 2.2× sooner than CPU-only.Figure 6 breaks down CPU-only and LMCache processing time across model sizes; LMCache matches CPU-only at 14B.Source: §3 · p. 4
• On Testbed-2, concurrent NVMe read p99 latency reaches 898 ms versus a 123 ms isolated p50, while PFS read p99 is 795 ms versus a 102 ms median.The heavy tails and competing ranks make chunk latency and bandwidth fluctuate across inference steps, undermining static tier splits.Source: Figure 8 · p. 5, §3 · p. 5
• Doubling host memory cuts Chutes storage reads by 98.6% and mean TTFT 3.5×, but changes Qwen-Coder reads by less than 1%.In Qwen-Coder, mean TTFT stays between 0.76 and 0.90 s; Figure 9 brackets show storage reads per rank.Source: Figure 9 · p. 5, §3 · p. 5
• Concurrent 1 TB reads and writes take 6% longer on Testbed-1 and 27% longer on Testbed-2 than isolated operations, while PFS bandwidth is otherwise idle during inference.The local NVMe is only 2.2× and 3.2× faster than the PFS in isolation on Testbed-1 and Testbed-2, respectively.Source: §3 · p. 5
• For Qwen-Coder, round-robin session interleaving yields 42.8 s mean TTFT, while cache-friendly arrival order yields 0.42 s; raising arrival rate also increases queueing and TTFT.At fixed round-robin order, mean in-flight requests grow from 3.4 to 128 as mean TTFT rises 120×, from 0.36 to 42.8 s.Source: Figure 10 · p. 5, §3 · p. 5

4.1 KVStream’s I/O Mechanisms

• KVStream pools storage reads across a step, defers writes behind the forward pass, replicates each chunk across tiers, and uses completion-driven routing without prediction or runtime tuning.The design preserves the engine’s batch order; pooling lets early-finishing tiers take more work.Source: §4 · p. 6, §4.1 · p. 6
• Replicating chunks on every tier lets any prefix chunk be read from whichever tier is free, using otherwise idle aggregate bandwidth.The extra copy normally stays off the read path because writes are deferred, but replication still consumes write bandwidth.Source: §4.1 · p. 6

4.2 I/O Lifecycle of an Iteration

• After matching the batch, the lifecycle submits storage chunks as one pool, reads from opposite ends in batches, and lets each completing tier claim more chunks.Host-resident chunks are copied concurrently; staged writes are submitted before the forward pass, which overlaps them.Source: §4.2 · p. 7

4.3 Implementation

• The standalone C++ io_uring engine plugs into LMCache as a storage backend, allowing integrated engines such as vLLM to use multi-tier retrieval without code changes.In SGLang’s HiCache, writes are synchronous and do not overlap retrieval.Source: §4.3 · p. 7

5.1 Retrieval Demand as Function of Reuse Distance and Memory Capacity

• Storage demand is reused KV volume times the probability that reuse distance exceeds GPU-plus-host cache capacity under LRU; request order and provisioning affect misses.Source: §5.1 · p. 7

5.2 Aggregate-Bandwidth Bound and the Static-Split Penalty

• Completion-driven, work-conserving routing reaches the aggregate-bandwidth retrieval bound without bandwidth monitoring, with only each tier’s final batch mismatch remaining.Each tier claims unread chunks when it finishes its batch, so faster tiers take on more work.Source: §5.2 · p. 8
• A 75:25 NVMe:PFS split meets the bound at 3 and 1 GB/s, but is 12.5% slower when NVMe drops to 2 GB/s and loses to NVMe alone at PFS 0.5 GB/s.Source: §5.2 · p. 8

5.3 End-to-End Gains and Losses

• End-to-end service-time gains are capped by retrieval’s share of a step and become negligible when memory serves most prefixes or long outputs stretch forward computation.Source: §5.3 · p. 8
• At moderate or high load, faster retrieval can improve TTFT beyond per-request savings by draining the queue and starting waiting requests sooner.Source: §5.3 · p. 8
• Replication writes stay off the critical path only when they drain behind forward passes; the second tier gains little or loses when storage demand is small.This includes cases where memory holds the reuse working set, arrival order keeps reuse distances short, or reuse is sparse.Source: §5.3 · p. 8

6.1 Experimental Setup

• Evaluations span four models from 14B to 110B, three offline datasets, three online traces, and two testbeds; online runs measure TTFT and SLO attainment.Offline throughput is measured as total tokens processed divided by wall-clock serving time.Source: §6.1 · pp. 8–9

6.2 Online Serving: TTFT, SLOs, Load, and Reuse

• Mean-TTFT speedup over LMCache rises with arrival rate to 3.12× on Qwen-Coder and 2.01× on Chutes; on SWE-bench, it reaches 6.07× at arrival CV 4.On Qwen-Coder, retrieval is 15–22% faster at every rate, while the queue grows substantially with load.Source: §6.2 · p. 10, Figure 13 · p. 10, Figure 14 · p. 11

6.3 Closed-Loop Offline Dataset Results

• 1.49×: KVStream reaches this throughput advantage over LMCache at 110B; across LooGLE, NarrativeQA, and CUAD at 32B, its advantages are 1.37×, 1.21×, and 1.05×.The gain comes from retrieval: KVStream adds 2.8–4.9 GB/s of PFS reads to similar NVMe bandwidth.Source: §6.3 · pp. 10–11, Figure 18 · p. 11
• From 16 to 256 output tokens, KVStream’s throughput advantage over LMCache stays between 1.19× and 1.37× on LooGLE.Longer decode phases dilute retrieval’s share of step time, capping the speedup.Source: §6.3 · p. 11, Figure 19 · p. 11

6.4 Attaining the Aggregate-Bandwidth Bound

• KVStream stays within 4.3% of the aggregate-bandwidth bound; the best static split has an 8.0% gap and throughput 4.6% below KVStream.With co-located PFS traffic, the static gap grows to 11.8–23.6%, while KVStream remains within 4.3% of the bound.Source: §6.4 · p. 11, Figure 20 · p. 12, Figure 21 · p. 12

6.5 Demand and Write Cost: Host Memory and Arrival Order

• Storage-read predictions track measurements across 20–2410 GB per rank, but doubling host memory cuts Chutes reads 70× and leaves Qwen-Coder reads flat.More memory reduces storage I/O when reuse distances straddle capacity; interleaved sessions can keep spilling.Source: §6.5 · p. 12

6.6 Scaling and Ablations

• From 4 to 32 nodes, KVStream maintains a 1.23–1.36× throughput advantage over LMCache on NarrativeQA; p90 step time stays near 2.7 s.At 32 nodes, KVStream’s p99 step time remains 1.4× below LMCache’s.Source: §6.6 · p. 12, Figure 26 · p. 13
• Offline, adding replication and a fixed 70:30 split raises throughput to 1.24× LMCache’s, and completion-driven routing raises it to 1.48×.Online at high arrival rate, the full design lowers mean TTFT 2.39× versus LMCache; alternate replication policies remain 12–74% above the bandwidth bound or up to 5% slower than KVStream.Source: §6.6 · pp. 12–13

Larger memories

• Larger memories reduce storage-bound reuse, but workloads with many long sessions can still spill beyond memory.Most reuses in the round-robin Qwen-Coder trace would fit the cited Vera Rubin memory configuration, while 100 resumable 1M-token sessions of a 70B model need about eight times that memory.Source: §7 · pp. 13–14

Other second tiers

• An independent second tier can add bandwidth even if it is slower, but its write path must keep up with replicated writes.Examples include managed file systems, object stores, remote NVMe, and CXL-attached memory.Source: §7 · p. 14

Many nodes

• Per-node completion-driven routing adapts to shared-PFS congestion without coordination, while shared-copy coordination could reduce capacity use and writes.The section reports KVStream’s advantage at up to 128 GPUs and leaves coordination for dynamically scaling nodes as future work.Source: §7 · p. 14

KV compression

• Compression reduces both reused KV volume and reuse distance, while KVStream accelerates the remaining spill across storage tiers.Even after 8× compression, 100 resumable 128K-token sessions of a 70B model require about 500 GB of KV, exceeding the cited 320 GB of host memory devoted to KV.Source: §7 · p. 14

Request reordering

• Reuse-aware reordering and KVStream can compose when serving order is flexible, but a cache-friendly order may leave little for a second tier to accelerate.For online latency objectives or dependent multi-turn sessions, arrivals set the demand and the read path can be made faster instead.Source: §7 · p. 14

Disaggregated prefill and decode

• Disaggregated prefill and decode change where KV is produced and consumed, not how prefixes return from storage; KVStream’s routing can extend across their independent paths.The described paths include memory on both prefill and decode nodes, as well as the PFS.Source: §7 · p. 14

• Up to 1.49× higher offline throughput than LMCache and up to 6.1× lower mean TTFT under bursty arrivals are reported for KVStream.The evaluation spans up to 128 GPUs.Source: §8 · p. 14
• KVStream retrieves within 5% of the aggregate-bandwidth bound in the reported evaluation.Source: §8 · p. 14
• The design batches each step’s reads, defers writes behind the forward pass, replicates chunks on every tier, and routes reads by completion.The model says this attains the aggregate-bandwidth bound for any per-tier bandwidths, whereas static splits lose as bandwidths drift or fluctuate.Source: §8 · p. 14

• Appendix A.1, A.2, and A.3 extend Sections 6.2, 6.3, and 6.5, respectively.Source: A Additional Experimental Results · p. 16
• Online appendix runs serve the 32B model on one Testbed-2 node.The stated setup follows Section 6.1.Source: A Additional Experimental Results · p. 16
• Offline appendix runs serve LooGLE on one Testbed-1 node, with TP=4.The stated setup follows Section 6.1.Source: A Additional Experimental Results · p. 16

SLO attainment on the production traces

• At medium Qwen-Coder arrival rate, median TTFTs differ by only 1.14×, yet KVStream has 3.35× fewer requests miss the 5 s SLO.Source: §A.1 · p. 16
• At high arrival rates, KVStream’s TTFT curve lies well above LMCache’s on both traces, with gains concentrated in queued requests.Source: §A.1 · p. 16

Retrieval versus queueing on Chutes

• On Chutes, KVStream retrieves about 1.3× faster per request at every rate, while queueing carries the speedup from 1.23× to 2.01× as rate rises.Source: §A.1 · p. 16

A second serving engine

• KVStream lowers SGLang mean TTFT 1.57× against HiCache’s file backend and 1.22× against Mooncake; in vLLM, it has the lowest mean, p50, and p90 TTFT.In SGLang, HiCache makes KVStream write synchronously, without M2’s deferred writes.Source: §A.1 · p. 16

A.2 Offline Throughput

• At 70B, KVStream serves LooGLE in 25 minutes, versus 37 for LMCache and 64 for CPU-only.LMCache and KVStream spend nearly the same compute and store time, so the gain lies in retrieval; deferred writes drain during the forward pass.Source: §A.2 · p. 16
• Storage serves about a third of chunks at 14B and about 60% at 70B and 110B, while KVStream reads at both tiers’ combined bandwidth.LMCache and KVStream serve nearly the same shares from GPU, host memory, and storage, so they face the same storage demand.Source: §A.2 · p. 16
• With 60 to 100 GB of host memory per rank, LooGLE storage reads fall from 2,832 to 1,856 GB, but KVStream’s advantage over LMCache remains 1.37–1.41×.Every approach speeds up, but LooGLE continues spilling at every host-memory size.Source: §A.2 · p. 16

A.3 Storage Demand and Write Cost

• On Chutes, storage reads fall from 1412 to 20 GB per rank as host memory grows, and KVStream’s speedup falls from 1.71× to 0.98×.On Qwen-Coder, reads remain 1428 GB per rank and mean TTFT stays near 0.56 s for KVStream, versus 0.76–0.90 s for LMCache.Source: §A.3 · p. 16, Figure 35 · p. 17
• With Qwen-Coder, reads grow 5.8× from cache-friendly to round-robin arrival order, while KVStream’s speedup rises from 1.05× to 3.12×.KVStream has the lowest p90 in every order; CPU-only completes only 6200 and 4600 of 6934 requests in the random and round-robin orders, so those bars are lower bounds.Source: §A.3 · pp. 16–17, Figure 36 · p. 17
• Across 120 s intervals, writes are exactly replicated; rank 0 writes 549.7 GB to each tier, and PFS serves 22–29% of reads, near its 24% bandwidth share.Completion-driven routing reaches the split without measuring bandwidth.Source: §A.3 · p. 17, Figure 37 · p. 17