Optimal Autoregressive Chain-of-Thought Learning via Bagging

Optimal, length-independent sample complexity for learning from chain-of-thought demonstrations, achieved by a simple and efficient algorithm based on bagging.

arXiv (opens in new tab)

Abstract

We study how to learn an autoregressive next-token generator f ⁣:Σ⋆→Σf\colon\Sigma^\star\to\Sigma from a class F\mathcal{F}, given chain-of-thought (CoT) demonstrations of length TT generated by ff. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of O((dVC+log⁡(1/δ))/ε)O((d_{\mathrm{VC}}+\log(1/\delta))/\varepsilon), independent of the CoT length TT, where dVCd_{\mathrm{VC}} is the VC dimension of F\mathcal{F}. For finite token sets Σ\Sigma, the VC dimension is replaced by a multiclass analogue, the Graph dimension dGd_{\mathrm{G}}, and the sample complexity is optimal up to a log⁡∣Σ∣\log|\Sigma| factor. The number of generators in the majority-vote ensemble is O(log⁡(T/δ))O(\log(T/\delta)), and we show that the ensemble can be distilled into a single generator in F\mathcal{F} at the expense of nlog⁡(nT)n\log(nT) unlabeled prompts.

Related
PaperAbstractThis page

Optimal Autoregressive Chain-of-Thought Learning via Bagging

reasoninglanguage modelslearning theory

Optimal, length-independent sample complexity for learning from chain-of-thought demonstrations, achieved by a simple and efficient algorithm based on bagging.

Cite
@misc{altabaa2026optimalcot,
  author = {Altabaa, Awni and Lafferty, John and Montasser, Omar},
  title = {Optimal Autoregressive Chain-of-Thought Learning via Bagging},
  year = {2026},
  url = {https://arxiv.org/abs/2611.21597},
  eprint = {2611.21597},
  archivePrefix = {arXiv},
  primaryClass = {cs.LG}
}