Skip to content

VC Dimension and Expressivity of Real-Valued Transformers

Sep 2026 · 0 citations · 24 references
Computer Science

TL;DR

This work studies softmax-attention, multi-layer transformers operating on real values, with very few additional assumptions, and proves limitations on how many bits of a real number a transformer can access.

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 ($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.

View source

Similar papers

#artificial intelligence Preprint Oct 2026

Exact-Solution Volume and Length Generalization in Transformers

Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter regi...

Y. Zhu, David Chiang · 0 citations
#machine learning Preprint Oct 2026

Stability of Measure-to-Measure Transformers on Sub-Gaussian Data

Transformers have exhibited impressive empirical success across various domains, but their theoretical foundations remain less developed. This work constitutes a mathematical study of the measure-to-measure operators defined by transformers. We show that transformers map sub-Gaussian inputs to sub-Gaussian outputs; thi...

Frank Cole, N. Nelsen, Takashi Furuya · 1 citation
#machine learning Preprint Sep 2026

Universality and Generalization of Causal Transformers Across Context Lengths

This work studies whether one masked transformer can approximate causal token-to-token maps uniformly over sequences of arbitrary length sampling a fixed normalized horizon, and characterizes the causal families admitting uniform approximation on these compact input classes by a single transformer with length-independe...

Takashi Furuya, Maarten V. de Hoop, Gabriel Peyré · 0 citations
Open access Oct 2026

Bounds on the realizations of zero-nonzero patterns and sign conditions of polynomials restricted to varieties and applications

Abstract We obtain upper bounds, independent of the ambient dimension, for the number of realizable zero-nonzero patterns and (over ordered fields) sign conditions of a finite family of polynomials P $\mathcal P$ script upper P restricted to an algebraic subset V of affine or projective space. The bounds depend only...

Saugata Basu, L. Parida · 0 citations
Preprint Oct 2026

High-Arity Rademacher Complexity and Uniform Laws of Large Numbers

We characterize several properties of higher-arity function classes, specifically finite $\VC_k$-dimension, slicewise finite $\VC$-dimension, and finite slicewise Littlestone dimension, in terms of generalizations of Rademacher complexity. These characterizations sets up simple new proofs of several results on finite $...

A. Anderson, Henry Towsner · 0 citations
Preprint Sep 2026

Irreducible polynomials with restricted digits in base $b(T)$

We study monic irreducible polynomials over $\mathbb{F}_q[T]$ whose non-leading digits, with respect to an arbitrary polynomial base $b(T)$, avoid a prescribed set of forbidden digits. Identifying the digit set with the ring $D=\mathbb{F}_q[T]/(b)$, we obtain an asymptotic formula for the number of such irreducible pol...

J. Arévalo, Matilde Lal'in · 0 citations

Related blog posts

MIT News · Artificial Intelligence Sep 29, 2026

Who we become when we talk to machines

Professor Sherry Turkle’s new book, “Artificial Intimacy,” offers a withering critique of chatbots and the antisocial dynamics she believes they encourage.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.