The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule \mathtt{halt} and every pointwise \mathtt{halt}-halting local class H, n_{PAC}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(H))=O((\operatorname{DSdim}(H)+\log(1/δ))/\varepsilon), with no dependence on rollout length. The dependence on \operatorname{DSdim}(H) is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of H. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.