# Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2025.

## Built on by (most cited first, 7 of 7)

- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Shared Parameter Subspaces and Cross-Task Linearity in Emergently Misaligned Behavior](https://mlsanity.com/paper/2511.02022/) (2025)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information](https://mlsanity.com/paper/2510.25542/) (2025)
- [Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently](https://mlsanity.com/paper/2511.17852/) (2025)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)

## Abstract (arXiv)

Transformers have demonstrated remarkable capabilities in multi-step reasoning tasks. However, understandings of the underlying mechanisms by which they acquire these abilities through training remain limited, particularly from a theoretical standpoint. This work investigates how transformers learn to solve symbolic multi-step reasoning problems through chain-of-thought processes, focusing on path-finding in trees. We analyze two intertwined tasks: a backward reasoning task, where the model outputs a path from a goal node to the root, and a more complex forward reasoning task, where the model implements two-stage reasoning by first identifying the goal-to-root path and then reversing it to produce the root-to-goal path. Our theoretical analysis, grounded in the dynamics of gradient descent, shows that trained one-layer transformers can provably solve both tasks with generalization guarantees to unseen trees. In particular, our multi-phase training dynamics for forward reasoning elucidate how different attention heads learn to specialize and coordinate autonomously to solve the two subtasks in a single autoregressive path. These results provide a mechanistic explanation of how trained transformers can implement sequential algorithmic procedures. Moreover, they offer insights into the emergence of reasoning abilities, suggesting that when tasks are structured to take intermediate chain-of-thought steps, even shallow multi-head transformers can effectively solve problems that would otherwise require deeper architectures.