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 $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,\delta}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/\delta))/\varepsilon)$, with no dependence on rollout length.

The dependence on $\operatorname{DSdim}(\mathrm{H})$ is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of $\mathrm{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.