Attention Approximation

Follow this topic Ask about this topic

Latest papers

17 papers4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Oct 9, 2026

Not All Dimensions Are Equal: Outlier-Aware Attention Linearization with Grouped Quadratic Kernels

Linearizing softmax attention offers a route to efficient Transformer inference, but preserving pretrained attention remains challenging. We identify an important source of approximation error overlooked by standard linearization methods: a small number of outlier dimensions contribute disproportionately to query-key dot products and account for a large fraction of the approximation error. Motivated by this heterogeneity, we propose Outlier-Aware Attention Linearization (OAL), a dimension-aware method for constructing quadratic attention approximations. Starting from a second-order Taylor approximation, we introduce a Hadamard-product formulation that makes individual query-key contributions explicit. This formulation relaxes globally shared coefficients to support dimension-specific linear terms and cross-dimensional quadratic interactions while preserving separable evaluation. To retain this flexibility with fewer parameters, OAL groups dimensions with similar contribution scales to share coefficients, while allowing distinct treatment of the few outliers. The resulting positive quadratic kernel is calibrated against pretrained attention outputs and admits linear-time evaluation with respect to sequence length for fixed head dimensions. On Qwen2.5-0.5B, OAL reduces frozen-attention output relative MSE by approximately 8.9% compared with DiJiang. Replacing middle-layer attention modules and jointly fine-tuning the kernel coefficients with LoRA further lowers WikiText-103 perplexity from 31.71 to 27.50 compared with a learned global quadratic, while improving accuracy on PIQA, HellaSwag, and ARC-E. These results demonstrate the value of outlier-aware dimension grouping for both attention approximation and pretrained-model conversion. The code is available at https://github.com/wuqianyue09/OAL

Weiqi Sun, Qianyue Wu, Wenjia Wang +1

The Chinese University of Hong Kong, Shenzhen · Beijing Normal University, Zhuhai · National University of Singapore

Attention Approximation Efficient Attention Linear Attention Transformer Inference

Oct 7, 2026

Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values

Large Language Models (LLMs) achieve strong performance across many domains, but their efficiency is limited by the quadratic cost of attention with respect to prompt length. Sparse attention reduces this cost by retaining only a small fraction of query-key interactions to approximate the full attention matrix. However, existing methods are trapped in a mathematically wrong view: they simply keep large scalar entries or high-mass regions of the attention matrix. This treats the attention matrix as a bag of values, ignoring that it is used as a structured matrix whose entries jointly determine the attention output through multiplication with value vectors. We argue that this is the core conceptual issue: sparse attention should be formulated as matrix approximation, not as blindly choosing the largest values from a bag of entries. Based on this view, we propose Matrix Approximation Sparse Attention (MASA). MASA replaces raw attention-mass ranking with a closed-form score that measures how much each sparse unit reduces matrix-product approximation error. As a theory-grounded plug-in correction, MASA can be added to existing sparse attention frameworks without changing their sparse kernels or budgets. Extensive experiments across multiple sparse attention methods, benchmarks, and LLM backbones show consistent accuracy gains, supporting both MASA and the matrix-approximation view of sparse attention.

Fang Wan, Xufeng Liu, Fan Li +1

Stony Brook University · Duke University

Sparse Attention Efficient Attention Attention Mechanisms Attention Approximation LLM Inference Acceleration

Oct 7, 2026

Attention via Black-Box Vector Search

Sparse attention mechanisms estimate attention over

n

tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heaviest keys, which motivates the following question: given black-box access to a MIPS oracle, how many keys must be retrieved to output an

\varepsilon

-accurate attention estimate? We answer this question by unifying prior approaches through the framework of priority sampling. With a single MIPS index, we show that

Θ(\sqrt{n}/\varepsilon)

retrieved keys are both sufficient and necessary. With

Θ(\log n)

indices, we give an algorithm that retrieves only

O(\log n+1/\varepsilon^2)

keys and prove that this is near-optimal. More generally, we design algorithms that establish a smooth tradeoff between the number of MIPS indices and number of retrieved keys. We then show that if we allow augmentation of keys and queries, we can bypass the above lower bounds: there exists a simple priority-sampling estimator using a single MIPS index and

O(1/\varepsilon^2)

retrieved keys. When integrated into LLM inference, our algorithms outperform top-

k

and sampling approaches used in prior work and yield attention approximation that scales favorably to long contexts.

Stepan Zharkov, Krish Singal, Ashwin Padaki +1

University of Pennsylvania

Attention Approximation Efficient Attention Sparse Attention LLM Inference Efficiency

