# From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 70 references that are in the map.
- First posted on arXiv 21 Feb 2024.

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

- [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)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Get To The Point: Summarization with Pointer-Generator Networks](https://mlsanity.com/paper/1704.04368/) (2017)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [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)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Using the Output Embedding to Improve Language Models](https://mlsanity.com/paper/1608.05859/) (2016)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Learning to Break the Loop: Analyzing and Mitigating Repetitions for Neural Text Generation](https://mlsanity.com/paper/2206.02369/) (2022)
- [Vision Transformers provably learn spatial structure](https://mlsanity.com/paper/2210.09221/) (2022)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [A Theoretical Analysis of the Repetition Problem in Text Generation](https://mlsanity.com/paper/2012.14660/) (2020)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [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)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Consistency of a Recurrent Language Model With Respect to Incomplete Decoding](https://mlsanity.com/paper/2002.02492/) (2020)

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

- [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)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [Mechanics of Next Token Prediction with Self-Attention](https://mlsanity.com/paper/2403.08081/) (2024)
- [Selective Attention: Enhancing Transformer through Principled Context Control](https://mlsanity.com/paper/2411.12892/) (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)
- [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)
- [Attention (as Discrete-Time Markov) Chains](https://mlsanity.com/paper/2507.17657/) (2025)
- [Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers](https://mlsanity.com/paper/2506.10887/) (2025)
- [From Condensation to Rank Collapse: A Two-Stage Analysis of Transformer Training Dynamics](https://mlsanity.com/paper/2510.06954/) (2025)
- [Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection](https://mlsanity.com/paper/2410.14581/) (2024)
- [Selective Induction Heads: How Transformers Select Causal Structures In Context](https://mlsanity.com/paper/2509.08184/) (2025)
- [What Happens During the Loss Plateau? Understanding Abrupt Learning in Transformers](https://mlsanity.com/paper/2506.13688/) (2025)
- [On the Power of Convolution Augmented Transformer](https://mlsanity.com/paper/2407.05591/) (2024)
- [On the Convergence of Gradient Descent on Learning Transformers with Residual Connections](https://mlsanity.com/paper/2506.05249/) (2025)
- [Prompting Large Language Models with Partial Knowledge for Answering Questions with Unseen Entities](https://mlsanity.com/paper/2508.01290/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)
- [Achieving the Tightest Relaxation of Sigmoids for Formal Verification](https://mlsanity.com/paper/2408.10491/) (2024)
- [State space models, emergence, and ergodicity: How many parameters are needed for stable predictions?](https://mlsanity.com/paper/2409.13421/) (2024)
- [Key and Value Weights Are Probably All You Need: On the Necessity of the Query, Key, Value weight Triplet in Self-Attention Transformers](https://mlsanity.com/paper/2510.23912/) (2025)
- [Towards Understanding Transformers in Learning Random Walks](https://mlsanity.com/paper/2511.23239/) (2025)
- [Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge](https://mlsanity.com/paper/2602.02470/) (2026)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Resource Consumption Threats in Large Language Models](https://mlsanity.com/paper/2603.16068/) (2026)
- [Transformers Provably Learn to Internalize Chain-of-Thought](https://mlsanity.com/paper/2605.28600/) (2026)
- [Attention with Trained Embeddings Provably Selects Important Tokens](https://mlsanity.com/paper/2505.17282/) (2025)
- [Transformers Learn Latent Mixture Models In-Context via Mirror Descent](https://mlsanity.com/paper/2604.10848/) (2026)
- [Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models](https://mlsanity.com/paper/2505.00818/) (2025)

## Abstract (arXiv)

Modern language models rely on the transformer architecture and attention mechanism to perform language understanding and text generation. In this work, we study learning a 1-layer self-attention model from a set of prompts and associated output data sampled from the model. We first establish a precise mapping between the self-attention mechanism and Markov models: Inputting a prompt to the model samples the output token according to a context-conditioned Markov chain (CCMC) which weights the transition matrix of a base Markov chain. Additionally, incorporating positional encoding results in position-dependent scaling of the transition probabilities. Building on this formalism, we develop identifiability/coverage conditions for the prompt distribution that guarantee consistent estimation and establish sample complexity guarantees under IID samples. Finally, we study the problem of learning from a single output trajectory generated from an initial prompt. We characterize an intriguing winner-takes-all phenomenon where the generative process implemented by self-attention collapses into sampling a limited subset of tokens due to its non-mixing nature. This provides a mathematical explanation to the tendency of modern LLMs to generate repetitive text. In summary, the equivalence to CCMC provides a simple but powerful framework to study self-attention and its properties.