acceptodds
Under review as a conference paper at ICLR 2027

PQ-HSA: Reusing Product-Quantized Scores for Hybrid Sparse-Approximate Attention

Abstract

At each decoding step a language model attends over the key–value (KV) cache of every earlier token, so at long context the attention call is bounded by memory bandwidth. Sparse attention reads only a subset of keys chosen by a cheap score estimate, and most methods give the unread tokens zero weight. The output then draws on only a small fraction of the KV cache, and accuracy drops at small budgets, most on tasks that aggregate information across the context. An inverted-file product-quantization (IVF-PQ) index over the cached keys computes an approximate score for every indexed token in order to rank them; after ranking, those scores approximate the attention logits of the tokens left out. PQ-HSA (hybrid sparse-approximate attention) attends the selected tokens with their original keys and values, and the unselected tokens, the background, enter the same softmax through those scores, summed per inverted list and multiplied by the list's mean value. At 128K and a 1–2% retrieval budget, PQ-HSA is more accurate than Quest and SnapKV on Llama-3.1-8B and Qwen3-30B-A3B and stays close to full attention in macro accuracy; with the same selector, the background term raises macro accuracy on the 8B model from 0.71 to 0.83. In the same 128K setting, inside vLLM on one NVIDIA H20, the decode attention call runs 1.6× faster than the FlashAttention-3 kernel; the speedup grows with context length, and a cost model fitted on 8B to 30B models gives the context length at which it begins. A vLLM plugin runs PQ-HSA on two engine versions without changes to the engine source; code is available at https://anonymous.4open.science/r/pqhsa_release-71BF.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
sparse attention, long-context inference, KV cache, product quantization, approximate attention, LLM decoding, vector search, efficient inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_5X5jOpenReview ↗
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
  1. The method is implemented and evaluated within vLLM, lending credibility to the results and supporting its practical feasibility.

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

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

  1. What is the discrepancy between the estimated and exact attention scores of the remaining tokens?

  2. How would including the index update overhead affect the reported decoding performance? What impact does index construction have on the prefill stage?

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

Response to Reviewer 5X5j #1

We thank Reviewer 5X5j for your insightful comments. Below is our rebuttal content:

Relation to PQCache and TurboQuant.

  • TurboQuant is a quantized compression method. It quantizes vectors so that inner products can be estimated from fewer bits, and for the KV cache it reports quality against bits per channel. It does not select tokens for exact attention and reports no decoding latency.
  • PQCache uses PQ estimates to pick the top-k tokens and drops the rest. It keeps the KV cache in CPU memory and fetches the selected tokens to the GPU, and its latency is compared with other KV-dropping and offloading methods, not with full attention on the GPU.
  • PQ-HSA is a hybrid sparse–approximate attention. One IVF-PQ scan gives a logit estimate for every cached token; the top-k tokens by that estimate receive exact attention, and every other token stays in the same softmax through its estimate (Eq. 5). This takes the method outside the framework of sparse attention. It is a hybrid of vector-quantized (VQ) attention and sparse attention in which the quantized part and the retrieval share one index and one set of codebooks, so the quantized part comes at almost no extra cost.

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.

Index (4 code bytes/token)Unselected mass, exact / estimatedRMS logit error (nats)Total variation, per token / per listRelative output error, truncate / keep background
Submitted IVF-PQ0.124 / 0.0781.140.019 / 0.0130.123 / 0.061
Query-aware residual quantizer0.107 / 0.0880.830.012 / 0.0060.103 / 0.029

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.

AuthorsOpenReview ↗

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.

QuantizerCode bytes/tokenExact top-k recallRelative output error
VQ, centroid only (512 / 4096 / 8192 lists)00.47 / 0.58 / 0.620.062 / 0.039 / 0.032
Query-aware PQ, 8 × 4 bits40.570.038
Residual quantizer, 4 × 8 bits40.640.029
SQ, 1 / 2 / 4 bits per dimension16 / 32 / 640.63 / 0.73 / 0.910.027 / 0.018 / 0.013
RaBitQ, 1 bit per dimension160.550.042
PQ / residual quantizer, both 16 × 8 bits160.74 / 0.810.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 10−210^{-2} 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.

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

