acceptodds
Under review as a conference paper at ICLR 2027

The Hit Is (Almost) Always Cheaper: Prefix-Cache Economics on Bandwidth-Rich, FLOPs-Poor Accelerators

Abstract

Automatic prefix caching (APC) is widely described as an almost-free win: when a request shares a prefix with a prior one, the engine skips recomputing the shared tokens’ key/value (KV) cache. We present a controlled measurement study of what a prefix-cache hit actually costs and buys on a bandwidth-rich, FLOPs-poor accelerator (NVIDIA H20-141GB), where folklore calibrated on compute-rich parts may not transfer. Across Qwen2.5 models at 0.5B–7B, contexts up to 32K, and batches 1–64, we fit a two-term cost model that separates the compute-bound recompute path from the bandwidth-bound hit path, and validate it end-to-end on vLLM. Three findings organize the results. First, hits win overwhelmingly at realistic prefix lengths — up to 169× lower suffix-prefill latency at 32K context — and no measured regime inverts (512 tokens, the grid’s shortest, already sits above the fitted crossover); the honest boundary of the win is a short-prefix crossover (locally fitted at 152–635 tokens at batch 1; a slope-poor interpolation, with the win settling near 1.7× at 128-token prefixes end-to-end) and a fixed 15–21 ms hit-path floor. Second, the hit path is not free even when it wins: materializing paged KV state with a 16-token-block gather achieves only 0.135–0.141 TB/s at small working sets (0.072 TB/s at 30 GB) versus 1.10 TB/s for a contiguous device copy — an 8–15× penalty on any back-end that materializes paged KV through gather-like scattered reads (engines that share physical blocks, such as vLLM’s APC, avoid this path). Third, 141 GB capacity declines with workload skew but does not vanish: under Zipf popularity with exponent 1.0, a 30 GB LRU budget still leaves 21 points of hit rate on the table versus 106 GB; only at exponent 1.4 does the gap close to 9 points. We release all harnesses and raw results.

Primary area:
foundation or frontier models, including LLMs
Keywords:
prefix caching, KV cache, TTFT, vLLM, APC, H20, measurement

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_fvUfOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

In practical LLM hosting, many requests share content with earlier ones (a system prompt, a document, a chat history), so it is beneficial for the LLM engines to store and reuse the state already computed for it. Since reuse trades computation for memory traffic, prefix caching is a natural test bed for benchmarking memory-fast against compute-fast devices, the basis of this paper. The work examines how much reuse accelerates serving on a memory-fast, compute-limited GPU (NVIDIA H20-141GB), set against assumptions carried over from compute-fast GPUs. It then looks at which conditions bring out that acceleration: the length of the shared prompt, how many requests are batched together, how the stored cache is laid out in memory, and how much cache capacity helps when some prompts repeat far more often than others. Finally, it checks how the results hold up in a production serving engine (vLLM) with caching switched on and off.

To study these claims, the authors model each path's latency as a simple straight line in prompt length: recomputing grows steeply with length because it is compute-bound, while reusing the cache grows only slightly on top of a fixed cost because it is bound by memory traffic. Overlaying the two lines gives a crossover length, below which recomputing would be cheaper, and above which reuse wins. The fitted crossover falls at roughly 100–600 tokens depending on model size and batch.

The authors report that reuse wins at every prompt length they measured, from about 3× at 512 tokens to about 169× at 32K tokens. They also find that collecting a scattered cache layout is 8–15× slower than copying a contiguous one, and that a larger cache adds 9–24 points of hit rate depending on how concentrated the traffic is. In vLLM, reuse cut latency by 8.8× at 2,048-token prompts but only 1.7× at 128 tokens, and the gain disappeared with caching switched off.

Critical strengths
  1. Modelling is straightforward and interpretable. The two-term linear model (a compute term for recompute, and a bandwidth term plus a fixed floor for the hit) captures the overall serving cost well. Each parameter has a physical interpretation, and parametric variations of the fit can explain many serving scenarios on a particular GPU. The authors are open about the model’s limits: they document why a pooled fit failed (Appendix A) and report R² for every per-batch fit. The model can be extended to any new hardware and compared against established ones for an expected speed-up in practical hosting scenarios.

  2. Experiments are carefully set up and deeply probed. Both paths share weights, seeds and prompt distribution; prompt lengths are verified per request, and a unique-prefix negative control removes reuse while holding everything else fixed. The authors go beyond the main timing grid: a memory probe isolates the cache-layout effect, a capacity simulation sweeps traffic skew, and an end-to-end vLLM arm confirms the kernel-level ordering with both an APC-off baseline and a reuse-blocked control. In doing so they also surface two practical pitfalls, vLLM V1’s default-on prefix caching and a 6× tokenization overshoot, that anyone benchmarking caching should know about. These controls and setup make the reported speed-ups credible.

