Research map / Architectures and efficiency / Attention and transformers
From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers
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 that a one-layer self-attention model is equivalent to a context-conditioned Markov chain (CCMC), derives coverage conditions and sample-complexity rates for learning it from prompts, and analyzes single-trajectory generation, revealing a distribution-collapse (winner-takes-all) phenomenon.
Problem
Understanding how a one-layer self-attention generative model can be learned from sampled (prompt, output) pairs or a single generation trajectory, and why generated text becomes repetitive.
Approach
Establishes that sampling-from-softmax in one self-attention layer equals a context-conditioned Markov chain whose transitions are reweighted by prompt token frequencies; under weight-tying and linear-independence assumptions the maximum-likelihood problem becomes convex, enabling consistency (graph connectivity), O(K^2/n) rates, and a winner-takes-all collapse analysis for single trajectories.
Key results
- Sample complexity of order K^2 log(n/(Kδ))/n for squared parameter error under connected co-occurrence graphs.
- For K=2 with weak-token transition p<1/2, the ratio of weak to strong token frequency goes to zero, so the dynamics collapse onto one token.
- Weak-to-weak transition counts grow super-logarithmically for p>1/3 and sub-logarithmically for p<1/3 in simulations, matching the t^{-2q} Borel-Cantelli prediction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generate a single trajectory autoregressively from initial prompt [6] | Randomly initialized 1-layer self-attention · Single-trajectory generation | token diversity | Hurt |
Surprising findings
- Single-trajectory generation collapses to sampling one or very few tokens even though all tokens are visited infinitely often.
Limitations
- Relies on strong assumptions: linearly independent token embeddings, weight tying with C E^T = I, and d >= K, which makes the output restricted to prompt tokens.
- Analysis restricted to one attention layer, no multi-layer or positional-encoding experiments beyond lemma-level results.
- Some single-trajectory results are heuristic/non-rigorous (weak-to-weak transition growth).
Experimental setup
Datasets: synthetic prompts and trajectories sampled from randomly initialized or ground-truth one-layer self-attention models
Metrics: negative log-likelihood estimation error token frequency
Builds on: Transformer attention Markov chain estimation theory
Closest papers by meaning
- The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains (NeurIPS 2024 · similarity 0.89)
- A Phase Transition between Positional and Semantic Learning in a Solvable Model of Dot-Product Attention (NeurIPS 2024 · similarity 0.88)
- Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers (NeurIPS 2024 · similarity 0.87)
- Selective Induction Heads: How Transformers Select Causal Structures in Context (ICLR 2025 · similarity 0.87)
- Transformers on Markov data: Constant depth suffices (NeurIPS 2024 · similarity 0.87)
- Generative Adapter: Contextualizing Language Models in Parameters with A Single Forward Pass (ICLR 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.