- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper tackles the problem of decoding overhead. To the best of my understand, the authors propose to index keys in coordinates ordered by joint query-key score energy. These coordinates come from request-local query and key second moments.
Critical strengths
There is no clear critical strengths. There might be some novelties in the approach design, but is not presented in the current writeup.
Critical weaknesses
W1. The paper requires significant polishing to reach the level of a ICLR paper. There is no intuitions or supporting evidences behind the approach at all.
W2. There is also no experimental evidences that QKSieve outperforms the literature. It seems to maintain the accuracy (sometimes better than the competitors, but not consistent) at a lower speed.
Questions for authors
N/A
2 comments
I appreciate the authors' rebuttal. However, it is still very hard for me to follow and understand what is the core intuition behind the approach (is it a compression bit allocation problem, or it is a selection problem, or a joint bit allocation and selection problem), and why this design is intuitively better than the competitors that solve the same problem (and what are they).
I also noticed that there are some results comparing against the direct competitors, as in table 8, 9, 12, 13. I suggest to move them into the main experiments. However, it is still very hard to understand what are the key measurements to check and what are the main takeaways.
I also appreciate the effort that the authors put in the experiments; I encourage the authors to polish the paper to explicitly present the intuitions of the design, and make the baselines clear and clarify the distinctions to them. for the current version, I will maintain my scores.
We agree with your reading of the downstream scores. Several selectors reach similar task scores at the same budget. The clearest advantage we measured against a competing selector is lower complete-attention latency than our FIER reference when both use the same exact sparse-attention kernel. Our whole-model timing compares QKSieve with dense decoding, and it includes a grouped-query setting where dense is faster.
W1. Why the representation can improve retrieval
If a cached key has reconstruction error e, its unscaled attention score has error q⊤e for the current query q. Two key errors of the same length can therefore change a token's rank differently. Figure 2(a) gives an example in which their expected squared score errors are 4 and 1. QKSieve uses prompt queries and keys to identify these directions, then measures how much score error each available bit width introduces. At every decoding step it selects tokens from the packed index and reads their original keys and values. For Robust, a separate value sketch and the query's approximate scores estimate the contribution of omitted tokens. Figure 1 and Algorithm 1 now show where each approximation enters.
We tested the retrieval mechanism directly on Qwen3-4B at 32K, over 18,432 held-out layer/head/query conditions (Appendix G). The 240-bit QKSieve reference retrieves 75.70% of the tokens in the exact top 2% and captures 87.30% of the dense attention mass. The 256-bit FIER reference gives 47.90% recall and 81.61% mass. Recall counts how many high-scoring tokens survive selection. Retained mass also matters for the output. For Quant, Section 4 bounds the output error by the omitted dense probability mass times the diameter of the value vectors. Thus a change in recall can have little effect on output when the exchanged tokens carry little mass.
W2. How quality compares at the same active-token budget
Table 3 uses 800 matched LongBench examples per model. Each selector receives the same token allowance on each example. Mean macro-score retention relative to dense attention is 99.77% for Robust, 99.86% for FIER, 100.00% for RaBitQ, 99.75% for SparQ and 92.12% for Quest. The relative order changes by model. For example, FIER scores higher than Robust on Qwen, while Robust scores higher on Llama. We therefore describe the quality result as preserving aggregate task score at this budget. It also comes with a storage cost. The original cache stays resident, and the auxiliary key index and value sketch together add 7.47% of the original FP16 K+V storage under the paper's rate accounting.
W2. Where speed improves, and where it falls short
Matched complete-attention timing. Table 14 times our FIER RTN-1 group-32 CUDA reference, Quant and Robust at batch size one on the same RTX 3090. All paths use native multi-head attention with 32 query and 32 KV heads, the same token-budget schedule, and the same downstream exact sparse-attention kernel. Results are medians over three seeds. Lower times are better.
These numbers include selection, exact sparse attention and, for Robust, the omitted-value correction. They establish a speed advantage over this FIER implementation. A full-model race against FIER's released runtime remains unmeasured.
Whole-model decoding and startup. This comparison uses dense attention as the baseline. At 64K history, Robust reaches 2.22× dense speed in steady native multi-head decoding (Table 4). Over a 64-token generation that includes index construction and excludes dense prefill, the speedup is 1.31×. At 32K history the same 64-token comparison gives only 0.81× (Figure 3). On the separate native Qwen grouped-query path at 32K, Robust is slower even in steady state, at 47.675 versus 42.574 ms/token for dense attention (Table 16). The revised abstract and conclusion identify this grouped-query result alongside the multi-head speedup.