This paper proposes PQ-HSA, a training-free method for long-context decoding. The method builds an PQ index over cached keys and reuses the approximate scores for both token selection and background approximation. Selected tokens are attended using their original keys and values, while unselected tokens contribute through their approximate scores and per-list mean values.

Critical strengths
  1. The motivation of retaining the contribution of unselected tokens is clear.

  2. Reusing the scores already computed for retrieval is an efficient design.

  3. The paper includes a vLLM implementation and actual latency measurements across different context lengths and models.

Critical weaknesses
  1. The largest concern is the limited novelty. PQ-HSA combines PQ-based retrieval with background approximation, which is closely related to existing methods such as SparQ, RetroInfer, and Multipole Attention, but comparisons with the existing works are missing.

  2. The accuracy-efficiency trade-off against existing sparse-attention methods is unclear. Accuracy is compared at matched token budgets, while speed is mainly compared against dense attention.

  3. The overall efficiency benefit is limited. The 1.58x speedup at 128K is attention-only and excludes index construction.

  4. The long-context evaluation is limited to subsets of RULER and InfiniteBench. LongBench results are only reported as an average.

Questions for authors

please see weakness section.

3 comments
AuthorsOpenReview ↗

Response to Reviewer MrXd #1

We thank Reviewer MrXd for your insightful comments. Below is our rebuttal content:

Novelty. The submission described the mechanism too briefly. PQ-HSA is a hybrid sparse–approximate attention. One IVF-PQ scan gives a logit estimate for every cached token; the top-k tokens by that estimate receive exact attention, and every other token stays in the same softmax through its estimate (Eq. 5). This takes the method outside the framework of sparse attention. It is a hybrid of vector-quantized (VQ) attention and sparse attention in which the quantized part and the retrieval share one index and one set of codebooks, so the quantized part comes at almost no extra cost. Top-k retrieval and background approximation are designed together around one shared set of scores, which is different from each of the three closest lines of work:

  • Selection only (PQCache, and top-k sparse attention in general). Approximate scores rank the tokens and are then discarded, so the mass of the unselected tokens is lost.
  • Mean compensation (SparQ). The lost mass is returned to one mean value of the whole context, whatever the query's distribution over the remaining tokens.
  • Cluster-level approximation (RetroInfer, Multipole Attention). All tokens of a cluster share the logit of its centroid. A high-weight token inside a low-scoring cluster cannot be selected, and RetroInfer gives zero weight outside its retrieval and estimation zones.

PQ-HSA selects individual tokens wherever they sit and weights every unselected token by its own estimate, at no additional scoring cost.

What this mechanism buys. Figure 4 isolates the background with the selector and the budget held fixed: it adds 12.0 points [9.1, 15.0] of RULER macro accuracy on Llama-3.1-8B at 1% and 1.6 points [0.3, 2.9] on Qwen3-30B at 2%. At 126K and ρ = 1%, scoring only the centroids of 512, 4096 or 8192 lists gives relative attention-output errors of 0.062, 0.039 and 0.032; 512 lists with a four-byte code per token give 0.029. Restricting our own scan to the 128 or 256 best of the 512 lists and treating the others at list level raises the output error by 20–30% and 10–15%, because some high-weight tokens sit in lists whose centroid scores low. In the Multipole Attention release each unselected cluster enters the softmax as a single centroid term, and removing that term lowers its RULER score at the released budget from 0.705 to 0.552, so that design also depends on a background term. PQ-HSA supplies it at token resolution. Against our SparQ implementation the RULER gain is 4.9 points [1.4, 8.6] (Appendix D). Against official Multipole Attention it is 10.0 points [5.9, 14.4] at about 0.5% and 7.6 [3.8, 11.7] at 1%. Against official RetroInfer it is 4.9 points [1.7, 8.2] at about 0.5%, and at the same RULER threshold (0.808) the PQ-HSA attention call takes 117 µs where RetroInfer's takes 260 µs (2.2×).

