\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage[titles]{tocloft}
\setlength{\cftbeforesecskip}{0.7em}
\setlength{\cftbeforesubsecskip}{0.2em}
\setlength{\cftbeforetoctitleskip}{0pt}
\setlength{\cftaftertoctitleskip}{0.8em}
\usepackage{enumitem}
\usepackage{booktabs}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
\usepackage{graphicx}
\usepackage{xcolor}
\definecolor{citewarm}{HTML}{B5403B}
\definecolor{refcool}{HTML}{2C5AA0}
\definecolor{easy}{HTML}{1B9E77}
\definecolor{open}{HTML}{9A9A9A}
\definecolor{hard}{HTML}{D95F02}
\usepackage{tikz}
\usetikzlibrary{positioning,decorations.pathreplacing,calc,patterns}
\usepackage[colorlinks=true,linkcolor=refcool,citecolor=citewarm,urlcolor=refcool]{hyperref}
\usepackage[capitalise,nameinlink]{cleveref}
\usepackage{environ}

\setlist{itemsep=1pt,parsep=0pt,topsep=3pt,partopsep=0pt}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Imported Theorem}
\newtheorem{headline}{Theorem}
\renewcommand{\theheadline}{\Alph{headline}}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Open Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{fact}{Imported Theorem}{Imported Theorems}
\crefname{hypothesis}{Hypothesis}{Hypotheses}
\crefname{problem}{Open Problem}{Open Problems}
\crefname{claim}{Claim}{Claims}
\crefname{headline}{Theorem}{Theorems}
\crefname{figure}{Figure}{Figures}

