acceptodds
Under review as a conference paper at ICLR 2027

Efficiently Approximating Attention Is Hard

16 views

Abstract

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 already holds at the boundary where known algorithms 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.

Primary area:
learning theory
Keywords:
attention, complexity, runtime lower bounds

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dEncOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the complexity of approximating softmax attention with guarantees that hold uniformly over all valid inputs. Based on the existing SETH theorem, it proves truly subquadratic-time hardness at fixed nontrivial additive and relative error in a logarithmic-dimensional, bounded-entry regime. It also proves lower bounds for query-time attention after polynomial KV-cache preprocessing and for retrieving keys that carry a specified fraction of attention mass. The arguments reduce variants of approximate closest-pair search to attention.

Critical strengths

The main theorem closes the fixed-error gap left by Alman and Song (2023) at the same dimension and entry-bound regime, where Gupta et al. (2026) prove constant-error hardness with much larger entries. The proof makes the normalized attention output an almost-binary test by separating genuine-key scores from dummy keys, rather than simply changing an error parameter in the earlier reduction. The KV-cache result addresses the query setting after preprocessing, and the sparse theorem uses random perturbations to isolate a dominant key when near ties are possible. Together, these results clarify the limits of uniform approximation under SETH theorem.

Critical weaknesses
  1. The inherited hardness and the new proof steps could be separated more clearly. All lower bounds are conditional on SETH and draw on Rubinstein’s hardness result for approximate closest pair. Alman and Song (2023) already used closest-pair reductions and dummy keys for attention at the same dimension and entry bound. This paper’s new steps are the fixed-error threshold construction and the random isolation argument for sparse retrieval. The discussion should foreground how these steps transfer the existing source-problem hardness to the new attention tasks, rather than leaving the origin and extent of the new theory implicit.

  2. The practical implications are limited by the uniform-guarantee model. The lower bounds apply to algorithms required to succeed on every admissible input. Methods used in deployed Transformers often rely on properties of their input distributions or architecture. The paper correctly states its uniform scope; a more direct account of which practical methods fall outside that scope would help interpret the results.

  3. The sparse theorem concerns one retrieval formulation. It proves hardness even under the favorable promise that a single key carries at least an α\alpha fraction of the attention mass. This is a strong result for explicit subset retrieval, but it does not directly characterize methods designed for mass shared among several keys or methods that use sparsity without returning a subset.

Questions for authors
  1. Could the authors distinguish the hardness inherited from SETH and earlier closest-pair reductions from the new threshold and isolation constructions? In particular, please explain why the earlier attention reduction did not establish fixed-error or sparse-retrieval hardness, and how each new step overcomes that obstacle.

  2. Which approximation methods discussed in the introduction are covered by the uniform-guarantee model, and which rely on restricted input classes? A short discussion would help relate the lower bounds to the practical motivation without extending their formal scope.

  3. Can the sparse-retrieval argument address attention mass shared among a small group of keys, or methods that exploit sparsity without explicitly returning a subset? If these cases require different arguments, please identify them as outside the current theorem.

Reviewer_mAKoOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper establishes new complexity-theoretic lower bounds for approximating softmax attention with uniform guarantees over all inputs. Under SETH, the authors show that no truly subquadratic algorithm can achieve any nontrivial additive or relative approximation guarantee when d=Θ(log⁡n)d=\Theta(\log n) and B=Θ(log⁡n)B=\Theta(\sqrt{\log n}), strengthening prior results that only ruled out high-precision approximation. They further extend the hardness results to autoregressive decoding with polynomial-time KV-cache preprocessing and sparse attention retrieval, showing that neither preprocessing nor attention concentration alone enables efficient approximation with uniform guarantees.

Critical strengths
  • Stronger lower bounds for attention approximation. Theorem 3.7 strengthens existing hardness results from high-precision approximation to any fixed nontrivial additive or relative error guarantee. The result holds at the asymptotic boundary of known efficient approximation regimes, making it a significant theoretical contribution.

  • Extensions to preprocessing and sparse retrieval. Theorems 4.1 and 5.1 establish hardness even with polynomial-time KV-cache preprocessing or highly concentrated attention distributions. The randomized perturbation construction for sparse retrieval is particularly interesting, extending the analysis beyond approximating the full attention output.

