Linear Attention
An attention variant that replaces explicit softmax dot-product attention with kernel or feature-map formulations that scale near-linearly with sequence length.
Linear attention is an attention variant that replaces full all-pairs softmax scoring with feature-map or recurrent formulations, trading exact dense attention for better sequence-length scaling on long inputs.
At a glance
Released
June 2020
Authors
Katharopoulos, Angelos, Vyas, Apoorv, Pappas, Nikolaos, et al.
Optimizes
- Sequence Scaling
- Attention Compute
- Memory Bandwidth
What It Is
Linear attention is an attention variant that reformulates attention without building the full softmax score matrix. Feature maps on queries and keys let the model accumulate key-value statistics in linear time rather than scoring every query-key pair explicitly.Why It Exists
Linear attention targets sequence-length scaling, attention compute cost, and memory bandwidth when dense quadratic attention would dominate runtime on long contexts.How It Works
Queries and keys pass through a feature map φ that makes their product associative. The model accumulates φ(K)ᵀV across positions and combines the result with φ(Q) at each step, avoiding explicit materialization of the full n-by-n attention matrix.QueriesqqqqValuesRunning summariesVV\phi(K)^{\top} V\phi(K)^{\top} VV to \phi(K)^{\top} VV to \phi(K)^{\top} V\phi(K)^{\top} V to q\phi(K)^{\top} V to q\phi(K)^{\top} V to q\phi(K)^{\top} V to q
Math Or Compute Schema
With feature map φ applied to queries and keys, linear attention computes output through associative products rather than softmax over all pairs. The formulas below contrast dense multi-head attention against linear attention that routes through φ and a normalization term.Compared To Nearby Modules
Compared with multi-head attention, linear attention changes the compute mechanism rather than only sharing key-value heads. Multi-query and grouped-query attention remain dense over allowed positions but reduce key-value head count. Linear attention instead pursues subquadratic sequence scaling through kernel or recurrence formulations.| Comparison dimension | Linear Attention | Multi-Head Attention | Multi-Query Attention | Grouped-Query Attention |
|---|---|---|---|---|
| Sequence scaling | Near-linear O(n) per head with fixed feature-map dimension | Quadratic O(n²) per head | Quadratic O(n²) with fewer key-value projections | Quadratic O(n²) with reduced key-value head count |
| Compute mechanism | Feature-map φ on queries and keys; associative key-value accumulation | Explicit softmax over all query-key dot products | Dense softmax with shared key-value heads | Dense softmax with grouped key-value heads |
| Expressiveness | Approximates softmax dot-product attention via chosen kernel | Full pairwise softmax attention | Full pairwise softmax attention with shared key-value heads | Full pairwise softmax attention with grouped key-value heads |