Subquadratic Algorithms and Hardness for Attention with Any Temperature

2025/05/20 by Shreya Gupta, Boyang Huang, Gupta, Shreya +7 · 2 citations
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #CCD and CMOS Imaging Sensors #Computational Complexity (cs.CC) #F.2.1 #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2505.14840

openalex publication_date 2025/05/20 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

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 = Θ(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 (SETH). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for d=Θ(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 O(n^{2 - 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 = 2^{Θ(log^* n)}, Attention requires n^{2 - o(1)} time under SETH. Finally, in the regime where d = poly(n), we show that the standard algorithm is optimal under popular fine-grained complexity assumptions.

Citations

• Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
• Exploring the Impact of Temperature Scaling in Softmax for Classification and Adversarial Robustness
• Fundamental Limitations on Subquadratic Alternatives to Transformers
• Finer-Grained Hardness of Kernel Density Estimation
• Understanding Transformer Reasoning Capabilities via Graph Algorithms
• More Asymmetry Yields Faster Matrix Multiplication
• Transformers, parallel computation, and logarithmic depth
• HyperAttention: Long-context Attention in Near-Linear Time
• PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
• A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time
• Solving Attention Kernel Regression Problem via Pre-conditioner
• Dynamically Scaled Temperature in Self-Supervised Contrastive Learning
• Fast Quantum Algorithm for Attention Computation
• Trainable Transformer in Transformer
• Representational Strengths and Limitations of Transformers
• Fine-Tuning Language Models with Just Forward Passes
• Differentially Private Attention Computation
• Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
• Temperature Schedules for Self-Supervised Contrastive Methods on Long-Tail Data
• Fast Attention Requires Bounded Entries
• KDEformer: Accelerating Transformers via Kernel Density Estimation
• On The Computational Complexity of Self-Attention
• Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
• Can contrastive learning avoid shortcut solutions?
• Approximation Algorithms for Min-Distance Problems in DAGs
• Understanding the Behaviour of Contrastive Loss
• Temperature check: theory and practice for training models with softmax-cross-entropy losses
• Big Bird: Transformers for Longer Sequences
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
• Language Models are Few-Shot Learners
• Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere
• A Simple Framework for Contrastive Learning of Visual Representations
• On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
• Attention Is All You Need
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Faster all-pairs shortest paths via circuit complexity
• All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

Cited by

• Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
• Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse

Related

• Fast Attention Requires Bounded Entries
• Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
• Fast attention mechanisms: a tale of parallelism
• Support Basis: Fast Attention Beyond Bounded Entries
• Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers