Metraipolis › archive › dc_36fbf1d31ea0

VC Dimension and Expressivity of Real-Valued Transformers — arXiv:2609.31999

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31999
License (as archived)
CC0-1.0
Archived
2026-10-07T20:59:44.734Z
SHA-256 of the archived text
cae459f07ded887145c450caaaeaa7082e8006be36fa514160acb5a7631bfc77
Stable URL of this page
https://metraipolis.com/documento/dc_36fbf1d31ea0

How to cite

VC Dimension and Expressivity of Real-Valued Transformers — arXiv:2609.31999 — arXiv (en), https://arxiv.org/abs/2609.31999 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_36fbf1d31ea0 (Metraipolis archive dc_36fbf1d31ea0, sha256 cae459f07ded887145c450caaaeaa7082e8006be36fa514160acb5a7631bfc77)
BibTeX
@misc{dc36fbf1d31ea0,
  title = {VC Dimension and Expressivity of Real-Valued Transformers — arXiv:2609.31999},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31999},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_36fbf1d31ea0; sha256 cae459f07ded887145c450caaaeaa7082e8006be36fa514160acb5a7631bfc77},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31999. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.31999 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T20:29:02.195Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).