Linformer: Self-Attention with Linear Complexity

Sinong WangBelinda Z. LiMadian KhabsaHan FangHao Ma

article2020arXiv2,408 citations

Proposes Linformer, an attention architecture that reduces Transformer computational and memory complexity from quadratic to linear via low-rank matrix approximation without sacrificing accuracy.

Listen

Modern natural language processing relies heavily on Transformer models, but their core self-attention mechanism scales quadratically with sequence length in both computation time and memory. This computational bottleneck makes processing long texts prohibitively expensive for training and deployment. The article addresses this limitation by investigating whether Transformer self-attention can be mathematically simplified without sacrificing model accuracy.

The article demonstrates that self-attention matrices can be effectively approximated using low-rank representations and introduces the Linformer, an architecture that reduces self-attention complexity from quadratic to linear with respect to sequence length. The authors evaluated their design by pretraining models on large text corpora (BookCorpus and English Wikipedia) and benchmarking downstream performance across multiple standard language understanding and sentiment analysis tasks, alongside empirical speed and memory tests on high-performance GPUs.

The findings confirm three critical results. First, spectrum analysis shows that attention matrices are inherently low rank, with information concentrated in the top singular values. Second, the Linformer matches standard Transformer models in validation perplexity and downstream accuracy, scoring 92.30 on benchmark tasks compared to 92.25 for standard RoBERTa baselines, while outperforming distilled models. Third, the Linformer provides dramatic efficiency gains that scale with sequence length, achieving up to a 20-fold speedup in inference and a 60-fold reduction in memory consumption at long sequence lengths.

These results demonstrate that organizations can significantly lower computing costs, decrease power consumption, and deploy high-performance Transformer architectures on longer documents and resource-constrained environments. Practitioners should consider adopting linear projection techniques, particularly layerwise parameter sharing, for long-sequence tasks. Future work should explore extending this linear attention design to image processing and evaluating non-uniform projections across different layers.

Meta attention mechanism encoder-decoder linear complexity linear self-attention Linformer model linear complexity

arXiv: 2006.04768 facebookresearch/fairseq

Paper: Attention Is All You Need, Ashish Vaswani et al. (2017). Mastering the foundational Transformer architecture introduced here is essential for understanding how the Linformer modifies the self-attention mechanism to reduce complexity.
Paper: Reformer: The Efficient Transformer, Nikita Kitaev et al. (2020). Reading this work on locality-sensitive hashing provides crucial context on prior efficient Transformer designs that directly motivated the low-rank approximation approach of the Linformer.

Paper: Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, Angelos Katharopoulos et al. (2020). This paper builds directly upon linear attention concepts to formulate linear transformers with recurrent inference properties.
Paper: Rethinking Attention with Performers, Krzysztof Choromanski et al. (2021). This work extends linear complexity ideas to the full softmax kernel using random feature maps, offering an alternative approach to efficient attention.
Paper: Longformer: The Long-Document Transformer, Iz Beltagy et al. (2020). This paper generalizes efficient long-context modeling by combining local windowed attention with task-specific global attention.
Paper: Synthesizer: Rethinking Self-Attention for Transformer Models, Yi Tay et al. (2021). This research continues the investigation into whether dot-product self-attention is truly necessary by proposing synthetic attention mechanisms.
Paper: FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, Tri Dao et al. (2022). This work tackles the quadratic memory bottleneck from an IO-aware exact-attention perspective, complementing low-rank approximation methods.

Cover for Linformer: Self-Attention with Linear Complexity

Abstract

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.

Topics

attention mechanism encoder-decoder linear complexity natural language understanding

Keywords

linear self-attention Linformer model linear complexity dot-product attention low-rank matrix linear projection inference-time efficiency space complexity

1 Introduction
2 Backgrounds and Related works
2.1 Transformer and Self-Attention
2.2 Related works
3 Self-Attention is Low Rank
4 Model
5 Experiments
5.1 Pretraining Perplexities
5.2 Downstream Results
5.3 Inference-time Efficiency Results
6 Conclusion
References
A Proof of Theorem 1
B Proof of Theorem 2