Critical weaknesses
  1. The study is framed around “folklore” that cache hits may stop paying off on bandwidth-rich, FLOPs-poor GPUs, and the authors set out to find the prefix length where recompute overtakes the hit. No source is cited for this folklore. The paper’s own introduction argues the opposite: §1 states a FLOPs-poor profile makes recompute comparatively more expensive, and §6 states the study was designed expecting recompute to win. It is therefore difficult to understand what exactly the authors’ motivation was in pursuing this research. A hit replaces compute with memory reads, so the less compute a device has relative to its bandwidth, the more a hit saves. And a H20 is a prime example of a bandwidth rich GPU: about 4 TB/s of bandwidth against 138 TFLOPS. Recomputing one 7B prefix token costs about 15 GFLOP, while reading that token’s cached KV is 57 KB. That is about 265,000 FLOPs per byte, four orders of magnitude above the baseline. Even at the paper’s slowest measured gather rate, reading a token’s KV takes <1 µs against 121 µs to recompute it. The paper’s own two-term model, at long prefixes, is a roofline reading of the device: the recompute slope is peak FLOPS, the hit slope is bandwidth, and the ratio between them is what the roofline already gives. The recompute-versus-load question is important when the cache lives in host memory, on disk or across a network, which is the setting of Cake, CacheGen and LMCache in §2. When the cache is already in GPU memory, reading it is almost always cheaper than recomputing it. What the roofline does not give is the fixed cost of a hit, roughly 20 ms here, and the paper does measure that carefully. But §7 states that the fitted constants should not transfer to other hardware, and no second device is measured. So, once the folklore framing is removed, the contribution is a set of constants for one GPU that the authors themselves do not expect to generalize. That is a calibration study, with very limited novelty.

  2. The two-term model fits the data well, but the paper’s reading of what its terms mean does not hold up, and the paper’s conclusions rest on that reading. The hit’s cost per cached token (β) is called a “bandwidth term” and its fixed cost a “fixed hit-path floor” made of “per-request bookkeeping, block-table construction, and the parts of suffix processing that do not scale with L” (§3). The bandwidth-rich framing of the whole paper hangs on the first label. The numbers in Table 2 do not support either. At batch 64 the fitted cost per cached token is about 60 times too large to be cache reads at the H20’s bandwidth. So, whatever that term measures, it is not the memory traffic that the model attributes. At batch 64 the suffix compute alone exceeds the fitted floor at all three model scales, so there the floor is compute. At batch 1 the floor stays at 15–21 ms across scales while the suffix compute ranges from 0.6 to 7.7 ms, so there it is mostly a per-request overhead that the paper does not identify, and in a Hugging Face DynamicCache harness it cannot be block-table construction. Moving on to the gather result, which has the same problem. The timing harness holds the cache in one contiguous buffer, so the scattered-page gather of §5.3 never occurs in any timed request. It is a separate index_select micro-benchmark, and vLLM’s APC does not take that path: as described in the PagedAttention paper (Kwon et al., 2023, §4.1), the attention kernel reads shared blocks in place through the block table, and the paper itself says APC “avoid[s] materializing” (§5.3). Yet §1 presents the 8–15× figure as a lower bound on what “any paged layout pays”. A slow generic gather is, if anything, an upper bound on that penalty, and the paper’s own §5.3 states the figure applies only “if a back-end must materialize”. The crossover is also weaker than it is presented. Eleven of the twelve fitted values in Table 2 fall below 512 tokens, the shortest prefix in the fit, though §3 calls them “an interpolation within L ≤ 4096”; they are below the smallest point used in the fit, and §7 itself concedes the high-batch values are “an interpolation artifact”. The one measurement the paper has below that point, vLLM at 128 tokens, shows the hit winning by 1.7× where the fitted lines predict recompute should be faster. The paper cites the 1.7× as consistent with the model (§3) without noting that its fitted lines predict the opposite ordering at that length. This matters because the paper’s explanation of why hits win, and where they stop winning, is the decomposition into these terms. The measurements stand true, but their interpretations does not, which ultimately is what the paper offers as its insights.

Questions for authors

On the H20, recomputing one prefix token costs roughly 15 GFLOP while its cached KV is 57 KB to read, a ratio of about 265,000 FLOPs per byte against the device’s ridge of about 34. Given that gap, what led the authors to expect recompute could beat the hit on this device, and what is the source of the “folklore” the paper tests?

Reviewer_wpPSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a measurement study of prefix-cache reuse versus recomputation on the NVIDIA H20, a bandwidth-rich, FLOPs-poor accelerator. The authors develop a two-term latency model characterizing the recomputation and cache-hit paths and evaluate it across three Qwen2.5 model sizes, multiple prefix lengths, and batch sizes. The paper reports that prefix caching consistently outperforms recomputation in the measured configurations, with speedups reaching 169× for long prefixes. It also studies the overhead of materializing paged KV caches through scattered gathers and evaluates the impact of memory capacity on cache-hit rates using synthetic Zipf-distributed prefix popularity. Finally, the authors perform end-to-end validation using vLLM with automatic prefix caching enabled and disabled.

Critical strengths
  1. Quantitative characterization of prefix-cache performance.

