mlsanityData to 14 Oct 2026

From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency

arXiv 2410.05459 ↗First posted 7 Oct 2024cs.LG cs.CL stat.MLcited by 29

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Chain-of-thought (CoT) significantly enhances the reasoning performance of large language models (LLM). While current theoretical studies often attribute this improvement to increased expressiveness and computational capacity, we argue that expressiveness is not the primary limitation in the LLM regime, as current large models will fail on simple tasks. Using a parity-learning setup, we demonstrate that CoT can substantially improve sample efficiency even when the representation power is sufficient. Specifically, with CoT, a transformer can learn the function within polynomial samples, whereas without CoT, the required sample size is exponential. Additionally, we show that CoT simplifies the learning process by introducing sparse sequential dependencies among input tokens, and leads to a sparse and interpretable attention. We validate our theoretical analysis with both synthetic and real-world experiments, confirming that sparsity in attention layers is a key factor of the improvement induced by CoT.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 40 of its 79 references that are in the map. First posted on arXiv 7 Oct 2024.

Builds on

40 of 79 references.

Closest ancestors · 13

Same direction, newest first

  1. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods25 Aug
  2. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning20 Jun
  3. 2024Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanism24 May
  4. 2024How to think step-by-step: A mechanistic understanding of chain-of-thought reasoning28 Feb
  5. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  6. 2024Chain-of-Thought Reasoning Without Prompting15 Feb
  7. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  8. 2023Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learning30 May
  9. 2023The CoT Collection: Improving Zero-shot and Few-shot Learning of Language Models via Chain-of-Thought Fine-Tuning23 May
  10. 2023Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models6 May
  11. 2023Why think step by step? Reasoning emerges from the locality of experience7 Apr
  12. 2022Automatic Chain of Thought Prompting in Large Language Models7 Oct
1 more
  1. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Models21 May

Other references · 27

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  3. 2020Scaling Laws for Neural Language Modelscited by 6,586
  4. 2024Qwen2 Technical Reportcited by 2,120
  5. 2023MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Modelscited by 735
  6. 2023MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuningcited by 487
  7. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  8. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  9. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  10. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  11. 2022Rationale-Augmented Ensembles in Language Modelscited by 111
  12. 2017Failures of Gradient-Based Deep Learningcited by 80
15 more
  1. 2020Learning Parities with Neural Networkscited by 78
  2. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  3. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 74
  4. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  5. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  6. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 36
  7. 2020Poly-time universality and limitations of deep learningcited by 23
  8. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 22
  9. 2024Implicit Regularization of Gradient Flow on One-Layer Softmax Attentioncited by 19
  10. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  11. 2024Matching the Statistical Query Lower Bound for k-Sparse Parity Problems with Sign Stochastic Gradient Descentcited by 7
  12. 2021On the Provable Generalization of Recurrent Neural Networkscited by 6
  13. 2024In-Context Learning of Linear Systems: Generalization Theory and Applications to Operator Learningcited by 6
  14. 2018Provable limitations of deep learningcited by 5
  15. 2023Tight Time-Space Lower Bounds for Constant-Pass Learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 16; 2026: 13.

29 papers.

Sort:

By area:

  1. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 91
  2. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  3. 2025Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thoughtcited by 16
  4. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 14
  5. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 13
  6. 2025Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to DT Tasks?cited by 11
  7. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 11
  8. 2025Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoningcited by 10
  9. 2025United Minds or Isolated Agents? Exploring Coordination of LLMs under Cognitive Load Theorycited by 10
  10. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  11. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  12. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
17 more
  1. 2025Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regressioncited by 3
  2. 2025The Impossibility of Inverse Permutation Learning in Transformer Modelscited by 2
  3. 2025Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Informationcited by 2
  4. 2026Unlabeled Data Can Provably Enhance In-Context Learning of Transformerscited by 2
  5. 2026Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridgecited by 2
  6. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  7. 2026Transformers Provably Learn to Internalize Chain-of-Thoughtcited by 2
  8. 2026Tuning the Implicit Regularizer of Masked Diffusion Language Models: Enhancing Generalization via Insights from k-Paritycited by 1
  9. 2026When Is Compositional Reasoning Learnable from Verifiable Rewards?cited by 1
  10. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1
  11. 2026Fine-Tuning Dynamics of In-Context Factual Recall in Transformerscited by 1
  12. 2025Debiasing LLMs by Masking Unfairness-Driving Attention Headscited by 0
  13. 2026How Transformers Learn to Plan via Multi-Token Predictioncited by 0
  14. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  15. 2026Steered Generation via Gradient-Based Optimization on Sparse Query Featurescited by 0
  16. 2026Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixingcited by 0
  17. 2026Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis
  2. 2025How does Chain of Thought Think? Mechanistic Interpretability of Chain-of-Thought Reasoning with Sparse Autoencoding
  3. 2025Don't Take Things Out of Context: Attention Intervention for Enhancing Chain-of-Thought Reasoning in Large Language Models
  4. 2024Understanding Hidden Computations in Chain-of-Thought Reasoning
  5. 2026Triggering Chain-of-Thought via Latent Feature Interventions in Large Language Models
  6. 2024Chain-of-Thought in Large Language Models: Decoding, Projection, and Activation
  7. 2025Stream: Scaling up Mechanistic Interpretability to Long Context in LLMs via Sparse Attention
  8. 2026Zipping the Thought: When and How Compressed Reasoning Data Works in LLM Post-Training