PaperlayerView exact revision on arXiv

Source-linked AI summary

When the KV Cache Is Slower Than the GPU: Scaling Remote KV Tiers for Context-Parallel Prefill

Muhammad Ibrahim

arXiv:2610.21500v1cs.DCcs.LG

TL;DR

Remote KV tiers promise reuse across engines, but this paper finds that loading can be slower than recomputing and can destabilize hit-heavy service. It models the costs and redesigns storage and loading around context-parallel ranks; the resulting changes sharply reduce hit-heavy p99 latency.

  • Problem

    Remote KV tiers are attractive for sharing reusable prompt caches, but the assumption that loading KV is cheaper than recomputing failed in the studied production setting.

    Source: §1 · p. 1

  • Method

    The paper replays a reconstructed production request stream, models hit costs, and shards MLA KV storage across context-parallel ranks with rank-partitioned remote instances and asynchronous loading.

    Source: §3 · p. 2, §1 · p. 2, §5.1 · p. 4

  • Results

    Hit-heavy p99 fell from 83.32 s to 0.67 s, a 124× reduction, with 98.5% of prompt tokens served from L2.

    Source: §1 · p. 2, §10 · p. 8

  • Takeaways & Limitations

    For GLM-5.3 on a B300 node, a cache tier must meet the prefill-rate bandwidth bar, and rank scaling or concurrent loading can address the shortfall.

    Source: §7 · p. 7

    Each condition was run once, and the replays omit decode handoff and use one engine as the only Valkey client, leaving shared-instance contention unmeasured.

    Source: §8 · p. 8

Abstract

from arXiv · show

Reusing the attention KV cache across requests is a standard way to cut prefill cost in long-context LLM serving, and production systems increasingly back the per-engine cache with a remote tier shared by every engine. We study such a tier in a disaggregated deployment of GLM-5.3, an FP8 mixture-of-experts model with multi-head latent attention (MLA), on 8xB300 nodes running prefill context parallelism (PCP8). Enabling the remote tier (LMCache with a Valkey store) left median time-to-first-token unchanged but raised the 16k-token p99 from 3.96 s to 17.3 s. Replaying a production request stream on an isolated engine, we find that a remote hit took 0.88 s against 0.31 s to recompute the prompt, and that synchronous loading turned a hit-heavy stream into an unstable queue: p99 83.32 s with the GPUs 7% busy. A two-term cost model explains both: a hit pays off only if the tier delivers more than B* = sR (2.53 GB/s for this model and GPU), and a fixed per-hit engine cost (T0 ~ 0.33 s) means that hits on prompts shorter than about 17k tokens cannot beat recompute at any bandwidth. Guided by the model, we (i) shard the MLA KV store across PCP ranks, with a proof that the existing minimum-over-ranks lookup returns the longest cached prefix and a load protocol that can never desynchronize collectives; (ii) partition the remote tier by rank, one server instance per rank with no coordination, which raises GET bandwidth 6.3x to 10.76 GB/s; (iii) add asynchronous loading to the sharded store; and (iv) fix three client bugs that caused unbounded stalls. On the hit-heavy stream, with 98.5% of prompt tokens served from the remote tier, p99 falls from 83.32 s to 0.67 s. The sharded store raises prefill throughput by 14%, and by 34% together with an upstream kernel fix. All changes are submitted upstream to LMCache.

1 Introduction

Remote KV tiers promise reusable cache capacity, but their value depends on loading KV faster than recomputing it. In the studied production setting, enabling the tier worsened tail latency; replay and analysis motivate a rank-sharded, asynchronous design.

1 Introduction

  • At 16k tokens, enabling L2 raised p99 TTFT from 3.96 s to 17.3 s, while median TTFT stayed unchanged.At 32k tokens, p99 rose from 6.06 s to 25.0 s; the deployment was rolled back to L1 only.Source: §1 · p. 1
  • A 16k-token L2 hit took 0.88 s versus 0.31 s to recompute, and synchronous hit-heavy replay grew to 52.30 s median latency with GPUs 7% busy.The introduction attributes the regression to hits slower than misses, queue instability, and rare client bugs that could cause unbounded stalls.Source: §1 · p. 1
  • The proposed design shards MLA KV across PCP ranks, partitions remote storage by rank, adds asynchronous loading, and fixes three client bugs.The existing minimum-over-ranks lookup returns the longest cached prefix, while the load protocol keeps every rank issuing the same collectives.Source: §1 · p. 2
  • On the hit-heavy stream, p99 fell from 83.32 s to 0.67 s with 98.5% of prompt tokens served from L2; sharding raised prefill throughput by 14–34%.A five-node disaggregated deployment using the changes passed the workload’s SLA.Source: §1 · p. 2
  • A remote cache tier should be judged against the hardware’s prefill rate, not merely network latency.The paper frames recomputation on current GPUs as a demanding baseline.Source: §1 · p. 2