Sep 29, 2026

Efficiently Approximating Attention Is Hard

Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.

Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno +2

Institute for Data Science in Mechanical Engineering, RWTH Aachen University · Autonomous Systems Lab, Stanford University

Attention Approximation Efficient Attention Softmax Attention Sparse Attention

Sep 12, 2026

Exact Finite Attention Responses From RoPE Derivatives

We derive exact local responses for attention interventions, allowing candidate edits to be scored from a cached baseline and one backward pass. The starting point is the RoPE derivative

\partial_p z(p) = A z(p)

: its integral gives the finite positional displacement, which we carry through the softmax without linearising either rotation or normalisation. The resulting predictions achieve 95.36--96.52% sign accuracy across 92,160 executed positional edits on 768 held-out prompt sets, reducing answer-margin MAE by 73.6--82.5% against the positional Jacobian and by 36.2--50.9% against zero. For simultaneous key and value edits, the same divided-difference calculus isolates the interaction term

C_{KV} = \sum_j (p'_j - p_j)\,\varepsilon_j

, which is omitted by adding separate attributions. Retaining it reduces downstream margin MAE by more than a factor of nine in every setting of a 5,120-intervention sweep across two Qwen sizes, two tasks, and multiple layers; reductions against a quadratic interaction correction are 75.9--98.5%. Exactness concerns the edited attention write; downstream predictions contract that response with a baseline gradient and are evaluated by native execution. The calculus also yields a KL certificate for local approximation error, an exact query-conditioned gradient-step representation whose curvature identifies attention-preserving query directions, and minimum-norm query control. Sparse evaluation supports candidate ranking and cache decisions under explicit local distortion criteria.

Julie Huang, Maggie Chlon, Gregory Gutin +1

Hassana Labs · Department of Computer Science, Royal Holloway, University of London · University of Oxford

Attention Approximation Causal Interventions in Language Models Softmax Attention Gradient-Based Attribution Rotary Positional Embeddings

Aug 27, 2026

ClusterAttention: A training-free speedup of bidirectional attention

We introduce ClusterAttention, a general training-free speedup of bidirectional attention at large token counts. We point out two common assumptions in contemporary training-free methods; attention sparsity, and context that can be leveraged, such as structure in the input or multiple similar forward passes, and show when they fail. Our proposed method utilizes a fast attention-aware recursive clustering method, and compensation of excluded clusters through their mean. The clustering method gives power-of-two cluster sizes, allowing block-sparse attention to match dense attention in GPU throughput. On TabPFN-3 arXiv:2605.13986, a model where none of the assumptions hold, ClusterAttention is to our knowledge the first method to provide a substantial speedup over the default attention, while consistently keeping over 99% of its accuracy. On the largest dataset from the TALENT benchmark suite, it makes processing of the training dataset close to 8x faster at nearly 11x attention speedup. ClusterAttention is also competitive with domain-specific methods, while avoiding any of the domain-specific engineering. On video-generation with Wan 2.1-T2V-14B arXiv:2503.20314 it produces output closer to dense attention at a larger speedup (1.8x vs 1.4x) than SVOO arXiv:2603.18636, a leading method in this domain, with both evaluated without offline calibration.

Kasper Nordenram, Amelie Dittmann

Independent researcher

Efficient Attention Attention Mechanisms Attention Approximation

Aug 26, 2026

How Much Rank Does LoRA Need? Rank-Error Bounds for Transformer Attention

Choosing the rank of a low-rank adaptation (LoRA) update is usually an empirical task. In this paper, we provide a task-dependent theory of the approximation error achievable at each LoRA rank for Transformer attention. We fix a pretrained attention head, a target attention function, and a distribution over inputs from the downstream task, and bound the smallest expected Kullback--Leibler (KL) error achievable by a rank-

r

query LoRA update. When target attention probabilities are bounded away from zero, we prove a lower bound of the error proportional to

ψ(\|d\|_2)

, where

d

is the difference between candidate and target attention scores and

ψ(t)=\min\{t^2,t\}

. We also prove an unconditional upper bound

\min\{\|d\|_2^2/4,\sqrt2\|d\|_2\}

. Under explicit realizability, geometry, and moment conditions, we then bound the best rank-

r

error between an explicit multiple of

ψ(\sqrt{T_r})

and

\min\{T_r/4,\sqrt{2T_r}\}

, where

T_r

is the downstream-weighted tail energy of the target update. We also provide target-Fisher bounds when candidate scores remain within a fixed range of the target scores, and an unrestricted lower bound when a subset of tokens carries most of the probability mass. These spectral bounds describe finite-score approximation. We then construct explicit families in which softmax saturation makes the rank required to match the attention function strictly smaller than the rank required to match the finite logits. Finally, we extend the analysis to fused multi-head LoRA and joint query/key updates, exposing the effects of rank sharing and query/key factorization constraints.

Gerard Conangla Planes

Aily Labs

Attention Approximation Low-Rank Adaptation Transformer Attention Efficient Attention Softmax Attention

Jun 22, 2026

SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers

Long contexts have become standard in pretrained LLMs, yet they remain expensive to run: prefill compute grows quadratically with sequence length, and every decode step re-reads a key-value cache that grows linearly with it. Sparse attention cuts these costs by attending only to a relevant subset of past tokens, but selecting that subset is itself expensive. We present SpotAttention, a lightweight selector that attaches to a frozen pretrained transformer and learns by KL distillation to estimate its attention distribution. The selector picks the top-K keys each query attends to, and because its estimate is a calibrated distribution, a dual top-p rule reads the per-query, per-layer budget directly from it. Across Qwen3 (dense, 4B-32B) and Qwen3.5 (hybrid linear/full attention, 4B-9B), SpotAttention matches dense accuracy at contexts up to 128K tokens, eight times the training length. Decode at L=128K runs 3.9x faster than FlashAttention and 1.8x faster than Twilight, the strongest training-free baseline. Quantizing the selector's K-cache to INT4 or FP4 microscale shrinks it 3.5x at no accuracy cost.

Huzama Ahmad, Se-Young Yun

KAIST

Sparse Attention Block-Sparse Attention Attention-Guided Distillation Long-Context Language Model Inference LLM Inference Acceleration Memory-Efficient Attention+2

Jun 9, 2026

Express Language Modeling

We introduce a new tool, Express, for converting a non-causal attention approximation into a causal approximation with matching approximation guarantees. When combined with the state-of-the-art Thinformer approximation, Express improves upon the best known causal attention guarantees, delivering

\log^{3/2}(n)/s

approximation error with only

O(s)

memory and

O(s^2 \log^2(n))

compression overhead for a sequence of length

n

. We pair these developments with an efficient I/O-aware Triton implementation, demonstrate substantial speedups over FlashAttention 2, and use Express to overcome four resource bottlenecks in the language modeling pipeline: long-context prefill, KV cache compression, long-form memory-constrained decoding, and long-form compute-constrained decoding.

Albert Gong, Annabelle Michael Carrell, Raaz Dwivedi +1

Cornell Tech · University of Cambridge · Microsoft Research

Long-Context Language Model Inference Attention Mechanisms Efficient Language Model Inference Attention Approximation Memory-Efficient Attention Causal Attention

May 11, 2026

Variational Linear Attention: Stable Associative Memory for Long-Context Transformers

Linear attention reduces the quadratic cost of softmax attention to

\mathcal{O}(T)

, but its memory state grows as

\mathcal{O}(T)

in Frobenius norm, causing progressive interference between stored associations. We introduce Variational Linear Attention (VLA), which reframes the memory update as an online regularised least-squares problem with an adaptive penalty matrix maintained via the Sherman-Morrison rank-1 formula. We prove that normalising the write direction to unit length gives the recurrence Jacobian spectral norm exactly

1

for all sequence lengths and head dimensions (Proposition 2), and that the state norm is self-limiting under bounded inputs (Proposition 1). Empirically, VLA reduces

\|S_t\|_F

by

109\times

relative to standard linear attention at

T{=}1{,}000

, achieves near-perfect exact-match accuracy on multi-query associative recall within the effective per-head memory regime (

n_\text{pairs} < d_h

), maintaining substantially higher retrieval performance than DeltaNet and standard linear attention under increasing memory load, and maintains 62% accuracy at the per-head capacity boundary. A Triton-fused kernel achieves

14\times

speedup over sequential Python and

\mathcal{O}(T)

scaling, crossing below softmax attention latency at approximately 43,000 tokens.

Vishal Pandey, Gopal Singh

Independent Researcher London, UK · Metriqual Athens, GR

Efficient Attention Linear Attention Associative Memory Memory-Efficient Attention Attention Approximation

May 10, 2026

Nectar: Neural Estimation of Cached-Token Attention via Regression

Evaluating softmax attention over a fixed long context requires reading every cached key-value pair for each new query token. For a given context (a book, a manual, a legal corpus) the attention output is a deterministic function of the query. We propose Nectar, which fits a compact neural network to this function for queries drawn from a task-relevant distribution. Nectar fits two networks per layer and KV-head: a target network that predicts the attention output and a score network that predicts the log-normalizer. The pair plugs into the standard masked self-attention at inference time, replacing the

O(n)

attention over the cache with a forward pass whose cost does not depend on

n

. Each module carries on the order of

|θ|

parameters per layer and KV-head, typically much smaller than the

2nd

KV-cache footprint at the same granularity. We report experiments on models from 1.7B to 8B parameters across five long-context datasets. The approximation error tracks the next-token accuracy gap to full attention, and allocating capacity non-uniformly across layers reduces that gap in our ablation. Beyond this analysis of metrics, we check that the text generations (following a question prompt) of a model equipped with a Nectar module match in semantic content those obtained by giving the same model access to the full cache.

João Monteiro, Michal Klein, Pierre Ablin +1

Apple

Attention Approximation Softmax Attention Self-Attention KV Caching Long-Context Language Model Inference Efficient Attention+2

May 7, 2026

Nearly Optimal Attention Coresets

We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values

(K,V)

in

\mathbb{R}^d

, there exists a subset

(K',V')

of size at most

O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})

