acceptodds
Under review as a conference paper at ICLR 2027

New Lower Bound Techniques for Transformers

Abstract

Existing lower bound techniques for transformers still do not allow us to fully understand even the one-layer case. One example of this is such a fundamental and simple task like PARITY – checking if the number of 1s in a binary input sequence is even. While a 2-layer construction for PARITY due to Chiang and Cholak is known, it is open if 1-layer transformers can solve PARITY. Known techniques like communication complexity and split vc dimension are not enough to resolve this problem as in the case of PARITY they do not yield non-trivial lower bounds. In this paper, we develop a new technique that allows us to resolve this problem. We first show for every language, computable by a 1-layer transformer, can be in some sense expressed in the first-order theory of reals with addition, multiplication and order. More precisely, one can write a fixed formula where, for each input length, free variables can be substituted by linear expressions in input bits in a way that the resulting formula computes the restriction of the language to this input length. Using results from Boolean function complexity, we then conclude that every language 1-layer transformers can do has average sensitivity , which means that PARITY is not doable by 1-layer transformers. Moreover, we notice that for 1-layer transformers with a single attention head, the formula does not require multiplication, and this allows us to separate 1-layer transformers with 1 head from 1-layer transformers with 2 heads. More specifically, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transformer. A similar separation result was previously obtained for the attention-only model, while our results assume the model with the output MLP.

Primary area:
foundation or frontier models, including LLMs
Keywords:
transformers, attention heads, lower bounds, parity, sensitivity

Reviews

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

This paper studies the expressiveness of fixed-size Transformers with softmax attention, infinite precision, a ReLU-based output MLP, and no CoT. Its main result establishes that a one-layer Transformer in this setting cannot compute PARITY.

The main proof idea is that these Transformers can compute only functions with average sensitivity bounded by O(n polylog(n))O(\sqrt{n}\,\mathrm{polylog}(n)), whereas PARITY has average sensitivity nn.

Critical strengths

The paper makes a clear theoretical contribution and develops a new lower-bound technique. Moreover, the one-layer lower bound yields two important comparisons with previous work:

  1. Two-layer Transformers are known to compute PARITY, establishing a sharp depth separation within the stated model.
  2. Several previous communication-complexity lower bounds require precision to be restricted to no(1)n^{o(1)} bits. This paper establishes a lower bound without such a restriction, and resolves the one-layer PARITY problem. Though existing Split-VC methods could do not require bounded-precision, it could not address the PARITY problem.
Critical weaknesses

About the one-layer vs. two-layer contrast: the known two-layer construction uses a non-standard positional encoding. This assumption should be explicitly stated in the paper.

Minor: The citation commands \citep and \cites are used incorrectly in some places.

Questions for authors

None.

1 comment

Thank you for the positive review! We will clearly state that we are using i↦(i,i2)i \mapsto (i, i^2) PE in the introduction, and will fix the \citep, \cites issue in the revised version.

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

The authors of this work propose new lower bound strategy in analyzing the expressiveness of one-layer soft attention transformers. The main contribution is the utilization of a fixed first-order formula to represent a transformer than can computed by some Boolean functions; then, the authors use quantifier eliminates and existing bounds on the average sensitive of the polynomial threshold functions to establish the upper bound of O(npolylog⁡n)O(\sqrt{n} \mathrm{poly} \log n) on average sensitivity. This paper also has other interesting theoretical results beyond this.

Critical strengths
  • The lower bound theory is interesting and new, it is novel to connect transformer expressiveness, first-oder logic over the reals, and the polynomial threshold functions. The new lower bound theory tends to be better than existing lower bound for PARITY by communication-complexity and Split-VC dimension.

  • The new expressiveness theory seems to be tighter than existing ones because the author show that two layers of soft attention transformer are necessary and sufficient to compute PARITY. The authors also create a strict separation between one head and two head one layer transformer which involves residual connections and an output MLP.

Critical weaknesses
  • One thing I concern is that the theory will be hard to extend to multi-layer setting because the final position query is determined by a single input token, allowing attention outputs to be expressed as ratios of affine functions. If we extend this to multi-layer, queries and keys will depend on contextualized representations.

  • Another thing is the connection with the realistic settings. In practice, we will have floating-point precision models and often with finite precision setting. The expressiveness bound developed on real number may become too loose to capture the real transformer. I would like to how will this new lower bound theory develop where precisions are floating-point precisions (constant, log⁡n\log n, poly(n)\mathrm{poly}(n)) like [Li et al, ICLR'24], or the authors can simply work on a finite set such as the setting in [Grazzi et al, ICLR'25].