Knowls

Knowl 1 — Linformer Multi-Head Linear Self-Attention Mechanism
model/method
The Linformer modifies standard Multi-Head Self-Attention (MHA) by projecting the sequence length dimension of the key and value representations to a lower-dimensional subspace $k \ll n$ .

Given input embedding matrices $Q, K, V \in \mathbb{R}^{n \times d_m}$ for sequence length $n$ and embedding dimension $d_m$ , head projection matrices $W_i^Q, W_i^K \in \mathbb{R}^{d_m \times d_k}$ , $W_i^V \in \mathbb{R}^{d_m \times d_v}$ , and output matrix $W^O \in \mathbb{R}^{h d_v \times d_m}$ for $h$ attention heads (setting $d_k = d_v = d$ ), the Linformer introduces two linear projection matrices $E_i, F_i \in \mathbb{R}^{n \times k}$ per head $i$ :

$\text{head}_i = \text{Attention}(Q W_i^Q, E_i K W_i^K, F_i V W_i^V) = \text{softmax}\left( \frac{Q W_i^Q (E_i K W_i^K)^T}{\sqrt{d}} \right) F_i V W_i^V$

$\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, \text{head}_2, \dots, \text{head}_h) W^O$

The context mapping matrix $\bar{P}_i = \text{softmax}\left( \frac{Q W_i^Q (E_i K W_i^K)^T}{\sqrt{d}} \right)$ has dimensions $n \times k$ , and the projected value layer $F_i V W_i^V$ has dimensions $k \times d$ . Computing each head requires $O(n k d)$ time and space complexity instead of $O(n^2 d)$ . When $k$ is chosen to be constant with respect to $n$ , the overall self-attention mechanism operates in $O(n)$ time and memory.
Knowl 2 — Low-Rank Approximability of the Transformer Self-Attention Matrix
theoretical result
Let $Q, K, V \in \mathbb{R}^{n \times d}$ and $W_i^Q, W_i^K, W_i^V \in \mathbb{R}^{d \times d}$ . Define the standard self-attention context mapping matrix as:

$P = \text{softmax}\left( \frac{Q W_i^Q (K W_i^K)^T}{\sqrt{d}} \right) = \exp(A) \cdot D_A^{-1}$

where $A = Q W_i^Q (K W_i^K)^T / \sqrt{d} \in \mathbb{R}^{n \times n}$ and $D_A \in \mathbb{R}^{n \times n}$ is a diagonal normalization matrix with $(D_A)_{ii} = \sum_{j=1}^n \exp(A_{ji})$ .

For any column vector $w \in \mathbb{R}^n$ of matrix $V W_i^V$ and any error parameter $\epsilon > 0$ , there exists a low-rank matrix $\tilde{P} \in \mathbb{R}^{n \times n}$ with $\text{rank}(\tilde{P}) = \Theta(\log(n))$ such that:

$\Pr\left( \|\tilde{P} w^T - P w^T\| < \epsilon \|P w^T\| \right) > 1 - o(1)$

Specifically, $\tilde{P}$ can be constructively defined as $\tilde{P} = \exp(A) D_A^{-1} R^T R$ , where $R \in \mathbb{R}^{k \times n}$ is a random projection matrix with i.i.d. Gaussian entries drawn from $\mathcal{N}(0, 1/k)$ and projected dimension $k = \frac{5\log(n)}{\epsilon^2 - \epsilon^3}$ .
Knowl 3 — Linear Self-Attention Error Bound and Sequence-Length Independence
theoretical result
Let $Q_i, K_i, V_i \in \mathbb{R}^{n \times d}$ and projection matrices $W_i^Q, W_i^K, W_i^V \in \mathbb{R}^{d \times d}$ , where $d$ is the projection hidden dimension.

For any row vector $w \in \mathbb{R}^n$ of the scaled query-key matrix $Q_i W_i^Q (K_i W_i^K)^T / \sqrt{d}$ and any approximation error tolerance $\epsilon \in (0, 1)$ , if the projected sequence dimension satisfies:

$k = \min\left\{ \Theta\left(\frac{9d \log(d)}{\epsilon^2}\right), 5\Theta\left(\frac{\log(n)}{\epsilon^2}\right) \right\}$

then there exist linear projection matrices $E_i, F_i \in \mathbb{R}^{n \times k}$ such that:

$\Pr\left( \|\text{softmax}(w E_i^T) F_i V_i W_i^V - \text{softmax}(w) V_i W_i^V\| \le \epsilon \|\text{softmax}(w)\| \|V_i W_i^V\| \right) > 1 - o(1)$

Because the rank of $A = Q_i W_i^Q (K_i W_i^K)^T / \sqrt{d}$ is at most $d$ , the projected dimension $k = O(d/\epsilon^2)$ can be selected entirely independent of the input sequence length $n$ while maintaining the bounded relative approximation error $\epsilon$ with high probability.
Knowl 4 — Parameter Sharing Strategies for Linformer Projections
model/method
To reduce the parameter footprint of the linear projection matrices $E_i, F_i \in \mathbb{R}^{n \times k}$ that downsample sequence length $n$ to $k$ , three parameter sharing schemes across attention heads $i \in \{1, \dots, h\}$ and layers $l \in \{1, \dots, L\}$ are defined:
1. Headwise sharing: For each layer, all attention heads share the same projection matrices $E$ and $F$ , setting $E_i = E$ and $F_i = F$ across all heads $i$ , yielding $2$ projection matrices per layer ( $2L$ total).
2. Key-value sharing: Headwise sharing is applied with the additional constraint that key and value projections share the exact same matrix, setting $E_i = F_i = E$ for all heads $i$ , yielding $1$ projection matrix per layer ( $L$ total).
3. Layerwise sharing: A single projection matrix $E \in \mathbb{R}^{n \times k}$ is shared across all $L$ layers, all attention heads $i$ , and both key and value projections, setting $E_i^{(l)} = F_i^{(l)} = E$ for all $l \in \{1, \dots, L\}$ and $i \in \{1, \dots, h\}$ , adding only $1$ projection matrix to the entire model.
For an $L=12$ layer, $h=12$ head Transformer model, unshared Linformer requires $2 \times 12 \times 12 = 288$ projection matrices, whereas headwise, key-value, and layerwise sharing require 24, 12, and 1 matrices, respectively.
Knowl 5 — Long-Tail Spectrum Distribution and Layerwise Rank Decline in Self-Attention
empirical result
Singular value decomposition (SVD) of the self-attention context mapping matrix $P \in \mathbb{R}^{n \times n}$ (evaluated with sequence length $n = 512$ ) in pretrained RoBERTa-base (12 layers) and RoBERTa-large (24 layers) on Wiki103 (masked language modeling) and IMDB (classification) across 10,000 sentences reveals two core spectral properties:
1. Long-tail spectrum: The normalized cumulative singular value distribution exhibits a long-tail profile across all layers, heads, and tasks. Most of the information in $P$ is concentrated in the first few singular values; at the 128th largest singular value (out of 512), cumulative normalized singular values reach between 0.88 and 0.96 across all heads.
2. Layerwise rank decline: Deeper layers exhibit a more heavily skewed singular value distribution than shallower layers. In higher layers, a larger proportion of total singular value mass is concentrated in the top singular values, showing that the effective rank of $P$ decreases as network depth increases.

Knowl 6 — Per-Layer Complexity and Sequential Operations Comparison of Transformer Architectures

data/table

The table below compares the per-layer asymptotic time complexity and the minimum number of sequential operations as a function of sequence length $n$ across recurrent and self-attention architectures:

Model Architecture	Complexity per Layer	Sequential Operation
Recurrent	$O(n)$	$O(n)$
Transformer (Vaswani et al., 2017)	$O(n^2)$	$O(1)$
Sparse Transformer (Child et al., 2019)	$O(n\sqrt{n})$	$O(1)$
Reformer (Kitaev et al., 2020)	$O(n\log(n))$	$O(\log(n))$
Linformer	$O(n)$	$O(1)$

