Source-linked AI summary
VC Dimension and Expressivity of Real-Valued Transformers
Gavin Dooley, Andy Yang, Yijia Jessica Zhu, David Chiang, Peter Cholak, Anand Pillay
TL;DR
Earlier work often restricted transformer attention, precision, or depth, leaving limitations for multi-layer infinite-precision transformers unresolved. This paper applies real-geometry methods to real-valued softmax-attention transformers and proves VC-dimension bounds. It also identifies limits on symmetric-function expressivity and access to real-number bits.
Problem
Previous results on transformer abilities and limitations imposed restrictions such as hard attention, bounded numerical precision, or limited depth, while inexpressibility tasks for multi-layer infinite-precision transformers remained an open problem.
Source: §1 · p. 2Method
The paper applies real-geometry results directly to multi-layer softmax-attention transformers operating on real values to bound their VC and split VC dimensions.
Source: §1 · p. 2Results
VC dimension is O(n4) and split VC dimension is O(n6); some six-symbol symmetric functions are inexpressible, and access to the k-th input-number bit is impossible when k ∈ ω(n4).
Source: §1 · p. 2Takeaways & Limitations
The results rule out using real numbers as data structures that store unbounded information for transformer computation.
Source: §5.3 · p. 8The VC and split VC upper and lower bounds have gaps, and closing similar gaps for RNNs remains an open problem.
Source: §8 · p. 9
Abstract
from arXiv · showhide
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(n^4)$ and $O(n^6)$, 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.
1 INTRODUCTION
Prior transformer results often restrict attention, precision, or depth; this paper studies real-valued, multi-layer softmax-attention transformers and establishes both expressivity limits and positive expressivity results.
1 INTRODUCTION
- Earlier transformer studies restricted attention type, numerical precision, or layer count, while some limitations relied on complexity-theoretic conjectures.The paper notes that finding an inexpressible task for multi-layer infinite-precision transformers had remained open.Source: §1 · pp. 1–2
- The paper’s real-geometry approach extends prior VC-dimension methods beyond settings where transformers can be simulated by feedforward networks.The authors apply the general Karpinski–Macintyre theorem, whose use requires additional technical work.Source: §1 · p. 2
- VC dimension is O(n4) and split VC dimension is O(n6) for multi-layer softmax-attention transformers, using a general real-geometry bound.The approach applies Karpinski and Macintyre’s theorem directly because general transformers cannot be simulated by feedforward networks for this purpose.Source: §1 · p. 2
- Some symmetric functions over six-symbol alphabets are inexpressible, and transformers cannot extract the k-th input-number bit when k ∈ ω(n4).These results limit how much an idealized real-valued transformer can use its infinite precision.Source: §1 · p. 2
- Transformers can express every symmetric function over a two-symbol alphabet with function-specific positional encodings, and a one-layer transformer can retrieve a queried input bit.The examples also provide lower bounds for untrained-transformer VC dimension and trained-transformer split VC dimension.Source: §1 · p. 2
2 BACKGROUND
The background introduces asymptotic and VC-dimension notation, reviews geometric methods for bounding VC dimension, and specifies the transformer setting to which the paper’s results apply.
2.1 NOTATION
- The paper uses O, Ω, ω, and soft-O notation for asymptotic growth, with transformer-dependent constants indicated by O_T.It writes [n] for {1, …, n} and uses base-2 logarithms.Source: §2.1 · pp. 2–3
2.2 PREVIOUS RESULTS ON VC DIMENSION
- VC dimension measures the largest set shattered by a family, and Karpinski–Macintyre bound it using connected-component bounds for smooth-function families.Their framework, together with Khovanskiĭ’s bounds for exponential–linear polynomials, underlies the paper’s transformer analysis.Source: §2.2 · p. 3
2.3 TRANSFORMERS
- The paper follows a standard transformer definition and its main results are independent of details such as masking, normalization, residual connections, and positional encodings.Results hold with or without word or position embeddings, whether fixed or parameterized; an untrained transformer has unspecified learnable parameters, while a trained one fixes them.Source: §2.3 · p. 4
- For each input length n, an untrained transformer’s parameter settings define a family of accepted-input sets whose VC dimension is bounded in the main results.Acceptance is determined by whether the final output is positive.Source: §2.3 · p. 4
3 MAIN RESULTS
The main results bound transformer VC dimension by O(n4) and split VC dimension by O(n6), using real-geometry methods; the section also relates split VC dimension to finite-alphabet languages.
3.1 VC DIMENSION OF TRANSFORMERS
- An untrained transformer’s VC dimension is O(n4).The proof converts the acceptance condition into a Boolean combination of smooth inequalities, then bounds connected components after introducing variables to handle square roots, division, and exponential arguments.Source: §3.1 · pp. 4–5
3.2 INPUTS AS PARAMETERS
- For a trained transformer and a partition K of input positions, the relevant VC dimension is O(n4 · |K|2), yielding an O(n6) split VC-dimension bound.The proof treats vectors at positions in K as parameters; split VC dimension maximizes over such partitions.Source: §3.2 · p. 5
- For any finite alphabet Σ and language L, Split-VC(L(n)) is at most n log |Σ|.Because this bound is asymptotically below the transformer split-VC bound, the authors look beyond finite-alphabet languages for inexpressibility examples, including real-number bit access.Source: §3.2 · p. 5
4 SYMMETRIC FUNCTIONS
Here, symmetric functions depend only on symbol counts. The section shows unary uniform expressivity, binary expressivity with length-dependent positional encodings, and six-symbol non-expressibility even for non-uniform transformers.
4 SYMMETRIC FUNCTIONS
- A symmetric language is determined by symbol counts: strings with the same count of each symbol share membership.The paper also calls such functions permutation equivariant or permutation invariant.Source: §4 · p. 6
4.1 NON-EXPRESSIBLE FUNCTIONS
- Some symmetric functions over six symbols are inexpressible even for non-uniform transformers, although the functions guaranteed to be inexpressible need not be computable.The result applies even when transformer parameters and encoding functions vary with input length, including uncomputably.Source: §4.1 · p. 6
4.2 ALPHABET OF SIZE 1
- Every family of symmetric functions over a one-symbol alphabet can be expressed by one trained transformer uniformly across input lengths.The same trained transformer, including its word and position embeddings, is used at every length.Source: §4.2 · p. 6
4.3 ALPHABET OF SIZE 2
- Every symmetric function over a two-symbol alphabet can be expressed by a trained transformer using a positional encoding that may depend on input length.If the function is uncomputable, the positional encoding in this construction is also uncomputable.Source: §4.3 · p. 6
4.4 EXPRESSING AN UNCOMPUTABLE FUNCTION USING REAL WEIGHTS
- A transformer recognizes the computably enumerable but noncomputable language whose fraction of 1s is below Chaitin’s Ω.The construction uses real weights with a computable positional encoding.Source: §4.4 · p. 6
5 BIT INDEXING
The section studies whether transformers can retrieve a specified bit of a real number, with the number and bit index encoded in the input or the index fixed in advance. It establishes growth-rate limits on both forms of access and discusses their scope.
5.1 DYNAMIC BIT INDEXING
- If ℓ(n) grows faster than n^4(p(n))^2, no transformer solves the p-partitioned ℓ-bit index task for all sufficiently large input lengths.The task permits arbitrary surjective encodings of the real number and index in separate input blocks.Source: §5.1 · p. 7
5.2 STATIC BIT INDEXING
- If b(n) grows faster than n^4, no trained transformer can retrieve that bit of a real number supplied directly as the first input coordinate for all sufficiently large lengths.This remains true even when the bit index is hard-coded into the transformer rather than supplied as input.Source: §5.2 · p. 7
5.3 DISCUSSION
- Infinite precision does not provide unbounded data storage; the results cover specified operations that exclude rounding, and the bit-indexing languages require alphabets growing with ℓ(n).The discussion notes that real-world models are trained at higher precision and quantized to lower precision without catastrophic loss of accuracy.Source: §5.3 · p. 8
6 POSITIONAL INDEXING
Positional indexing asks a transformer to return the bit at a queried position in a binary sequence. The section uses this task to establish a split VC dimension lower bound and gives a one-layer construction.
6 POSITIONAL INDEXING
- n−1 positions can be shattered, yielding an Ω(n) lower bound on the split VC dimension.The queried position is treated as a parameter, and the input bits determine membership in the shattered set.Source: §6 · p. 8
- A one-layer transformer recognizes positional indexing by assigning the queried position the highest attention score and retrieving its bit.The attention output at the last position is made positive exactly when the selected bit is 1.Source: §6 · p. 8
- This task differs from the one-layer impossibility result of Kozachinskiy et al. (2025), which reads its output at an appended blank token.Here, the query is part of the input and the output is read at the last input position.Source: §6 · pp. 8–9
7 GENERALIZATION BOUNDS
The VC dimension bounds yield generalization bounds for multi-layer real-valued SMATs. The paper compares these bounds with prior results and identifies conditions under which its bound is asymptotically stronger.
7 GENERALIZATION BOUNDS
- The VC dimension result gives a generalization error bound of ˜O(n^2/N) for multi-layer real-valued SMATs, where N is training-set size.The bound is derived using Thm. 3.1.Source: §7 · p. 9
- The bound is asymptotically stronger than cited covering-number bounds when input-norm bounds grow sufficiently fast with n, and stronger than Li et al. (2026) when distribution parameters grow sufficiently fast or no input-distribution assumptions are available.The compared prior bounds depend on input norms or assumptions about the input distributions.Source: §7 · p. 9
8 FUTURE RESEARCH
The paper leaves gaps between its VC-dimension upper and lower bounds and identifies practical testing of its theoretical results as future work.
8 FUTURE RESEARCH
- The VC-dimension upper and lower bounds remain separated; closing the gaps is desirable but similar gaps for RNNs remain an open problem.The authors report that the analogous RNN problem is still open to their knowledge.Source: §8 · p. 9
- Experiments on learning symmetric or indexing functions, or accessing particular real-number bits, could clarify the practical implications of the theory.Source: §8 · p. 9
- The paper does not report such experiments, identifying them as a direction for further research.Source: §8 · p. 9
USE OF ARTIFICIAL INTELLIGENCE
The appendix records the use of AI in literature review and writing, defines the transformer components and embeddings used, and introduces topology concepts used in the paper’s background.
USE OF ARTIFICIAL INTELLIGENCE
- AI was used to review literature and polish writing, but not to generate proofs.Source: USE OF ARTIFICIAL INTELLIGENCE · p. 9
A DEFINITION OF TRANSFORMERS
- The transformer definition specifies attention heads, multi-head attention, layer normalization, feed-forward networks, layers, embeddings, and an output layer.Transformers are treated as binary classifiers, and discrete-input transformers combine a real-input transformer with an embedding.Source: A DEFINITION OF TRANSFORMERS · pp. 12–13
B BACKGROUND ON SUBMANIFOLDS OF Rn
- The background defines submanifolds and regular values, then states the regular level set theorem and Sard’s theorem for smooth maps between submanifolds.It also defines measure zero in a submanifold.Source: B BACKGROUND ON SUBMANIFOLDS OF Rn · pp. 13–14
C PROOF OF THM. 3.1
The proof adapts real-geometry bounds to transformers by representing their computation with smooth formulas and bounding connected components, yielding an O(n^4) VC-dimension bound.
C PROOF OF THM. 3.1
- The proof treats the transformer output as a parameterized function and applies a VC-dimension theorem to its expression over inputs and parameters.The output expression is not smooth because the feed-forward network uses max, motivating the piecewise-smooth rewrite.Source: C PROOF OF THM. 3.1 · p. 14
- Softmax and layer-normalization operations are encoded with new variables and equations so exponential–linear polynomial bounds can control connected components.The resulting system has O(n^2) exponentials, giving log B in O(n^4).Source: C PROOF OF THM. 3.1 · p. 15
- O(n^4) bounds the VC dimension by rewriting the transformer’s max operations as a Boolean combination of smooth inequalities and applying real-geometry bounds.The proof inductively branches on the signs of max inputs to form smooth expressions.Source: C PROOF OF THM. 3.1 · pp. 14–15
D TRANSFORMERS COMPUTING SYMMETRIC FUNCTIONS
The constructions use positional encodings to express symmetric functions over unary and binary alphabets, and a one-layer transformer to recognize a language defined by a density threshold.
D TRANSFORMERS COMPUTING SYMMETRIC FUNCTIONS
- A single trained transformer works uniformly across input lengths for any family of symmetric functions over a one-symbol alphabet, using a positional encoding that stores the desired output.Attention retrieves the encoding’s final coordinate at the last position.Source: D TRANSFORMERS COMPUTING SYMMETRIC… · p. 16
- For any symmetric binary-alphabet function, the same learned parameters can be paired with a function-specific positional encoding to compute it.The encoding stores the function of the number of 1s; the construction’s positional encoding depends on input length.Source: D TRANSFORMERS COMPUTING SYMMETRIC… · p. 16
- A one-layer transformer with uniform attention accepts exactly strings whose fraction of 1s is below Ω.Source: D TRANSFORMERS COMPUTING SYMMETRIC… · p. 16
E PROOF OF PROP. 5.4
The proof bounds the positive-output set of a fixed transformer by 2^O(n^4) connected components, then uses output alternation to bound the bit index by O_T(n^4).
E PROOF OF PROP. 5.4
- Extracting a deeper bit requires the output to alternate increasingly many times as x varies, so the proof bounds connected components of the positive-output set.For fixed transformer parameters and sequence v, that set has 2^O(n^4) connected components.Source: E PROOF OF PROP. 5.4 · p. 16
- The transformer computation is rewritten as an equivalent system of exponential–linear polynomial equations by eliminating roots, divisions, max operations, and inequalities.The representation uses O(n^2) variables, constraints, and exponential terms, with polynomial degrees bounded by O(1).Source: E PROOF OF PROP. 5.4 · pp. 16–17
- Because the equation system may define a nonsmooth set, the proof constructs a nearby regular level set to apply the connected-component bound.A slack variable restricts the variables to a closed ball; a regular value then preserves points in the selected components while excluding intermediate x values.Source: E PROOF OF PROP. 5.4 · pp. 17–18
- b(n) ∈ O_T(n^4) for any transformer solving the b(n)-th-bit index task.The proof derives this from a connected-component bound and the alternations required to extract deeper bits.Source: E PROOF OF PROP. 5.4 · pp. 16, 18