Search papers, labs, and topics across Lattice.
This paper establishes that the sample complexity for learning autoregressive Chain-of-Thought traces is bounded by the multiclass rate defined by the Daniely鈥揝halev-Shwartz dimension, revealing that the sample complexity does not depend on rollout length. The authors introduce a new concept, parity dimension, which serves as a more stable refinement of DS dimension, ensuring that the sample complexity remains optimal even as the complexity of the task increases. This work highlights the critical relationship between stopping rules and sample complexity, providing a theoretical foundation for improving learning efficiency in autoregressive models.
Autoregressive Chain-of-Thought learning can achieve optimal sample complexity without being hindered by rollout length, thanks to a new stability measure called parity dimension.
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,未}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/未))/\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.
