HEXAGONbeta

Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitycs.AI — Artificial Intelligencecs.DS — Data Structures and Algorithms

Contributed by Xiaoyu Li ↗

Version 1 / Nov 06, 2026 / CC BY 4.0

Abstract

Alman and Song showed that attention with head dimension O(log⁡n)O(\log n) can be approximated in almost linear time when the entries are o(log⁡n)o(\sqrt{\log n}), and needs quadratic time at Θ(log⁡n)\Theta(\sqrt{\log n}) under the Strong Exponential Time Hypothesis. In October 2026 the Exponential Time Hypothesis was refuted, and with it SETH. The quadratic lower bound now rests on the hardness of Orthogonal Vectors in dimension clog⁡nc\log n (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread WW, the largest gap between two logits of a row. At every nontrivial constant precision and in every dimension between ω(log⁡n)\omega(\log n) and no(1)n^{o(1)}, we show that under LDOV the time exponent of attention is exactly 1+min⁡{W/ln⁡n,1}1+\min\{W/\ln n,1\}: uniform sampling of keys is optimal, the cost is min⁡{n eW,n2}\min\{n\,e^{W},n^2\} up to factors no(1)n^{o(1)}, and the transition to quadratic time sits at W=ln⁡nW=\ln n, the spread at which one key can outweigh all others. At polynomial precision and in dimension O(log⁡n)O(\log n) the threshold becomes Θ(log⁡n)\Theta(\log n), with a constant that tends to zero as the precision grows, and the dimension moves it: at precision n−1−O(1/log⁡log⁡n)n^{-1-O(1/\log\log n)}, spread O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) is hard in dimension (log⁡n)1+Ω(1)(\log n)^{1+\Omega(1)} but easy in dimension O(log⁡n)O(\log n). From satisfiability we obtain hardness at spread (1+θ)ln⁡n(1+\theta)\ln n in dimension no(1)n^{o(1)}, provided the hard CNF formulas have Nc0N^{c_0} clauses for some c0<2c_0<2, and we show that the construction behind this bound, which builds one instance for each proof of a Merlin–Arthur protocol for disjointness, needs c0<2c_0<2 for every such protocol. For the entry bound, every reduction that embeds Orthogonal Vectors vector by vector, with polynomial blowup and logit gap Ω(log⁡n)\Omega(\log n), yields a Merlin–Arthur protocol for disjointness; by Klauck's lower bound, such reductions cannot derive B=Θ(log⁡n)B=\Theta(\sqrt{\log n}) from Orthogonal Vectors in dimension (log⁡n)1+Ω(1)(\log n)^{1+\Omega(1)}. We also map the conditional lower bounds for attention in the literature to the hypotheses that now support them, and find two families whose hypotheses are false, one of them in part of its parameter range.

Provenance statement

This work was produced on 30–31 October 2026 with Claude Opus 5.5 (Anthropic), working as an agent in Claude Code, and revised on 6 November 2026. The submitting contributor chose the direction, attention lower bounds after the refutation of the Strong Exponential Time Hypothesis, from a list of questions that Claude had proposed, asked for the extension of the lower bounds to every precision below 1, directed the presentation, chose the title, and had the paper reviewed by ChatGPT (OpenAI). Claude chose the results, proved them, wrote the text and drew the figures. Separate Claude agents searched the literature and checked the citations, attacked the proofs in several independent rounds, and reviewed the paper as referees; the paper was revised after each round. The external review by ChatGPT checked the proofs and the tables of prior results and found no fatal or major problems; Claude checked each of its ten minor findings against the proofs and the cited sources, and corrected the definitions, statements of prior results and summaries concerned, without changing any proof. The gadgets, the counting identities and the reductions for the precision bounds were tested on small random instances, the identities in exact arithmetic; the script is in anc/. The paper uses results of Williams, Chen, Rubinstein and Razborov, quoted as Imported Theorems. No part of this paper is formally verified.

Tools used

Anthropic
Claude OpusVersion 5.5
OpenAI
ChatGPT
Python
Python 3 (checks in anc/)