Generality. The background term can reuse a selector's scores whenever the selector produces an attention-logit estimate for every cached token. It works with all five score sources we tried (PQ, residual quantization, SQ, RaBitQ and centroid-only VQ; table under 5X5j Q3), and the same construction applies to learned selectors such as DeepSeek Sparse Attention, whose indexer scores are likewise dropped after top-k. We have not run that combination; the step to verify is whether the indexer's scores are calibrated well enough to enter the softmax. We regard a mechanism that is effective, costs no extra scoring pass and carries over across selectors and quantizers as the contribution of the paper, and we will rewrite Sections 1 and 3 to present it this way.

Attention-only speedup. The paper's 1.58× and the 2.5–3.4× above both measure the attention operator, the only part PQ-HSA changes. Request-level times with prefill, construction and updates are in the general response under "End-to-end latency".

AuthorsOpenReview ↗

Response to Reviewer MrXd #2

Per-task results

Benchmark (128K)PromptsFull attentionPQ-HSA, ρ = 1%Paired difference [95% CI]
RULER, 8 tasks4000.8850.887–
RULER, last 5 tasks2500.8230.827+0.004 [−0.021, +0.028]
LongBench v1, 16 tasks80047.647.3−0.30 [−0.98, +0.37]
InfiniteBench, 6 tasks30064.859.8−5.0 [−7.5, −2.7]

RULER. Eight 128K tasks, 50 prompts per task. At ρ = 1%, group-shared retrieval scores 0.887 on average against 0.885 for full attention. The largest gain is on cwe (0.364 to 0.486) and the largest loss is on QA (0.980 to 0.900).

Methodniah_singleniah_multikeyvtniah_multiqueryniah_multivaluecwefweqaaverage
full attention1.0000.9601.0000.9700.9500.3640.8530.9800.885
PQ-HSA, group-shared, ρ = 1%1.0000.9601.0000.9600.9300.4860.8600.9000.887
PQ-HSA, group-shared, ρ = 0.25%1.0000.9001.0000.9600.9150.4740.8470.8400.867
PQ-HSA, per-head, ρ = 1%1.0000.9601.0000.9650.9400.4260.8330.9000.878
PQ-HSA, group-shared, ρ = 0.5%–––0.9650.9250.4800.8600.860–
PQ-HSA, per-head, ρ = 0.25%–––0.9350.8550.4220.8600.800–

On the last five tasks alone (250 prompts), the group-shared score is 0.827 at ρ = 1% and 0.818 at 0.5% against 0.823 for dense, paired differences of +0.004 [−0.021, +0.028] and −0.006 [−0.033, +0.020].

InfiniteBench. Six 128K tasks, 50 prompts per task, scored with the upstream task scorers. Generation stops at EOS. At ρ = 1% most of the gap comes from Math.Find (62 to 40), followed by Retrieve.KV (88 to 80). Math.Find's integer scorer rejects responses such as "94.0". On Retrieve.KV, PQ-HSA sometimes copies a single character incorrectly in a 36-character identifier.

taskfull attentiongroup-shared, ρ = 1%group-shared, ρ = 0.5%group-shared, ρ = 0.25%per-head, ρ = 1%submitted index, ρ = 1%
Retrieve.PassKey100100100100100100
Retrieve.Number989896969296
Retrieve.KV888074648478
En.MC222424262222
En.QA19.017.117.818.417.315.8
Math.Find624038344850
average64.859.858.356.460.560.3
difference to full attention [95% CI]−5.0 [−7.5, −2.7]−6.5 [−9.5, −3.7]−8.4 [−11.6, −5.4]−4.3 [−6.7, −2.2]−4.5 [−7.1, −2.1]

