mlsanityData to 14 Oct 2026

Data Shifts Hurt CoT: A Theoretical Study

arXiv 2506.10647 ↗First posted 12 Jun 2025cs.LG cs.AIcited by 2

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

Abstract (arXiv)

Chain of Thought (CoT) has been applied to various large language models (LLMs) and proven to be effective in improving the quality of outputs. In recent studies, transformers are proven to have absolute upper bounds in terms of expressive power, and consequently, they cannot solve many computationally difficult problems. However, empowered by CoT, transformers are proven to be able to solve some difficult problems effectively, such as the k-parity problem. Nevertheless, those works rely on two imperative assumptions: (1) identical training and testing distribution, and (2) corruption-free training data with correct reasoning steps. However, in the real world, these assumptions do not always hold. Although the risks of data shifts have caught attention, our work is the first to rigorously study the exact harm caused by such shifts to the best of our knowledge. Focusing on the k-parity problem, in this work we investigate the joint impact of two types of data shifts: the distribution shifts and data poisoning, on the quality of trained models obtained by a well-established CoT decomposition. In addition to revealing a surprising phenomenon that CoT leads to worse performance on learning parity than directly generating the prediction, our technical results also give a rigorous and comprehensive explanation of the mechanistic reasons of such impact.

Key facts. Cited by 2 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 21 of its 27 references that are in the map. First posted on arXiv 12 Jun 2025.

Builds on

21 of 27 references.

Closest ancestors · 8

Same direction, newest first

  1. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation2 Feb
  2. 2024Mind Your Step (by Step): Chain-of-Thought can Reduce Performance on Tasks where Thinking Makes Humans Worse27 Oct
  3. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought11 Oct
  4. 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning18 Sep
  5. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models24 Apr
  6. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  7. 2022On Second Thought, Let's Not Think Step by Step! Bias and Toxicity in Zero-Shot Reasoning15 Dec
  8. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 13

  1. 2017Attention Is All You Needcited by 60,361
  2. 2023Let's Verify Step by Stepcited by 3,789
  3. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 940
  4. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  5. 2023Chain-of-Verification Reduces Hallucination in Large Language Modelscited by 324
  6. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  8. 2017Failures of Gradient-Based Deep Learningcited by 80
  9. 2020Learning Parities with Neural Networkscited by 78
  10. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 63
  11. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  12. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
1 more
  1. 2023Memory Injections: Correcting Multi-Hop Reasoning Failures during Inference in Transformer-Based Language Modelscited by 21

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMscited by 5
  2. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4

Similar, not cited

Close in wording, no citation either way

  1. 2025Is Chain-of-Thought Reasoning of LLMs a Mirage? A Data Distribution Lens
  2. 2025Beyond In-Distribution Success: Scaling Curves of CoT Granularity for Language Model Generalization
  3. 2026Zipping the Thought: When and How Compressed Reasoning Data Works in LLM Post-Training
  4. 2023Measuring Faithfulness in Chain-of-Thought Reasoning
  5. 2024Deciphering the Factors Influencing the Efficacy of Chain-of-Thought: Probability, Memorization, and Noisy Reasoning
  6. 2024On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models
  7. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency
  8. 2025Through the Valley: Path to Effective Long CoT Training for Small Language Models