References

  1. Amol Aggarwal and Josh Alman. Optimal-degree polynomial approximations for exponentials and G aussian kernel density estimation. In 37th Computational Complexity Conference (CCC) , volume 234 of LIPIcs , pages 22:1--22:23, 2022. Proposition numbers refer to arXiv:2205.06249v1.arXiv
  2. Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In 61st IEEE Symposium on Foundations of Computer Science (FOCS) , pages 541--552, 2020. Theorem numbers refer to arXiv:2011.02466v1.arXiv
  3. Josh Alman and Yunfeng Guan. Finer-grained hardness of kernel density estimation. In 39th Computational Complexity Conference (CCC) , volume 300 of LIPIcs , pages 35:1--35:21, 2024. Theorem numbers refer to arXiv:2407.02372v1.arXiv
  4. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP theorems for hardness of approximation in P . In 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 25--36, 2017.
  5. Josh Alman and Zhao Song. Fast attention requires bounded entries. In Advances in Neural Information Processing Systems 36 (NeurIPS) , pages 63117--63135, 2023.
  6. Josh Alman and Zhao Song. The fine-grained complexity of gradient computation for training large language models. In Advances in Neural Information Processing Systems 37 (NeurIPS) , pages 61419--61454, 2024. Theorem numbers refer to arXiv:2402.04497v1.arXiv
  7. Josh Alman and Zhao Song. How to capture higher-order correlations? G eneralizing matrix softmax attention to K ronecker computation. In International Conference on Learning Representations (ICLR) , pages 4306--4333, 2024.
  8. Josh Alman and Zhao Song. Fast RoPE attention: Combining the polynomial method and fast F ourier transform. arXiv:2505.11892, 2025.arXiv
  9. Josh Alman and Virginia Vassilevska Williams . Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs. arXiv:2610.06783, 2026.arXiv
  10. Josh Alman and Ryan Williams. Probabilistic polynomials and H amming nearest neighbors. In 56th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 136--150, 2015. Theorem numbers refer to arXiv:1507.05106v1.arXiv
