arXiv · 2026 · Preprint

Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds

Zixuan Huang, Guozhang Chen

An algorithmic complexity analysis establishes faster subquadratic softmax attention bounds in fixed dimensions across arbitrary positive temperatures, matching maximum-inner-product limits.

The scientific question

What are the fundamental time-complexity limits of exact-temperature softmax attention in fixed dimensions?

Direct softmax attention compares all query-key pairs in quadratic time, creating a fundamental scalability bottleneck for long-context language, vision, and scientific AI models.

A score window retaining near-maximal keys while discarding a bounded tail.
Figure 1 from the preprint ↗

The core idea

Polylogarithmic-Error Fixed-Dimension Attention Algorithm

For any fixed head dimension, we design an approximation algorithm whose polylogarithmic dependence on coordinate magnitudes and inverse error supports arbitrary positive temperatures, alongside a reduction from batch maximum inner product.

What we found

Matching Best Known Inner-Product Bounds

The algorithm improves the previous fixed-dimension upper bound to match the best known batch maximum-inner-product bound in each fixed dimension, achieving near-linear runtime in dimensions two and three while reducing integer batch maximum inner product computation to a single attention call.

Continue the question

Related reading

Explore our research

Cite this work

Zixuan Huang, Guozhang Chen. Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds. arXiv, 2026. doi:10.48550/arXiv.2611.06055.