Megadose The AI curve, compressed.

Optimal Autoregressive Chain-of-Thought Learning via Bagging

· ArXiv · AI/CL/LG ·
For binary tokens, the method reaches optimal sample complexity without depending on the length of the reasoning chain.

The algorithm trains generators to match chain-of-thought demonstrations on bootstrap samples, then combines their predictions by majority vote. Its binary-token guarantee depends on the generator class’s VC dimension, target error and confidence. For larger finite vocabularies, the bound uses Graph dimension and is optimal up to a logarithmic vocabulary-size factor. The ensemble size grows logarithmically with chain length, and the authors show it can be distilled into a single generator using additional unlabeled prompts.

ArXiv · AI/CL/LG's note

score 4

Categories: Research