acceptodds
Under review as a conference paper at ICLR 2027

DeSKV: Low-Rank Routing and Deferred Selection for KV-Cache Offloading

Abstract

Long-context generation is limited by KV-cache storage and access. Routing-based offloading reduces GPU memory use by keeping exact K/V in host memory and retrieving only a query-dependent working set. This requires a compact router that preserves token rankings as queries change, while minimizing the routing overhead for latency. This paper presents DeSKV, a low-rank routing method with step-deferred selection. The router is fitted from query and key moments, with more weight on keys; Step deferral selection utilizes the preceding step's token selection while preparing the next working set. On Qwen3-8B, DeSKV achieves a 48.3 average LongBench score at a 256-token prompt-KV budget versus 48.5 with full cache, and reduces decode latency by 33.6% relative to full-cache execution at a 97K-token context.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV cache compression, long-context LLM inference, dynamic KV cache selection, KV cache offloading, sparse attention

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_337LOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The authors propose DeSKV which keeps exact KV in host memory, routes with INT4 rank-32 key-weighted sketch. It reuses the previous step's selection to overlap routing with the forward pass. DeSKV obtains 48.35 LongBench vs 48.51 full cache and reduces decode latency by 33% at 97K context on Qwen3-8B .

Critical strengths
  1. Simple and useful finding that best query-key mixing weight shifts toward keys during decoding
  2. Extensive latency measurement with CUDA graphs and accounting of GPU footprint
  3. Step deferral is easy to implement and gives a clear speedup over immediate selection
Critical weaknesses
  1. Mostly a combination of known pieces with concepts from Loki routing, PQCache, InfLLM offload
  2. Mistral loses 3 points vs full cache but main text says near-full-cache. The latency gain is only at 97K and batch size , at 8K the method is slower than full cache
Questions for authors
  1. Authors should report TPOT at batch size 4, 8, 16 at 97K context
  2. Why does Mistral lose 3 points when Qwen and Llama do not?
5 comments

W1. Relationship to Loki, PQCache, and InfLLM

DeSKV addresses both routing accuracy and the cost of preparing a small working set for decoding. Loki constructs a low-rank basis from key statistics, PQCache uses product-quantized keys, and InfLLM retrieves blocks through representative keys. Our analysis examines how a shared query-key projection preserves routing scores as decode queries change. Sections 4.1–4.2 show that the mixture preferred during prefill differs from the one preferred during decoding. This finding motivates fitting the basis jointly, with more weight on the fixed prompt keys, and using the resulting compact sketch for token-level selection.

For execution, Figure 5(a,b) identifies two patterns: deferral incurs larger losses during the initial decode steps, and missed high-ranked targets tend to lie near selected positions. Priming uses current-step selection during the initial interval, while local expansion shares scores between neighboring positions within the same token budget. Appendix D.6 evaluates these components separately, showing that pooling helps prepare selections for step deferral.

The contribution lies in designing the router and selection policy for deferred selection. Our analysis shows when deferral loses the most attention mass and where missed next-step targets occur. DeSKV uses these findings to prepare a compact, token-level working set that supports deferred execution at 128–256 tokens per head. We will make this connection clearer in the revised paper.

Q1. TPOT at batch sizes 4, 8, and 16

We measured Qwen3-8B at 97K context on one 96 GB RTX PRO 6000, using a 256-token prompt budget per KV head. Each request has a different prompt and independent KV state. Table R11 reports TPOT with the complete decode step captured in a CUDA Graph.

Batch sizeFull-cache TPOT (ms)Immediate TPOT (ms)Deferred TPOT (ms)
123.1619.7015.51
451.4225.4320.11
8OOM31.7425.33
16OOM46.0336.19

Table R11. Batch-size scaling on Qwen3-8B at 97K context. latencies are medians of five 128-step runs after 16 warm-up steps, with the complete decode step captured in a CUDA Graph. OOM denotes insufficient GPU memory.

Deferral reduces TPOT from 25.43 to 20.11 ms at batch 4 and from 46.03 to 36.19 ms at batch 16. Routing and KV-transfer work increase with the number of requests, but overlapping this preparation continues to reduce decoding latency across the tested batch sizes.

At batch 16, the deferral generates approximately 442 tokens/s in total, with about 228 GB of exact KV stored in host memory. Full-cache execution exceeds GPU memory capacity at batches 8 and 16. We will include these measurements in the revised paper.

W2-1. Performance at shorter contexts

DeSKV targets long-context generation, where KV-cache storage and access become major memory-capacity/bandwidth bottlenecks, and reducing the GPU-resident working set and per-step KV reads provides greater benefits. Therefore at 8K context and batch size one, the time saved by reducing KV access is smaller than the remaining routing and fetching overhead, making DeSKV slightly slower than full-cache execution.

