# Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2024.

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

- [A Survey on Latent Reasoning](https://mlsanity.com/paper/2507.06203/) (2025)
- [Training Dynamics of In-Context Learning in Linear Attention](https://mlsanity.com/paper/2501.16265/) (2025)
- [When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformers](https://mlsanity.com/paper/2504.10957/) (2025)
- [Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought](https://mlsanity.com/paper/2502.21212/) (2025)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [How Do LLMs Perform Two-Hop Reasoning in Context?](https://mlsanity.com/paper/2502.13913/) (2025)
- [Toward Understanding In-context vs. In-weight Learning](https://mlsanity.com/paper/2410.23042/) (2024)
- [Context parroting: A simple but tough-to-beat baseline for foundation models in scientific machine learning](https://mlsanity.com/paper/2505.11349/) (2025)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations](https://mlsanity.com/paper/2504.12691/) (2025)
- [Language Model Behavioral Phases are Consistent Across Architecture, Training Data, and Scale](https://mlsanity.com/paper/2510.24963/) (2025)
- [How Transformers Get Rich: Approximation and Dynamics Analysis](https://mlsanity.com/paper/2410.11474/) (2024)
- [KV Shifting Attention Enhances Language Modeling](https://mlsanity.com/paper/2411.19574/) (2024)
- [In-Context Learning of Linear Systems: Generalization Theory and Applications to Operator Learning](https://mlsanity.com/paper/2409.12293/) (2024)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers](https://mlsanity.com/paper/2512.18634/) (2025)
- [Scaling sparse feature circuit finding for in-context learning](https://mlsanity.com/paper/2504.13756/) (2025)
- [In-Context Occam's Razor: How Transformers Prefer Simpler Hypotheses on the Fly](https://mlsanity.com/paper/2506.19351/) (2025)
- [On the Emergence of Induction Heads for In-Context Learning](https://mlsanity.com/paper/2511.01033/) (2025)
- [In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-Separation](https://mlsanity.com/paper/2502.08136/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Understanding Contextual Recall in Transformers: How Finetuning Enables In-Context Reasoning over Pretraining Knowledge](https://mlsanity.com/paper/2603.20969/) (2026)
- [Induction Signatures Are Not Enough: A Matched-Compute Study of Load-Bearing Structure in In-Context Learning](https://mlsanity.com/paper/2509.22947/) (2025)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information](https://mlsanity.com/paper/2510.25542/) (2025)
- [Towards Understanding Transformers in Learning Random Walks](https://mlsanity.com/paper/2511.23239/) (2025)
- [Incremental Learning of Sparse Attention Patterns in Transformers](https://mlsanity.com/paper/2602.19143/) (2026)
- [Hierarchical Latent Structures in Data Generation Process Unify Mechanistic Phenomena across Scale](https://mlsanity.com/paper/2603.06592/) (2026)
- [Weight Decay Regimes in Grokking Transformers: Cheap Online Diagnostics](https://mlsanity.com/paper/2605.20441/) (2026)
- [Universal Response and Emergence of Induction in LLMs](https://mlsanity.com/paper/2411.07071/) (2024)

## Abstract (arXiv)

In-context learning (ICL) is a cornerstone of large language model (LLM) functionality, yet its theoretical foundations remain elusive due to the complexity of transformer architectures. In particular, most existing work only theoretically explains how the attention mechanism facilitates ICL under certain data models. It remains unclear how the other building blocks of the transformer contribute to ICL. To address this question, we study how a two-attention-layer transformer is trained to perform ICL on n-gram Markov chain data, where each token in the Markov chain statistically depends on the previous n tokens. We analyze a sophisticated transformer model featuring relative positional embedding, multi-head softmax attention, and a feed-forward layer with normalization. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model that performs a generalized version of the induction head mechanism with a learned feature, resulting from the congruous contribution of all the building blocks. In the limiting model, the first attention layer acts as a mathitcopier, copying past tokens within a given window to each position, and the feed-forward network with normalization acts as a mathitselector that generates a feature vector by only looking at informationally relevant parents from the window. Finally, the second attention layer is a mathitclassifier that compares these features with the feature at the output position, and uses the resulting similarity scores to generate the desired output. Our theory is further validated by experiments.