% ---------- restatable results: \begin{restatable}[title]{env}{name} ... \end{restatable},
% restated later by \name* with the same number and without labels ----------
\makeatletter
\theoremstyle{plain}
\newcommand{\rst@thename}{}
\newtheorem*{rst@plain}{\rst@thename}
\def\rst@name@theorem{Theorem}
\def\rst@name@lemma{Lemma}
\def\rst@name@corollary{Corollary}
\def\rst@name@proposition{Proposition}
\def\rst@name@fact{Imported Theorem}
\NewEnviron{restatable}[3][]{%
  \def\rst@tmptitle{#1}%
  \ifx\rst@tmptitle\@empty\begin{#2}\BODY\end{#2}\else\begin{#2}[#1]\BODY\end{#2}\fi
  \expandafter\xdef\csname rst@num@#3\endcsname{\csname the#2\endcsname}%
  \expandafter\global\expandafter\let\csname rst@body@#3\endcsname\BODY
  \expandafter\gdef\csname rst@title@#3\endcsname{#1}%
  \expandafter\xdef\csname rst@env@#3\endcsname{#2}%
  \expandafter\gdef\csname #3\endcsname{\@ifstar{\rst@do{#3}}{\rst@do{#3}}}}
\newcommand{\rst@do}[1]{%
  \begingroup
  \edef\rst@tmpenv{\csname rst@env@#1\endcsname}%
  \edef\rst@thename{\csname rst@name@\rst@tmpenv\endcsname\space\csname rst@num@#1\endcsname}%
  \renewcommand{\label}[2][]{}%
  \expandafter\let\expandafter\rst@b\csname rst@body@#1\endcsname
  \expandafter\let\expandafter\rst@t\csname rst@title@#1\endcsname
  \ifx\rst@t\@empty\begin{rst@plain}\rst@b\end{rst@plain}%
  \else\begin{rst@plain}[\rst@t]\rst@b\end{rst@plain}\fi
  \endgroup}
\makeatother

% ---------- Lamport-style structured proofs (L. Lamport, "How to Write a Proof", 1995) ----------
\newcommand{\pflab}[2]{\ensuremath{\langle#1\rangle}#2}
\newenvironment{steps}{\begin{list}{}{%
    \setlength{\leftmargin}{2.1em}\setlength{\labelwidth}{1.9em}\setlength{\labelsep}{0.2em}%
    \setlength{\itemsep}{2pt}\setlength{\parsep}{1pt}\setlength{\topsep}{2pt}\setlength{\partopsep}{0pt}%
    \renewcommand{\makelabel}[1]{##1\hfil}}}{\end{list}}
\newcommand{\step}[2]{\item[\pflab{#1}{#2}.]}
\newcommand{\qedstep}[2]{\item[\pflab{#1}{#2}.]\textsc{q.e.d.}}
\newcommand{\pf}{\par\textsc{Proof:}\ }
\newcommand{\sref}[2]{\pflab{#1}{#2}}
\newcommand{\Assume}{\textsc{Assume:}\ }
\newcommand{\Prove}{\textsc{Prove:}\ }
\newcommand{\Let}{\textsc{Let:}\ }
\newcommand{\Suffices}{\textsc{Suffices:}\ }
\newcommand{\Case}{\textsc{Case:}\ }

% ---------- macros ----------
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\poly}{\mathrm{poly}}
\DeclareMathOperator{\polylog}{polylog}
\newcommand{\eps}{\varepsilon}
\newcommand{\ind}{\mathbf{1}}
\newcommand{\OV}{\mathsf{OV}}
\newcommand{\DISJ}{\mathsf{DISJ}}
\newcommand{\ATT}{\mathsf{ATT}}
\newcommand{\LDOV}{\mathrm{LDOV}}
\newcommand{\MA}{\mathsf{MA}}
\newcommand{\Spread}{W}
\newcommand{\ip}[2]{\langle #1,#2\rangle}
\DeclareMathOperator*{\argmax}{arg\,max}

\title{Fast Attention after SETH:\\ The Exact Exponent and the Hypotheses Behind It}
\hypersetup{pdftitle={Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It},
  pdfauthor={Xiaoyu Li}}
\author{Xiaoyu Li\thanks{University of New South Wales, \texttt{xiaoyulics@gmail.com}}}
\date{}

\begin{document}
\maketitle

\input{abstract}

\newpage
\setcounter{tocdepth}{2}
{\small\tableofcontents}
\newpage

\input{sec1_intro}
\input{sec2_prelim}
\input{sec3_threshold}
\input{sec4_precision}
\input{sec5_sat}
\input{sec6_ledger}
\input{sec7_outlook}

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{HAPM{\etalchar{+}}26}

\bibitem[AA22]{AA22}
Amol Aggarwal and Josh Alman.
\newblock Optimal-degree polynomial approximations for exponentials and
  {G}aussian kernel density estimation.
\newblock In {\em 37th Computational Complexity Conference (CCC)}, volume 234
  of {\em LIPIcs}, pages 22:1--22:23, 2022.
\newblock Proposition numbers refer to arXiv:2205.06249v1.

\bibitem[ACSS20]{ACSS20}
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song.
\newblock Algorithms and hardness for linear algebra on geometric graphs.
\newblock In {\em 61st IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 541--552, 2020.
\newblock Theorem numbers refer to arXiv:2011.02466v1.

\bibitem[AG24]{AG24}
Josh Alman and Yunfeng Guan.
\newblock Finer-grained hardness of kernel density estimation.
\newblock In {\em 39th Computational Complexity Conference (CCC)}, volume 300
  of {\em LIPIcs}, pages 35:1--35:21, 2024.
\newblock Theorem numbers refer to arXiv:2407.02372v1.

\bibitem[ARW17]{ARW17}
Amir Abboud, Aviad Rubinstein, and Ryan Williams.
\newblock Distributed {PCP} theorems for hardness of approximation in {P}.
\newblock In {\em 58th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 25--36, 2017.

\bibitem[AS23]{AS23}
Josh Alman and Zhao Song.
\newblock Fast attention requires bounded entries.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, pages 63117--63135, 2023.

\bibitem[AS24a]{AS24grad}
Josh Alman and Zhao Song.
\newblock The fine-grained complexity of gradient computation for training
  large language models.
\newblock In {\em Advances in Neural Information Processing Systems 37
  (NeurIPS)}, pages 61419--61454, 2024.
\newblock Theorem numbers refer to arXiv:2402.04497v1.

\bibitem[AS24b]{AS24tensor}
Josh Alman and Zhao Song.
\newblock How to capture higher-order correlations? {G}eneralizing matrix
  softmax attention to {K}ronecker computation.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 4306--4333, 2024.

\bibitem[AS25]{AS25rope}
Josh Alman and Zhao Song.
\newblock Fast {RoPE} attention: Combining the polynomial method and fast
  {F}ourier transform.
\newblock arXiv:2505.11892, 2025.

\bibitem[AV26]{AVW26}
Josh Alman and Virginia {Vassilevska Williams}.
\newblock Truly subquadratic {3SUM} and truly subcubic {APSP} via triangles in
  sparse lopsided graphs.
\newblock arXiv:2610.06783, 2026.

\bibitem[AW15]{AW15}
Josh Alman and Ryan Williams.
\newblock Probabilistic polynomials and {H}amming nearest neighbors.
\newblock In {\em 56th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 136--150, 2015.
\newblock Theorem numbers refer to arXiv:1507.05106v1.

\bibitem[AWY15]{AWY15}
Amir Abboud, Ryan Williams, and Huacheng Yu.
\newblock More applications of the polynomial method to algorithm design.
\newblock In {\em Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 218--230, 2015.

\bibitem[AY25]{AY25}
Josh Alman and Hantao Yu.
\newblock Fundamental limitations on subquadratic alternatives to transformers.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 47475--47498, 2025.

\bibitem[BIS17]{BIS17}
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt.
\newblock On the fine-grained complexity of empirical risk minimization: Kernel
  methods and neural networks.
\newblock In {\em Advances in Neural Information Processing Systems 30
  (NeurIPS)}, pages 4308--4318, 2017.

\bibitem[CGI{\etalchar{+}}16]{CGIMPS16}
Marco~L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan
  Paturi, and Stefan Schneider.
\newblock Nondeterministic extensions of the strong exponential time hypothesis
  and consequences for non-reducibility.
\newblock In {\em Proceedings of the 2016 ACM Conference on Innovations in
  Theoretical Computer Science (ITCS)}, pages 261--270, 2016.

\bibitem[Che18]{Che18}
Lijie Chen.
\newblock On the hardness of approximate and exact (bichromatic) maximum inner
  product.
\newblock In {\em 33rd Computational Complexity Conference (CCC)}, volume 102
  of {\em LIPIcs}, pages 14:1--14:45, 2018.
\newblock Lemma numbers refer to arXiv:1802.02325v2.

\bibitem[CHL{\etalchar{+}}24]{CHLSS24}
Yang Cao, Jiayan Huo, Yingyu Liang, Zhenmei Shi, and Zhao Song.
\newblock {RoPE} attention can be trained in almost linear time.
\newblock arXiv:2412.17316, 2024.

\bibitem[CKNS20]{CKNS20}
Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis.
\newblock Kernel density estimation through density constrained near neighbor
  search.
\newblock In {\em 61st IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 172--183, 2020.
\newblock Theorem numbers refer to arXiv:2011.06997v1.

\bibitem[{Cla}26]{Cla26}
{Claude (Anthropic)}.
\newblock A $2^{o(n)}$ time algorithm for 3-{SAT}.
\newblock Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026.
  \url{https://hexagonmath.org/2610.00577v1}. Lean development at
  \url{https://github.com/anthropics/formal-math/tree/main/eth}, 2026.

\bibitem[CLSS24]{CLSS24}
Yang Cao, Yingyu Liang, Zhenmei Shi, and Zhao Song.
\newblock Training tensor attention efficiently: From cubic to almost linear
  time.
\newblock arXiv:2405.16411, 2024.

\bibitem[CPA26]{CPA26}
Sayak Chakrabarti, Toniann Pitassi, and Josh Alman.
\newblock Poly-attention: A general scheme for higher-order self-attention.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 11844--11906, 2026.
\newblock arXiv:2602.02422.

\bibitem[CS17]{CS17}
Moses Charikar and Paris Siminelakis.
\newblock Hashing-based-estimators for kernel density in high dimensions.
\newblock In {\em 58th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 1032--1043, 2017.
\newblock Theorem numbers refer to arXiv:1808.10530v1.

\bibitem[CW16]{CW16}
Timothy~M. Chan and Ryan Williams.
\newblock Deterministic {APSP}, orthogonal vectors, and more: Quickly
  derandomizing {R}azborov--{S}molensky.
\newblock In {\em Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 1246--1255, 2016.

\bibitem[CW19]{CW19}
Lijie Chen and Ryan Williams.
\newblock An equivalence class for orthogonal vectors.
\newblock In {\em Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 21--40, 2019.

\bibitem[GHS{\etalchar{+}}26]{GHSXY25}
Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, and Christopher Ye.
\newblock Subquadratic algorithms and hardness for attention with any
  temperature.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 85672--85701, 2026.
\newblock Theorem numbers refer to arXiv:2505.14840v1.

\bibitem[HAPM{\etalchar{+}}26]{HAPTP26}
Lukas Haverbeck, Carmen {Amo Alonso}, Andres~Felipe Posada-Moreno, Sebastian
  Trimpe, and Marco Pavone.
\newblock Efficiently approximating attention is hard.
\newblock arXiv:2609.37261, 2026.

\bibitem[HJK{\etalchar{+}}24]{HJKMWZ24}
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David~P. Woodruff, and
  Amir Zandieh.
\newblock {HyperAttention}: Long-context attention in near-linear time.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 39310--39325, 2024.

\bibitem[HLSL24]{HLSL24}
Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu.
\newblock On computational limits of modern {H}opfield models: A fine-grained
  complexity analysis.
\newblock In {\em Proceedings of the 41st International Conference on Machine
  Learning (ICML)}, volume 235 of {\em PMLR}, pages 19327--19343, 2024.
\newblock arXiv:2402.04520.

\bibitem[HSK{\etalchar{+}}25]{HSKSL25}
Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu.
\newblock Computational limits of low-rank adaptation ({LoRA}) fine-tuning for
  transformer models.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 6167--6206, 2025.
\newblock Theorem numbers refer to arXiv:2406.03136v2.

\bibitem[HWG{\etalchar{+}}25]{HWGLSL25}
Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han
  Liu.
\newblock Fundamental limits of prompt tuning transformers: Universality,
  capacity and efficiency.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 29634--29686, 2025.
\newblock arXiv:2411.16525.

\bibitem[HWL{\etalchar{+}}24]{HWSL24}
Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu.
\newblock On statistical rates and provably efficient criteria of latent
  diffusion transformers ({DiTs}).
\newblock In {\em Advances in Neural Information Processing Systems 37
  (NeurIPS)}, pages 31562--31628, 2024.
\newblock arXiv:2407.01079.

\bibitem[IPZ01]{IPZ01}
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.
\newblock Which problems have strongly exponential complexity?
\newblock {\em Journal of Computer and System Sciences}, 63(4):512--530, 2001.

\bibitem[Kla03]{Kla03}
Hartmut Klauck.
\newblock Rectangle size bounds and threshold covers in communication
  complexity.
\newblock In {\em 18th Annual IEEE Conference on Computational Complexity
  (CCC)}, pages 118--134, 2003.
\newblock Theorem numbers refer to arXiv:cs/0208006.

\bibitem[KLL{\etalchar{+}}25]{KLLSSS25}
Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song.
\newblock On computational limits and provably efficient criteria of visual
  autoregressive models: A fine-grained complexity analysis.
\newblock arXiv:2501.04377, 2025.

\bibitem[KWH23]{KWH23}
Feyza~Duman Keles, Pruthuvi~Mahesakya Wijewardena, and Chinmay Hegde.
\newblock On the computational complexity of self-attention.
\newblock In {\em International Conference on Algorithmic Learning Theory
  (ALT)}, volume 201 of {\em PMLR}, pages 597--619, 2023.

\bibitem[Lam95]{Lam95}
Leslie Lamport.
\newblock How to write a proof.
\newblock {\em The American Mathematical Monthly}, 102(7):600--608, 1995.

\bibitem[Lam12]{Lam12}
Leslie Lamport.
\newblock How to write a 21st century proof.
\newblock {\em Journal of Fixed Point Theory and Applications}, 11(1):43--63,
  2012.

\bibitem[Li26]{Li26}
Xiaoyu Li.
\newblock What does the refutation of the {E}xponential {T}ime {H}ypothesis
  mean for learning theory?
\newblock Hexagon preprint hexagon:2610.00613v2, October 2026.
  \url{https://hexagonmath.org/2610.00613v2}, 2026.

\bibitem[{Ope}26]{OAI26}
{OpenAI}.
\newblock The {E}xponential {T}ime {H}ypothesis is false.
\newblock OpenAI Math Release preprint, dated October 17, 2026, revised October
  25, 2026, released October 26, 2026.
  \url{https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf},
  2026.

\bibitem[Raz92]{Raz92}
Alexander~A. Razborov.
\newblock On the distributional complexity of disjointness.
\newblock {\em Theoretical Computer Science}, 106(2):385--390, 1992.

\bibitem[Rub18]{Rub18}
Aviad Rubinstein.
\newblock Hardness of approximate nearest neighbor search.
\newblock In {\em Proceedings of the 50th Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 1260--1268, 2018.
\newblock Theorem numbers refer to arXiv:1803.00904v1.

\bibitem[SSWZ23]{SSWZ23}
Tamas Sarlos, Xingyou Song, David~P. Woodruff, and Qiuyi Zhang.
\newblock Hardness of low rank approximation of entrywise transformed matrix
  products.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, pages 52568--52582, 2023.
\newblock arXiv:2311.01960.

\bibitem[SXY26]{SXY26}
Barna Saha, Yinzhan Xu, and Christopher Ye.
\newblock Furthest pair requires quadratic time in superconstant dimension
  under {SETH}.
\newblock arXiv:2606.25887, 2026.

\bibitem[SXYY26]{SXYY26}
Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu.
\newblock On the computational hardness of transformers.
\newblock In {\em Proceedings of the 58th Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 1073--1084, 2026.
\newblock Theorem numbers refer to arXiv:2603.11332v1.

\bibitem[vSZ24]{vBSZ24}
Jan {van den Brand}, Zhao Song, and Tianyi Zhou.
\newblock Algorithm and hardness for dynamic attention maintenance in large
  language models.
\newblock In {\em Proceedings of the 41st International Conference on Machine
  Learning (ICML)}, volume 235 of {\em PMLR}, pages 49008--49028, 2024.
\newblock Lemma numbers refer to arXiv:2304.02207v1.

\bibitem[Wil05]{Wil05}
Ryan Williams.
\newblock A new algorithm for optimal 2-constraint satisfaction and its
  implications.
\newblock {\em Theoretical Computer Science}, 348(2--3):357--365, 2005.

\bibitem[ZHDK23]{ZHDK23}
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi.
\newblock {KDE}former: Accelerating transformers via kernel density estimation.
\newblock In {\em Proceedings of the 40th International Conference on Machine
  Learning (ICML)}, volume 202 of {\em PMLR}, pages 40605--40623, 2023.

\end{thebibliography}

\clearpage
\appendix
\crefalias{section}{appendix}
\crefalias{subsection}{appendix}
\input{app_0_roadmap}
\input{app_a_threshold}
\input{app_b_precision}
\input{app_c_sat}

\end{document}