We study how to learn an autoregressive next-token generator from a class , given chain-of-thought (CoT) demonstrations of length generated by . 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 , independent of the CoT length , where is the VC dimension of . For finite token sets , the VC dimension is replaced by a multiclass analogue, the Graph dimension , and the sample complexity is optimal up to a factor. The number of generators in the majority-vote ensemble is , and we show that the ensemble can be distilled into a single generator in at the expense of unlabeled prompts.
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.
Abstract
Related
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.
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}
}