PreprintCited by 855Topic ModelingNatural Language Processing TechniquesAdvanced Neural Network Applications

Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention

Open access
Katharopoulos, Angelos, Vyas, Apoorv, Pappas, Nikolaos, Fleuret, François·2020·arXiv

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2006.16236

Cites

0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Despite efficiency and ability to scale to longer context, linear Transformers do not show competitive performance compared to Transformers because the kernel trick makes the model a linear recurrent network that compresses data into matrix-valued states.

    “Despite efficiency and the ability to scale to longer context, linear Transformers do not show competitive performance compared to Transformers as the kernel trick makes the model a linear recurrent network, in which the data is compressed into a matrix-valued states (Katharopoulos et al. 2020).”

    From Titans: Learning to Memorize at Test Time (2025) · cites this paper as Katharopoulos et al. 2020

    Split into 2 atoms — 0 confirmed, 1 partially supported, 1 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured
  • Approximate attention methods reduce compute complexity by trading off model quality but often do not achieve wall-clock speedup.

    “Approximate attention methods have attempted to address this problem by trading off model quality to reduce the compute complexity, but often do not achieve wall-clock speedup.”

    From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [50]

    The Introduction (p. 1) says sparse attention and locality-sensitive hashing reduce computational complexity but do not speed up autoregressive inference. That supports the speed claim only for that setting: the paper also says these methods can be trained efficiently on long sequences, and it does not establish a general trade-off in model quality. (LLM, conf=0.86)

    Experimental — accuracy not yet measured
  • Linear RNNs use a vector-valued memory while linear Transformers use a matrix-valued memory.

    “While both linear Transformers and linear RNNs (including state space models) compress the information in memory update step, the critical difference lies in the structure of the memory, where linear RNNs (vs. linear Transformers) use a vector-valued memory (vs. matrix-valued memory).”

    From Titans: Learning to Memorize at Test Time (2025) · cites this paper as Katharopoulos et al. 2020

    Section 3.3.2 (p. 4) says the linear Transformer stores a matrix as its internal state, supporting the matrix-valued-memory half of the claim. Section 3.4 (p. 5) describes that same Transformer as an RNN with two hidden states; it does not establish that linear RNNs, including state space models, generally use vector-valued memory. (LLM, conf=0.84)

    Experimental — accuracy not yet measured
  • Current large language models exhibit remarkable single-turn capabilities but suffer from severe limitations in maintaining coherent, personalized interactions over extended temporal horizons (the 'goldfish problem').

    “Current large language models (LLMs) exhibit remarkable single-turn capabilities but suffer from severe limitations in maintaining coherent, personalized interactions over extended temporal horizons a phenomenon we term the 'goldfish problem.'”

    From From Goldfish to Elephant: Long-Term Memory for Large Language Models via Selective Storage and Hierarchical Compression (2026) · cites this paper as [5]

    The Introduction (p. 1) says transformers perform impressively on various tasks, but limited context can disrupt temporal coherence and hinder long-term dependencies. It does not assess single-turn versus extended interactions or whether models maintain personalization across them; the 'goldfish problem' is the citing authors’ term. (LLM, conf=0.87)

    Experimental — accuracy not yet measured
  • In linear Transformer (or FWP) with zero initial memory state, the stored knowledge of a lower level (fast weight) directly affects the output of the model in another level.

    “As an example of this type of knowledge transfer, in linear Transformer (or FWP) (Katharopoulos et al. 2020; Schlag et al. 2021), where the initial memory state is zero, the stored knowledge of a lower level (fast weight) directly affect the output of the model in another level.”

    From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Katharopoulos et al. 2020

    Algorithm 1 (p. 5) initializes the attention state S to zero, updates it with key–value information, and uses S to compute the output. Section 3.4 (p. 5) likewise describes attention memory as a recurrent hidden state. Our copy does not identify that state as a “fast weight” or describe its stored information as directly affecting the output of another level, so the cross-level claim is not fully supported. (LLM, conf=0.81)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 34

  1. Bahdanau, D., Cho, K., and Bengio, Y. Neural machine translation by jointly learning to align and translate. In Proceedings of the 5th International Conference on Learning Representations , San Diego, CA, USA, 2015.
  2. Blanc, G. and Rendle, S. Adaptive sampled softmax with kernel based sampling. arXiv preprint arXiv:1712.00527 , 2017. · arXiv
  3. Child, R., Gray, S., Radford, A., and Sutskever, I. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509 , 2019. · arXiv
  4. Clark, K., Luong, M.-T., Le, Q. V., and Manning, C. D. ELECTRA: Pre-training text encoders as discriminators rather than generators. In International Conference on Learning Representations , 2020.
  5. Clevert, D.-A., Unterthiner, T., and Hochreiter, S. Fast and accurate deep network learning by exponential linear units (ELUs). arXiv preprint arXiv:1511.07289 , 2015. · arXiv
  6. Cordonnier, J.-B., Loukas, A., and Jaggi, M. On the relationship between self-attention and convolutional layers. In International Conference on Learning Representations , 2020.
  7. Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q., and Salakhutdinov, R. Transformer-XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics , pp. 2978-2988, Florence, Italy, July 2019. Association for Computational Linguistics.
  8. Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, Ł. Universal transformers. arXiv preprint arXiv:1807.03819 , 2018. · arXiv
  9. Goodman, J. Classes for fast maximum entropy training. In 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. 01CH37221) , volume 1, pp. 561-564. IEEE, 2001.
  10. Graves, A., Fern´ andez, S., Gomez, F., and Schmidhuber, J. Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks. In Proceedings of the 23rd international conference on Machine learning , pp. 369-376, 2006.
  11. Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation , 9(8):1735-1780, 1997.
  12. Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014. · arXiv
  13. Kitaev, N., Kaiser, Ł., and Levskaya, A. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451 , 2020. · arXiv
  14. Lample, G., Sablayrolles, A., Ranzato, M. A., Denoyer, L., and Jegou, H. Large memory layers with product keys. In Wallach, H., Larochelle, H., Beygelzimer, A., d ´ Alch´ e-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32 , pp. 85468557. Curran Associates, Inc., 2019.
  15. Lan, Z., Chen, M., Goodman, S., Gimpel, K., Sharma, P., and Soricut, R. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations , 2020.
  16. Liu, L., Jiang, H., He, P., Chen, W., Liu, X., Gao, J., and Han, J. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv:1908.03265 , 2019. · arXiv
  17. Michel, P., Levy, O., and Neubig, G. Are sixteen heads really better than one? In Wallach, H., Larochelle, H., Beygelzimer, A., d' Alch´ e-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32 , pp. 14014-14024. Curran Associates, Inc., 2019.
  18. Mnih, A. and Hinton, G. E. A scalable hierarchical distributed language model. In Advances in neural information processing systems , pp. 1081-1088, 2009.
  19. Morin, F. and Bengio, Y. Hierarchical probabilistic neural network language model. In Aistats , volume 5, pp. 246252. Citeseer, 2005.
  20. Parmar, N., Ramachandran, P., Vaswani, A., Bello, I., Levskaya, A., and Shlens, J. Stand-alone self-attention in vision models. In Wallach, H., Larochelle, H., Beygelzimer, A., d' Alch´ e-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32 , pp. 68-80. Curran Associates, Inc., 2019.
  21. Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems , pp. 8024-8035, 2019.
  22. Paul, D. B. and Baker, J. M. The design for the wall street journal-based csr corpus. In Proceedings of the workshop on Speech and Natural Language , pp. 357-362. Association for Computational Linguistics, 1992.
  23. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. OpenAI Blog , 1(8):9, 2019.
  24. Rawat, A. S., Chen, J., Yu, F. X. X., Suresh, A. T., and Kumar, S. Sampled softmax with random fourier features. In Advances in Neural Information Processing Systems , pp. 13834-13844, 2019.
  25. Salimans, T., Karpathy, A., Chen, X., and Kingma, D. P. Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications. arXiv preprint arXiv:1701.05517 , 2017. · arXiv
  26. Shen, Z., Zhang, M., Zhao, H., Yi, S., and Li, H. Efficient attention: Attention with linear complexities. arXiv preprint arXiv:1812.01243 , 2020. · arXiv
  27. Song, K., Tan, X., Qin, T., Lu, J., and Liu, T.-Y. MASS: Masked sequence to sequence pre-training for language generation. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pp. 5926-5936, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
  28. Sperber, M., Niehues, J., Neubig, G., Stker, S., and Waibel, A. Self-attentional acoustic models. In 19th Annual Conference of the International Speech Communication Association (InterSpeech 2018) , Hyderabad, India, September 2018.
  29. Sukhbaatar, S., Grave, E., Bojanowski, P., and Joulin, A. Adaptive attention span in transformers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics , pp. 331-335, Florence, Italy, July 2019. Association for Computational Linguistics.
  30. Sutskever, I., Vinyals, O., and Le, Q. V. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems 27 , pp. 31043112. Curran Associates, Inc., 2014.
  31. Tsai, Y.-H. H., Bai, S., Yamada, M., Morency, L.-P., and Salakhutdinov, R. Transformer dissection: An unified understanding for transformer's attention via the lens of kernel. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) , pp. 4343-4352, Hong Kong, China, November 2019. Association for Computational Linguistics.
  32. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In NIPS , 2017.
  33. Yang, Z., Dai, Z., Yang, Y., Carbonell, J. G., Salakhutdinov, R., and Le, Q. V. Xlnet: Generalized autoregressive pretraining for language understanding. CoRR , abs/1906.08237, 2019. · arXiv
  34. Zafrir, O., Boudoukh, G., Izsak, P., and Wasserblat, M. Q8BERT: quantized 8bit BERT. CoRR , abs/1910.06188, 2019. · arXiv

Cited by

Sorted by citations

Authors
Katharopoulos, A., Vyas, A., Pappas, N., & Fleuret, F.
Affiliations
  • École Polytechnique Fédérale de Lausanne (CH)
  • Idiap Research Institute (CH)
  • University of Washington (US)
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
1
Pages
5156-5165
ISSN
2331-8422 (ISSN-L)
OpenAlex
W3034573343
Cited by
827
References
0
Citations by year
2026: 5 · 2025: 149 · 2024: 202 · 2023: 188 · 2022: 125 · 2021: 135 · 2020: 23
Type
posted content
Language
en
Open access
Locations
  • arXiv (Cornell University) (submittedVersion)
  • Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion)
  • Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University)
  • International Conference on Machine Learning
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
Keywords
linear transformer, linear attention, self-attention, autoregressive transformers, recurrent neural networks, quadratic complexity, iterative implementation, computational efficiency

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review