mlsanityData to 14 Oct 2026

Tight Sample Complexity of Transformers

arXiv 2606.09731 ↗First posted 8 Jun 2026cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We tightly characterize the VC dimension of depth-L Transformers with a total of W parameters, mapping an input sequence of length T to a single output, establishing an upper bound of O(L W log (T W)) and a nearly matching lower bound of Omega(L W log (T W / L)). We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity Oleft(L W log left(left(T+Tprimeright) Wright)right) and that any learning rule that uses chain-of-thought data requires at least Omegaleft(L W log left(left(T+Tprimeright) W / Lright)right) examples, where T is the input length and Tprime is the number of autoregressive steps.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 14 of its 29 references that are in the map. First posted on arXiv 8 Jun 2026.

Builds on

14 of 29 references.

References · 14

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020GLU Variants Improve Transformercited by 1,804
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
  5. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  7. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  8. 2022Transformers Learn Shortcuts to Automatacited by 268
  9. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  10. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  11. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  12. 2025PENCIL: Long Thoughts with Short Memorycited by 33
2 more
  1. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 29
  2. 2022An Analysis of Attention via the Lens of Exchangeability and Latent Variable Modelscited by 16

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Eracited by 0
  2. 2026VC Dimension and Expressivity of Real-Valued Transformerscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
  2. 2026Finite-Time Analysis of Gradient Descent for Shallow Transformers
  3. 2026A Sharper Picture of Generalization in Transformers
  4. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  5. 2025Exact Expressive Power of Transformers with Padding
  6. 2026Transformers Provably Learn to Internalize Chain-of-Thought
  7. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought
  8. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)