cs.LGNov 16, 2026

Optimal Autoregressive Chain-of-Thought Learning via Bagging

Authors: Awni Altabaa, John Lafferty, Omar Montasser

Organizations: Department of Statistics and Data Science, Yale University

Abstract

We study how to learn an autoregressive next-token generator f ⁣:Σ⋆→Σf\colonΣ^\star\toΣ 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/δ))/ε), independent of the CoT length TT, where dVCd_{\mathrm{VC}} is the VC dimension of F\mathcal{F}. For finite token sets ΣΣ, 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|Σ| factor. The number of generators in the majority-vote ensemble is O(log⁡(T/δ))O(\log(T/δ)), 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.

Figures & tables

Explore similar work

CardsList
  1. Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

    Apr 13, 2026Steve Hanneke, Idan Mehalel, Shay MoranCoT SupervisionSample Complexity

  2. Stochastic Autoregressive Learning

    Aug 7, 2026Ilan Doron-Arad, Idan Mehalel, Elchanan MosselAutoregressive GenerationPAC Learning