Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
PreprintCited by 90Complexity and Algorithms in GraphsTopic ModelingAlgorithms and Data Compression

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

On The Computational Complexity of Self-Attention

Open access
Keles, Feyza Duman, Wijewardena, Pruthuvi Mahesakya, Hegde, Chinmay·2022·arXiv
DOI 10.48550/arxiv.2209.04881arXiv 2209.04881
Open this paper in CoChat — free accountOpen PDF

Abstract

Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the input. Several approaches have been proposed to speed up self-attention mechanisms to achieve sub-quadratic running time; however, the large majority of these works are not accompanied by rigorous error guarantees. In this work, we establish lower bounds on the computational complexity of self-attention in a number of scenarios. We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false. This argument holds even if the attention computation is performed only approximately, and for a variety of attention mechanisms. As a complement to our lower bounds, we show that it is indeed possible to approximate dot-product self-attention using finite Taylor series in linear-time, at the cost of having an exponential dependence on the polynomial order.

Overview

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.2209.04881

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

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?

Self-check

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

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

Citations

Cites

Show all 1 references

Research works printed but not linked: 40

  1. [1][1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, 'Attention is all you need,' Advances in neural information processing systems , vol. 30, 2017. -
  2. [2][2] J. D. M.-W. C. Kenton and L. K. Toutanova, 'Bert: Pre-training of deep bidirectional transformers for language understanding,' in Proceedings of NAACL-HLT , 2019, pp. 4171-4186. -
  3. [3][3] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly et al. , 'An image is worth 16x16 words: Transformers for image recognition at scale,' in International Conference on Learning Representations , 2021. -
  4. [4][4] S. Khan, M. Naseer, M. Hayat, S. W. Zamir, F. S. Khan, and M. Shah, 'Transformers in vision: A survey,' ACM Computing Surveys (CSUR) , 2021. -
  5. [5][5] J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko et al. , 'Highly accurate protein structure prediction with alphafold,' Nature , vol. 596, no. 7873, pp. 583-589, 2021. -
  6. [6][6] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman et al. , 'Evaluating large language models trained on code,' CoRR , 2021. -
  7. [7][7] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark et al. , 'Learning transferable visual models from natural language supervision,' in International Conference on Machine Learning . PMLR, 2021, pp. 8748-8763. -
  8. [8][8] J.-B. Alayrac, J. Donahue, P. Luc, A. Miech, I. Barr, Y. Hasson, K. Lenc, A. Mensch, K. Millican, M. Reynolds et al. , 'Flamingo: a visual language model for few-shot learning,' arXiv preprint arXiv:2204.14198 , 2022. - · arXiv
  9. [9][9] N. Kitaev, L. Kaiser, and A. Levskaya, 'Reformer: The efficient transformer,' in International Conference on Learning Representations , 2020. -
  10. [10][10] M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang et al. , 'Big bird: Transformers for longer sequences,' Advances in Neural Information Processing Systems , vol. 33, pp. 17 283-17 297, 2020. -
  11. [12][12] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, 'Transformers are rnns: Fast autoregressive transformers with linear attention,' in International Conference on Machine Learning . PMLR, 2020, pp. 5156-5165. -
  12. [13][13] J. Lu, J. Yao, J. Zhang, X. Zhu, H. Xu, W. Gao, C. XU, T. Xiang, and L. Zhang, 'Soft: Softmax-free transformer with linear complexity,' in Advances in Neural Information Processing Systems , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 21 297-21 309. -
  13. [14][14] Y. Chen, Q. Zeng, H. Ji, and Y. Yang, 'Skyformer: Remodel self-attention with gaussian kernel and nystr \ " om method,' Advances in Neural Information Processing Systems , vol. 34, 2021. -
  14. [15][15] A. Backurs and P. Indyk, 'Edit distance cannot be computed in strongly subquadratic time (unless seth is false),' in Proceedings of the forty-seventh annual ACM symposium on Theory of computing , 2015, pp. 51-58. -
  15. [16][16] K. Bringmann, 'Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails,' in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science . IEEE, 2014, pp. 661-670. -
  16. [17][17] K. Bringmann and M. Künnemann, 'Quadratic conditional lower bounds for string problems and dynamic time warping,' in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . IEEE, 2015, pp. 79-97. -
  17. [18][18] K. Bringmann, 'Fine-grained complexity theory: Conditional lower bounds for computational geometry,' in Conference on Computability in Europe . Springer, 2021, pp. 60-70. -
  18. [19][19] A. Backurs, P. Indyk, and L. Schmidt, 'On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks,' Advances in Neural Information Processing Systems , vol. 30, 2017. -
  19. [20][20] A. Rubinstein, 'Hardness of approximate nearest neighbor search,' in Proceedings of the 50th annual ACM SIGACT symposium on theory of computing , 2018, pp. 1260-1268. -
  20. [21][21] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell et al. , 'Language models are few-shot learners,' Advances in neural information processing systems , vol. 33, pp. 1877-1901, 2020. -
  21. [22][22] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, 'Swin transformer: Hierarchical vision transformer using shifted windows,' in Proceedings of the IEEE/CVF International Conference on Computer Vision , 2021, pp. 10 012-10 022. -
  22. [23][23] C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar, 'Are transformers universal approximators of sequence-to-sequence functions?' in International Conference on Learning Representations , 2019. -
  23. [24][24] Y. Dong, J.-B. Cordonnier, and A. Loukas, 'Attention is not all you need: Pure attention loses rank doubly exponentially with depth,' in International Conference on Machine Learning . PMLR, 2021, pp. 2793-2803. -
  24. [25][25] H. Kim, G. Papamakarios, and A. Mnih, 'The lipschitz constant of self-attention,' in International Conference on Machine Learning . PMLR, 2021, pp. 5562-5571. -
  25. [26][26] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma, 'Linformer: Self-attention with linear complexity,' arXiv preprint arXiv:2006.04768 , 2020. - · arXiv
  26. [27][27] I. Beltagy, M. E. Peters, and A. Cohan, 'Longformer: The long-document transformer,' CoRR , vol. abs/2004.05150, 2020. - · arXiv
  27. [28][28] A. Roy, M. Saffar, A. Vaswani, and D. Grangier, 'Efficient content-based sparse attention with routing transformers,' Transactions of the Association for Computational Linguistics , vol. 9, pp. 53-68, 2021. -
  28. [29][29] Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh, 'Nyströmformer: A nyström-based algorithm for approximating self-attention,' in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 35, no. 16, 2021, pp. 14 138-14 148. -
  29. [30][30] V. Likhosherstov, K. M. Choromanski, J. Q. Davis, X. Song, and A. Weller, 'Sub-linear memory: How to make performers slim,' Advances in Neural Information Processing Systems , vol. 34, 2021. -
  30. [31][31] H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. Smith, and L. Kong, 'Random feature attention,' in International Conference on Learning Representations , 2021. -
  31. [32][32] S. Bhojanapalli, A. Chakrabarti, A. Veit, M. Lukasik, H. Jain, F. Liu, Y.-W. Chang, and S. Kumar, 'Leveraging redundancy in attention with reuse transformers,' arXiv preprint arXiv:2110.06821 , 2021. - · arXiv
  32. [33][33] R. Impagliazzo and R. Paturi, 'On the complexity of k-sat,' Journal of Computer and System Sciences , vol. 62, no. 2, pp. 367-375, 2001. -
  33. [34][34] R. Impagliazzo, R. Paturi, and F. Zane, 'Which problems have strongly exponential complexity?' Journal of Computer and System Sciences , vol. 63, no. 4, p. 512-530, 2001. -
  34. [35][35] P. Indyk, 'Beyond p vs. np: quadratic-time hardness for big data problems,' in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures , 2017, pp. 1-1. -
  35. [36][36] A. Rubinstein and V. V. Williams, 'Seth vs approximation,' ACMSIGACT News , vol. 50, no. 4, pp. 57-76, 2019. -
  36. [37][37] A. Abboud, A. Backurs, and V. V. Williams, 'Tight hardness results for lcs and other sequence similarity measures,' in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . IEEE, 2015, pp. 59-78. -
  37. [38][38] K. Bringmann and A. Nusser, 'Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation,' in 37th International Symposium on Computational Geometry , 2021. -
  38. [39][39] A. Abboud, A. Backurs, and V. V. Williams, 'If the current clique algorithms are optimal, so is valiant's parser,' SIAM Journal on Computing , vol. 47, no. 6, pp. 2527-2555, 2018. -
  39. [40][40] A. Abboud, V. Cohen-Addad, and H. Houdrougé, 'Subquadratic high-dimensional hierarchical clustering,' Advances in Neural Information Processing Systems , vol. 32, 2019. -
  40. [41][41] R. Williams, 'A new algorithm for optimal 2-constraint satisfaction and its implications,' Theoretical Computer Science , vol. 348, no. 2, pp. 357-365, 2005.

Cited by

See all 90

Metadata

Authors
Keles, F. D., Wijewardena, P. M., & Hegde, C.
Affiliations
Microsoft (United States) (US)
ORCID
Hegde, Chinmay
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2209.04881
arXiv
2209.04881
OpenAlex
W4295689449
Cited by
90
References
1
Citations by year
2026: 3 · 2025: 47 · 2024: 33 · 2023: 7
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by-sa/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
Keywords
self-attention, computational complexity, lower bounds, Strong Exponential Time Hypothesis, dot-product attention, Taylor series expansion, linear-time approximation, transformer models

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: On The Computational Complexity of Self-Attention. https://app.cochat.ai/papers/10.48550/arxiv.2209.04881
The paper
Keles, F. D., Wijewardena, P. M., & Hegde, C. (2022). On The Computational Complexity of Self-Attention. arXiv. https://doi.org/10.48550/arxiv.2209.04881

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.