Optimal Autoregressive Chain-of-Thought Learning via Bagging
Organizations: Department of Statistics and Data Science, Yale University
Abstract
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.
Figures & tables
| Reference | Sample Complexity | Alphabet | Learner |
|---|---|---|---|
| [ 40 ] | binary | CoT-consistent learner | |
| [ 34 ] | binary | sample-compression majority-vote | |
| [ 22 ] | arbitrary | online-to-batch conversion | |
| [ 46 ] | arbitrary | one-inclusion hypergraphs | |
| This work ( Theorem 1 ) | arbitrary | Bagging CoT-consistent predictors | |
| Lower bound [ 46 ] | arbitrary | any learner, already for |
Autoregressive Language Modeling
Autoregressive language modeling predicts sequences one step at a time, using prior tokens to generate text, speech, code, and other data.
See all 142 papers