LongBench v1. All 16 English tasks, the first 50 prompts per task, official prompts and metrics, ρ = 1%. The group-shared difference from dense is −0.30 points [−0.98, +0.37] over 800 paired prompts; per-head retrieval and the submitted index give −0.41 [−0.83, −0.02] and −0.43 [−1.10, +0.23].

taskdensePQ-HSA, group-sharedPQ-HSA, per-headsubmitted index
narrativeqa27.626.926.328.1
qasper43.243.942.542.3
multifieldqa_en60.461.161.060.8
hotpotqa49.948.549.547.9
2wikimqa47.347.247.345.0
musique30.231.130.231.3
gov_report35.636.435.536.4
qmsum26.324.725.625.3
multi_news26.525.525.626.1
trec74.074.074.074.0
triviaqa89.889.889.888.6
samsum44.544.844.344.6
passage_count4.02.04.04.0
passage_retrieval_en100.0100.0100.0100.0
lcc56.253.454.052.8
repobench-p46.648.045.847.9
average47.647.347.247.2

A single run at 640K gave 1.02×.

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

AuthorsOpenReview ↗

To Reviewer MrXd

Thank you again for your review. Our response now includes measurements of index construction and update costs, along with attention speedups at 128K. If time permits, we’d appreciate hearing whether any questions remain.

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

This paper proposes PQ-HSA, which combines exact attention over selected tokens with approximate attention over the remaining context. It reuses IVF-PQ retrieval scores to estimate background attention mass and aggregates background values through per-list means under a shared normalizer. Experiments demonstrate improved accuracy over several sparse-attention baselines and decoding attention speedups in long-context settings.

Critical strengths

S1: The method addresses the information loss caused by discarding unselected tokens in sparse attention.

S2: The B-versus-T comparison isolates the background contribution using the same selector and exact-token budget. Additional ablations and attention-output measurements support the proposed mechanism.

S3: PQ-HSA improves accuracy over Quest and SnapKV in the reported settings while remaining relatively close to full attention

Critical weaknesses

W1: Incomplete comparisons with recent and closely related methods. The main comparisons emphasize Quest and SnapKV, while the ParisKV comparison is limited to quality in a single model–context–budget setting, without latency or memory measurements. ShadowKV and RetroInfer are discussed but not evaluated experimentally, and their exclusion is not explicitly justified. RetroInfer is particularly relevant because it also combines exact attention with an approximation of the remaining context. Although differences in offloading and memory residency complicate direct comparisons, controlled quality evaluations and system measurements under matched GPU-memory constraints would better establish PQ-HSA’s advantages.

W2: Limited end-to-end request-level evaluation. Most headline speedups measure the attention segment, which does not establish the reduction in total request latency. Although the paper reports whole-step TPOT at 512K and request-level timings against PQCache and MagicPIG in Appendix F, these measurements cover limited configurations and without more relevant baselines such as RetroInfer. A systematic evaluation should include prefill, index construction, periodic updates, and decoding across different prompt lengths, generation lengths, and concurrency levels. Such results are necessary to determine when decoding savings amortize indexing overhead and translate into meaningful request-level gains.

W3: Limited evaluation across GPU platforms. All efficiency measurements are conducted on a single NVIDIA H20 GPU. Evaluations on additional GPUs, such as A100 and H100, would strengthen the generality of the efficiency claims.

W4: Insufficient analysis of indexing overhead and amortization. The paper reports an index-construction time of 0.84 seconds for Llama-3.1-8B at 128K on an H20, but does not systematically characterize this overhead across models and context lengths. The cost of periodic index updates during decoding is also not separately quantified. An amortization analysis across generation lengths would clarify when decoding savings outweigh construction and maintenance costs, yielding a net reduction in total request latency.

Questions for authors

As stated in weak points.

