Linformer: Self-Attention with Linear Complexity

By Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, Hao Ma. 2020

2,339 citations recorded by the source corpus.

Large transformer models have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. However, training and deploying these models can be prohibitively costly for long sequences, as the standard self-attention mechanism of the Transformer uses $O(n^2)$ time and space with respect to sequence length. In this paper, we demonstrate that the self-attention mechanism can be approximated by a low-rank matrix. We further exploit this finding to propose a new self-attention mechanism, which reduces the overall self-attention complexity from $O(n^2)$ to $O(n)$ in both time and space. The resulting linear transformer, the \textit{Linformer}, performs on par with standard Transformer models, while being much more memory- and time-efficient.

Subfields: Artificial Intelligence, 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

In Model Architectures

In Efficiency & Compression

Citations in the corpus

Rethinking Attention with Performers (2020, methodology): “…as mentioned above, we replaced the attention function with the Linformer variant via Jax, with δ = 10 − 6 , k = 600 (same notation used in the paper (Wang et al., 2020)), where δ is the exponent in a renormalization procedure using e − δ as a multiplier in order to approximate softmax, while k…”
FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “Linformer Attention [88], Smyrf [20], and LongShortFormer (LSFormer) [98].”
Self-attention Does Not Need $O(n^2)$ Memory (2021, methodology): “…and architectures with more favorable complexity classes (Kitaev et al., 2020; Roy et al., 2021; Zaheer et al., 2020; Choromanski et al., 2020; Wang et al., 2020; Ren et al., 2021; Child et al., 2019; Tay et al., 2021; Wang et al., 2020; Ma et al., 2021; Shen et al., 2021; Qiu et al., 2020).”
Landmark Attention: Random-Access Infinite Context Length for Transformers (2023, methodology): “Linformer [37] uses a low-rank approximation of the attention matrix while Performer [7] uses a non-softmax kernel to obtain a more efficient implementation.”
Perceiver IO: A General Architecture for Structured Inputs & Outputs (2021, methodology): “Our work uses attention over inputs and outputs of different sizes in part to produce an efficient attention architecture, and several other efficient attention architectures have been proposed, largely for language or small-scale problems (e.g. Xiong et al. 2021; Wang et al. 2020; Tay et al. 2021a;”
Perceiver: General Perception with Iterative Attention (2021, methodology): “Audio+video fusion leads to solid improvements over single modalities (and outperforms specialized fusion optimization approaches (Wang et al., 2020c)) but is still lower than the state-of-the-art approach that uses separate models with late fusion (Fayek & Kumar, 2020).”
Compacter: Efficient Low-Rank Hypercomplex Adapter Layers (2021, background): “For PROMPT TUNING, high memory costs are due to the fact that the computational complexity of self-attention, which requires storing the full attention matrix for gradient computation, scales quadratically with the sequence length [36].”
Deformable DETR: Deformable Transformers for End-to-End Object Detection (2020, background): “Wang et al. (2020) reduces the number of key elements through a linear projection on the size dimension instead of the channel dimension.”
Long Range Arena: A Benchmark for Efficient Transformers (2020, methodology): “Natural Language Understanding / GLUE tasks Evaluation on natural language understanding (NLU) tasks is also common (Wang et al., 2020).”
Pyramid Vision Transformer: A Versatile Backbone for Dense Prediction without Convolutions (2021, methodology): “, linear attention [10], sparse attention [14] and deformable attention [17]), and improve the position embedding in PVT? Answer: In this work, we target to introduce the pyramid framework into Transformer, for dense prediction tasks.”
Efficient Transformers: A Survey (2020, methodology): “On the other hand, the Linformer (Wang et al., 2020c) focuses on subsets of the GLUE (Wang et al., 2018) benchmark.”
MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers (2020, background): “Later, the complexity of transformer attention has been reduced [49, 90], by introducing local [68] or sparse attention [23], together with a global memory [6, 103, 31, 1].”
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 efﬁciency improvements to vanilla self-attention can be seamlessly incorporated to our approach.”
Synthesizer: Rethinking Self-Attention for Transformer Models (2020, methodology): “On encoding tasks, our factorized Synthesizers can outperform other low-rank efficient Transformer models such as Linformers (Wang et al., 2020).”
Multiscale Vision Transformers (2021, background): “Recent works [106, 65, 20, 100, 23, 19, 72, 6] reduce the quadratic attention complexity to make transformers more efficient for natural language processing applications, which is complementary to our approach.”
ViViT: A Video Vision Transformer (2021, background): “Many variants of the transformer have also been proposed to reduce the computational cost of self-attention when processing longer sequences [10, 11, 37, 62, 63, 73] and to improve parameter efﬁciency [40, 14].”
LambdaNetworks: Modeling Long-Range Interactions Without Attention (2021, background): “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).”