acceptodds
Under review as a conference paper at ICLR 2027

QKSieve: Query-Key Balanced Mixed-Bit Retrieval for Efficient Long-Context Attention

Abstract

Autoregressive decoding repeatedly scans the complete key-value (KV) history. Query-aware sparse attention helps only when selection is cheaper than dense QK scoring and faithful to joint Query-Key geometry. We present QKSieve, a training-free, GPU-resident exact-KV retrieval method. Request-local Query and Key second moments define biorthogonal coordinates that preserve every unquantized dot product and order dimensions by joint score energy. A per-layer, per-head allocator assigns 0/1/2/4/8 bits to eight 16-D bands under a 240-bit token/head budget by minimizing a separable logit-MSE surrogate. The packed index targets B(N) = minN, 1280, max(256, ceil(0.06N)) positions, after which the original 16-bit K/V receive exact sparse attention. No learned router, exact-QK reranking, task rule, or dense fallback is used. QKSieve-Robust adds a current-Query rank-16 INT4 estimate of the omitted softmax partition and Value numerator, bringing total auxiliary storage to 7.47%. On complete LongBench, Robust retains 99.98%, 99.73%, and 100.00% of Full macro score on Llama-3.1-8B, Qwen3-4B, and Mistral-7B while targeting 6.85-7.43% of history. Across 13 RULER tasks from 4K to 128K, it retains 100.33% on average with 4.97% measured active attention. In a controlled native-MHA RTX 3090 implementation, the complete Robust attention path is 2.09-4.12x faster at 32K-128K, and real steady decode is 1.32-3.98x faster. We separately report index construction and persistent-cache break-even rather than hiding fixed cost in steady-state timing. Analysis connects representation error to ranking margins, omitted probability mass, and attention-output error.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, KV cache retrieval, mixed-bit quantization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_P6HzOpenReview ↗
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

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 ee, its unscaled attention score has error q⊤eq^\top e for the current query qq. 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.

  • At 32K history, FIER takes 0.4647, Quant 0.2324 and Robust 0.2945 ms per complete attention call.
  • At 128K history, FIER takes 1.3322, Quant 0.3722 and Robust 0.5757 ms per complete attention call.

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.

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.

Reviewer_iTkgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

QKSieve tackles the cost of autoregressive decoding, where every step must scan the full key–value history. Its core idea is to make selection cheap enough that sparse attention actually pays off, while keeping the selected attention computation exact. Instead of learning a router or approximating QK scores, it builds a retrieval index from request-local second-moment statistics of Queries and Keys.

Critical strengths
  • Comprehensive collection of experiments are provided.
  • It is a great idea to optimize on the selection of KV-caches.
Critical weaknesses
  • Writing. The logic flow of this manuscript is not smooth. For example in Section 3. The equations appears without introduction.
  • Is the basic idea to pick a cheap enough representation that can optimize decode? It is not clear how this connect to the algorithm design. I am not clear why section 3.1 is needed.
  • The algorithm is not clear enough. An introduction and pseudo code are recommended.
Questions for authors
  • Please redraw Figure 1.
  • What's the definition of F\mathcal{F} in Equation 4?
  • Please carefully review your TeX file. The current formatting differs significantly from other manuscripts I have reviewed.
  • Scores will be adjusted according to rebuttal.
1 comment

Thank you for pointing to Section 3.1 in particular. The missing link in our explanation was how a cheaper key representation leads to a useful decision about which cache entries to read. We rewrote the opening of Section 3 around that decision.

Why Section 3.1 comes before bit allocation

Let e=k−k^e=k-\hat{k} be the reconstruction error of a cached key. For the current query qq, the error in its unscaled retrieval score is q⊤eq^\top e. An error aligned with a common query direction can move an important token below the selection threshold. An equally large error in a direction that queries seldom use has less effect on the score. Figure 2(a) gives a concrete example. With query second moment diag⁡(4,1)\operatorname{diag}(4,1), unit key errors along the two axes have expected squared score errors of 4 and 1.

Section 3.1 uses sampled prompt queries and keys to build paired transforms for each layer and KV head. The transforms satisfy AD⊤=IAD^\top=I, so q′=A⊤qq'=A^\top q and k′=D⊤kk'=D^\top k preserve every dot product before quantization (Eq. 8). Their regularized second moments share a diagonal that orders the coordinates by joint score energy (Eq. 9). Section 3.2 then measures the score error incurred by each bit width in each group of coordinates. For example, three 4-bit bands use 192 coefficient bits plus 48 scale bits, exactly filling the 240-bit budget. The alternative 4/4/2/1 layout can represent another band at the same total cost. The measured score errors determine which one to store.