2 comments
AuthorsOpenReview ↗

Response to Reviewer MA4X

We thank Reviewer MA4X for your insightful comments. Below is our rebuttal content:

W1. Related systems. We ran the official RetroInfer, ShadowKV, ParisKV and Multipole Attention code on the same H20 and the same RULER prompts. RetroInfer in GPU-only mode is the only one that reaches the accuracy of full attention, so the table compares attention time against it at the same RULER threshold: PQ-HSA uses 109–117 µs per layer where RetroInfer uses 233–280 µs. The middle row uses the smallest tested budget in each sweep that scores at least 0.808, one percentage point below the full-attention reference of 0.818.

RULER targetPQ-HSA ρ, scorePQ-HSA (µs)RetroInfer cluster budget, scoreRetroInfer (µs)Attention speedup
About 0.800.25%, 0.8011090.6%, 0.7962332.1×
At least 0.8080.5%, 0.8451171.15%, 0.8162602.2×
RetroInfer's highest measured score0.5%, 0.8451171.8%, 0.8242802.4×

RetroInfer's middle row uses 1.15% of clusters on RULER and 1.3% on the timing prompt. At these settings the full decode step takes 17.0 ms in vLLM with PQ-HSA and 16.4 ms in RetroInfer. At roughly 1,450 exact tokens the five methods score as follows on the same 100 prompts:

Method (official code)Exact tokensRULERPQ-HSA lead [95% CI]Attention call (µs/layer)
PQ-HSA, ρ = 1%14430.849–133
RetroInfer, GPU-only, 1.15% of clusters14140.816+3.3 [0.5, 6.2]260
Multipole Attention, budget 124814580.773+7.6 [3.8, 11.7]317 (released kernel benchmark, synthetic tensors)
ParisKV, top-k 1%14430.762+8.7 [5.0, 12.7]570 (measured at top-k 0.25%)
ShadowKV, budget 104014560.613+23.6 [18.6, 28.7]–

ShadowKV exposes no separate attention timer; its decode step takes 20.7 ms against 25.7 ms for its dense baseline. ParisKV timings use its official code and its scores use our implementation of its ranking. For Multipole Attention we loaded Llama into the released Qwen2 class and verified identical logits on a 4096-token input.

In their released configurations, ParisKV uses 3 GB more GPU memory than its dense baseline (24.5–25.3 vs. 25.1 ms/token), and ShadowKV uses 13.3 GB less (24.8–25.0 vs. 25.7 ms/token). GPU-only RetroInfer peaks at 32.0 GiB on the GPU and 17.9 GiB on the host. vLLM preallocates its KV pool (79.5 GiB allocated after loading). At 126K the PQ-HSA index adds 2.7 GiB, or 4.9 GiB with a checkpoint for prefix reuse. We measured native allocations without a common memory cap.

W2 and W4. Cold requests and index costs. The request-level table is in the general response under "End-to-end latency": a cold 126K request with 4096 output tokens takes 118.4 s against 133.0 s for dense (1.12×), and 256K and 384K give 1.21× and 1.20×. The index costs are:

  • Construction runs once per prompt at the first decode step and takes 2.1 / 2.7 / 3.3 / 4.2 / 5.2 s at 32K / 64K / 126K / 256K / 384K. It is recovered after about 820 output tokens at 126K, about 300 at 256K and fewer than 256 at 384K. In a multi-turn session it is paid once.
  • Updates run every 256 output tokens and cost 4.9 ms per layer at 126K, which is 0.55 ms per generated token (0.28 at 32K, 1.31 at 384K). All request times above include them.
  • Memory. The index adds 2.7 GiB at 126K, next to 15.4 GB for the KV cache.

At 126K, outputs of 256 and 1024 tokens take 50.8 and 64.8 s (dense 48.8 and 65.5 s). GPU-only RetroInfer at 1.3% reports 129.4 s for 4096 outputs, including clustering and starting after cache allocation. The submitted index at its 1% budget takes 137.0 s against 133.1 s for dense.