Critical weaknesses
  • Limited practical implications of worst-case hardness. The lower bounds rely on adversarially constructed inputs whose correspondence to attention distributions in trained models is unclear. Moreover, the existential constants in the dimension and entry bounds make it difficult to assess the relevance of the hard instances to realistic attention configurations.

  • Incomplete characterization of the boundary for relative approximation. The paper claims a sharp transition between efficient and intractable uniform approximation, but the complementary upper bounds primarily establish additive-error guarantees. Since additive guarantees do not necessarily imply nontrivial relative-error guarantees, it is unclear whether this sharp boundary also holds for the relative approximation settings considered.

Questions for authors
  • Can the authors quantify the constants in the dimension and entry bounds, or discuss how the resulting hard instances relate to practical attention configurations? This would help clarify the practical significance of the asymptotic hardness results.

  • Do the existing near-linear algorithms also provide nontrivial uniform relative-error guarantees in the complementary parameter regimes? If not, should the claimed sharp computational boundary be qualified as applying specifically to additive approximation?

Reviewer_H9oxOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper establishes conditional hardness results for uniformly approximating softmax attention, extending previous high-precision lower bounds to coarse additive and relative approximation guarantees. It also shows that polynomial KV-cache preprocessing and concentrated attention do not suffice for uniformly efficient approximation or retrieval. Validation is theoretical, through reductions from approximate closest-pair problems under randomized SETH.

Critical strengths
  • The results extend previous high-precision lower bounds to the full range of fixed nontrivial approximation guarantees. This closes an important gap between near-exact computation and coarse approximation.
  • The paper separates KV-cache preprocessing from query evaluation and establishes lower bounds even with polynomial preprocessing. This addresses an important computational setting that standard batch-attention lower bounds do not directly cover.
  • The paper separates KV-cache preprocessing from query evaluation and establishes lower bounds even with polynomial preprocessing. This addresses an important computational setting that standard batch-attention lower bounds do not directly cover.
Critical weaknesses
  • The constants governing dimension and entry bounds depend on the desired runtime improvement and, for preprocessing results, the preprocessing exponent. The theoremsof therefore do not establish hardness for every fixed choice of constants within the stated asymptotic regime. More explicit parameter dependence and finite-size illustrations would help assess the scope and practical significance of the conclusions.
  • The sparse-retrieval reduction uses continuous exponential samples and real-valued constructions while claiming explicit preprocessing and query runtimes. The paper should state its arithmetic and sampling model and explain how finite-precision implementation preserves the isolation probability and runtime exponents. This is relevant to the formal completeness of the reduction.
Questions for authors
  • How do C_{d}, C_{B}, and the minimum applicable sequence length depend on the approximation tolerance, runtime improvement, and preprocessing exponent? Could concrete examples or a small synthetic study illustrate the resulting logit ranges and attention separation at finite sequence lengths?
  • Can the clipped exponential perturbations in Lemma A.8 and the resulting query/key entries be implemented with bounded precision while preserving the guarantees used in Theorem 5.1? Please specify the computational model and quantify any additional sampling or arithmetic overhead.
2 comments

As the discussion period is coming to an end, we would like to kindly follow up on our response to your review. We would greatly appreciate it if you could let us know whether our clarifications address your concerns, or if there are any remaining questions we could help resolve.

Thank you again for your time and consideration.

Thank you for your rebuttal and follow-up. Your clarifications on OVC-style existential parameter dependence and on finite-precision implementations of the sparse-retrieval construction are helpful. After reading your responses, I will keep my score unchanged.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision of the manuscript

We want to thank the reviewers once again for their valuable feedback, which we have now incorporated to improve our manuscript. In particular, we made the following changes.

  • We have removed the dependence on SETH and replaced it with the Orthogonal Vectors Conjecture (OVC), which is a standard complexity-theoretic assumption that is weaker than SETH and not affected by the recent refutations of SETH.
  • We clarified that our results identify a sharp transition from highly accurate approximation in near-linear time to the impossibility of any nontrivial uniform approximation guarantee in truly subquadratic time under OVC, for both additive and relative error, at the boundary where d=Θ(log⁡n)d=\Theta(\log n) and B=Θ(log⁡n)B=\Theta(\sqrt{\log n}).
  • In this context, we also made explicit that the constants CdC_d and CBC_B for which we prove hardness depend existentially on the exponent saving, whereas they are independent of the approximation error thresholds ηadd\eta_{\mathrm{add}} and ηrel\eta_{\mathrm{rel}}.
  • We clarified that our formalization of sparse attention is canonical in that our hardness results subsume multi-token sparseness and attention output approximation under sparsity.
  • We have revised our proofs to make explicit that all reductions work with bounded precision in the standard O(log⁡n)\mathcal{O}(\log n)-bit word model with only fair coin flips for randomness, without weakening any of our results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.