mlsanityData to 14 Oct 2026

Transformers Provably Solve Parity Efficiently with Chain of Thought

arXiv 2410.08633 ↗First posted 11 Oct 2024cs.LG stat.MLcited by 50

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

Abstract (arXiv)

This work provides the first theoretical analysis of training transformers to solve complex problems by recursively generating intermediate states, analogous to fine-tuning for chain-of-thought (CoT) reasoning. We consider training a one-layer transformer to solve the fundamental k-parity problem, extending the work on RNNs by Wies et al. (2023). We establish three key results: (1) any finite-precision gradient-based algorithm, without intermediate supervision, requires substantial iterations to solve parity with finite samples. (2) In contrast, when intermediate parities are incorporated into the loss function, our model can learn parity in one gradient update when aided by teacher forcing, where ground-truth labels of the reasoning chain are provided at each generation step. (3) Even without teacher forcing, where the model must generate CoT chains end-to-end, parity can be learned efficiently if augmented data is employed to internally verify the soundness of intermediate steps. Our findings, supported by numerical experiments, show that task decomposition and stepwise reasoning naturally arise from optimizing transformers with CoT; moreover, self-consistency checking can improve multi-step reasoning ability, aligning with empirical studies of CoT.

Key facts. Cited by 50 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 15 of its 53 references that are in the map. First posted on arXiv 11 Oct 2024.

Builds on

15 of 53 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods25 Aug
  2. 2024Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanism24 May
  3. 2024Beyond Answers: Transferring Reasoning Capabilities to Smaller LLMs Using Multi-Teacher Knowledge Distillation7 Feb
  4. 2023Igniting Language Intelligence: The Hitchhiker's Guide From Chain-of-Thought Reasoning to Language Agents20 Nov
  5. 2023Implicit Chain of Thought Reasoning via Knowledge Distillation2 Nov

Other references · 10

  1. 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,202
  2. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  3. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  4. 2020Integer Quantization for Deep Learning Inference: Principles and Empirical Evaluationcited by 188
  5. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 170
  6. 2023In-Context Convergence of Transformerscited by 115
  7. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  8. 2023GPT-4 Can't Reasoncited by 40
  9. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  10. 2023Memory Injections: Correcting Multi-Hop Reasoning Failures during Inference in Transformer-Based Language Modelscited by 21

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 28; 2026: 21.

50 papers.

Sort:

By area:

  1. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  2. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 18
  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. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  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. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  10. 2025Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithmscited by 7
  11. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 6
  12. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 6
38 more
  1. 2025What makes a good feedforward computational graph?cited by 5
  2. 2025Beyond In-Distribution Success: Scaling Curves of CoT Granularity for Language Model Generalizationcited by 5
  3. 2025DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMscited by 5
  4. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  5. 2025A Theoretical Framework for OOD Robustness in Transformers using Gevrey Classescited by 4
  6. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  7. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  8. 2025Transformers Provably Learn Sparse XOR with Polylogarithmic Parameterscited by 3
  9. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  10. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 3
  11. 2025Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regressioncited by 3
  12. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  13. 2026How Do Transformers Learn to Associate Tokens: Gradient Leading Terms Bring Mechanistic Interpretabilitycited by 3
  14. 2026Can Vision-Language Models Solve the Shell Game?cited by 3
  15. 2026Learning to Think from Multiple Thinkerscited by 3
  16. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoningcited by 3
  17. 2025Data Shifts Hurt CoT: A Theoretical Studycited by 2
  18. 2025Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Informationcited by 2
  19. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 2
  20. 2026Unlabeled Data Can Provably Enhance In-Context Learning of Transformerscited by 2
  21. 2026Transformers Provably Learn to Internalize Chain-of-Thoughtcited by 2
  22. 2025Discovering Learning-Friendly Generation Orders for Sequential Computationcited by 1
  23. 2026Tuning the Implicit Regularizer of Masked Diffusion Language Models: Enhancing Generalization via Insights from k-Paritycited by 1
  24. 2026When Is Compositional Reasoning Learnable from Verifiable Rewards?cited by 1
  25. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  26. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  27. 2026The Scaling Properties of Implicit Deductive Reasoning in Transformerscited by 1
  28. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1
  29. 2026Fine-Tuning Dynamics of In-Context Factual Recall in Transformerscited by 1
  30. 2026Learning through Internalizationcited by 1
  31. 2025RACE-Align: Retrieval-Augmented and Chain-of-Thought Enhanced Preference Alignment for Large Language Modelscited by 0
  32. 2025CALT: A Library for Computer Algebra with Transformercited by 0
  33. 2025Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decodingcited by 0
  34. 2026How Transformers Learn to Plan via Multi-Token Predictioncited by 0
  35. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  36. 2026Learning Large-Scale Modular Addition with an Auxiliary Moduluscited by 0
  37. 2026Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixingcited by 0
  38. 2026Learn Your Own Thoughts: Abstract Token Curriculumcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
  2. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
  3. 2025Deep Thinking by Markov Chain of Continuous Thoughts
  4. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
  5. 2024Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization
  6. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis
  7. 2025Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
  8. 2026Beyond the Training Horizon: Mechanisms and Limits of Length Generalization in Looped Transformers