acceptodds
Under review as a conference paper at ICLR 2027

StrideKV: Accelerating Batched Long-Context Decoding via Periodic Reuse of Retrieved KV Cache

Abstract

Query-aware KV cache retrieval enables long-context inference by keeping the full KV cache in CPU memory and maintaining only a small GPU-resident working set of entries relevant to each query, but repeatedly selecting and loading these entries can dominate decoding time. We study how often this retrieval needs to occur in synchronous batched decoding. A natural approach is adaptive: reuse the previous working set and perform a correction, an immediate retrieval for the current query, only when the query changes substantially. However, when requests in a batch execute in lockstep, different requests need corrections at different layers and steps, so the batch as a whole must perform corrections far more often than any single request; as the batch grows, the throughput gain of such adaptive schemes vanishes and eventually turns negative. We also observe that queries at adjacent steps select largely overlapping tokens, and that retrieving only every other step yields the same top-1 token as per-step retrieval at 99.4% of decoding steps. Motivated by these findings, we introduce StrideKV, which retrieves relevant KV entries only once every few decoding steps, with all requests in the batch following the same schedule. When retrieval happens, the entries are still selected based on the current query; in the steps between retrievals, the model simply reuses the entries already on the GPU, avoiding both selection and CPU-to-GPU transfer. Across multiple models and context lengths, StrideKV improves decoding throughput on an A100 GPU by up to 66% over ShadowKV, a strong KV offloading method that retrieves at every step, while keeping long-context accuracy close to that of ShadowKV. These results show that StrideKV is a simple and effective way to accelerate batched long-context decoding with KV cache offloading.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Long-Context Inference, KV Cache Management, Sparse Attention, Batched Decoding

Reviews

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

The paper presents StrideKV, a simple method for cache retrieval in long-context inference. It's essentially a modification of ShadowKV in which the offloaded KV cache entries are retrieved every 's' steps instead of every step (plus adding FreeKV's speculative retrieval to the ShadowKV backend). The paper demonstrates that a significant portion of time is spent loading the KV cache (Fig 2a). The method achieves ~50% speedup over ShadowKV (Figure 4) While retaining accuracy (Table 3).

Critical strengths
  • The paper is well-written and easy to understand.
  • The paper includes clear diagrams and tables that demonstrate the method (Figure 3).
  • The problem is well-motivated (Figure 2), though I have a few notes on Fig 2 below.
  • The method outperforms FreeKV in terms of accuracy, (though there is no speed comparison), and nearly maintains ShadowKV's accuracy while providing a significant speedup (~50%).
Critical weaknesses
  • There's no speed comparison with FreeKV. The accuracy is better (Table 3), but the speed (Fig 4) is not compared.
  • The best way to demonstrate the speed-vs-accuracy tradeoff induced by your model is with a single plot (with the x-axis as speed, and the y-axis as accuracy). This would help make the comparison clearer.
  • In Figure 2, I'm wondering why 2a shows such a small context size. It seems your method is intended for much larger context sizes.
  • Is it possible to measure the speed during the actual evaluation? This would be the best runtime measurement for a real load.
  • The algorithmic novelty is a bit limited in my opinion. It seems that the core contribution is not loading the KV cache every iteration.
Questions for authors
  • Is it possible to measure the speed during the actual evaluation? This would be the best runtime measurement for a real load.
3 comments

We sincerely appreciate the reviewer’s time and feedback.Below, we address each question individually:

Q1: Can throughput be measured during the actual evaluation?

A: We thank the reviewer for suggesting this measurement. We measured decoding throughput on 128K RULER QA2 using the same greedy decoding and stopping rules as in the accuracy evaluation. Each prompt contained 131,040 tokens, and generation stopped at EOS or after 32 output tokens. All three methods ran on the same 80 GB A100 using Gradient Llama-3-8B-Instruct-1048k in BF16. ShadowKV and StrideKV used the same retrieval settings, with a budget of 2,048 tokens, a rank of 160, and a chunk size of 8 tokens.

We measured one batch per method. ShadowKV and StrideKV processed the same 24 questions. Due to GPU memory constraints, we ran full attention at B=3 using the first three of those questions. Timing began when the first output token was ready and ended after the final GPU synchronization. We calculated decoding throughput by dividing the number of valid tokens generated during that interval by the elapsed batch decoding time.

MethodDecode batch sizeQuestions per prefill groupValid tokens during timingDecode time (s)Decode throughput (tok/s)
Full attention31751.474450.87
ShadowKV_CPU (corrected)2423925.423272.28
StrideKV (s=2)2423972.9373135.16

