acceptodds
Under review as a conference paper at ICLR 2027

Exact Softmax Attention Has the Rectangular Matrix-Multiplication Exponent in Extended Arithmetic Circuits

Abstract

Standard softmax attention explicitly forms all query–key scores, even when each query produces only a single scalar output. This raises a fundamental question: can exact attention avoid the arithmetic complexity of the underlying rectangular matrix multiplication? We show that it cannot. For queries and keys of width , with fixed , the minimum size of an exact-real circuit with gates is , even with only one scalar value per key. This matches standard exact evaluation and closes the previous single-head gap between and . Our main technical contribution is an exp–log span theorem showing that, modulo additive constants, all within-row score differences lie in the -linear span of the circuit's exponential inputs and logarithm outputs. Combined with mixed-coefficient extraction, this recovers the rectangular matrix-multiplication tensor and yields the lower bound. The same theorem also exactly characterizes transcendental complexity, giving exp/log gates for dense independently parameterized attention.

Primary area:
learning theory
Keywords:
softmax attention, arithmetic circuit complexity, rectangular matrix multiplication, exact computation, circuit lower bounds, functional transcendence, exp--log circuits

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FRqGOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors study the complexity of attention: how many arithmetic operations are needed to compute attention with context length nn and head dimension mm? The standard algorithm to compute attention involves computing a n×m×nn \times m \times n matrix product, but is this optimal? In the regimes where m = n^{o(1}} or m=Θ(n)m = \Theta(n), this optimality has previously been established, however a significant gap remained in the regime where mm is a small polynomial. The authors resolve this gap, and show that the size of a circuit required to compute attention is at least the size of the circuit required to compute a n×m×nn \times m \times n matrix product. The authors show this lower bound in the extended arithmetic circuit (eAC) model, following previous work, which is all circuits with +,−,×,/,exp⁡,log⁡+, -, \times, /, \exp, \log gates.

The proof proceeds (roughly) as follows: suppose we have a eAC of size s that computes attention. Then, if we set the input of the attention mechanism to be QQ and KK, then it can be shown (see Theorem 5) that each entry of QKtQK^{t} can be written as a linear combination of the inputs to exp⁡\exp gates and outputs of log⁡\log gates. Unfortunately, we may not know these linear equations, and they might be large/hard to compute (i.e. the overhead of the reduction may be too high). The key insight is that while the linear map may have large circuit size, they do not increase tensor rank. Thus, if we have a circuit that computes inputs to exp⁡\exp gates and outputs of log⁡\log gates (which our assumed circuit does), then we have a circuit of the same tensor rank that computes the matrix product QKtQK^{t}, and this yields a lower bound.

Critical strengths

It goes without saying that attention is an important algorithmic routine to study, and the paper provides strong lower bounds against faster attention computation, wrapping up open questions from prior work.

The result is interesting (if not particularly surprising) and the technical depth seems substantial.

Critical weaknesses

However, the reason I do not provide the paper a stronger rating lies in its presentation, and I worry that the poor presentation of the result hampers the ability of a reader to understand the submission. Thus, while the motivation and result are strong, the presentation is opaque. As an example, tensor rank is the key quantity that allows the authors to obtain the claimed lower bound, and this is not even defined in the submission (only that the authors use R(T)R(T) to denote it). Similarly, in the main technical tool (Theorem 5), "holomorphic germ" is undefined. Overall, the technical discussions are fairly terse, jargon-heavy, and difficult to understand.

If the presentation is significantly improved, I would be happy to improve my score. As it stands, I'm not sure publishing the result in its current form is very useful to the community.

Questions for authors

Can you give some intuition for Theorem 5?

3 comments
AuthorsOpenReview ↗

Revised presentation and intuition for Theorem 5

We thank the reviewer for the careful review and for an accurate summary of our argument. We agree that parts of the original paper were difficult to follow, and improving the presentation was our main focus in the revision.

