- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes TesseraKV, a KV paging method that clusters keys whose attention logits tend to vary together across queries. Pages are selected using a score that combines the page centroid’s logit with a correction for within-page key spread. TesseraKV achieves higher accuracy at matched KV retrieval budgets than the evaluated baselines and reports improvements in decoding throughput. The paper offers an interesting perspective on page construction through query-aware geometry. However, the manuscript could more clearly explain the experimental choices underlying the page-scoring rule and the selection of related hyperparameters. Its general framing also appears broader than its demonstrated applicability: all evaluated models use NoPE global-attention layers, and the authors acknowledge that the method does not directly support RoPE.
Critical strengths
-
This paper proposes an interesting concept of “co-retrieval”: grouping keys whose attention logits tend to vary together across queries. Based on this principle, the authors formulate a tractable clustering objective for constructing KV pages. I also find the spread-aware approximation of the page score clever. Together, these provide a principled approach to designing page partitioning and scoring.
-
TesseraKV achieves higher accuracy than the baseline methods under the same retrieved-KV budget across the evaluated workloads. The paper also reports improvements in inference throughput, demonstrating practical benefits beyond retrieval accuracy.
Critical weaknesses
-
In Section 3.3, the authors derive the quadratic spread-corrected page score in Eq. 13, whereas the main results use a linear correction. Appendix E.2 provides an empirical rationale for this choice, but Table 7 and Figure 10 also show substantial sensitivity to the correction coefficient, particularly on RULER. The coefficient-selection protocol and its ability to generalize beyond the evaluated benchmarks remain unclear. Since the correction contributes substantially to performance, this uncertainty makes it difficult to assess the robustness of the reported gains.
-
The scope of the paper’s claims exceeds the demonstrated applicability of the method. TesseraKV is presented as a general approach to KV paging in autoregressive transformers, but all evaluated models use NoPE global-attention layers. Moreover, the authors acknowledge that the method does not directly support RoPE in the limitation section. The authors should either restrict the claims to NoPE attention or provide evidence of broader applicability.
Questions for authors
-
Figure 11 suggests that the preferred mixing parameter is highly dataset- and task-dependent. Although Table 5 lists the values used, how were these values selected? In particular, what data and selection criterion were used, and were the tuning examples separate from the evaluation examples?
-
How were the spread-correction coefficients and selected? Appendix E.2 discusses their sensitivity and the choice of a linear correction, but it would be helpful to clarify whether coefficient selection used separate tuning data and whether the selected coefficients transfer reliably across models and unseen workloads.
-
Figure 6 reports a decoding throughput improvement of 1.23–1.33× at context lengths of 32k–256k. Given the substantial reduction in KV accesses intended by the method, the end-to-end improvement appears modest. Could the authors specify the KV budget and measurement settings used for these results, including the number of tokens attended outside the retrieval budget? A whole-model latency breakdown under the same settings would also help clarify which costs limit the overall speedup.
8 comments
Official Comment by Authors
We thank the reviewer for raising this question. We did not tune against downstream accuracy. Instead, we selected it using two intrinsic metrics: co-retrieval agreement and covariance agreement between the estimated covariance and a reference covariance computed from decoding queries.
This protocol reveals two distinct regimes. Synthetic retrieval tasks favor 0.5–0.6, while natural-text tasks favor . Accordingly, we use for all RULER tasks and for all InfiniteBench and Claw-Eval tasks, without per-task tuning. This distinction is also consistently observed in additional experiments on other subtasks reported in Appendix E.4.
Calibration data. We calibrate using a small, balanced RULER subset (10 samples per task, 130 in total) and 10 documents from InfiniteBench Book Summarization in Fig. 4. Using 10 samples per task provides sufficient pooled decoding tokens to obtain a stable reference covariance, as detailed in Appendix D.1.
Regarding data separation, calibration samples were not excluded from evaluation, but the overlap is small: 130 of 8,500 RULER samples and 10 of approximately 2,000 InfiniteBench samples. Additionally, the selection criteria depend only on model queries, without using downstream task scores, and therefore do not optimize for evaluation accuracy. We also apply to Claw-Eval directly, based on its natural-text characteristics, without any additional calibration. We will clarify this calibration protocol and the distinction between intrinsic metric-based selection and downstream accuracy tuning in the revision.
This clarification is added to Appendix D (line 943) to reflect your suggestion.
Q2
Please refers to W1
Q3
We thank the reviewer for this question. Here we clarify them one by one.
Measurement settings. All experiments use a single NVIDIA B200 GPU with SGLang, FlashAttention 4, BF16, and CUDA Graphs enabled for every decode step. Each request contains context tokens followed by a 256-token question and generates 512 tokens. This clarification is added to the inference throughput section (line 481).
Tokens attended beyond the retrieval budget. The retrieval budget counts only selected context keys. At decode step , each global-attention layer and KV head additionally attends to 4 sink tokens, all 256 question tokens, and the generated tokens. Thus, TesseraKV attends to tokens, approximately 1,028 on average in total, compared with for full attention. This clarification is added to experiment details in (Appendix D, line 933).
Whole-model latency breakdown. To explain the bounded end-to-end speedup, we provide a breakdown of GPU decoding latency in Figure Q3. Decode is memory-bound, but KV-cache reads account for only part of the total memory traffic. Model weights alone contribute approximately 50 GB of reads per step, largely independent of batch size. At the largest batch size for each context length, global-attention KV reads account for only 35–40% of total data movement.
Figure Q3. Decode latency breakdown
Table Q3. Figure Q3 equivalent of decode latency breakdown
| GPU time (ms/step) | 32k / B64 | 64k / B32 | 128k / B16 | 256k / B8 |
|---|---|---|---|---|
| Global attention (13 layers, including page scoring and selection), Full / TesseraKV | 4.67 / 0.76 | 4.68 / 0.58 | 4.59 / 0.59 | 4.23 / 0.69 |
| Sliding-window attention (39 layers), Full / TesseraKV | 1.51 / 2.38 | 1.25 / 1.37 | 0.97 / 1.24 | 0.84 / 1.19 |
| FFN, Full / TesseraKV | 7.52 / 7.54 | 7.45 / 7.44 | 6.65 / 6.65 | 6.71 / 6.71 |
| QKV/O projections, Full / TesseraKV | 2.42 / 2.52 | 2.41 / 2.43 | 2.51 / 2.52 | 2.50 / 2.50 |
| Norms, residual, LM head, sampling, Full / TesseraKV | 1.40 / 1.44 | 1.32 / 1.36 | 1.25 / 1.35 | 1.23 / 1.49 |
| Total decode step, Full / TesseraKV | 17.69 / 14.33 | 16.82 / 12.94 | 15.41 / 11.98 | 14.82 / 12.15 |
| Speedup | 1.23× | 1.30× | 1.29× | 1.22× |
| Ceiling with zero global-attention cost | 1.36× | 1.38× | 1.40× | 1.38× |
TesseraKV reduces global-attention latency by 6–8×, saving 3.5–4.1 ms per decode step. However, global attention accounts for only about 27% of full-attention decoding time, while the majority of computation (FFN, projections, normalization, and LM head) remains largely unchanged. This imposes an Amdahl's-law speedup ceiling of approximately 1.4×, which TesseraKV approaches.
For CPU-offloaded KV Cache serving, TesseraKV’s advantage becomes greater. With PCIe bandwidth as a key bottleneck, TesseraKV’s 4× lower KV read requirements per step allows it to reduce data transfer overhead significantly compared to LouisKV.
We thank the reviewer again for the time invested in raising the questions and comments that improved the quality and scope of our work. Hopefully this addresses your concerns.
Public Discussion Phase Ending Soon
Dear Reviewer,
We have added experiments, and analysis to answer your questions and hope that our responses have sufficiently addressed the concerns you raised. We welcome further discussion if you have more questions and suggestions.
As the discussion deadline is approaching, we would be very grateful if you could take a moment to review our reply. Thank you for your time and consideration.
Official Comment by Authors
Thank you for the valuable suggestions. We would like to answer your questions one by one. Meanwhile, the revised parts of the manuscript are colored in blue and the changes reflecting your comments are highlighted with "@Reviewer 5D7g" in red. The line numbers are based on the revised version.
We thank the reviewer for raising this concern. We would like to clarify the coefficient-selection calibration and provide some analysis of the robustness of such process.
We recommend linear form + kappa value [4−6] as an empirically robust configs from our experimentation. We hope this clarification has addressed the reviewer’s concern and has added it to Appendix D (line 943) to reflect your suggestion.
We thank the reviewer for raising this question. Theoretically, our closed-form analysis assumes NoPE attention, where attention logits depend solely on query-key geometry. With RoPE, logits also depend on relative positions, so the covariance-to-logit-variance derivation no longer holds exactly. Therefore, we make no theoretical claim about RoPE support.
Here we provide empirical results to evaluate how well TesseraKV transfers to RoPE-based models. We consider two variants and test on Llama-3.1-8B and Ministral-3-8B: (i) estimating the covariance directly from post-RoPE queries, and (ii) combining TesseraKV with EA [1], a workaround discussed in the limitations section that approximates position-dependent rotation matrices using a single average rotation matrix.
As shown in Table W2a and Table W2b, both variants outperform LouisKV on the majority of the budgets in every model, context setting, with gains of 0.3–5.7 points for the first variant and 1.2–5.8 points for the EA-enhanced variant. Gains are largest at moderate budgets on Llama and at (B=32) on Ministral-3. EA also provides a small but consistent improvement over the first variant, with larger gains at longer context lengths. We hope this clarifies that our method empirically can be extended to RoPE-based models and also demonstrate SoTA accuracy results there under the same computational budget.
Table W2a, ruler accuracy on Llama-3.1-8B-Instruct across budgets.
Table W2b, ruler accuracy on Ministral-3-8B-Instruct across budgets.
These empirical results and related discussion have been added to the limitations section in Appendix I (line 1509).