Standard self-attention computes an $n \times n$ pairwise matrix with $O(n^2)$ complexity in $O(1)$ sequential operations. Sparse attention reduces computation to $O(n\sqrt{n})$ at the cost of downstream accuracy. The Reformer uses locality-sensitive hashing (LSH) to achieve $O(n\log(n))$ complexity but introduces $O(\log(n))$ sequential steps. Linformer achieves $O(n)$ time complexity per layer while maintaining $O(1)$ parallelizable sequential operations.

Knowl 7 — Linformer Pretraining Convergence Across Sequence Lengths and Dimension Projections
empirical result
Linformer models pretrained with the masked-language-modeling (MLM) objective on BookCorpus plus English Wikipedia (3.3 billion words) across 64 Tesla V100 GPUs for 250,000 updates demonstrate the following:
1. Effect of projected dimension $k$ : For a fixed sequence length $n$ , validation perplexity improves as projected dimension $k$ increases. At $n = 512$ , Linformer with $k = 128$ approaches standard Transformer perplexity, while $k = 256$ matches it. At $n = 1024$ , Linformer with $k = 256$ matches standard Transformer validation perplexity.
2. Parameter sharing equivalence: Layerwise sharing (a single shared projection matrix across all layers and heads) achieves validation perplexity curves nearly identical to headwise and key-value sharing for $n = 512$ , showing that parameter count can be reduced with negligible impact on pretraining loss.
3. Sequence length invariance: When fixing the projected dimension at $k = 256$ and scaling sequence length $n \in \{512, 1024, 2048, 4096\}$ , converged validation perplexity remains virtually constant, demonstrating that model capacity depends on $k$ rather than the compression ratio $n/k$ or sequence length $n$ .

Knowl 8 — Downstream Natural Language Understanding Performance of Linformer

data/table

Linformer models pretrained with the MLM objective for 250k updates were finetuned and evaluated on the development sets of SST-2, IMDB, QNLI, and QQP, compared against RoBERTa-base, BERT-base, and 6-layer DistilBERT:

$n$	Model	SST-2	IMDB	QNLI	QQP	Average
512	RoBERTa-base	93.1	94.1	90.9	90.9	92.25
512	Linformer, $k=128$	92.4	94.0	90.4	90.2	91.75
512	Linformer, $k=128$ , shared kv	93.4	93.4	90.3	90.3	91.85
512	Linformer, $k=128$ , shared kv, layer	93.2	93.8	90.1	90.2	91.83
512	Linformer, $k=256$	93.2	94.0	90.6	90.5	92.08
512	Linformer, $k=256$ , shared kv	93.3	93.6	90.6	90.6	92.03
512	Linformer, $k=256$ , shared kv, layer	93.1	94.1	91.2	90.8	92.30
512	BERT-base	92.7	93.5	91.8	89.6	91.90
512	Distilled BERT	91.3	92.8	89.2	88.5	90.45
1024	Linformer, $k=256$	93.0	93.8	90.4	90.4	91.90
1024	Linformer, $k=256$ , shared kv	93.0	93.6	90.3	90.4	91.83
1024	Linformer, $k=256$ , shared kv, layer	93.2	94.2	90.8	90.5	92.18

Linformer ( $n = 512, k = 256$ , shared kv, layer) achieves an average score of 92.30, slightly outperforming RoBERTa-base (92.25), BERT-base (91.90), and Distilled BERT (90.45). Layerwise sharing yields the highest average accuracy among parameter sharing strategies. When pretrained with $n = 1024$ and $k = 256$ , Linformer achieves 92.18 average accuracy, confirming that performance depends primarily on $k$ rather than $n/k$ .

Knowl 9 — Inference Time Speedup and Memory Savings of Linformer

data/table