such that

\left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon

simultaneously for all queries whose norm is bounded by

ρ

. This outperforms the best known results for this problem. We also offer an improved lower bound showing that

\varepsilon

-coresets must have size

Ω({\sqrt{d} e^ρ/ε})

.

Edo Liberty, Alexandr Andoni, Eldar Kleiner

Softmax Attention Efficient Attention Coreset Selection Attention Approximation Memory-Efficient Attention

Apr 27, 2026

Transformer Approximations from ReLUs

We provide a systematic recipe for translating ReLU approximation results to softmax attention mechanism. This recipe covers many common approximation targets. Importantly, it yields target-specific, economic resource bounds beyond universal approximation statements. We showcase the recipe on multiplication, reciprocal computation, and min/max primitives. These results provide new analytical tools for analyzing softmax transformer models.

Jerry Yao-Chieh Hu, Mingcheng Lu, Yi-Chen Lee +1

Center for Foundation Models and Generative AI, Northwestern University, Evanston, IL 60208, USA · Department of Computer Science, Northwestern University, Evanston, IL 60208, USA · Department of Physics, National Taiwan University, Taipei 10617, Taiwan +1

Softmax Attention Neural Network Approximation Theory Attention Mechanisms Attention Approximation Function Approximation

Apr 10, 2026