How one request runs

The redrawn Figure 1 (p. 2) follows one request. Panel A shows what is built once after prefill, panel B shows the Quant decode step, and panel C shows the extra work for Robust. Algorithm 1 (p. 6) gives the execution order.

  1. After prefill, estimate prompt moments, build the transforms, choose the bit widths and pack the keys. Robust also fits a value basis and stores a compact code per token. The original keys and values remain on the GPU.
  2. For each new query, estimate a threshold from a sample of packed scores. One scan of the packed index produces candidate token IDs. During this same scan, Robust also accumulates proxy softmax weights and weighted value codes for omitted tokens.
  3. On the retrieved IDs, read the original keys and values and recompute attention scores exactly. Quant normalizes over those IDs. Robust combines the exact selected numerator and partition with its estimates for omitted tokens. As the cache grows, new entries use the transforms fitted at prefill.

Thus the retrieval scores are approximate. Exact computation applies to attention restricted to the selected original entries. Figure 1 now makes both operations visible.

The operator in the submitted Eq. (4)

F\mathcal F is an eigenvalue-flooring operator. For a symmetric matrix X=Rdiag⁡(λi)R⊤X=R\operatorname{diag}(\lambda_i)R^\top, the revised Eq. (4) defines

\mathcal F(X)=R\operatorname{diag}\bigl(\max(\lambda_i,\tau(X))\bigr)R^\top .$$ It keeps the eigenvectors and raises every eigenvalue below $\tau(X)$ to that floor. Equation (5) applies it to the empirical key second moment and to the query second moment after shrinkage. With few calibration samples the raw moments can be rank deficient. Flooring makes the matrices positive definite so the inverse square roots in Eq. (7) exist. ### TeX and readability We checked the style files against the official ICLR 2027 template, corrected the text-font fallback, and recompiled the anonymous PDF. The introduction to Section 3 now precedes the derivation, the operator is defined before use, and the conclusion ends on page 10 of the discussion version.
Reviewer_kw7uOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents QKSieve, a query–key balanced mixed-bit retrieval framework for accelerating long-context attention during autoregressive decoding. QKSieve focuses on preserving query–key attention scores, which are more directly related to the retrieval quality required by sparse attention. It first constructs a biorthogonal coordinate system based on query and key statistics, then divides the transformed key representation into multiple bands and assigns different quantization precisions under a fixed storage budget. The paper further introduces a packed CUDA retrieval procedure based on sampled-quantile thresholding and a Robust variant that uses a low-rank quantized ValueSketch to estimate the contribution of omitted tokens. The paper evaluates QKSieve on LongBench and RULER and reports retrieval, latency, and storage results across different context lengths and attention configurations.

Critical strengths
  1. The method optimizes a more relevant objective than conventional key reconstruction. A key strength is the focus on query–key score distortion rather than key reconstruction error alone. Since attention retrieval depends on the interaction between queries and keys, minimizing key-side reconstruction error does not necessarily preserve the ranking of attention scores. QKSieve explicitly incorporates query statistics into its quantization objective, making its bit allocation strategy better aligned with the downstream retrieval task. This is a meaningful design choice and provides a principled motivation for the proposed mixed-bit quantization.
  2. The paper considers the practical retrieval pipeline. The packed CUDA retrieval procedure and the integration with exact attention over selected original K/V entries demonstrate attention to actual decoding efficiency. The paper also investigates the omitted-value problem through the Robust variant. The combination of representation design, retrieval implementation, and system-level evaluation is valuable for practical long-context inference.
Critical weaknesses
  1. The experimental presentation does not provide a sufficiently balanced comparison between Quant and Robust. The paper emphasizes the computational efficiency of Quant while primarily highlighting the downstream quality results of Robust. However, these results leave two important questions insufficiently answered: how much downstream quality does Quant achieve without the omitted-value correction, and how much additional computational overhead does Robust introduce to obtain its quality improvements? Although the appendix provides latency comparisons between the two variants, the main experimental narrative does not present a sufficiently unified quality–efficiency trade-off. In particular, a direct comparison of Quant and Robust under the same models, datasets, context lengths, and evaluation settings is needed to establish whether the additional ValueSketch computation is justified by the resulting quality gains. This is consequential because the practical value of Robust depends precisely on this trade-off, while the effectiveness of the simpler Quant variant should be independently established.
  2. The novelty of the central score-aware principle is not sufficiently distinguished from prior work. The idea of optimizing an index to preserve query–key attention scores, rather than merely minimizing key reconstruction error, is not introduced for the first time in this paper. Prior work such as SAKI has already studied score-aware key indexing using query and key statistics, with an explicit objective for preserving attention-score fidelity. Therefore, the broad motivation of moving from key reconstruction to score-aware indexing should not itself be treated as a novel contribution. QKSieve does provide additional contributions, particularly its mixed-bit allocation strategy, packed retrieval implementation, and omitted-value correction. However, the paper should more precisely articulate which aspects are fundamentally new beyond the existing score-aware indexing formulation, and provide a clearer comparison with closely related work.
