Research map / Architectures and efficiency / Attention and transformers
Transformers on Markov data: Constant depth suffices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows empirically that small fixed-depth 1-head transformers learn k-th order Markov chains for large k, and theoretically that a 3-layer 1-head transformer with layer norm can represent the in-context conditional k-gram, while attention-only models need log-depth or many heads.
Problem
Prior work suggested low-depth transformers need the number of heads to scale linearly with the Markov order k to learn k-th order Markov processes in-context; the paper asks how depth, heads, and non-linearity interact in representing k-th order Markov sources.
Approach
Builds a constant-depth construction in which layer normalization acts as an L2-normalizer, turning dyadic-sum encodings of the last k symbols into a unit vector so that a softmax-based attention can match k-length histories in a single head; attention-only models need O(log k) layers, and lower bounds are proven under an input-independent attention assumption.
Key results
- A 2-layer 1-head and a 3-layer 1-head transformer reach low test loss on random Markov sources for k up to 4 and 8 respectively, averaged over 3 runs.
- Theorem: a 3-layer, 1-head transformer with relative position encodings and layer normalization can represent the conditional k-gram with embedding dimension O(S).
- Attention-only transformers need L = ceil(log2(k+1)) layers with 1 head per layer, and under an input-independent attention assumption, 2-layer 1-head models cannot realize a k-th order induction head for k >= 4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a 2-layer, 1-head transformer | Transformer trained on random Markov data · Order-4 Markov data | test loss | Helped |
| Use a 3-layer, 1-head transformer | Transformer trained on random Markov data · Order-8 Markov data | test loss | Helped |
| Add layer normalization and feedforward nonlinearity | Transformer representing conditional k-grams · k-th order Markov data | representation of conditional k-grams | Helped |
Surprising findings
- Single-head, 2- and 3-layer transformers learn order-4 and order-8 Markov chains, contradicting prior claims that single-head models cannot beat bigram performance.
- Layer normalization enables constant-depth, single-head representation of k-gram models, whereas attention-only models require logarithmic depth or many heads.
Limitations
- Lower bounds rely on an assumption that attention patterns are independent of the input sequence, so they are conditional.
- Representability does not establish that gradient descent learns these constructions; learning dynamics are left open.
- Constructions assume infinite attention temperature limits and bit precision only discussed as remarks (O(log T) bits for O(1/T) error).
Experimental setup
Datasets: synthetic k-th order Markov sequences (Dirichlet(1) prior)
Benchmarks: synthetic k-th order Markov sources (gap to optimal test loss)
Metrics: test loss gap to optimal (Bayes) loss
Baselines: 2-layer attention-only transformer with k heads Bayes-optimal conditional k-gram estimate
Builds on: induction heads conditional k-gram (Bayes-optimal in-context estimator)
Closest papers by meaning
- What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains (NeurIPS 2025 · similarity 0.90)
- Local to Global: Learning Dynamics and Effect of Initialization for Transformers (NeurIPS 2024 · similarity 0.89)
- Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers (NeurIPS 2024 · similarity 0.88)
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.88)
- Selective Induction Heads: How Transformers Select Causal Structures in Context (ICLR 2025 · similarity 0.88)
- How Transformers Learn Structured Data: Insights From Hierarchical Filtering (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.