Inference efficiency of Linformer (with layerwise sharing) was benchmarked against the standard Transformer on a 16GB Tesla V100 GPU across sequence lengths $n \in [512, 65536]$ and projected dimensions $k \in [128, 2048]$ . Batch sizes were set to the maximum that fit in memory, and memory savings represent the relative increase in maximum batch size:

	Time Speedup (relative to Transformer)					Memory Savings (relative to Transformer)
$n$	$k=128$	$k=256$	$k=512$	$k=1024$	$k=2048$	$k=128$	$k=256$	$k=512$	$k=1024$	$k=2048$
512	1.5 $\times$	1.3 $\times$	-	-	-	1.7 $\times$	1.5 $\times$	-	-	-
1024	1.7 $\times$	1.6 $\times$	1.3 $\times$	-	-	3.0 $\times$	2.9 $\times$	1.8 $\times$	-	-
2048	2.6 $\times$	2.4 $\times$	2.1 $\times$	1.3 $\times$	-	6.1 $\times$	5.6 $\times$	3.6 $\times$	2.0 $\times$	-
4096	3.4 $\times$	3.2 $\times$	2.8 $\times$	2.2 $\times$	1.3 $\times$	14 $\times$	13 $\times$	8.3 $\times$	4.3 $\times$	2.3 $\times$
8192	5.5 $\times$	5.0 $\times$	4.4 $\times$	3.5 $\times$	2.1 $\times$	28 $\times$	26 $\times$	17 $\times$	8.5 $\times$	4.5 $\times$
16384	8.6 $\times$	7.8 $\times$	7.0 $\times$	5.6 $\times$	3.3 $\times$	56 $\times$	48 $\times$	32 $\times$	16 $\times$	8 $\times$
32768	13 $\times$	12 $\times$	11 $\times$	8.8 $\times$	5.0 $\times$	56 $\times$	48 $\times$	36 $\times$	18 $\times$	16 $\times$
65536	20 $\times$	18 $\times$	16 $\times$	14 $\times$	7.9 $\times$	60 $\times$	52 $\times$	40 $\times$	20 $\times$	18 $\times$

At $n = 512, k = 128$ , Linformer achieves a $1.5\times$ speedup and $1.7\times$ memory savings over the standard Transformer. At $n = 65536, k = 128$ , Linformer achieves a $20\times$ inference speedup and a $60\times$ memory saving. As sequence length increases, standard Transformer inference time grows quadratically while Linformer inference time remains nearly flat.

Knowl 10 — Architectural Extensions for Linformer Projections
model/method
In addition to uniform linear projection matrices, the Linformer design accommodates non-uniform dimension allocation and alternative projection operators:
1. Nonuniform projected dimension: Because higher Transformer layers have lower effective attention rank (more skewed singular value spectrum), the projected dimension $k$ can be set non-uniformly across layers, choosing smaller $k$ for deeper layers and larger $k$ for shallower layers.
2. General projection operators: The linear projection matrices $E, F \in \mathbb{R}^{n \times k}$ $E, F \in R^{n \times k}$ can be replaced with other low-dimensional projection mechanisms:
  - Mean pooling or max pooling along the sequence length dimension with pooling factor $n/k$ .
  - Trainable 1D convolution along the sequence length dimension with kernel size and stride set to $n/k$ .

Coverage note — All substantial contributed material—including the low-rank attention theory (Theorems 1 and 2), linear self-attention mechanism, parameter sharing strategies, projection extensions, spectrum analysis, pretraining perplexities, GLUE/IMDB downstream results, and inference speed/memory benchmarks—has been captured. Intermediate proof steps (Appendices A and B) were omitted to focus on standalone theoretical results.

References