W2, Q2. Mistral's larger quality loss

Mistral is more sensitive to tight prompt-KV budgets than Qwen3 and Llama. To identify where the loss occurs, we separately examined working-set restriction, score approximation, and deferred selection. Table R12 reports results on the first 64 examples of six LongBench tasks: HotpotQA, 2WikiMQA, PassageRetrieval-en, Qasper, GovReport, and TREC.

SelectionScore: 128 BudgetsScore: 256 Budgets
Full cache (all KV)55.3755.37
Exact-score, immediate50.1248.99
INT4 sketch, immediate49.3849.20
INT4 sketch, deployed49.1848.74

Table R12. Mistral-7B-Instruct-v0.3, mean over six tasks. Budgets include 32-token prompt tail.

At a 256-token budget, Mistral's mean score drops from 55.37 with full cache to 48.99 with exact-score immediate selection. INT4 immediate selection scores 49.20, and the deployed policy scores 48.74. Thus, a substantial gap is already shown before score approximation or deferred execution is introduced.

We also compared exact-score selection across models on the three shared tasks: HotpotQA, 2WikiMQA, and TREC. At budget 256, the full-cache and exact-score selection means are 53.7 and 48.6 for Mistral, 57.1 and 56.8 for Llama, and 53.9 and 53.7 for Qwen3. The same working-set restriction therefore has a larger effect on Mistral.

Increasing DeSKV's prompt budget from 256 to 1,024 raises Mistral's six-task mean from 48.74 to 54.39, compared with 55.37 for full cache. These results support strong budget sensitivity on Mistral. We will make this model dependence explicit and scope the near-full-cache quality statement to the reported Qwen3 and Llama results.

AuthorsOpenReview ↗

Gentle reminder: author–reviewer discussion ending in two days

Dear Reviewer 337L,

Thank you again for your review and helpful questions. With the author–reviewer discussion period ending in two days, we would like to briefly follow up on our responses and the revised manuscript.

Regarding batch scaling, Appendix E.3, Table 20 now reports results at batch sizes 1, 2, 4, 8, and 16 with distinct prompts. Deferral reduces latency relative to immediate DeSKV at every tested batch size; at batch 16, latency decreases from 46.03 to 36.19 ms/token per request.

Regarding Mistral’s larger quality loss, Appendix D.1 includes a diagnostic showing that a substantial gap is already present with exact-score immediate selection. Increasing the prompt budget from 256 to 1,024 improves the deployed six-task mean from 48.74 to 54.39, compared with 55.37 for full cache. Section 6.3 also explains why routing overhead outweighs attention savings at 8K context.

We would appreciate any follow-up feedback on whether these additions address your questions. If anything remains unclear, we would be happy to clarify it during the remaining discussion period.

Thank you again for your time and consideration.

Best regards,
The authors

AuthorsOpenReview ↗

Follow-up before the discussion deadline

Dear Reviewer 337L,

With one day remaining in the discussion period, we would appreciate any brief feedback on whether our responses and revised manuscript address your main concerns. If any questions remain, we would be happy to clarify them before the discussion closes.

Thank you again for your time and consideration.

Best regards, The authors

Reviewer_rYAjOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper proposes a routing-based selection method to make LLM attention over long input contexts less costly. The method saves GPU memory by storing the full KV cache in host memory instead of in GPU memory. It saves compute because it maintains small sketches of the keys (= SVD scores) on the GPU, allowing for quick score approximation, and because a number of latency-hiding tricks are used.

Although the method and evaluation appears suitable, the paper does not adequately position itself w.r.t. related work, both in discussion and in experimental study. I recommend to reject the paper mainly for this reason.

UDPATE: Positioning to related work has been addressed during the revision in both discussion and experiments. I hence recommend to accept the paper.

Critical strengths

S1. It's a simple approach

S2. Heuristics appear suitable

S3. Experimental results look promising: w.r.t. to the methods considered in the experimental study, the proposed method achieves a favorable quality/cost tradeoff.

Critical weaknesses

UDPATE: During the revison, W1 and W4 have been fully, W2 and W3 have been partially addressed by the authors.

W1. Related work is not adequately covered. Related work is only very briefly discussed so that the difference to closely related work (such as PQCache or RetrievalAttention) remains unclear. Moreover, and more critically, several highly relevant works have not been not been considered, neither in discussion nor experimental study. This includes:

Not cited:

  • MagicPIG: LSH Sampling for Efficient LLM Generation (ICLR25)
  • RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference (VLDB26)
  • SmallKV: Small Model Assisted Compensation of KV Cache Compression for Efficient LLM Inference (NeurIPS25)
  • AttentionPredictor: Temporal Patterns Matter for KV Cache Compression (NeurIPS25)