Questions for authors
  1. Could the authors provide a direct, controlled comparison of Quant and Robust on the same models, datasets, and context lengths, reporting both downstream quality metrics (e.g., LongBench and RULER) and latency? In particular, how much quality does Quant retain relative to full attention, and what is the incremental quality improvement obtained by Robust for its additional computational cost?
  2. Could the authors quantify the overhead introduced specifically by the ValueSketch and omitted-value estimation components, relative to Quant, across different context lengths and attention configurations? How does this overhead affect end-to-end decoding latency, especially in GQA settings where the ValueSketch appears to be a significant bottleneck?
  3. How do the authors distinguish the QK-balanced coordinate construction and score-distortion objective from the score-aware indexing formulation in SAKI? More specifically, which mathematical or algorithmic components of QKSieve cannot be obtained from, or viewed as an extension of, existing score-aware low-rank indexing approaches? A more explicit comparison would help clarify the paper's conceptual novelty.
  4. How sensitive is the proposed mixed-bit allocation to the calibration query/key statistics and potential distribution shifts during decoding? An evaluation of allocation stability and retrieval quality under different calibration conditions would help establish the robustness of the proposed quantization strategy.
2 comments

Thank you for asking how much quality Quant preserves on its own and whether the extra work in Robust pays off. On the matched LongBench slice, mean retention across the three models is 99.9% for Quant and 100.3% for Robust. The observed difference depends on the model and the task.

Q1. Downstream quality at the same token budget

In Table 2 of the revised manuscript, Quant and Robust run on the same 160 LongBench prompts per model, ten from each of 16 tasks, with the same number of active tokens per prompt at a fixed 2% budget. Retention is the method's macro-average task score divided by the dense score on those same prompts, expressed as a percentage.

  • On Llama-3.1-8B, Quant retains 99.56% and Robust 100.34% (+0.78 percentage points).
  • On Qwen3-4B, Quant retains 98.39% and Robust 99.79% (+1.40 points).
  • On Mistral-7B, Quant retains 101.66% and Robust 100.77% (−0.89 points).

That average gain of about 0.4 points hides variation even within a model. Figure 4 shows all task-level differences. For example, Robust gains 5.50 native task-score points on Qwen's LCC task and loses 5.00 on Mistral's TriviaQA task. These runs recorded final task scores with per-step execution diagnostics disabled, so we interpret the differences at the configuration level. At the default budget, the full LongBench and RULER suites compare Robust with dense attention. A full-suite Quant score at that budget and deployment timings for those same benchmark generations remain unmeasured.

Q1–Q2. Quality and latency measured on the same inputs

Table 5 gives the closest direct test of whether the correction pays for itself. In a separate Llama-3.1-8B grouped-query attention (GQA) diagnostic we replayed the same three teacher-forced text streams, fixing the key index, the 512 quantile samples and the 1,280-candidate cap. We toggled only the omitted-value correction. Quality here is 100 times dense perplexity divided by the method's perplexity on the same target tokens. Timing is whole-model steady decode.

  • 32K history, one RTX 3090, 192 paired tokens. Turning the correction on changes retention from 98.58% to 100.52% and latency from 39.79 to 52.43 ms/token.
  • 96K history, two RTX 3090s, 96 paired tokens. Retention changes from 95.10% to 99.77% and latency from 52.62 to 68.33 ms/token.

The additional time is 12.64 and 15.71 ms/token, respectively. The point estimates favor the correction on these streams. At both lengths the paired token-bootstrap 95% interval for the mean NLL change includes zero, so the size of the quality gain remains uncertain.

Q2. How the cost changes with attention layout

