arXiv · 2026 · Preprint
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
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.

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
- SFA: A Statistical Physics-Inspired Diffusion Transformer for Efficient and High-Quality Image GenerationarXiv · 2026
- Aligning Inductive Bias for Data-Efficient Generalization in State Space ModelsNeurIPS 2026 · 2026
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.