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

arXiv:2607.07423v1 Announce Type: new Abstract: 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}^{arepsilon,elta}(operatorname{Roll}_{mathtt{halt}}(H))=O((operatorname{DSdim}(H)+log(1/elta))/arepsilon), 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.

Source: arXiv cs.LG | 2026-07-09