“Overall, the technical discussions are fairly terse, jargon-heavy, and difficult to understand.”

Tensor rank is now defined in Section 2.1 (pp. 3–4): for a bilinear map TT, its rank R(T)R(T) is the smallest rr such that T(x,y)=∑k=1rak(x)bk(y)ckT(x,y)=\sum_{k=1}^{r}a_k(x)b_k(y)c_k, where ak,bka_k,b_k are linear forms and ckc_k are fixed output vectors. The same section explains the two properties used in our proof: a size-ss division-free circuit for a bilinear map gives rank O(s)O(s), and a fixed linear map on the output space cannot increase tensor rank. Holomorphic and meromorphic germs are now defined in Section 4 (p. 6), before Theorem 5, and we also explain why we use these local analytic tools. Transcendence degree is also defined in Section 2.1 (p. 3).

Beyond adding definitions, we revised the main technical sections to make the proof easier to follow. Section 2.3 (p. 4) now explains the three main steps of the proof and the two technical obstacles they overcome. Section 4 (pp. 5–7) now begins by explaining why the span theorem is needed and adds a simple example and a three-step proof overview; the detailed gate-prefix proof of Lemma 6 is moved to Appendix B.3. Section 5 (pp. 7–8) now explains the difficulties that remain after Theorem 5 and how Lemmas 8 and 9 address them.

“Can you give some intuition for Theorem 5?”

Differentiating the attention outputs with respect to the values gives the softmax weights, and ratios of weights within a row give esij−si,rie^{s_{ij}-s_{i,r_i}}. This does not mean, however, that the circuit computes the differences sij−si,ris_{ij}-s_{i,r_i} themselves. Adding a logarithm gate for each difference would cost n(m−1)n(m-1) extra gates, which can be as large as the target tensor rank, so the reduction would no longer be tight. Theorem 5 shows that these extra gates are unnecessary: once the value inputs are fixed at a regular point, every score difference already lies, modulo constants, in the rational linear span of the circuit's exponential inputs and logarithm outputs.

For a simple example, consider one query with scores (0,x)(0,x). A circuit may compute exe^x directly, or compute ex/2e^{x/2} and then square it. In the second circuit, xx is never an input to an exponential gate, but it is twice such an input. Theorem 5 shows that the same holds for arbitrary circuits with nested exponential and logarithm gates.

The proof restricts the inputs to a suitable affine line and compares two bounds on the transcendence degree of the field FF generated by the circuit's gate values. For the upper bound, we examine the gates in topological order. Each exponential or logarithm gate increases the transcendence degree by at most one, and only when it enlarges the span WW of exponential inputs and logarithm outputs; otherwise its output is algebraic over the field generated by the earlier gates. This gives trdeg⁡CF≤1+q\operatorname{trdeg}_{\mathbb{C}} F \leq 1+q.

Here q=dim⁡Q(W/C)q=\dim_{\mathbb{Q}}(W/\mathbb{C}).

For the lower bound, value differentiation shows that ep∈Fe^p\in F for every score difference pp. Suppose some pp lies outside WW. A basis of W/CW/\mathbb{C} together with pp then gives q+1q+1 functions that are rationally linearly independent modulo constants, and their exponentials are algebraic over FF. Ax's theorem, applied through an algebraic extension that preserves transcendence degree, then gives trdeg⁡CF≥q+2\operatorname{trdeg}_{\mathbb{C}}F\ge q+2, contradicting the upper bound.

We have included this explanation in Section 4, with the full technical details in Appendix B. We hope these revisions address the presentation concerns, and we welcome any suggestions on parts that still need clarification.

I appreciate the authors' revisions and there is some meaningful improvement in the updated draft (e.g. all terms seem defined). However, I still find that the steps behind the proof are not particularly well motivated, and would appreciate more intuition and motivation behind the proof (it does not necessarily need to be fully rigorous, but it is not clear to me what are the main ideas that make the proof work). ICLR is a general machine learning conference, and, especially now, the presentation of the results should be accessible to a general machine learning audience, which I do not believe is currently the case for this submission.

