- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the expressive power of fixed-size, real-valued multi-layer softmax Transformers as the input length grows. The main results are and The paper also gives lower bounds, results for symmetric functions, and limitations on accessing deep bits of a real-valued input.
The main proof uses real geometry: Transformer computations are rewritten using exponential--linear polynomial systems, and bounds of Karpinski--Macintyre and Khovanskii are then applied. The static deep-bit result uses a related connected-component argument.
Critical strengths
-
The paper studies multi-layer softmax Transformers with arbitrary real precision, without replacing softmax by hard attention.
-
The static deep-bit result is interesting. It shows that infinite precision does not imply unlimited access to the information stored in a real number. The connected-component argument gives a clear mathematical explanation of this point.
-
Extending split-VC upper bounds to trained multi-layer softmax Transformers also appears useful.
Critical weaknesses
- The novelty of the main VC result is not sufficiently clear.
Polynomial VC bounds for neural computations with exponential/Pfaffian structure are classical [1], and split VC dimension and infinite-precision limitations for one-layer softmax Transformers were already studied in [2]. Unconditional limitations for multi-layer Transformers were also given in [3]. More importantly, He et al. [4] already use a VC-dimension upper bound for standard Transformers with softmax, ReLU, and residual connections. Therefore, the paper should explain more clearly what is new in the result beyond existing VC bounds for exponential computations.
- The lower bounds are weak compared with the upper bounds: $ \Omega(n)\leq \mathrm{VC}(T^{(n)})\leq O(n^4), \qquad \Omega(n)\leq \mathrm{SplitVC}(T^{(n)})\leq O(n^6). $
These gaps are very large. Moreover, the lower-bound constructions have close precedents. The binary symmetric-function construction explicitly builds on Chiang and Cholak [5], and the indexing task has been studied recently in [6].
- I also have two proof concerns.
The proof of Theorem 3.1 uses a parameter number that is independent of , but it is unclear how this is consistent with arbitrary learned positional embeddings. In addition, the LayerNorm lifting uses and later claims uniqueness of the auxiliary variables, although has two real solutions when . Thus, the claimed homeomorphism is not justified as written.
[1] M. Karpinski and A. Macintyre. Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Journal of Computer and System Sciences, 1997.
[2] A. Kozachinskiy et al. Strassen Attention, Split VC Dimension and Compositionality in Transformers. NeurIPS, 2025.
[3] L. Chen, B. Peng, and H. Wu. Theoretical limitations of multi-layer Transformer. FOCS, 2025.
[4] X. He, Y. Jiao, X. Lu, and J. Z. Yang. Approximation Error Upper and Lower Bounds for Holder Class with Transformers. ICML, 2026.
[5] D. Chiang and P. Cholak. Overcoming a Theoretical Limitation of Self-Attention. ACL, 2022.
[6] A. Kozachinskiy, V. Opazo, and F. Urrutia. Indexing: the Beginning and the End. arXiv:2607.22361, 2026.
Questions for authors
-
Can the authors explain precisely why the VC bound does not follow from existing VC bounds for real computations with exponential operations, especially in view of the standard-softmax analysis in [4]?
-
What class of positional embeddings is allowed in Theorem 3.1? If an arbitrary learned positional table is allowed, how is its parameter growth handled in the proof?
-
How should the LayerNorm lifting be modified to justify the claimed homeomorphism when has two real solutions for ?
-
What is the main new content of the lower bounds beyond the constructions in [5] and [6]? Is there a way to reduce the large gap between the upper and lower bounds?
3 comments
Thank you again for your very careful review!
We have submitted a newer version of the manuscript (with changes in blue) to address the technical concerns that you've pointed out. Our handling of word and positional encodings in the original manuscript was flawed, and we have added Section 3.2, together with corresponding changes to the abstract and introduction, to fix this. We have fixed the issue of having multiple real solutions by pointing out that the equations we define have a solution set consisting of multiple homeomorphic copies of the original solution set (witnessed by the local homeomorphisms mentioned in our proof of Theorem 3.1 in Appendix C), and that a bound on the number of connected components in this solution set thus implies a bound on the number of connected components in the original solution set.
We believe we have addressed your main concerns, and as the discussion period closes, we’d like to hear from you whether there are any further last-minute concerns we can speak to. Thank you!
Thank you for your very careful and insightful review!
Thank you for bringing the paper by He et al [4] to our attention. They use Anthony and Bartlett's Theorem 8.14 to get a VC bound of O(D4) for transformers with depth D and no layer normalization. They do not analyze how it depends on n (sequence length), but if they had, they would have obtained the same asymptotic bounds as our Theorem 3.4. The reason they omit layer normalization is that it uses a square root, which Anthony and Bartlett's theorem does not allow. By contrast, our bound follows the definition of transformer closely, including layer normalization.
You also mentioned [3] as a previous unconditional bound on multi-layer transformers; as pointed out briefly in Section 1, this bound assumes O(logn) precision, whereas we make no assumptions on precision.
In Theorem 3.1, we assume fixed positional encodings, as in the original paper and as in Definition A.1 (where the input is simply taken to be a sequence of vectors). With learned positional encodings, the bound would increase to O(n6). We will add this as a new claim in the paper.
However, Prop 4.4 uses learned positional encodings, so we acknowledge that the implicit comparison in the first column of Table 1 is not apples-to-apples. We will revise this table to read:
Thank you for pointing this issue out. One way to resolve it would to be observe that the new solution set is made of 22Ln homeomorphic copies of the old solution set (2 copies for each layernorm, and there are 2Ln layernorms), so an upper bound on the number of connected components of the new solution set implies the same upper bound on the number of connected components of the old solution set.
Proposition 4.4 generalizes the PARITY construction of [5] to a much larger class of functions. Even if the required change to the proof is very small, we think the generalization is a genuine improvement.
Proposition 6.3 is similar to Theorem 12c of [6]. However, the two proofs use different techniques. Our construction is uniform (none of the parameters of the model depend on n), whereas their construction requires multiplying the logits by a sufficiently large constant that does depend on n. (Kozachinskiy et al.'s paper [6] is considered contemporaneous work according to ICLR guidelines, but we will certainly add a citation and discussion in the final version.)
We acknowledge in Section 8 that there are gaps between the upper and lower bounds and leave the improvement of these bounds for future research.