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

Sep 29, 2026

Efficiently Approximating Attention Is Hard

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.

Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno +2

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

Attention Approximation Efficient Attention Softmax Attention Sparse Attention

Ask PDF

May 22, 2026

Approaching I/O-optimality for Approximate Attention

We revisit the I/O complexity of attention in large language models. Given query-key-value matrices

Q,K,V\in\mathbb{R}^{n\times d}

, and a machine with fast memory size

M

, the goal is to compute the "attention matrix"

A=\text{softmax}(Q K ^{\top}/\sqrt{d}) V

with the minimal number of data transfers between fast and slow memory. Existing methods in the literature, most notably FlashAttention and its variants, incur an I/O cost that depends quadratically on the context length

n

, while a trivial lower bound only requires

Ω(nd)

I/O's to read the inputs and write the output. In this work we show that the dependence on

n

can be reduced to almost-linear, by developing I/O-efficient algorithms inspired by the recent approximate attention method of Alman and Song [NeurIPS'23]. We also provide (algorithm-specific) lower bounds in different parameter regimes, which nearly match the corresponding upper bounds, indicating that the proposed algorithms are indeed close to I/O-optimal.

Pál András Papp, Aleksandros Sobczyk, Anastasios Zouzias

Computing Systems Lab, Huawei Technologies, Zurich, Switzerland

Self-Attention Efficient Attention Memory-Efficient Attention

Ask PDF

Aug 28, 2026

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

How much matrix rank is required to preserve every bounded value output of normalized softmax attention? We study the unrestricted maximum-row-

\ell_1

approximation rank

r_\varepsilon(A)

, exactly the least rank achieving uniform error over all bounded vector-valued values. Row softmax exposes the intrinsic interaction

C=P_m(\log A)P_N

, whereas invertible

Q/K

gauges leave

A

fixed while changing the Euclidean geometry of a chosen query/key factorization. We replace that coordinate-dependent description by a projective residual

q(C-T)

and an attained factor-radius size

κ(T)

. For every rank-

r

retained interaction with

τ(T)<\varepsilon

, we prove

r_\varepsilon(A)\le \min\left\{ N,\; C_r\left( 1+\frac{κ(T)} {(\varepsilon-τ(T))^2} \right)^{r/2} \right\},

with the same unknown dimension constant as the underlying weighted Gibbs-row cover. The profile is gauge invariant, termwise no worse than native retained-subspace bounds at the same declared dimension, and has a worst-case sharp

r/2

size exponent at fixed

r

and

\varepsilon

. We then measure

r_\varepsilon(A)

directly on learned attention using 9,978 certified brackets across BERT, GPT-2, Qwen2.5, and two ViT checkpoints; where certificates do not close, the optimum remains interval-valued. A pre-specified 2,302-cell held-out study further shows that the historical native-coordinate geometry block contains coarse, mostly head-level information but no detectable incremental information beyond a strong calibrated baseline. The new intrinsic descriptor is not evaluated in that study. Together, the theory and measurements distinguish an operator-intrinsic complexity control from a stronger empirical explanation that the learned-head evidence does not support.

Yuhe Sui, Jianing Zhang, Yingzhi Tang

Nanyang Technological University, Singapore · Carnegie Mellon University

Softmax Attention Low-Rank Attention Low-Rank Approximation Attention Mechanisms

Ask PDF

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