# Transformers on Markov Data: Constant Depth Suffices

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 25 Jul 2024.

## Builds on (most cited first, 20 of 20)

- [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)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Localizing Model Behavior with Path Patching](https://mlsanity.com/paper/2304.05969/) (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)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)
- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [Toward a Theory of Tokenization in LLMs](https://mlsanity.com/paper/2404.08335/) (2024)

## Built on by (most cited first, 27 of 27)

- [Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Points](https://mlsanity.com/paper/2508.12837/) (2025)
- [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](https://mlsanity.com/paper/2502.10178/) (2025)
- [Transformers Handle Endogeneity in In-Context Linear Regression](https://mlsanity.com/paper/2410.01265/) (2024)
- [How Transformers Get Rich: Approximation and Dynamics Analysis](https://mlsanity.com/paper/2410.11474/) (2024)
- [KV Shifting Attention Enhances Language Modeling](https://mlsanity.com/paper/2411.19574/) (2024)
- [Selective Induction Heads: How Transformers Select Causal Structures In Context](https://mlsanity.com/paper/2509.08184/) (2025)
- [In-Context Occam's Razor: How Transformers Prefer Simpler Hypotheses on the Fly](https://mlsanity.com/paper/2506.19351/) (2025)
- [In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-Separation](https://mlsanity.com/paper/2502.08136/) (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)
- [An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains](https://mlsanity.com/paper/2410.05493/) (2024)
- [Latent Concept Disentanglement in Transformer-based Language Models](https://mlsanity.com/paper/2506.16975/) (2025)
- [Facts in Stats: Impacts of Pretraining Diversity on Language Model Generalization](https://mlsanity.com/paper/2510.16096/) (2025)
- [Understanding Contextual Recall in Transformers: How Finetuning Enables In-Context Reasoning over Pretraining Knowledge](https://mlsanity.com/paper/2603.20969/) (2026)
- [Benchmarking graph construction by large language models for coherence-driven inference](https://mlsanity.com/paper/2502.13953/) (2025)
- [Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information](https://mlsanity.com/paper/2510.25542/) (2025)
- [Hierarchical Latent Structures in Data Generation Process Unify Mechanistic Phenomena across Scale](https://mlsanity.com/paper/2603.06592/) (2026)
- [Transformers Learn Latent Mixture Models In-Context via Mirror Descent](https://mlsanity.com/paper/2604.10848/) (2026)
- [Effective Context in Transformers: An Analysis of Fragmentation and Tokenization](https://mlsanity.com/paper/2605.13485/) (2026)
- [Induction Heads Interpolate N-Grams](https://mlsanity.com/paper/2607.02800/) (2026)
- [Decomposing Prediction Mechanisms for In-Context Recall](https://mlsanity.com/paper/2507.01414/) (2025)
- [Coherence-driven inference for cybersecurity](https://mlsanity.com/paper/2509.18520/) (2025)
- [Performance-Efficiency Tradeoffs in Transformers: An Approximation Theory Perspective](https://mlsanity.com/paper/2510.03784/) (2025)
- [Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions](https://mlsanity.com/paper/2510.18638/) (2025)
- [Gaussian Match-and-Copy: A Minimalist Benchmark for Studying Transformer Induction](https://mlsanity.com/paper/2602.07562/) (2026)
- [Position: Let's Develop Data Probes to Fundamentally Understand How Data Affects LLM Performance](https://mlsanity.com/paper/2605.18801/) (2026)
- [Learning Source Structure: Bayesian Prediction with Transformers](https://mlsanity.com/paper/2610.18725/) (2026)

## Abstract (arXiv)

Attention-based transformers have been remarkably successful at modeling generative processes across various domains and modalities. In this paper, we study the behavior of transformers on data drawn from kth Markov processes, where the conditional distribution of the next symbol in a sequence depends on the previous k symbols observed. We observe a surprising phenomenon empirically which contradicts previous findings: when trained for sufficiently long, a transformer with a fixed depth and 1 head per layer is able to achieve low test loss on sequences drawn from kth Markov sources, even as k grows. Furthermore, this low test loss is achieved by the transformer's ability to represent and learn the in-context conditional empirical distribution. On the theoretical side, our main result is that a transformer with a single head and three layers can represent the in-context conditional empirical distribution for kth Markov sources, concurring with our empirical observations. Along the way, we prove that textitattention-only transformers with O(log2(k)) layers can represent the in-context conditional empirical distribution by composing induction heads to track the previous k symbols in the sequence. These results provide more insight into our current understanding of the mechanisms by which transformers learn to capture context, by understanding their behavior on Markov sources.