acceptodds
Under review as a conference paper at ICLR 2027

TesseraKV: KV Paging via Co-Retrieval

Abstract

Agentic workloads increasingly operate over long contexts, causing KV caches to grow rapidly and making memory bandwidth a major bottleneck during generation. KV paging alleviates this cost by retaining the cache while retrieving only the pages needed at each decoding step. There are two critical challenges in KV paging: how keys are grouped into pages and how pages are scored for retrieval. Existing methods construct pages using heuristics, and score those pages using a separate criterion. These two decisions should instead be derived from a common objective: whether the keys in a page are likely to be retrieved together. We propose TesseraKV, which derives both page construction and page scoring from : keys should share a page when their attention logits tend to vary together under the query distribution of a head. This common principle yields a covariance-weighted geometry for partitioning keys and a spread-aware score for estimating the attention mass of each page. Because the decoding-query distribution is unavailable when the cache is constructed, we further study how to estimate this geometry from queries available beforehand. We find that prefill queries provide a useful but task-dependent signal for decoding-query geometry, while incorporating queries from the downstream instruction substantially improves the co-retrieval structure relevant to partitioning. Across a range of LLMs, long-context tasks, and agentic workloads, TesseraKV consistently improves downstream generation quality over state-of-the-art KV retrieval methods at matched KV budgets. For example, on Claw-Eval agentic tasks, TesseraKV achieves an overall success rate of , improving over the previous state of the art at by points.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLMs, KV cache retrieval

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_5D7gOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. Figure 11 suggests that the preferred mixing parameter λ\lambda 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?

  2. How were the spread-correction coefficients κ′\kappa' and κ\kappa 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.

  3. 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
AuthorsOpenReview ↗

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.