W3. H200. The H200 and the H20 belong to the same GPU generation, and the cost of a PQ-HSA attention call is mostly fixed per call, so it is nearly the same on both: about 130 µs on the H200 and 117 µs on the H20 at 130K. Dense attention is bound by memory bandwidth and runs 2.3× faster on the H200 (145 µs against 341 µs). In decode throughput the break-even prompt length moves from about 64K on the H20 to about 192K on the H200, and whole requests with 4096 output tokens are faster than dense from 256K to 512K.

Prompt length on the H200 (ρ = 0.5%)126K192K256K384K512K
Decode throughput, PQ-HSA / dense0.88×1.01×1.13×1.27×1.42×
Request speedup, 4096 output tokens0.87×0.97×1.03×1.09×1.12×

A single run at 640K gave 1.02×.

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

AuthorsOpenReview ↗

To Reviewer MA4X

Thank you again for your review. We’ve added attention latency measurements and downstream results to our response. If you have a chance before discussion closes, we’d appreciate hearing whether these results address your concerns.

Comments on the paper

2 comments
AuthorsOpenReview ↗

# PQ-HSA (submission 56525): author response

General response

At 128K context on one H20, PQ-HSA takes 117 µs per layer for decoding attention, down from 341 µs with vLLM's FlashAttention (2.9× at ρ = 0.5%). With nearly identical retrieval budgets, PQ-HSA scores 0.845 on RULER (787 tokens receiving exact attention) and GPU-only RetroInfer scores 0.796 (785 tokens). The paired gain is 4.9 percentage points [1.7, 8.2]. RetroInfer takes 233 µs per layer at this budget.

Retrieval budget ρExact tokensPQ-HSA (µs/layer)FlashAttention (µs/layer)Attention speedupRULER
0.125%296993343.4×0.788
0.25%4601093343.1×0.801
0.5%7871173412.9×0.845
1%14431333342.5×0.849

We timed one attention call on a 130,400-token prompt with Llama-3.1-8B-Instruct, batch size one. RULER scores are macro-averages over five 128K tasks with 20 prompts each. Full attention scores 0.818. Brackets give paired 95% bootstrap intervals for score differences.

What PQ-HSA is. PQ-HSA is a hybrid of sparse and approximate attention built on a single retrieval pass. One IVF-PQ scan gives an estimated logit for every cached token. The top-k tokens by that estimate receive exact attention. Every other token stays in the same softmax with its estimated logit, summed per index list and paired with the list's mean value (Eq. 5). Selection and approximation share one scan and one set of scores, and each covers the other's weak point: exact attention removes the quantization error where the weights are largest, and the background estimates the 10.7% of attention mass that top-k truncation drops at ρ = 1% (estimated as 8.8%). Selection-only methods such as PQCache compute the same scores and discard them after ranking. Keeping them lowers the relative error of the attention output from 0.103 to 0.029 and, with the selector held fixed, raises RULER by 12.0 points [9.1, 15.0] (Fig. 4).

Index improvements since the submission. Equation (5) is unchanged. Since the submission we have kept optimizing the index underneath it, in three incremental steps at the same four code bytes per token:

  • a four-stage residual quantizer trained under the second moment of the queries replaces 8 × 4-bit PQ (relative output error 0.061 → 0.029 at ρ = 1%);
  • a sampled threshold replaces the exact top-k sort;
  • the four query heads of a GQA group share one scan, and each head keeps its own background weights.

With these changes the attention speedup at 128K rises from the paper's 1.58× to 2.5–3.4× and RULER multi-key accuracy at ρ = 1% rises from 0.84 to 0.96 (full attention: 0.96). The index builds in 3.2 s at 126K. The table above and the numbers below use this index unless a row says "submitted index".