Hierarchical Kernel Transformer: Multi-Scale Attention with an Information-Theoretic Approximation Analysis

The Hierarchical Kernel Transformer (HKT) is a multi-scale attention mechanism that processes sequences at L resolution levels via trainable causal downsampling, combining level-specific score matrices through learned convex weights. The total computational cost is bounded by 4/3 times that of standard attention, reaching 1.3125x for L = 3. Four theoretical results are established. (i) The hierarchical score matrix defines a positive semidefinite kernel under a sufficient condition on the symmetrised bilinear form (Proposition 3.1). (ii) The asymmetric score matrix decomposes uniquely into a symmetric part controlling reciprocal attention and an antisymmetric part controlling directional attention; HKT provides L independent such pairs across scales, one per resolution level (Propositions 3.5-3.6). (iii) The approximation error decomposes into three interpretable components with an explicit non-Gaussian correction and a geometric decay bound in L (Theorem 4.3, Proposition 4.4). (iv) HKT strictly subsumes single-head standard attention and causal convolution (Proposition 3.4). Experiments over 3 random seeds show consistent gains over retrained standard attention baselines: +4.77pp on synthetic ListOps (55.10+-0.29% vs 50.33+-0.12%, T = 512), +1.44pp on sequential CIFAR-10 (35.45+-0.09% vs 34.01+-0.19%, T = 1,024), and +7.47pp on IMDB character-level sentiment (70.19+-0.57% vs 62.72+-0.40%, T = 1,024), all at 1.31x overhead.

Giansalvo Cirrincione

Laboratoire LTI, Université de Picardie Jules Verne, 33 rue Saint-Leu, Amiens, 80039, France

Attention Approximation Transformer Attention Attention Mechanisms Multi-Scale Attention Efficient Attention Kernel Methods

Mar 31, 2026

Tucker Attention: A generalization of approximate attention mechanisms

