mlsanityData to 7 Oct 2026

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

arXiv 2402.04161 ↗First posted 6 Feb 2024cs.LG cs.CL cs.ITcited by 39

Not on the map. Why?

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 .

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

Builds on

35 of 66 references.

References · 35

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2022Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallcited by 1,130
  5. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 915
  6. 2023Progress measures for grokking via mechanistic interpretabilitycited by 822
  7. 2022Transformers learn in-context by gradient descentcited by 714
  8. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  10. 2023Dissecting Recall of Factual Associations in Auto-Regressive Language Modelscited by 512
  11. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  12. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
23 more
  1. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  2. 2016Using the Output Embedding to Improve Language Modelscited by 266
  3. 2016Benefits of depth in neural networkscited by 248
  4. 2019Analyzing the Structure of Attention in a Transformer Language Modelcited by 241
  5. 2023Looped Transformers as Programmable Computerscited by 224
  6. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  7. 2021Thinking Like Transformerscited by 182
  8. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  9. 2020Rethinking embedding coupling in pre-trained language modelscited by 103
  10. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  11. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  12. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  13. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  14. 2023Transformers as Support Vector Machinescited by 67
  15. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  16. 2023Max-Margin Token Selection in Attention Mechanismcited by 57
  17. 2023On the Role of Attention in Prompt-tuningcited by 49
  18. 2023The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limitcited by 47
  19. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  20. 2021Approximating How Single Head Attention Learnscited by 38
  21. 2022What is my math transformer doing? -- Three results on interpretability and generalizationcited by 19
  22. 2018On Learning Markov Chainscited by 13
  23. 2018Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Spacecited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 17; 2025: 16; 2026: 6.

39 papers.

Sort:

By area:

  1. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 115
  2. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  3. 2024Mechanics of Next Token Prediction with Self-Attentioncited by 34
  4. 2024Large Language Models as Markov Chainscited by 33
  5. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtcited by 32
  6. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  7. 2024Transformers on Markov Data: Constant Depth Sufficescited by 26
  8. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  9. 2024Understanding and Mitigating Tokenization Bias in Language Modelscited by 18
  10. 2024Training LLMs over Neurally Compressed Textcited by 16
  11. 2024From Pixels to Tokens: Byte-Pair Encoding on Quantized Visual Modalitiescited by 16
  12. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 15
27 more
  1. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  2. 2024Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformerscited by 14
  3. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysiscited by 14
  4. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  5. 2025Gating is Weighting: Understanding Gated Linear Attention through In-context Learningcited by 11
  6. 2024Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selectioncited by 9
  7. 2025Unified Multimodal Understanding via Byte-Pair Visual Encodingcited by 9
  8. 2025All You Need is One: Capsule Prompt Tuning with a Single Vectorcited by 8
  9. 2025Selective Induction Heads: How Transformers Select Causal Structures In Contextcited by 7
  10. 2024On the Power of Convolution Augmented Transformercited by 5
  11. 2025Universality of Layer-Level Entropy-Weighted Quantization Beyond Model Architecture and Sizecited by 4
  12. 2025Pre-trained Large Language Models Learn Hidden Markov Models In-contextcited by 4
  13. 2025Provable In-Context Learning of Nonlinear Regression with Transformerscited by 4
  14. 2025Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data?cited by 3
  15. 2025Facts in Stats: Impacts of Pretraining Diversity on Language Model Generalizationcited by 3
  16. 2025Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectoriescited by 3
  17. 2024An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chainscited by 2
  18. 2025Multiple Choice Learning of Low-Rank Adapters for Language Modelingcited by 2
  19. 2026Syllabic Agglutinative Tokenizations for Indonesian LLM: A Study from Gasing Literacy Learning Systemcited by 2
  20. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  21. 2025Cognitive Activation and Chaotic Dynamics in Large Language Models: A Quasi-Lyapunov Analysis of Reasoning Mechanismscited by 1
  22. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 1
  23. 2026Transformers Learn Latent Mixture Models In-Context via Mirror Descentcited by 1
  24. 2024Analysis of Unstructured High-Density Crowded Scenes for Crowd Monitoringcited by 0
  25. 2025Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functionscited by 0
  26. 2026Induction Heads Interpolate N-Gramscited by 0
  27. 2026Relevant and Irrelevant: A Renormalization Group Analysis of Transformer Attentioncited by 0