# VC Dimension and Expressivity of Real-Valued Transformers

arXiv: https://arxiv.org/abs/2609.31999 · HTML: https://mlsanity.com/paper/2609.31999/

## 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 (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [Simulating Hard Attention Using Soft Attention](https://mlsanity.com/paper/2412.09925/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [Sharper Generalization Bounds for Transformer](https://mlsanity.com/paper/2603.21541/) (2026)
- [Tight Sample Complexity of Transformers](https://mlsanity.com/paper/2606.09731/) (2026)
- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)

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