The pursuit of reducing the memory footprint of the self-attention mechanism in multi-headed self attention (MHA) spawned a rich portfolio of methods, e.g., group-query attention (GQA) and multi-head latent attention (MLA). The methods leverage specialized low-rank factorizations across embedding dimensions or attention heads. From the point of view of classical low-rank approximation, these methods are unconventional and raise questions of which objects they really approximate and how to interpret the low-rank behavior of the resulting representations. To answer these questions, this work proposes a generalized view on the weight objects in the self-attention layer and a factorization strategy, which allows us to construct a parameter efficient scheme, called Tucker Attention. Tucker Attention requires an order of magnitude fewer parameters for comparable validation metrics, compared to GQA and MLA, as evaluated in LLM and ViT test cases. Additionally, Tucker Attention~encompasses GQA, MLA, MHA as special cases and is fully compatible with flash-attention and rotary position embeddings (RoPE). This generalization strategy yields insights of the actual ranks achieved by MHA, GQA, and MLA, and further enables simplifications for MLA.

Timon Klein, Jonas Kusch, Sebastian Sager +2

Department of Mathematics; Otto von Guericke University Magdeburg; 39106 Magdeburg; Germany. · Scientific Computing, Norwegian University of Life Sciences, ˚As, Norway · Max Planck Institute for Dynamics of Complex Technical Systems; 39106 Magdeburg; Germany. +1

Tucker Decomposition Attention Mechanisms Attention Approximation Memory-Efficient Attention Multi-Head Attention Low-Rank Attention+3

Mar 12, 2026

Why Attend to Everything? Focus is the Key

Standard attention scales quadratically with sequence length. Efficient attention methods reduce this O(n^2) cost, but when retrofitted into pretrained models, they often degrade perplexity, downstream accuracy, or both. We introduce Focus, a method that learns which token pairs matter. Focus adds a small set of learnable centroids--as few as 148K parameters per layer--that act as gates: only token pairs belonging to the same centroid group attend to each other over long ranges. Focus is composable: it can be added to any pretrained model by training only the centroids while keeping all original weights frozen. Experiments show that composing Focus onto pretrained models yields zero degradation on downstream benchmarks across model sizes from 124M to 70B parameters and five attention architectures. Surprisingly, sparse Focus attention outperforms full attention at 124M scale (30.3 vs. 31.4 perplexity) and matches full attention when trained from scratch at 7B scale (13.82 vs. 13.89). Focus is also fast: top-k group membership gives a 2x speedup with better quality than the original pretrained model. Using our FlashAttention decomposition, Focus achieves an 8.6x speedup at 1M tokens without custom kernels.

Hengshuai Yao, Xing Chen, Ahmed Murtadha +8

Sapient Intelligence · University of Alberta · Tsinghua University

Attention Mechanisms Efficient Attention Attention Approximation Sparse Attention Long-Context Modeling

Mar 9, 2026

SVG-EAR: Parameter-Free Linear Compensation for Sparse Video Generation via Error-aware Routing

Diffusion Transformers (DiTs) have become a leading backbone for video generation, yet their quadratic attention cost remains a major bottleneck. Sparse attention reduces this cost by computing only a subset of attention blocks. However, prior methods often either drop the remaining blocks, which incurs information loss, or rely on learned predictors to approximate them, introducing training overhead and potential output distribution shifting. In this paper, we show that the missing contributions can be recovered without training: after semantic clustering, keys and values within each block exhibit strong similarity and can be well summarized by a small set of cluster centroids. Based on this observation, we introduce SVG-EAR, a parameter-free linear compensation branch that uses the centroid to approximate skipped blocks and recover their contributions. While centroid compensation is accurate for most blocks, it can fail on a small subset. Standard sparsification typically selects blocks by attention scores, which indicate where the model places its attention mass, but not where the approximation error would be largest. SVG-EAR therefore performs error-aware routing: a lightweight probe estimates the compensation error for each block, and we compute exactly the blocks with the highest error-to-cost ratio while compensating for skipped blocks. We provide theoretical guarantees that relate attention reconstruction error to clustering quality, and empirically show that SVG-EAR improves the quality-efficiency trade-off and increases throughput at the same generation fidelity on video diffusion tasks. Overall, SVG-EAR establishes a clear Pareto frontier over prior approaches, achieving up to 1.77

\times

and 1.93

\times

speedups while maintaining PSNRs of up to 29.759 and 31.043 on Wan2.2 and HunyuanVideo, respectively.

Xuanyi Zhou, Qiuyang Mang, Shuo Yang +7

UC Berkeley, USA

Video Diffusion Models Efficient Attention Sparse Attention Diffusion Model Inference Acceleration Block-Sparse Attention Attention Approximation