Subquadratic Algorithms and Hardness for Attention with Any Temperature
Authors: Shreya Gupta
Boyang Huang
Barna Saha
Yinzhan Xu
Christopher Ye
Venue: ICLR 2026 Poster (2026)
Keywords: Attention
Complexity
Primary area: learning theory
TL;DR: We resolve the complexity of Attention for any temperature and (almost) any head dimension.

Abstract: Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length $n$. Alman and Song showed that when the head dimension $d = \Theta(\log n)$, subquadratic Attention is possible if and only if the inputs have small entries bounded by $B = o(\sqrt{\log n})$ in absolute values, under the Strong Exponential Time Hypothesis ($\mathsf{SETH}$). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for $d=\Theta(\log n)$. Running times of these algorithms depend exponentially on $B$ and thus they do not lead to even a polynomial-time algorithm outside the specific range of $B$. 

This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size $B$? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant $d = O(1)$, we give the first subquadratic $\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$ time algorithm for Attention with large $B$. Our result holds even for matrices with large head dimension if they have low rank. Combined with a reduction from Gradient Computation to Attention, we obtain a subquadratic algorithm for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when $d = 2^{\Theta(\log^* n)}$,  Attention requires $n^{2 - o(1)}$ time under $\mathsf{SETH}$.

Finally, in the regime where $d = \mathrm{poly}(n)$, the standard algorithm requires $O(n^{2} d)$ time while previous lower bounds only ruled out algorithms with truly subquadratic time in $n$. We close this gap and show that the standard algorithm is optimal under popular fine-grained complexity assumptions.

Published as a conference paper at ICLR 2026
SUBQUADRATIC ALGORITHMS AND HARDNESS FOR ATTENTION WITH ANY TEMPERATURE
Shreya Gupta
Boyang Huang Yale New Haven, CT
UW
Seattle, WA sgupta63ccs
boyang www.ghaale...eeeeeee
Barna Saha
Yinzhan Xu UCSD La Jolla, CA syzhan@ucsda edu
Christopher Ye UCSD La Jolla, CA czye@ucsd edu
UCSD La Jolla, CA bssha@ucsd.
ABSTRACT
Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length n. Alman and Song showed that when the head dimension = O n), sub- quadratic Attention is possible if and only if the inputs have small entries bounded by B of o(vlogn) n)) absolute values, under the Strong Exponential Time Hy- pothesis (SETH). Equivalently, subquadratic Attention is possible if and only if the softmax is applicd with high temperature for d = (log n)). Rumning times these algorithms depend exponentially B and thus they do not lead polynomial-time algorithm outside the specific range of
This naturally leads to the question: when can Attention computed efficiently without strong assumptions temperature? Are there fast attention algorithms that scale polylogarthhmically with entry size B? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant d O(1), give the first subquadratic 2 1/d polylog(B) (B) time algorithm for Attention with large B. Our result holds even for matrices with large head dimension if they have low rank. Combined with reduction from Gradient Computation to Attention, we obtain a subquadratic algorithm for the full LLM training process. Furthermore, we show that any substantial improvement algorithm is unlikely. In particular, we show that when d = 29(lo n), Attention requires 2-2((1) time under SETH.
Finally, in the regime where = poly (n), the standard algorithm requires (n time while previous lower bounds only ruled out algorithms with truly subquadratic time in n. We close this gap and show that the standard algorithm is optimal under popular fine-grained complexity assumptions.
INTRODUCTION
Large Language Models powered by the Transformer architecture (Vaswani et al., 2017) have been at the heart of modern Al revolution completely reshaping the landscapes of natural language processing, computer vision, and multitude of other applications. The Attention mechanism is the cornerstone of the Transformer architecture. Attention computes correlations between different tokens of the sequences, allowing Transformers model dependencies regardless of the position of the tokens in the sequences. Despite its popularity, standard algorithms for computing Attention require quadratic time complexity, as they compute the Attention matrix explicitly.
Formally, the Attention mechanism is defined as follows. Let Q, K, V be size n x d matrices (respectively query, key and value matrices). We call the context length and d the head dimension.

---

Published as a conference paper at ICLR 2026
The Attention matrix is obtained by applying softmax' to each row of QK Each entry in the matrix represents the attention weight between a particular imput token (query token Q) and output token (key token K). Finally, Attention outputs the product of the Attention matrix with V.
We give the formal definition below. Note that exp(X) applics exp to each entry of a matrix X.
Definition 1.1 (Attention). Given input matrices Q, K, V E IRaxd Attention on Q, K, V is defined Attention @Q K, V) == D- Raxd where exp(QK and D == diag(A1).
In practice, there is an input X E Raxd and weight matrices Wo. WK, Wv E Rddd such that Q XWQ. K XWK, V XWy. Since Q, K, V can be computed from X, Wq. WK, Wy in Onnd) time, we assume for simplicity that the inputs Q, K, V are given directly.
Typically, it suffices to approximately perform Attention computations. In particular, is not necessary (or even reasonable) to expect Attention to be computed exactly due to the softmax operation. Thus, we study Approximate Attention, where each entry is computed with polynomial precision (i.e. inverse polynomial additive error).
Definition 1.2 (Approximate Attention Computation AttC(n, d, B,))). Given matrices Q.K,V V [-B, B|ndd and B, > 0, compute O E Raidd such that ||O - Attentionn(2 (Q, K, 1l < E.
The standard (and most widely used) algorithm for Attention (even in approximate form) requires quadratic time. The algorithm begins by explicitly computing matrix product QK! applies softmax to obtain D-1 A and then computes the matrix product (D- A)V. Using standard matrix multiplica- tion, this requires (n''d) d) time. Even ignoring computation time of matrix multiplication, explicitly computing the A matrix already requires ?2(n²) time.
However, the inputs (and outputs) only have size O(nd). Indeed, an algorithm that does not compute A explicitly could compute Attention in ((nd) time, incurring only linear dependence on the context length n. This leads to the fundamental question concerning the complexity of Attention.
Question 1: When can Attention be computed faster than n² time?
Towards answering this question, Alman & Song (2024a) showed that for d Olog rt). Attention can be computed in n ++((1) time whenever B of Vlog n). Furthermore, whenever B 22 n) and d = Olog n),, Attention requires n 2-1) time under SETH, popular hardness hypothesis.
Yet there remain several shortcomings in our current understanding of Attention. Fast algorithms for Attention are only known for inputs with small entries (i.e. B = ((Vloog))) Such strong bound on the entries of Q, K essentially restricts the Attention mechanism to use softmax with high temperature (enforcing near- caaurunfform distribution over the value matrix). Temperature, denoted by T, is a key hyperparameter for Attention that dictates how random the output is. Formally, Attention with temperature T replaces A corresponds to high entropy (more likely to select keys with lower scores). In many tasks across machine learning, temperature a key hyperparameter with potentially significant impact on accuracy and stability (Agarwala et al., 2023; Xuan et al., 2025). While the original transformer of Vaswani et al. (2017) fixes attention temperature to @(va) and only varies temperature in the final softmax layer, recent works have shown that varying attention temperature (in some cases even setting it as a learnable parameter) can improve performance across NLP and vision applications (Lin et al., 2018; Zhang et al., 2022; Peng et al., 2023; Lee et al., 2021; Chen et al., 2023; Dufter et al., 2020; Zou et al., 2024; Demir & Dogan, 2025). Indeed, Alman & Song (2025b) prove that transformers with high temperature are provably less expressive. Beyond transformers, in contrastive learning, temperature has been found to significantly impact both the accuracy (Chen et al., 2020; Wang & Liu, 2021; Hu et al., 2021) as well as the learned representations (Wang & Isola, 2020; Wang & Liu, 2021; Robinson al., 2021) of the model. Dynamically varying temperature throughout the training process can also help balance multiple training objectives (Khaertdinov et al., 2022; Kukleva et al., 2023; Manna et al., 2023). In instances where low entropy is required, subquadratic algorithms are known.
(QP] with A == exp(QK* /T) so that high temperature
Given a vector applying softmax replaces 2, with exp(x,)/ E, exp(x;). In practice, scaled dot- dot-product attention, defined as A == (QKT /Vd), is also commonly used for training efficiency Vaswani et al. (2017).
2

---

