Bagging technique optimizes learning of chain-of-thought token prediction

Optimal Autoregressive Chain-of-Thought Learning via Bagging

Machine Learning

Summary

This paper studies how to efficiently learn a step-by-step text generator that predicts the next word given previous words. The researchers propose a simple approach that trains multiple models on different random samples of training data and combines their outputs by voting. This method achieves the best possible sample efficiency even when the step-by-step reasoning sequences are long. They also show how to compress the multiple models into a single model using additional unlabeled examples. This work helps improve learning for systems that generate reasoning or explanations token-by-token.

What this means in practice

  • For machine learning engineers: Use bagging-based ensembles to train next-token predictors that efficiently learn from chain-of-thought examples without sample size growing with reasoning length.
  • For natural language processing teams: Implement single-model distillation from ensemble learners to maintain performance while reducing model complexity in autoregressive natural language generators.

A theory result. No direct application yet.

Authors

Awni Altabaa, John Lafferty, Omar Montasser

Abstract

We study how to learn an autoregressive next-token generator $f\colonΣ^\star\toΣ$ from a class $\mathcal{F}$, given chain-of-thought (CoT) demonstrations of length $T$ generated by $f$. 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((d_{\mathrm{VC}}+\log(1/δ))/ε)$, independent of the CoT length $T$, where $d_{\mathrm{VC}}$ is the VC dimension of $\mathcal{F}$. For finite token sets $Σ$, the VC dimension is replaced by a multiclass analogue, the Graph dimension $d_{\mathrm{G}}$, and the sample complexity is optimal up to a $\log|Σ|$ factor. The number of generators in the majority-vote ensemble is $O(\log(T/δ))$, and we show that the ensemble can be distilled into a single generator in $\mathcal{F}$ at the expense of $n\log(nT)$ unlabeled prompts.