[Li et al, ICLR'24] Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

[Grazzi et al, ICLR'25] Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues

Questions for authors

Q1: Have authors considered the multi-layer setting? Or some intuition of how theory will develop in the multi-layer setting?

Q2: How will the precision impact the theory bounds?

2 comments

Thank you for the generally positive review!

Q1/W1 While the multi-layer setting is, of course, of interest to us, the scope of our paper is to develop a technique sufficient to fill the gaps in our understanding of 1 layer – for instance, to resolve whether parity can be done in 1 layer. Thus, by default, our technique in its current form cannot be directly applied to more than 1 layer – it applies to parity, and parity can be done in 2 layers. Nevertheless, we believe that accumulating such results and techniques will eventually be useful for multi-layer lower bounds.

Q2/W2 Note that in the case of the lower bounds, the infinite-precision assumption gives the strongest result possible. It removes the discussion of what the correct precision regime is and shows that the task is impossible to do in any of them. At the same time, for our upper bounds – the 1-layer 2-head construction for ORDERED – O(log⁡n)O(\log n) bits of precision are enough.

Thanks for the explanation! I will maintain my score

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

This paper proves lower bounds on the number of layers a transformer needs to recognize two languages: PARITY and ORDERED (= 01). For both languages, they show that at least two layers are needed. For both languages, they rely on a translation of one-layer transformers to a first-order formula over (R, <, +, *), which I believe was previously known (https://arxiv.org/abs/2501.19215), and quantifier elimination. PARITY uses a previous result relating the size of this formula to sensitivity. For ORDERED, they give a geometric argument for the lower bound and a new proof that two layers are sufficient.

Critical strengths

Since quite a bit of previous work has been done on one-layer transformers, I believe that results separating one-layer from multi-layer transformers are very important. The technique of relating the size of a formula defining a language with the sensitivity of that language seems like it could be more generally useful.

Critical weaknesses

I think the writing could be more clear in places, but other than that I don't really see weaknesses I would call "critical."

Questions for authors

None

1 comment

Thank you for the generally positive review! We would just like to point out that the paper you are referencing introduces the split vc dimension technique; we believe there is no first-order formula translation. We mention this paper in the introduction and explain why split-vc technique is not sufficient to show lower bounds for parity.

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

The paper proves that transformers with softmax attention cannot decide PARITY with just 1 attention layers. The result that transformer decides PARITY with 2 attention layers was proved in existing literature. Therefore, the paper's result strictly separate the expressive power of 1-layer and 2-layer transformers.

Moreover, the paper proves that 1-layer transformer with 1 head cannot decide ORDERED, while 1-layer transformer with 2 heads can.

A key technique used throughout the paper is to express transformer computations in terms of logics expressions over the reals and thereby applying related results.

Proofs (in the main body of the paper) seem valid to me.

In general, the paper is a nice addition to transformer expressivity literature, both in terms of its results and its techniques. Therefore, I lean towards accepting.

Critical strengths

The use of logic over reals and average sensitivity is an interesting addition to the literature of transformer expressivity.

The paper proves separation results in transformer, which helps add to a more complete picture in computational power separations of transformers with different computational budgets.

Critical weaknesses

The results in the paper are somewhat incremental and do not have large implications to the general expressivity of transformers. A few more general questions arise immediately. For instance, is there a separation between n-layer and (n-1)-layer transformer? Is there a separation between 1-layer transformer with (n-1) heads and 1-layer transformer with n heads?

Questions for authors

Did the use of first-order logic over reals appear before in the literature of transformer expressivity? I see no such references in the introduction.

Where do lemmas/theorems in Sections 3 and 4 fail to be true for a transformer with 2 layers?

On lines 416-417, does C depend on r and n?

2 comments

Thank you for the generally positive review!

Q1 In general, logical methods have been used widely in the context of hard-attention transformers, but the use of the first-order logic of reals, as far as we know, is a new insight.

Q2 Crucially, each input token is determined by the value of the input bit in its position. Any expression a(xi)a(x_i) that depends just on the input bit xix_i can be written linearly in xix_i due to a trick: a(xi)=a(1)xi+a(0)(1−xi)a(x_i) = a(1) x_i + a(0)(1 - x_i), allowing linear expressions developed in lines 270-289. After just one layer, the value of the ii-th token already depends not only on x(i)x(i), which disables the a(xi)=a(1)xi+a(0)(1−xi)a(x_i) = a(1) x_i + a(0)(1 - x_i) trick.

Q3 CC does not depend on nn. Both CC and rr come through Lemma 2 from a 1-layer, 1-head transformer that supposedly computes ORDERED. These are constants independent of the input length – CC is the number of atomic subformulas of the formula after quantifier elimination, and rr is its number of free variables

I thank the authors for their answers to my questions.

A minor comment is that the authors should do some thorough proof-reading for a camera-ready version. For instance, in lines 270-271, you mentioned equation 15, which is not introduced prior; in line 413, you say "the proof of Appendix 6."

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised version

We thank all the reviewers for their constructive remarks. Following them, in the revised version, we have indicated explicitly in the introduction what kind of PE we are using in our 2-head 1-layer construction for ORDERED; we also fixed some issues with citations and references to equations.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.