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

This paper explores the sample complexity of autoregressive models, specifically comparing Chain-of-Thought (CoT) supervision against End-to-End (e2e) learning. The researchers demonstrate that while e2e learning exhibits a diverse range of growth rates where the required data can scale linearly with reasoning length, CoT supervision effectively eliminates this dependence. By providing intermediate reasoning steps, the sample complexity becomes independent of the generation length, making the learning process significantly more efficient. The authors introduce the autoregressive tree dimension to provide a more refined condition for logarithmic growth in e2e settings, surpassing previous benchmarks like the Littlestone dimension. Ultimately, the paper provides a nearly complete taxonomy of how supervision depth influences the learnability of next-token generators.