In the native multi-head attention (MHA) test on one RTX 3090, Quant and Robust share the selector and exact sparse-attention consumer. Robust additionally accumulates omitted softmax weights and weighted value codes. Relative to Quant, its complete-attention latency increases by 17.6%, 26.7% and 54.7% at 8K, 32K and 128K, respectively (Table 4). For whole-model steady decoding the increases are 24.1%, 23.2% and 21.6% at 32K, 64K and 128K. At 64K this means 52.97 ms/token for Quant and 65.25 for Robust, versus 144.75 for dense decoding. These times exclude index construction. Figure 3 shows its effect on shorter generations.

On native Qwen3-4B GQA at 32K, four query heads share each key index but retain separate candidates and query-dependent tail weights. Robust takes 47.675 ms/token in steady decode versus 42.574 for dense, or 0.89× dense speed (Table 16). A separate component profile attributes 19.845 ms/token to ValueSketch and 4.446 to exact sparse attention. The former measures time spent in that stage. The net Robust-minus-Quant latency on this identical Qwen path remains unmeasured. The faster shared-candidate Llama prototype in Appendix H also changes the selector and budget, so it cannot isolate the cost of the Qwen tail. For this measured Qwen configuration, dense decoding is faster.

Q3. What QKSieve shares with SAKI and what the bit budget changes

We agree that optimizing an index for query–key scores is an idea we share with SAKI. SAKI already derives the covariance-weighted rank-constrained score objective and its SVD solution. With the same moment matrices, QKSieve's unquantized full-rank transform has the same algebraic endpoint as SAKI at full rank. Section 2 of the revision now credits this explicitly. SAKI-RoPE further averages query covariance over rotations. Zhang, SAKI-RoPE

Our design question starts once those coordinates have been chosen. Each layer and KV head must encode a key in at most 240 physical bits. Each of eight 16-dimensional bands may use 0, 1, 2, 4 or 8 bits per coefficient. Every active band also needs a 16-bit scale per token. Both of the following layouts occur in the 240 fits in Figure 2(b).

  • Three 4-bit bands use 192 coefficient bits and 48 scale bits.
  • Four bands at 4, 4, 2 and 1 bits use 176 coefficient bits and 64 scale bits.

Both fit exactly. The second layout trades precision in the third band for coverage of a fourth. To choose between them, we quantize sampled keys at each available width and measure the squared error this induces in the prompt-query scores for each band. We enumerate feasible layouts and minimize the sum of those measured errors (Eqs. 10–12). This optimization is exact for the stated within-band surrogate. Cross-band terms can affect the full score error. A choice of rank alone leaves this bit-allocation problem undetermined.

The resulting packed index is scanned to select token IDs for exact attention on the original keys and values. Robust additionally uses the current query to estimate the omitted softmax partition and value numerator. We view the mixed-bit allocation, the scan that consumes it and the optional correction as extensions of score-aware indexing. A speed or quality advantage over SAKI itself would require a matched implementation comparison that we have not measured.

Q4. Sensitivity to calibration and later queries

The deployed index is fitted once per request. Section 3.1 samples prompt keys at stride 32 and uses the last eight prompt query positions, pooling the query heads mapped to each KV head. The query second moment is shrunk because there are few query positions. In Appendix F and Figure 5, the Llama-3.1-8B reference audit ranks all proxy scores and takes the top 1,280 prompt keys. This isolates the representation from the deployed scan's sampled threshold.

  1. Varying the number of calibration queries. On the same 32K prompt-key histories, we evaluated both settings over the same 13 teacher-forced continuation positions. Calibrating with eight versus 32 prompt query positions gives 92.85% versus 93.32% recall of the exact top 2% of tokens. The retrieved tokens carry 86.55% versus 86.62% of dense attention mass. On these prompts, using four times as many calibration positions changes recall more than it changes retained mass.
  2. Keeping the index fixed through a continuation. We teacher-forced 4,096 continuation tokens for each of six text topics and evaluated retrieval against the original prompt keys. At the measured positions from 1K through 4K, recall is 88.76% and retained mass is 84.21%. Even choosing the best 1,280 prompt keys by exact scores captures 85.83% of mass. The paired gap is 1.62 percentage points (95% topic-cluster bootstrap interval 1.45–1.80). When we refit just the bit widths to later queries in the same coordinates, 82.66% of band choices agree with the frozen assignment. For the sampled within-band score-error surrogate, the mean ratio of frozen to locally optimized distortion is 1.072.

These measurements show a detectable loss under later queries and quantify the part that remains even with exact selection at the same budget. Because the keys are held fixed and the continuation is teacher-forced, shifts from newly generated keys, free-running generation and reuse across prompts remain open.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.