The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Zhiyuan Li
cs.LG, stat.ML
Submitted: 2026-07-08
Comments: 33 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification
- A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
- An Optimal Sauer Lemma Over $k$-ary Alphabets
- The Optimal Sample Complexity of Multiclass and List Learning
- Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
- Show Your Work: Scratchpads for Intermediate Computation with Language Models
- Self-Consistency Improves Chain of Thought Reasoning in Language Models
- The Expressive Power of Transformers with Chain of Thought
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
- PENCIL: Long Thoughts with Short Memory
- Recursive Models for Long-Horizon Reasoning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks