mlsanityData to 14 Oct 2026

VC Dimension and Expressivity of Real-Valued Transformers

arXiv 2609.31999 ↗First posted 25 Sep 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

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 (O(n4) and O(n6), respectively, where n is the input length). Conversely, we also construct specific transformers witnessing lower bounds on these quantities (Omega(n) 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 14 of its 24 references that are in the map. First posted on arXiv 25 Sep 2026.

Builds on

14 of 24 references.

References · 14

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  3. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  4. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  5. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  6. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  7. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  8. 2024Theoretical limitations of multi-layer Transformercited by 45
  9. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 29
  10. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  11. 2025Strassen Attention, Split VC Dimension and Compositionality in Transformerscited by 12
  12. 2026Sharper Generalization Bounds for Transformercited by 3
2 more
  1. 2026Tight Sample Complexity of Transformerscited by 2
  2. 2026Indexing: the Beginning and the Endcited by 2

Built on by

Not cited yet.