Source-linked AI summary
On The Computational Complexity of Self-Attention
Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde
TL;DR
The paper asks whether self-attention can achieve provably sub-quadratic runtime while retaining near-accuracy. It uses SETH-based reductions to establish conditional quadratic lower bounds across several attention mechanisms and gives a linear-time Taylor approximation with an exponential dependence on polynomial order.
Problem
Existing fast self-attention methods often lack rigorous guarantees on the error–runtime tradeoff, motivating the question of whether provably sub-quadratic and near-accurate attention is possible.
Method
The paper derives conditional lower bounds through reductions from SETH-related problems and also analyzes finite Taylor-series approximations for dot-product self-attention.
Results
The paper proves quadratic or rectangular lower bounds for numerous exact and approximate attention mechanisms under SETH, while finite Taylor approximations achieve linear time with exponential dependence on polynomial order.
Takeaways & Limitations
Provably sub-quadratic self-attention that remains near-accurate for all inputs appears unlikely, while polynomial score functions provide a linear-time alternative with an order-dependent cost.
Takeaways & Limitations
The theorems concern worst-case inputs, leave average-case hardness unresolved, and leave open randomized sub-quadratic algorithms correct with high probability.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies whether self-attention can be made both provably sub-quadratic and near-accurate, establishing conditional quadratic lower bounds while giving a linear-time polynomial approximation with an exponential order cost.
- Motivation: Standard self-attention computes pairwise token interactions, creating quadratic costs for both transformer training and inference.
- Motivation: Existing faster methods empirically reduce runtime, sometimes from quadratic to linear, but generally lack rigorous guarantees for their computation error.Approximation errors can reduce accuracy or have more dramatic effects on adversarial inputs.
- Our contributions: Conditional quadratic lower bounds hold for self-attention across a large variety of settings, including additive and multiplicative approximation errors.The bounds also cover windowing, striding, and kernelization with radial basis function kernels.
- Our contributions: The results suggest a fundamental no-free-lunch phenomenon: provably sub-quadratic self-attention is unlikely to remain provably near-accurate for all inputs.
- Our contributions: Finite Taylor series can approximate dot-product self-attention in linear time, but runtime scales exponentially with the polynomial order.
- Techniques: The proofs use reductions from SETH through the Orthogonal Vectors Problem, Thresholded Vectors Product Problem, and Bichromatic Hamming Close Pair problem.Constructing vector gadgets and identifying the correct softmax temperature scaling form the main technical difficulties.
2 Related work
Related work has developed many sub-quadratic self-attention methods using hashing, sparsification, low-rank approximation, and kernel approximation, but theoretical error characterizations remain uncommon.
- Speeding up self-attention: Standard self-attention requires O(dn^2) time for a length-n sequence of d-dimensional tokens.
- Speeding up self-attention: Hashing, sparsification, and low-rank approximation have been used in methods including Reformer, Big Bird, Linformer, Longformer, and routing transformers.
- Speeding up self-attention: Other approaches replace softmax attention with kernel approximations to reduce computational cost.
- Speeding up self-attention: Most prior methods emphasize runtime improvements, while few theoretically characterize the error introduced by their approximations.
- Speeding up self-attention: The related-work question is whether self-attention can be both provably subquadratic and provably near-accurate, which the paper finds unlikely.
3 Notations and Preliminaries
The preliminaries define standard and generalized self-attention and explain its quadratic computation, then introduce SETH and OVP as the basis for the paper's conditional lower bounds.
- Background on Self-Attention: Self-attention forms query, key, and value matrices from X using trainable parameter matrices, then applies attention to these representations.The query and key dimensions are assumed equal, while values may have a different output dimension.
- Background on Self-Attention: For very large n, computing score matrices, softmax normalization, and value aggregation yields quadratic dependence on the sequence length.The main costs are O(n^2d_k) for scores and O(n^2d_v) for multiplying attention weights by values.
- Background on Self-Attention: Generalized self-attention defines scores as S_ij = f(Q_i, K_j) and applies a normalization function h to the score matrix.Softmax dot-product attention is recovered using a scaled dot product for f and row-wise softmax for h.
- Background on Self-Attention: The paper aims to establish SETH-based lower bounds for softmax dot-product attention, approximate variants, and more general score functions.
- Fine-grained complexity: SETH asserts that, for every ε, SAT has no O(2^(n(1−ε))) sub-exponential-time algorithm.
- Fine-grained complexity: The Orthogonal Vectors Problem asks whether two sets of binary vectors contain a pair with zero dot product and requires near-quadratic time under SETH.The stated hardness applies when d = ω(log n).
4 Hardness of Computing Self-Attention
The paper derives SETH-based reductions showing near-quadratic hardness for exact and approximate self-attention across multiple mechanisms, including windowed and kernelized variants.
- Hardness foundations: SETH implies TVPP, BHFP, and BHCP require Ω(n2−ε) time for any ε > 0 when d = ω(log n).These problems serve as intermediate hardness waypoints for the self-attention reductions.
- Reduction strategy: The reductions use OVP-derived vector gadgets to encode threshold-product and Hamming-distance instances into self-attention inputs.The proofs modify the score and normalization functions and construct query and value matrices from the problem vectors.
- Dot-product self-attention: For dq = ω(log n), exact dot-product self-attention and element-wise multiplicative or additive approximations require Ω(n2−ε) time under SETH.A faster algorithm would decide TVPP in O(n2−ε) time, contradicting its conditional hardness.
- Softmax and score computation: The same near-quadratic lower bound applies to computing the self-attention score matrix with exact, multiplicative-error, or additive-error guarantees.The score-matrix result follows by an argument similar to the output-computation reduction.
- Windowing and striding: Windowed or strided self-attention still requires Ω(nw1−ε) time when dq = ω(log w) and w = ω(dq), for exact or approximate outputs.The listed guarantees include exact computation, multiplicative approximation, and additive approximation.
- Kernelized self-attention: ℓ2 self-attention, which uses an RBF kernel, also requires Ω(n2−ε) time for exact or multiplicative-approximate computation when dq = ω(log n).The reduction is from BHCP, whose hardness is established under SETH.
5 Polynomial Approximations of Self-Attention
The paper shows that polynomial attention kernels can be evaluated in linear time in the sequence length, while the runtime grows exponentially with the polynomial order.
- Polynomial attention: Polynomial score functions of order p permit self-attention computation in O(ndp_qd_v) time, with or without row-wise normalization.The dominant dependence on the query-key dimension arises from the highest polynomial exponent.
- Taylor approximation: Finite Taylor-series approximation of dot-product softmax self-attention yields linear time in n, but the runtime depends exponentially on the Taylor polynomial order p.The approximation replaces the exponential score function with a finite polynomial.
- Computation method: The computation avoids explicitly forming the n × n score matrix by reorganizing polynomial terms and multiplying aggregated query-key factors with values.For the unnormalized case, matrix products such as K^T V and Q(K^T V) provide the linear-in-n computation.
- Row-wise normalization: Row-wise normalization remains linear-time because each row denominator can be computed separately and then used to rescale the corresponding output row.After computing SV, each element is divided by its row sum.
6 Conclusions
The paper establishes conditional lower bounds for self-attention while identifying a linear-time polynomial-score alternative. Its conclusions leave average-case hardness and randomized subquadratic algorithms open.
- Quadratic or rectangular lower bounds hold for numerous self-attention mechanisms assuming SETH.
- Linear-time self-attention is possible when the score computation function is polynomial.
- The theorems characterize a landscape between exponential and polynomial forms of self-attention, leaving a clearer picture for future work.
- The hardness results concern worst-case inputs, while average-case hardness remains open.
- Randomized algorithms with subquadratic complexity and high-probability correctness remain possible directions.
A Proofs for Hardness of TVPP, BHCP and BHFP
The appendix proves hardness for TVPP, BHFP, and BHCP by reducing from OVP under SETH. Vector gadgets preserve the relevant dot-product or distance conditions while transferring any subquadratic algorithm into a contradiction.
- Under SETH, TVPP requires Ω(n2−ε) time for d = ω(log n).
- The reductions construct augmented vectors in O(nd) time and encode orthogonality or threshold distances through dot products and squared ℓ2 distances.
- Under SETH, BHFP requires Ω(n2−ε) time for d = ω(log n).
- Any O(n2−ε) algorithm for BHFP, BHCP, or TVPP would decide the corresponding OVP instance in O(n2−ε) time when d = o(n1−ε), contradicting OVP hardness.
- Under SETH, BHCP requires Ω(n2−ε) time for d = ω(log n).
B Proof for Hardness of Sliding Window Dot-Product Self-Attention
The sliding-window proof reduces TVPP to self-attention by placing vector gadgets into windows and separating threshold cases through exponential score gaps. This yields conditional lower bounds even under exact or approximate computation.
- Computing sliding-window self-attention requires Ω((nw)1−ε) time under SETH for exact, multiplicative, or additive approximation.
- The construction uses k = √(nw) TVPP vectors and assembles query and value matrices whose window outputs aggregate exponential dot-product scores.
- Choosing C = 2 log w separates the no-threshold-pair and threshold-pair cases for exact computation.
- Multiplicative and additive errors remain distinguishable with temperature choices depending on µ and w.
- The same hardness argument extends to dilated sliding windows and softmax dot-product attention restricted to each window.
C Proofs for Hardness of Self-Attention Matrix S Approximation
The proof transfers TVPP hardness to approximating the self-attention score matrix and then analyzes polynomial feature maps for faster computation. Under SETH, even approximate score computation retains quadratic complexity, whereas polynomial scores admit structured matrix multiplication.
- Computing self-attention with exact, multiplicative, or additive score approximation requires Ω(n2−ε) time when dq = ω(log n).
- The reduction encodes TVPP threshold cases into attention outputs and distinguishes them by bounding all outputs in the false case and one output in the true case.
- For p = 1, the factorization computes K^T V first and then multiplies by Q, avoiding direct formation of the n × n score matrix.
- Polynomial feature maps transform degree-p score functions into vectors of dimension dpq, enabling factorized computation rather than explicit score-matrix construction.
- The resulting polynomial self-attention computation has costs expressed through O(ndp^q), O(dp^qndv), and O(ndp^qdv) terms.
E Proof for Hardness of ℓ2-Self-Attention
Assuming SETH, the paper reduces Bichromatic Hamming Close Pair instances to ℓ2-distance self-attention and derives conditional near-quadratic lower bounds, including for exact and multiplicative approximations.
- Multiplicative approximation: The same reduction rules out O(n^(2−ε))-time self-attention with multiplicative error μ < 1 under the stated dimension condition.Such an algorithm would decide BHCP in O(n^(2−ε)) time, contradicting its SETH-based hardness.
- Reduction: The reduction encodes BHCP instances with binary vectors into self-attention matrices using vector gadgets.The constructed output values distinguish whether a sufficiently close vector pair exists.
- Exact computation: For exact computation, close and non-close BHCP cases produce separated output magnitudes, with the positive case satisfying Y_l ≥ e^(−C(t−1)).Choosing C = 2 log n makes the separating threshold sufficient.
- RBF kernel: For a general RBF kernel, the hardness result initially depends on a predefined kernel parameter C, but vector rescaling extends it to the desired setting.The rescaling is performed in O(n) time.
F Multi-Head Self-Attention
The paper establishes a direct-sum hardness result for multiple parallel OVP-, TVPP-, BHCP-, or BHFP-type instances, preserving near-quadratic total complexity under SETH.
- Multi-head hardness: k parallel OVP, TVPP, BHCP, or BHFP problems require O(k n^(2−ε)) time for any ε.Each problem contains two sets of n binary vectors.
- Reduction: The proof arranges shifted pairings of the k input-set families to construct a larger combined instance.The pairings are (A1, Bt), (A2, Bt+1), through (Ak, Bt+k−1), with indices taken cyclically.
- Contradiction: A faster algorithm for the parallel problems would yield an O(k n^(2−δ))-time algorithm for a size-kn combined problem, contradicting SETH.The argument selects δ = ε/2 and assumes k < n.
- Conclusion: The lemma therefore validates a direct-sum computational-complexity bound for these vector problems.
G Discussion of Additive Approximation
The additive-approximation discussion gives conditional near-quadratic lower bounds for softmax self-attention when the error is sufficiently small, while identifying exponentially small accuracy thresholds.
- ℓ2-distance self-attention: ℓ2-distance self-attention requires Ω(n^(2−ε)) time when d_q = ω(log n) and μ ≤ e^(−2d log(n+2)) additive error.This threshold equals (n + 2)^(−2d).
- ℓ2-distance self-attention: The ℓ2-distance reduction distinguishes BHCP cases by separating output bounds δ and Δ, with C = 2 log(n + 2).The construction maps the BHCP instance through self-attention and checks the first n output elements.
- ℓ2-distance self-attention: An O(n^(2−ε))-time algorithm with μ ≤ e^(−2d log(n+2)) would decide BHCP in the same time, contradicting its hardness.The reduction overhead is O(n + nd).
- Accuracy boundary: The additive error bound can be improved slightly, but its order must remain O(n^(−d)).
- Dot-product self-attention: The softmax dot-product proof uses TVPP vector gadgets to create distinct row-sum scales for instances with and without a high-dot-product pair.The resulting approximation hardness requires μ ≤ e^(−3d log(n)−3d^2).
H Discussion of Remark in Section 4.4
The multiplicative-hardness remark examines the boundary μ = 1 and notes that the proof parameter C is undefined there, while values close to one remain compatible with the argument.
- Boundary case: The multiplicative-error hardness proof assumes μ < 1 because its parameter C is undefined at μ = 1.
- Boundary case: At μ = 1, setting every approximated entry to zero satisfies the condition in O(n) time.Thus the exact endpoint is not covered by the quadratic-hardness argument.
- Near-boundary regime: Values arbitrarily close to one can preserve the proof’s parameter scaling by setting μ = 1 − 1/n^x for constant x.