- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes PQ-HSA, which uses IVF-PQ to estimate attention scores for all cached tokens, performs exact attention computation for the selected top-k tokens, and uses PQ-based approximations for the remaining tokens. The method is implemented within the vLLM framework. Experiments show that, at a context length of 128K and retrieval budgets of 1%–2%, PQ-HSA achieves overall accuracy close to full attention while delivering measurable speedups.
Critical strengths
-
The method is implemented and evaluated within vLLM, lending credibility to the results and supporting its practical feasibility.
-
The controlled ablation study in Figure 4 is logically sound and effectively rules out the explanation that the method’s gains stem solely from more accurate retrieval.
Critical weaknesses
-
The novelty of this paper is limited. PQCache already uses PQ to select top-k tokens. The novelty of this paper lies in how the remaining tokens are handled: PQCache directly discards them, whereas this paper uses their proxy scores to estimate their attention scores. However, there are related works such as TurboQuant that estimate the original attention scores using proxy scores obtained by quantization methods. Therefore, the paper should focus on reporting the discrepancy between the estimated and exact scores of these remaining tokens.
-
The performance results are questionable. As shown in Section 3.3 and Table 5, the performance experiments generate 64 output tokens, but the index update interval is 256 tokens, so these experiments do not include the index update overhead. As stated in line 245, the optimized index construction takes 0.84 seconds at 128K on one H20, which still has a considerable impact on single-step decoding latency. Furthermore, the paper does not report the impact of index construction on the prefill stage.
Questions for authors
I will consider raising my rating if the authors can answer the following questions:
-
What is the discrepancy between the estimated and exact attention scores of the remaining tokens?
-
How would including the index update overhead affect the reported decoding performance? What impact does index construction have on the prefill stage?
-
Could other quantization methods used in approximate nearest neighbor search (ANNS), such as SQ, VQ and RaBitQ, replace PQ in the proposed method?
5 comments
Response to Reviewer 5X5j #2
Q3. Can SQ, VQ or RaBitQ replace PQ? Yes. Equation (5) needs one estimated logit per token. The same operator gives the following results at ρ = 1%, with 512 lists unless specified. Code sizes exclude the list ID. RaBitQ also stores two floats per token outside its bit code.
| Quantizer | Code bytes/token | Exact top-k recall | Relative output error |
|---|---|---|---|
| VQ, centroid only (512 / 4096 / 8192 lists) | 0 | 0.47 / 0.58 / 0.62 | 0.062 / 0.039 / 0.032 |
| Query-aware PQ, 8 × 4 bits | 4 | 0.57 | 0.038 |
| Residual quantizer, 4 × 8 bits | 4 | 0.64 | 0.029 |
| SQ, 1 / 2 / 4 bits per dimension | 16 / 32 / 64 | 0.63 / 0.73 / 0.91 | 0.027 / 0.018 / 0.013 |
| RaBitQ, 1 bit per dimension | 16 | 0.55 | 0.042 |
| PQ / residual quantizer, both 16 × 8 bits | 16 | 0.74 / 0.81 | 0.018 / 0.014 |
One-bit SQ gives about the same output error as the four-byte residual code (0.027 vs. 0.029) using 16 bytes. At the same 16-byte code size, PQ and residual quantization give the lowest errors in this comparison.
Thank you again for your review. As the discussion period is approaching the end, we would like to kindly confirm whether we have sufficiently addressed your concerns.
If you are satisfied with our responses, we would greatly appreciate your consideration in adjusting the evaluation scores accordingly.
We sincerely look forward to your feedback.
Best regards, Authors
Thank you for your responses. An earlier response would have allowed more time for a thorough discussion.
Regarding W1, my understanding remains that the central idea is to use PQ-based estimates to select top-k tokens for exact attention, while approximating the contribution of the remaining tokens using those estimates. Sharing the index and codebooks between retrieval and approximation reduces the additional overhead, but I remain unconvinced that this constitutes substantial novelty.
In principle, a similar reuse strategy could also apply to TurboQuant: its quantized inner-product estimates could guide token selection, followed by exact refinement of important tokens if the original K/V vectors were retained. Conceptually, fully quantized attention represents the case with no exact-token branch, which could be extended with selective exact computation. Although the implementation details would differ, I still consider the conceptual novelty of the proposed method limited.
Regarding Q3, exact top-k recall can be a misleading proxy for whether another quantizer can effectively replace PQ. It treats all tokens in the reference top-k set equally, despite potentially large differences in their attention weights. Low recall may primarily reflect missed tokens near the cutoff that contribute little to the attention output. For sparse attention, the more relevant quantity is the fraction of true attention mass captured by the selected tokens, together with downstream model quality.
For example, Twilight’s analysis suggests that retaining approximately 90% of attention mass can preserve useful model performance in its evaluated settings. This motivates comparing quantizers at comparable retained attention mass and downstream quality, then examining their speed and memory tradeoffs. The reported top-k recall and relative output error alone do not establish these tradeoffs.
PQ also introduces codebook construction and maintenance costs, and its retrieval quality depends on the learned k-means codebooks. SQ does not require learning or periodically updating such codebooks, suggesting potentially lower construction and maintenance overhead. I would therefore expect SQ to have potential speed advantages, although this should be established through direct measurements that include index construction, updates, and decoding costs.
Finally, it remains unclear whether differences in relative output error on the order of translate into meaningful differences in downstream model quality. Evidence connecting these numerical differences to task performance would make the comparison more informative.
Based on these concerns, I maintain my current rating.
Response to Reviewer 5X5j #1
We thank Reviewer 5X5j for your insightful comments. Below is our rebuttal content:
Relation to PQCache and TurboQuant.
Q1 measures what the background recovers, and Figure 4 shows a gain of 12.0 points on RULER with the selector held fixed. Against FlashAttention on the same GPU the attention call is 2.5–3.4× faster at 128K.
Q1. How accurate are the scores for unselected tokens? At ρ = 1%, the unselected tokens carry 10.7% of the true attention mass with the revised index. PQ-HSA estimates 8.8%. Reusing those scores reduces the relative output error from 0.103 with truncation to 0.029. In PQ-HSA the scores also determine how much each list's mean value contributes to the output.
These measurements use real keys, values and queries on 126K NarrativeQA and RULER prompts (16 layers, 8 KV heads, 4 query heads per KV head, 32 decode steps). Masses are means. The other columns average per-task medians. The codebooks here used ten training iterations. The fast build used for the timing measurements gives about 5% higher output error.
Per sample, the estimated background mass is low by a median factor of exp(−0.33) with the revised index and exp(−0.76) with the submitted one (medians of the log ratio, averaged over tasks). A Gaussian model of the logit error explains the sign: if the error given the estimate has zero mean and variance σ², the expected weight is the estimated weight times exp(σ²/2). Adding qᵀΣq/(2d) to the background logits, with Σ the covariance of the key reconstruction error that index construction already provides, brings the log ratio to +0.03 and the relative output error to 0.020. On RULER this correction changes accuracy by −0.025 [−0.052, 0.000] at ρ = 1% and by +0.003 at 0.25%, so Eq. (5) stays as submitted and we will add the correction to the paper as an analysis.
Q2. Prefill and periodic updates. A 64-token generation ends before the first update. On a 126K prompt at ρ = 0.25%, the first token takes 43.0 s with either method. The index is built from the completed KV cache at the first decode step (3.2 s). An update every 256 tokens costs 4.9 ms per layer, or 0.55 ms per generated token (0.28 at 32K and 1.31 at 384K). Generating 4096 tokens triggers 15 updates per layer, and the whole 126K request then takes 118.4 s against 133.0 s for dense at ρ = 0.5% (64.8 s against 65.5 s for 1024 tokens). Between outputs 1024 and 4096, decode costs 17.12 ms/token including updates at ρ = 0.25%, against 21.96 for dense. Appendix C's 0.84 s is the batched build of the submitted index at 128K. Its unbatched build in the 126K cold request takes 6.2 s.