Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
By Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, Franccois Fleuret. 2020
2,953 citations recorded by the source corpus.
Transformers achieve remarkable performance in several tasks but due to their quadratic complexity, with respect to the input's length, they are prohibitively slow for very long sequences. To address this limitation, we express the self-attention as a linear dot-product of kernel feature maps and make use of the associativity property of matrix products to reduce the complexity from $\mathcal{O}\left(N^2\right)$ to $\mathcal{O}\left(N\right)$, where $N$ is the sequence length. We show that this formulation permits an iterative implementation that dramatically accelerates autoregressive transformers and reveals their relationship to recurrent neural networks. Our linear transformers achieve similar performance to vanilla transformers and they are up to 4000x faster on autoregressive prediction of very long sequences.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures, Efficiency & Compression
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Mohit Bansal
- Jianfeng Gao
- Quoc V. Le
- Luke S. Zettlemoyer
- Yoshua Bengio
- Percy Liang
- Dacheng Tao
- Noah A. Smith
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Ming-Hsuan Yang
- Xiaogang Wang
- Trevor Darrell
- Jitendra Malik
- Andrew Zisserman
- Yi Yang
In Model Architectures
In Efficiency & Compression
Citations in the corpus
- RoFormer: Enhanced Transformer with Rotary Position Embedding (2021, methodology): “The authors of Katharopoulos et al. [2020] have proposed φ(x) = φ(x) = elu(x)+1 and first computed the multiplication between keys and values using the associative property of matrix multiplication. A softmax function is used in Shen et al. [2021] to normalize queries and keys separately before the ”
- Rethinking Attention with Performers (2020, methodology): “There is also a long line of research on using dense attention matrices, but defined by low-rank kernels substituting softmax (Katharopoulos et al., 2020; Shen et al., 2018).”
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “These methods range from sparse-approximation [53, 77] to low-rank approximation [13, 52, 88], and their combinations [3, 9, 96].”
- Perceiver: General Perception with Iterative Attention (2021, methodology): “…simplifying the matrix multiplications used in QKV attention (Choromanski et al., 2021; Peng et al., 2021; Ki-taev et al., 2020; Xiong et al., 2021; Katharopoulos et al., 2020; Tay et al., 2021a), or by introducing bottlenecks into each module’s computation (Lee et al., 2019; Wang et al., 2020b).”
- Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction (2022, background): “Second, attention, often interpreted as a mechanism for measuring similarities (Katharopoulos et al., 2020), may be inherently biased when being used for updating quantity representations.”
- Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “We opted for a Linear Transformer (Katharopoulos et al., 2020) relies on a linearized attention mechanism, defined as where x is the input of the linearized attention layer, φ ( · ) is a non-linear feature map, J is the size of the input x (in our case, J = d 2 ), and Q , K , and V are linear…”
- Deformable DETR: Deformable Transformers for End-to-End Object Detection (2020, background): “Katharopoulos et al. (2020); Choromanski et al. (2020) rewrite the calculation of self-attention through kernelization approximation.”
- Long Range Arena: A Benchmark for Efficient Transformers (2020, methodology): “, 2020), Linear Transformers (Katharopoulos et al., 2020), and Performers (Choromanski et al.”
- Efficient Transformers: A Survey (2020, methodology): “The Linear Transformer (Katharopoulos et al., 2020) also evaluates on speech recognition, which is a rare benchmark amongst this group of papers.”
- Group Equivariant Stand-Alone Self-Attention For Vision (2020, background): “This is an active area of research, e.g., Kitaev et al. (2020); Wang et al. (2020); Zaheer et al. (2020); Katharopoulos et al. (2020) and we believe that efficiency improvements to vanilla self-attention can be seamlessly incorporated to our approach.”
- LambdaNetworks: Modeling Long-Range Interactions Without Attention (2021, methodology): “They are recently enjoying a resurgence of popularity with many works modifying the popular Transformer architecture for sequential processing applications (Katharopoulos et al., 2020; Wang et al., 2020b; Choromanski et al., 2020; Xiong et al., 2021).”
- Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention (2021, methodology): “In (Shen et al. 2018b; Katharopoulos et al. 2020), linearizing the softmax attention in transformers was based on heuristically separat-ing keys and queries in a linear dot product approximation.”
- Multi-Scale Vision Longformer: A New Vision Transformer for High-Resolution Image Encoding (2021, methodology): “The fourth is the (generalized) kernel-based mechanism, including Performer[9] and Linear Transformers[16].”
- Understanding and Overcoming the Challenges of Efficient Transformer Quantization (2021, background): “…(Child et al., 2019; Beltagy et al., 2020) or learned (Kitaev et al., 2020) sparsity patterns to the otherwise dense attention matrix, while others introduce efficient approximations based on low-rank (Wang et al., 2020b) or kernel methods (Katharopoulos et al., 2020; Choro-manski et al., 2020).”
- Random Feature Attention (2021, methodology): “Katharopoulos et al. (2020) inspire the causal attention variant of R FA .”
- FNet: Mixing Tokens with Fourier Transforms (2021, methodology): “…FNet is slower than the Performer and, based on results in Tay et al. (2021a), likely also slower than the other efficient Transformers that linearize attention, namely Local Attention (Parmar et al., 2018), Lin-former (Wang et al., 2020) and Linear Transformer (Katharopoulos et al., 2020).”