At the matched batch size of B=24, StrideKV achieved 87.0% higher decoding throughput than ShadowKV on this QA2 workload.

Q2: Decoding throughput comparison with FreeKV.

A: We thank the reviewer for pointing out this missing comparison. We measured the decoding throughput of StrideKV (s=2) and the complete FreeKV system on the same 80 GB A100. Both used Llama-3-8B-Instruct-Gradient-1048k, the same 48 distinct requests with 61,440 input tokens each, and a 1,024-token dynamic KV retrieval budget. We recorded one timed run per method after warm-up.

MethodDecoding throughput (tokens/s)
FreeKV133.46
StrideKV (s=2)576.36

Under these matched conditions, StrideKV achieved 4.32× the decoding throughput of FreeKV.

Q3: Accuracy–throughput tradeoff.

A: We thank the reviewer for suggesting a single plot. We have added Figure 8 to Appendix C (“Accuracy–Throughput Tradeoff,” page 19). The plot shows mean decoding throughput on the x-axis and mean 128K RULER accuracy on the y-axis, with one point each for ShadowKV, StrideKV (s=2), and StrideKV (s=3).

Both axes use the two models shared by Table 4 and Figure 5. We weight the six model–context configurations equally for throughput and the two models equally for accuracy. Compared with ShadowKV, StrideKV (s=2) improves mean decoding throughput by 54.0% with a 0.255 percentage-point decrease in mean accuracy. Increasing the stride to 3 raises mean throughput by a further 24.0% and decreases mean accuracy by another 0.750 percentage points.

Q4: Methodological novelty.

A: We appreciate the reviewer’s comment. Cross-step KV reuse is an established technique. Our analysis shows why it can yield limited throughput gains at high concurrency. In a synchronous batch, even when most requests can reuse their cached KV, one request that needs a refresh can make the entire batch wait.

StrideKV makes reuse a batch-wide decision by scheduling refreshes on the same steps for all requests. With s=2, every request attends to its own cached historical KV on alternating steps, removing both selection and loading from the batch’s critical path on those steps.

In the paired experiment with 32 distinct requests, this schedule increased decoding throughput by 49.25% over ShadowKV. In a separate 128K RULER evaluation on Llama-3-8B-1M, the two methods achieved comparable mean accuracy (86.05% for StrideKV and 85.76% for ShadowKV).

Q5. Why does Figure 2(a) use a short context when StrideKV is designed for much longer contexts?

We thank the reviewer for the suggestion. We repeated the Figure 2(a) experiment at 60K (61,440 input tokens). KV selection, loading, and maintenance accounted for 68.3%, 76.1%, and 77.1% of the decoding critical path at batch sizes 8, 16, and 32, respectively. These results confirm the original finding that these operations dominate ShadowKV’s decoding time at the longer context.

Reviewer_3ef1OpenReview ↗

Response to Reviewer

Thank you for the experiments. The additional speed comparisons have alleviated many of my concerns. The main remaining concern is on novelty and the magnitude of the algorithmic contribution.

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

This paper proposes StrideKV, a shared periodic retrieval schedule for synchronous batched long-context decoding with CPU-offloaded KV caches. All requests in a batch retrieve historical KV entries at fixed intervals and reuse the GPU-resident working set between retrievals, skipping historical token selection and loading on reuse steps. The authors implement the schedule using ShadowKV as the backend. The design is motivated by the temporal overlap between selected KV entries and the observation that request-specific corrections can become frequent at the batch level when distinct requests execute synchronously. On a single A100 GPU, the default stride of two improves decoding throughput by 34.4%-66.0% over ShadowKV across two models and context lengths of 60K-244K. Across three models and ten RULER tasks at 128K context, the mean accuracy decreases by 0.65 percentage points relative to ShadowKV.

Critical strengths
  1. The paper addresses a practical performance bottleneck. The profiling identifies historical KV retrieval and maintenance as substantial contributors to decoding time, providing a clear motivation for reducing retrieval frequency.

  2. The analysis of batch composition provides useful insight. By distinguishing replicated inputs from distinct requests, the paper illustrates how differences in correction timing across requests can increase the frequency of batch-level corrections in synchronous decoding. This is a useful consideration when evaluating batched inference systems.

  3. The method is simple and well motivated. A shared periodic schedule creates steps at which every request skips historical retrieval. The design translates the observed temporal overlap in selected KV entries into an opportunity to reduce selection and transfer costs within the ShadowKV backend.

  4. The reported accuracy-throughput tradeoff is promising. StrideKV improves throughput over ShadowKV at matched batch sizes in all evaluated throughput configurations while maintaining similar average RULER accuracy. The stride ablation also demonstrates how longer reuse intervals exchange some accuracy for additional throughput.