W1

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.

  • Calibration settings. We calibrate \kappa' offline, using a single model Muse-Glimmer-30B, on two representative settings: a RULER-16K subset (synthetic retrieval) and InfiniteBench Book Summarization (natural prose). The selected values, κ′=6\kappa'=6 and κ′=4\kappa'=4, respectively, are then fixed and reused without further tuning across North-Mini, Cmdr-7B, all other tasks, and Claw-Eval.
  • A robust operating range. The benchmarks generally exhibit an inverted-U trend, particularly on RULER, with the best performance achieved at [4−6][4-6]. Too little correction underweights pages with larger spreads, while too much overweights them. Performance is also relatively stable within this range: the difference between 4to64 to 6 is less than 0.6 points on both benchmarks.
  • Linear vs quadratic form. Both forms achieve comparable performance at their respective optima. However, the linear correction is more robust to overestimating (\kappa'), exhibiting a smaller performance drop at κ′=10\kappa'=10 in 7 of 8 evaluated settings. This makes it a more suitable choice for deployment when the coefficient must be calibrated offline and fixed across models and tasks.

We recommend linear form + kappa value [4−6][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.

W2

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.

Method8K B=3264128256Avg.16K B=3264128256Avg.
FullCache94.0694.0694.0694.0694.0692.6992.6992.6992.6992.69
LouisKV45.9862.6377.7088.2868.6542.1754.9670.4482.5862.54
TesseraKV50.8471.3585.1190.1974.3740.9159.5475.1886.0765.43
TesseraKV + EA50.6871.5385.5790.0674.4642.3361.1477.5486.4066.85

Table W2b, ruler accuracy on Ministral-3-8B-Instruct across budgets.

Method8K B=3264128256Avg.16K B=3264128256Avg.
FullCache93.9593.9593.9593.9593.9593.0693.0693.0693.0693.06
LouisKV53.1273.8887.5492.7776.8346.1969.0482.3988.4971.53
TesseraKV57.2675.2784.9291.1677.1553.0970.0380.8089.5273.36
TesseraKV + EA58.6474.8586.6091.9778.0255.8772.3982.6690.2375.29

These empirical results and related discussion have been added to the limitations section in Appendix I (line 1509).

AuthorsOpenReview ↗

Official Comment by Authors

We thank the reviewer for raising this question. We did not tune λ\lambda 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 λ≈\lambda \approx 0.5–0.6, while natural-text tasks favor λ≈0.2–0.3\lambda\approx0.2–0.3. Accordingly, we use λ=0.5\lambda=0.5 for all RULER tasks and λ=0.2\lambda=0.2 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 λ=0.2\lambda=0.2 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 CC 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 ii, each global-attention layer and KV head additionally attends to 4 sink tokens, all 256 question tokens, and the ii generated tokens. Thus, TesseraKV attends to 772+i772+i tokens, approximately 1,028 on average in total, compared with C+256+iC+256+i 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 / B6464k / B32128k / B16256k / B8
Global attention (13 layers, including page scoring and selection), Full / TesseraKV4.67 / 0.764.68 / 0.584.59 / 0.594.23 / 0.69
Sliding-window attention (39 layers), Full / TesseraKV1.51 / 2.381.25 / 1.370.97 / 1.240.84 / 1.19
FFN, Full / TesseraKV7.52 / 7.547.45 / 7.446.65 / 6.656.71 / 6.71
QKV/O projections, Full / TesseraKV2.42 / 2.522.41 / 2.432.51 / 2.522.50 / 2.50
Norms, residual, LM head, sampling, Full / TesseraKV1.40 / 1.441.32 / 1.361.25 / 1.351.23 / 1.49
Total decode step, Full / TesseraKV17.69 / 14.3316.82 / 12.9415.41 / 11.9814.82 / 12.15
Speedup1.23×1.30×1.29×1.22×
Ceiling with zero global-attention cost1.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.

AuthorsOpenReview ↗

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.

Reviewer_UPhAOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

TesseraKV groups cached keys using query covariance, aiming to place keys that are likely to be retrieved together on the same page. It adds a spread-based correction to page scores and shows better quality at tight retrieval budgets, alongside faster decoding than full attention.

Critical strengths
  • The covariance-based partition has a clear mathematical motivation.

  • The experiments cover retrieval, long-document tasks, and agent workloads, with useful ablations separating partitioning from scoring.

  • A working GPU implementation demonstrates whole-model throughput gains, with indexing and prefill overhead reported.

Critical weaknesses
  • The “closed-form” gate relies on unvalidated assumptions and several approximations. The deployed linear correction also differs from the derived formula.

  • The stated KV budget excludes the question and generated tail, which are always read in full. It is unclear whether all baselines use the same policy and incur comparable actual KV traffic.

  • Speed comparisons only use full attention. Without direct latency comparisons against LouisKV and ArkVale, the efficiency advantage over existing retrieval methods remains unclear.

Questions for authors

see weakness

4 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for careful reviewing and raising questions about experiment setup and results. We would like to answer them one by one. Meanwhile, the revised parts of the manuscript are colored in blue and the changes reflecting your comments are highlighted with "@Reviewer UPhA" in orange. The line numbers are based on the revised version.

W1

We made the following assumptions for gates in our work. Here we provide analysis or empirical evidence to support each:

  1. Gaussian model for per-key logit derviation. We approximate each key's δti\delta_{ti} with the N(0, si2s_i^2) model. Figure R.1 compares the empirical distributions of δ_ti across decode queries in different layers/heads/pages with the predicted Gaussian distributions. The predicted spread s_i closely matches the observed per-key variation. Although individual key means are not exactly zero, they fall within the predicted 10–90% range for the majority of keys.
  2. Approximating per-key spreads with page means. Spreads are similar within a page (median coefficient of variation 0.14–0.16, visible as the near-constant band height in Fig. R1), so replacing each sis_i with the page mean sps_p changes the estimated page correction by only 2.3–2.7% at the median.

Figure R1. Distribution comparison across different heads/layers/pages seed 0

Figure R2. Distribution comparison across different heads/layers/pages seed 1

These experiments and discussions are added to the assumption validation section in Appendix I (line 1444) in the revised manuscript.

W2

The budget BB counts only the context keys selected per KV head at each decoding step. For every baseline, the four attention-sink tokens, the question block and all generated tokens are always attended in full and are not charged to BB. All methods therefore attend over the same set of uncompressed tokens and differ only in which BB context keys they select, so their per-step KV traffic is matched across ruler, InfiniteBench and Claw-Eval. The clarification has been added to experiment details in Appendix D (line 933) in the revised manuscript.

W3

We report additional inference results on Claw-Eval, the Claw-Eval benchmark on average has 12 turns per task, and for each turn the 10K ISL and OSL of 279 tokens.

In Table W2a, we report prefill performance in TTFT, along with a breakdown into indexing and matmul time. Measurements are taken at batch size 1 across Claw-eval tasks, with KV-cache write-back to CPU included for the offloaded configurations on a single B200 with PCIe Gen 5.

Table W2a. Prefill comparison with LouisKV

MethodTTFT per task (sum over turns)of which index buildof which pre-fill
TesseraKV-1285.44 s1.85 s3.59 s
LouisKV-512, prefix cache + rebuild6.68 s2.65 s4.03 s

Summed across all turns, TTFT is 5.4 s for TesseraKV-128 and 6.7 s for LouisKV-512. Index construction and maintenance account for 1.85 s and 2.65 s, respectively. Both methods incur similar overhead on the median task (about 3.6 s). However, LouisKV's per-turn index rebuilding becomes increasingly costly in longer sessions, resulting in 1.3 s higher average TTFT than TesseraKV.

In Table W2b, we report decode performance with the KV cache offloaded to CPU memory, using a RetroInfer-style wave buffer with the same 768-key GPU cache for both methods on the same GPU setup.

As batch size increases, TesseraKV-128’s performance advantage widens. It delivers 10% higher decoding throughput at batch 64 and 15% higher at batch 128 (3,418 vs. 2,962 tokens/s), while reducing per-step latency by 13%. This advantage comes from lower KV transfer overhead, which accounts for an increasing share of each decoding step at larger batch sizes. TesseraKV-128 selects 4× fewer keys per step than LouisKV-512. It also achieves a higher GPU cache hit rate (82% vs. 66%), meaning more selected keys are already resident on the GPU. Together, these reduce PCIe KV transfers by 6.1×, from 2.31 to 0.38 MiB per sequence per step.

Table W2b. Decode performance comparison with LouisKV

BatchTesseraKV-128: ms per step (GPU + offload)LouisKV-512: ms per step (GPU + offload)TesseraKV-128 throughputLouisKV-512 throughputTesseraKV advantage (throughput)
118.1 (17.3 + 0.8)18.2 (17.3 + 0.9)55 tok/s55 tok/s+0.9%
1622.7 (22.0 + 0.8)23.4 (21.9 + 1.5)704 tok/s684 tok/s+2.9%
6429.0 (27.9 + 1.1)31.9 (28.1 + 3.8)2,205 tok/s2,004 tok/s+10.0%
12837.4 (35.8 + 1.7)43.2 (36.1 + 7.1)3,418 tok/s2,962 tok/s+15.4%

These experiments have been added Appendix G.2 (line 478, line 1320) in the revised manuscript.

AuthorsOpenReview ↗

Reaching the End of the Public Discussion Phase

Dear Reviewer,

We hope that our responses have sufficiently addressed the concerns you raised. We welcome more 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.

AuthorsOpenReview ↗

Public Discussion Phase Ending Soon

Dear Reviewer,

As the rebuttal deadline is approaching in 2 days, we would be very grateful if you could take a moment to review our responses to your questions and suggestions.

We have carefully addressed your concerns by providing additional clarifications, experiments, and analyses. The corresponding revisions have been highlighted with “@Reviewer UPhA” in orange.

If you have any follow-up questions and suggestions, we would be happy to address them.

Thank you for your valuable time and consideration.

Dear Reviewers,

Thank you again for your time. The authors have posted their rebuttal, please take a moment to read their response, share your follow-up thoughts, and update your rating if appropriate.

Best,
Area Chair

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

TesseraKV reduces decoding-time KV-cache reads by organizing historical keys into pages and retrieving a subset for each query. It estimates query covariance from context and question tokens, clusters keys in the resulting covariance-weighted geometry, and augments query–centroid scores with a precomputed within-page spread correction. For multi-turn workloads, it retains existing pages and partitions newly accumulated history. Experiments on NoPE attention models report improved quality at matched retrieved-token budgets across RULER, InfiniteBench, and Claw-Eval, alongside decoding throughput improvements over full attention.

Critical strengths
  • Strong quality gains at small retrieval budgets. On Claw-Eval at B=128, TesseraKV achieves 70.32% success, versus 42.58% for LouisKV and 76.77% for full attention.
  • Controlled evidence for the proposed partitioning. In Table 8, replacing identity-based partitioning with covariance-based partitioning, while keeping the covariance-aware gate fixed, improves RULER performance from 77.71 to 81.37 at B=64.
Critical weaknesses
  1. The comparison omits a relevant retrieval-plus-estimation alternative. RetroInfer estimates contributions from non-retrieved content, whereas TesseraKV omits them from the current attention output. Comparing these strategies at matched measured decoding cost would clarify their quality–latency trade-off. Equal retrieved-token budgets alone would not ensure equal cost.
  2. End-to-end efficiency on multi-turn tasks remains unverified. The reported 1.23–1.33× decoding throughput and 3.5–4.0% TTFT overhead are useful, but do not establish the cost of completing Claw-Eval tasks. In particular, TesseraKV at B=128 achieves 70.32%, while LouisKV at B=512 achieves 72.26%; their execution costs, including index construction and maintenance, are not compared.
Questions for authors
  1. How does TesseraKV compare with RetroInfer in task quality versus measured decode latency under the same GPU-resident setup, model, and workload?
  2. Could you report task quality versus measured decoding latency or throughput for TesseraKV and LouisKV across the evaluated budgets, with prefill and index-maintenance costs reported separately?
5 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for the careful review and enlightening questions. Here we answer them one by one. Meanwhile, the revised parts of the manuscript are colored in blue and the changes reflecting your comments are highlighted with "@Reviewer YCYE" in green. The line numbers are based on the revised version.

W1

We thank the reviewer for this suggestion. We report both RetroInfer's GPU-only decoding performance and CPU-offloaded KV-cache performance using the released implementation, evaluated on RULER-16k with Command-R7B. All experiments are conducted on a single B200 with PCIe 5.

Before presenting our results, we would clarify that RetroInfer's retrieval-and-estimation techniques are orthogonal to TesseraKV instead of directly competing approaches. TesseraKV can readily incorporate these techniques, and here we also evaluate their combined effects.

In Table W1a, although TesseraKV has better retrieval accuracy with a smaller budget, increasing the GPU retrieval budget from 128 to 512 keys has little impact on decoding latency for either method, owing to the high bandwidth of HBM. Both methods achieve comparable decoding latency across the two budgets.

Table W1a. Ruler accuracy vs decode speed on a single B200 GPU-only system.

Method (64-key pages/clusters)RULER-16kDecode µs/layer, bs=1 / bs=4Decode ms/step, bs=32Decode ms/step, bs=64
RetroInfer, 2 clusters (+ est.)66.2324.7 / 28.58.6912.49
TesseraKV, B=12879.9721.2 / 24.28.4512.06
TesseraKV, B=128 + RetroInfer est.85.0124.3 / 28.18.6012.32
RetroInfer, 8 clusters (+ est.)86.5025.7 / 33.58.9513.01
TesseraKV, B=51286.4621.6 / 27.08.4112.19
TesseraKV, B=512 + RetroInfer est.86.6024.7 / 31.08.6912.47

In Table W1b, we evaluate CPU-offloaded KV-cache performance, the retrieval is more sensitive due to the PCIe bandwidth. We used RetroInfer's wave buffer with capacities of 800 (5% context budget).

With an 800-key buffer, TesseraKV combined with RetroInfer’s estimation at a 128-key budget achieves 1.49 points of RetroInfer at 512 keys. With a 4× smaller key budget in TesseraKV, the same wave buffer becomes relatively larger for it, giving a higher hit rate (0.96 vs 0.73). Together with fewer key budgets in the read traffic, this provides 20× less PCIe traffic, and 37% lower decoding latency (13.13 vs. 20.91 ms) at batch size 64.

Table W1b. Ruler accuracy and decode time on a single B200 with CPU offloading.

Method (64-key pages/clusters)RULER-16kDecode ms/step, bs=32 (800)Decode ms/step, bs=64 (800)
RetroInfer, 2 clusters (+ est.)66.239.1913.15
TesseraKV, B=12879.979.0412.92
TesseraKV, B=128 + RetroInfer est.85.019.1513.13
RetroInfer, 8 clusters (+ est.)86.5013.0520.91
TesseraKV, B=51286.4611.4117.85
TesseraKV, B=512 + RetroInfer est.86.6011.6218.03

We have added RetroInfer to the intro and related work (line 140). These experiments and the analysis have been added to Appendix G.1 (line 364, line 1268) in the revised manuscript.

AuthorsOpenReview ↗

Official Comment by Authors

W2

We report additional inference results on Claw-Eval, the Claw-Eval benchmark on average has 12 turns per task, and for each turn the 10K ISL and OSL of 279 tokens.

In Table W2a, we report prefill performance in TTFT, along with a breakdown into indexing and matmul time. Measurements are taken at batch size 1 across Claw-eval tasks, with KV-cache write-back to CPU included for the offloaded configurations on a single B200 with PCIe Gen 5.

Table W2a. Prefill comparison with LouisKV

MethodTTFT per task (sum over turns)of which index buildof which pre-fill
TesseraKV-1285.44 s1.85 s3.59 s
LouisKV-512, prefix cache + rebuild6.68 s2.65 s4.03 s

Summed across all turns, TTFT is 5.4 s for TesseraKV-128 and 6.7 s for LouisKV-512. Index construction and maintenance account for 1.85 s and 2.65 s, respectively. Both methods incur similar overhead on the median task (about 3.6 s). However, LouisKV's per-turn index rebuilding becomes increasingly costly in longer sessions, resulting in 1.3 s higher average TTFT than TesseraKV.

In Table W2b, we report decode performance with the KV cache offloaded to CPU memory, using a RetroInfer-style wave buffer with the same 768-key GPU cache for both methods on the same GPU setup.

As batch size increases, TesseraKV-128’s performance advantage widens. It delivers 10% higher decoding throughput at batch 64 and 15% higher at batch 128 (3,418 vs. 2,962 tokens/s), while reducing per-step latency by 13%. This advantage comes from lower KV transfer overhead, which accounts for an increasing share of each decoding step at larger batch sizes. TesseraKV-128 selects 4× fewer keys per step than LouisKV-512. It also achieves a higher GPU cache hit rate (82% vs. 66%), meaning more selected keys are already resident on the GPU. Together, these reduce PCIe KV transfers by 6.1×, from 2.31 to 0.38 MiB per sequence per step.

BatchTesseraKV-128: ms per step (GPU + offload)LouisKV-512: ms per step (GPU + offload)TesseraKV-128 throughputLouisKV-512 throughputTesseraKV advantage (throughput)
118.1 (17.3 + 0.8)18.2 (17.3 + 0.9)55 tok/s55 tok/s+0.9%
1622.7 (22.0 + 0.8)23.4 (21.9 + 1.5)704 tok/s684 tok/s+2.9%
6429.0 (27.9 + 1.1)31.9 (28.1 + 3.8)2,205 tok/s2,004 tok/s+10.0%
12837.4 (35.8 + 1.7)43.2 (36.1 + 7.1)3,418 tok/s2,962 tok/s+15.4%

These experiments have been added Appendix G.2 (line 478, line 1320) in the revised manuscript.

Q1

Please refer to W1

Q2

Please refer to W2

AuthorsOpenReview ↗

Public Discussion Phase Ending Soon

Dear Reviewer,

We updated additional experiments, and analysis to answer your questions and hope that our responses have sufficiently addressed the concerns you raised. We welcome more 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.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the reviewers' concerns and our corresponding responses

Dear ACs,

We would like to thank all reviewers for their time and suggestions. We have thoughtfully addressed the concerns raised by the reviewers one by one. Below is a summary of the reviewers' concerns and our corresponding responses.

C1: Comparison with a relevant retrieval-plus-estimation alternative (reviewer YCYE)

We added experiments comparing TesseraKV, RetroInfer, and TesseraKV+RetroInfer. The results show that TesseraKV achieves lower latency and higher output quality because it needs to read substantially fewer KV entries. Furthermore, we demonstrate that TesseraKV can be combined with the estimation techniques introduced in RetroInfer to achieve an even better performance-quality trade-off.

C2: Direct latency comparison with LouisKV (reviewer YCYE, UPhA)

We added experiments to directly compare TesseraKV with LouisKV on agentic tasks, reporting both prefill and decode times. TesseraKV achieves lower latency because it requires reading 4× fewer KV entries than LouisKV.

C3: Discussion of assumptions and approximations used in the close-form gate (reviewer UPhA)

We added a section discussing the two approximations used. We provide an analysis or additional empirical evidence to support each approximation made in the mathematical derivation.

C4: Clarification of KV budget and hyperparameter settings (reviewer UPhA, 5D7g)

We added a clarification paragraph to the manuscript detailing the budget settings and hyperparameter selection process.

C5: Paper's scope and RoPE support (reviewer 5D7g)

We clarified that our theoretical analysis is based on NoPE attention. We also provided additional empirical experiments demonstrating the SOTA results of TesseraKV to RoPE-based models under the same budget. Finally, we refined the paper's claims to avoid over generalising the theoretical contribution of TesseraKV to all attentions. We explicitly clarified the theoretical derivation under the NoPE setting from the empirical results on RoPE-based models, which are now presented as a discussion.

C6: Whole-model decode latency breakdown (reviewer 5D7g)

We added an experiment to clarify the breakdown the whole-model latency and indicate why and where TesseraKV brings in the most gain.

Best regards,

Submission 42969 authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.