- 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 and head dimension ? The standard algorithm to compute attention involves computing a matrix product, but is this optimal? In the regimes where m = n^{o(1}} or , this optimality has previously been established, however a significant gap remained in the regime where 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 matrix product. The authors show this lower bound in the extended arithmetic circuit (eAC) model, following previous work, which is all circuits with 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 and , then it can be shown (see Theorem 5) that each entry of can be written as a linear combination of the inputs to gates and outputs of 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 gates and outputs of gates (which our assumed circuit does), then we have a circuit of the same tensor rank that computes the matrix product , 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 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
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.
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 provides both and , while a logarithm gate with output provides both and . The exponential of any rational linear combination of these 's and 's is algebraic over the field generated by the input functions and gate values. This motivates studying their rational linear span .
We have also extended the example with scores . A circuit can obtain by squaring , but cannot obtain it using only arithmetic operations and a single gate computing . Here and are rationally independent modulo constants, and Ax's theorem rules out obtaining this way.
Theorem 5 extends this idea to arbitrary circuits with nested exponential and logarithm gates. Let be the dimension of modulo constants, and let be the field generated by the input functions and gate values after restricting to a suitable line. If a score difference lay outside , it would add another rationally independent direction modulo constants, while would still belong to . The exponentials of a basis of are algebraic over , so adjoining them does not change its transcendence degree. Ax's theorem would then imply that has transcendence degree at least over , whereas the gate-by-gate argument gives an upper bound of . This contradiction forces .
We appreciate the reviewer's continued feedback and hope these revisions make the main ideas of the proof easier to follow.
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 T, its rank R(T) is the smallest r such that T(x,y)=∑k=1rak(x)bk(y)ck, where ak,bk are linear forms and ck are fixed output vectors. The same section explains the two properties used in our proof: a size-s division-free circuit for a bilinear map gives rank 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,ri. This does not mean, however, that the circuit computes the differences sij−si,ri themselves. Adding a logarithm gate for each difference would cost 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). A circuit may compute ex directly, or compute ex/2 and then square it. In the second circuit, x 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 F 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 W of exponential inputs and logarithm outputs; otherwise its output is algebraic over the field generated by the earlier gates. This gives trdegCF≤1+q.
Here q=dimQ(W/C).
For the lower bound, value differentiation shows that ep∈F for every score difference p. Suppose some p lies outside W. A basis of W/C together with p then gives q+1 functions that are rationally linearly independent modulo constants, and their exponentials are algebraic over F. Ax's theorem, applied through an algebraic extension that preserves transcendence degree, then gives trdegCF≥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.