# Large Language Models as Markov Chains

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

## Key facts

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

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

- [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)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [How Much Knowledge Can You Pack Into the Parameters of a Language Model?](https://mlsanity.com/paper/2002.08910/) (2020)
- [Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning](https://mlsanity.com/paper/2012.13255/) (2020)
- [Large Language Models Are Zero-Shot Time Series Forecasters](https://mlsanity.com/paper/2310.07820/) (2023)
- [Sentiment Analysis in the Era of Large Language Models: A Reality Check](https://mlsanity.com/paper/2305.15005/) (2023)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [The Learnability of In-Context Learning](https://mlsanity.com/paper/2303.07895/) (2023)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://mlsanity.com/paper/2402.14903/) (2024)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [An Information-Theoretic Analysis of In-Context Learning](https://mlsanity.com/paper/2401.15530/) (2024)
- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [Transformers are Minimax Optimal Nonparametric In-Context Learners](https://mlsanity.com/paper/2408.12186/) (2024)

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

- [Atom of Thoughts for Markov LLM Test-Time Scaling](https://mlsanity.com/paper/2502.12018/) (2025)
- [Fine-Tuning Discrete Diffusion Models with Policy Gradient Methods](https://mlsanity.com/paper/2502.01384/) (2025)
- [The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations](https://mlsanity.com/paper/2509.12886/) (2025)
- [Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation](https://mlsanity.com/paper/2502.01694/) (2025)
- [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)
- [A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMs](https://mlsanity.com/paper/2410.18779/) (2024)
- [Recitation over Reasoning: How Cutting-Edge Language Models Can Fail on Elementary School-Level Reasoning Problems?](https://mlsanity.com/paper/2504.00509/) (2025)
- [Text-Trained LLMs Can Zero-Shot Extrapolate PDE Dynamics, Revealing a Three-Stage In-Context Learning Mechanism](https://mlsanity.com/paper/2509.06322/) (2025)
- [Clip Your Sequences Fairly: Enforcing Length Fairness for Sequence-Level RL](https://mlsanity.com/paper/2509.09177/) (2025)
- [Old Habits Die Hard: How Conversational History Geometrically Traps LLMs](https://mlsanity.com/paper/2603.03308/) (2026)
- [Position: We Need An Algorithmic Understanding of Generative AI](https://mlsanity.com/paper/2507.07544/) (2025)
- [RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasoner](https://mlsanity.com/paper/2410.23912/) (2024)
- [Provable Benefits of In-Tool Learning for Large Language Models](https://mlsanity.com/paper/2508.20755/) (2025)
- [Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories](https://mlsanity.com/paper/2511.07368/) (2025)
- [Markovian Generation Chains in Large Language Models](https://mlsanity.com/paper/2603.11228/) (2026)
- [Multiple Choice Learning of Low-Rank Adapters for Language Modeling](https://mlsanity.com/paper/2507.10419/) (2025)
- [On the Notion that Language Models Reason](https://mlsanity.com/paper/2511.11810/) (2025)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Safety Alignment Depth in Large Language Models: A Markov Chain Perspective](https://mlsanity.com/paper/2502.00669/) (2025)
- [In-Context Learning can Perform Continual Learning Like Humans](https://mlsanity.com/paper/2509.22764/) (2025)
- [The 4/δ Bound: Designing Predictable LLM-Verifier Systems for Formal Method Guarantee](https://mlsanity.com/paper/2512.02080/) (2025)
- [Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs](https://mlsanity.com/paper/2607.06145/) (2026)
- [Optimal Watermark Localization in Mixed-Source Large Language Model Texts](https://mlsanity.com/paper/2608.14906/) (2026)
- [Reasoning-Aware Query-Focused Summarization over Multi-Table Data](https://mlsanity.com/paper/2412.08970/) (2024)
- [Context-Aware Regularization with Markovian Integration for Attention-Based Nucleotide Analysis](https://mlsanity.com/paper/2507.09378/) (2025)
- [Human-AI collaboration or obedient and often clueless AI in instruct, serve, repeat dynamics?](https://mlsanity.com/paper/2508.10919/) (2025)
- [Additive Multi-Step Markov Chains and the Curse of Dimensionality in Large Language Models](https://mlsanity.com/paper/2603.04412/) (2026)
- [Memory as a Markov Matrix: Sample Efficient Knowledge Expansion via Token-to-Dictionary Mapping](https://mlsanity.com/paper/2605.04308/) (2026)
- [Position: Let's Develop Data Probes to Fundamentally Understand How Data Affects LLM Performance](https://mlsanity.com/paper/2605.18801/) (2026)

## Abstract (arXiv)

Large language models (LLMs) are remarkably efficient across a wide range of natural language processing tasks and well beyond them. However, a comprehensive theoretical analysis of the LLMs' generalization capabilities remains elusive. In our paper, we approach this task by drawing an equivalence between autoregressive transformer-based language models and Markov chains defined on a finite state space. This allows us to study the multi-step inference mechanism of LLMs from first principles. We relate the obtained results to the pathological behavior observed with LLMs such as repetitions and incoherent replies with high temperature. Finally, we leverage the proposed formalization to derive pre-training and in-context learning generalization bounds for LLMs under realistic data and model assumptions. Experiments with the most recent Llama and Gemma herds of models show that our theory correctly captures their behavior in practice.