Critical weaknesses
  1. The methodological novelty appears limited. The analysis of correction timing in synchronous batches is useful, but the proposed solution is a fixed periodic retrieval schedule shared across requests. Reusing previously retrieved KV entries across decoding steps is already central to existing approaches, including FreeKV-inspired reuse mechanisms. The main distinction appears to be when the working set is refreshed, rather than a fundamentally new reuse mechanism. The paper would benefit from a clearer explanation of the substantive advance over prior temporal reuse strategies, beyond applying a shared fixed schedule to the CPU-offloading setting. This is my primary concern.

  2. The evaluation has limited task coverage and lacks a throughput comparison with the complete FreeKV system. Accuracy is evaluated only on RULER, leaving it unclear whether periodic reuse preserves quality on tasks with different generation patterns, such as mathematical reasoning. The retrieval-schedule throughput comparisons use ShadowKV and the authors' ShadowKV-Adaptive implementation. Appendix A.1 describes KV-head-level correction and speculative updates on a separate stream, but this implementation retains ShadowKV's representation and associated key reconstruction and is not the complete FreeKV system. Using a common backend helps isolate scheduling differences, but these results do not establish a throughput advantage over the complete FreeKV system. A direct comparison would strengthen the evaluation.

  3. The management of KV states generated during decoding is insufficiently specified. Section 4.1 and Figure 7 state that newly generated KV entries are appended to a GPU-resident recent set, which is attended to alongside the retrieved historical working set. However, the paper does not clearly specify whether this set has a capacity limit or whether older generated entries eventually move into the historical retrieval pool. If all generated KV entries remain on the GPU, memory consumption and attention cost increase with output length, independently of the fixed historical retrieval budget. Clarifying the retention and update rules, along with how memory usage scales with generation length, would make the resource requirements easier to assess.

  4. The prediction-fidelity analysis does not establish robustness during long free-running generation. The reported 99.41% top-1 agreement is measured under a shared reference-generated token prefix. Although hidden and KV states evolve independently and can accumulate discrepancies along that prefix, the protocol does not capture the feedback from divergent generated tokens into subsequent predictions. The free-running RULER evaluation provides complementary evidence, but aggregate scores may obscure degradation on individual tasks or longer outputs. Reporting sequence-level agreement, output length distributions, task-level variability, and quality over longer generation horizons would provide a more complete assessment.

Questions for authors
  1. Broader task evaluation. Could the authors add evaluations on LongBench v2, AIME, and MATH-500, comparing StrideKV with full attention, ShadowKV, and FreeKV? These results would help establish whether periodic reuse preserves quality beyond RULER, particularly on long-context understanding and mathematical reasoning tasks. Please specify the models, generation length limits, and decoding settings.

  2. End-to-end comparison with the complete FreeKV system. Could the authors compare StrideKV directly with the complete FreeKV system, rather than relying only on ShadowKV-Adaptive as the adaptive baseline? Please use the same hardware, models, workloads, and KV budgets, with batches of distinct requests, and report end-to-end latency and throughput alongside decoding throughput. The end-to-end measurements should include prefill and the full generation process, with the timing boundaries stated explicitly.

  3. FreeKV runtime breakdown and computation-communication overlap. The runtime breakdown in Figure 2 provides a clear account of ShadowKV's bottlenecks. Could the authors provide a comparable analysis of the complete FreeKV system, particularly quantifying the time spent on KV-head-level corrections and their contribution to the decoding critical path? It would also be helpful to report how much of the streamed recall is overlapped with GPU computation and how much remains exposed, to better explain the performance impact of adaptive correction across batch sizes.

  4. Diminishing adaptive gains with replicated requests. Table 5 reports a nearly constant batch-level correction frequency of 13.98% for replicated requests across batch sizes. Nevertheless, Table 6 shows that ShadowKV-Adaptive's throughput gain over ShadowKV falls from 17.54% at B=8 to 0.98% at B=32 in this setting. Could the authors explain why the benefit diminishes even when correction timing is aligned across requests and correction frequency does not increase? Clarifying the additional sources of overhead would help distinguish their effects from those of misaligned corrections in distinct-request batches.

  5. Free-running generation and the onset of divergence. Could the authors evaluate StrideKV under free-running generation, allowing it to condition on its own generated tokens rather than forcing the shared reference-generated prefix, to assess the impact of error accumulation? For the reported 99.41% shared-prefix top-1 agreement, please also indicate whether disagreements occur early or late in decoding, since early divergence could affect subsequent generation from the outset.

