acceptodds
Under review as a conference paper at ICLR 2027

Efficient Attention via Pre-Scoring: Prioritizing Informative Keys in Transformers

Abstract

Efficient attention methods restrict which key-query pairs are evaluated, but the rules they use are query-dependent and data-independent: HyperAttention hashes queries and keys with angular locality-sensitive hashing, then estimates everything outside the resulting blocks by sampling residual columns uniformly. We replace that uniform proposal with a query-independent, data-dependent prior over keys, ranked once per layer by clustering or leverage-style scoring. We bound the resulting output error as a tail-mass bias plus a variance term linear in the retained budget, which predicts the interior optimum we observe. On ChatGLM3-6B-32k with LongBench, pre-scoring reduces perplexity from to at a retained budget of keys; clustering dominates leverage-score selection at tight budgets ( vs. at keys) and converges to it as the budget grows. In ViT-Large it retains \verb|98.4%| of base accuracy at keys per head. Theoretically, we show that the importance measure matched to degree- polynomial attention is the sensitivity-and that Minkowski- clustering recovers the top--sensitivity keys under a planted-subspace model.

Primary area:
optimization
Keywords:
Machine Learning, Transformer, Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_9UWnOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes adding a pre-scoring step before HyperAttention, using k-means, k-median, or leverage scores to select a subset of important keys before attention is computed. The authors provide a planted-model analysis showing that clustering can recover the same heavy keys as leverage scores, and evaluate the method on long-context perplexity with ChatGLM2/3-6B-32k and on pretrained Vision Transformers on ImageNet.

Critical strengths

The Idea of the paper sounds exciting and practical, and the paper is easy to follow.

Critical weaknesses
  1. The headline claim that pre-scoring reduces perplexity from 12 to 8.3 is not supported. Appendix A.1 states that the 8.3 result is obtained with pre-scoring turned off and comes from the min-seq-len setting. In Tables 2–4, plain HyperAttention without residual sampling already reaches 10.41, which matches or beats nearly every pre-scored configuration.

  2. The GLM2 results come from code that Appendix F says had three bugs, yet they are still used in the abstract and main text.

  3. GLM3 results are shown only as a plot, with no table or runtime, and the gains are modest.

  4. In the forward-only test (Fig. 1), HyperAttention reaches about 13.5× over FlashAttention at 131K tokens, while the pre-scored variants reach only about 3–5×. Pre-scoring therefore makes HyperAttention roughly 3× slower, yet the text describes it as giving “a mild acceleration.”

  5. The ViT comparison is not apples to apples. The K-means results use pretrained ViTs, while the LevAttention numbers come from models trained from scratch with a lower baseline. Relative to their own baselines, both keep about 98% accuracy.

  6. The experimental scope is narrow. Important related work on clustering-based attention (e.g., Routing Transformer, clustered attention) is neither discussed nor compared against, and there are no LongBench task scores. The abstract also mentions a 131K context while both models are 32K.

Minor: the presentation needs polish (Figures and tables are not in a good shape), and the header still says ICLR 2026.

I do not think the paper is ready for acceptance in its current form, and I recommend strong rejection. The central empirical claims are not adequately supported, particularly the attribution of the reported gains to pre scoring.

Questions for authors

Please see Weaknesses section.

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

This paper proposes a modified version of HyperAttention that chooses important keys first, which are chosen by k-means or k-median clustering, or leverage score ranking. The motivation is to reduce the computational cost while not losing important information. The work analyses the filtering approach under a specific model, and evaluates the method in the experiments using ChatGLM2/3 and ViT.

Critical strengths
  1. Motivation is kind of intuitive. Choosing a subset of keys can reduce computational cost, but the paper chooses them based on the importance of the keys themselves.
  2. The paper reports the performance in language modeling and image classification, which is kind of diverse.
Critical weaknesses
  1. The advantage of pre-scoring is unclear. The perplexity of 8.3 in the Abstract comes from the configuration of disabling pre-scoring. Single-layer speedup is not enough to prove end-to-end speedup.
  2. The references and experiments are outdated. The LLM experiments only use ChatGLM2/3, and baselines such as MInference and FlexPrefill are missing, which makes it very hard to see whether this method is competitive. The presentation also makes the paper very hard to read. Some technical terms are not clearly explained.
Questions for authors

When other configurations and settings are kept the same, how much would the perplexity and end-to-end latency improve by adding pre-scoring?

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

The paper proposes a pre-scoring stage that ranks keys (via k-means, kernel k-means, k-median, or leverage scores) and retains only a subset of “informative” keys before running HyperAttention. Uniform residual sampling is replaced by this content-aware selection.Theoretical analysis under a planted-subspace model claims that clustering recovers the same heavy keys as leverage-score thresholding. Empirically, the method is tested on ChatGLM2/3 (LongBench perplexity) and monkey-patched ViTs (ImageNet). Headline claims include a perplexity drop from 12 to 8.3 and substantial speed-ups over FlashAttention.

Critical strengths
  • Simple, practical hybrid design: inserting a lightweight clustering or leverage pre-filter before HyperAttention is a natural way to improve coverage of important keys while preserving sub-quadratic scaling.

  • Transparent handling of implementation issues: the authors document and partially correct earlier bugs (zeroed K/V tensors, residual double-counting) when moving from GLM2 to GLM3, which increases confidence in the remaining results.

Critical weaknesses
  • Headline gains appear misattributed. The strongest reported perplexity (≈8.3) is obtained in a configuration where pre-scoring is effectively deactivated (Appendix A.1); under the exact setting described in the abstract, pre-scoring either hurts or yields no improvement over plain HyperAttention. Several GLM2 numbers further rely on an implementation the authors themselves later call buggy.

  • Theory and empirical claims are weakly supported. The planted-model analysis contains internal inconsistencies (normalization of noise rows, leverage lower bounds, mismatched cluster counts) and applies only to polynomial attention, while all experiments use softmax. Speed figures largely inherit HyperAttention’s gains; once pre-scoring cost is included the variants are often slower. ViT comparisons are not matched, and strong random / top-norm / oracle baselines are missing.

  • Limited novelty and incomplete baseline comparison. Pre-filtering keys by importance before an approximate attention method is incremental; LevAttention already selects high-leverage keys and HyperAttention already supplies the LSH machinery. Strong contemporary long-context baselines (Quest, H2O, StreamingLLM, MInference, DuoAttention, etc.) are absent, leaving the incremental value of the proposed combination unclear.

  • Reproducibility and experimental transparency gaps. Critical details (exact evaluation set and lengths, which layers are replaced, cluster count, k-means iterations, noise scale σ\sigma, fallback threshold) are missing or only partially reported. Code is promised but unavailable to reviewers, and several claims (e.g., exponential perplexity scaling, “denoising” effect) lack supporting evidence.

Questions for authors
  1. What perplexity do GLM2 and GLM3 achieve against HyperAttention with sample_size=0 and identical min_seq_len, both with and without pre-scoring?

  2. What exact configuration produces the baseline “perplexity = 12”?

  3. How do random-key, top-norm, and oracle-attention selection compare at the same retained set size ss?

  4. Can the planted-model theorems be repaired for unit-norm noise rows, and can σmin⁡2=Θ(1/ε)\sigma_{\min}^2 = \Theta(1/\varepsilon) be reconciled with the Ω(n/d)\Omega(n/d) lower bound induced by those rows?

  5. What are end-to-end forward and forward+backward wall-clock times that include the full cost of k-means (or leverage) pre-scoring, at matched ss?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.