# Subquadratic Algorithms and Hardness for Attention with Any Temperature

arXiv: https://arxiv.org/abs/2505.14840 · HTML: https://mlsanity.com/paper/2505.14840/

## 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 (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Understanding the Behaviour of Contrastive Loss](https://mlsanity.com/paper/2012.09740/) (2020)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Can contrastive learning avoid shortcut solutions?](https://mlsanity.com/paper/2106.11230/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [AdCo: Adversarial Contrast for Efficient Learning of Unsupervised Representations from Self-Trained Negative Adversaries](https://mlsanity.com/paper/2011.08435/) (2020)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Temperature Schedules for Self-Supervised Contrastive Methods on Long-Tail Data](https://mlsanity.com/paper/2303.13664/) (2023)
- [Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models](https://mlsanity.com/paper/2304.02207/) (2023)
- [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels](https://mlsanity.com/paper/2310.01655/) (2023)
- [Temperature check: theory and practice for training models with softmax-cross-entropy losses](https://mlsanity.com/paper/2010.07344/) (2020)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2205.06249/) (2022)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Trainable Transformer in Transformer](https://mlsanity.com/paper/2307.01189/) (2023)
- [On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product](https://mlsanity.com/paper/1802.02325/) (2018)

## Built on by (most cited first, 5 of 5)

- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Towards Tight Bounds for Streaming Attention](https://mlsanity.com/paper/2606.07205/) (2026)
- [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026)
- [Efficiently Approximating Attention Is Hard](https://mlsanity.com/paper/2609.37261/) (2026)

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