Tight Sample Complexity of Transformers

2026/06/08 by Chenxiao Yang, Nathan Srebro, Zhiyuan Li
#cs.LG

paper · pdf

Abstract

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 Ω(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 O(L W log ((T+T^′) W)) and that any learning rule that uses chain-of-thought data requires at least Ω(L W log ((T+T^′) W / L)) examples, where T is the input length and T^′ is the number of autoregressive steps.

Related

• The Expressive Power of Transformers with Chain of Thought
• Transformers Learn Shortcuts to Automata
• Exact Expressive Power of Transformers with Padding
• Transformers know more than they can tell -- Learning the Collatz sequence
• Transformers Provably Solve Parity Efficiently with Chain of Thought