What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains
Chanakya Ekbote [email protected], Marco Bondaschi, Nived Rajaraman, Jason D. Lee, Michael Gastpar, Ashok Vardhan Makkuva, Paul Pu Liang - Massachusetts Institute of Technology - École Polytechnique Fédérale de Lausanne - University of California, Berkeley - Princeton University · 2025
Read What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains by Chanakya Ekbote [email protected], Marco Bondaschi, Nived Rajaraman, Jason D. Lee, Michael Gastpar, Ashok Vardhan Makkuva, Paul Pu Liang - Massachusetts Institute of Technology - École Polytechnique Fédérale de Lausanne - University of California, Berkeley - Princeton University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07208.txt.
Introduction
Chanakya Ekbote and co-authors prove, in a 2025 paper, that a two-layer transformer can mimic the pattern-matching circuits behind learning from context, for sequences of any memory length. Transformers learn new tasks from examples in their input, a skill traced to circuits called induction heads. Those circuits act like conditional tallies of what followed what in the past. Earlier work showed two layers handle the simplest case but left open whether they could cover longer-range dependencies.
The authors settle the question: one attention head in each of two layers suffices for a Markov source of any order. That makes the depth-versus-memory trade-off fully tight. They also study how such a circuit forms during training, using a simplified first-order case. The results sharpen the theory of why depth matters so much in these models.
Catalog record
| CREATOR | Chanakya Ekbote [email protected], Marco Bondaschi, Nived Rajaraman, Jason D. Lee, Michael Gastpar, Ashok Vardhan Makkuva, Paul Pu Liang - Massachusetts Institute of Technology - École Polytechnique Fédérale de Lausanne - University of California, Berkeley - Princeton University |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 190 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-07208
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains Chanakya Ekbote [email protected], Marco Bondaschi, Nived Rajaraman, Jason D. Lee, Michael Gastpar, Ashok Vardhan Makkuva, Paul Pu Liang - Massachusetts Institute of Technology - École Polytechnique Fédérale de Lausanne - University of California, Berkeley - Princeton University Abstract In-context learning (ICL) is a hallmark capability of transformers, through which trained models learn to adapt to new tasks by leveraging information from the input context. Prior work has shown that ICL emerges in transformers due to the presence of special circuits called induction heads. Given the equivalence between induction heads and conditional k k -grams, a recent line of work modeling sequential inputs as Markov processes has revealed the fundamental impact of model depth on its ICL capabilities: while a two-layer transformer can efficiently represent a conditional 1 1 -gram model, its single-layer counterpart cannot solve the task unless it is exponentially large. However, for higher order Markov sources, the best known constructions require at least three layers (each with a single attention head) — leaving open the question: can a two-layer single-head transformer represent any k th k^{\text{th}} -order Markov process? In this paper, we precisely address this and theoretically show that a two-layer transformer with one head per layer can indeed represent any conditional k k -gram. Thus, our result provides the tightest known characterization of the interplay between transformer depth and Markov order for ICL. Building on this, we further analyze the learning dynamics of our two-layer construction, focusing on a simplified variant for first-order Markov chains, illustrating how effective in-context representations emerge during training. Together, these results deepen our current understanding of transformer-based ICL and illustrate how even shallow architectures can surprisingly exhibit strong ICL capabilities on structured sequence modeling tasks. Code is available at https://anonymous.4open.science/r/markov-llm-depth-icl-63F0 . 1 Introduction Transformers, powered by the attention mechanism, have emerged as the dominant architecture in machine learning, achieving state-of-the-art performance across a wide range of domains, including natural language processing [ 6 ] , computer vision [ 32 ] , and complex reasoning tasks [ 23 , 36 ] . A key factor underpinning this success is their ability to efficiently model sequences and perform in-context learning (ICL)—adapting to unseen tasks during inference by leveraging the relevant input context [ 22 ] . It is well known that ICL emerges in transformers due to the presence of special circuits called induction heads [ 22 , 31 ] . Intuitively, these circuits enable transformers to implement a “copy-and-match” mechanism by copying earlier tokens from the input and matching them with the desired context for next-token prediction. For example, a first-order induction head mimics the functionality [\ldots,A,B,\ldots,A]\to B . Capitalizing on the connection between induction heads and conditional k -gram models, a recent active line of work has leveraged k^{\text{th}} -order Markov chains as a simple yet powerful framework to analyze how transformers learn induction heads, with the framework referred to as Markov-ICL [ 10 , 20 , 26 , 7 , 5 ] . In particular, using Markovian input sequences, the goal is to understand how transformers learn to represent conditional k -grams–equivalent to k^{\text{th}} -order induction heads (Def. 2.1 ). Building upon the Markov-ICL setting, Bietti et al. 2023 , Edelman et al. 2024 , and Nichani et al. 2024 demonstrate that a conditional 1 -gram model can be efficiently represented by a two-layer (i.e., two attention layers), single-head transformer. In contrast, Sanford et al. 2024 show that a one-layer, single-head counterpart cannot solve this task unless its hidden dimension is exponentially larger than that of the two-layer model. On the other hand, for higher-order processes, Edelman et al. 2024 and Nichani et al. 2024 argue that low-depth transformers need the number of heads scaling linearly in k , in order to learn k^{\text{th}} -order Markov processes. However, Rajaraman et al. 2024 establish a surprising result that a three-layer, single-head transformer can represent the conditional k -gram model for any k\geq 1 , and thereby learn k^{\text{th}} -order Markov models in-context. Together, these findings illustrate that while a 1 -layer transformer cannot efficiently represent an induction head, a 3 -layer model with 1 head per layer suffices for all Markov orders k\geq 1 . However, these results leave open a natural and important question: Can a two-layer, single-head transformer learn k^{\text{th}} -order Markov processes in-context? In this paper, we approach this question from two perspectives—representational power and learning dynamics. In particular, we affirmatively answer this on the representation front and make partial progress on the learning dynamics through the following key contributions: Main Contributions. 1. Improving upon the best known three-layer construction, we prove that a two-layer single-head transformer is sufficient to represent the conditional k -gram model, and thus can learn k\textsuperscript{th} -order Markov chains in-context (Sec. 4 ). To the best of our knowledge, this is the tightest characterization of transformer depth and Markov order for Markov-ICL. 2. In the course of establishing this result, we uncover an interesting tradeoff between depth and width: the existing three-layer single-head construction (depth is three, width is one) is equivalent to a two-layer architecture with two heads in the first layer and one in the second (depth is two, width is two). (Sec. 3 ) 3. For first-order Markov chains, we prove that gradient descent on our simplified two-layer transformer learns an induction head, and thereby the in-context conditional empirical distribution. (Sec. 5 ) Previous works Markov order Architecture # Parameters Bietti et al. 2023 1 2 -layer, 1 -head 9d^{2}+dS+Td Edelman et al. 2024 1 2 -layer, 1 -head 21S^{2}+3TS Nichani et al. 2024 k 2 -layer, k -head (k+(k+1)^{2})(S+T)^{2}+T(S+T) Rajaraman et al. 2024 k 3 -layer, 1 -head 15(3+6S)^{2}+(S+T)(3+6S) Ours k 2 -layer, 1 -head 9(3+6S)^{2}+(S+T)(3+6S) Table 1 : Comparison with prior works on transformers with Markov-ICL. Here k\geq 1 is the Markov order, T the sequence length, and S the state-space (vocabulary) size. Note that Bietti et al. 2023 do not explicitly state what d is and assume it to be large enough. To the best of our knowledge, our work obtains the tightest known characterization of transformer depth and Markov order for higher-order processes. The bit precision for our representation results is the same as that of Rajaraman et al. 2024 : it suffices to have \Omega(\log(T)+k) bits per parameter, with \mathcal{O}(1/T) additive approximation error. Comparison with other Markov-ICL works vis-a-vis transformer architecture. In this paper, as we focus on higher-order processes, we consider the general transformer architecture (Sec. 2.2 ) closer to real-world models with relative positional encodings [ 30 ] , softmax attention [ 32 ] , MLPs, and layer normalization [ 2 ] . For first-order processes, past literature has considered simplified variants: Bietti et al. 2023 use frozen and fixed random embeddings with no MLPs in the first layer, Edelman et al. 2024 consider attention-only models with no MLPs and embeddings, and Nichani et al. 2024 study a variant called disentangled transformer , splitting the residual and attention streams, with the hidden dimension scaling with depth. While our gradient descent result for first-order processes (Sec. 5 ) is similar to that of Nichani et al. 2024 , the