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

Zixuan Huang; Guozhang Chen

cs.DSNov 4, 2026

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

Authors: Zixuan Huang, Guozhang Chen

Organizations: State Key Laboratory of Multimedia Information Processing, School of Computer Science, Peking University, Beijing, China · School of Physics, Peking University, Beijing, China · National Engineering Research Center of Visual Technology, School of Computer Science, Peking University, Beijing, China

Abstract

Attention is central to modern AI models for language, vision, and scientific modeling. However, direct evaluation compares every query with every key, requiring quadratic time in the context length, which limits its scalability to long contexts. Consequently, characterizing the complexity bounds of attention is of fundamental importance. For every fixed dimension $d$ , we give an algorithm for $m$ queries, $n$ key-value pairs, and additive error $\varepsilon$ , with expected time $\widetilde{\mathrm{O}}\bigl((mn)^{k/(k+1)}+m+n\bigr),\qquad k=\lfloor d/2\rfloor.$ For fixed dimension and a fixed number of value channels, soft-O hides factors of the form $\operatorname{poly}_d\bigl(b,\log(m+n),\log B,\log(1/\varepsilon)\bigr),$ where $b$ bounds input encoding lengths and $B$ bounds coordinate and value magnitudes. In particular, the dependence on $B$ and $1/\varepsilon$ is polylogarithmic, which allows arbitrary positive temperature. When $m=n$ and $d\ge2$ , the bound is $\widetilde{\mathrm{O}}(n^{2-2/(\lfloor d/2\rfloor+1)})$ : near-linear in dimensions two and three, with exponent $4/3$ in dimensions four and five and $3/2$ in dimensions six and seven. It improves the previous $\widetilde{\mathrm{O}}(n^{2-1/d})$ upper bound and matches the best known batch maximum-inner-product bound in each fixed dimension. Additionally, we reduce integer batch maximum inner product computation to one attention call with the same dimension and input sizes $m,n$ .

Figures & tables

Dimension	Time upper bounds $\widetilde{\mathrm{O}}(\cdot)$
Dimension	Prior work [ 38 ]	Offline counting baseline	This work	Batch Max-IP
$2$	$n^{3/2}$	$n^{4/3}$	$n$	$n$
$3$	$n^{5/3}$	$n^{3/2}$	$n$	$n$
$4$	$n^{7/4}$	$n^{8/5}$	$n^{4/3}$	$n^{4/3}$
$5$	$n^{9/5}$	$n^{5/3}$	$n^{4/3}$	$n^{4/3}$
$6$	$n^{11/6}$	$n^{12/7}$	$n^{3/2}$	$n^{3/2}$

Table 1: Time bounds and the offline counting baseline derived in Section 1.2.1 by combining polynomial approximation with offline halfspace range counting. Here

d

is fixed,

m=n

, coordinate encoding lengths are polylogarithmic, magnitudes are polynomial, and

\varepsilon=n^{-\mathrm{O}(1)}

. The exponent is the same in dimensions

2k

and

2k+1

, where

k=\lfloor d/2\rfloor

; the algorithm is Las Vegas for

d\geq 3

and deterministic for

d=2

. The last column lists the best known deterministic real-RAM bound for exact batch maximum inner product [ 51 , 27 , 43 , 13 ] , which reduces to attention by Theorem 3.1 .

Panel of Figure 1 — Figure 1: Scores in one attention row. The shaded interval contains the near-maximal keys; each omitted key contributes at most $B\mathrm{e}^{-L}$ to the shifted numerator.

Panel of Figure 2 — Figure 2: A schematic level of the random doubling prefix for $d=3$ , in the column orientation. (a) A square window of the maximizing regions of the perturbed functions in $P_{\ell}$ , with each polygon triangulated for the illustration. Thick lines bound the maximizing regions, and thin lines triangulate them. (b) The shaded cell $\Delta$ , with owner $s_{\Delta}$ , enlarged. Dashed lines separate the regions where different sources of $C_{\Delta}\cap B_{\ell}$ have the largest perturbed score. The markers represent targets in $\Delta$ whose first hit occurs after $P_{\ell}$ . Filled markers of the same shape share an anchor $s_{*}\in C_{\Delta}\cap B_{\ell}$ and form one anchor block with source set $C_{\Delta}$ ; hollow markers have their first hit in a later batch.

Panel of Figure 3 — Figure 3: A non-symmetric convex pentagon centered at its area centroid, with $h_{i}=3L>L$ . Blue marks the eligible boundary arc, and the orange dashed polygon is $(2/3)\mathcal{C}$ . All points in the shaded region, including its boundary, satisfy both retention conditions.

Panel of Figure 4 — Figure 4: One induction step, read clockwise from the upper left. Row shifts express attention through $\mathrm{KP}_{d}$ ; Lagrange temperature interpolation then gives $\mathrm{BP}_{d-1}$ , whose anchor blocks factor through $\mathrm{KP}_{d-1}$ . The induction ends at the planar kernel algorithm.

Panel of Figure 5 — Figure 5: Two possible anchor types for an original block $\bm{S}_{IJ}$ . The highlighted scores lie in $[-L_{\mathrm{anc}},0]$ . (a) Subtracting a column anchor’s score cancels the row bias; each kernel row then has its maximum over $I$ , so $\bm{T}$ has indices $J\times I$ and appears transposed. (b) Subtracting a row anchor’s score cancels the column bias; the maxima are over $J$ and $\bm{T}$ keeps indices $I\times J$ . Lemma 7.4 proves both factorizations and estimates their diagonal factors.

Efficient Attention

Efficient attention reduces the compute, memory traffic, and cache costs of Transformer attention while preserving useful long-range interactions.

See all 148 papers

Efficiently Approximating Attention Is Hard
Sep 29, 2026Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno +2Attention Approximation Efficient Attention
Institute for Data Science in Mechanical Engineering, RWTH Aachen University · Autonomous Systems Lab, Stanford University
Approaching I/O-optimality for Approximate Attention
May 22, 2026Pál András Papp, Aleksandros Sobczyk, Anastasios ZouziasSelf-Attention Efficient Attention
Computing Systems Lab, Huawei Technologies, Zurich, Switzerland
Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention
Aug 28, 2026Yuhe Sui, Jianing Zhang, Yingzhi TangSoftmax Attention Low-Rank Attention
Nanyang Technological University, Singapore · Carnegie Mellon University

Sep 29, 2026J/K move · Enter open · S save

Efficiently Approximating Attention Is Hard

Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe+1

Institute for Data Science in Mechanical Engineering, RWTH Aachen University · Autonomous Systems Lab, Stanford University

Attention Approximation Efficient Attention Softmax Attention Sparse Attention

Open paper AskPDF arXiv

Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.

Abstract

Efficient Attention

Explore similar work

Efficiently Approximating Attention Is Hard

Approaching I/O-optimality for Approximate Attention

Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention