Optimal Autoregressive Chain-of-Thought Learning via Bagging
Altabaa et al.
A majority vote of bootstrap-trained generators learns from chain-of-thought demonstrations with optimal sample complexity that does not depend on the length of the chain.
Source published · In the Daily Brief of 18 November 2026
Filed under Learning theory, Reasoning and inference
The paper asks how many chain-of-thought demonstrations are needed to learn an autoregressive next-token generator \(f\) from a class \(\mathcal{F}\), when each demonstration has length \(T\). The proposed algorithm trains generators that are consistent with the chains on bootstrap samples and outputs their majority vote.
For binary tokens it achieves the optimal sample complexity \(O((d_{\mathrm{VC}} + \log(1/\delta))/\epsilon)\), where \(d_{\mathrm{VC}}\) is the VC dimension of \(\mathcal{F}\), independent of \(T\). For finite token sets the Graph dimension replaces the VC dimension and the rate is optimal up to a \(\log|\Sigma|\) factor. The ensemble needs only \(O(\log(T/\delta))\) generators and can be distilled into a single member of \(\mathcal{F}\) using \(n\log(nT)\) unlabelled prompts.