acceptodds
Under review as a conference paper at ICLR 2027

SIEVE: Estimate-Aware Clustering in the Query-Induced Space for Sparse Attention

Abstract

Sparse attention uses only a small part of the KV cache at each decoding step, while cluster-based indices rank and estimate groups of keys through their centroids. Existing methods cluster keys by angular similarity, even though attention depends on the inner products between keys and decoding queries. Keys that are close in angle can therefore induce very different logits, causing important keys to be diluted in both retrieval and estimation. We introduce **SIEVE**, which clusters keys in the score space induced by the query distribution. Its objective minimizes residual logit error under a robust query-induced metric and places additional weight on keys that are likely to become important retrieval targets. We show that this objective controls errors in attention estimation. Across long-context and long-reasoning benchmarks, SIEVE outperforms training-free sparse-attention baselines at equal budget and remains close to full attention while using only a small fraction of the KV cache.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, KV cache, long-context inference, vector quantization, maximum inner product search

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_bmKpOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SIEVE, a training-free clustering method for sparse attention. It combines a robust query-induced metric with retrieval-target-aware weighting to improve cluster-based retrieval and estimation. The authors derive cluster-level estimation-error bounds and evaluate the method on RULER, LongBench, AIME-25, and GPQA Diamond.

Critical strengths
  1. Well-motivated methodology. Section 4.1 and Appendix D identify and empirically characterize the mismatch between angular similarity and attention-logit geometry. Designing clusters around query-dependent errors is a meaningful contribution to retrieval and estimation.
  2. Controlled comparisons and informative ablations. The shared evaluation framework and matched retrieval budgets support comparisons with RetroInfer. Table 14 further shows that adding the target-aware term reduces the reported estimation-zone numerator error from 59.8 to 43.1 while improving task accuracy.
Critical weaknesses
  1. Limited connection between the theoretical bounds and final attention-output error. Appendix A.2 correctly extends Proposition 4.4 to non-mean centroids, with Equations (5)–(6) remaining valid and an additional first-order term in the log-mass ratio. However, Equation (6) alone does not control the query-dependent exponential factors retained in the estimation bounds. Table 14 reports estimation-zone numerator error, leaving the corresponding effect on the final normalized attention output insufficiently characterized.
  2. Modest aggregate gains and limited evidence of robustness. The macro-average gains over RetroInfer are modest on RULER (0.8–1.9 points) and LongBench (0.3–0.5 points), although Table 2 shows larger gains on some challenging RULER subtasks. Table 19 indicates comparable decoding speed and peak memory. The practical benefit therefore rests primarily on improved quality, but the stochastic reasoning gains lack uncertainty estimates and their attribution to the target-aware component remains unclear.
Questions for authors
  1. Can the authors compare robust-metric-only clustering with full SIEVE on identical queries and KV states, reporting signed relative estimation-zone mass error and relative L2 error of the final attention output?
  2. What motivates omitting target-aware weighting for newly generated keys? Please assess its contribution to reasoning by disabling it for the prefill index while keeping online indexing unchanged. Separately, please report paired, problem-level confidence intervals for the SIEVE–RetroInfer score differences.
Reviewer_4MdXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies sparse attention with a KV cache offloaded to the CPU. It addresses the problem that cluster means may fail to represent high-scoring keys, affecting both retrieval and estimates of the contributions from clusters that are not retrieved. SIEVE estimates second moments from prefill queries, clusters keys using a query-based metric with ridge regularization, and protects potential retrieval targets through an importance-gated directional penalty and corresponding centroid updates. It retains the existing cluster retrieval and estimation procedures. In the reported RULER settings, it outperforms sparse baselines, while on LongBench it largely maintains full-attention performance. The paper also reports results on AIME-25 and GPQA Diamond, along with component ablations.

Critical strengths
  1. Proposes a clustering method that supports both retrieval of important tokens and estimation of cluster contributions. SIEVE uses prefill queries to estimate the attention score error caused by replacing individual keys with representative vectors, and groups keys accordingly. Regularization prevents grouping from relying too heavily on a limited query sample. The method then adds a directional penalty for keys likely to receive high scores and derives corresponding updates to the representative vectors. By adjusting both the groups and their representatives, it reduces the dilution of important keys through averaging while also supporting estimates of the contributions from groups that are not retrieved.
  2. Links representation error from clustering to attention estimation error. The authors show that even keys with similar directions can receive very different scores under the same query. Representing an entire group by a single mean can therefore miss important tokens and misestimate the group's attention contribution when it is not retrieved. The paper further derives error bounds for cluster contribution estimates based on the score differences between keys and their representative vectors. This provides an analytical basis for designing a clustering objective around attention score error.
