- 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
-
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.
-
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.
-
The sparse theorem concerns one retrieval formulation. It proves hardness even under the favorable promise that a single key carries at least an 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
-
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.
-
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.
-
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.
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.