Research map / Large language models / Reasoning and chain of thought
CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops a statistical learning theory for chain-of-thought supervision, introducing a CoT information measure that links CoT risk and end-to-end risk to give sample complexity d/CoT-info(ε) in the realizable setting, with matching-style lower bounds and DFA/linear-threshold simulations.
Problem
Standard PAC theory does not explain the statistical advantage of chain-of-thought supervision, because the training loss (CoT risk) differs from the test metric (end-to-end risk), so existing analyses give only 1/ε rates.
Approach
Introduces CoT information, the minimal negative log-probability that a hypothesis agreeing with the reference on both CoT and output disagrees with it end-to-end by more than ε; this directly links the two risks and yields sample complexity scaling as d/CoT-info(ε) instead of d/ε.
Key results
- For a finite class under CoT consistency, sample complexity is (log|H| + log(1/δ)) / CoT-info(ε), which is faster than log|H|/ε when CoT is informative.
- In DFA simulations with n=10, the limit of CoT-info/ε+ is roughly 600, and empirical sample efficiency gains of 10^2–10^3 were observed.
- For iterated linear thresholds (d=8, T=16), the CoT-info ratio is about 6 and roughly 5-fold empirical sample complexity improvement was seen for CoT consistency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CoT supervision instead of E2E supervision | CoT consistency learning on finite hypothesis classes · Realizable finite hypothesis classes | sample complexity: log |H| / ε -> (log |H| + log (1 / δ)) / CoT information(ε; H) | Helped |
| use CoT supervision instead of E2E supervision | DFA learning with CoT consistency · DFA simulation, zero target error | sample efficiency: roughly 600 | Helped |
| use CoT supervision instead of E2E supervision | DFA learning with CoT consistency · DFA simulation | sample efficiency: 10^2--10^3 | Helped |
| use CoT supervision instead of E2E supervision | Iterated linear-threshold learning with CoT consistency · Iterated linear thresholds, smallest target error levels | sample complexity: roughly 5-fold | Helped |
| increase input sequence length | DFA CoT supervision · DFA simulation | CoT information relative to ε | Helped |
| reveal more of the state trajectory in the CoT (ablation) | DFA CoT supervision · DFA simulation, varying detail level T | CoT information | Helped |
| increase the CoT trajectory detail level T (ablation) | DFA CoT supervision · DFA simulation, varying detail level T | CoT information relative to ε | Mixed |
| use CoT-ERM rather than E2E-ERM when the CoT component is not realizable but outputs are realizable | Agnostic CoT learning · Agnostic setting with a CoT-misaligned hypothesis class | end-to-end risk | Hurt |
Surprising findings
- In the agnostic setting, CoT supervision can hurt: CoT-ERM can provide no guarantee when the CoT class is misaligned with the data, while E2E-ERM succeeds.
Limitations
- Lower bounds established only for the realizable setting; agnostic lower bounds left open.
- Upper bounds use simple proper learning rules (CoT consistency, CoT-ERM) whose optimality is unknown.
- Analysis is for abstract hypothesis classes, not neural sequence models, and noise in CoT is only modeled in the Fano bound.
Experimental setup
Datasets: synthetic DFA and iterated linear threshold hypothesis classes
Metrics: end-to-end risk empirical sample complexity CoT information ratio to epsilon
Baselines: end-to-end ERM CoT risk bounding (VC of CoT loss class)
Builds on: PAC learning VC dimension Fano's inequality
Closest papers by meaning
- Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis (ICLR 2025 · similarity 0.91)
- CoT Vectors: Transferring and Probing the Reasoning Mechanisms of LLMs (ICLR 2026 · similarity 0.89)
- Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought (NeurIPS 2024 · similarity 0.89)
- How Does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding (AAAI 2026 · similarity 0.89)
- C3oT: Generating Shorter Chain-of-Thought Without Compromising Effectiveness (AAAI 2025 · similarity 0.89)
- Enhancing Chain of Thought Prompting in Large Language Models via Reasoning Patterns (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.