3 comments

We sincerely appreciate the reviewer’s time and feedback.Below, we address each question individually:

Q1: Broader task evaluation.

A: We thank the reviewer for suggesting these benchmarks. We evaluated full attention, ShadowKV, FreeKV, and StrideKV (s=2) on LongBench v2 using Llama-3-8B-Instruct-Gradient-1048k. We included all 297 of the 503 examples whose complete prompts fit our evaluation limits without truncation. Each example was decoded once with greedy decoding at B=1 and a cap of 128 generated tokens.

MethodLongBench v2 accuracy
Full attention27.95% (83/297)
ShadowKV27.61% (82/297)
FreeKV27.95% (83/297)
StrideKV (s=2)27.27% (81/297)

We also evaluated AIME 2024 and MATH-500 with the same model and decoding settings and a cap of 4,096 generated tokens. The short prompts in both benchmarks caused ShadowKV and StrideKV to use dense attention. We therefore focus the comparison on LongBench v2, where periodic KV reuse is exercised.

StrideKV used sparse historical KV retrieval on all 297 LongBench v2 examples and maintained accuracy comparable to the three baselines, answering 81 questions correctly versus 82–83 for the baselines.

Q2: End-to-end comparison with the complete FreeKV system.

A: We thank the reviewer for requesting this comparison. We ran StrideKV (s=2) and the complete FreeKV system serially on the same 80 GB A100. Both used Llama-3-8B-Instruct-Gradient-1048k, the same batch of 48 distinct requests with 61,440 input tokens each, and a 1,024-token dynamic KV retrieval budget. We used greedy decoding with a cap of 128 generated tokens per request and recorded one timed run per system after a full warm-up.

End-to-end timing started before the input tokens were transferred to the GPU and ended once the last valid output token was available on the host and all asynchronous work had completed. This interval includes prefill, KV cache construction, and full generation. Model loading, pinned host-memory allocation, and warm-up took place before timing. Decode-only timing started when the first output token was ready and counted the subsequent tokens through the same endpoint.

MethodPrefill (s)End-to-end batch latency (s)End-to-end throughput (tok/s)Request throughput (req/s)Decoding throughput (tok/s)
StrideKV (s=2)971.42981.996.260.0489576.36
FreeKV474.30519.9711.820.0923133.46

StrideKV achieved 4.32× the decoding throughput of FreeKV. The end-to-end latency gap was driven by prefill, which in StrideKV includes constructing the ShadowKV cache through low-rank factorization of the historical keys and offloading the historical values to CPU memory.

Q3: FreeKV correction overhead and recall overlap.

A: We thank the reviewer for suggesting this analysis. We evaluated the complete FreeKV system on a single 80 GB A100 using Gradient Llama-3 8B, 61,440 input tokens per request, and a 2,048-token dynamic KV retrieval budget. Each batch contained distinct requests. We measured 50 decoding steps after eight warm-up steps. We report the median per-step decoding latency from three independent runs and use separate CUDA traces to measure individual phases.

FreeKV preloads KV entries that the next step is likely to need, a process we refer to as speculative recall. When the current step needs an update, FreeKV reselects the KV entries and loads them through corrective recall.

Batch sizeDecoding latency (ms/step)KV reselection during correction (ms/step)Share of speculative recall overlapping with model computation
122.111.6271.50%
866.517.4740.29%
16181.2443.7813.35%
32419.28107.713.60%

As batch size increased from 1 to 32, the share of speculative recall that overlapped with model computation fell from 71.50% to 3.60%. At B=32, 96.40% of speculative recall time fell outside the model computation intervals.

Only about 3–4% of eligible KV-head positions triggered a correction. At each layer and decoding step, correction runs whenever any KV head in the batch needs it. As batch size increased from 1 to 32, the share of layer–step pairs with at least one correction rose from 15.87% to 88.97%. Larger batches therefore triggered KV reselection and loading more frequently, while a smaller share of speculative recall could run alongside model computation.

Q4: Diminishing adaptive gains with replicated requests.

A: We thank the reviewer for highlighting this result in Table 6. We repeated the experiment three times on the same 80 GB A100, using the original 32 requests and the same reference token sequences. For replicated requests, the batch-level correction rate stayed at approximately 13.98%. ShadowKV-Adaptive’s throughput gain over ShadowKV fell from 22.24% at B=8 to 2.69% at B=32.

