Research map / Large language models / Reasoning and chain of thought
From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency
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.
Shows theoretically and empirically that chain-of-thought improves transformer sample efficiency on parity learning (polynomial vs. exponential samples) by introducing sparse sequential dependencies that induce sparse, interpretable attention.
Problem
Why chain-of-thought helps LLM reasoning is unclear; prior theory attributes it to expressiveness, but expressiveness is not the bottleneck for simple tasks. The paper asks how CoT affects sample complexity of learning.
Approach
Frame CoT as introducing sparse sequential dependencies among tokens; with CoT a one-layer transformer learns parity with polynomial samples and its attention becomes one-hot on the secret indices, while without CoT learning requires exponential samples under bounded memory SGD.
Key results
- Without CoT, sample complexity grows exponentially in k; with CoT it grows approximately linearly in k (n=100, k up to 100), while no-CoT training exceeds the 10^7 budget for k>=4 in one-pass training.
- With CoT, a 1-layer 1-head transformer's attention becomes one-hot on the secret indices (theory: error below 1/n^8).
- On GSM8K, Qwen2-7B shows lower normalized attention entropy with CoT data than with No-CoT data, and Qwen2-Math-7B (fine-tuned on CoT) is sparser still.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add step-by-step CoT examples | Transformer parity learning · Parity (n,k) | sample complexity: 2^{\Omega(k)} without CoT; \Tilde O(n) with CoT | Helped |
| add CoT training data | GPT-2-style Transformers · Parity (n=30, k=1,2,3,4) | sample complexity | Helped |
| use multi-pass training instead of one-pass training | Transformer without CoT · Parity (n=20, k=6) | evaluation accuracy | Helped |
| add CoT training data rather than multi-pass no-CoT training | Transformer parity learning · Parity (n=20, k=6) | epochs to perfect accuracy: 5 epochs | Helped |
| increase the number of heads rather than the number of layers | Transformer trained without CoT · Parity (n=20, k=6) | evaluation accuracy | Helped |
| use CoT-formatted GSM8K data instead of final-answer-only data | Pretrained Qwen2-7B · GSM8K | normalized attention entropy | Helped |
| fine-tune on CoT data | Qwen2-7B · GSM8K with CoT | normalized attention entropy | Helped |
| train on 1000000 samples rather than 50000 samples | 4-layer 4-head Transformer without CoT · Parity (n=20, k=6) | evaluation accuracy | Hurt |
Surprising findings
- Multi-pass no-CoT training on a 1M-sample set failed to learn parity even though a 50k-sample set succeeded, with attention entropy staying high in the failure case.
Limitations
- Theory covers only the parity function and assumes each CoT token depends on exactly one previous token.
- Lower bound applies only to constant-pass SGD with bounded memory; multi-pass no-CoT training is studied empirically only.
- Real-world evidence is indirect, using attention entropy of pretrained models on GSM8K rather than measuring sequential dependence directly.
Experimental setup
Datasets: GSM8K synthetic parity data
Benchmarks: GSM8K synthetic parity problems
Metrics: sample complexity evaluation accuracy normalized attention entropy
Baselines: No-CoT training Qwen2-Math-7B
Builds on: GPT-2 DenseNet branching program memory-bounded learning lower bounds
Closest papers by meaning
- Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis (ICLR 2025 · similarity 0.91)
- How Does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding (AAAI 2026 · similarity 0.91)
- Don't Take Things Out of Context: Attention Intervention for Enhancing Chain-of-Thought Reasoning in Large Language Models (ICLR 2025 · similarity 0.90)
- Eliciting Chain-of-Thought in Base LLMs via Gradient-Based Representation Optimization (AAAI 2026 · similarity 0.89)
- Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropy (ICLR 2026 · similarity 0.89)
- Towards Efficient Large Language Reasoning Models via Extreme-Ratio Chain-of-Thought Compression (ICML 2026 · 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.