AuthorsOpenReview ↗

Further Intuition and Motivation for Theorem 5

We thank the reviewer for the follow-up and for acknowledging the improvements. We agree that our previous revision explained the proof steps more clearly than the ideas behind them. We have therefore further revised the Proof Overview (Section 2.3, p. 4) and the discussion of Theorem 5 (Section 4, pp. 6–7).

The main difficulty is that an attention circuit need not compute the score differences explicitly, even though differentiating its outputs with respect to the values reveals their exponentials. We therefore examine the exponential relations already present in the circuit. An exponential gate with input gg provides both gg and ege^g, while a logarithm gate with output LL provides both LL and eLe^L. The exponential of any rational linear combination of these gg's and LL's is algebraic over the field generated by the input functions and gate values. This motivates studying their rational linear span WW.

We have also extended the example with scores (0,x)(0,x). A circuit can obtain exe^x by squaring ex/2e^{x/2}, but cannot obtain it using only arithmetic operations and a single gate computing e2xe^{\sqrt{2}x}. Here xx and 2x\sqrt{2}x are rationally independent modulo constants, and Ax's theorem rules out obtaining exe^x this way.

Theorem 5 extends this idea to arbitrary circuits with nested exponential and logarithm gates. Let qq be the dimension of WW modulo constants, and let FF be the field generated by the input functions and gate values after restricting to a suitable line. If a score difference pp lay outside WW, it would add another rationally independent direction modulo constants, while epe^p would still belong to FF. The exponentials of a basis of WW are algebraic over FF, so adjoining them does not change its transcendence degree. Ax's theorem would then imply that FF has transcendence degree at least q+2q+2 over C\mathbb C, whereas the gate-by-gate argument gives an upper bound of q+1q+1. This contradiction forces p∈Wp\in W.

We appreciate the reviewer's continued feedback and hope these revisions make the main ideas of the proof easier to follow.

Reviewer_yETTOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies transformers as real-valued circuits (with the basic arithmetic operations and exp and log) and asks whether they could be implemented more efficiently than the obvious way, which requires multiplying an Nxd matrix with a dxN matrix (where N = sequence length and d = query/key dimension) and N^2 exp operations. The answer is no.

Critical strengths

The paper studies an interesting question and applies mathematical techniques that I believe have not been commonly seen in the transformer theory literature. However, I must give the caveat that much of the math is unfamiliar to me and I am not in a position to judge its correctness.

Critical weaknesses

I had difficulty understanding large parts of the paper, and do not know to what extent it's because of my math background and to what extent the paper could have been written better. My general impression is that it's probably more the former.

Questions for authors

I don't have any.

1 comment
AuthorsOpenReview ↗

A more accessible overview of the proof

We thank the reviewer for the thoughtful assessment. We agree that some parts of the original paper were difficult to follow, especially for readers who are less familiar with the algebraic tools we use. We have revised the presentation so that readers can understand the main proof before going through all the technical details.

One-channel attention produces only nn scalar outputs, yet we show that computing them requires as many operations, up to a constant factor, as the rank of a rectangular matrix-multiplication tensor. The proof has three main steps.

  1. Softmax does not change when we add a constant to every score in the same row, so we focus on within-row score differences. For dot-product attention, these differences form a rectangular matrix-multiplication tensor (Section 3).

  2. Any exact circuit implicitly contains these differences. If we differentiate the attention outputs with respect to the values, we obtain the softmax weights, and their ratios give the exponentials of the score differences. The exp–log span theorem (Theorem 5) shows that the differences themselves lie, modulo constants, in the rational linear span of the circuit's exponential inputs and logarithm outputs. For example, a circuit may compute exe^x as (ex/2)2(e^{x/2})^2; although xx does not appear as an exponential input, it is twice one.

  3. The linear combinations from step 2 can contain many terms, and computing them directly could require many additional operations. Instead, mixed-coefficient extraction produces the bilinear parts of the relevant internal functions with only constant overhead per gate, and the rectangular matrix-multiplication tensor is a fixed linear image of these bilinear parts. Since fixed linear maps on the output space cannot increase tensor rank, we obtain the circuit-size lower bound without computing the combinations (Section 5).

