mlsanityData to 14 Oct 2026

Large Language Models as Markov Chains

arXiv 2410.02724 ↗First posted 3 Oct 2024stat.ML cs.AI cs.CLcited by 35

Not on the map. Why?

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.

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

40 of 57 references.

References · 40

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023GPT-4 Technical Reportcited by 18,396
  5. 2024The Llama 3 Herd of Modelscited by 14,715
  6. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  7. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  8. 2015Distilling the Knowledge in a Neural Networkcited by 10,324
  9. 2023Mistral 7Bcited by 3,164
  10. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  11. 2019Root Mean Square Layer Normalizationcited by 1,480
  12. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 938
28 more
  1. 2020How Much Knowledge Can You Pack Into the Parameters of a Language Model?cited by 719
  2. 2020Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuningcited by 671
  3. 2023Large Language Models Are Zero-Shot Time Series Forecasterscited by 500
  4. 2023Sentiment Analysis in the Era of Large Language Models: A Reality Checkcited by 268
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  6. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 222
  7. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  8. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  9. 2023The Learnability of In-Context Learningcited by 127
  10. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 118
  11. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 118
  12. 2024Tokenization counts: the impact of tokenization on arithmetic in frontier LLMscited by 115
  13. 2023Tokenizer Choice For LLM Training: Negligible or Crucial?cited by 108
  14. 2023Non-Vacuous Generalization Bounds for Large Language Modelscited by 53
  15. 2024Transformers are Universal In-context Learnerscited by 43
  16. 2024An Information-Theoretic Analysis of In-Context Learningcited by 40
  17. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 40
  18. 2024Transformers are Minimax Optimal Nonparametric In-Context Learnerscited by 37
  19. 2023Scaling Laws for Associative Memoriescited by 35
  20. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  21. 2023Probing the Creativity of Large Language Models: Can models produce divergent semantic association?cited by 33
  22. 2024LLMs learn governing principles of dynamical systems, revealing an in-context neural scaling lawcited by 32
  23. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methodscited by 29
  24. 2023xVal: A Continuous Numerical Tokenization for Scientific Language Modelscited by 27
  25. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  26. 2024Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Modelscited by 25
  27. 2023Generalization bounds for neural ordinary differential equations and deep residual networkscited by 21
  28. 2018Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Spacecited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 19; 2026: 13.

35 papers.

Sort:

By area:

  1. 2025Atom of Thoughts for Markov LLM Test-Time Scalingcited by 54
  2. 2025Fine-Tuning Discrete Diffusion Models with Policy Gradient Methodscited by 38
  3. 2025The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representationscited by 29
  4. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  5. 2025Context parroting: A simple but tough-to-beat baseline for foundation models in scientific machine learningcited by 18
  6. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 16
  7. 2024A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMscited by 15
  8. 2025Recitation over Reasoning: How Cutting-Edge Language Models Can Fail on Elementary School-Level Reasoning Problems?cited by 15
  9. 2025Text-Trained LLMs Can Zero-Shot Extrapolate PDE Dynamics, Revealing a Three-Stage In-Context Learning Mechanismcited by 7
  10. 2025Clip Your Sequences Fairly: Enforcing Length Fairness for Sequence-Level RLcited by 7
  11. 2026Old Habits Die Hard: How Conversational History Geometrically Traps LLMscited by 6
  12. 2025Position: We Need An Algorithmic Understanding of Generative AIcited by 5
23 more
  1. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  2. 2025Provable Benefits of In-Tool Learning for Large Language Modelscited by 4
  3. 2025Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectoriescited by 4
  4. 2026Markovian Generation Chains in Large Language Modelscited by 3
  5. 2025Multiple Choice Learning of Low-Rank Adapters for Language Modelingcited by 2
  6. 2025On the Notion that Language Models Reasoncited by 2
  7. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  8. 2025Safety Alignment Depth in Large Language Models: A Markov Chain Perspectivecited by 1
  9. 2025In-Context Learning can Perform Continual Learning Like Humanscited by 1
  10. 2025The 4/δ Bound: Designing Predictable LLM-Verifier Systems for Formal Method Guaranteecited by 1
  11. 2026Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMscited by 1
  12. 2026Optimal Watermark Localization in Mixed-Source Large Language Model Textscited by 1
  13. 2024Reasoning-Aware Query-Focused Summarization over Multi-Table Datacited by 0
  14. 2025Context-Aware Regularization with Markovian Integration for Attention-Based Nucleotide Analysiscited by 0
  15. 2025Human-AI collaboration or obedient and often clueless AI in instruct, serve, repeat dynamics?cited by 0
  16. 2026Additive Multi-Step Markov Chains and the Curse of Dimensionality in Large Language Modelscited by 0
  17. 2026Memory as a Markov Matrix: Sample Efficient Knowledge Expansion via Token-to-Dictionary Mappingcited by 0
  18. 2026Position: Let's Develop Data Probes to Fundamentally Understand How Data Affects LLM Performancecited by 0
  19. 2026Modeling Memory-Dependent Reliability of LLMs: A Hidden Markov Modelcited by 0
  20. 2026A Graph Signal Processing Perspective on Numerical Sequence Representations in LLM In-Context Learningcited by 0
  21. 2026A Systematic Evaluation of Cross-Lingual Consistency Enhancement Methods in Multilingual Language Modelscited by 0
  22. 2026Robust Detection of LLM-Generated Text under Contaminationcited by 0
  23. 2026The Asymptotics of Language Model Alignment with Memorycited by 0