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

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 $17.54$ to $10.38$ at a retained budget of $2048$ keys; clustering dominates leverage-score selection at tight budgets ($10.30$ vs. $13.45$ at $512$ keys) and converges to it as the budget grows. In ViT-Large it retains \verb|98.4%| of base accuracy at $128$ keys per head. Theoretically, we show that the importance measure matched to degree-$r$ polynomial attention is the ${\ell }_r$ sensitivity-and that Minkowski-$r$ clustering recovers the top-${\ell }_r$-sensitivity keys under a planted-subspace model.