acceptodds
Under review as a conference paper at ICLR 2027

VC Dimension and Expressivity of Real-Valued Transformers

Abstract

Whereas previous results on abilities and limitations of transformers have restricted the definition of transformers in various ways, here we study softmax-attention, multi-layer transformers operating on real values, with very few additional assumptions. Applying results from real geometry, we obtain upper bounds on the VC dimension and split VC dimension of such transformers ( and , respectively, where is the input length). Conversely, we also construct specific transformers witnessing lower bounds on these quantities ( in each case). These results have some notable consequences. For example, within the class of symmetric (permutation-invariant) functions, we show that transformers can uniformly express all functions over an alphabet of one symbol and non-uniformly express all functions over an alphabet of two symbols, but cannot (even non-uniformly) express some functions over an alphabet of six symbols. We also prove limitations on how many bits of a real number a transformer can access.

Primary area:
learning theory
Keywords:
transformers, learning theory, real geometry, VC dimension, splitting VC dimension, generalization bounds

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_X7sJOpenReview ↗
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 nn grows. The main results are VC(T(n))=O(n4)\mathrm{VC}(T^{(n)})=O(n^4) and SplitVC(Tθ(n))=O(n6).\mathrm{SplitVC}(T_\theta^{(n)})=O(n^6). The paper also gives Ω(n)\Omega(n) 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
  1. The paper studies multi-layer softmax Transformers with arbitrary real precision, without replacing softmax by hard attention.

  2. 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.

  3. Extending split-VC upper bounds to trained multi-layer softmax Transformers also appears useful.

Critical weaknesses
  1. 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 O(n4)O(n^4) result beyond existing VC bounds for exponential computations.

  1. 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].

  1. I also have two proof concerns.

The proof of Theorem 3.1 uses a parameter number that is independent of nn, but it is unclear how this is consistent with arbitrary learned positional embeddings. In addition, the LayerNorm lifting uses z4=vz^4=v and later claims uniqueness of the auxiliary variables, although z4=vz^4=v has two real solutions when v>0v>0. 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
  1. Can the authors explain precisely why the O(n4)O(n^4) 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]?

  2. What class of positional embeddings is allowed in Theorem 3.1? If an arbitrary learned positional table is allowed, how is its O(n)O(n) parameter growth handled in the proof?

  3. How should the LayerNorm lifting be modified to justify the claimed homeomorphism when z4=vz^4=v has two real solutions for v>0v>0?

  4. What is the main new content of the Ω(n)\Omega(n) 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 for your very careful and insightful review!

  1. 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]?

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)O(D^4) for transformers with depth DD and no layer normalization. They do not analyze how it depends on nn (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(log⁡n)O(\log n) precision, whereas we make no assumptions on precision.

  1. What class of positional embeddings is allowed in Theorem 3.1? If an arbitrary learned positional table is allowed, how is its O(n) parameter growth handled in the proof?

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)O(n^6). 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:

VC, trained, fixed PEVC, trained, learned PEsplit-VC, untrained
upper boundO(n4)O(n^4) (Thm. 3.1)O(n6)O(n^6)O(n6)O(n^6) (Cor. 3.5)
lower boundn/aΩ(n)\Omega(n) (Prop 4.4)Ω(n)\Omega(n) (Prop. 6.3)
  1. How should the LayerNorm lifting be modified to justify the claimed homeomorphism when z4=vz^4=v has two real solutions for v>0v>0?