In the revised paper, Section 2.1 (pp. 3–4) defines tensor rank and transcendence degree and explains the properties needed in the proof, and Section 2.3 (p. 4) gives a clearer overview of the three steps and the two main difficulties. We have also revised Section 4 (pp. 5–7) to explain why the exp–log span theorem is needed. This section now defines holomorphic germs before using them, includes the example above, and explains the proof in three steps. We moved the detailed gate-prefix proof of Lemma 6 to Appendix B.3 so that the main text can focus on the key ideas.

We hope these changes make the paper easier to follow, and we welcome any suggestions on parts that still need clarification.

Reviewer_qnntOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This theory paper makes a connection between exact attention computation and rectangular matrix multiplication. Specifically, it gives a lower bound for one head and one scalar value/key attention computation based on the current matrix multiplication exponent, extending the previous result from Saha et al. (2026). The main technical aspects of this paper are based on Ax's theorem and algebraic complexity for matrix multiplication.

Critical strengths
  1. This paper gives a clear comparison table and some visual aids to show the main technical contribution of this paper. This helps to understand the novelty and general technical aspects of this paper.

  2. This paper improves previous lower bounds from Saha et al. (2026), giving results in a different setting. The techniques used in this paper are interesting.

  3. This paper studies an interesting problem, that focuses on the fundamental limits of attention computation. The potential impact of this paper is desirable.

Critical weaknesses
  1. The presentation quality of this paper requires further improvements. This paper is basically proof-driven, and its organization is quite hard to follow. It would be better if the authors first clearly put the main results in a section, or in the introduction, and then give preliminaries and a brief technical overview. The proof steps should be better put in appendix, especially for Section 4.

  2. It would make this paper easier to understand if the authors improve this draft by explaining the necessity of the span theorem, and reviewing the main technical obstacles to showing the lower bound.

  3. This paper only discusses the foward computation of softmax attention. It would be better if the authors also consider a potential extension to the backward computation.

Questions for authors
  1. Could the authors explain the main obstacles to establishing the lower bound, and why the exp-log span theorem is necessary to overcome them?

  2. Could the authors discuss if the proposed lower-bound framework can be extended to backward computation?

2 comments
AuthorsOpenReview ↗

On the main obstacles and backward computation

We thank the reviewer for the helpful suggestions on the paper's organization and for the two questions. We have revised the presentation and added a result on backward computation.

“It would be better if the authors first clearly put the main results in a section, or in the introduction, and then give preliminaries and a brief technical overview. The proof steps should be better put in appendix, especially for Section 4.”

The main results are summarized in Section 1.1, and the main theorem is stated formally in Section 2.2, before any proofs. Section 2.1 (pp. 3–4) now defines tensor rank and transcendence degree and explains the properties of tensor rank used in the proof. Section 2.3 (p. 4) now gives a clearer proof overview, organized around three main steps and the two technical obstacles explained below. Section 4 (pp. 5–7) now includes a motivating example and a three-step explanation of Theorem 5; we moved the detailed gate-prefix proof of Lemma 6 to Appendix B.3 while keeping the main proof in the paper.

“Could the authors explain the main obstacles to establishing the lower bound, and why the exp-log span theorem is necessary to overcome them?”

The score differences sij−si,ris_{ij}-s_{i,r_i}, where rir_i is a reference column in row ii, form a rectangular matrix-multiplication tensor. Recovering them from an attention circuit faces two obstacles.