2 Background

The background describes why KV size and rank synchronization matter for caching in this deployment. It also outlines the cache layout and the single-threaded execution constraint of its remote store.

2 Background

  • MLA projects each token’s keys and values into one low-rank latent shared by attention heads, making KV state independent of head count.For GLM-5.3 FP8, a 256-token chunk across all layers is 12.4 MB, or about 48.4 KB per token.Source: §2 · p. 2
  • PCP splits prompts across ranks, then uses AllGather so causal attention can access earlier-token KV; afterward, every rank holds the full latent KV.Collectives keep ranks in lockstep, so a delay to any rank delays all of them.Source: §2 · p. 2
  • In the disaggregated setup, prefill computes or loads prompt KV and sends it to a decode engine over NIXL.Prefill and decode are separated because prefill is compute-bound while decode is memory-bandwidth-bound.Source: §2 · p. 2
  • LMCache chunks KV under token-prefix hashes; lookup returns the longest fully cached prompt prefix, with later tokens recomputed after a gap.For MLA, the original setup stores and loads only on worker 0 because tensor-parallel ranks hold the same latent KV.Source: §2 · p. 2
  • A Valkey instance executes commands on one main thread, so its command throughput is bounded by one core regardless of client count.I/O threads parallelize socket reads and writes, not command execution.Source: §2 · p. 2

3 Methodology

The methodology reconstructs a production prefill request stream and replays it on an isolated engine. Separate cache-state runs and profiling distinguish latency measurement from time attribution.

3 Methodology

  • The replay reconstructs 683 requests from router logs and the benchmark database, preserving original prompts and send times from one production engine’s 16k-token workload cell.The replayer records completion time, prompt tokens, and cached tokens.Source: §3 · p. 2
  • Replays ran on a free 8×B300 node with the production container image and configuration, but used prefill only, a private Valkey instance, and no production router selection.A sampler recorded engine metrics and Valkey GET command statistics.Source: §3 · p. 2
  • The hit-path subset uses the first 450 requests, whose 7.35M prompt tokens fit in Valkey; after priming and clearing L1, 98.5% of prompt tokens came from L2.The same requests in a cold run provide the recompute baseline.Source: §3 · p. 2
  • Nsight Systems and py-spy profiled GPU workers and engine stalls, but profiled runs were used only to attribute time, not as latency measurements.The original system overview describes every chunk from rank 0 being stored in a single Valkey instance.Source: §3 · p. 2, Figure 1 · p. 3
  • Each condition was run once, and reported percentiles use linear interpolation over all requests in a run.A single script computes every §6 number from raw per-request logs.Source: §3 · p. 3

4 A Cost Model for Remote KV Hits

The cost model compares recomputation with remote loading using a bandwidth-dependent transfer term and fixed per-hit overhead. Its thresholds explain why the measured single-instance path loses to recomputation and why short prompts may not benefit even with faster storage.

4 A Cost Model for Remote KV Hits

  • Ignoring T0, a remote hit pays off iff B > B* = sR; for GLM-5.3 FP8 on one B300 node, 48.4 KB/token times the median cold-miss rate of 52.2k tokens/s implies about 2.53 GB/s.Source: §4 · p. 3
  • The single Valkey instance delivered at most 1.71 GB/s to eight PCP ranks, below break-even, so every L2 hit was slower than recomputing.Figure 2 compares the model with a 16k-token hit measurement; its dashed line marks measured recompute median.Source: §4 · p. 3, Figure 2 · p. 3
  • Fixed per-hit cost T0 makes the payoff length-dependent: the implied threshold is about 17k tokens, below which recomputing is faster at any bandwidth.T0 is fitted at about 0.33 s; the model predicts a 0.79 s 16k hit on one instance, close to measured 0.83–0.88 s.Source: §4 · p. 3
  • At 16k tokens, L2 may still save GPU compute when prefill engines are saturated, even though it cannot improve median latency.The capacity benefit does not change the model’s latency threshold for this hardware and implementation.Source: §4 · p. 3
  • With synchronous loading, hit-heavy arrivals produced utilization ρ≈1.13, so the queue had no steady state while hits continued arriving.The eight-instance configuration instead had ρ≈0.09.Source: §4 · p. 3

5 Design

The design shards MLA KV work across PCP ranks and partitions the remote tier by rank to increase bandwidth while keeping the engine running during slow loads. It also extends asynchronous loading to the sharded store and fixes three client bugs associated with stalls.