1.Rosa I Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine Learning, 63(2):161–182, 2006.
2.Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020.
3.Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005.14165, 2020.
4.Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cost. arXiv preprint arXiv:1604.06174, 2016.
5.Zihan Chen, Hongbo Zhang, Xiaoji Zhang, and Leqi Zhao. Quora question pairs, 2018.
6.Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019.
7.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171–4186, 2019.
8.Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.
9.Angela Fan, Pierre Stock, Benjamin Graham, Edouard Grave, Remi Gribonval, Herve Jegou, and Armand Joulin. Training with quantization noise for extreme fixed-point compression. arXiv preprint arXiv:2004.07320, 2020.
10.Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015.
11.Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. In Advances in Neural Information Processing Systems, pp. 103–112, 2019.
12.Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2704–2713, 2018.
13.Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
14.Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. ACL, 2019.
15.W Johnson J Lindenstrauss. Extensions of lipschitz maps into a hilbert space. Contemp. Math, 26: 189–206, 1984.
16.Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692, 2019.
17.Andrew L Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies-volume 1, pp. 142–150. Association for Computational Linguistics, 2011.
18.Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv:1609.07843, 2016.
19.Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training. arXiv preprint arXiv:1710.03740, 2017.
20.Abdelrahman Mohamed, Dmytro Okhonko, and Luke Zettlemoyer. Transformers with convolutional context for asr. arXiv preprint arXiv:1904.11660, 2019.
21.Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 1–9, 2018.
22.Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations), pp. 48–53, 2019.
23.Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint arXiv:1911.02972, 2019.
24.Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAI Blog, 1(8):9, 2019.
25.Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683, 2019.
26.Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383–2392, 2016.
27.Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108, 2019.
28.Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pp. 1631–1642, 2013.
29.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998–6008, 2017.
30.Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. CoRR, abs/1804.07461, 2018. URL http://arxiv.org/abs/1804.07461.
31.Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pp. 19–27, 2015.

Citation

MLA

Wang, S., et al. “Linformer: Self-Attention with Linear Complexity”. arXiv, 2020, https://doi.org/10.48550/arxiv.2006.04768.

APA

Wang, S., Li, B. Z., Khabsa, M., Fang, H., & Ma, H. (2020). Linformer: Self-Attention with Linear Complexity. arXiv. https://doi.org/10.48550/arxiv.2006.04768

Chicago

Wang, S., B. Z. Li, M. Khabsa, H. Fang, and H. Ma. 2020. “Linformer: Self-Attention with Linear Complexity”. Preprint, ArXiv. https://doi.org/10.48550/arxiv.2006.04768.

Harvard

Wang, S. et al. (2020) “Linformer: Self-Attention with Linear Complexity”. arXiv. Available at: https://doi.org/10.48550/arxiv.2006.04768.

Vancouver

1. Wang S, Li BZ, Khabsa M, Fang H, Ma H (2020) Linformer: Self-Attention with Linear Complexity. https://doi.org/10.48550/arxiv.2006.04768

BibTeX

@misc{https://doi.org/10.48550/arxiv.2006.04768,
  doi = {10.48550/ARXIV.2006.04768},
  url = {https://arxiv.org/abs/2006.04768},
  author = {Wang, Sinong and Li, Belinda Z. and Khabsa, Madian and Fang, Han and Ma, Hao},
  keywords = {Machine Learning (cs.LG), Machine Learning (stat.ML), FOS: Computer and information sciences, FOS: Computer and information sciences},
  title = {Linformer: Self-Attention with Linear Complexity},
  publisher = {arXiv},
  year = {2020},
  copyright = {arXiv.org perpetual, non-exclusive license}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Linformer: Self-Attention with Linear Complexity

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Linformer Multi-Head Linear Self-Attention Mechanism

Knowl 2 — Low-Rank Approximability of the Transformer Self-Attention Matrix

Knowl 3 — Linear Self-Attention Error Bound and Sequence-Length Independence

Knowl 4 — Parameter Sharing Strategies for Linformer Projections

Knowl 5 — Long-Tail Spectrum Distribution and Layerwise Rank Decline in Self-Attention

Knowl 6 — Per-Layer Complexity and Sequential Operations Comparison of Transformer Architectures

Knowl 7 — Linformer Pretraining Convergence Across Sequence Lengths and Dimension Projections

Knowl 8 — Downstream Natural Language Understanding Performance of Linformer

Knowl 9 — Inference Time Speedup and Memory Savings of Linformer

Knowl 10 — Architectural Extensions for Linformer Projections

References

Citation

BibTeX

Source Code

Access the Paper