Critical weaknesses
  1. The sources of the gains from the target term have not been fully separated. In Section 5.3 and Table 14 in Appendix H, the first four variants all use mean centroids, so they already test the effects of changing the grouping method. However, the final step adds the target term and changes both token assignments and representative vectors. A comparison that fixes the preceding partition and updates only the representative vectors using Equation (8) is missing. It therefore remains unclear how much of this step's gain comes from adjusting the representatives and how much extra benefit comes from reassigning tokens.
  2. Simplified grouping and the applicability of query moments during long reasoning need targeted validation. Appendix C states that tokens newly added to the index during generation use only the first term of Equation (7), omitting the target term. Table 3 supports the effectiveness of the overall strategy on the tested reasoning tasks, but does not isolate how omitting the target term affects quality and update cost. Appendix E reports reasoning prompts of only 58–215 tokens, with a generation limit of 32,768 tokens, making the treatment of newly generated tokens worth evaluating separately. In addition, Table 4 in Appendix B validates the moment estimates on RULER, but does not show the prediction error of the initial query moments at different stages of long reasoning.
Questions for authors
  1. If the partition before adding the target term in Table 14 is fixed and only the representative vectors are updated using Equation (8), how do task performance and estimation error compare with full SIEVE? Can this comparison establish the extra benefit of reassigning tokens?
  2. For tokens newly added to the index during generation, how do quality and update cost differ with and without the target term? How does the prediction error of the query moments estimated from prefill change across the early, middle, and late stages of generation?
  3. Are the quality differences on AIME and GPQA stable under repeated sampling? Were parameters selected using samples independent of the final evaluation?
  4. Appendix J already compares prefill, decoding, and GPU memory use at 128K. With the same hardware and input length, how does the end-to-end request runtime of SIEVE and RetroInfer vary with generation length when periodic index updates are included?
Reviewer_zukLOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces a method called SIEVE to improve training-free sparse attention by changing how the KV-cache index is built. Existing cluster-based methods (e.g ClusterKV, RetroInfer) partition keys with angular distance, which can dilute high-logit keys. SIEVE instead clusters in a query-induced logit space using a ridge-whitened second-moment metric of recent prefill queries, plus a target-aware reweighting term that protects keys likely to be important retrieval targets.The index is constructed only at prefill / flush time, so decode-time retrieval and estimation engines remain unchanged. Evaluations on RULER (up to 128 K), LongBench, AIME-25 and GPQA-Diamond with several 4 B–8 B models show consistent gains over prior sparse methods while staying close to full attention.

Critical strengths
  1. Principled formulation that directly targets key dilution: the robust query-induced metric and target-aware terms are derived from logit-error bounds and give a concrete geometric explanation for why angular clustering fails on hard retrieval tasks. This is consequential because it moves sparse-attention indexing from pure heuristics toward a well-motivated objective.

  2. Clean systems design: only the offline index construction is modified, so the method plugs into existing sparse-attention kernels with zero decode-time overhead. Combined with solid empirical coverage across synthetic, document and reasoning benchmarks, this makes the gains immediately usable.

Critical weaknesses

Some weaknesses are as follows:

  1. Potential information leakage from question tokens: Σ\Sigma and μ\mu are estimated from the last 100 prefill queries, which on RULER/LongBench include the question itself. This confounds geometry with extra task information that the baselines do not receive, and would require re-indexing for every new query in a realistic long-context serving setting.

  2. Statistical support is thin and several claims sit inside noise: reasoning results use few samples per problem (large binomial SE), many reported margins are 0.1–0.5 points, hyperparameters appear tuned on evaluation tasks, and the effective metric at the chosen ridge is close to Euclidean plus a mild rank-1 boost. The theory bounds the mean-centroid objective but does not tightly control ranking failure or signed estimation bias of the final SIEVE centroids.

  3. Limited practical scope and missing strong baselines: experiments are confined to 4B–8B GQA models with no MLA variants, long-generation behavior, or measured in-decode re-clustering cost. Closest prior work (ClusterKV) and natural query-informed competitors (Expected-Attention / SnapKV-style pinning given the same information) are not compared, leaving the true incremental gain over existing sparse-attention techniques unclear.

Questions for authors
  1. Do the gains remain when Σ\Sigma and μ\mu are estimated only from document tokens (or from an offline calibration set) that exclude the question?

  2. How different is the SIEVE partition from ordinary Euclidean kk-means at the chosen ρ=10\rho=10, and what do ρ\rho / γ\gamma sweeps look like on held-out tasks?

  3. What are the results on reasoning benchmarks with ≥16 samples per problem, confidence intervals, and a paired test? How much does the target term actually fire, and how much does Σ\Sigma drift, over long generations?

  4. What is the signed estimation bias (and mass-overestimation rate) of the SIEVE centroids relative to the true attention mass?

  5. On a realistic serving workload where a long context is indexed once and then many different questions arrive later, how often must the index be rebuilt, and what is the resulting end-to-end latency overhead compared with methods that never use question tokens?

  6. Does SIEVE still outperform strong cache-matched or query-informed baselines (ClusterKV, Expected-Attention-style pinning, or SnapKV-style token selection given the same prefill information) when those baselines are also allowed access to the same query statistics?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.