# Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 66 references that are in the map.
- First posted on arXiv 6 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [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)
- [Dissecting Recall of Factual Associations in Auto-Regressive Language Models](https://mlsanity.com/paper/2304.14767/) (2023)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Using the Output Embedding to Improve Language Models](https://mlsanity.com/paper/1608.05859/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Analyzing the Structure of Attention in a Transformer Language Model](https://mlsanity.com/paper/1906.04284/) (2019)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Rethinking embedding coupling in pre-trained language models](https://mlsanity.com/paper/2010.12821/) (2020)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding](https://mlsanity.com/paper/2303.04245/) (2023)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)
- [The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limit](https://mlsanity.com/paper/2306.17759/) (2023)

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

- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Mechanics of Next Token Prediction with Self-Attention](https://mlsanity.com/paper/2403.08081/) (2024)
- [Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought](https://mlsanity.com/paper/2502.21212/) (2025)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Transformers on Markov Data: Constant Depth Suffices](https://mlsanity.com/paper/2407.17686/) (2024)
- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [Training LLMs over Neurally Compressed Text](https://mlsanity.com/paper/2404.03626/) (2024)
- [From Pixels to Tokens: Byte-Pair Encoding on Quantized Visual Modalities](https://mlsanity.com/paper/2410.02155/) (2024)
- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformers](https://mlsanity.com/paper/2406.18400/) (2024)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis](https://mlsanity.com/paper/2410.02167/) (2024)
- [Gating is Weighting: Understanding Gated Linear Attention through In-context Learning](https://mlsanity.com/paper/2504.04308/) (2025)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection](https://mlsanity.com/paper/2410.14581/) (2024)
- [Unified Multimodal Understanding via Byte-Pair Visual Encoding](https://mlsanity.com/paper/2506.23639/) (2025)
- [Selective Induction Heads: How Transformers Select Causal Structures In Context](https://mlsanity.com/paper/2509.08184/) (2025)
- [All You Need is One: Capsule Prompt Tuning with a Single Vector](https://mlsanity.com/paper/2510.16670/) (2025)
- [On the Power of Convolution Augmented Transformer](https://mlsanity.com/paper/2407.05591/) (2024)
- [Universality of Layer-Level Entropy-Weighted Quantization Beyond Model Architecture and Size](https://mlsanity.com/paper/2503.04704/) (2025)
- [Pre-trained Large Language Models Learn Hidden Markov Models In-context](https://mlsanity.com/paper/2506.07298/) (2025)
- [Provable In-Context Learning of Nonlinear Regression with Transformers](https://mlsanity.com/paper/2507.20443/) (2025)
- [Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories](https://mlsanity.com/paper/2511.07368/) (2025)
- [An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains](https://mlsanity.com/paper/2410.05493/) (2024)
- [Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data?](https://mlsanity.com/paper/2501.15857/) (2025)
- [Facts in Stats: Impacts of Pretraining Diversity on Language Model Generalization](https://mlsanity.com/paper/2510.16096/) (2025)
- [Multiple Choice Learning of Low-Rank Adapters for Language Modeling](https://mlsanity.com/paper/2507.10419/) (2025)

## Abstract (arXiv)

Attention-based transformers have achieved tremendous success across a variety of disciplines including natural languages. To deepen our understanding of their sequential modeling capabilities, there is a growing interest in using Markov input processes to study them. A key finding is that when trained on first-order Markov chains, transformers with two or more layers consistently develop an induction head mechanism to estimate the in-context bigram conditional distribution. In contrast, single-layer transformers, unable to form an induction head, directly learn the Markov kernel but often face a surprising challenge: they become trapped in local minima representing the unigram distribution, whereas deeper models reliably converge to the ground-truth bigram. While single-layer transformers can theoretically model first-order Markov chains, their empirical failure to learn this simple kernel in practice remains a curious phenomenon. To explain this contrasting behavior of single-layer models, in this paper we introduce a new framework for a principled analysis of transformers via Markov chains. Leveraging our framework, we theoretically characterize the loss landscape of single-layer transformers and show the existence of global minima (bigram) and bad local minima (unigram) contingent on data properties and model architecture. We precisely delineate the regimes under which these local optima occur. Backed by experiments, we demonstrate that our theoretical findings are in congruence with the empirical results. Finally, we outline several open problems in this arena. Code is available at https://github.com/Bond1995/Markov .