Reproduce “Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Steve Hanneke, Idan Mehalel, Shay Moran
Researchers from Purdue University, The Hebrew University, and Google Research formally analyze the sample complexity of autoregressive reasoning, distinguishing between End-to-End (E2E) and Chain-of-Thought (CoT) supervision. Their work demonstrates that CoT supervision eliminates the dependence of sample complexity on generation length, while E2E learning exhibits a range of T-dependent complexities, characterized by a novel Autoregressive Tree Dimension for logarithmic growth.
Key insights
- Chain-of-Thought (CoT) supervision can completely eliminate the dependence of sample complexity on the generation length T for base classes with finite VC dimension.
- End-to-End (E2E) learning can exhibit a rich and continuous spectrum of sample complexity growth rates, ranging from constant to linear in T, depending on the base class structure.
- The newly introduced Autoregressive Tree Dimension (ATdim) provides a strictly broader sufficient condition for logarithmic E2E sample complexity compared to existing measures like the Littlestone dimension.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.