Published as a conference paper at ICLR 2026
Furthermore, it is generally undesirable for the running time of an algorithm scale poorly with the numerical values of the input. In fact for many fundamental problems (Knapsack, All-Pairs Shortest Paths, 3-SUM), having small entries makes the problems much easier. For example, there is a simple pseudo-polynomial time dynamic programming algorithm for Knapsack, while designing polynomial time algorithm for Knapsack is NP-complete." Therefore, in this work study algorithms for Attention that scale polynomially with the representation length of the entries. Equivalently, the algorithm should scale polylogarithmially with the entry size B.
Currently, the only known algorithms for Attention beyond the standard Onndd) algorithm scales exponentially with the entry size B (Alman & Song, 2024a). Following the terminology of pseudo- polynomial time, we will call an algorithm that is subquadratic but scaling polynomially (or worse) with the numerical value of the input pseudo-subquadraatic We call an algorithm that is subquadratic and scales logarithmically with the numerical value of the inputs simply subquadratic. Following from our above discussion, the question of whether subquadratic algorithms for Attention exist remains open." Even if d = O(), there is a tantalizing gap between the O(n²) upper bound and the ((1)) lower bound.
Juuquuarrra,,, or
Question 2: Is there a truly (non-psee moon-pseudo-an juuuddd--uuuuurtttte algorithm for Attention?
In our work, we resolve this question for almost all regimes of head dimension d. Our main result gives the first truly sub-quadratic algorithm for attention that scales polylogarithmically with entry-size B. Our algorithm obtains truly sub-quadratic time for constant d.a
Theorem 1.1 (Main Theorem). Let = O(1). There is an algorithm that computes AttC(n, d, B, g)
in 2nn2-1/d polylog(B/s)) time.
The result also generalizes to the case where the matrices Q, K have low rank.
Theorem 1.2. Letr O1). There is an Ô (nd + 22-1// polylog(B/e)) time algorithm comput- ing AttC(n, d, B, where r = (annannk))) rank(a))
As side result, we complement this algorithm with a subquadratic algorithm for Attention Gradient Computation. In the training process, gradient descent tunes the weight matrices We. WK. Wy according to the input data. In contrast to previous algorithms which give ad hoc algorithms for gradient computation, we show that gradient computation computation. Combined with our previous result, we give a truly pettt-sssoooosuuuuaeeee for the full LLM training process when d = O(1).
be generically reduced to attention
algorithm
Theorem 1.3 (Informal Theorem B. The Attention gradient can be computed with O(d) calls to AttC(n, d, B, /.eeO(nd with (nd?) overhead. In particular, if d = O(1) the Attention gradient can be computed in ((22-1/4polylo (B/))) time.
Above, we obtain a sub-quadratic algorithm for constant When d= (1) is super-constant, the above algorithms requires 2=))(1)) time. Is there a truly subquadratic algorithm for super-constant d? Our remaining results provide stronger lower bounds for super-constant d. Alman & Song (2024a) show that 2-01) time is necessary when d = ((log under the Strong Exponential Time Hypothesis (SETH). Under the same hardness assumption we provide a much stronger lower bound and show that Attention is hard even when d -0tllog' n),7
Theorem 1.4 (Informal Theorem C.4). Under SETH, AttC(n, d, B,e) requires n² 2--((1) time for d 20ng n) and B (nly
It suffices to consider instances with polynomial entry size B = poly(n) since any (non-pseudo-) subquadratic algorithm must handle such instances in subquadratic time. Formally, we show that
'An algorithm runs in seeudo-polyoomia time if its running time is polynomial in the numerical value of the input. A polynomial time algorithm must be polynomial in the length of the input.
*Similarly, while there are pseudo-subeubic algorithms for APSP (e.g.. Shoshan & Zwick (1999); Zwick (2002)), there is no truly subcubic (O(n² for some >> 0) algorithm.
An algorithm runs in truly subquadratic time if runs in O(z² time for some > 0
We use Ō(-) notation to suppress polylogarithmic factors.
"log" denotes the iterated logarithm. For example, log" (16) 3 since log log log 16 S 1.
3

---

Published as a conference paper at ICLR 2026
any fast algorithm for AttC d, E) implies fast algorithm for (Bichromatic) Maximum Inner Product (Max-IP) on d-dimensional vectors with integer entries. The (Bichromatic) Max-IP problem asks an algorithm given two sets of vectors A, B _ zd to compute maXae b. Under SETH, this requires n²2-0(1) time whenever d 200 n) (Chen, 2018). Furthermore, the best known algorithms for Max-IP run in n² (2///) time (Yao, 1982; Agarwal et al., 1991; Matoušek, 1992) so that any algorithm improving significantly over Theorem 1.1 must improve upon the best known algorithms for Max-IP. Chen (2018) conjectures that no such algorithm exists under SETH.
Stronger Lower Bounds for Large Head Dimension. The head dimension d can often be relatively large with respect the context length n (in some cases Vaswani et al. (2017), the head dimension d can even be larger than the context length n). In these settings, a large gap remains between the standard algorithm requiring O(n²d) dl time and the known n² 21=)(1) lower bound. We address this gap and shows that the standard algorithm is conditionally optimal.
Our conditional lower bound depends on a natural generalization of a popular hypothesis. The Orthogonal Vectors (OV) problem is among the most well studied problems in fine-grained complexity. In the OV problem, an algorithm is given two sets of n vectors A, B S {0. 1)" and is asked to determine if there exists an orthogonal pair E A, b E B such that b = 0. The naive algorithm for this problem requires (n²d) time and the current best algorithm for OV achieves truly subquadratic time only for d = O r.) (Abboud et al., 2015b; Chan & Williams, 2016). A central hypothesis (known the OV Hypothesis) in fine-grained complexity states that there is no =2²o(1) algorithm for OV whenever d = w(og n), and the OV Hypothesis is known to hold under SETH (Williams, 2004).
If = (nly(n), one can compute a - b for all pairs a E A. E B using a matrix product between an x d matrix containing the vectors in A as rows and a d matrix containing the vectors of B as columns. The above algorithm requires O(T MUL (n, d, n)) time, where T (a, b, c) is the time complexity for multiplying an b matrix with b x matrix. The High-Dimensional OV Hypothesis introduced by Dalirrooyfard & Kaufmann (2021) hypothesized that when d = n, any algorithm computing OV requires (n, nt n)n 1o(() = n n())(() time, where w < 2.3714 denotes the square matrix multiplication exponent (Alman et al., 2025). We consider a generalization of their hypothesis: the MuUL (n, d, n)t n)1 -001) running time is required for any d poly(n). We call it the Generalized High-Dimensiona OV Hypothesis.
Under this hypothesis, we show that the standard algorithm for computing Attention is optimal. Note that using fast matrix multiplication, one can easily obtain an algorithm for Attention using O(TMUL (n, d, n)) time.
Theorem 1.5 (Informal Theorem C.5). Under the Generalized High- high-DDimessioal OV Hypothesis, AttC(n, d, B,E) requires MML((1 d, n) 11)) time for poly(n).
Table 1 summarizes our results. In particular, we tightly characterize the complexity of Attention (up to aub-polynomial factors) when B = poly(n) for all regimes of d except 1 < d < 28(log" n) Within this regime, our running time matches the best known algorithms for Max-IP (Yao, 1982; Agarwal et al., 1991; Matoušek, 1992), and as mentioned earlier, significant improvements over our algorithm will imply improvements over the current best known algorithms for Max-IP which will be breakthrough.
1.1 TECHNICAL OVERVIEW
In this section, we give a high level overview of our algorithm. For simplicity, we focus on the d = 1 case in this overview. Given inputs q, k. u E R", our goal is to compute o, = E, Pi for all i where Pi.j are probabilities in the softmax distribution proportional to exp(g.k;))
Our first observation is that small key values can be discarded: in particular, we show that for each i it suffices to only consider keys where q,k, is near the maximum. Assume without loss of generality that q > 0 and let kmax = max, ky. For appropriate threshold t, we define j to be irrelevant (with respect to q,) if 9;4g S qıkmaa t and relevant otherwise. By setting t = ((log(n/E) (E)). we can ensure that all softmax probabilities corresponding to irrelevant indices are negligible. Since discarding such j does not significantly change the value of the output significantly, we consider only relevant j for the remainder of the overview.
4

---

Published as a conference paper at ICLR 2026
Table 1: Summary of known results when B poly(n) and 1/poly(n). Sub-polynomial dependencies are suppressed for simplicity. Previous upper bounds that are not starred follow from the standard algorithm for computing attention (Vaswani et al., 2017). Previous lower bounds that are not starred are trivial and follow directly from input and output size. * The starred results are due to Alman Song (2024a). For d = (log their lower bound holds when B = S2( (2(Vogg)) while ours holds even when B 2 log 2.
Upper Bound
I Lower Bound
Previous
New
Previous
New
((1) 20 m) O(logn) poly(n)
n² n²
2-1d (1.1)
22-o(1) (1.4)
n²
n 21-a(1x
2²-o(1) (C.7)
TMUL (n, d,
n² 21=o(1)
TmuL(n, d, n) 1o(1) (1.5)
Relevant Indices +
k1
13
k4
lss
k6
kr
ki
Value (v)
6
3
8
5
7
4
2
Key (k) 0.5
1.8
2.6
4.5
6.1
7.4
8.2
9.4
Rounding (k)
00
4
7
10
10
10
Figure I: Rounding based algorithm for 1-dimensional Attention illustrated for gi 1. Each point is placed at ky and has value Vy. Points (e.g. kt) such that q:ki; < 4.kmax are irrelevant and discarded (in this example kmmaxx = 1). Relevant points with similar k, (e.g. {Kig, kig) or (ke, k7, ks)) are grouped together and assigned the same (rounded) key K. The width of each region is log(1 (in this example log(1 E) 3). The algorithm outputs Pf where P,, x exp(F;))
Combining this observation with a simple rounding scheme, we already obtain modest improvement over known algorithms for Attention. We illustrate this for the d = 1 case. Consider relevant key ky. If we round such k; to k, such that g,yy S q S q:ky + log(1 + =). then en is (1 + e)- multiplicative approximation of eack; This gives us good multiplicative approximations of the softmax probabilities. Plugging in these approximate probabilities, we obtain good multiplicative approximation of the output.
Since the value of the output is bounded by entries of the value matrix V. (i.e. o, = O(B),, this gives a e B-additive approximation of the output. compute the approximation, we can now treat all keys ky that are rounded to the same value k, as equivalent. Since relevant keys are within a range of length t and we round all keys within log(1 + E) to the same value, we only need to consider Ol1 log(1 1 =)) ((1/s) intervals for each query. Now, we leverage the fact that similar ky lie in contiguous intervals to design an efficient data structure. particular, we can preprocess the keys in ((n) time to ensure that we can query the sum of all values in each continuous interval keys Ö(1) time. Repeating this procedure for all queries and scaling the approximation factor (recall that our goal is to compute an E-additive approximation), we obtain an algorithm that computes an s-additive approximation of attention in total time O(BB/s). Figure illustrates the rounding scheme.
The above rounding method gives polynomial dependence on the entry bound B, and is only subquadratic when B = on)). Although this already improves on Alman Song (2024a)'s algorithm (which exhibits exponential dependence B, and thus only worked for values of B of Vlog n)), we would like a truly subquadratic algorithm for all polynomial B. To do this, we leverage the powerful polynomial method in algorithm design (see e.g. Williams (2018); Abboud et al. (2015a)).
natural attempt to utilize the polynomial method to approximate ex with polynomial. As simple case, by approximating ex 1 + x we can compute exp(QKT)V T QKTV
5

---

Published as a conference paper at ICLR 2026
efficiently. However, E* can only be approximated well by polynomials with degree p when | S p (Aggarwal & Alman, 2022). For a rank d = O11) matrix QK" exp(QKK)) can be upproximated with a rank 20(B²) matrix. Using this observation (as in Alman & Song (2024a)) one can obtain a subquadratic algorithm by assuming B = olvlog n), , but this approach falls short of obtaining sub-quadratic algorithms for polynomial B.
We now describe how to obtain truly sub-quadratic algorithm by leveraging the polynomial method only on relevant indices. For simplicity, consider 1 1-dimensional Attention. For x = O()), there is low-degree polynomial P such that [((x)=expé [x)] < E ex)(()). In order to apply this approximation. we crucially use the fact that irrelevant indices are discarded, since the relevant indices have 9: lying within an interval of length (t). Since the probabilities are normalized, we can further assume that this interval lies around 0, allowing to approximate exp with polynomial. Formally, we define = maxj 9:ky - O(t) and observe that exp(g:kz) is proportional to exp(qik; ct). Then, we can approximate pi.j which is proportional
exp(q:kj - (a) with polynomial P that approximates exp on the range (t), since for all relevant indices q, k,ki
= O(). We denote Pr,5 x Plyck c4) as our approximate probabilities and output 6 = Σ, P.. As above, if the approximate probabilities are accurate, our output is a good multiplicative approximation of attention computation.
It remains to argue that our algorithm is efficient. Note that it suffices to describe how to compute E, P(akk - G))y over relevant since we can compute o; by computing this quantity twice (once with and once with replaced by 1 for normalization). The idea is that in contrast to the exponential function, the polynomial kig:k - 0:) can be decoupled into a product of terms that only depend on q. and terms that only depend on k; (see Equation (2) for example). As in the rounding scheme, use the fact that relevant keys lie in a continuous interval to create data-structure that preprocesses the terms depending on ki in ((n) time, while for each query qı efficiently supports queries to relevant precomputed values in Ô(1) time.
Generalizing to Higher Dimensions. What happens when we try to generalize this algorithm to higher dimensions? In one dimension, we knew that for each i, the set of relevant j included all where q:k, 2 qinimax I. In higher dimensions, our goal similarly to compute a set of relevant indices relative to each Q2 such that (I) discarding irrelevant indices outside this range does not significantly affect the additive error of our estimate and (2) the range of Q K, is now sufficiently restricted so that
low-degree polynomial approximate exp(Q, -K)).
In one dimension, the set of all relevant j consists exactly of the set of sufficiently large ky (either in the positive negative direction). A simple interval searching data structure can support the necessary queries. In d > dimensions, each row of Q, K (denoted Q., K,) is now a d-dimensional vector. Even in 2 dimensions, different K₃ may be larger with respect to different Qi. Sorting all Ký with respect each Qi already requires n² time. Instead, the key observation is that the set of relevant j with respect to Q; is exactly the set of Kj contained in the half-space
Rdd Qi x max Q2 K3 -
This can be handled with a simplex range-searching data structure (Matoušek, 1992). In particular, we can initialize the data structure using points {Kj} so that for each Qi we can query the data structure for the appropriate half-space. Matoušek's data structure supports queries in Ö(n²~1/á time and computes the sum of the weights assigned to all points in the half-space. Since in high dimensions, the number of monomials in the polynomial P grows exponentially in dimension d, need instantiate and query (d) instances of Matoušek's 's data structure. Still, for constant = O11,, this only occurs sub-polynomia factors in runtime. Using appropriate queries to the data structure over all i, our algorithm requires 2(n2-1/d) time. Figure 2 illustrates the algorithm.
Generalizing to Low Rank Matrices. To generalize the algorithm for low-rank matrices Q, K with rank r, we may decompose Q = V2VT ; K = UK V where UQ. Vo, UK, Vx are x r matrices.
Then, obtain Theorem 1.2 by applying Theorem 1.1 to Q' Uq and K'T Vo V.UKV V which may be computed in O(nr) time.
Outline. We give our algorithm in Section 3. The reduction from gradient computation to Attention computation is given in Appendix B. Our lower bounds are presented in Appendix C.

---

Published as a conference paper at ICLR 2026
Figure 2:
Algorithm for d-dimensional Attention illustrated for Q: = (2, 1). Relevant points are in the shaded blue region. Irrelevant points are in the white region. Weights are omitted for clarity.
1.2 RELATED WORK
Approximate Attention Computation. In an orthogonal line of work, many approximate notions of Attention have been studied to reduce its compute constraints with the goal of computing an approximation in linear time (Brown et al., 2020; Beltagy et al., 2020; Choromanski et al., 2020; Daras et al., 2020; Katharopoulos et al., 2020; Kitaev et al., 2020; Wang et al., 2020; Zaheer et al., 2020; Chen al., 2021; Choromanski et al., 2021; Xiong et al., 2021; Gao et al., 2023a; Panigrahi et al., 2023; Malladi et al., 2023). Several works obtain provable guarantees well as practical improvements (Zandich et al., 2023; Han et al., 2024; Kacham ct al., 2024). However, these works only obtain theoretical guarantees with respect to matrix norms such operator norm rather than any guarantee on the correctness each entry. Indeed, our lower bounds show that linear time approximations do not obtain such strong approximation guarantees.
In the low dimension regime d = o(log n), the Fast Multipole Method gives fast algorithms for the related Gaussian Kernel Density Estimation (KDE) problem (Alman & Guan, 2024). However, these algorithms do not apply in our regime of polynomial entries. In particular, using the standard reduction from Attention Gaussian KDE the error produced by the known KDE algorithms is amplified that only Attention with subpolynomial entries B 20(logn) can be computed efficiently, even with constant dimension = O())
Attention with MIP Units. Many works have studied the expressive power of Transformers (Sanford et al., 2023; 2024b;a; Yehudai et al., 2025) for classical algorithmic problems. In an independent work (Alman & Yu, 2025) show that Attention unit with input and output MIP Layers can compute OV and (Monochromaticc) Max-IP. While the constructions are similar, we reduce (Bichromatic) Max-IP Attention, and thus obtain a strong conditional lower bound for d d 20 n) via (Chen, 2018).
Rather than allowing arbitrary inputs Q, K, V E Raxd these works consider Attention with MLP Units: Given inputs X E Rxxd and Wq. WK, Wy Rd xd compute Q XW q. K XWK, K, V XWy and then Attention(Q, K, V). This preprocessing step requires only O(nd²) time and does not change the running time of our algorithm. Via a simple modification (to either our construction or (Alman Yu, 2025)), 9 it is possible show that an Attention unit with MLP Units can compute (Bichromatic) Max-IP. Our reductions from OV naturally hold for bichromatic instances as well.
Variants of Attention and Transformers Several works have studied variants of attention and transformers (Hu al., 2024; Ke et al., 2025), including several which leverage the polynomial method for fast computation (Alman & Song, 2023; 2025a).
Attention Computation in Alternative Settings. Attention has also been studied several settings, including differential privacy (Gao et al., 2023c), fine-tuning (Hu et al., 2025), dynamic updates (Brand et al., 2023), quantum algorithms (Gao al., 2023b), and I/O complexity (Saha & Ye, 2024).
$ Map + (x, 0,rz) and y (v. ry. 0) for appropriate 7z, Ty so that ||ا yll 2x. y for some constant
We describe how to obtain Q. K. Given sets of vectors A, B d let X RR consist of A in the first d columns, B in the next d columns. Let Wq (Ia 0) and Wx = (0 Ia).
7

---

Published as a conference paper at ICLR 2026
Conditional lower bounds for Attention have been studied as well (Keles et al., 2023; Alman & Song, 2024a;b; Alman & Yu, 2025).
2
PRELIMINARIES
We begin with the relevant definitions. Let log denote the natural log. Let [n] = (1,2.....,1) For a matrix M E Raxm we denote its (i.j)-entry by Maj- its transpose M and its inverse M- Let || = max,, j [Ma and exp(M) denote applying ex entry-wise to M. Let O and denote the all zeros and all ones vectors, For vector E R", diag(e) denotes the n diagonal matrix whose (i, i)-entry equals
Fine-grained Complexity Hypotheses. We establish new fine-grained lower bounds for the approxi- mate attention computation problem AttC(n, d, B) These lower bounds are conditional on some well-known fine-grained complexity hypotheses, which we introduce below.
The Strong Exponential Time Hypothesis (SETH) was introduced by Impagliazzo & Paturi (2001).
They hypothesized that solving k-SAT for cannot be significantly improved beyond exhaustive search.
Hypothesis 2.1 (Strong Exponential Time Hypothesis (SETH)). For every > 0, there is a positive integer 2 such that k-SAT on formulas with n variables cannot be solved in ((2(1=)))) time, even by randomized algorithms.
SETH is strengthening of the famous P * NP conjecture and has later been used to derive fine-grained lower bounds for many fundamental computational problems, from string edit distance (Backurs & Indyk, 2018) to graph diameter (Roditty & Vassilevska Williams, 2013). 3). Our lower bounds under SETH will proceed via reduction to the Orthogonal Vectors (OV) Problem and the Max-IP Problem.
Theorem 2.2 (Williams (2004)), Assuming SETH, for any 5 >> 0 there is constant C such that any randomized algorithm solving OV in dimension d = log n with high probability requires (m 2- time.
The Max-IP problem asks to compute given sets of integer-valued vectors A, B E Zd, m,x a- b. Chen (2018) showed that computing Max-IP requires 2-2o(1) time even when d = 20 n)
Theorem 2.3 (Chen (2018)). Assuming SETH. for any 8 >> 0 there is a constant C' such that any exact algorithm for Max-IP in dimension Clog" n with O(log -biti entries requires 2(n2-6) time.
FAST ATTENTION FOR CONSTANT HEAD DIMENSION
In this section, we present our algorithms for computing Attention in truly subquadratic time for constant head dimension d and polynomial entry size B.
Theorem 1.1 (Main Theorem). Let O(1). There is an algorithm that computes AttC(n, d, B) in ( polylog( B/e)) time.
The algorithm naturally extends to the case when d is large but the matrices are low dimensional. Omitted proofs in this section may be found in Appendix A.2. A key tool we require is efficient data structure for the range searching problem.
Definition 3.1 (Simplex Range Searching). Preprocess a weighted point set ((ks, w;)) where k; R and E E so that given any simplex query a,, the data structure returns Ekyeo Wi.
Matoušek gives an efficient data structure for the simplex range searching problem. In our work, we will only query the data structure with halfspaces a, which are special case of simplex queries (one can imagine simplex defined by the half-space and sufficiently large bounding box that contains all input points).
Theorem 3.1 (Matoušek (1992)). There data structure RSDS for the Simplex Range Searching problem for input points in d-dimension with Onllog preprocessing and ((n--1/d) query time.
8

---

Published as a conference paper at ICLR 2026
Given this data structure, present our algorithm for arbitrary head dimension d. Our inputs n x d matrices Q, K, V with entries in [-B, B). Our goal to compute the n X d output matrix O = Attention(Q, K, V). We rewrite Oi. Σ, PipiV where Piçi Σn (gp))
exp(Q; K2).
Step 1:
Removing Irrelevant Keys. We begin by showing that removing irrelevant keys does not significantly alter the quality of the approximation. Define for each [n] the maximum probability
(i) in the distribution Pi.j as Pmaxx = max, Pi.j- Let Smax denote the maximum integer s such that the half-space
{ R Qi s slog(1 + +)}
contains at least one Ký vector. In particular, Smax is the largest integer satisfying max, Qi K2 2 (6) Smax log(1 s). We now define relevant and irrelevant keys.
Definition 3.2. Let j E [n] be irrelevant with respect to Qi if Qi Kÿ < 8max log(1 + - logn Otherwise j is relevant with respect Q.- When Q; is clear, we simply say is irrelevant relevant.
We argue that we can discard irrelevant indices.
Pi. Lemma 3.2. Define pi Eintone Piis i j is relevant and 0 otherwise for all i, E [n]. Let
0 E,P%% V for all i [n],t [d]. Then 0 Ora S 3:B.
Step 2: Polynomial Approximation of Exponential. We then show how to use polynomial approximations of ee to efficiently estimate attention. We require the following result:
Lemma 3.3 (Aggarwal & Alman (2022); Alman & Song (2024a)). Let E < 0.1. There is a
polynomial P IR R of degree g = max
log(log(1/2)/B) B)) such that for all [-BB, B).
log(1/s)
we have P(x)) exp(x)) exp(x)) Moreover, its coefficients rationals with poly(g)-bit integer numerators and denoninators and can be computed in
Consider an entry Oi,t. We first remove irrelevant with respect to Q; and aim to approximate O,1)- Recall that
0.7-= = EE! Vn Exelevant ; exp(Q; K3)V
Exelevant J exp(Qi K5 - eQQi))VBB
Erelevant exp(Q; K2) Erelevant j exp(Q; K₁ c(Q.))
where c(Q,) == 8mix log(1 + log(n/E).
By the definition of 1i we have that for all relevant Q. K E [0, log(n/s) log(1 +e)] We then invoke Lemma 3.3 to obtain g = colylog(n//))o))
polynomial such that for all E [0, loggn/s)) + log(1 + =)] [0, 2 log(n/e)), [2 exp(x)) S & exp(x)). Define for relevant j. Pr.j x P(Q; K;- - c(Q:)) as an approximation of P.g x exp(Q; K₃ c(Qi)). For irrelevant j.
set Pr. Pij = 0. Then, define oz,- = ES We claim Ôz, is good approximation.
Lemma 3.4. |Ô,, O., S 7e for all e [m], E [d].
Furthermore, we present an algorithm that computes Ô efficiently, The key ingredient to the algorithm is the following data structure which utilizes the range searching data structure of Matoušek (1992). Lemma 3.5. Given matrices Q, K, V E gnxd there exist functions co.... &s such that any entry Ôz can be computed with g ((d) queries to du and Φr and g ((d) additional time.
Furthermore, for each Ór with < t S d there is data structure with Ô (() logn) preprocess- ing and Ô (()) 1-1/d log( B/E)) query time.
We bound the running time of Algorithm 1. Lemma 3.6. ApproxAttention (Algorithmm 1) runs in time Ô (n2-1/d 1/d polylog(B/E)).
To conclude the proof of Theorem 1.1, run Algorithm 1 with error parameter e' S 7B We note that we can generalize our result to obtain an algorithm for computing Attention when the input matrices have low rank. We defer the proof to Appendix A.3.

---

Published as a conference paper at ICLR 2026
Algorithm 1 ApproxAAttention(...
Input
:Matrices Q, K, V E [-B, B)".
: parameter E
Output
:Matrix Ô satisfying
Ö Attention k 0) S TeB.
Compute (8) for all E [nx] using Theorem 3.1
Compute <(Qi) < Smax log(1 + log(n/s) for all E [m]
Compute a g-degree polynomial (x)) for range [0, 2 log(n/2 (n/E) using Lemma 3.3 Initialize the data structure for queries @r f...... .a) for all 0 s t S d using Lemma 3.5
Compute Oz for all (i, () E [n] [d] using queries to Lemma 3.5
return Ô
Theorem 1.2. Letr = There an Ô (nd + n2-1/r polylog(B/e)) time algorithm comput- ing AttC(n, d, B, where min(rank ran)
CONCLUSION
We conclude with some open questions. The most natural question is settling the complexity of Max-IP when < < 20 n), We have shown several conditional lower bounds for Attention computation. Is Attention fine- mneeggained equivalent to any well-studied problem? If such relationship can be established, then breakthroughs on well-studied problems fine-grained complexity can lead to breakthroughs on Attention computation. While this work focuses on characterizing the complexity of training a single Attention unit, the complexity of computing a full transformer remains open: perhaps the cost of computing many Attention units less than computing each of them separately.
ACKNOWLEDGMENTS
The authors would like to thank Josh Alman for helpful discussions and pointing us the Fast Multipole Method. The authors are grateful to anonymous reviewers for their valuable feedback and helpful suggestions. BS, YX, and CY were supported by NSF HDR TRIPODS Phase grant 2217058 (EnCORE Institute). CY was supported by NSF grants 1652303, 1909046, 2112533 This work was done while SG and BH were at UCSD.
REFERENCES
Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium Discrete Algorithmms, SODA. SIAM, 2015a.
Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More applications of the polynomial method algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 218-230. SIAM, 2015b.
Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete and Computational Geometry, 6:407-422 1991.
Atish Agarwala, Samuel Stern Schoenholz, Jeffrey Pennington, and Yann N. Dauphin. Temperature check: theory and practice for training models with softmax-cross-entrooy losses. Trans. Mach. Learn. Res., 2023, 2023.
Amol Aggarwal and Josh Alman. Optimal-degree polynomial approximations for exponentials and gaussian kernel density estimation. In 37th Computational Complexity Conference (CCC), 2022.
Josh Alman and Yunfeng Guan. Finer sreer-gaannd hardness of kernel density estimation. In Rahul Santhanam (ed.), 39th Computational Complexity Conference, 2024.
10

---

Published as a conference paper at ICLR 2026
Josh Alman and Zhao Song. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. arXiv preprint arXiv:2310.04064 2023.
Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings of the 37th International Conference on Neural Information Processing Systems. Curran Associates Inc., 2024a.
Josh Alman and Zhao Song. The fine-grained complexity of gradient computation for training large language models. arXiv preprint arXiv:2402.0447 2024b.
Josh Alman and Zhao Song. Fast rope attention: Combining the polynomial method and fast fourier transform. arXiv preprint arXiv:2505. 2025a.
Josh Alman and Zhao Song. Only large weights (and not skip connections) can prevent the perils of rank collapse. arXiv preprint arXiv:2505.16284, 2025b.
Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In The Thirleenth International Conference on Learning Reprexentations, 2025.
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2005-2039. SIAM, 2025.
Arturs Backurs and Piotr Indyk. Edit distance cammot be computed in strongly subquadratic time (unless SETH is false). SIAM J. (7()):44837111100000 2018.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint 20xvv22004.051500 2020.
Jan van den Brand, Zhao Song, and Tianyi Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. arXiv preprint arXiv:2304.022077 2023.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Neural Information Processing Systems, NeurlPS, 2020.
Timothy M. Chan and Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolenske In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1246-1255. SIAM, 2016.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention. In Neural Information Processing Systems, NeurIPS, 2021.
Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In Proceedings of the 33rd Computational Complexity Conference (CCC), 2018.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, ICML, volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, 2020.
Xiangyu Chen, Qinghao Hu, Kaidong Li, Cuncong Zhong, and Guanghui Wang. Accumulated trivial attention matters in vision transformers small datasets. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pp. 3994-3992, 2023.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.

---

Published as a conference paper at ICLR 2026
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser. David Ben- jamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, ICLR, 2021.
Mina Dalirrooyfard and Jenny Kaufmann. Approximation algorithms for min-distance problems in dags. In 48th International Colloquium on Automala, Languages, and Programming ICALP, 2021.
Giannis Daras, Nikita Kitaev, Augustus Odena, and Alexandros G Dimakis. Smyrf-efficient attention using asymmetric clustering. Advances in Neural Information Processing Systems, 33:6476-6489, 2020.
Samet Demir and Zafer Dogan. Optimal attention temperature enhances in-context learning under distribution shift. arXiv preprint 1.00222511000292 2025.
Philipp Dufter, Martin Schmitt, and Hinrich Schüitze Increasing learning efficiency of self-attention networks through direct position interactions, learnable temperature, and convoluted attention. In Proceedings of the 28th international conference computational linguistics, pp. (630-3636, 2020.
Yeqi Gao, Zhao Song, Weixin Wang, and Junze Yin. A fast optimization view: Reformulating single layer attention in Ilm based tensor and svm trick, and solving it in matrix multiplication time. arXiv preprint arXiv:239.074//8 2023a.
Yeqi Gao, Zhao Song, Xin Yang, and Ruizhe Zhang. Fast quantum algorithm for attention computa- tion. arXiv preprini arXiv:2307.08045 2023b.
Yeqi Gao, Zhao Song, Xin Yang, and Yufa Zhou. Differentially private attention computation. arXiv preprint arXiv:2305. 04701, 2023c.
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandich. Hyperattention: Long-context attention in hear-linear time. The Twelfth International Conference on Learning Representations, 2024.
John Hopcroft and Ravi Kannan. Singular value decomposition (svd). https::tp/// //ww...//www/////// cs cm.. sduu/vvnkatee www.eekettttttcchg/n////////// 2024-12-21.
htw.:///eooooooooooooooooooooaao whwpeechaape-reeeeeee w.p.eerr............... Accessed:
Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). Advances in Neural Information Processing Systems, 37:31562-33 31628, 2024.
Jerry Yao-Chiel Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (Iora) fine-tuning for transformer models. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy, 2025.
Qianjiang Hu, Xiao Wang, Wei Hu, and Guo-Jun Qi. Adeo: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR. pp. 1073-1083. Computer Vision Foundation / IEEE, 2021.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001.
Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketching polynomial kernels. In Forty-first International Conference Machine Learning, 2024.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mnns: Fast autoregressive transformers with linear attention. International conference on machine learning, pp. 5156-5165. PMLR, 2020.
Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. On computational limits and provably efficient criteria visual autoregressive models: A fine-grained complexity analysis. arXiv preprint AxXv:250/0043777 2025.
12

---

Published as a conference paper at ICLR 2026
Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In International Conference on Algorithmic Learning Theory, pp- 597-619. PMLR, 2023.
Bulat Khaertdinov, Stylianos Asteriadis, and Esam Ghaleb. Dynamic temperature scaling in con- trastive self-supervised learning for sensor-based human activity recognition. IEFE Trans. Biom. Behav. Identity Sci., 4(4):498-507, 2022.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, ICLR, 2020.
Anna Kukleva, Moritz Böhle, Bernt Schiele, Hilde Kuehne, and Christian Rupprecht. Temperature schedules for self-supervised contrastive methods on long-tai tail data. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
Scung Hoon Lee, Seunghyun Lee, and Byung Cheol Song, Vision transformer for small-size datasets. arXiv preprint 11. 2021.
Junyang Lin, Xu Sun, Xuancheng Ren, Muyu Li, and Qi Su. Learning when to concentrate or divert attention: Self-adaptive attention temperature for neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2985-2990, 2018.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-53075, 2023.
Siladittya Manna, Soumitri Chattopadhyay, Rakesh Dey, Saumik Bhattacharya, and Umapada Pal. Dystress: Dynamically scaled temperature in self-supervised contrastive learning. CoRR, abs/2308.01 0400, 2023.
Jiří Matoušek. Efficient partition trees. Discrete and Computational Geometry, 8(1):315- 3344,,444 1992.
Abhishek Panigrahi, Sadhika Malladi, Mengzhou Xia, and Sanjeev Arora. Trainable transformer in transformer. In Fortieth International Conference on Machine Learning (ICML), 2023.
Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yam: Efficient context window extension of large language models. arXiv preprint arXiv:2309.0000 2023.
Joshua Robinson, Li Sun, Ke Yu, Kayhan Batmanghelich, Stefanie Jegelka, and Suvrit Sra. Can contrastive learning avoid shortcut solutions? In Advances in Neural Information Processing Systems NeurIPS 34, 2021.
Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (eds.), Symposium on Theory of Computing Conference, STOC. ACM, 2013.
Tim Roughgarden and Gregory Valiant. The singular value decomposition (svd) and low-rank matrix approximations. https:/ stanford. codd//classcs/// 68 /1////99... pdf. Accessed: 2024-12-21.
Barna Saha and Christopher Ye. I/O complexity of attention, or how optimal is FlashAttention? In Proceedings of the 41st International Conference on Muchine Learning, 2024.
Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Advances in Neural Information Processing Systems, 2023.
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vabab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In Advances in Neural Information Processing Systems, 2024a.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarith- mic depth. In Forty-first International Conference Machine Learning, ICMI., 2024b.
13

---

Published as a conference paper at ICLR 2026
Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pP- 605-615. IEEE Computer Society, 1999.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems NeurIPS, 2017.
Feng Wang and Huaping Liu. Understanding the behaviour of contrastive loss. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pp. 2495-2504. Computer Vision Foundation / IEEE, 2021.
Sinong Wang. Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04700 2020.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. Proceedings of the 37th International Conference on Machine Learning. ICML, volume 1 19 of Proceedings of Machine Learning Research, pp. 9929-9939, PMLR, 2020.
R. Ryan Williams. Faster all all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5),
2018.
Ryan Williams. A new algorithm for optimal constraint satisfaction and its implications. In Proceed- ings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung. Yin Li, and Vikas Singh. Nyströmformer: A nyström- algorithm for approximating self afff-attentinn In Proceedings of the AAAI conference artificial intelligence, volume 35, 2021.
Hao Xuan, Bokai Yang, and Xingyu Li. Exploring the impact of temperature scaling in softmax for classification and adversarial robustness. CoRR, abs/2502.20604, 2025.
Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. Siam Journal on Computing, 11(4):721-736, 1982.
Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher. Orr Fischer, Ran Amir Globerson. Depth-width tradeoffss in algorithmic reasoning of graph tasks with transformers. CoRR, abs/2503.01805, 2025.
and
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. Neural Information Processing Systems, NeurlPS, 2020.
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In International Conference on Machine Learning, pp. 40605-40623, PMLR, 2023.
Shengqiang Zhang. Xingxing Zhang, Hangbo Bao, and Furu Wei. Attention temperature matters in abstractive summarization distillation. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 127-141, 2022
Yixiong Zou, Ran Ma, Yuhua Li, and Ruixuan Li. Attention temperature matters in vit-based cross-domain fhw-shot learning. Advances in Neural Information Processing Systems, 17:326 116354, 2024.
Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3)2289-317, 2002.
14

---

Published as a conference paper at ICLR 2026
A OMITTED PROOFS FOR ALGORITHMS
A. WARM-UP: d=1
For simplicity, we begin with our algorithm for the d case and explain how to generalize the constant head dimension case later. Formally, we prove in this section the following result.
Lemma A.I. There is algorithm computing AttC(n, B,)) in Ö(n polylog(B/a) (B/e)) time.
In the above, Attention(g, k, v) is defined by viewing vectors q, k, E IRxx1 as matrices. When 1, the input given by vectors q. k v B, B) In the output vector, we hope to compute the entries
0, = Σ egcking
Σ egck;
for all i. Define the softmax probabilities
elikks
Pij
Eg Eakk
so that O; = E3 E, Pig
We begin with an overview of our algorithm. Without loss generality, we assume q, 2 are non-negative for all i. In particular, if we compute Attention(Ig), k. v) and Attention( -kl v). where !q) is a vector where we take entrywise absolute value of we can recover the entries of Attention[g- & v) from the two outputs. If 9; 2 O, we read the output from Attention (lg), (gl, k. and otherwise we read the output from Attention[[g). v).
Let kmax denote the maximum value of and pinxx max, Pi.j be the corresponding maximum probability for some fixed i. First, we argue that we may ignore all indices where k; < kmma-- Since all of these indices have exponentially small pi.j. ignoring these indices incurs only a small additive error to the output estimate o, Second, we argue that the remaining values of ky satisfy the property that q:yy lie small range. In particular, on this range, we use the low-degree polynomial P from Aggarwal & Alman (2022) to give low-error approximation of the exponential function. Using this polynomial approximation, we instead compute
P(ikk c)ug 0, E, c)
E, Eg E, encky -
E, Eeukio E, Encky
for some value that guarantees g:ki lies in bounded interval around 0 for the remaining values kj.
Consider monomial mas of P. Then -a(kk (2 This allows to pre-compute Σ, kt for all exponents b pre-processing phase, and then efficiently compute 6; using the pre-computed values. We now describe the algorithm in more detail.
Step 1: Removing Irrelevant Keys. We argue that ignore irrelevant keys ky (Definition 3.2) with only small additive error the estimate.
Since q: 0, by rearranging, note that for all irrelevant j. we have q;kk g:kmmax I - log(n/e). Then, we conclude
Pi.j (8) Piaxx
(.l kanax) E
Summing over all such indices j.
p(0) E < s.
P&.
irvelevant
irrelevant
Thus, we define
j is relevant,
Pij
Eecieaat of Pi.j'
0/v W
15

---

Published as a conference paper at ICLR 2026
can obtain the guarantees for all relevant j
(r)
Pi.j
Pij S Pij _
1
Then, define
(r) Σ
(r) Pi,j 2/
so that
(
Σ
w paj]us
Σ
w pi,)
relevant
irrelovant
Σ
PijUz
Pig
1
relevant
irrelevant
B + EB
1- B
where we assume 3
Step 2: Polynomial Approximation of Exponential. approximations of e to efficiently estimate attention.
We now show how we use polynomial
Our goal to approximate (*):
Erelevant encksuy
Erelevant cauky Erelevant , egihk -c(ac)
Evelevant enccy
relevant
where e(g:) = qi Aimax log(n/8). In particular, we have geky c(ai) E [0, log(n/s)) for every relevant
On this interval, by Lemma 3.3, there a polynomial of degree
log(1/s) g 0 max (gg(log(1/)//oo((n//) log(n/e) )) O (log(n/e))
such that IP(x)= cxp(z)) cxp(2x) for all lo,log(//E))- Then, define Pij P(ack, -c(g)) Erelevaat jr ( for relevant j and pr,j = otherwise. Next, define o; we prove the desired approximation guarantee. For all relevant j.
= E, Pu, First,
1-
1+ (r) I+E 2 S W T- Pij
so that
b,
0fr)
< B
Σ
Pij (r)
relevant
B
Σ
4spl2 4eB.
relevant j
Combined with our previous bound using triangle inequality, we get
||0 21loo < | - 1'' + +1|00 - of
TeB.
(I)
Now, we describe how to compute efficiently. Consider a monomial mex of P. Then,
melgik - c(g.)) = -me Σ
b di (-c(g:))
6=
16

---

Published as a conference paper at ICLR 2026
Summing over the indices j,
Σ
melg:ki
- -(qi))² me E Σ
(1)
(-c(q.))
relevant j
relevant j
m Σ
relevant j (1 of
(-c(a)))
b=U
Let ((i,b) = Erelvant j kg be the sum of K3 for all relevant with respect qr- In particular,
Σ
P(ack - c(qi)) = Σ
P(gskz c((:))
relevant
relevant j
Σ relevant
Σ
my (g: - -(4)))
Σ
of (-c(a:)) 6(i,b)
m
b
6=0
Following similar computations we obtain
Plask c(a)))
Σ me Σ d=0
di (-c(g))) o.(1,)
(2)
b
where (1, Evelevant Mg0
The following lemmas show that we can compute â efficiently. Lemma A.2. Let 2 1 and kn ho 2 ... 2 kin Let qı,... In arbitrary. Then, b), (1. can be computed for all in time O(n log n.) time.
Proof. Given b, we can compute Σ/=1 kÿ for all S S n in O(n) time. Then, for each we use binary search find J., the maximum index j where kj 2 max, ky - log(n/s)/g; i.e., ky is relevant with respect to g:- Then we assign o(i, b) = Σ/n kj. Over all i, this takes O log n) time. We can compute d, (i, b) similarly.
Algorithm 2 VectorAAtenntoong,, k, v)
Input
Vectors q, kt v [- B, B)".
Parameters :rrameters:Error parameter E
Vector satisfying ||ó Attention(q k; 1) &B, Compute a polynomial P(x)) = Σe mga² for range [0, (log(n/e)) using Lemma 3.3.
Output
Compute kmax f- max, k, and sort [
Compute dii, d., for all S S n, < b 6 using Lemma A.2.
for 1 S i do Compute 0;
Emalevant: -(c.)))c(4))) using Lemma A.3. Exelevau Plack;-((a))
1
12
return Ô
Lemma A.3. Let P(x) =
Ee mex be a degree g-polynomial with poly(g)-br -bit coefficients. Given qo, (li, b), Bu (i, b), there is an algorithm computing o; poly(g) time.
Proof. We recall that
E, P(ak, c(g:))u
0, Σ
Pi.u
E, Plack, c(qi))
From Equation (2), we note
(6) b
P(a c(a)),, Σ me Σ
of (- o((
b=0
17

---

Published as a conference paper at ICLR 2026
so that given access to (t, b), compute the numerator in poly(g)-time. Similarly, by accessing o(i, b), we can compute the denominator as well.
To conclude the proof of Lemma A.I. apply Algorithm 2 with e' A obtain approximation under Equation (I). particular, the degree of the polynomial required is
O (log(n/E')) = O (log(nB/E)).
Then, Algorithm takes time Ón polyloo polylog(B/s)).
A.2 CONSTANT HEAD DIMENSION
We provide the omitted proofs for Theorem 1.1.
Lemma 3.4. JÔ,, Oz,11 S TeB for all E [ri], I E [d].
This follows from identical arguments as to those in the one-dimensional warm-up.
Lemma 3.5. Given matrices Q, K, V K,V
Raxd there exist functions .o....da such that any entry Õu can computed with g g(d queries to do and Φt and g ( additional time.
Furthemorr, for each Or with < 1. E d there is data structure with Ô (gD(d) logn) preprocess- ing and O nn 1-1// log( B/e)) query time.
Proof. Recall that Õz,6 Eeelevant KKQ..K, obtained from Lemma 3.3.
Eretevant P(Q:-K)-((Q.) where P is the polynomial of degree
We begin with describing how compute the numerator of Ö.,.. Suppose P(x) Ei mpx*
Σ
P(Q. K2 - VQ{
relevant/
Σ
mm K2- - V(Qi))
relevant
Σ m Σ
Σ
II (unKg,)) Vis
relevant j Ea that
( C totttto (eorer....,
) (-c(2.))
Σ mf
Σ
t Σ
II V3,
relevant
Σ me
tottetttttst Ca, Caslis...,.e ,aa) (o..,Re(- (-c(Q.))
Σ EL
II
k=1
where we define the function beli,ti,... (.. Erolevant M function
3.b Vy. Similarly, define the
doli,e1...... (a) (a)=
Σ II
K
relevant j
so that
Σ P(Q. K, - c(Qi))
Σ m
Σ (6o.ii..,,,
c)d-)))))
II
o (i....
tottt
The following lemma describes how build the appropriate data structures.
18

---

Published as a conference paper at ICLR 2026
Lemma A.A. Let fi...., Eg be nonnegative integers. Ler < t d. Given matrices Q, K, V, there a data structure with O(nd+ + n logn) preprocessing time that answers queries di(i, l....., ,.....,,)) Ed) in δ (n 1/d 1ogg////o/// log(dB/e)) time.
Proof. We initialize two RSDS data structures using Theorem 3.1, one with unweighted point set {Kj} and one with weighted point set { {KK, IT= Ky V. } By Theorem 3.1, this requires
j=1
(n log preprocessing. Computing each weight requires ((d) time.
Now, consider query (i, ....., fa) for some i E [n]]. We compute s using binary search with the first RSDS data structure. Since Q2: K5} Σ dB² there are at most O + E)) values to search through. This requires O(log(dB/e) queries which requires Ô (n (n log /E)) overall time by Theorem 3.1. The set of j relevant to Q, is the set of Kj such that Q; K2 Z
smax log(1 + =) log(n/e). This can easily be captured by simplex query with the half-space
(8) Q 2 Smax log(1 + +) - log(n/s) and thus requires one query to the second RSDS instance. C
Our data structure for Lemma 3.5 is simply the combination of all data structures that answer queries (i, f,,...,e)) (2). Since P is degree and { + f2 +.... Es S f S g. there are at most (g + d)o(d) go(d) distinct tuples f,..... la since d is a constant. In particular, we can initialize all the necessary data structures to compute queries of de in Ô (g)0 (nd log n)) time.
We now show to compute an entry of Ó Note that numerator sums over L, tuples lo, , La of which there are at most g ((d) summands. Each summand can be computed with one query to Φe and go(d) additional time. Since the denominator can be computed similarly (instead querying Φo) the total time to compute Ö is Ô n log(dB/s)).
Lemma 3.6. ApproxAttention (Algorithm 1) runs in time Ô (n²-1/d polylog(B/oo) (B))).
Proof. We now analyze the running time. From Lemma 3.3, we have
log(1/E)
g 0 max log(log(1/E) (og////))))/()) log(n/e)) O(log(n/e)).
Then, initialize all the necessary data structures, invoke Lemma 3.5 total of + 1 times, thus requiring preprocessing time (recall d is constant)
Ô (n polylog(1/E))
Then, computing all Ôz, requires time
Ô (ng ((d) (n' log(B/s))) 2 (n2-1/a -0
polylog(B/e))
A.3 GENERALIZATION TO Low RANK MATRICES
To prove Theorem 1.2, we require the following standard result on computing a representation of low-rank matrices.
Lemma A.S (e.g., Hopcroft& & Kannan; Roughgarden & Valiant). Let A be a d matrix of rank with entries in [-B, B, B). Then, there is an (ndrr) time algorithm computing an n X r matrix A and d X matrix VA such that A = UAV Furthermore, U. VA have entries bounded by poly (Bny).
Suppose we are given n x d input matrices Q, K of rank TO, Tk respectively. Then, we apply Lemma A.5 to compute U2, Vo, UK, VK in time O(nd max(rq, rK)) = O(nd). Suppose without loss of generality rq < TK. Then, we compute
Q' UQ KJT UUVV
in time O(rornn) O(n) and note that Q', K' have entries bounded by poly(Bnd)..
19

---

Published as a conference paper at ICLR 2026
We then apply Theorem 1.1 to approximate Attention(Q' K" V) Attention(Q K, V) which is an instance of (n, min(rq. rK), poly(Bnd), which requires time
Ô 2 min(rq.rx) polylog(B/E))
to compute an output Ô such that | Altention(Q, V) Theorem 1.2.
S.. This completes the proof of
B THE COMPLEXITY OF ATTENTION GRADIENT COMPUTATION
In this section, we leverage our algorithm for approximate attention computation obtain the corresooniigg upper bounds for approximate attention gradient computation. We begin by formalizing the notion of attention optimization:
Definition B.1 (Attention Optimization). Given input matrices AI, A2, Ag, E E Raxd and Y gdxd find matrix X E Raddd that minimizes the objective:
L(X) | AV -E EE
where :: exp(AA A3Y, and D(X) == diag(A1,)) R2x
The gradient of the objective function L(X) with respect to X is then used to optimize the atten- tion mechanism by iteratively adjusting X minimize L(X). Formally, we define the following approximate version of the gradient computation problem for attention optimization:
Definition B.2 (Approximate Gradient Computation for Attention Optimization AAttLGC(n, d, E)),
Given A,, A2, As, E [-B, B]xxd E B] such that
dxd and > compute matrix g E Rdxd
( dx
Se.
B.1 NOTATION
Throughout this section we use the following notation. We overload the diag operator. In this section, the diag operator indicates turning all the non-diagonal entries to zero. The operator indicates entry-wise multiplication. The @ operator denotes the Kronecker product, defined by
[ 1)n + ( 1)d k] X jl Y| where X,Y Raxd and Z p The &r operator denotes row-wise Kronecker product, as defined by Zii, (i - 1)d + k) = [(r Y k] where X, Y E R and Z E Rax We use e(t.)) shorthand to denote e '02, where a and 02 are rows of A and A₂ respectively. If is a matrix, we use M, to denote the i-th row of M, Ma, to denote the i-th column of M. We use M[i][j] to denote the (i, j)-th entry of M (since our matrices have subscripts, the previous notation M.,j is confusing).
B.2 UPPER BOUND ON ATTENTION BACKWARD COMPUTATION
We show that the backwards pass for approximate attention can be computed in time Ô (n2-1/d, polylog(B/oo) (B/e)) when d 0(1).
Theorem B.1 (Formal Theorem 1.3). AAttL d, B,e) is reducible O(d) calls to AAttC(n, d, B, B(ndns)) using ((nd)) time.
Corollary B.2. Let d = 0().. There exists an algorithm that computes AAttLGC(m, d, B,e) in time Ô (n² 1/d polylog(B/E))
Proof of Corollary B.2. This follows directly from Theorem B.1 and Theorem 1.1.
10 Alman & Song (2024b) scale the Attention matrix A by d for training efficiency, becoming =
exp A1xA]] Since algorithms scale polylogarithmicaly with entry size, safely ignore this scaling term.
20

---

Published as a conference paper at ICLR 2026
Proof of Theorem B.I. We begin by recalling the following definitions from Alman & Song (2024b), which we will use to define the gradient computation formula.
Definition B.3. Let AI, A2 E Ru be two matrices and let A = A @ A2 E xR"xxd" Let æ E Rd be the vectorization of the matrix X E Raxd in Definition B.I. We define Ajo E Raxd to be the n x d' size sub-block of A consisting of rows {(o - 1)m + ji jibj Let (x) be the n x n matrix whose jo-th row, denoted (xx) is given by:
f(=);0 = ((exp(Ajoz) nxl
exp (x)())))))
nx1
Note that f(x) = ( (iag(exp(A A 1m)) Therefore f( where Z is an n matrix, is evaluated by Attention(AI, X2)
Definition B.4. Let Y E RRdxd denote the matrix representation of y R and Yo,io indicate the th column of Y. h(y) Raxd is defined the matrix whose in-th column is h(y)in which is defined as follows:
h(y)s
As Yo.0
axd dx1
Note that throughout this section, we occasionally use as a shorthand for hty) is clear that h(y) can be computed in (nu d, d) time.
Definition B.5. Let c(x) be an n x d matrix defined as follows:
c(x)
f(x) h(y) E
nxd
nxn
axd
axd
We can approximate c(y) by evaluating Attention(A:,X, A2, h(y)) to get f(x)h(y), then subtracting E which takes (nd)) time.
From Alman & Song (2024b) we have the following formula for attention gradient computation:
aL(x) AT [f(x) o [f())) - (M)))) A f(x) (iag(f())((())(()) T (Eh(y) ]] )]A2
dx
[f()) (f(#)M())h())) []422 - A [f(x) (Eh())
-AT (lag)/(()((())(()))))))
The first line comes from the characterization the gradient as dl(x)
dz A p(x) A2 where p(x) = (xx) p2 (z) (see Appendix D.4-D.6 of Alman & Song (2024b)), In the notation of Alman & Song (2024b), the first term corresponds to Pı (z) := f(z) o ((x) := f(x) o (c(z)h(y))) The second term corresponds to P2(x) which is
matrix whose Jo-th column is f
[()), (x)))(() Note that pa (2)) = f(x) (x){([())((()) = f(x) diag [[agg/((x)) diagg/()))(x))MM)) T..
Note that q(x) = c()) is notation in Alman & Song (2024b) which we do not use here.
Let us denote
B (f(x) ((()))())M()) T)
B₃ = [f(x) o (E)h(y) A4,
B3 == f(x) diaglf (r)((r)(()) "AA
We now have the following formula which can clearly be computed in O(nd) time if given B1, B2. and B3:
dL(x) ④
B ABBAABAA
dr
dxn nxd dxn nxd
dxn axd
Note that for each attention computation we perform in order to evaluate the attention gradient, we do with E2 poly(d,B)m additive enror.
21

---

Published as a conference paper at ICLR 2026
approximate B3 using series of matrix multiplications and attention computations, which are illustrated below in the following equations. C denotes the intermediate matrix products from each of these matrix multiplicattions/atteniiii computations. We compute an approximation of B3 as follows:
Computing By. Given f(x), c(z), and h(y),
B3 = f(x) diag (fag)(())))) [ o()) h(y) AA2
nxn axd
[() diag C. h A2 nxd
-f() C2 A2
=f(x) C2
We begin by computing C1 f())c(x) by evaluating Attention(A1 A2, c(z)). Next, we compute
C2 diag] (y))()) J, which consists of the diagonal of the matrix product Cih(y) Since we only need the diagonal entries, this step takes O(nd²) time. We then compute C3 = C2A2. As C2 is diagonal matrix, this matrix multiplication can be performed in ((nd) time. Finally, we compute By f( by evaluating Attention( (A, A2,
We argue that our computed output is good approximation of B3. Let B3 denote the computed matrix. For any matrix Z, Z indicates approximation of Z derived by step in our algorithm. Then,
|| BB B3
< [(x)C3 AHtC(A,X, A2, C3)
- [(1)Cs ((x))ss
+62
$ Cs - C5. +
diag ']A diag T |
+
diag (1)(()) 7 diag C1 7] A2
+
- |
diag(Cih(u) diag Cih(y)
+
< ||
Cih(y) -(ih())-(ihh())))
+
& d2l
[M(v)]l C - T
+
S d d||42|l
~0 [1(0) [(x))(()) AttC(A, A2, c(x))
+
A2
|n(0) (E2 [(=))(x) (f f(x)((x)) ) +
S d A2|l | (52 +
((()) c(x) +
< 2dB + +
Above, step follows from how our algorithm approximates B3, step 2 follows from our eg-error approximation of attention and the triangle inequality, step 3 follows from the fact that f(x) is stochastic matrix and distributivity of matrix multiplication, step 4 follows from our definition of Cs. step 5 follows from the distributivity of matrix multiplication, and step 6 follows from basic properties of the oc-norm and diagonal matrices. Step 7 follows from the fact that the diag operator simply zeroes out the off-diagonal entries, making the off off-diagonal elements of Czh(y) T and Cjh(y) identical. Step 8 follows from basic properties of the co-norm, step follows from how algorithm approximates C₁ step 10 follows from the triangle inequality and our Eg approximation of attention, step 11 follows from similar arguments as steps 9 and 10, and step 12 follows from entry bounds.
22

---

Published as a conference paper at ICLR 2026
Computing B1. We now show how to compute B1. We begin by noting that B1 (f())(((())))) 3r A2)) & (f(z)h(y))+ fact we will prove later. Using this fact, can compute B, efficiently, as illustrated in the following:
B1 =
Σ (f())( @r A2)) or (f(z)h()))..
P=
=
Σ
(f(x) 8r A2)
8r Co..
1=
ax1
nxd
Σ (f(x)) Ca.
Br Cs...
nxd
CT.P Cs..pp nx1
Cs.p
We begin by approximating C3 f(x)h(y) by evaluating Attention(A, X, A2, h(y)). Next, for each S p S d, we compute the matrix Co.p = h(y)),p 3r A2. Each matrix requires (nd) time to compute, constructing all matrices incurs a total cost of O
We then compute each matrix C7 C( by evaluating p E [d]. Computing the row-wise Kronecker products Cs.p C7 0r Cs..p takes O(nd) time for each p E [d]. totaling O Finally, summing over all Cs.p requires an additional O(nd²) time.
(, A2, Cs.p) across all
We argue that our algorithm returns a close approximation of B1. Let B1 indicate our computation of Bi. For any matrix 2, Z indicates an approximation of Z derived by step in our algorithm.
d
d
B1 B
Σ
Csp
Σ
Cs.p p=0
p=0
d max
| Ca.P
P
< d max
{1
|T.p Er Co.p
Crp 8r Cs.,p 1100
p
s d max
1|0TT - -CTpp
Oo.r - -Conp
|r,0 -Or.p 11an,plloo
+ -|1o,r -Comp 11 || |1Cr,pllo0]
dmax [IAtIC(A, Ag, C6.p) - ( | A2, Complloo
+ ||AUC(AIX, A2, Co,p) (x)) ICCs,
+ +||AttC(AIX, As, ((,h((y))))))))))) Cs |CT,pllac)
< dmax {e2 82 [1f (1 ppl) + 82 (=l)(()) &r A2)l
P
S d dmx
{c2 E2 (M(() + (/1)).p Er Az A
p
S dmax {0 + E2 [1(()))) + c2 (1 ||
S dd (5) B2 b² dež d de,
Step 1 follows from our definition of Cs step follows from the triangle inequality, and step follows from how define Cs.p- Step 4 follows from analyzing the entry-wise error in the row-wise
23

---

Published as a conference paper at ICLR 2026
Kronecker product. Let C7 Ct.p b Cs.,, and let e1 and e2 denote the entry-wist approximation errors in (7.p|][]] and C. Co.,ptl. respectively. Then the approximated entry is z= (C,pp 3r Cs [ (a + eb) + e2) ab + be1 + ae2 + c162. Therefore, the entry-wise error in the approximation is č = bel + u62 + e1e2, where (c = Cr.p 8r Cb., [ilbi.
Step 5 follows from how our algorithm approximates Ct.p and Cs.,,- Step follows from the fact
that C. Cs and eg approximation of the attention computation. Step 7 follows from the fact that f(x) is a stochastic matrix, step is based on the lincarity of the Kronecker product, and step follows from entry bounds.
We defined B1 := (x) (f())(y))())) 12. We now show We begin by noting that the format and 1 s d:
of each entry of B1 is follows, where i
e
1
elhmm
B1 B1 k=
Σ
Σ p=
he, Meepp/mmmp)) vl
A2le,1]
((t,A)
k= eli,))
e(t,e)
((tm)
k= els,yy hlm, pl
hle, pl22,.12
e(i,k)
t=
k=
We now compute the sum Epno Cs.p and verify that
Σ Cs.p [i.s] B2li.5].
Let C. = f(z)h(y). For 1 sisn n and S p S d. we have:
(t.m)
Coli.pl = Σ
K== e(i,k)
m=0
Let Co.p h(y)r,p 3r Ag. For S 2 n and 1 S S d. this gives:
Co.pl..l My)]i. A2l
We define = = Co
eli
Cr,pii, = Σ
K=n ela, h(y) [A]
8=0
Let Cs.p OT. &r Cs.,p- Then for 1sisn, n. Iiid:
eli
elim)
Csplits1 =
M()bi,
Σ
(w)(m,
k= c(i
k= cli,)
m=u
ell,e)
(bim)
h(y)mm, pl h(y)(e.p) A2l4.
k=o c(iM)
En cliny
Summing over all p. recover:
d BBli.j] = Σ Cs.
D=0
Computing B2. We begin by noting that B2 = Σd (l)_)l((())))))))))))))))))))))) 8 A2)l 8r E.,,, a fact that we will prove later on. Using this fact, we use the following procedure to compute an approximation of Bz:
24

