From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers

M. Emrullah Ildiz, Yixiao Huang, Yingcong Li, Ankit Singh Rawat, Samet Oymak

TL;DR

This paper mathematically bridges the gap between the non-Markovian nature of transformers and the well-understood theory of Markov chains. By introducing Context-Conditioned Markov Chains (CCMC), the authors provide a rigorous framework to analyze the learning dynamics of 1-layer self-attention, establishing conditions for consistent model estimation and offering a mathematical explanation for why large language models (LLMs) often fall into repetitive "loops."

What Problem Does This Paper Address?

While transformers dominate modern AI, their internal dynamics—especially during autoregressive text generation—remain theoretically opaque. Standard Markov chains, where the next state depends only on the current one, are easy to analyze but fail to capture the "long-memory" property of self-attention, where the next token depends on the entire preceding context.

The authors tackle three core questions:

  1. Can self-attention be formally mapped to a fundamental model like a Markov chain?
  2. Under what conditions can we consistently learn a transformer's weights from data?
  3. Why do LLMs exhibit "distribution collapse," where they start repeating the same few tokens indefinitely?

Methods

The researchers introduce a novel mathematical object: the Context-Conditioned Markov Chain (CCMC). In a CCMC, the transition probabilities of a base Markov chain are weighted by the empirical frequencies of tokens present in the current input prompt.

Key methodological steps include:

  • Formal Equivalence: Proving that a 1-layer self-attention head is mathematically equivalent to a CCMC, provided the token embeddings are linearly independent.
  • Convexification: Showing that under this mapping, the typically non-convex optimization of attention weights becomes a convex maximum likelihood estimation problem, making it tractable for theoretical analysis.
  • Co-occurrence Graphs: Developing a graph-theoretic approach to define "coverage." They represent training data as graphs where nodes are tokens and edges represent tokens appearing together in a prompt.
  • Trajectory Analysis: Studying the "single-trajectory" setting, where a model is trained on its own generated output, to observe how generation dynamics evolve over time.
Figure 1: Demonstration of Definition 2.1. We provide an example where the vocabulary size K = 3 and the input prompt X = [1, 2, 1], which results in a frequency vector m(X). P represents the transition matrix of the base Markov chain.

Datasets

The study is primarily theoretical, supported by controlled empirical experiments:

  • Synthetic Generative Models: 1-layer self-attention models with a vocabulary size of $K=6$ were used to generate data for testing learnability and repetition.
  • IID Prompt-Output Pairs: Used to establish sample complexity bounds.
  • Single-Trajectory Sequences: Autoregressively generated sequences of length up to 500 were analyzed to study the "winner-takes-all" phenomenon.

Key Insights and Ideas

  • The "Aha" Mapping: Self-attention isn't just a complex black box; it acts as a Markov chain whose transition matrix is dynamically "masked" by the frequency of tokens in the context.
  • Connectivity is Learnability: For a model to be learned consistently, the training prompts must "cover" the vocabulary such that the co-occurrence graphs are connected. If your training data never shows certain tokens appearing together, the model cannot learn the relationship between them.
  • Winner-Takes-All Repetition: The paper provides a mathematical proof for the "repetition problem." Because self-attention reinforces tokens that have already appeared frequently in the context, it creates a positive feedback loop. Eventually, a few tokens dominate the probability distribution, causing the model to collapse into a repetitive state.
Figure 3: Illustration of co-occurrence graphs for the self-attention (Left) and cross-attention (Right) models. We fit the same input examples where the only difference is the use of self- vs cross-attention (which includes vs excludes the query token ‘1’ from the list of key tokens). Following Theorem 3.4, in the cross-attention setting, where the token ‘1’ is not contained in the prompt, the co-occurrence graph becomes disconnected, resulting in inconsistent estimation. In contrast, the estimation is consistent for the self-attention model since both inputs share the same query token within their key tokens.

Key Results

  • Consistency Theorem: The authors prove that estimation of the transition matrix is consistent if and only if the co-occurrence graphs $G^{(k)}$ are connected for all tokens $k$.
  • Sample Complexity: They establish a fast statistical learning rate of $O(K^2/n)$, where $K$ is the vocabulary size and $n$ is the number of samples.
  • Repetition Phase Transition: In a simplified 2-token setting, they identified a phase transition at a transition probability of $p=1/3$. If the probability of transitioning to a "weak" token is below this threshold, the model is mathematically guaranteed to collapse into repeating the "strong" token.
Figure 6: Growth of transitions showing the sub-logarithmic vs. super-logarithmic regimes that lead to inconsistent estimation.

Limitations and Future Work

The primary limitation is the focus on 1-layer models. While this provides a clean mathematical foundation, real-world LLMs have dozens of layers with complex hierarchical interactions. Additionally, the proofs rely on an Assumption of Over-parameterization ($d \ge K$), where the embedding dimension is at least as large as the vocabulary size.

Future research directions suggested by the authors include:

  • Extending the CCMC framework to multi-layer transformers.
  • Studying the impact of the End-Of-Sequence (EOS) token on generation stability.
  • Analyzing the low-rank regime ($d \ll K$), which is highly relevant to techniques like LoRA (Low-Rank Adaptation).

Summary updated

Abstract

Modern language models rely on the transformer architecture and attention mechanism to perform language understanding and text generation. In this work, we study learning a 1-layer self-attention model from a set of prompts and associated output data sampled from the model. We first establish a precise mapping between the self-attention mechanism and Markov models: Inputting a prompt to the model samples the output token according to a context-conditioned Markov chain (CCMC) which weights the transition matrix of a base Markov chain. Additionally, incorporating positional encoding results in position-dependent scaling of the transition probabilities. Building on this formalism, we develop identifiability/coverage conditions for the prompt distribution that guarantee consistent estimation and establish sample complexity guarantees under IID samples. Finally, we study the problem of learning from a single output trajectory generated from an initial prompt. We characterize an intriguing winner-takes-all phenomenon where the generative process implemented by self-attention collapses into sampling a limited subset of tokens due to its non-mixing nature. This provides a mathematical explanation to the tendency of modern LLMs to generate repetitive text. In summary, the equivalence to CCMC provides a simple but powerful framework to study self-attention and its properties.
BibTeX
@inproceedings{ildiz2024from,
  author = {M. Emrullah Ildiz and Yixiao Huang and Yingcong Li and Ankit Singh Rawat and Samet Oymak},
  title = {{From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=72oT4mPLUb},
}
Figure