Skip to content
Preprint

Attend at the Right Resolution: Head-Adaptive Sparse Attention via Query-Key Interaction Structure

Nov 2026 · 0 citations · 29 references
Computer Science

TL;DR

The proposed Head-Adaptive Sparse Attention (HASA), a training-free sparse attention framework that jointly adapts selection resolution along these two dimensions, captures 88.1% of dense-attention mass and, compared with UNIQUE, improves accuracy and speedup over dense attention.

Abstract

Attention is a major scalability bottleneck in large language models (LLMs), with its computational cost and key-value (KV) memory traffic becoming increasingly prohibitive as context length grows. Sparse attention addresses this bottleneck by restricting each query to a subset of the context, but its effectiveness hinges on identifying relevant regions both cheaply and reliably. Existing training-free methods primarily rely on runtime relevance estimates, with selection dimensionality and granularity typically governed by fixed heuristics rather than the intrinsic interaction structure of pretrained attention heads. We take a different perspective: the query-key operator of each pretrained head defines a characteristic response structure that determines the resolution needed for sparse selection, both across feature directions and across context tokens. Building on this insight, we propose Head-Adaptive Sparse Attention (HASA), a training-free sparse attention framework that jointly adapts selection resolution along these two dimensions. Along the feature dimension, the singular spectrum of each head's query-key operator determines an effective rank, yielding a compact, head-specific response space. Along the sequence dimension, neighboring regions are progressively merged according to the directional coherence of their token responses in this same space, while heterogeneous regions remain separate. Exact attention is then computed using the original full-dimensional KV states of the selected regions. HASA captures 88.1% of dense-attention mass and, compared with UNIQUE, a strong recent sparse-attention baseline, improves accuracy by up to 3.47 and 2.57 points on RULER and LongBench-Pro, respectively, and accelerates self-attention by up to 1.32x, while achieving up to 14.07x speedup over dense attention.

View source

Similar papers

MoSAR: Mixture of Semantic Attention Regimes for Learning Adaptive and Approximable Attention Geometries

Mixture of Semantic Attention Regimes (MoSAR) is introduced, which learns such an adaptive, controlled-decay geometry over query--key interactions, suggesting that it is not only adaptive, but also amenable to low-cost approximation at inference time.

Michele Paolicelli, Alessandro Petruzzelli, Alessandro Francesco Maria Martina et al. · 0 citations

Retrieval Capacity of Self-Attention Under Competition

How many tokens from its context does a language model actually use, and what determines that number? We study this question through self-attention. Without retraining, we retain only the tokens with the highest attention weights at each head, layer, and query, keeping their original weights unchanged. By varying the s...

Timur Mudarisov, M. Burtsev, R. State · 0 citations
Preprint Nov 2026

ADIndex: Layer-Adaptive Sparse Attention Indexing via Group-Level Distillation

DeepSeek Sparse Attention (DSA) reduces the computational cost of attention through token-level selection. However, its indexer still scores the entire causal prefix for each query, making indexing a dominant source of latency in long-context inference. Notably, the indexer alone can account for more than 50% of total...

Jin-Fei Qi, Yi-Duo Li, Jiang-Xin Shi et al. · 0 citations
Preprint Nov 2026

AttentionIndex: Accelerating Learned Sparse Attention with a Causal Inverted-File Index

Learned sparse attention, used in production models such as DeepSeek-V4 and GLM-5, lets each query attend to only k keys chosen by a lightweight indexer, but the indexer still scores every key in the prefix. At one million tokens, this selection takes more than half of prefill time. Two-stage selection over contiguous...

Jeongmin Brian Park, Wen-mei W. Hwu · 0 citations
#machine learning Preprint Nov 2026

Recursive Sparse Attention: Million-Token Length Extrapolation at Logarithmic Cost

At context lengths of about 1M tokens, dense attention is costly in prefill and decoding, and training typically relies on long documents, which become scarcer as the target length increases. Most sparse attention methods score all preceding blocks or tokens, so their selection cost per query is $O(L)$ at context lengt...

Rui-Tian Wang, Xin-Yu Yang, Min-Shen Zhang et al. · 0 citations

Scaling Parameter and Context in Attention: Native Sparse Attention from Mixture-of-Head

NAMOH, an architecture-native sparse attention mechanism that activates only its assigned tokens and performs causal attention within this subsequence, is introduced, and it is hoped this work offers a new path for scaling attention, with parameter scaling directly enabling context scaling.

Zi-Zhuo Fu, Run-Sheng Wang, Meng Li · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.