5.1 Sharding the MLA KV Store Across PCP Ranks

  • Rank 0 wrote 19.1 GB to host memory and accumulated rank waits during two concurrent ∼200k-token prompts, motivating storage across PCP ranks.Rank 0 was 82% busy versus 98% on other ranks, which each accumulated ∼1.55 s of AllGather wait in a 9.5 s window.Source: §5.1 · p. 4
  • Each rank stores, looks up, and loads only chunks it owns, with chunk c assigned to rank c mod W and each rank receiving 1/W of the engine’s host-memory budget.Because every rank holds the whole prompt’s KV after AllGather, any rank can store any chunk; total memory is unchanged.Source: §5.1 · p. 4
  • The scheduler’s existing minimum-over-ranks lookup returns exactly the longest prefix whose chunks are all present, so sharded lookup needs no new messages.The proposition establishes that the minimum of the ranks’ first-missing-chunk answers is the first missing chunk overall; the claim was also checked exhaustively up to 10 chunks and W∈{2, 3, 4, 8}, and on random prompts up to 800 chunks.Source: §5.1 · p. 4
  • Every rank fetches and stages its owned chunks, exchanges fingerprints and failure metadata, agrees on a prefix, then broadcasts its chunks so all ranks follow the same collectives.Local failures become an agreed shorter prefix, while mismatched inputs produce an agreed prefix of zero; tests check these invariants under random failures and repeated failed loads.Source: §5.1 · p. 4

5.2 A Rank-Partitioned Remote Tier

  • The static rank partition lets each rank use its own remote-store instance without routing or inter-instance traffic while retaining cross-engine reuse.Each instance serves its rank’s chunk indexes, fetched in parallel with the other ranks.Source: §5.2 · p. 4, §5.1 · p. 4

5.3 Asynchronous Loading for the Sharded Store

  • Asynchronous loading extends to sharded storage by having each rank prefetch its owned chunks and use a cumulative-length vector that preserves the agreed-prefix lookup.A property test over 3,000 random presence patterns checks equivalence with the synchronous path; a rank with no hits reports the first entry of its vector.Source: §5.3 · p. 4

5.4 Three Client Bugs

  • Three client bugs caused stalls: lost completions, missing-key GETs that never returned, and asynchronous GETs using the wrong key.Fixes synchronize completion registration and draining, parse null replies as per-key misses, and rewrite asynchronous GET keys to the worker-0 name.Source: §5.4 · p. 5

6 Evaluation

Across replay evaluation, the rank-partitioned remote tier with fixes reduced hit-heavy p99 latency to 0.67 s, while sharding improved prefill throughput. Correctness tests passed, and the end-to-end deployment comparison is contextual because it also changes parallelism and prefill/decode placement.

6.1 Where a 16k-Token Prompt’s KV Comes From

  • 2.7× slower than recompute, a single L2 instance loaded prompts even on an idle engine; L1 was slightly faster than recompute.The comparison replays the 683-request 16k-token stream.Source: §6.1 · p. 5, Table 1 · p. 5

6.2 Remote-Tier Bandwidth

  • 10.76 GB/s aggregate GET bandwidth (6.3×) came from one remote-store instance per rank; adding eight clients to one instance improved bandwidth by only 13%.A rank’s 99 MB batch took 70 ms with one instance per rank, versus 440 ms at p50 on one instance.Source: §6.2 · p. 5, Figure 3 · p. 5

6.3 Hit-Heavy Traffic

  • H1b median latency rose from 3.52 s in the first third to 52.30 s in the last, with up to 59 requests in the engine and GPUs 7% busy.Every request completed, but the engine spent most of its time waiting for Valkey.Source: §6.3 · p. 5, Figure 6 · p. 7
  • With one instance and asynchronous loading, 49% of requests hit the 3 s timeout and recomputed while prefetch continued; only 50.6% of tokens came from L2.This configuration had the same number of GETs as H1b.Source: §6.3 · pp. 5–6
  • With one instance per rank and all fixes, p99 fell to 0.67 s, 124× below H1b; median latency was 0.41 s.The latency distribution was close to the production engine’s on the same requests.Source: §6.3 · p. 6, Figure 5 · p. 6, Figure 4 · p. 6

6.4 Prefill Throughput

  • Together, sharded storage and the upstream kernel rewrite delivered 57.3–58.0k tokens/s (+34%), within 4–5% of running without LMCache.The sharded store alone raised throughput from 43.2k to 49.4k tokens/s (+14%).Source: §6.4 · pp. 6–7, Figure 7 · p. 7

6.5 Correctness

  • 24/24 needle-prompt answers found the hidden code; cache-served answers differed from cold runs no more than two cold runs differed.The synchronous sharded store also passed 36/36 concurrent answers and a 30-minute, 1,549-request soak without errors.Source: §6.5 · p. 7

6.6 End-to-End Deployment

  • The 200k-token SLA comparison changes parallelism and prefill/decode placement as well as cache configuration, so it is deployment context rather than a techniques ablation.The benchmark is compared with earlier deployments that passed the same benchmark.Source: §6.6 · p. 7, Table 3 · p. 7

