# Transformers Provably Solve Parity Efficiently with Chain of Thought

arXiv: https://arxiv.org/abs/2410.08633 · HTML: https://mlsanity.com/paper/2410.08633/

## 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 15 of 15)

- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Integer Quantization for Deep Learning Inference: Principles and Empirical Evaluation](https://mlsanity.com/paper/2004.09602/) (2020)
- [Implicit Chain of Thought Reasoning via Knowledge Distillation](https://mlsanity.com/paper/2311.01460/) (2023)
- [One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention](https://mlsanity.com/paper/2307.03576/) (2023)
- [In-Context Convergence of Transformers](https://mlsanity.com/paper/2310.05249/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Igniting Language Intelligence: The Hitchhiker's Guide From Chain-of-Thought Reasoning to Language Agents](https://mlsanity.com/paper/2311.11797/) (2023)
- [Beyond Answers: Transferring Reasoning Capabilities to Smaller LLMs Using Multi-Teacher Knowledge Distillation](https://mlsanity.com/paper/2402.04616/) (2024)
- [GPT-4 Can't Reason](https://mlsanity.com/paper/2308.03762/) (2023)
- [Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods](https://mlsanity.com/paper/2408.14511/) (2024)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [Memory Injections: Correcting Multi-Hop Reasoning Failures during Inference in Transformer-Based Language Models](https://mlsanity.com/paper/2309.05605/) (2023)
- [Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanism](https://mlsanity.com/paper/2405.15302/) (2024)

## Built on by (most cited first, 30 of 50)

- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thought](https://mlsanity.com/paper/2509.23365/) (2025)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformers](https://mlsanity.com/paper/2506.00744/) (2025)
- [How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias](https://mlsanity.com/paper/2505.00926/) (2025)
- [Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning](https://mlsanity.com/paper/2502.04667/) (2025)
- [Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent](https://mlsanity.com/paper/2504.04702/) (2025)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [What makes a good feedforward computational graph?](https://mlsanity.com/paper/2502.06751/) (2025)
- [Beyond In-Distribution Success: Scaling Curves of CoT Granularity for Language Model Generalization](https://mlsanity.com/paper/2502.18273/) (2025)
- [DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs](https://mlsanity.com/paper/2510.19842/) (2025)
- [RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasoner](https://mlsanity.com/paper/2410.23912/) (2024)
- [A Theoretical Framework for OOD Robustness in Transformers using Gevrey Classes](https://mlsanity.com/paper/2504.12991/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters](https://mlsanity.com/paper/2502.07553/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective](https://mlsanity.com/paper/2503.11272/) (2025)
- [Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression](https://mlsanity.com/paper/2508.07571/) (2025)
- [Test time training enhances in-context learning of nonlinear functions](https://mlsanity.com/paper/2509.25741/) (2025)
- [How Do Transformers Learn to Associate Tokens: Gradient Leading Terms Bring Mechanistic Interpretability](https://mlsanity.com/paper/2601.19208/) (2026)
- [Can Vision-Language Models Solve the Shell Game?](https://mlsanity.com/paper/2603.08436/) (2026)
- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)
- [Data Shifts Hurt CoT: A Theoretical Study](https://mlsanity.com/paper/2506.10647/) (2025)
- [Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information](https://mlsanity.com/paper/2510.25542/) (2025)

## 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.