Show all 46 referencesShow fewer references
  1. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 218--230, 2015.
  2. Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In International Conference on Learning Representations (ICLR) , pages 47475--47498, 2025.
  3. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. In Advances in Neural Information Processing Systems 30 (NeurIPS) , pages 4308--4318, 2017.
  4. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS) , pages 261--270, 2016.
  5. Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In 33rd Computational Complexity Conference (CCC) , volume 102 of LIPIcs , pages 14:1--14:45, 2018. Lemma numbers refer to arXiv:1802.02325v2.arXiv
  6. Yang Cao, Jiayan Huo, Yingyu Liang, Zhenmei Shi, and Zhao Song. RoPE attention can be trained in almost linear time. arXiv:2412.17316, 2024.arXiv
  7. Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. In 61st IEEE Symposium on Foundations of Computer Science (FOCS) , pages 172--183, 2020. Theorem numbers refer to arXiv:2011.06997v1.arXiv
  8. Claude (Anthropic) . A 2o(n)2^{o(n)} time algorithm for 3- SAT . Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026. https://hexagonmath.org/2610.00577v1. Lean development at https://github.com/anthropics/formal-math/tree/main/eth, 2026.hexagon
  9. Yang Cao, Yingyu Liang, Zhenmei Shi, and Zhao Song. Training tensor attention efficiently: From cubic to almost linear time. arXiv:2405.16411, 2024.arXiv
  10. Sayak Chakrabarti, Toniann Pitassi, and Josh Alman. Poly-attention: A general scheme for higher-order self-attention. In International Conference on Learning Representations (ICLR) , pages 11844--11906, 2026. arXiv:2602.02422.arXiv
  11. Moses Charikar and Paris Siminelakis. Hashing-based-estimators for kernel density in high dimensions. In 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 1032--1043, 2017. Theorem numbers refer to arXiv:1808.10530v1.arXiv
  12. Timothy M. Chan and Ryan Williams. Deterministic APSP , orthogonal vectors, and more: Quickly derandomizing R azborov-- S molensky. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1246--1255, 2016.
  13. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 21--40, 2019.
  14. Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, and Christopher Ye. Subquadratic algorithms and hardness for attention with any temperature. In International Conference on Learning Representations (ICLR) , pages 85672--85701, 2026. Theorem numbers refer to arXiv:2505.14840v1.arXiv
  15. Lukas Haverbeck, Carmen Amo Alonso , Andres Felipe Posada-Moreno, Sebastian Trimpe, and Marco Pavone. Efficiently approximating attention is hard. arXiv:2609.37261, 2026.arXiv
  16. Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, and Amir Zandieh. HyperAttention : Long-context attention in near-linear time. In International Conference on Learning Representations (ICLR) , pages 39310--39325, 2024.
  17. Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern H opfield models: A fine-grained complexity analysis. In Proceedings of the 41st International Conference on Machine Learning (ICML) , volume 235 of PMLR , pages 19327--19343, 2024. arXiv:2402.04520.arXiv
  18. Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation ( LoRA ) fine-tuning for transformer models. In International Conference on Learning Representations (ICLR) , pages 6167--6206, 2025. Theorem numbers refer to arXiv:2406.03136v2.arXiv
  19. Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency. In International Conference on Learning Representations (ICLR) , pages 29634--29686, 2025. arXiv:2411.16525.arXiv
  20. Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers ( DiTs ). In Advances in Neural Information Processing Systems 37 (NeurIPS) , pages 31562--31628, 2024. arXiv:2407.01079.arXiv
  21. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001.
  22. Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In 18th Annual IEEE Conference on Computational Complexity (CCC) , pages 118--134, 2003. Theorem numbers refer to arXiv:cs/0208006.arXiv
  23. Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. On computational limits and provably efficient criteria of visual autoregressive models: A fine-grained complexity analysis. arXiv:2501.04377, 2025.arXiv
  24. Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In International Conference on Algorithmic Learning Theory (ALT) , volume 201 of PMLR , pages 597--619, 2023.
  25. Leslie Lamport. How to write a proof. The American Mathematical Monthly , 102(7):600--608, 1995.
  26. Leslie Lamport. How to write a 21st century proof. Journal of Fixed Point Theory and Applications , 11(1):43--63, 2012.
  27. Xiaoyu Li. What does the refutation of the E xponential T ime H ypothesis mean for learning theory? Hexagon preprint hexagon:2610.00613v2, October 2026. https://hexagonmath.org/2610.00613v2, 2026.hexagon
  28. OpenAI . The E xponential T ime H ypothesis is false. OpenAI Math Release preprint, dated October 17, 2026, revised October 25, 2026, released October 26, 2026. https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 2026.link
  29. Alexander A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science , 106(2):385--390, 1992.
  30. Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC) , pages 1260--1268, 2018. Theorem numbers refer to arXiv:1803.00904v1.arXiv
  31. Tamas Sarlos, Xingyou Song, David P. Woodruff, and Qiuyi Zhang. Hardness of low rank approximation of entrywise transformed matrix products. In Advances in Neural Information Processing Systems 36 (NeurIPS) , pages 52568--52582, 2023. arXiv:2311.01960.arXiv
  32. Barna Saha, Yinzhan Xu, and Christopher Ye. Furthest pair requires quadratic time in superconstant dimension under SETH . arXiv:2606.25887, 2026.arXiv
  33. Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu. On the computational hardness of transformers. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC) , pages 1073--1084, 2026. Theorem numbers refer to arXiv:2603.11332v1.arXiv
  34. Jan van den Brand , Zhao Song, and Tianyi Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. In Proceedings of the 41st International Conference on Machine Learning (ICML) , volume 235 of PMLR , pages 49008--49028, 2024. Lemma numbers refer to arXiv:2304.02207v1.arXiv
  35. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science , 348(2--3):357--365, 2005.
  36. Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. KDE former: Accelerating transformers via kernel density estimation. In Proceedings of the 40th International Conference on Machine Learning (ICML) , volume 202 of PMLR , pages 40605--40623, 2023.

Version history

  1. v1 · 43 pagesSubmitted by Xiaoyu LiInitial depositCurrentNov 05, 2026