Index configuration (128K, H20)ρPQ-HSA (µs/layer)Attention speedupRULER
Submitted IVF-PQ1%2101.6×0.825
Revised, one scan per head0.25% / 0.5% / 1%112 / 127 / 1433.0× / 2.6× / 2.3×0.806 / 0.810 / 0.826
Revised, one scan per GQA group (default)0.25% / 0.5% / 1%109 / 117 / 1333.1× / 2.9× / 2.5×0.801 / 0.845 / 0.849
Default with codebooks trained for 10 iterations0.25% / 0.5% / 1%101 / 115 / 1303.4× / 3.0× / 2.6×0.841 / 0.851 / 0.861

The last row takes 18 s to build instead of 3.2 s and is more accurate: on these 100 prompts it scores 2.3 to 4.3 points above full attention (0.818), and at ρ = 1% the paired interval lies above zero ([+1.9, +7.1]).

Correction to Table 1. The submission's evaluation code fed the final prompt token twice. With a single feed, the six-task InfiniteBench means are 64.8 for full attention, 60.3 for the submitted index and 59.8 for the revised index at ρ = 1%. The submitted index trails full attention by 4.5 points (Table 1 reported 0.9). The corrected LongBench means are 47.6 for full attention and 47.3 for the revised index.

Related systems, index costs and the H200 are under Reviewer MA4X. The mechanism, its novelty and per-task results are under Reviewer MrXd. Estimate quality, updates and other quantizers are under Reviewer 5X5j. Request-level times follow in the second part of this general response.

AuthorsOpenReview ↗

# PQ-HSA (submission 56525): author response #2

End-to-end latency

PQ-HSA replaces the attention operator and leaves the FFN and the rest of vLLM as they are. Attention is 48% of a dense decode step at 128K and a larger share at longer prompts, so the gain in decode throughput grows with the prompt length. Each request below starts from a fresh prompt and generates 4096 tokens on one H20 at ρ = 0.5%. Request times include prefill, index construction and an index update every 256 output tokens. We use Llama-3.1-8B-Instruct through 126K and Llama-3-8B-Instruct-Gradient-1048k at 256K and 384K.

Prompt length32K64K126K256K384K
Decode throughput, PQ-HSA / dense0.90×1.04×1.26×1.66×2.01×
Dense / PQ-HSA request (s)64.3 / 72.584.3 / 84.2133.0 / 118.4283.4 / 234.2492.3 / 409.1
Request speedup0.89×1.00×1.12×1.21×1.20×
Index build (s)2.12.73.34.25.2
Output tokens to recover the build costNo crossover~4070~820~300<256

Time to first token is the same with either method, because the index is built from the finished KV cache. With concurrent requests the whole-batch request speedups are 1.20× for 4 × 64K, 1.48× for 2 × 126K and 0.76× for 8 × 32K, and the decode throughput ratios are 1.39× for 4 × 64K, 1.98× for 2 × 126K, 1.44× for 3 × 126K and 2.57× for 2 × 192K (request speedup 1.55×). At 448K (ρ = 0.25%) a single request decodes 2.10× faster and finishes 1.18× sooner. Reusing one 126K document across turns at ρ = 0.25% takes 4.68 s per 256-token follow-up against 5.69 s for dense (1.22×).

The per-token advantage widens with the prompt length. The table gives the whole decode step in ms per token for a single request, PQ-HSA in vLLM at ρ = 0.25% with index updates included and the official GPU-only RetroInfer code in its own loop:

Prompt length64K126–130K256K384K
Dense (vLLM)17.022.032.842.7
PQ-HSA16.517.119.721.0
RetroInfer, 1.8% of clusters (released)15.317.320.424.8
RetroInfer, 1.3% of clusters14.716.419.523.3
RetroInfer, 0.31% of clusters14.115.417.720.4

From 64K to 384K the PQ-HSA step grows by 4.5 ms, the RetroInfer step by 6.2–9.5 ms and the dense step by 25.7 ms.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.