The first obstacle is that the circuit need not compute the score differences explicitly. Since the attention output is linear in the values vv, differentiating with respect to vv shows that the softmax weights lie in the field generated by the circuit's gate values, and their within-row ratios give esij−si,rie^{s_{ij}-s_{i,r_i}}. This yields the exponentials of the differences as field elements, but not the differences themselves as gate values. Adding a logarithm for each difference would cost n(m−1)n(m-1) extra gates, which can be as large as the target tensor rank, so the reduction would no longer be tight. The exp–log span theorem (Theorem 5) shows that these gates are unnecessary: once the value inputs are fixed at a regular point, every score difference already lies, modulo constants, in the rational linear span of the circuit's exponential inputs and logarithm outputs. For example, a circuit may compute exe^x as (ex/2)2(e^{x/2})^2; then xx is not an exponential input, but it is twice one. The theorem extends this to arbitrary nesting of exponential and logarithm gates.

The second obstacle is that the linear combinations may be expensive to compute. The relations given by Theorem 5 can contain many terms, so evaluating them directly could take far more than ss arithmetic operations. We never evaluate them. Mixed-coefficient extraction produces, with only O(s)O(s) arithmetic gates, a bilinear tensor of which ⟨n,d,m−1⟩\langle n,d,m-1\rangle is a fixed linear image. Because a fixed linear map on the output space cannot increase tensor rank, this gives R(⟨n,d,m−1⟩)=O(s)R(\langle n,d,m-1\rangle)=O(s) (Section 5, pp. 7–8).

As discussed in Section 2.3 and Appendix G, standard approaches do not reach this bound: a first-order softmax expansion recovers products with exponent ω(1,a,a)\omega(1,a,a), and coordinate selectors recover only O(d)O(d) score columns per call, requiring N1−a+o(1)N^{1-a+o(1)} more calls. The span theorem lets us use all m−1m-1 difference columns from a single circuit.

“Could the authors discuss if the proposed lower-bound framework can be extended to backward computation?”

Yes, for exact value-gradient computation; we have added a matching lower bound. Let P=softmax⁡(QK⊤)P=\operatorname{softmax}(QK^\top), and suppose a circuit of size ss computes B(Q,K,λ)=P⊤λB(Q,K,\lambda)=P^\top\lambda, where λ∈RN\lambda\in\mathbb{R}^N is a variable upstream gradient. With an auxiliary vector vv, define F=v⊤B=λ⊤PvF=v^\top B=\lambda^\top Pv; then ∇λF=Pv\nabla_\lambda F=Pv is exactly the forward one-channel attention output. By the extended Baur–Strassen theorem for eACs (Theorem 29; Saha et al., 2026, Theorem 4.4), this gradient can be computed with O(s+N)O(s+N) gates, and fixing λ\lambda at a valid point yields a circuit for forward attention. Theorem 1 then gives R(⟨N,d,N−1⟩)=O(s+N)R(\langle N,d,N-1\rangle)=O(s+N). Since the NN outputs of BB are distinct functions, none of which is a constant or an input coordinate, the circuit has at least NN gates, so s=Ω(R(⟨N,d,N−1⟩))s=\Omega(R(\langle N,d,N-1\rangle)). For d=⌈Na⌉d=\lceil N^a\rceil with fixed 0<a≤10<a\le1, exact value-gradient computation thus has the same optimal exponent Nω(1,a,1)+o(1)N^{\omega(1,a,1)+o(1)} as forward attention.

This result assumes that the circuit receives the original inputs and a variable upstream gradient λ\lambda. It does not cover a backward pass that receives forward values such as PP for free, since P⊤λP^\top\lambda then costs only O(N2)O(N^2) operations, and we do not claim lower bounds for gradients with respect to QQ or KK. The full statement and proof are in Corollary 27 (Appendix E.5, pp. 24–25).

Thanks for the careful response to my concerns. I have no further questions and would like to keep my positive recommendation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.