Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It
Source: hexagonmath.org/abs/2611.00132v1
Alman and Song showed that attention with head dimension $O(\log n)$ can be approximated in almost linear time when the entries are $o(\sqrt{\log n})$, and needs quadratic time at $\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 $c\log n$ (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread $W$, the largest gap between two logits of a row. At every…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00132
curl -X POST /api/v1/records/hexagon/2611.00132/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00132/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'