Cited but not discussed/compared to:

  • RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval (NeurIPS25)

W2. No analysis. The method is largely heuristic w/o any analysis. The low-rank approximation appears suitable, only the actual directions are chosen heuristically (hyperparameter alpha). The deferred selection for latency hiding, however, is very hacky (don't defer initially, average scores with neighbors) and feels more like the result of a try-and-error process.

W3. Retrieval quality (i.e., selected tokens) severely drops with decoding length (Fig 2b) and the deferral (Fig 4b, which unfortunately does not show the deployed approach). So it seems to be only suitable for short generation tasks.

W4. It's not clear to me to what extent the experimental study is comprehensive in that (i) key methods are missing (see W1) and (ii) in that it's not clear whether alternative methods have been suitably tuned (e.g., PQCache, which is closest to the proposed method in the study). It's also not clear to what extent the results transfer over once the batch size in increased (the study only considers batch size 1) since then latency hiding may become more challenging.

Questions for authors

None

6 comments

W1, W4-1. Related work and missing baselines

We agree that the original discussion did not explain the differences to several closely related methods sufficiently. We will expand it to distinguish their routing representations, prediction mechanisms, and attention computation. We have also evaluated DeSKV against these methods and report the results below.

PQCache divides each key into subvectors and represents them using codebook indices (indices of representative vectors). During decoding, it combines query–codebook scores to rank tokens and fetches the selected exact K/V. This lookup-and-selection process takes 12.37 ms per step in our Qwen3-8B evaluation at 97K context and a 256-token prompt budget, compared with 5.16 ms for DeSKV’s low-rank routing. DeSKV also overlaps routing and KV fetching with decoding.

RetrievalAttention addresses the query–key distribution mismatch by linking keys associated with the same prefill queries into a search graph. During decoding, it traverses this graph and computes attention over retrieved K/V on the CPU, then combines the result with GPU attention. This requires host computation for both search and attention. DeSKV scans a compact GPU-resident sketch and transfers selected exact K/V to the GPU for attention, eliminating these CPU-side computations during decoding.

RetroInfer groups KV entries into clusters, retrieves important clusters, and estimates contributions from non-retrieved clusters using representative keys and aggregated values. This makes retrieval cluster-granular and uses summaries directly in the attention output. DeSKV allocates its prompt budget to individual tokens and uses the sketch only for selection; attention uses the selected exact K/V.

MagicPIG uses LSH (locality-sensitive hashing) to sample keys for attention estimation. Sampling can capture contributions from lower-scoring tokens that top-score selection may omit. Hash lookup and sampled attention run on the CPU, with the sampled-token count varying across queries and context lengths. DeSKV uses a fixed prompt-token working set, computes attention on the GPU, and overlaps preparation of the next working set with decoding.

AttentionPredictor uses a small CNN predictor on attention history to estimate next-step token importance and prefetch the corresponding KV, and SmallKV similarly uses a smaller model to compensate for information lost through cache compression. These approaches require training which cannot run parallel during the prefill phase. DeSKV uses a prompt-fitted linear router which does not require such model training.

We evaluated AttentionPredictor, RetroInfer, and MagicPIG using their official implementations on Llama-3.1-8B-Instruct, with the same prompts, recommended hyperparameters, and scoring procedures for the first 64 examples of six LongBench tasks: TriviaQA, MultiFieldQA-en, SAMSum, PassageRetrieval-en, RepoBench-P, and GovReport. AttentionPredictor uses its released predictor. FreeKV results are reported in Table R1; we couldn't find public implementations of RetrievalAttention and SmallKV.

MethodBudget (tokens/head)Allocation within budgetMean score
Full cacheAllFull attention62.18
AttentionPredictor (original policy)128 total64 predicted + 32 sink + 32 recent57.05
AttentionPredictor (original policy)256 total192 predicted + 32 sink + 32 recent59.94
AttentionPredictor128 prompt64 predicted + 32 sink + 32 prompt-tail58.07
AttentionPredictor256 prompt192 predicted + 32 sink + 32 prompt-tail60.07
DeSKV deployed128 prompt96 selected + 32 prompt-tail61.76
DeSKV deployed256 prompt224 selected + 32 prompt-tail62.05

Table R4. AttentionPredictor comparison on Llama-3.1-8B-Instruct, 64 examples per task. AttentionPredictor uses the released predictor, retains its first two full-attention layers, and calibration every five decode steps. Its original policy selects tokens from both prompt and generated tokens; we implemented a prompt-tail variant that attends all generated tokens.

AttentionPredictor scores 58.07 and 60.07 at prompt budgets of 128 and 256 tokens, compared with 61.76 and 62.05 for DeSKV. DeSKV therefore maintains higher mean quality at both prompt budgets. The evaluated AttentionPredictor implementation simulates sparse attention by masking dense attention and does not support CUDA Graph capture. At 32K context and a 256-token budget, it takes 179.1 ms/token, compared with 22.3 ms/token for full cache, both without graph capture. We exclude this simulation runtime from the latency comparison.

MethodPrompt budget (tokens/head)Mean score8K latency (ms/token)32K latency (ms/token)
Full cacheAll62.1813.0015.11
RetroInfer132 (96 selected + 4 sink + 32 prompt-tail)61.5727.929.0
RetroInfer260 (224 selected + 4 sink + 32 prompt-tail)61.8128.028.1
DeSKV deployed128 (96 selected + 32 prompt-tail)61.7613.113.2
DeSKV deployed256 (224 selected + 32 prompt-tail)62.0513.213.5

Table R5. RetroInfer comparison on Llama-3.1-8B-Instruct, using the same six tasks and 64 examples per task as Table R4. RetroInfer retrieves tokens with multiples of 16 and fixed 4 sink tokens, with an additional 23.2% of clusters contributing through attention estimation outside the listed token budget. Latency is measured separately at fixed 8K and 32K contexts on one RTX PRO 6000, median of 5 iterations.

At about 256-token prompt budget, RetroInfer scores 61.81, compared with 62.05 for DeSKV. At 32K context, their decode latencies are 28.1 ms/token which largely exceeds our 13.5 ms/token, respectively.

MethodPrompt tokens attended/headMean score8K latency (ms/token)32K latency (ms/token)
Full cacheAll62.1813.0015.11
MagicPIG236 (mean)62.1720.3625.87
DeSKV deployed128 (fixed)61.7613.1413.16
DeSKV deployed256 (fixed)62.0513.2313.49

Table R6. MagicPIG comparison on Llama-3.1-8B-Instruct, using the same six tasks and 64 examples per task as Table R4. Mean token counts include sampled keys and 68 protected prompt tokens; generated history is excluded. Latency is measured separately at fixed 8K and 32K contexts on one RTX PRO 6000, median of 5 iterations.

As mentioned earlier, MagicPIG deploy variable token budgets per queries and context lengths. MagicPIG scores 62.17, compared with 62.05 for DeSKV at 256 prompt tokens. At 32K context, DeSKV takes 13.49 ms/token compared with MagicPIG's 25.87 ms/token, achieving similar mean quality with lower latency. Table R7 further shows how MagicPIG's attended prompt-token count changes with context length.

Prompt lengthMagicPIG K10/L150: mean tokens/headMagicPIG K8/L75: mean tokens/head
<8K140279
8–16K259623
16–32K374954
>32K (2 prompts)7822,097
Overall (mean prompt length: 10.6K)236557

Table R7. Mean prompt tokens attended per query head in the monitored MagicPIG sparse layer. K10/L150 is the default setting recommended in their paper; K8/L75 is the paper’s lower-memory setting (half the hash tables). Counts include sampled CPU keys, 4 sink tokens, and 64 prompt-tail tokens.

MagicPIG's attended prompt-token count grows with context length, while DeSKV maintains a fixed prompt working set of 128 or 256 tokens per KV head.

W2. Analysis behind the design choices

Thank you for raising this concern. We have clarified the analysis and empirical evidence underlying DeSKV’s design. Our study of query–key geometry and selection errors across decoding steps and token positions motivates joint fitting, priming, and local expansion. Controlled component studies evaluate these choices and their interactions. Below, we explain how each observation motivates the corresponding design and how the experiments support its use.

Query-key fitting. We agree that α\alpha is a design parameter. We have clarified the analysis motivating the mixture and the experiments used to select its value. The router’s shared basis must preserve relevant directions from both queries and keys. Figure 1 shows that prefill query energy occupies fewer effective dimensions than prompt-key energy, motivating substantial key coverage. Given (\alpha) and the rank, Equation 8 determines the basis by minimizing weighted, normalized reconstruction error.

Decode-time behavior provides another reason to retain more key information: the fitted basis and prompt keys remain fixed while queries evolve. A query-heavy basis may fit prefill queries well but transfer less effectively to later queries. Figure 3(a–b) tests this with the same fitted bases on both query sets: the preferred query weight shifts from approximately 0.8 on prefill queries to 0.2-0.5 on decode queries. Appendix D.5 examines this pattern across three models and extends the Qwen3-8B evaluation to 512 decode steps.

In the downstream sweep in Table 10, α=0.2\alpha=0.2 gives the highest mean at budget 128 and remains close to the highest mean at budget 256. We therefore use it as an empirically supported choice within the decode-preferred range.

Priming. Although reusing the preceding step’s selection preserves much of the current step’s attention mass overall, we observe substantially greater loss during the first few decode steps across eight tasks (Figure 5(a)). This makes early decoding a particularly poor time to defer selection. Errors at this stage may also influence the direction and accuracy of subsequent generation (SpecCoT (EMNLP 2025); PMPD (ICLR 2025)). We therefore select with the current query for the first three steps, then switch to deferred execution. With the deployed scoring rule, three priming steps improve the six-task mean over one step at both tested budgets (Table 11); Appendix D.7 shows that gains from further priming vary by task.

Local expansion. Step-deferred selection requires the working set prepared at the current step to cover the next step’s attention targets. Relevant prompt information can span adjacent KV positions (SnapKV, (NeurIPS 2024)), while query continuity and positional encoding can support attention shifts between nearby positions (AttentionPredictor (NeurIPS 2025)). These properties motivate sharing routing evidence among adjacent positions.

Figure 5(b) supports this locality: 96–98% of next-step top-16 targets are already in the current top-128 selection, and the remaining targets lie near selected positions. This is consistent with attention remaining within the same context region while shifting between individual tokens. DeSKV therefore averages adjacent routing scores before selecting the next working set, without increasing the KV budget. We compare average and max pooling at widths two, three, and five; width-two averaging gives the highest deferred LongBench mean at both tested budgets (Appendix D.8).

If pooling compensates for attention shifts between steps, it should benefit deferred selection more than immediate selection. Table R8 tests this prediction using the same router and common examples, with priming fixed at three steps for the deferred comparison. At 256 tokens per head, pooling leaves the immediate six-task mean nearly unchanged (63.44 to 63.41), but improves deferred selection from 61.87 to 63.01. At 128 tokens per head, the gains are 0.45 and 1.30 points, respectively. These results support local expansion as compensation for the loss introduced by previous-step deferral.

We will incorporate these analyses and supporting references into the revised paper to clarify the rationale and empirical support for query-key fitting, priming, and local expansion.

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

DeSKV reduces GPU KV-cache storage and access costs during long-context decoding. It builds an INT4 low-rank routing index from query and key statistics collected during prefill, while keeping complete KV entries in host memory. During decoding, each query selects KV entries for the next step, allowing routing and fetching to overlap with model execution. Three initial immediate-selection steps and local score pooling help reduce the error from reusing the previous step’s selection. Experiments evaluate generation quality and latency across three models (Sections 5–6 and Appendices D–E).

Critical strengths
  1. The method achieves a useful memory–quality trade-off. With a budget of 256 prompt tokens per KV head, Qwen3-8B reaches a LongBench average of 48.35, compared with 48.51 for the full cache. This is a promising result for such a small prompt working set (Table 2).
  2. The ablations are thorough. The paper studies query–key weighting, rank, quantization, priming, and pooling. The results help explain the design choices, particularly the benefit of joint query–key fitting over key-only fitting and the additional speedup from deferred execution (Appendices D–E).
Critical weaknesses
  1. The main scheduling idea has limited novelty given FreeKV. FreeKV already uses the previous decoding step’s retrieved KV entries while moving selection and fetching off the critical path. It also introduces fine-grained correction to handle inaccurate reuse.(arxiv.org) DeSKV’s step-deferred selection follows the same basic principle (Section 5.2). The differences are mainly its joint low-rank router and its use of priming and local pooling to control reuse error. These are useful changes, and the router has supporting ablations, but I find the overall contribution incremental. My concern is the extent of the conceptual advance over existing work, rather than simply the absence of a FreeKV baseline.
  2. The reliability of cross-step reuse needs stronger evidence. Figure 5(b) shows that the previous top-128 set covers 96–98% of the next step’s top-16 targets. This supports persistence of the highest-ranked tokens, but it does not show how much attention mass the full reused working set preserves. Figure 4(b), which compares equal-size top-128 sets, reports only about 58% overlap. These results are compatible, but the paper does not explain how the remaining changes affect generation. Although each step scans the entire prompt index, newly selected entries are used one step later. It remains unclear how often this delay causes errors when attention shifts abruptly after priming (Sections 5.2–5.3).
Questions for authors
  1. Given FreeKV’s step-wise KV reuse, what is the main conceptual contribution of DeSKV beyond the routing representation? Does the combination of joint fitting, priming, and pooling provide a capability or insight that is not already captured by the existing reuse-and-correction approach?
  2. Why does Figure 5(b) use the next step’s top-16 targets? How does coverage change for larger target sets? After priming, how often does reuse miss a substantial amount of attention mass, and do these events correspond to output errors?
4 comments

W1, Q1. FreeKV comparison and novelty

We agree that FreeKV establishes previous-step KV reuse with overlapped selection and fetching. DeSKV’s contribution is the joint design of a compact token-level router and a selection policy that supports accurate reuse at tight KV budgets of 128–256 tokens per head, without query-triggered current-step correction. Beyond the routing representation, the central insight is that the temporal and spatial structure of reuse error can guide how the working set is prepared.

FreeKV handles changes in the required working set through query-similarity-based correction. When similarity falls below threshold, it triggers correction for that head. However, similarity checking and correction are performed on the attention-critical path. Similarity checking alone increases latency by 24%, while correction is triggered in average 43% of heads per steps, increasing overall latency by 39% at 32K context. DeSKV instead uses measured patterns in selection error to remove the need for this corrective path: the largest attention-mass loss occurs during the initial decoding steps, and missed next-step high-ranked targets tend to lie near currently selected positions (Figure 5(a–b)).

These observations connect the three components. Joint query–key fitting constructs a routing basis that transfers from prefill to changing decode queries. Priming uses current-step selection during the initial interval where deferral is least reliable. Local expansion shares routing evidence among adjacent positions, preparing the working set to cover nearby next-step targets within the same token budget. This combination allows DeSKV to maintain deferred execution while controlling deferral error under a small working-set budget.

We evaluated FreeKV's official accuracy implementation on Llama-3.1-8B-Instruct using the first 64 examples of six LongBench tasks: TriviaQA, MultiFieldQA-en, SAMSum, PassageRetrieval-en, RepoBench-P, and GovReport. τ\tau denotes FreeKV's query-similarity threshold for correction. Table R1 compares its released and reduced-budget configurations with DeSKV.

MethodKV budget (tokens/head)Selection policyMean score8K latency (ms/token)32K latency (ms/token)
Full cache (DeSKV environment)AllFull attention62.1813.0015.11
Full cache (FreeKV environment)AllFull attention61.8913.3515.52
FreeKV2,048Deferred + correction, τ=0.8\tau=0.861.1520.5422.33
FreeKV256Immediate57.6618.3519.44
FreeKV256Deferred55.3513.2013.30
FreeKV256Deferred + correction, τ=0.8\tau=0.856.7417.9618.56
FreeKV128Immediate52.2716.5917.77
FreeKV128Deferred51.4213.0113.09
FreeKV128Deferred + correction, τ=0.8\tau=0.852.6517.6117.97
DeSKV256Deferred + priming + Avg262.0513.2313.49
DeSKV128Deferred + priming + Avg261.7613.1413.16

Table R1. Mean score over six LongBench tasks, 64 examples per task. FreeKV uses 128 sink + 128 recent + 1,792 retrieved tokens at 2,048; the 128/256-token adaptations use 32 recent tokens and 32 sink. Latency is measured separately at fixed 8K and 32K contexts on one RTX PRO 6000, median of 5 iterations.

At a 256-token budget, FreeKV’s immediate selection scores 57.66 with 19.44 ms/token at 32K. Their deferral reduces latency to 13.30 ms/token but lowers the score to 55.35. Enabling correction improves the score to 56.74, while latency increases to 18.56 ms/token. In comparison, DeSKV achieves a higher score of 62.05 at 13.49 ms/token without runtime correction. These results demonstrate that DeSKV maintains accurate cross-step deferral under tight KV budgets while keeping routing and fetching off the attention critical path.

W2, Q2. Attention-mass coverage and output reliability

We chose top-16 targets to focus on high-weight tokens. Equal-size top-128 overlap counts every selected token equally, so changes among lower-weight entries can reduce overlap without a proportional loss of attention mass. Figure 4(b) compares overall selection consistency, while Figure 5(b) examines the persistence and locations of high-ranked targets.

We extended the analysis to larger target sets and the actual deployed working set. Table R2 reports target coverage together with the attention mass carried by those targets.

Current-query target setTop-16Top-32Top-64Top-128
Attention mass in target set (% of total)54.257.259.862.2
Targets retained by deployed selection (%)58.051.944.836.9

Table R2. Per-query-head measurements on Qwen3-8B: 16 GovReport prompts (mean length 11.5K), 256 prompt tokens per KV head, steps 33–128.

Increasing the target set from top-16 to top-128 tokens increases its cumulative mass from 54.2% to 62.2%, which tells that top-16 tokens contain most of the mass carried by the top-128. This supports our focus on high-ranked targets in Figure 5(b), where we examine which potentially-critical tokens the preceding selection misses at the next step. We next separate the effects of pooling and one-step delay by comparing selections on the same live queries.

Score poolingCurrent-step mass coverage (%)Immediate task meandeferred (+prime) task mean
None87.4863.4461.87
Avg269.7063.4163.01

Table R3. Pooling effects on Qwen3-8B at 256 prompt tokens per KV head. Avg2 averages neighboring routing scores. Mass coverage uses 16 GovReport prompts and steps 33–128; both current-step selections are evaluated on the same deployed-generation queries. Task means use the same six tasks and 64 examples per task as Table R1

Applying Avg2 (deployed local pooling) changes current-step mass coverage from 87.48% to 69.70%. Reusing the pooled selection at the next step changes coverage from 69.70% to 66.73%. Although pooling captures less raw attention mass, Table R3 shows that it improves three-prime deferral from 61.87 to 63.01. This suggests that deferred selection accounts for the potentially critical tokens across steps for better performance, alongside aggregate attention-mass coverage.

We will present these summary-quality results alongside the attention-mass analysis in the revised paper.

AuthorsOpenReview ↗

Gentle reminder: author–reviewer discussion ending in two days

Dear Reviewer HNAY,

Thank you again for your review and thoughtful questions. With two days remaining in the discussion period, we would like to briefly highlight the explanations and additional evidence provided in our responses and revised manuscript.

Regarding the comparison with FreeKV, we added a detailed evaluation and analysis in Appendix D.2, Table 9 of the revised manuscript. At the 256-token budget, DeSKV achieves a six-task mean of 62.05 versus 56.74 for corrected FreeKV, with 13.49 versus 18.56 ms/token at 32K context. We also clarified how joint fitting, priming, and local expansion support deferred selection without runtime correction.

Regarding reuse reliability, our response examines larger target sets and the deployed working set, and compares attention-mass coverage with downstream task quality. These results help explain why changes in selection overlap or retained mass do not directly determine the effect on generation quality.

We would appreciate your feedback on whether these explanations and experiments address your concerns. If they do, we would be grateful if you could consider updating your assessment and rating accordingly. If any questions remain, we would be happy to address them within the remaining discussion period.

Thank you again for your time and consideration.

Best regards,
The authors

AuthorsOpenReview ↗

Follow-up before the discussion deadline

Dear Reviewer HNAY,

With one day remaining in the discussion period, we would appreciate any brief feedback on whether our responses and revised manuscript address your main concerns. If any questions remain, we would be happy to clarify them before the discussion closes.

Thank you again for your time and consideration.

Best regards, The authors

Comments on the paper

2 comments

Thank you for the constructive follow-up and for taking the time to consider our additional experiments.

W1. We appreciate your feedback. We will expand the related-work discussion and baseline comparisons in the revised paper.

W2. We appreciate your acknowledgment that these design choices appear suitable. Below, we also like to clarify the mathematical basis for joint fitting and explain the contribution of our deferral selection policy.

Our Equation (6) bounds the routing-score error by the product of the query and key projection residuals. Let a=∥(I−Π)q∥2/μQa=\|(I-\Pi)q\|_2/\sqrt{\mu_Q} and b=∥(I−Π)k∥2/μKb=\|(I-\Pi)k\|_2/\sqrt{\mu_K}, where μQ\mu_Q and μK\mu_K denote their respective mean squared vector norms. Applying Young's inequality with η>0\eta>0 gives

\leq ab \leq \frac12(\eta a^2+\eta^{-1}b^2).$$ Setting $\eta=\sqrt{\alpha/(1-\alpha)}$ and averaging over calibration query-key pairs yields, for a fixed $0<\alpha<1$, $$\mathbb E\left[\frac{|q^\top k-q^\top\Pi k|}{\sqrt{\mu_Q\mu_K}}\right] \leq \frac{J_\alpha(U)}{2\sqrt{\alpha(1-\alpha)}},$$ where $$J_\alpha(U)= \alpha\frac{\|Q(I-UU^\top)\|_F^2}{\|Q\|_F^2} +(1-\alpha)\frac{\|K(I-UU^\top)\|_F^2}{\|K\|_F^2}.$$ Minimizing $J_\alpha(U)$ is equivalent to maximizing $\operatorname{tr}(U^\top C(\alpha)U)$, where $C(\alpha)$ is exactly Equation (8). Thus, for each fixed mixture weight, our joint fitting minimizes an explicit upper bound on normalized routing-score error. The choice of $\alpha$ is further guided by our query-key effective dimensionality and prefill-to-decode transfer analysis. Second, as discussed in our response to Reviewer HNAY, the current SOTA deferred selection method, FreeKV, uses cosine similarity between consecutive queries to determine whether the old selection remains valid. When similarity falls below threshold, it triggers correction for that head. However, this approach has two limitations. First, similarity checking and correction are performed on the attention-critical path. Similarity checking alone increases latency by 24%, while correction is triggered in average 43% of heads per steps, increasing overall latency by 39% at 32K context. Second, cosine similarity alone cannot reliably determine whether the top-k selection remains unchanged, as selection stability also depends on other factors. **DeSKV instead uses priming and local expansion to avoid runtime correction**. Although heuristic, these choices are based on consistent observations across tasks. We consider accurate deferral without runtime correction a significant contribution beyond step-wise reuse. In details, in FreeKV, for a token $i$ selected at step $t-1$ and an unselected token $j$, let $\Delta_{ij}=q_{t-1}^\top(k_i-k_j)>0$ denote their attention-score margin. At the next step, $$q_t^\top(k_i-k_j) =\Delta_{ij}+(q_t-q_{t-1})^\top(k_i-k_j) \geq \Delta_{ij} -\|q_t-q_{t-1}\|_2\|k_i-k_j\|_2.$$ Therefore, the top-k selection is guaranteed to remain unchanged if, for every selected-unselected token pair, $$\Delta_{ij}> \|q_t-q_{t-1}\|_2\|k_i-k_j\|_2.$$ For normalized queries, the query-change term becomes $\|q_t-q_{t-1}\|_2 = \sqrt{2(1-\textbf{sim}(q _t,q _{t-1}))}$. Thus, highly similar queries can still change the top-k selection when score margins are small. Conversely, larger query changes can preserve the selection when the margins exceed the corresponding bounds. Accounting for score margins and key differences could provide an accurate trigger, but would require non-trivial additional overhead and may cause frequent correction. **W3**. Selection overlap and attention-mass coverage are both meaningful indicators of **routing quality**. Higher values are desirable, but they do not uniquely determine downstream quality, which also depends on the subsequent computation and context history. We use these metrics to analyze routing behavior, and evaluate the downstream quality separately. The observation from Figure 3(a-c) is that achieving full-cache-level downstream quality does not necessarily require routing quality to reach 100\%, and Figure 2(b) and Figure11 shows routing quality stabilizes and remains consistent after some point. We may not have made this distinction sufficiently clear in our original response. Regarding Figure 4(b), its purpose is to isolate the difference between layer-wise and step-wise deferral under the same policy. Priming and pooling are motivated by temporal and positional locality across decoding steps within the same layer, which does not directly extend to layer-wise deferral. Applying them only to step-wise deferral would introduce additional variables into the comparison. Figure 5(c) evaluates the corresponding downstream raw-deferral selection quality, where layer-wise deferral also performs worse. We will clarify these distinct purposes in the revised paper. **W4**. Thank you for highlighting batch-size scaling. We will incorporate these results in the revision.
AuthorsOpenReview ↗

Global response

We thank the reviewers for their comments and discussion. We have uploaded a revised manuscript incorporating the main clarifications and additional evaluations from our responses. Revised and added text is marked in blue in the uploaded PDF. We summarize the key revisions below. All section, figure, and table references refer to the revised manuscript.

  1. Expanded related work (Section 3). We expanded the discussion of RetrievalAttention, RetroInfer, MagicPIG, SmallKV, AttentionPredictor, and FreeKV, and clarified their routing representations, selection mechanisms, and attention computation.

  2. Additional baseline comparisons (Section 6 and Appendices C.2, D.1, E.2, and E.4). We added RetroInfer and FreeKV to the retrieval, LongBench, latency, and memory comparisons. The LongBench results cover Qwen3-8B, Llama-3.1-8B-Instruct, and Mistral-7B-Instruct-v0.3. We also documented their hyperparameters, budget allocations, and runtime settings.

  3. Batch-size scaling (Appendix E.3, Table 20). We added measurements at batch sizes 1, 2, 4, 8, and 16 with 97K-token contexts and distinct prompts for each request, including additional routing baselines. Deferral reduces latency relative to immediate DeSKV at every tested batch size. At batch 16, it reduces latency from 46.03 to 36.19 ms per output token per request, reaching an aggregate throughput of 442 tokens/s.

  4. Detailed comparison with FreeKV (Appendix D.2, Table 9). We added comparisons of immediate selection, deferred selection, similarity checking without correction, and deferred selection with correction. We also included an analysis showing that selection stability depends on score margins and key differences in addition to query similarity. This clarifies the distinction between FreeKV’s correction mechanism and DeSKV’s use of priming and local expansion to support deferred execution without runtime correction.

  5. Mathematical justification for joint fitting (Section 4.2 and Appendix A.1). We explicitly stated the joint query–key reconstruction objective and its relationship to the fitted basis. For a fixed mixture weight and rank, we proved that this basis minimizes the stated upper bound on the attention-score error caused by projection on the fitting samples.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.