FreeKV overlaps bandwidth-intensive KV recall over the CPU–GPU link with model computation, including attention and FFN, to reduce waiting. ShadowKV-Adaptive follows this approach by preparing KV for the next decoding step after the current layer’s attention finishes, while the model continues with output projection and FFN. ShadowKV reconstructs keys from low-rank factors on the GPU. As the batch grows, key reconstruction requires more GPU compute and memory bandwidth, increasing contention with the model operations running alongside it.

We measured the same four decoding steps for the same two replicated requests at each batch size. ShadowKV executes K reconstruction and post-attention computation in sequence. In ShadowKV-Adaptive, the post-attention interval falls almost entirely within the speculative KV refresh interval. The table reports times in ms per decoding step.

Batch sizeShadowKV K reconstructionShadowKV post-attentionShadowKV sumAdaptive speculative KV refreshTime differenceRelative reduction
817.678.8026.4723.203.2712.4%
1635.199.2344.4241.572.856.4%
3265.7410.1975.9373.292.643.5%

The relative time savings from overlapping these operations shrink as the batch grows. Adaptive’s speculative refresh interval is 12.4% shorter than the sum of the two ShadowKV intervals at B=8 and 6.4% shorter at B=16. By B=32, the two timings are nearly equal, with a difference of only 2.64 ms per step, or 3.5%. This small time saving helps explain why the overall throughput gain diminishes at larger batch sizes even when all replicas correct at the same time.

Q5: Free-running generation and the onset of divergence.

A: We thank the reviewer for raising these questions. We compared ShadowKV (s=1) and StrideKV (s=2) on the same 32 explanatory RULER QA2 requests used in Table 2. We used Gradient Llama-3 8B, 15,360-token inputs, a 2,048-token KV retrieval budget, and greedy decoding at B=4. We measured up to 58 decoding steps after the first token produced during prefill.

When does divergence first occur? We reran the shared-prefix experiment to locate the disagreements. The rerun yielded 99.35% top-1 agreement (1,844/1,856 predictions). Among the 11 requests that diverged, the first disagreement occurred as early as step 7 and as late as step 52, with a median of 33. Four of the 32 requests first diverged within the first quarter of the evaluated steps.

What happens under free-running generation? We let each method feed its own generated tokens back into the model. The complete token sequences matched exactly on 21/32 requests (65.62%). The same 11 requests diverged, and each first diverged at the same step as in the shared-prefix rerun. Once the methods generated different tokens, they could follow different continuations. By steps 41–58, position-wise token agreement fell to 75.69% under free-running generation and remained above 99% under the shared prefix.

Decode stepsShared-prefix token agreementFree-running token agreementFree-running requests with a divergence by window end (cumulative)
1–1099.06%97.50%3/32
11–2099.69%88.75%4/32
21–4099.53%85.31%7/32
41–5899.13%75.69%11/32

Task quality. Under the original QA2 scoring rule, ShadowKV answered 21/32 requests correctly and StrideKV answered 22/32 correctly. The methods received the same score on 31/32 requests, even though 11 output sequences differed.

The 128K RULER results in Table 3 show that StrideKV’s effect on accuracy varies by model and task. Across the three models, the change in mean accuracy over ten tasks relative to ShadowKV ranged from −1.44 to +0.29 percentage points, with larger differences on individual tasks. For example, fwe accuracy rose from 70.83% to 75.00% on Llama-3-8B-1M, while niah_multikey_2 accuracy fell from 73.96% to 66.67% on Llama-3.1-8B.

Q6: Methodological novelty.

A: We thank the reviewer for asking us to clarify the contribution. We agree that reusing previously retrieved KV across decoding steps is an established idea. Our contribution is to identify how request-level refresh decisions affect throughput in large synchronous batches and to show that a simple shared schedule can address this bottleneck while preserving accuracy.

In a batch of distinct requests, one request’s query-triggered correction can delay attention for the entire batch. StrideKV gives the entire batch a common schedule. With s=2, all requests reuse their own GPU-resident historical KV on alternating steps, so the whole batch skips both selection and loading on those steps. At B=32 with distinct requests, StrideKV improved decoding throughput over ShadowKV by 49.25% in the paired experiment. On the separate 128K RULER evaluation with Llama-3-8B-1M, it maintained comparable mean accuracy (86.05% vs. 85.76%).

Q7: Retention of KV generated during decoding.

A: We thank the reviewer for pointing out that the retention rule needs clarification. StrideKV targets workloads with long inputs and short outputs. For each request, we reserve GPU space according to the configured maximum number of generated tokens. Each decoding step appends its new K and V entries to this GPU-resident set, and attention uses all generated entries accumulated so far alongside the historical working set. Generated entries stay on the GPU throughout the request. The historical retrieval pool is built from the input prompt and stays fixed during generation.