---

Published as a conference paper at ICLR 2026
B2
Σif(a (M()) 8r A2 A2 10 E..
p=0
axd
(1x) Co.pl 00 E....
axd
Σ Cro. 1r Exp
p=U axd nxl
d
Σ Cup p=U axd
We start by approximating the set of d matrices, Cy. = h(v)+pp 3r Ag. For each 1 S p $ d. computing Co takes ((nd) time, so this takes ( time in total. We approximate each Cl0.p = Co) by evaluating Attention(A,X,, A2, C- Next, we compute all ClI.p Cio.p 8, E...p which takes O(n?²) time in total. Finally, summing over Cl1.p takes O(nd²) time.
We now analyze the error from approximating B2 using the method we just described. For any matrix z, Z indicates an approximation of Z derived by a step in our algorithm.
d
B2 B2
CLI.
p=0
p=0
{ C -up
s dax P
d max
Clou Er Exp Clo,p 8r Exp
P
d max p
|11.00 -ionn 8r Ea.pl }
-C0.o)-Croon)
{ ||
BaallllIcoooo [1000- G1o.p
< d max p
dax
Eo [lf( 0r A2) - Att((A1X, My)) 0r A2)
p
s dmax
fcz }
< BegB.
Above, step 1 follows from our definition of Ct.,p step 2 is follows from the triangle inequality, and step 3 follows from our definition of CII.p. Step 4 follows from the linearity of the row-wise Kronecker product and step 5 follows from the fact that the row-wise Kronecker product scales every element in C by element in E..p- Step 6 follows from how approximate Coo,p in our algorithm, step 7 follows from our e2-error approximation of attention, and step 8 follows from our defined entry bounds.
We defined Bg = [f(x) o (E))()) A))2 Finally, show that Bg ES (<) or
A2)] 8r Eng, which can be proven by showing that B2[i, Σp C1n,p for all sisn and < d. We note the following:
(1.0)
B2[i, =
Σ Eli plM(e, pl
A2le.j]
c(G,k)
E=0
d
elfie)
A2
n
= c(i,k)
p=
1=
25

---

Published as a conference paper at ICLR 2026
and it is clear that the following is true:
eli, Σ k= eliyy M6
Ci.pli-))=
Σ E=
Bounding Approximation Error. Now all that left to show our procedure gives us an approximation of the gradient with e additive error. Recall that we did all the attention calculations with #2 By) additive error. Let dL(æ) dz denote the matrix our procedure returns and let c(x) be the approximation of o(x) given by Attention(A X, A2, h(v))-
dl(x) dr
dL(x)
d A B2 AJ ABB (4 Σ Cs.p A
d Σ pm
A Bi
Cn. A M
dr
n=
d
d
A
(B]
Σ
Cs.p) + +B2 Σ
C11p) + (Bs f(z)C3))
P=0
P=U
Sn |
(B)
Cs.p) + +B2
Σ
Cn. + - (B3-
p=
p=0
< n ||A]
Bi Σ
Cs.p
+ B2
Σ CII
- f(r)-
p=0
p=0
S (dE + d + de + d
(2dB² E2 + E2))
= O(ndB =.
Above, steps and 2 follow from definitions and rearranging terms, step 3 follows from basic properties of the co-ormm step 4 follows from the triangle inequality, and step 5 was justified previously.
C NEW LOWER BOUNDS FOR ATTENTION
In this section, we prove Theorem 1.4 which shows Attention hard even with d = 29(log" n) and Theorem 1.5 which shows that the standard algorithm is optimal for d = poly(n). We begin with generic self-reduction (Lemma C.I) that shows it suffices to prove lower bounds for Attention without normalization. We also prove Theorem C.7 which shows that Atlention is hard for d ((log n) even for constant entry size.
Recall that in the attention computation Attention K, V) D-IAV, the diagonal matrix D-1 applies a normalization to each row of A. In our reductions, however, it is necessary to work directly with the unnormalized entries of As a key lemma, we show that given oracle access to AttC with eaadiitive error approximation, one can approximately recover the row sums of A up to O(e)- multiplicative errors, hence recovering the unnormalized entries of A. Specifically, if S; is the actual row sum of the i-th row of A, then the reduction computes an approximation S, such that
S - St < (s)SS,
turns out that multiplicative error approximation on the row sums sufficient for our lower bound proofs.
Lemma C.I. Let < =0000==000 O().. Given matrices E Blaxd with B 2 1, we can estimate the row sums of A = exp(QK) up -())iilliil error in time
O(llg log n + Log(dB//))) T + 1,d d B,B,)))
Proof. We use a parallel binary search approach to estimate the row sums. In order to implement parallel binary search, it suffices to perform the following task T:
26

---

Published as a conference paper at ICLR 2026
Given array of numbers [c1..... ........ Col T output an array b {0, such that if S; 2 (1+E)c, then b, 1: if S, & (1 e)c, then 6; 0. Otherwise, b, can be arbitrary.
Indeed, at each round we let c := (1 + e)--1 for some fi- We the indicator = 1 to perform binary search for the smallest fi such that (1 (1+ 2 S; for all Such an fi gives the guarantee that S S (1 + e).h < (1 E),,, which is e-multiplicative approximation of S,- Note that the value of each row sum S; belongs to the range In (xp(-BBd)) n cxp(B²d)) so we just need to binary search Therefore, the number of rounds
for the correct E [log1+>(M) exp(-B==d logi+e (n
for binary search (i.e., for performing the task 7) is given by
(logg logi 45 (n exxx d)) Ollo log + log(dB/e)).
It now remains to show how to perform the task T. We claim the following:
Claim C.2. The task T can be completed with one oracle call to AttC(n + 1,d + e, and ((nd) additional time.
Proof. We create the following matrices as inputs to the oracle AttC(n + 1,, + 1, B,e):
0 0
0
Q' = In c
Q K' 0
0
V
0n
K
0
0
Then,
Ine Q'K
QK
0
0_
so the (i, 1)-th entry of Attention(Q?"
(Q', V*) D'-1''''" would be
S 9. C; 5
Assume we have an (e/100)-additiv) approximation of o; (denoted by ō:). Then, we set b, if 6; 2 and b, = 0 otherwise. We now show that all entries of b are correctly set. If 2 (1+ then
S 4: + S
1+ e/100
1 2
0; 2 0; E/100 2
e/100 2
2 2
On the other hand, if S, S (1 11=5ja E)c;, then
S
1 1
1
0, S 0; + 8/100 <
+ e/1000 <
2 e/100 <
C S
2
In the first inequality, we use algorithm will output b; 1 in the former case and b; the latter case, as desired.
1+s > 1 + f and in the second we use 1- < - 6. 242
Thus, the
This completes the proof of Lemma C.I.
C.I LOWER BOUND FOR ATTENTION WITH SMALL HEAD DIMENSION
In this section, we show via reduction from the Max-IP problem that AttC(n, d, B,s) requires ?-1)(1) time when d = 2000""" n), B (n)y(n), and = O(1) additive approximation error. In particular, we note that we are able compute Max-IP exactly even with oracle access to AttC that allows & O(1) additive error.
Lemma C.3. Let > O. Max-IP(n, d, B) can be computed exactly in time
O(log log n 1
27

---

Published as a conference paper at ICLR 2026
Proof. Given 8, choose C C()) and set d 2C Let A {ai.... ...... an [bi..... bn} S Zd be two sets of d-dimensional integer-valued vectors with entries bounded by
B2 Let In n and we choose the smallest integer C > 0 such that
0.5C > 1 log. (1 + and 0.5C < logn (1 - =)).
Define the following matrices Q, K Raxd;
a
b
02
T
02
Q
=
K = KC
(3)
an
bn
By Lemma C.I, we get the (1 + + e)multippicative appooxattionss of the row sums of exp(Q in time
O(log log n + Here, note that kCB = O logn), n). Note that the i-th row sum is given by
+ 1, k,b,))))) =)).
5 kC(apb)) = Σ (lax))))
Let S be the (1 + multiplilieee approximation for S, and let Mj := max, a, by (note that all inner products are integers) be the maximum inner product over all vectors in B for a fixed aj A. We claim that Mj can be recovered exactly by
M, logn S + 0.5
Note that each non-maximum term on a single row can be bounded by 0 < (larb)) & n CM, so we bound the sum by
CM. S. S n CM.. n CM,+1
Thus, applying (1 + approxxmaaii to the upper and lower bounds respectively we get
(1- CM, < S < (1 (1+ s3n CM,+1
we can show M, S (log,, S1)/C + 0.5 < M, + 1 then we are done. Indeed, using our definition for C' we get
log, S
CM; + 1 + log, (1 +
+ 0.5 = A,5==,++ 1 log, &1+
0.5
+0.5 < M, +
C
C
C
and
log, S
CM, log, 8)
log, (1-E)
+ +.5
+ 0.5 M, +
+ 0.5 M,.
C
Combining the above reduction with the conditional lower bound for Max-IP (Theorem 2.3), obtain Theorem 1.4.
Theorem C.4 (Formal Theorem 1.4). Fix e = O(1) and B poly(n). For all 8 > there exists C C(ő) and d 20 log" a such that any algorithm computing AttC(n, d, B, requires n2-5 time under SETH.
C.2 LOWER BOUND FOR ATTENTION WITH LARGE HEAD DIMENSTON
In this section, we study the case of large head dimension where = (n)y Through a reduction from the OV problem, show that computing AAttC(n, d, B, requires explicitly computing the matrix product QK when d (n)y( B O (Vlogn), and O(1) (additive approximation error). Furthermore, we establish similar lower bound from the OV problem when d = poly(n).
B = 0(1, and s = O poly(m))
28

---

Published as a conference paper at ICLR 2026
Theorem C.5 (Formal Theorem 1.5). Fix d poly(n). There exists B OOvlog and = (())
such that any algorithm computing AttC(n, d, B, requires TuuL (n, d, 1n)--(01) time under the Generalized High-Dimensions Di-eemsiiinnl OV Hypothesis.
We show the following lemma prove Theorem C.5. Lemma C.6. The OV problem can be computed exactly with one call to AttC(n, d, B O(ylogn); & = = (()) and ((nd) additional time.
an). (bi...., b.) S 10. be two sets of vectors. We chose Proof. Let A ...,,........................... . constant such that & < c and a constant such that I-c We then define Q, K E Ra
m[1+e]
02
62
Q = -
K = Vl
(4)
b
Due to Lemma C.I, we can recover the row sums of exp(QKT) up to e-multiplicative error in O (loglogg log + log(dB/=)) +1, E)) time. Let S be the (1 approximmaion of the i-th row sum.
S =
Ju(k)aapb)) = = (1
h
Larby
j=l
j=l
which implies
a (1 - karb S, S (1 +
n
karb
j=1
there are no orthogonal pairs vectors in and B, then ag by positive integer for all
1 S i,j < n. Consequently, because < the maximum value of kar is k. From this follows that if there are pairs of orthogonal vectors, all of the sums S,...., Sn will be less than 1-c c:
e1+ - c) (1 c)+c)
(1 ()+ - (1 +c)
S: (1++) Σ fards < (1 e)nk e)nnk <
On the other hand, when there are one or more pairs of orthogonal vectors in A and B, there will be least k., by and a row sum S, will exist such that S:
c:
8, 2 (1
Σ barby (1 c)1 c.
By checking for the existence of a row sum St that greater than or equal to - c we can determine whether there is pair of orthogonal vectors in A and B.
We also show that when d = (log n). Attention is hard under SETH even with constant entry size B.
Theorem C.7. For all 5 0, there exists C. C(8), d = C logg n and = -C such that any algorithm computing AttC(n, d, log 2) requires 52 (n) time under SETH.
We show the following lemma to prove Theorem C.7.
Lemma C.8. The OV problem on vectors of dimension d. can be computed with high probability in time
ò ( (log (d log TATTC + 1, d log 10m2
29

---

Published as a conference paper at ICLR 2026
Given the above lemma, suppose have algorithm computing AttC. Given d define 8' = and let C' = (88) and C" log n as required in Theorem 2.2. Then, let 10n2d n --- for some large constant C C(5) 2 C². Any algorithm computing TATTC(" + 1, 1, 1, 2, E) then requires [2(=2-0) time, proving Theorem C.7.
Proof. Let A = (01,...,,,,, Jn J, (h,,.... ........,,,,. b S {0, 1] be two sets of vectors, Define Q K E paxd to be the matrices whose rows are formed by the vectors in and B, respectively, i.c.,
0i
a2
62
Q 1og(2)
K log(2)
an
b
Note that
log(2) a1 b1
log(2) a1 bn
QK
log(2) an 20. In particular, note that all row sums are and the i-th row sum of exp(QKT) is given by Σ integers satisfying n S S S n2d. From Lemma C.I, we can recover the row sums up 10n2a and therefore 1 additiie error time
log(2) an." bn
(log n log(dn2")) n + 1, 1, 1, 2, 10n2d
1
Given the to addiiivve approximation of S,, we may recover S; by rounding since they are integers. Note that S, S ndd and can therefore be represented in Od + log n) bits.
If there are no orthogonal pairs of vectors in A and B, then by is positive integer for all 1 < j I n, which means 20:4, is an even number. It follows that all of the sums SI...., Sn are also even numbers.
Conversely, when an orthogonal pair of vectors exists in A and B, we would like to detect this based on the sums .I,...: Sn, as well. Note that when a we have 20. 1, which may potentially make the sum into an odd number. However, when there are an even number of such orthogonal pairs, the sum remains even, and we cannot distinguish from the previous case. The workaround is to use a standard sampling method, so that with high probability, include exactly one pair of orthogonal vectors in the sample, and therefore the corresponding sum will be odd.
Fix an index 1 < in B orthogonal to ag. Without loss of generality, we may assume that the zero vector 0₂ & A. since we can check this in O (nd) time and immediately accepts the input if this is the case. Given 0,2 A, we know that vector 1 is not orthogonal to any vector in A. Consider the following sampling procedure:
such that a, A is orthogonal to some vector in B. Let b* be the last vector
Construct B' by including each vector of B with probability 1 independently and padding with 1, to ensure E has vectors. Note that with probability exactly 1/ we have that E' contains an odd number of orthogonal vectors to (i.e. 6* is included with probability 4). In particular, sampling B Olog n) -time allows us to detect an odd row sum with high probability.
Thus, the overall algorithm requires involves Ollog n) loops, where in each loop we check for an odd row-sum using Lemma C.I. The overall time is therefore
δ (log (logn)(d + log TATTC n + 1, d + 1, log 2, 10n24 ))
30


Reviews:
[{"review_id": "xq15B78Rqa", "reviewer": "Reviewer_Nr7R", "summary": "This work analyzes the computational complexity of approximating attention calculations. Authors propose a subquadratic algorithm particularly handling constant head dimensions with polylogarithmic scaling in input sizes, and establish matching conditional lower bounds under SETH. This work connects polynomial approximation methods with fine-grained complexity theory to clarify the efficiency limits of fast attention computation.", "questions": "1. The contents in Table 1 are confusing. Are the listed previous results upper bounds or lower bounds? In addition, there are only two citations, despite that four previous results are listed.\n2. The analysis in Line 392 raises concerns on the practical value of Theorem 1.3 when the head dimension $d$ is large, since then the exponent $2 - 1/d$ approaches quadratic complexity, reducing the \"sub-quadratic\" benefit of the proposed method.  \n3. In Line 452-454, the term $g^{\\mathcal{O}(d)}$ depends exponentially on the head dimension $d$, which could significantly affect query time and warrants further discussions.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper proposes a sub-quadratic algorithm for fast attention calculation with arbitrary temperatures within $\\tilde{O}(n^{2-1/d})$ runtime.\n2. There are complete complexity characterizations from constant to polynomial head dimensions.\n3. The technical approach is elegant, combining polynomial approximation with range searching.", "weaknesses": "1. The presentation and paper structure are not quite clear, making it hard to identify which parts are original. The technical overview could focus more on main insights or intuitions, deferring technical details to appendices.    \n2. The main concern of this work is lacking empirical comparisons between the proposed algorithm and existing methods (as baselines), making it difficult to evaluate their practical performance and efficiency.  \n3. Following 2, although the theoretical contributions are thorough, this work does not clearly explain how the derived theoretical results can be transformed to practical applications for further improvements in Transformer training or inference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "49ESQkUKHP", "reviewer": "Reviewer_4qhX", "summary": "This paper investigates the computational complexity of the Attention mechanism without temperature restrictions on the softmax operation. While prior work showed that subquadratic attention is possible only for small entry bounds $B=o(\\sqrt{\\log n})$ when $d=\\Theta(\\log n)$, this paper provides the first truly subquadratic algorithm with polylogarithmic dependence on $B$. The main contributions include: (1) an $\\mathcal{O}!\\left(n^{2-1/d},\\mathrm{polylog}(B)\\right)$ algorithm for constant head dimension $d$ using polynomial approximations and geometric range-searching data structures, (2) extensions to low-rank matrices and gradient computation, and (3) conditional lower bounds showing the algorithm is nearly optimal, with hardness results for $d=2^{\\Theta(\\log^* n)}$ under SETH and optimality for $d=\\mathrm{poly}(n)$ under the Generalized High-Dimensional OV Hypothesis.", "questions": "1. The algorithm achieves subquadratic time only for constant $d$, yet practical Transformers use $d=64, 128,$ or even $512$ for head dimensions. Given that your hardness results show $n^{2-o(1)}$ lower bounds for $d = 2^{\\Theta(\\log^* n)}$, could you comment on whether any algorithmic improvements are possible for the intermediate regime where $d$ ranges from $10$ to $100$?\n\n2. Your algorithm provides exact attention computation up to polynomial precision with $\\mathcal{O}(n^{2-1/d})$ time for constant $d$, while many existing works achieve $\\mathcal{O}(n)$ time using approximate attention with weaker guarantees as mentioned in lines 317-323. When would your approach be preferable to linear-time approximations?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Fundamental theoretical breakthrough. The paper resolves a key open question by providing the first subquadratic attention algorithm that scales polylogarithmically (rather than exponentially) with entry size $B$, enabling efficient computation for arbitrary temperature parameters. This represents a significant advance over Alman & Song (2024a), whose algorithms only worked for $B=o(\\sqrt{\\log n})$.\n\n\n2. Novel technical approach with elegant insights. The combination of polynomial approximation of the exponential function with Matoušek's simplex range-searching data structure is innovative. The key observation that relevant indices (those contributing significantly to softmax probabilities) form a half-space in $\\mathbb{R}^d$, enabling efficient geometric queries, demonstrates deep algorithmic insight that may have broader applications.\n\n\n3. Comprehensive complexity characterization. The paper provides nearly tight upper and lower bounds across multiple parameter regimes (Table 1), including a much stronger hardness result for $d=2^{\\Theta(\\log^* n)}$ compared to previous $d=\\Omega(\\log n)$, and establishing optimality of the standard algorithm for polynomial head dimensions. The reduction from gradient computation to attention (Theorem B.3) is also a clean theoretical contribution.", "weaknesses": "1. Limited practical applicability for realistic parameters. The algorithm only achieves subquadratic time for constant d, while practical Transformers commonly use d = 64, 128, or larger. As stated on lines 136–138, “when $d=\\omega(1)$, the above algorithms requires $n^{2-o(1)}$ time,” meaning no improvement over the standard $\\mathcal{O}(n^{2}d)$ algorithm for most practical settings.\n\n2. (minor) Limited experimental validation. Without experiments, it is unclear whether the algorithm is practical even for d = 2 or d = 3, or whether the overhead from the geometric data structures outweighs the asymptotic improvements.\n\n3. (minor) Missing relevant works. Despite the soundness and high impact of the theoretical results in this paper, there are still some works on efficient attention computation that require proper discussion [1,2,3,4,5,6]. \n\n### References\n\n[1] Josh Alman, Zhao Song. \"How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation\". ICLR 2024.\n\n[2] Josh Alman, Zhao Song. “Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform”. arXiv 2505.11892.\n\n[3] Josh Alman, Zhao Song. “Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse”. arXiv 2505.16284. \n\n[4] Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, Han Liu. “On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)”. NeurIPS 2024. \n\n[5] Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, Han Liu. “Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models”. ICLR 2025.  \n\n[6] Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song. “On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis”. arXiv 2501.04377.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EYlW1i3K2G", "reviewer": "Reviewer_RorL", "summary": "In this work the authors study fast algorithms for approximate attention computation in the transformer architecture. In particular for matrices $Q,K,V \\in \\mathbb{R}^{n\\times d}$, the goal of attention is to compute $Attention(Q,K,V) = D^{-1}AV$ where $A = \\exp(QK^T/\\sqrt{d})$ and $D = diag(A\\mathbb{1})$. The problem formulation they study is that assuming all entries of $Q,K,V$ lie in $[-B,B]$, the goal is to compute an $\\epsilon$ entrywise approximation to $Attention(Q,K,V)$. The classical naive algorithm for computing attention approximately runs in time $O(n^2 d)$, and a previous work of Alman and Song [AS2024] showed that for $d=\\Theta(\\log n)$ attention can be computed in time $n^{1+o(1)}$ whenever $B = o(\\sqrt{\\log N})$ and required $n^{2-o(1)}$ time whenever $B=\\Omega(\\sqrt{\\log n})$ and $d=\\Theta(\\log n))$ under the SETH hypothesis. \n\nThe algorithm of [AS2024] scales exponentially in $B$, and their first result makes progress towards improving this by presenting an algorithm that for $d=O(1)$ runs in time $n^{2-1/d}\\cdot polylog(B/\\epsilon)$. In the case when either $Q$ or $K$ have rank $r$, they show their algorithm generalizes to give a runtime of $nd + n^{2-1/r}\\cdot polylog(B/\\epsilon)$. Finally they show that when $d=O(1)$ this algorithm can be used to compute the gradient of the query,key and value projection matrices that project the hidden dimension to obtain the respective embeddings in time $n^{2-1/d}\\cdot polylog(B/\\epsilon)$. Finally they improve the previous lower bound to show that when $d= 2^{\\Omega(\\log^{*}n}$ and $B=poly(n)$ attention computation requires $n^{2-o(1)}$ time, and also when $d=poly(n)$ they show that matrix multiplication time is necessary for attention computation.", "questions": "One question I have is even though $n^{2-1/d} = n^{2-o(1)}$ for any $d=\\omega(1)$ but does the algorithmic result atleast hold in this regime ? Furthermore in the previous paper near the threshold $B=\\sqrt{\\log n}$ does your approach give a better lower bound than currently stated, i.e. can the results be improved in this regime because the strong lower bound holds for $d=2^{\\Omega(\\log^{*}n)}$ but $B=poly(n)$ ?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper has many strengths in particular developing an algorithm for approximate attention with a poly logarithmic dependence on $B$ when $d=O(1)$ which is a significant improvement over the previous works, and improving the lower bound for even smaller values of $d$, i.e. $d=2^{\\Omega(\\log^{*}n)}$.", "weaknesses": "One mild weakness is that the result appears to be entirely theoretical, and the algorithm not practical. However this is not a big negative as the theoretical contribution is substantial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7w3Bcr8cDV", "reviewer": "Reviewer_NyLU", "summary": "The paper gives subquadratic algorithms for attention at arbitrary temperature in constant dimension (and low-rank cases), paired with nearly tight conditional lower bounds. The theoretical picture is compelling.", "questions": "1. Could the authors provide any empirical or numerical evidence (even synthetic) to confirm that the proposed algorithm exhibits subquadratic scaling for n andwith  constant d? What are the actual constant factors involved in the halfspace data structure?\n2. The presentation is difficult to follow. Can the authors improve the paper writing? This would greatly help readers.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1.The paper successfully constructs the first true subquadratic algorithm for attention under arbitrary temperature when the dimension is constant, using a combination of relevance pruning, polynomial approximation, and halfspace range queries.\n2. The authors also give matching conditional lower bounds under SETH, making the theoretical landscape nearly complete.\n3. The problem is relevant of pratical and theoretical, understanding when subquadratic attention is theoretically possible has direct implications for scaling large models.", "weaknesses": "1. Writing quality is poor. Although the theoretical results is sound, exposition is hard to follow: section transitions are abrupt; key intuitions are buried under algebra; notation is very condusing; This substantially reduces accessibility. For example, you write too many theorems in the intro, informal veision, formal version. This is really confusing and make reader hard to find you core contribution,\n2. No experiments or even small numeric demos. Given the practical relevance of attention, the absence of any empirical validation (wall-clock, memory,  comparison to Flash/approximate/low-rank/kernelized attention under the paper’s error metric) makes it impossible to assess implementability. This make the paper not much meaningful to pratical sides.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)