mlsanityData to 14 Oct 2026

Subquadratic Algorithms and Hardness for Attention with Any Temperature

arXiv 2505.14840 ↗First posted 20 May 2025cs.LG cs.CCcited by 5

Not on the map. Why?

Abstract (arXiv)

Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length n. Alman and Song [NeurIPS 2023] showed that when the head dimension d = Theta(log n), subquadratic Attention is possible if and only if the inputs have small entries bounded by B = o(√log n) in absolute values, under the Strong Exponential Time Hypothesis (mathsfSETH). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for d=Theta(log n). Running times of these algorithms depend exponentially on B and thus they do not lead to even a polynomial-time algorithm outside the specific range of B. This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size B? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant d = O(1), we give the first subquadratic tildeO(n2 - 1/d · polylog(B)) time algorithm for Attention with large B. Our result holds even for matrices with large head dimension if they have low rank. In this regime, we also give a similar running time for Attention gradient computation, and therefore for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when d = 2Theta(log^* n), Attention requires n2 - o(1) time under mathsfSETH. Finally, in the regime where d = poly(n), we show that the standard algorithm is optimal under popular fine-grained complexity assumptions.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 37 of its 55 references that are in the map. First posted on arXiv 20 May 2025.

Builds on

37 of 55 references.

References · 37

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  4. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  5. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  6. 2020Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hyperspherecited by 1,405
  7. 2020Understanding the Behaviour of Contrastive Losscited by 398
  8. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  9. 2022On The Computational Complexity of Self-Attentioncited by 139
  10. 2023Representational Strengths and Limitations of Transformerscited by 133
  11. 2021Can contrastive learning avoid shortcut solutions?cited by 114
  12. 2023Fast Attention Requires Bounded Entriescited by 102
25 more
  1. 2020AdCo: Adversarial Contrast for Efficient Learning of Unsupervised Representations from Self-Trained Negative Adversariescited by 90
  2. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  3. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  4. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 67
  5. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  6. 2023Temperature Schedules for Self-Supervised Contrastive Methods on Long-Tail Datacited by 44
  7. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  8. 2023PolySketchFormer: Fast Transformers via Sketching Polynomial Kernelscited by 36
  9. 2020Temperature check: theory and practice for training models with softmax-cross-entropy lossescited by 31
  10. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  11. 2024More Asymmetry Yields Faster Matrix Multiplicationcited by 27
  12. 2023Differentially Private Attention Computationcited by 25
  13. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  14. 2022Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimationcited by 19
  15. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  16. 2023Beyond Classical Attention: Quantum Attention for Scalable Computationcited by 18
  17. 2023Trainable Transformer in Transformercited by 17
  18. 2018On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Productcited by 12
  19. 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
  20. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  21. 2025Exploring the Impact of Temperature Scaling in Softmax for Classification and Adversarial Robustnesscited by 9
  22. 2023Dynamically Scaled Temperature in Self-Supervised Contrastive Learningcited by 4
  23. 2013Faster all-pairs shortest paths via circuit complexitycited by 2
  24. 2024Finer-Grained Hardness of Kernel Density Estimationcited by 2
  25. 2021Approximation Algorithms for Min-Distance Problems in DAGscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  2. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  3. 2026Towards Tight Bounds for Streaming Attentioncited by 2
  4. 2026On the Computational Hardness of Transformerscited by 0
  5. 2026Efficiently Approximating Attention Is Hardcited by 0