Source-linked AI summary
Efficiently Approximating Attention Is Hard
Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe, Marco Pavone
TL;DR
Softmax attention has quadratic sequence-length cost, motivating fast approximations, but prior uniform lower bounds left open whether coarse guarantees were possible. The paper strengthens those bounds and shows that, under SETH, no truly subquadratic algorithm provides a nontrivial uniform additive or relative guarantee. The impossibility extends to preprocessing and sparse retrieval settings.
Problem
Prior lower bounds ruled out fast near-exact attention but left open whether efficient algorithms could provide even coarse uniform guarantees across inputs.
Source: §1 · p. 2Method
The paper strengthens an attention-to-closest-pair lower-bound argument and analyzes uniform approximation with additive and relative error guarantees.
Source: §3.1 · p. 4, §3.3 · p. 6Results
Takeaways & Limitations
Beyond regimes already allowing near-linear, near-exact approximation, uniform approximate attention must exploit data-dependent structure.
Source: §1 · p. 2, §6 · p. 9The hardness claims are conditional on SETH and use error conventions where values lie in [0,1] and nontrivial guarantees are below additive 1/2 or relative 1.
Source: §3.1 · p. 4
Abstract
from arXiv · showhide
Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.
1 INTRODUCTION
Softmax attention is a costly component of Transformers because its standard implementation scales quadratically with sequence length. The paper shows that, under standard complexity assumptions, fast uniform approximation remains impossible even with nontrivial error, including in settings with preprocessing or sparsity.
1 INTRODUCTION
- Standard attention scales quadratically with sequence length, making it a major inference bottleneck and often prohibitively expensive on long sequences.Its ability to model relationships between sequence elements is a key component of Transformer performance.Source: §1 · p. 2
- Fast attention approximations can work empirically or under input-structure assumptions, but diverse applications make uniform guarantees appealing.The paper frames the open question as whether efficient approximation with even a coarse uniform error guarantee is possible.Source: §1 · p. 2
- Under standard complexity-theoretic assumptions, no truly subquadratic algorithm gives any nontrivial uniform additive or relative approximation guarantee for attention.The result applies under minimal dimension and norm assumptions beyond regimes where known algorithms already achieve near-linear runtime and vanishingly small error.Source: §1 · p. 2
- Polynomial preprocessing still cannot enable truly sublinear per-token attention approximation, or sparse retrieval of a small set of keys capturing a constant attention fraction.The lower bound also covers autoregressive decoding under significant sparsity.Source: §1 · p. 2
- Beyond regimes where near-linear, high-accuracy approximation is already possible, approximate attention must exploit data-dependent structure.The paper presents new lower bounds as closing prior gaps and extending results to autoregressive decoding with preprocessing and sparsity.Source: §1 · p. 2
2 RELATED WORK
Prior work speeds up attention by exploiting sparsity, low rank, or other input structure, while uniform guarantees have been established only in restricted regimes. Earlier lower bounds leave open whether coarse uniform guarantees or preprocessing-based acceleration are possible in broader settings.
Fast approximate attention
- Fast approximation methods exploit sparsity, low-rank structure, or other properties of the attention matrix, but often rely on typical inputs or structural assumptions.These methods can reduce computation while preserving model quality.Source: §2 · p. 3
Uniform approximation guarantees
- Uniform near-linear algorithms achieve vanishing error only when dimensions and query/key norms are sufficiently small.Examples include polynomial and super-polynomial error decay under increasingly restrictive norm or magnitude conditions.Source: §2 · p. 3
Runtime lower bounds
- Earlier runtime lower bounds exclude near-exact or extreme-precision approximation in various regimes, but do not rule out every nontrivial error guarantee in the mild regime.The paper’s lower bound strengthens this line of work to rule out any nontrivial additive or relative error guarantee.Source: §2 · p. 3
Approximation with preprocessing and sparsity
- Prior work leaves open whether polynomial preprocessing can enable fast generation with uniform guarantees, despite the quadratic input-processing and added preprocessing costs.The paper extends runtime lower bounds to approximate attention after preprocessing and retrieval under sparsity.Source: §2 · p. 3
3 NONTRIVIAL GUARANTEES ARE IMPOSSIBLE UNDER MILD ASSUMPTIONS
The section formulates uniform attention approximation and explains why prior lower bounds leave coarse guarantees unresolved. It then strengthens the lower-bound argument to exclude nontrivial additive and relative guarantees under mild assumptions.
3.1 PROBLEM FORMULATION
- The formulation compares query-key scores, then aggregates values; it considers entrywise additive error and Schatten-norm relative error, with trivial thresholds of 1/2 and 1.The standard implementation takes O(n^2) operations when the number of queries equals the number of keys.Source: §3.1 · p. 4
3.2 EXISTING LOWER BOUNDS ONLY RULE OUT HIGH-PRECISION APPROXIMATION
- At d=Θ(log n) and B=Θ(√log n), prior lower bounds left coarse uniform errors open, although smaller-dimension or smaller-norm regimes already had near-linear, near-exact algorithms.Existing results mainly ruled out extreme precision or applied under more restrictive settings.Source: §3.2 · p. 5, Table 1 · p. 5
3 NONTRIVIAL GUARANTEES ARE IMPOSSIBLE UNDER MILD ASSUMPTIONS
- A fast algorithm for attention would yield a fast closest-pair algorithm by encoding pairwise distances in the attention matrix and recovering a close pair from value aggregation.The section’s main result strengthens this reduction so it works even for coarse, nontrivial approximation guarantees.Source: §3.3 · p. 6
3.3 NONTRIVIAL GUARANTEES ARE IMPOSSIBLE UNDER THE MILDEST ASSUMPTIONS
- At d=Θ(log n) and B=Θ(√log n), SETH rules out truly subquadratic algorithms for additive error below 1/2 and relative error below 1.The theorem establishes an O(n^(2−q)) runtime lower bound for every q>0, with suitable constants for the dimension and entry bound.Source: §3.3 · p. 6
- The proof encodes closest-pair distances in attention scores and uses dummy keys and value aggregation to test whether a close pair exists.Repeating the test over logarithmically many thresholds recovers an approximate closest pair, contradicting the SETH-based hardness of that problem.Source: §3.3 · p. 6
4 APPROXIMATION REMAINS HARD AFTER KV CACHE PREPROCESSING
The paper asks whether preprocessing the KV cache can enable fast attention approximation with nontrivial uniform guarantees. It formalizes this as preprocessing followed by answering a single revealed query, and shows that polynomial preprocessing does not remove the hardness outside already tractable regimes.
4 APPROXIMATION REMAINS HARD AFTER KV CACHE PREPROCESSING
- The question matters for autoregressive generation, where queries follow prefill and preprocessing the KV cache could reduce later decoding cost.The baseline scans the full cache per query; the target is truly sublinear decoding after preprocessing.Source: §4 · p. 7, §4.1 · p. 7
4.1 PROBLEM FORMULATION
- The formulation preprocesses keys and values into an arbitrary data structure, then requires an attention output for a single query revealed afterward.It defines additive and relative error using separate output-norm conditions.Source: §4.1 · p. 7
4.2 NONTRIVIAL GUARANTEES ARE IMPOSSIBLE UNDER THE MILDEST ASSUMPTIONS
- Under SETH, neither additive nor relative attention approximation admits polynomial preprocessing and truly sublinear decoding in the stated parameter regime.The theorem gives preprocessing time O(n^k), decoding time O(n^(1-q)), and D = C_d log n, with B determined by a constant C_B.Source: §4.2 · p. 7
5 APPROXIMATION REMAINS HARD FOR SPARSE ATTENTION
Sparse attention retrieval asks for a small set of keys capturing substantial attention when the distribution is concentrated. The paper shows that even polynomial preprocessing cannot guarantee such retrieval efficiently under the stated complexity assumption.
5 APPROXIMATION REMAINS HARD FOR SPARSE ATTENTION
- Sparse methods exploit the practical pattern that a few tokens may receive most attention, but the paper asks whether that structure alone supports uniform retrieval guarantees.The target differs from approximating the full attention output: it is to identify relevant tokens efficiently.Source: §5 · p. 8
5.1 PROBLEM FORMULATION
- The task permits preprocessing the keys, then asks for a small subset capturing a constant attention fraction when some key is promised to receive that fraction.The size of the returned set counts toward runtime, so returning all keys does not provide a speedup.Source: §5.1 · p. 8
5.2 EFFICIENTLY RETAINING TOKENS RECEIVING SUBSTANTIAL ATTENTION IS IMPOSSIBLE
- Random perturbations isolate an approximately closest key so that capturing a constant attention fraction reveals an approximate closest neighbor.The reduction creates perturbed copies; with high probability one copy makes a close key dominate the attention, and any sufficient subset must include it.Source: §5.2 · pp. 8–9
- Under SETH, SparseAtt cannot be solved with polynomial preprocessing and truly sublinear decoding for any fixed attention-fraction parameter in the theorem’s stated regime.The theorem sets preprocessing to O(n^k) and decoding to O(n^(1-q)).Source: §5.2 · p. 9
6 CONCLUSION
Beyond regimes where near-linear algorithms already achieve vanishingly small error, nontrivial uniform approximation requires essentially quadratic time under the paper’s assumptions. This barrier persists with KV-cache preprocessing and sparse retrieval, leaving input structure central to fast guarantees.
6 CONCLUSION
- Outside already tractable regimes, nontrivial additive or relative uniform attention guarantees require essentially quadratic time under standard complexity-theoretic assumptions.The paper identifies known near-linear, vanishing-error regimes as the boundary of this lower bound.Source: §6 · p. 9
- The hardness persists during autoregressive generation after arbitrary polynomial-time KV-cache preprocessing, including retrieval under sparsity.Source: §6 · p. 9
- The results do not rule out empirical success or strong guarantees under structural input assumptions; beyond tractable regimes, fast guarantees must exploit such structure.Source: §6 · p. 9
AI USE STATEMENT
The authors report that large language models were used to polish the paper’s original writing, while the authors wrote and reviewed all scientific content.
AI USE STATEMENT
- Large language models polished the original writing; the authors wrote and reviewed all scientific content.Source: AI USE STATEMENT · p. 10
A PROOFS
The appendix supplies formal proofs by reducing attention-approximation tasks to approximate closest pair problems. It covers coarse approximation and sparse retrieval reductions.
A.1 SOURCE PROBLEM
- The proofs reduce the results to a variant of approximate closest pair and connect it to Rubinstein’s lower bounds.Section A.1 presents the source problem; Sections A.2–A.3 use coarse attention approximation, while Sections A.4–A.5 treat sparse attention retrieval.Source: A PROOFS · p. 13
A.2–A.3
- The coarse-approximation reduction shows how to identify approximate closest pairs and proves Theorems 3.7 and 4.1.Sections A.2 and A.3 develop and apply this reduction.Source: A PROOFS · p. 13
A.4–A.5
- A separate sparse-attention retrieval reduction identifies approximate closest pairs and proves Theorem 5.1.Sections A.4 and A.5 develop and apply this reduction.Source: A PROOFS · p. 13
A.1 SOURCE PROBLEM
The source problem is approximate closest pair, whose fine-grained hardness yields lower bounds for attention approximation. The proof also establishes hardness with polynomial preprocessing for a balanced, gap-decision variant.
A.1 SOURCE PROBLEM
- Assuming SETH, CP on Boolean vectors in dimension C log n cannot be solved in O(n^(2-q)) time for suitable C and ε.The lower bound also rules out bounded-error randomized algorithms under the stated assumptions.Source: §A.1 · p. 13
- Under SETH, balanced PreCP remains hard with O(n^k) preprocessing and O(m(n)n^(1-q)) query time, even for bounded-error randomized algorithms.PreCP preprocesses a balanced set and decides whether a query set contains a pair within threshold t or beyond the (1+ε)t gap.Source: §A.1 · p. 13
- The reduction partitions the balanced sets, tests thresholds using repeated preprocessing and decoding, and obtains an O(n^(2-qγ/2)) algorithm contradicting the CP lower bound.It uses majority answers across repeated invocations and brute force on the small subsets.Source: §A.1 · p. 14
- For thresholds t ≤ c log n, enumerating nearby vectors in a trie solves PreCP in O(nd) preprocessing and O(mn^(1-q)) decoding time.This handles the small-threshold case separately from the main reduction.Source: §A.1 · p. 14
A.2 FINDING CLOSE PAIRS FROM A COARSE ATTENTION APPROXIMATION
The reduction encodes closest-pair instances as attention inputs whose outputs distinguish close from far pairs. Dummy keys make that distinction large enough to recover from a coarse approximation, while allowing key-value preprocessing before queries arrive.
A.2 FINDING CLOSE PAIRS FROM A COARSE ATTENTION APPROXIMATION
- The construction shifts scores against dummy keys so a close pair dominates while the combined contribution of far pairs stays negligible.Keys and values depend only on one closest-pair set, while queries depend only on the other, enabling preprocessing before queries are revealed.Source: §A.2 · p. 15
- The attention output serves as an almost-binary indicator of whether an approximate close pair exists.Recovering that indicator from even a coarse approximation would identify an approximate closest pair.Source: §A.2 · p. 15
- The construction forms K and V independently of the queries in O(nD) time, then forms Q in O(mD) time.This separation supports preprocessing the key-value cache before the query vectors are known.Source: §A.2 · pp. 15–16
- For a close pair, Y_i,1 ≥ n/(n + 1); when all pairs are far, Y_i,1 ≤ 1/(n + 1).The dummy keys each contribute score 1, while only the first value column is nonzero.Source: §A.2 · p. 16
A.3 PROOFS OF THEOREMS 3.7 AND 4.1
These proofs reduce coarse attention approximation to preprocessed closest-pair decision. The reduction establishes hardness for batch, single-query, absolute-error, and relative-error settings under SETH.
A.3 PROOFS OF THEOREMS 3.7 AND 4.1
- The proof encodes closest-pair decision as attention output, then uses an assumed approximation algorithm to decide the preprocessed source problem, contradicting its lower bound.The generalized formulation includes both attention problems treated by Theorems 3.7 and 4.1.Source: §A.3 · pp. 17–18
- Under SETH, batch attention approximation cannot achieve either absolute or Schatten-relative guarantees with O(n^k) preprocessing and O(m(n)n^(1-q)) query time.The proposition covers dimensions d = C log n and bounded entries with B = C_B√log n.Source: §A.3 · p. 17
- Under SETH, neither AbsAtt nor RelAtt can be solved in O(n^(2-q)) time in the stated logarithmic-dimension and entry-bound regime.The theorem statement specifies nontrivial absolute and relative error ranges.Source: §A.3 · p. 18
- Under SETH, single-query absolute and relative attention approximation also cannot combine O(n^k) preprocessing with O(n^(1-q)) decoding time.This is the preprocessed single-query form of the lower bound.Source: §A.3 · p. 18
A.4 FINDING CLOSE PAIRS FROM A SPARSE ATTENTION APPROXIMATION
The proof encodes query-to-key distances as attention scores, then uses clipped exponential perturbations to separate close from far pairs. This makes a close pair dominate attention so a sparse-attention retrieval algorithm can identify it.
A.4 FINDING CLOSE PAIRS FROM A SPARSE ATTENTION APPROXIMATION
- Clipped exponential perturbations limit how much a score can be amplified while allowing a close pair to separate from far pairs.The construction encodes distances as attention scores; close vectors receive larger scores before perturbation.Source: §A.4 · pp. 18–20
- With sufficiently high probability, the perturbed scores make an approximate closest pair carry almost all the attention mass.A sparse-attention retrieval algorithm must then include the dominant key.Source: §A.4 · pp. 18–19
- The construction uses randomly sampled key matrices and a query vector to realize the distance-based attention scores.The matrices are sampled independently of the query, which is constructed later.Source: §A.4 · pp. 19–20
A.5 PROOF OF THEOREM 5.1
Theorem 5.1 rules out sparse-attention retrieval with polynomial preprocessing and truly sublinear decoding under SETH. The proof reduces approximate closest-pair decision to sparse retrieval by arranging for a close pair's key to dominate attention in a successful copy.
A.5 PROOF OF THEOREM 5.1
- Under SETH, SparseAtt cannot be solved with O(n^k) preprocessing and O(n^(1-q)) decoding for the stated logarithmic dimension and bounded-entry parameters.The theorem applies for any α in (0, 1) and k, q > 0.Source: §A.5 · pp. 20–21
- The reduction samples polynomially many independent key-matrix copies during preprocessing and queries each copy after the closest-pair query arrives.It uses O(n^(k+1)) preprocessing and keeps decoding truly sublinear.Source: §A.5 · p. 21
- With probability at least 2/3, a successful copy makes the close-pair key necessary in any valid sparse-attention output, yielding a closest-pair decision algorithm.That algorithm contradicts the assumed closest-pair lower bound.Source: §A.5 · pp. 20–21