Linear Attention
A reformulation of transformer attention using kernel feature maps so cost scales linearly with sequence length instead of quadratically, equivalent to a recurrent update.
Linear attention is a reformulation of transformer self-attention that scales linearly with sequence length instead of quadratically. Standard attention computes a similarity score between every pair of tokens, an O(n squared) operation. Angelos Katharopoulos and coauthors showed in 2020 (Transformers are RNNs, arXiv:2006.16236) that replacing the softmax similarity with a kernel feature map lets matrix multiplication be reordered, using its associativity, so the same computation can be done in O(n) time and constant memory per step.
The reordering has a second consequence. It makes causal, autoregressive attention equivalent to a recurrent update over a fixed-size hidden state, the same state a plain RNN would carry from one token to the next. This connects linear attention to earlier and later linear-complexity sequence models, including state space models, and explains why linear attention layers can run autoregressive inference many times faster than standard attention. The cost is losing some of the expressiveness a full pairwise comparison provides.
Because linear attention trades softmax's precise pairwise comparison for a fixed-size summary, it typically loses accuracy on tasks needing precise long-range retrieval. This spurred a family of variants, including gated and hybrid attention layers that mix linear and full attention, aimed at closing that gap. Linear attention has since been combined with other efficiency techniques, including low-rank projections and rotary position embeddings, to build efficient attention layers for long video and image-generation transformers.
Sources
Research this in Signals
Signals turns a topic into a sourced research record you can inspect and rerun. Your first scan is free, and this one starts with Linear Attention already loaded, so edit it or scan as is.