# The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains

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

## Key facts

- Cited by 118 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 47 references that are in the map.
- First posted on arXiv 16 Feb 2024.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [The Pitfalls of Simplicity Bias in Neural Networks](https://mlsanity.com/paper/2006.07710/) (2020)
- [In-Context Learning Creates Task Vectors](https://mlsanity.com/paper/2310.15916/) (2023)
- [Data Distributional Properties Drive Emergent In-Context Learning in Transformers](https://mlsanity.com/paper/2205.05055/) (2022)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [The mechanistic basis of data dependence and abrupt learning in an in-context classification task](https://mlsanity.com/paper/2312.03002/) (2023)
- [Grokking as the Transition from Lazy to Rich Training Dynamics](https://mlsanity.com/paper/2310.06110/) (2023)
- [General-Purpose In-Context Learning by Meta-Learning Transformers](https://mlsanity.com/paper/2212.04458/) (2022)
- [How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?](https://mlsanity.com/paper/2310.08391/) (2023)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks](https://mlsanity.com/paper/2303.11873/) (2023)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)

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

- [A Practical Review of Mechanistic Interpretability for Transformer-Based Language Models](https://mlsanity.com/paper/2407.02646/) (2024)
- [Attention Heads of Large Language Models: A Survey](https://mlsanity.com/paper/2409.03752/) (2024)
- [Training Dynamics of In-Context Learning in Linear Attention](https://mlsanity.com/paper/2501.16265/) (2025)
- [Differentiation and Specialization of Attention Heads via the Refined Local Learning Coefficient](https://mlsanity.com/paper/2410.02984/) (2024)
- [In-Context Learning with Representations: Contextual Generalization of Trained Transformers](https://mlsanity.com/paper/2408.10147/) (2024)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought](https://mlsanity.com/paper/2502.21212/) (2025)
- [Iteration Head: A Mechanistic Study of Chain-of-Thought](https://mlsanity.com/paper/2406.02128/) (2024)
- [Next-Latent Prediction Transformers Learn Compact World Models](https://mlsanity.com/paper/2511.05963/) (2025)
- [Transformers on Markov Data: Constant Depth Suffices](https://mlsanity.com/paper/2407.17686/) (2024)
- [Understanding Transformers via N-gram Statistics](https://mlsanity.com/paper/2407.12034/) (2024)
- [A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Language](https://mlsanity.com/paper/2408.12578/) (2024)
- [The emergence of sparse attention: impact of data distribution and benefits of repetition](https://mlsanity.com/paper/2505.17863/) (2025)
- [Implicit Geometry of Next-token Prediction: From Language Sparsity Patterns to Model Representations](https://mlsanity.com/paper/2408.15417/) (2024)
- [Can In-context Learning Really Generalize to Out-of-distribution Tasks?](https://mlsanity.com/paper/2410.09695/) (2024)
- [Differential learning kinetics govern the transition from memorization to generalization during in-context learning](https://mlsanity.com/paper/2412.00104/) (2024)
- [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)
- [When can in-context learning generalize out of task distribution?](https://mlsanity.com/paper/2506.05574/) (2025)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [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)
- [Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformers](https://mlsanity.com/paper/2406.18400/) (2024)
- [Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context](https://mlsanity.com/paper/2410.01774/) (2024)
- [Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architectures](https://mlsanity.com/paper/2512.20607/) (2025)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Dynamics of Transient Structure in In-Context Linear Regression Transformers](https://mlsanity.com/paper/2501.17745/) (2025)
- [HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking](https://mlsanity.com/paper/2505.02322/) (2025)
- [On the origin of neural scaling laws: from random graphs to natural language](https://mlsanity.com/paper/2601.10684/) (2026)
- [Language Model Behavioral Phases are Consistent Across Architecture, Training Data, and Scale](https://mlsanity.com/paper/2510.24963/) (2025)
- [Distributional Associations vs In-Context Reasoning: A Study of Feed-forward and Attention Layers](https://mlsanity.com/paper/2406.03068/) (2024)

## Abstract (arXiv)

Large language models have the ability to generate text that mimics patterns in their inputs. We introduce a simple Markov Chain sequence modeling task in order to study how this in-context learning (ICL) capability emerges. In our setting, each example is sampled from a Markov chain drawn from a prior distribution over Markov chains. Transformers trained on this task form statistical induction heads which compute accurate next-token probabilities given the bigram statistics of the context. During the course of training, models pass through multiple phases: after an initial stage in which predictions are uniform, they learn to sub-optimally predict using in-context single-token statistics (unigrams); then, there is a rapid phase transition to the correct in-context bigram solution. We conduct an empirical and theoretical investigation of this multi-phase process, showing how successful learning results from the interaction between the transformer's layers, and uncovering evidence that the presence of the simpler unigram solution may delay formation of the final bigram solution. We examine how learning is affected by varying the prior distribution over Markov chains, and consider the generalization of our in-context learning of Markov chains (ICL-MC) task to n-grams for n > 2.