The occupied space for generated KV grows linearly with output length, and each generated entry adds one attended position per request. The short output cap keeps both costs bounded. For example, in our 60K experiment at B=48 with BF16 Gradient Llama-3 8B, reserving 128 generated positions per request takes 0.75 GiB across the batch. Those 128 positions add at most 10% to the 1,280 prompt-derived positions attended per request. This bounded cost allows us to retain all generated KV on the GPU in the target workload.

Reviewer_yzuLOpenReview ↗
Rating
2(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes StrideKV, a periodic KV cache retrieval strategy for accelerating batched long-context LLM decoding. Building on ShadowKV, the method reduces the frequency of historical KV selection and CPU-to-GPU transfers by reusing previously retrieved KV entries over a fixed number of decoding steps. All requests within a batch follow the same retrieval schedule, avoiding the synchronization overhead associated with request-specific adaptive retrieval.

The authors motivate the approach through profiling studies showing that KV retrieval and loading account for a substantial fraction of decoding time, while consecutive decoding steps often select overlapping KV entries. Experiments on RULER and A100 GPUs demonstrate improved decoding throughput over ShadowKV with relatively small average accuracy degradation.

Overall, the paper investigates a practically relevant optimization problem, but the proposed solution is relatively straightforward, and its technical novelty and generality are insufficiently established.

Critical strengths

S1. Relevant problem motivation.

The paper identifies a practical inefficiency in retrieval-based KV cache management: repeated historical KV selection and loading can dominate decoding time, particularly for large batches. The analysis of batch-level synchronization overhead provides a useful motivation for reconsidering retrieval frequency.

S2. Measurable throughput improvements.

The authors implement StrideKV on top of ShadowKV and report 34.4–66.0% throughput improvements under the evaluated long-context configurations. The results also suggest that short-term reuse of historical KV entries can preserve accuracy reasonably well on the evaluated RULER tasks.

Critical weaknesses

W1. Limited Algorithmic Novelty and Insufficient Differentiation from Existing Methods

The central contribution of StrideKV is to replace per-token historical KV retrieval with a fixed periodic retrieval schedule. Specifically, the method retrieves KV entries every ss decoding steps and reuses the previously selected GPU-resident working set during intermediate steps. While this design is simple and practically motivated, the algorithmic contribution appears rather limited.

The general idea of exploiting temporal stability in KV selection and reusing selected entries across decoding steps has already been explored in prior work, including LServe, TokenSelect, and RefreshKV. Although StrideKV applies periodic reuse to a CPU-offloading setting and emphasizes batch-level synchronization, the proposed method largely amounts to a scheduling modification of the existing ShadowKV framework rather than a fundamentally new retrieval or attention mechanism.

The paper does not sufficiently demonstrate why the proposed fixed-stride strategy constitutes a substantial technical advancement over existing reuse-based approaches. More direct comparisons with these methods, or adaptations of their scheduling strategies to the same KV-offloading backend, would help establish the novelty of StrideKV.

W2. Insufficient Technical Depth and Justification of the Fixed Retrieval Schedule

The technical mechanism underlying StrideKV is relatively straightforward. Its core operation is to perform retrieval when t mod s=0t \bmod s = 0 and otherwise reuse the previous KV working set. The method does not introduce a new KV representation, retrieval algorithm, or attention computation mechanism.

Although the authors identify synchronization problems in adaptive retrieval under synchronous batched decoding, the proposed solution is simply to enforce a shared retrieval schedule across all requests. The paper does not provide a sufficiently detailed investigation of alternative scheduling strategies or demonstrate that this simple periodic policy is particularly well suited to heterogeneous workloads.

In particular, a fixed retrieval interval does not account for changes in query relevance. It may perform unnecessary retrievals when the selected KV set remains stable, while delaying retrieval when the query changes substantially. The paper does not sufficiently analyze these limitations or compare against stronger batch-aware adaptive scheduling strategies that could potentially reduce synchronization overhead without relying on a fixed interval.

Consequently, the technical contribution appears closer to an empirical scheduling heuristic than a sufficiently developed algorithmic framework.

W3. Limited Experimental Generalization and Incomplete Baseline Comparisons

The experimental evaluation is relatively narrow and does not sufficiently establish the generality of the proposed approach.

First, the model coverage is limited. The accuracy experiments primarily use Llama and GLM models, while the throughput experiments are restricted to Llama-3-8B-1M and GLM-4-9B-1M. The absence of evaluations on other widely used model families, particularly Qwen, makes it difficult to determine whether the reported benefits generalize across different architectures and attention configurations. The evaluation also does not establish scalability to substantially larger models.

Second, the throughput comparisons primarily focus on ShadowKV and a ShadowKV-Adaptive variant constructed by the authors. Although FreeKV is included in the accuracy evaluation, the proposed adaptive baseline is not the complete FreeKV system. Therefore, the results do not convincingly establish the advantage of StrideKV over more comprehensively optimized adaptive retrieval implementations.

Third, the performance evaluation is conducted on a single A100 GPU and mainly reports aggregate decoding throughput. The paper provides limited evidence concerning heterogeneous serving workloads, asynchronous scheduling, per-request latency, and the behavior of the proposed strategy under different hardware and memory-transfer configurations.

Finally, the accuracy evaluation is concentrated on RULER. While average accuracy degradation is relatively small for s=2s=2, several individual tasks exhibit more noticeable differences. The paper does not systematically investigate scenarios involving abrupt changes in retrieval requirements or longer generation trajectories, where reusing outdated KV selections could have a greater impact.

Overall, more comprehensive comparisons across model families, workloads, retrieval policies, and serving configurations are needed to support the general applicability of StrideKV.

W4. Presentation and Experimental Visualization Could Be Improved

Although the overall organization is understandable, the presentation of several experimental results could be clearer.

Some figures contain dense annotations and relatively small labels, making detailed comparisons unnecessarily difficult. In particular, Figures 1, 4, and 5 would benefit from clearer visual organization and more readable labeling.

Furthermore, Figure 4 reports speedups over full attention using different feasible batch sizes, while comparisons against ShadowKV use matched batch sizes. Although the paper explains this distinction, the presentation could more clearly separate throughput improvements resulting from larger feasible batches and KV offloading from those specifically attributable to periodic retrieval reuse.

A more systematic visualization of the accuracy–throughput tradeoff, alongside a clearer decomposition of retrieval and computation costs, would make the empirical contributions easier to assess.

Questions for authors

How does StrideKV fundamentally differ from existing approaches such as LServe and TokenSelect that already exploit temporal stability in KV selection? Could the authors provide a controlled comparison with comparable reuse strategies implemented on the same ShadowKV backend?

Why is a fixed retrieval interval preferable to a batch-aware adaptive scheduling policy? Could the authors compare StrideKV against an adaptive baseline that explicitly accounts for batch-level synchronization costs, rather than relying only on the current ShadowKV-Adaptive implementation?

2 comments

We sincerely appreciate the reviewer’s time and feedback.Below, we address each question individually:

Q1: Comparison with LServe and TokenSelect.

A: We thank the reviewer for raising this question and suggesting a controlled comparison. TokenSelect and RefreshKV use query similarity to decide when to retrieve historical KV. In a batch of distinct requests, some requests can reuse their KV while others need to retrieve it. The requests ready to proceed must wait for the outstanding retrievals before the batch can advance. As the batch grows, more steps incur this wait.

LServe has a related dependency within each layer. Its streaming heads use fixed sink and local pages, while its retrieval heads select historical pages on refresh steps. The fused attention kernel needs those page selections before it can run, and the layer needs outputs from both head groups before it can advance. The extra work on the retrieval heads can therefore limit layer throughput.

We implemented three scheduling variants on the same corrected ShadowKV backend, keeping the selector, KV budget, and kernels fixed. The LServe variant uses its periodic page-selection rule with ShadowKV’s attention kernels. The results below are for Llama-3-8B-1M.

128K RULER accuracy (%)

TaskLServeTokenSelectRefreshKVShadowKVStrideKV (s=2)
Average84.1984.9783.9185.7686.05
niah_single_1100100100100100
niah_single_2100100100100100
niah_multikey_1100100100100100
niah_multikey_291.6795.8387.597.9296.88
niah_multiquery92.9797.6685.9498.797.66
niah_multivalue91.6793.7593.4993.2392.19
qa_169.7969.7971.8869.7970.83
qa_25048.9652.0851.0452.08
vt78.7575.6379.1776.0475.83
fwe67.0168.0669.170.8375

60K decoding throughput at B=48 (tok/s)

LServeTokenSelectRefreshKVShadowKVStrideKV (s=2)
67.8823.98139.5378.33627.88

The three variants are within 1.06 percentage points in mean accuracy, yet their decoding throughput varies by up to 5.82× at B=48. StrideKV uses a shared schedule that lets the entire batch skip KV selection and CPU-to-GPU loading every other step. StrideKV (s=2) achieves higher mean accuracy on 128K RULER (86.05%) and higher decoding throughput at B=48 (627.88 tok/s) than all three reuse variants in the reported experiments.

Q2: Fixed vs. batch-aware adaptive retrieval.

A: We thank the reviewer for suggesting this comparison. To our knowledge, no published adaptive retrieval policy for CPU-offloaded decoding explicitly uses the synchronization cost across requests in a batch to decide when to refresh historical KV. This cost motivates StrideKV’s fixed, batch-wide schedule. With s=2, all requests reuse the KV already on the GPU every other step, so the entire batch skips both selection and CPU-to-GPU loading on those steps.

We measured FreeKV’s decoding throughput and compared it with the manuscript’s StrideKV (s=2) result for the same model at 60K context and B=48. In the FreeKV run, at least one KV head in the batch triggered a correction in 93.0% of eligible layer-steps. For accuracy, we report both methods’ mean scores across the ten 128K RULER tasks in the manuscript.

MethodMean 128K RULER accuracy (%)60K decoding throughput at B=48 (tok/s)
FreeKV78.37102.98
StrideKV (s=2)86.05627.88

On Llama-3-8B-1M, StrideKV achieves 7.68 percentage points higher mean accuracy and 6.10× the reported decoding throughput of FreeKV. These results show that StrideKV outperforms FreeKV in long-context accuracy and delivers higher throughput in high-concurrency batched decoding.

Q3: Experimental coverage and baseline comparisons.

A: We thank the reviewer for pointing out these gaps. We added a Qwen2 accuracy evaluation, three additional task benchmarks, and a decoding throughput measurement for FreeKV.

128K RULER on Qwen2-7B-Instruct

We evaluated ten RULER tasks with 96 examples per task and greedy decoding at B=1. The two CPU-offloaded methods use the same 2,048-token retrieval budget. StrideKV (s=2) scores 62.59%, within 0.43 percentage points of ShadowKV_CPU on average and within 2.1 points on every task.

TaskFull attentionShadowKV_CPUStrideKV (s=2)
Average67.4763.0262.59
niah_single_1100100100
niah_single_297.9296.8896.88
niah_multikey_189.5886.4684.38
niah_multikey_240.6328.1328.13
niah_multiquery72.6669.7971.88
niah_multivalue63.859.1159.38
qa_158.3352.0851.04
qa_236.4633.3333.33
vt35.8339.7937.71
fwe79.5164.5863.19

Qwen2’s pretraining context reached 32K tokens, and we used 4× YaRN to extend it to 128K. Even with this extension, full attention scores 67.47% on average and only 40.63% on niah_multikey_2. The low full-attention scores suggest that extrapolating to 128K is challenging for this checkpoint and likely contributes to the modest scores of both ShadowKV and StrideKV.

LongBench v2 accuracy

We evaluated Llama-3-8B-Instruct-Gradient-1048k on the 297 of 503 LongBench v2 examples whose complete prompts fit our evaluation limits. We used one greedy generation per example at B=1, with a cap of 128 output tokens.

MethodAccuracy
Full attention27.95% (83/297)
ShadowKV27.61% (82/297)
FreeKV27.95% (83/297)
StrideKV (s=2)27.27% (81/297)

We focus this comparison on LongBench v2 because the short prompts in AIME 2024 and MATH-500 trigger dense fallback in both ShadowKV and StrideKV. On LongBench v2, StrideKV used sparse historical KV retrieval on all 297 examples and maintained accuracy comparable to the baselines, answering 81 questions correctly versus 82–83 for the baselines.

We chose an available 80 GB A100 to accommodate the peak memory requirements of our long-context evaluation. At a context length of 128K tokens, full attention exceeds the 32 GB memory capacity of a single RTX 5090 even at B=1.

Q4: Clearer throughput comparisons.

A: We thank the reviewer for suggesting a clearer presentation. We replaced Figure 4 with a table reporting decoding throughput for Gradient Llama-3-8B-1M at 122K context on a single A100. The table makes it possible to compare methods at the same batch size and to see how each offloaded method scales with batch size.

MethodB=4 (tokens/s)B=24 (tokens/s)
Full attention80.67—
ShadowKV101.35211.83
StrideKV (s=2)145.50326.74

Full attention reached its largest feasible batch size at B=4. At that same batch size, a paired run on the shared CPU-offloaded backend shows that periodic retrieval reuse increased StrideKV’s decoding throughput by 43.6% over ShadowKV.

Increasing the batch size from 4 to 24 raised throughput by 2.09× for ShadowKV and 2.25× for StrideKV. The original 4.05× comparison between StrideKV at B=24 and full attention at B=4 reflects the combined effects of CPU-offloaded sparse attention, a larger feasible batch, and periodic retrieval reuse.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.