Thank you for pointing this issue out. One way to resolve it would to be observe that the new solution set is made of 22Ln2^{2Ln} homeomorphic copies of the old solution set (2 copies for each layernorm, and there are 2Ln2Ln 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.

  1. 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?

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.

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 z4=vz^4 = v 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 π\pi 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!

Reviewer_NjxKOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

This paper mainly focuses on chatecrizing the expressive ability of a transformer with a fixed structure and size using VC dimension and split VC dimension. The research gap the paper aims to address is clear, and the problem is interesting.

Critical strengths
  1. The research gap the paper aims to address is clear. Existing studies mainly analyze some approximated or related versions of transformers. This paper focuses on the Fost and multi-layer transformer models, which address a clear gap.

  2. The results are interesting. The authors characterized the upper bound of the VC dimension for a fixed-size transformer, which is intriguing.

Critical weaknesses
  1. The paper is not easy to follow. See detailed comments below.
Questions for authors

My major concern is that the paper is not easy to follow. The authors are advised to significantly enhance the paper's readability.

  1. Figure 1 is not confusing. It tries to provide some related work and a research roadmap, but it does not serve its purpose. The authors are suggested to provide a clear table of related works to highlight what existing studies have done and the novelty/contribution of this paper as compared to existing ones.

  2. The introduction is not easy to follow. It does not provide any background, such as what problem we are focusing on, the motivation (why we are focusing on it), and the research gap is mentioned in the paper but is not clear. It reads like a composition of various existing methods, without a clear storyline. Thus, I suggest that the authors make the storyline clear.

  3. The paper does not have a related work section. While some related works are discussed in the introduction, it is still not clear enough what existing studies have done and what the contribution of the paper is. The authors are suggested to give a comprehensive review of existing studies.

  4. The paper includes a lot of definitions, theorems, propositions, but there is little discussion or interpretation of them, This makes the paper reads like a stack of mathematical equations and the audience may be buried in this mathematical equations but can not get much insights. It is reasonable that a theoretical paper can have many equatiosn and math symbols, but the authors should also provide something to help the audience to understand the paper. Such as some illustratice examples, some paragraphs before and after the definitions to help the audience understand why we need this definition/theorem, and what does it mean. I think this may help the audience understand it easier and get some insight from the paper.

  5. The proof is not well atructured. It does not have clear guidance for the audience to read it and how each step come out. Also, it does not provide sufficient mathematical background. This makes the proof hard to verify and understand. I suggest the authors to re-write the proof in a clear step-by-step way with sufficient details and guidance to make the audience easy to follow.

5 comments
  1. Figure 1 is not confusing. It tries to provide some related work and a research roadmap, but it does not serve its purpose.

The purpose of Figure 1 is not to show the relationship of this paper to existing VC bounds or expressivity results for transformers, but to show the historical and logical relationship of our VC bound to the results that it builds on. We discuss the relationship of this paper to existing VC bounds and expressivity results for transformers in the first paragraph of the introduction. (We did miss one paper by He et al, pointed out to us by Reviewer X7sJ, which we will add in the final version.)

  1. The introduction is not easy to follow. It does not provide any background, such as what problem we are focusing on, the motivation (why we are focusing on it), and the research gap is mentioned in the paper but is not clear.

We acknowledge that the introduction is written compactly, though we do believe that the introduction covers all of the points you listed. Given an extra page in the final version, we be able to revise the introduction to provide a fuller background, motivation, and problem statement. As for the research gap, since your Strengths section says, "The research gap the paper aims to address is clear," we're uncertain how to address your comment about the research gap here.

  1. The paper does not have a related work section.

We have opted to discuss related work in the introduction. If, in the revision, the discussion of related work becomes unwieldy, we will consider moving it to a separate section.

  1. The paper includes a lot of definitions, theorems, propositions, but there is little discussion or interpretation of them.
  2. The proof is not well atructured. ... Also, it does not provide sufficient mathematical background.

We acknowledge that some of the mathematical concepts in this paper may not be familiar to the ICLR audience. We have tried to explain what we feel needs explaining, but will continue to improve the presentation in the final version. Specific areas of improvement include:

  • We have reorganized the proof of Proposition 5.4 (in Appendix E) somewhat, which will hopefully make it easier to understand.

  • We provide background on topology in Appendix B and will add more cross-references to it where appropriate.

  • We have also separately written a exposition of Karpinski and Macintyre's theorem intended for a machine-learning audience; we would be happy to include this as another appendix if desired.

Finally, we would like to point out that both of the other reviewers have given our paper the maximum score for presentation.

Reviewer_NjxKOpenReview ↗

Response to the Rebuttal

Thank you for the response. I appreciate the authors' efforts and willingness to improve the presentation. However, I would like to clarify a few points regarding my comments.

First, regarding the research gap, my comments concern two different aspects: the research contribution itself and how it is presented. The research gap that the paper aims to address is clear, as acknowledged in my Strengths section. However, I believe that the introduction could communicate this gap more effectively by providing clearer background, motivation, and discussion of the limitations of existing work.

Second, regarding the mathematical presentation, my concern is not primarily that the mathematical concepts may be unfamiliar to ICLR readers. Rather, I believe that the paper would benefit from more discussion and interpretation of its mathematical results, including the intuition behind the theorems, their significance, and how the different results contribute to the main argument. Similarly, the proofs would benefit from a clearer overall structure and explanation of the key steps.

Third, regarding related work, I still believe that a dedicated Related Work section is necessary for this paper. My concern is not merely about the organization of the manuscript, but about the need for a more systematic discussion of existing results and their relationships to the proposed work. Such a discussion would help readers better understand the novelty and contributions of the paper.

Finally, regarding the presentation scores, I fully respect the assessments of the other reviewers. At the same time, as an independent reviewer, my assessment reflects my own reading of the manuscript and the specific concerns identified in my review. I believe that different reviewers may reasonably arrive at different assessments.

Overall, I appreciate the authors' response and recognize their efforts to address my comments. However, based on the current manuscript and the rebuttal, I believe that my main concerns regarding the presentation and organization remain insufficiently addressed. Therefore, I will maintain my original rating of Weak Reject.

Thank you for your feedback! We've submitted a newer version of the manuscript that has the changes colored in blue. Our proof of Proposition 5.4 in Appendix E now includes diagrams that provide intuition for some of the mathematical ideas in our proofs, and our introduction includes a more extended discussion of related previous work and the limitations of such work. We are willing to consider adding a "related work" section and an exposition of Karpinski and Macintyre's theorem to a future version of the paper.

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

This paper addresses a fundamental question in Transformer theory: If we allow Transformers to operate with infinite numerical precision, arbitrary real-valued weights, and multiple layers of softmax attention, are there still mathematical limits to what they can express?

The authors show that the answer is yes. More importantly, they establish rigorous expressivity limitations without relying on unproven computational complexity conjectures.

Critical strengths

The nontrivial VC-dimension bounds without relying on finite-precision assumptions or unproven complexity-theoretic conjectures are very surprising, and I find the use of real geometry particularly interesting. The consequences of the main results are also quite interesting. I particularly like the bit-indexing result, which shows that having access to infinite-precision real numbers does not mean a Transformer can extract arbitrary amounts of information from them. The paper also includes positive expressivity results, which help put the impossibility results into perspective and give a more complete picture of what these Transformers can and cannot express.

Critical weaknesses

The main inexpressibility result for symmetric functions is nonconstructive. It would be more convincing to identify an explicit, computable function that Transformers cannot express. As it stands, the practical implications of this result are somewhat unclear.

The gaps between the upper and lower bounds are quite large Ω(n)\Omega(n) versus O(n4)O(n^4) and O(n6)O(n^6). It is unclear how tight these bounds are, or whether the polynomial exponents mainly arise from the proof techniques rather than the actual expressive capacity of Transformers.

Questions for authors
  1. Regarding the nonconstructive inexpressibility result, is there any reason to believe that an explicit, computable symmetric function over six symbols could be shown to be inexpressible using your approach? Or is this a fundamental limitation of the VC-dimension argument?

  2. Do the authors have any intuition about how tight the O(n4)O(n^4) and O(n6)O(n^6) bounds are? In particular, to what extent do these exponents come from the geometric techniques rather than the inherent complexity of Transformers?

2 comments

Thank you very much for your review!

  1. Regarding the nonconstructive inexpressibility result, is there any reason to believe that an explicit, computable symmetric function over six symbols could be shown to be inexpressible using your approach? Or is this a fundamental limitation of the VC-dimension argument?

As discussed in Section 5.3, it has been pointed out by Chen et al. (2025) that an unconditional construction of such a function would entail a breakthrough in circuit complexity theory. So, at the moment we don't have a strong reason to believe that such a function exists.

  1. Do the authors have any intuition about how tight the O(n^4) and O(n^6) bounds are? In particular, to what extent do these exponents come from the geometric techniques rather than the inherent complexity of Transformers?

Our intuition is that the upper bounds are not tight, because Karpinski and Macintyre's theorem makes relatively few assumptions about the function in question. On the one hand, this suggests that exploiting more properties of transformers could yield a tighter upper bound; on the other hand, the paucity of assumptions means that our upper bound applies to many transformer variants.

Karpinski and Macintyre (1997) conjecture that the quadratic dependence on q (the number of exponentials) in Khovanskii's theorem could be tightened; this would tighten our bounds as well.

Thank you for the clear response. The connection to open problems in circuit complexity (Chen et al., 2025) is convincing, and I agree that exhibiting an explicit inexpressible function is beyond the scope of this paper. I would suggest briefly stating this in the paper, together with the remark that the upper bounds are likely not tight and would improve with sharper Khovanskii-type bounds. My concerns are addressed, and I maintain my positive assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.