7 Discussion

Remote KV tiers must be judged against GPU prefill speed, while fixed loading costs and context-parallel lockstep constrain their usefulness. Static rank ownership supports coordination-free scale-out, but short prompts can remain slower than recomputation.

7 Discussion

  • 2.53 GB/s per prompt is the break-even bandwidth for one B300 node; faster GPUs raise the bandwidth a tier must deliver to justify reading.The discussion suggests scaling general-purpose key-value servers with engine parallelism or using RDMA; compression and concurrent loading/computation can reduce the transfer trade-off.Source: §7 · p. 7
  • On this implementation, remote hits below about 17k tokens cannot beat recomputation at any bandwidth because T0 is approximately 0.33 s.The authors propose batching chunk broadcasts, overlapping exchange with fetch, or choosing load versus recompute per request to reduce the fixed-cost penalty.Source: §7 · p. 8
  • Static chunk-index ownership enables coordination-free rank scale-out, while capacity beyond the rank count requires a second-level hash within each rank’s partition.Scaling the instance count with W preserves one-server-per-rank communication.Source: §7 · p. 8
  • Under PCP, any per-rank stall—including a slow GET or lost completion—stalls all ranks, so potentially unbounded blocking should stay out of the step.The discussion recommends symmetric per-rank work for context-parallel engines.Source: §7 · p. 8

8 Limitations •

The evaluation has limited repeatability, deployment scope, prompt-length coverage, cache-state realism, and end-to-end comparability; small differences are not established.

8 Limitations •

  • Each condition was run once, so differences under about 10%—including H3 against H4—are not established.The authors characterize larger effects such as 124× at p99 and 6.3× bandwidth as far outside run-to-run variation.Source: §8 · p. 8
  • Replays cover prefill on one engine, omit KV handoff to decode, and do not measure contention from several engines sharing Valkey instances.At the workload’s approximately 0.45 requests/s per engine and 0.79 GB per prompt, six engines are estimated to draw about 2 GB/s, below 10.76 GB/s.Source: §8 · p. 8
  • Latency results cover 14.7k–17.9k-token prompts; T0 is fitted on one point, and its implied prompt-length threshold remains unmeasured.Source: §8 · p. 8
  • The hit-heavy subset fits in a private instance, unlike production’s full evicting instance, and the end-to-end comparison changes more than the cache tier.Source: §8 · p. 8

9 Related Work

Prior work addresses prefix reuse, disaggregated KV storage, transfer-versus-recomputation trade-offs, and context parallelism. This paper characterizes remote-tier break-even and applies context parallelism to scale the tier.

9 Related Work

  • vLLM’s PagedAttention and SGLang’s RadixAttention reuse prefixes within an engine, while CachedAttention keeps conversation KV in host memory and disk and overlaps loading with computation.Source: §9 · p. 8
  • MemServe [6] adds an elastic memory pool, while LMCache [19] provides the multi-tier cache layer this work builds on; the paper characterizes when remote tiers are slower than recomputation.It also shows how context parallelism enables coordination-free scale-out of the tier.Source: §9 · p. 8
  • CacheGen compresses KV, Cake [14] loads and computes different prompt parts concurrently, and HCache restores cached hidden states through partial recomputation.The paper’s cost model makes the remote-tier trade-off explicit, including a fixed cost these techniques act on through its s and B terms.Source: §9 · p. 8
  • DistServe and Splitwise separate prefill from decode, while Ring Attention [17], DeepSpeed-Ulysses [13], and context-parallel inference split sequences across devices.The paper reports that combining MLA, context parallelism, and a tensor-parallel-oriented cache concentrates I/O on one rank, then presents a sharded store grounded in the existing lookup protocol.Source: §9 · p. 8

10 Conclusion

The conclusion frames remote KV reuse as a competition with recomputation: bandwidth, fixed engine cost, and synchronous loading can make hits slower or destabilize queues. Rank-sharded storage, asynchronous loading, and client fixes reduce hit-heavy p99 to 0.67 s.

10 Conclusion

  • 0.67 s is the hit-heavy p99 after sharding the MLA store across context-parallel ranks, partitioning the tier by rank, adding asynchronous loading, and fixing three client bugs.The comparison is against 83.32 s; the conclusion also states that one B300 node requires more than 2.53 GB/s for a cache hit to beat recomputation, while fixed engine cost puts short prompts out of reach.Source: §10 · p. 8

Availability

The sharded store, per-rank remote URL, asynchronous loading, and three client fixes were submitted upstream to LMCache.

Availability

  • All four changes—the sharded store, per-rank remote URL, asynchronous loading, and three client fixes —were submitted upstream to LMCache.Source: Availability · p. 8

Related papers

Loading 2610.21500v1…