The paper provides a systematic empirical characterization of the relative costs of recomputation and prefix-cache reuse across different model sizes, batch sizes, and prefix lengths. This helps quantify the performance benefits of caching and identify the fixed overheads that become important for shorter prefixes. The paper also shows an end-to-end vLLM evaluation which validates the measurements.

Critical weaknesses
  1. Limited novelty in the findings and lack of hardware diversity.

First, Prefix-cache reuse is significantly more beneficial than recomputation on a bandwidth-rich, FLOPs-poor GPU, seems largely expected from the underlying hardware characteristics. It is unclear why the authors present this result as surprising or what new insight it provides beyond the expected compute-versus-memory tradeoff.

Second, Although this is primarily a hardware-dependent measurement study, the experiments are conducted exclusively on the NVIDIA H20. Evaluating a more diverse set of GPUs with different compute-to-bandwidth ratios (e.g., A100, H100, and H20) would help validate the proposed performance model and establish how the observed behavior varies across hardware architectures.

  1. Insufficient validation of the crossover model.

The authors emphasize the crossover prefix length below which recomputation becomes cheaper than cache reuse. However, the kernel-level experiments used to fit the model consider prefix lengths of 512 tokens or greater, while many of the predicted crossover points fall below this range. For example, the fitted crossover for Qwen2.5-7B at batch size 1 is approximately 152 tokens, but the end-to-end vLLM evaluation still demonstrates a 1.7× speedup from caching at a prefix length of 128 tokens. Although the two experiments use different measurement setups and therefore are not directly comparable, no reported experiment actually demonstrates a regime where recomputation outperforms caching.

Additionally, the cache-capacity analysis relies entirely on synthetic Zipf-distributed requests over a fixed pool of distinct, equal-length prefixes. This setup does not capture partial-prefix matching, where requests can reuse subsets of previously cached prefixes, as supported by real serving systems such as vLLM. Moreover, the authors do not establish whether real-world prefix popularity follows the assumed Zipf distributions or what degrees of skew are representative of production workloads. Evaluations using real-world traces, or at least more representative overlapping-prefix workloads, would significantly strengthen these conclusions.

Questions for authors

Hardware generalizability and novelty: What motivated the hypothesis that prefix-cache reuse might become less beneficial on a bandwidth-rich, FLOPs-poor accelerator, given that the hardware's compute-to-bandwidth ratio appears to favor cache reuse? Additionally, could the authors explain why the measurement study is limited to the H20 and how the proposed model is expected to generalize to GPUs with different compute-to-bandwidth ratios?

Crossover validation: The predicted crossover lengths are generally below the minimum prefix length used in the kernel-level measurements. Could the authors provide measurements at shorter prefix lengths, particularly around the predicted crossover points, to validate the fitted model? How should the predicted 152-token crossover for Qwen2.5-7B at batch size 1 be interpreted alongside the 1.7× caching speedup observed at 128 tokens in the end-to-end evaluation?

Workload realism: How representative are the chosen Zipf popularity distributions of real-world prefix-cache workloads? How would the capacity-versus-hit-rate results change when accounting for partial-prefix matching and overlapping prefixes of different lengths?

Reviewer_1KeaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates prefix-cache trade-offs on NVIDIA H20-141GB with Qwen2.5 (0.5B–7B). It uses timing measurements for full recomputation vs resident prefixes, copy/gather microbenchmarks, Zipf/LRU simulation, and vLLM 0.8.3 tests. Affine latency models predict the break-even point between recomputation and reuse. It observes up to 169.1x reuse speedup for 7B/32K prefixes, and 8.8x / 5.4x /1.7x gains in vLLM for 2048/1024/128 prefixes. Paged gather achieves only 1/8–1/15 the bandwidth of contiguous copy. Simulation shows cache gains diminish under skewed popularity. The main contribution is empirical characterization of prefill workloads; its A100 discussion is about cache budget analysis, not real GPU measurements.

Critical strengths
  1. Engine-level controls support the main empirical finding, and validated settings together with real token counts strengthen this result; the large-prefix speedup remains valuable despite flaws in the cost model.
  2. This work disentangles different caching components. Within some limits, the measurements and the failed pooled fit in Appendix A offer useful insights for future work.
Critical weaknesses
  1. Most crossover values in Table 2 lie below the 512-token lower bound of fitting data, which is out-of-range extrapolation. The 0.5B case also has inconsistent predictions: the fitted threshold contradicts measured latency ordering near the boundary.
  2. The 7B sensitivity test in Appendix A cannot fix the 0.5B mismatch, nor supply error bounds across the full crossover map.
  3. The authors assume all paged layouts require this gather step, but the benchmark only tests standalone index_select materialization, while vLLM avoids this operation via shared physical blocks.
  4. The paper does not clarify whether the latency measurement includes the tested gather, nor how the fitted latency parameters connect to this microbenchmark. Profiling or tighter claim scoping is required.
Questions for authors
  1. Could you repeat measurements near the crossover point to resolve the inconsistency for the 0.5B/B=1 case at L=512?
  2. What exact operations are counted in the DynamicCache hit timer?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.