Competition Dynamics Shape Algorithmic Phases of In-Context Learning
Authors: Core Francisco Park
Ekdeep Singh Lubana
Hidenori Tanaka
Venue: ICLR 2025 Spotlight (2025)
Keywords: In-Context Learning
Circuit Competition
Markov Chains
Training Dynamics
Generalization
Primary area: interpretability and explainable AI
TL;DR: In-context learning consists of phases of multiple algorithmic solutions, many phenomena are explained by this decomposition.

Abstract: In-Context Learning (ICL) has significantly expanded the general-purpose nature of large language models, allowing them to adapt to novel tasks using merely the inputted context. This has motivated a series of papers that analyze tractable synthetic domains and postulate precise mechanisms that may underlie ICL. However, the use of relatively distinct setups that often lack a sequence modeling nature to them makes it unclear how general the reported insights from such studies are. Motivated by this, we propose a synthetic sequence modeling task that involves learning to simulate a finite mixture of Markov chains. As we show, models trained on this task reproduce most well-known results on ICL, hence offering a unified setting for studying the concept. Building on this setup, we demonstrate we can explain a model’s behavior by decomposing it into four broad algorithms that combine a fuzzy retrieval vs. inference approach with either unigram or bigram statistics of the context. These algorithms engage in a competitive dynamics to dominate model behavior, with the precise experimental conditions dictating which algorithm ends up superseding others: e.g., we find merely varying context size or amount of training yields (at times sharp) transitions between which algorithm dictates the model behavior, revealing a mechanism that explains the transient nature of ICL. In this sense, we argue ICL is best thought of as a mixture of different algorithms, each with its own peculiarities, instead of a monolithic capability. This also implies that making general claims about ICL that hold universally across all settings may be infeasible.

Published as a conference paper at ICLR 2025
COMPETITION DYNAMICS SHAPE ALGORIHHMIC PHASES OF IN-CONTEXT LEARNING
Core Francisco Park 1,2,3, Park!.2.3. Ekkeep Singh Lubana!: 1.3,,, Itamar Pres*, Hidenori Tanaka"
I CBB-NTT Program in Physics of Intelligence, Harvard University Department of Physics, Harvard University
PPyyscss& & Informatics Laboratories, NTT Research, Inc.
4EECS Department, University of Michigan, Ann Arbor
ABSTRACT
In-Context Learning (ICL) has significantly expanded the general-purpose nature of large language models, allowing them to adapt to novel tasks using merely the inputted context. This has motivated series of papers that analyze tractable synthetic domains and postulate precise mechanisms that may underlie ICL. How- ever, the use of relatively distinet setups that often lack a sequence modeling na- ture to them makes it unclear how general the reported insights from such studies are. Motivated by this, we propose synthetic sequence modeling task that in- volves learning to simulate finite mixture of Markov chains. As we show, mod- els trained on this task reproduce most well-known results on ICL., hence offering unified setting for studying the concept. Building on this setup, demonstrate we can explain a model's behavior by decomposing it into four broad algorithms that combine fuzzy retrieval vs. inference approach with either unigram or bi- gram statistics of the context. These algorithms engage in a competition dynamics dominate model behavior. with the precise experimental conditions dictating which algorithm ends up superseding others: e.g., we find merely varying con- text size or amount of training yields (at times sharp) transitions between which algorithm dictates the model behavior, revealing mechanism that explains the transient nature of ICL. In this sense, we argue ICL best thought of a mixture of different algorithms, each with its own peculiarities, instead of a monolithic capability. This also implies that making general claims about ICL that hold uni- versally across all settings may be infeasible.
INTRODUCTION
In-Context Learning (ICL)-the the ability to perform novel tasks by merely using the inputted context-har has substantially expanded the general-purpor nature of large language models (LLMS) (Brown et al., 2020; Wei et al., 2022), allowing them to solve a broader spectrum of prob- lems than they may have been initially trained for (Gemini Team, 2023; Qin et al., 2023; Huang et al., 2022; Bai et al., 2022). To better understand the mechanisms underlying ICL, series of papers have designed toy, synthetic domains that are amenable to rapid experimentation and can offer precise hypotheses into how this capability operates. This line of work has established rich phenomenology. demonstrating, e.g., the importance of specialized attention heads (aka induction heads) (Olsson et al., 2022; Edelman et al., 2024; Singh al., 2024), change in ICL abilities as a function of data diversity (Raventós et al., 2023; Lu et al., 2024; Kirsch et al., 2022), the non- monotonic trend in test performance as context is increased (Min al., 2022; Lin Lee, 2024), and the transient nature of ICL with training time (Singh et al., 2023; Anand et al., 2024).
Despite the substantial progress highlighted above, we note unified account of ICL is still lack- ing. This can be partially attributed to the fact that prior work often focuses on rather disparate setups to develop its findings e.g., linear regression (Garg al., 2023; Von Oswald et al., 2023; Akyürek et al., 2023; Bai et al., 2024), classification (Chan et al., 2022a;b; Reddy, 2023; Singh et al., 2023; 2024), and probabilistic automata (Akyürek et al., 2024; Edelman et al., 2024; Bigelow al.,
* EEqull contribution. Contact: corefranci scopa proparkkg.... ha harvard.ees edu, {ekdeepl lubana, hi denori har.aaarddd..raadddeeeeee presi @umi ahheed..

---

Published as a conference paper at ICLR 2025
Data Diversity Threshold
i Bounded Efficacy
14
0.3
N Training Chains
2.
2
0.4
2.0
2
Fhanngg chara
10"
Contect Sae
b) Induction Head Emergence
20
c) Early Ascent
2
Cbt. Size
0.20
2
100
vedc
49
613
7525
160
0.40
N Steps
92318
0x10
100
Transient Nature
d) Task Retrieval vs Task Learning
Uni-Ret
Bi-Ret
2
Contre
Uni-Inf
Bi-Inf
Algorithmic phase diagram for finite Markov mixtures task. We propose study ICL phenomena through a minimal experimental system: Transformers trained on sequence data generated by finite mixture of Markov chains. This setup turns out to be extremely rich, capturing most (if not all) known phenomenology of ICL, but still being simple enough to be amenable to theoretical modeling. We identify four distinct, interpretable algorithmic solutions and characterize the transitions between them as functions of data diversity, optimization steps, and context size- labeled algorithmic phases. Considering the corresponding phase diagram (middle panel), we find part of the rich phenomenology of ICI. emerges from competing algorithmic strategies promoted or suppressed by broader experimental configurations. Specifically, our framework captures an array of known phenomena: a) Data diversity threshold (Raventós et al., 2023); b) Emergence of induction heads (Edelman et al., 2024); c) Transient nature (Singh et al., 2023); d) Task retrieval and task learning phases (Min et al., 2022); e) Early ascent of risk (Xie et al., 2021) I); and f) Bounded efficacy (Lin & Lee, 2024). See App. C for a concise summary of these findings and propositions.
Figure 1:
leaving it unclear precisely which ICL phenomena are universal, important, and worth in- vestigating to develop unified theory. To address this issue, we argue novel experimental setup is needed that is rich enough to capture most (if not all) known phenomenology of ICL., but is also simple enough to be amenable to modeling, hence offering fertile ground for unifying account. We aim to fill this gap in the current paper.
This work. We propose a novel sequence modeling task that involves learning to simulate a finite mixture of Markov chains. We train Transformers this task via standard autoregressive loss under different amounts of compute budget (training iterations and model size) and data diversity (number of Markov chains in the mixture), while evaluating them with different amounts of context seen at inference. Systematically varying these factors, we show our proposed task turns out to be extremely rich, reproducing most known phenomenology of ICL and hence offering unified setup for studying the concept. Building on this, we start to deconstruct how a model trained on our task performs ICL, finding that there exist (at least) four broad algorithms that can explain the model's 's behavior. These algorithms combine a fuzzy retrieval vs. inference approach with either unigram or bigram statistics of the context, and, as we show, engage in a competition dynamics with each other to dictate model behavior. Interestingly, we find the precise experimental conditions (e.g., amount of training and context-size) decide which algorithm wins the competition, hence yielding several phases in the model's ' ability to perform ICL: varying experimental conditions elicits different algorithmic behaviors (at times rather abruptly), making difficult for understanding of ICL derived in one configuration to help predict model behavior in another one. This picture also helps us better understand several existing phenomena of ICL, e.g., why it can be transient in nature, hence enabling step towards unified account. Our contributions follow.
A finite Markov mixtures task captures ICL's phenomenology. We introduce a synthetic se- quence modeling task wherein model is trained to simulate finite mixture of Markov chains (Sec. 2). As we show, models trained on this task reproduce most (if not all) known phenomenol- ogy of ICL (see Fig. 1, 3), hence offering unified, controlled setting for studying the concept.
2

---

512 Published as a conference paper at ICLR 2025
(a) Data generation
(b) Model training
(c) Evaluation
9 train
Context
Model Probabilities
Ti
Online sampling
5 4
2 24368462
T
53631483...
7
19224687
T
(KLchir9)
Ty
36240924
Figure 2: Data generation and evaluation protocol with finite Markov mixtures. (a) Data gen- eration. We first sample finite set Tiran {Ti, ...... ,T} } of random transition matrices to define our set of Markov chains. We then randomly select a chain from this set and sample a train- ing sequence from it. We repeat this process every step of training, sampling fresh batch of sequences from by randomly selecting a chain from our predefined set. (b) Model training, We train a Transformer (Karpathy, 2022) on this sequence data with standard autoregressive training loss. (c) Evaluation. A novel sequence of states is sampled from the test transition matrix, T", for evaluation. Here, 7 is either (i) selected from the finite set Taain (for in-distribution tests), or (ii) newly sampled (for OOD tests). We subsequently compute the KL divergence between the model's empirical transition matrix T vs. ground truth transition matrix T See App. A. for details.
Systematic experiments identify different algorithmic phases of ICL. By varying the amount of training steps, data diversity (number of chains), and context size in a systematic manner, we find model trained our proposed task transitions between (predominantly) four phases of algorithmic solutions that are characterized by use of unigram vs. bigram context statistics in a fuzzy retrieval inference manner (Fig. 4, 5). Furthermore, the scale of the model interacts with the boundaries of these phases, e.g., by shifting the critical amount of data diversity needed for transitioning between different algorithms (Fig. 8). These results indicate ICL is best regarded as an umbrella term for a spectrum of algorithms, instead of a monolithic model capability, and any identified phenomenology of ICL should not be deemed universal unless shown otherwise.
A competition of algorithms picture underlies ICL's phenomenology. To further develop precise understanding of our identified algorithmic phase diagram, we decompose our model's behavior any given time into linear interpolation of the four algorithms mentioned above (Fig. 6). This interpolation turns out to be surprisingly accurate, achieving approximately zero KL with respect the trained model's next token probabilities, and thus suggesting that different algorithms compete with each other to dictate model behavior. We then show these competition dynamics can explain part of ICL's phenomenology. e.g.. offering an explanation for the transient nature of ICL (Singh et al., 2023; Anand et al., 2024) and its non-monotonic out-of- citto--distribution performance curves (Kirsch et al., 2022) (Fig. 7).
PROBLEM SETUP: SIMULATING A FINITE MIXTURE OF MARKOV CHAINS
We begin by proposing a task that unifies (most) known phenomenology of ICL into singular setup: learning to simulate finite mixture of Markov chains. This task captures the sequence modeling nature of LLMs by applying a stochastic map to every token (similar to the probabilistic automata setting of Akyürek et al. (2024)), while also offering a knob (number of chains) that helps assess the impact of data diversity on ICL. (similar to the linear regression setting of Raventós et al. (2023)).
Sequence modeling with finite mixture of Markov chains. As illustrated in Fig. 2, our proposed task involves modeling of predefined set of N Markov chains (N E 22 ...., 22,1). A chain has a unique Transition matrix T, E Ri associated with it, where & denotes the number of states (k- = 10, unless noted otherwise). Each row of T, is sampled from Dirichlet distribution, with TE. denoting the ( element of the transition matrix, i.c., the probability of transition from state to state j. The overall set of transition matrices is denoted Turann {Ti, T TN- Tw). The data-generating process (DGP) involves first randomly selecting matrix T, E Train following a prior p E R. defining a Markov chain using Tn, and then sampling a sequence of length from it. Overall, we note the DGP is characterized by three key hyperparameters: (i) N: the number of chains (a measure of data diversity in this work); (ii) k: the number states; and (iii) l: the sequence length. See App. A.I for further experimental details.
Model Training, We train a 2-layer Transformer (Karpathy, 2022) on sequences sampled from the above DGP via the standard, autoregressive sequence modeling objective (see App. A.2 for model
3

---

Published as a conference paper at ICLR 2025
a)
N Training Chains
(b)
b) 088
000
0.5
COD
0.6 P
0.4
0.4
0.2
0.2
0.1
Training Steps
2
10
10"
10'
10
N Training Chains
Training Steps
Figure 3: Finite Markov mixture setup captures rich phenomenology of in-context learning (ICL). (a) KI. divergence (OOD evaluation) as a function of training steps and data diversity (Num- ber of Training Chains). (b) As the data diversity of the training data is increased (see ruby vertical dashed line in panel (a)), we reproduce the data diversity threshold for "task learning" ICL, similar to Raventós et al. (2023); Kirsch et al. (2022). (c) At high task-diversiyy regime with N = 27 (see green horizontal dashed line in panel (a)), we reproduce non-monen non-monotonic performance dynamics in sequence modeling setup. This phenomenon was previously reported as "transient nature of ICL" in Singh et al. (2023). See App. F.1 for more plots from these experiments.
details and hyperparameters). The sampling, process is repeated every step of training, i.e., the model unlikely to see the same sequence twice during training (a.k.a. online training).
Evaluation. We evaluate trained models on In In-Distribution (ID) and chains. For evaluations, we select the transition matrix T from the training set Tirain and for OOD evaluations, we sample novel T using a Dirichlet prior. We then draw many sample se- quences from these transition matrices and compute the average KL divergence between the model's predicted transition matrix T and T Formally, we compute:
(OOD)
[K(TTTT)
Σ
bull log T LJ
(1)
See Appendix A.3 for further detail about evaluation.
2.1 REPRODUCING ICL's PHENOMENOLOGY
We next demonstrate our proposed task reproduces several known results on ICL, yielding fertile ground for developing a unified account of this capability. While in the main paper we present only a few salient phenomena that are of interest our discussion later, we refer the reader to Fig. and App. C for a more comprehensive list of captured phenomenology.
Transition via Data Diversity, In Fig. 3 (a), we present a heatmap of the KI. divergence between model's predicted transition matrix (7) and an OOD chain's transition matrix (T*) as a function of training steps (x-axis) and the number of Markov chains used to generate the training dataset (y-axis) (See App. F.1 for ID evaluation). Similar to Raventós et al. (2023), who argue the model transitions from " "Bayesian averaging" approach to an "in-context learning" one the amount of data diversity is increased, we find that given sufficient training steps, there a sudden drop in KL on OOD evaluations: when diversity is low, we find the model performs well on ID chains but poorly on OOD chains; meanwhile, when diversity is high, we find the model performs well on OOD chains as well. This phenomenon is explicitly shown in Fig. 3 (b), where show the KL of ID and OOD chains at 839 steps of training for different data diversity values. As data diversity increases, the ID KL slightly increases since the task gets relatively more complex. The OOD KL drops slowly with data diversity until N = 26, where we see an abrupt decrease and for n > 26 there is nearly no gap between the ID and OOD performance.
Transient nature of ICL. We first highlight that, given enough data diversity (n > 2a), there always an emergence of induction heads once a critical number of training steps is reached, similar to Edelman et al. (2024) (see Fig. I (b)). Fig. 3 (c) shows KL as function of training steps at a high data diversity (N = 2²). Again, we observe the emergence of the induction head dropping both the KL of ID and OOD chains
6 x 10 steps. Strikingly, after this drop, the KL divergence begins to increase again, but only for OOD chains. As we show later, this behavior corresponds to the transient nature of ICI. proposed by Singh et al. (2023): the model transitions back from
4

---

n. to denote the stationary Published as a conference paper at ICLR 2025
Stationary Distributions
OOD
Ti
Uni-Ret
Histogram
Sequence
Uni-Inf
27350789
Bi-Inf
++
Transition Matrix
Training Chains
T
T,
Tx
Bi-Ret
Figure 4: Proposed algorithms for the finite Markov mixture task. (a) Unigram based Retrieval (Uni-Ret)): Given sequence, Uni-Ret involves computing histogram of token frequencies in the sequence and then creating new transition matrix that is weighted average of chains in Tuain- Weight associated to chain based on the distance between the computed histogram and a chain's steady-state distribution. (b) Bigram based Retrieval (Bi-Ret): Similar to Uni-Rets but uses observed transitions, ie.. bigrams, to weight the chains. The resulting likelihood is much sharper, making this algorithm better for the training data. (c) Unigram Inference (Un In This algo- rithm infers histogram from the given context and draws subsequent tokens from this histogram directly. (d) Bigram Inference (Bi-Inf)) This algorithm infers the transition matrix from the given context and draws subsequent tokens from this transition matrix directly. This approach achieves best OOD generalization among considered algorithms. The + and indicate the performance expected on ID chains and OOD chains, where + indicates better performance.
using an algorithm that performs well OOD that performs well solely ID; the latter relies on memorized information that is akin to what the authors in their paper call an "in-weights" solution.
3 ALGORITHMIC PHASES IN FINITE MIXTURE OF MARKOV CHAINS
Having ascertained the value of our proposed task by reproducing known phenomenology, we now aim take step towards developing a unified account of ICL. To this end, we must better under- stand how model trained on our task performs ICL. As we show, we can identify (at least) four broad algorithms that explain the trained model's behavior (i.e., its next token predictions) for differ- ent subsets of experimental configurations. We call these subsets algorithmic phases: continuous ranges of experimental configurations where the trained model's behavior explainable by a prede- fined algorithm. Building on this analysis, we show in the next section that ICL's phenomenology, as it manifests in our setup, partly driven by a competition between our identified algorithms. We also offer preliminary mechanistic evidence for analysis in App. E.
3.1 ALGORITHMS TO SIMULATE FINITE MIXTURE MARKOV CHAINS
Broadly, the axes that help characterize our algorithms (see Fig. 4) are (i) what statistics of the inputted context are used by the model (unigram vs. bigram), and (ii) whether the approach involves a fuzzy retrieval of the most relevant Markov chains seen during training to make the next-token prediction (akin to a Bayesian averaging operation where discrete prior is defined over Train i.e., chains seen during training), versus an inference of the Markov chain parameters based solely on the sequence seen in context (akin to Bayesian averaging operation where continuous prior, i.e., the Dirichlet distribution is used)'. A retrieval approach will generally achieve better performance evaluations; however, its performance on OOD evaluations will be worse, especially with increased context length (see App. D for detailed discussion). Below, distribution a chain T, and is the Kronecker delta.
ID
Retrieval Approach. Similar task-retrieval notions of ICL (Min et al., 2022), we detine "re- trieval" algorithms as the accumulation of some relevant statistics of the input sequence to compute
We note primarily use distinct names for the two approaches for clarity. but both approaches in fact Bayesian inference protocols with priors that depend vs. Tuain See App. B.1 for further discussion.
5

---

Published as a conference paper at ICLR 2025
likelihood function that depends the Markov chains underlying our training data, i..., Turin- Specifically, the algorithm utilizing unigram statistics of the input, which we call Uni-Ret (Uni- grams based Retrieval), uses the following likelihood function.
Unigram Likelihood: (T (xaa) = - Tn[z)]
(2)
where X1: is the sequence of all states 1 to t. Meanwhile, the algorithm utilizing bigram statistics of the input, which we call Bi Bi-Ret (Bigrams based Retrieval), uses the following likelihood function.
Bigram Likelihood: CB(Tn, x1:1) = 11j=:-a(es-1=3s)
(3)
Given the likelihood functions above, the posterior predictive distribution to predict how likely given next state is can be computed as follows.
Retrieval approach:
& Σ Pn ((T
(4)
Inference Approaches. Similar to "task-leaming"" notions of ICL (Raventós al., 2023; Lu al., 2024), we define "inference" algorithmss as the computation of relevant statistics from the inputted sequence to infer a probability distribution over the next feasible states. The precise Markov chains seen during training play no role in this computation (unlike the fuzzy retrieval approaches discussed above). Consequently, these algorithms exhibit no performance disparity between ID and OOD evaluations, as they do not incorporate any information from the training dataset. Formally, one uses either the frequency of token occurrences, i.e., the unigram distribution, or the frequency of pairwise token occurrences, i.e., the bigram distribution, to define transition matrix that encodes the predicted next-token probabilities. We call the former algorithm Uni-Inf and the latter Bi-Inns Inf, denoting their transition matrices T and T respectively.
Ex=1 6xan
Uni-Inf: (xi)
(xx)
(5)
1 Et=l 8 02
Bi- Bi-Inf: T (x1:))
(6)
k + ++
Ek=1 8 8ze
3.2 ISOLATING ALGORITHMIC PHASES
We now demonstrate the four algorithms proposed above delineate models trained on our task into broad algorithmic phases based on the train / test configuration. To this end, we define the following two evaluations protocols that assess whether the model utilizes bigram statistics and whether follows fuzzy retrieval approach, i.e., relies on the chains seen during training.
Assessing Bigram Utilization. We qu model's reliance on bigram statistics of the sequence shown in context by exploiting key difference between our proposed algorithms: unigram-based methods depend solely on stcady-state distributions (TT), while bigram- methods consider state transitions (I*). Thus. distinguish between these approaches, we simply shuffle the positions of all tokens in the imput sequence. This perturbation preserves the stationary distribution, but disrupts any order-sensitive information, e.g., information about bigram transitions. We can then measure change in KL between the empirical transition matrix inferred from the model's predicted next-token distributions and the ground truth matrix used for sampling the sequence: large change would suggest the model relies on bigram statistics to perform the task, while a small change would indicate a unigram- based approach is at play. See App. A.3.3 for implementation details.
Proximity to a Retrieval Approach. Assessing how much a model relies on the Markov chains seen during training, e.g., by internalizing their transition matrices (see also App. E. helps distin- guish between solutions that solely leverage context statistics (Bi [Bi-Inf and Uni (mi-Inf) and those that do not (Bi-Ret and Uni-Ret).. Motivated by this, we first sample a new set of transition matrices, denoted Trandom- with the same number of matrices as the train set, Tuain- We then define a chain using a transition matrix 7 that does not belong to either Timin or Trandom- Using a sequence sampled from this chain, we compute the empirical transition matrix T based on the model's next token predictions, and then check whether this matrix is closer (in terms of KL) to the set Train or to the set Trandom- If the model does not have a preference for the seen transition matrices, i.e., it is not utilizing a retrieval approach, then Î should be (approximately) equally close to the two sets; else, it should be closer to Tiain- See App. A.3.3 for further discussion and implementation details.

---

Published as a conference paper at ICLR 2025
a)
Bigram Utiliatioo
b)
Procemity
d)
N Traiiing Chare
68
Trannn Chvee
13
0.4
63
28
A
04
24
12
0.0 Inserative
Truining Stops
Training Steps
Figure 5: Algorithmic phases. (a) Bigram Utilization: We shuffle the order of all states in sequence and measure the KL (App. Eq. 9) before and after the perturbation to quantify bigram utilization of a model. The shuffling should only affect algorithms sensitive to higher-order statistics. (b) Proximity to Retrieval: A model is labeled "closer" to a retrieval approach when its next- token probabilities are closer to matrices seen in the training set. We evaluate this by sampling an unseen set of transition matrices, and measuring the model's next-token probabilities have lower KL w.r.f. transition matrices seen in training
if it is similar the freshly sampled set (App- Eq. 11). (c) Algorithmic Phases: The product of bigram utilization and proximity to retrieval scores delineates four distinct algorithmic phases. (d) Validating phases: KL between model's and predefined algorithms' next-token probabilities provides validation to our identified phase diagram.
Results. See Fig. 5. We find the evaluation protocols defined above clearly delineate experimen- tal configurations into regions where the solution is (i) unigram-dependent vs. bigram-dependent, and (ii) closer to retrieval vs. inference (Figs. (a,b)). These results divide Fig. 3 into four distinct phases, each in accordance with the four algorithms proposed in Sec. 3.1: Uni-Ret, Bi-Ret, Uni-Inf, and Bi-Inf (see Fig. (c)). We confirm the validity these phases by comparing KI. between the model and the predefined algorithms' next-token probabilities (Fig. 5 (d)). Impor- tantly, we observe that with enough training steps and data-diversity, bigram dependence consis- tently emerges. Meanwhile, if the data-diversity is large (small), the model is closer an inference (retrieval) approach. Medium data-diversity however sees an interesting learning dynamic, wherein the model starts off with a retrieval approach, transitions to inference approach with enough train- ing, but then slowly rolls back to retrieval approach! We also perform several other experiments to corroborate these findings, such as providing preliminary mechanistic evidence for these algorithms; e.g., we find can reconstruct transition mutrices from Tiain via MLP neurons in retrieval phases! (see App. E). We also report additional metries and attention analysis in App. F.
Overall, we conclude there are (at least) four algorithmic phases in the dynamics of learning to simulate finite mixture of Markov chains: a model uses (predominantly) one of the four algorithms identified above to perform our task, with the experimental configuration dictating which precise algorithm is finally used. Next, we will use these identified algorithmic solutions to better under- stand various phenomena associated with ICL. We will especially focus investigating the non- monotonic nature of OOD generalization dynamics, i.e., the transient nature ICL.
LINEAR INTERPOLATION OF ALGORITHMS: A COMPETITION PICTURE OF NON-MONOTONIC GENERALIZATION DYNAMICS IN ICL
In Sec. 3, we identified four algorithms that decompose the learning dynamics of a model trained on finite mixture of Markov chains into broad algorithmic phases. We now show these algorithms con- sistently compete with each other to dictate trained model's behavior (Sec. 4.1), partially driving ICL'S phenomenology. Specifically, we analyze the non-montonic generalization dynamics of ICL. in Sec. 4.2 (e.g., its transient nature), and how model design (e.g., width, tokenization) affect the algorithmic phases in Sec. 4.3.
4.1 LINEAR INTERPOLATION OF ALGORITHMS (LIA)
To begin, first show that a simple linear interpolation of the four algorithms described in Sec. captures a trained model's behavior, i.c., its next-token predictions, extremely well. Formally, let A denote the set of four algorithms [Uni -Ret, Bi Rett, Interpolation of these Algorithms (LIA) is identified by solving the following problem.
Bi IIn f). then the Linear
72
LIA: arg min Exi MEA
Pmoddl (x1=) - Σ Wa Pa (X1:1)
where Σ
Wa = 1 & 2 0.
(7)
aEA
acA
7

---

Published as a conference paper at ICLR 2025
a)
b)
N= In-Distribution
c)
N=2 In-Distribution
2 2r
N Training Chains
22
0.
4:75
8.3
1.3
175
6:3
2048
1925
30377 12316
Training Steps
Training Steps
Training Staps
Uni Ret
DI Ret
Uni-Inf
Gi-Inf
Model KL
LIA Fit KL
Figure 6: Linear Interpolation of Algorithms (LIA) (a) Algorithmic Phases extracted by LIA. We color each location by combining individual colors associated to an algorithm, weighted by their weights Wa- (b) LIA weights across checkpoints extracted using ID data for N = 2 KL of the empirical transition matrix fit by LIA from the ground truth matrix is shown as a black dotted line. The model KL is shown as black solid line. The evolution of the weights assigned to each algorithm is shown in the lower plot. (c) LIA weights across checkpoints for N 2 This model was trained with learned positional embeddings. See App. F.2, Fig. 36 for the phase diagram. LJA reveals transitions between algorithms which were seemingly hidden due to the smooth evolution of the ID KL divergence (top panel).
Here, Pmodel and Pa respectively denote the next-token predictions of the model and individual algo- rithms from set A. given the sequence X1:t as input; meanwhile, wa denotes the weight associated with algorithm E AA in the interpolation. We optimize the interpolation weights by minimizing Eq. over multiple ID sequences X1d, i.e., sequences sampled from Markov chains that constitute Tuain (see App. A.3.4 for further details). Fits are almost perfect for all settings (see App. I, Fig. 39).
Results. See Fig. 6. We run the LIA analysis for different amounts of training sleps and data diversity, hence analyzing the dynamics of how the algorithms underlying our identified phases evolve to dictate a model's ' behavior. Crucially, this fine fine-grati mne-grained analysis helps us better understand the model at different phases' boundaries, where find algorithms may possibly co-occur.
Fig. (a) shows that LIA qualitatively finds the same dominant algorithm in each phase as ones illustrated in Fig. 5, where used the bigram utilization and retrieval proximity tests.
Fig. 6 (b) shows LIA applied across checkpoints for N = 26 a moderately high data diversity setting. Per panel (a), this setting is the first to not have particularly dominant Bi-Inf phase. We see herein intriguing dynamic occurs the model undergoes training: since the bigram so- lution's KL divergence is lower, the model transitions from Uni Inf to Bi -In as it undergoes training. However, after 103 steps, start wimess transience: the model slowly cross-overs to utilizing the Bi-Ret solution, which performs better than Bi-Inf on ID sequences.
Fig. (c) finally shows that depending on experimental conditions, the order in which different algorithms come to explain the model behavior can be different. For N = 2 and when us- ing learned positional embeddings (please see App. F.2 for further details), we show that both delayed to long after Uni RRt is used solution by the model. We
Bi-Inf and Bi-Ret emphasize that the evolution of the ID KL, which is essentially the training loss, is smooth; how- ever, LIA detects interesting underlying dynamics that indicate persistent competition between different algorithms to supersede one another.
4.2 UNDERSTANDING VON-MONOTONIC OOD PERFORMANCE WITH LIA
Our results above show that LIA is useful tool to probe how model transitions between different algorithms to converge on a solution for the task. Next, we discuss how these transitions shape the evolution of OOD performance, explaining the transient nature of ICL (Singh et al., 2023). We again use LIA on the ID sequences for this analysis we emphasize that these experiments amount to predicting OOD performance of model by merely using the ID data. See App. A.3.4 for further explanation, and App. for more experiments in this vein.
Results. Fig. 7 shows that the weights extracted via LIA predict the evolution of OOD perfor- mance during training. Fig. 7 (a, b) correspond to the models in Fig. (b) and (c), but this time we plotting 0OD performance (unlike before, when analyzed the ID performance).
8

---

Published as a conference paper at ICLR 2025
a)
N=26
Out-of-Distribution
b)
N=27 Out-of-Distribution
0.6
KL
1.00
"method
0.75
"imethod
0.75
0.50
0.50
0.00
0.00
207
20a
10a
10
10"
10"
10'
Training Steps
Training Steps
Model KL
LIA Predicted KL
Figure 7: Algorithmic phase transitions drive non-monotonic OOD performance. Note that each algorithm's S KL. in colored dotted lines has changed from Fig. because of the distribution change. (a) Predicting out-of-distributiin (OOD) performance corresponding to Fig. (b) using LIA weights. By applying the LIA weights fit on ID data, we predict the model's OOD performance, explaining the transient nature of ICL. (b) Predicting out-of-distribution (OOD) performance corre- sponding to Fig. (c) using LIA weights. By applying the LIA weights fit on ID data, we predict the model's OOD performance, explaining non monotonic OOD performance and sudden changes.
Fig. (a) shows that as the model undergoes training, the Bi-Inf solution, which generalizes extremely well OOD, suddenly comes to dictate the model behavior. This algorithm is thus sim- ilar to what prior work calls "lask-learning" ICL, since the algorithm entirely reliant on input context (Raventós et al., 2023). However, takes over because of its superior performance on ID sequences. This causes the OOD perfor- mance degrade since the Bi-Ret solution does not generalize well to OOD sequences, as seen in Sec. 3.1. We argue this dynamic underlies the broader ICL phenomenon demonstrated by Singh al. (2023), who claim ICL can be transient in nature. Specifically, LIA demonstrates that an algorithm that heavily relies on internalized knowledge the train distribution (i.e., a retrieval solution) consistently competes with the better DoD-generaliziig algorithm. Since the former will ultimately achieve better loss on ID data, it slowly but steadily will supersede the better generalizing solution, manifesting as the transient nature of ICL. See also App. C.2.1 for further detailed analysis and discussion, and App. E for mechanistic evidence in support of these claims: we show we can reconstruct transition matrices from MLP neurons after the model returns to the Bi Bi-Ret phase, but not in the Bi-Inf phase.
saw in Fig, 6 (b), the Bi Ret solution slowly
Fig. 7 (b) shows that the emergence of Bi- which only changes the ID performance slightly, affects the OOD performance more drastically. This demonstrates that certain changes in OOD performance can be predicted by carefully decomposing the model's strategy for performing task. This result also complements the results (a), demonstrating that both ascents and descents in OOD performance can be explained with algorithmic transitions on the training set.
Overall, the results above show that training dynamics of sequence modeling tasks can be thought as competition of algorithms on the training set; the generalization performance of the model is reflection of the current combination of algorithms used.
4.3 MODEL ANALYSIS USING ALGORITHMIC PHASE DIAGRAMS
The core finding of Sec. 4.2 is that algorithmic transitions characterize model behavior under differ- ent experimental configurations. An extremely crucial component of this configuration is the precise set of design decisions made define the model work (Kirsch et al., 2022), scaling the width of the model can impact its ICL abilities. Building on this, now analyze the effects of model design choices on ICL, specifically evaluating the effects of model size, data complexity, and tokenization. See App. F for more experiments.
training. For example, as shown in prior
Results. See Fig. 8, which yields the following observations.
Fig. (a) shows the phase diagram when using a model with an embedding dimension of 256, which is 4 times bigger than our baseline experiments. We observe that the data diversity

---

Published as a conference paper at ICLR 2025
a)
Wider Model
b)
k=2
c)
Transition Encoding
Training Chains
N Training Chains
N Training Chains
2/
213 1530 411 100
257 112 120 642 18831
2:40 1335 8037 XI1A Training Steps
Training Steps
Training Stops
Figure 8: Algorithmic Phase Diagrams Explain the effects model size, data complexity, and tokenization. (a) Phase diagram for wider model with an embedding dimension of 256. Here, we find that the data diversity required observe Bi-Inf increased to 2 (b) A decreased state space (k = 2. decrease data complexity) enhances the retrieval solutions and causes Bi-Inf to almost never appear. (c) Encoding the transitions into the tokens removes the Uni Uni-Ret solution by making it the more complex and higher train loss solution compared to Bi-Ret.
quired to observe Inf is increased 16x. Since there is no a priori reason to believe a wider model cannot implement the Bi-Inn algorithm, conclusion is that Uni-Ret and Bi Bi-Ret algorithms are relatively faster to appear in a bigger model, hence impeding Bn-In ability to succeed in the overall competition. This finding is intuitive as bigger model will have more pa- rameters to memorize the training set transition matrices. We also note that this result is in contrast to Kirsch et al. (2022)'s, ss who claim width scaling leads to (faster) emergence of "task-learing" ICL. We provide further discussion of this point in App. C.2.2, C.2.3.
Fig. 8 (b) shows the case where the state space of the DGP is set to k = 2. reducing the complexity App. D for discussion). In this
of the data (note that this is independent of the data diversity; case, we find that the model can easily internalize the transition matrices needed for the Bi-Ret solution-eve even N 2 chains do not allow the Bi-Inf solution to win the competition.
Fig. 8 (c) shows the effect of expanding the token space to allow each token to represent the last state and transition (See App. A.2 for details). This experiment is motivated to understand the effect of tokenization downstream abilities. We find tokenization allows the model to be able to count transitions without a formation of a complex attention head, which we suspect is one of the reasons Bi Re is slower to learn than Uni-Res (see App. J for discussion and App. E.3 for attention head visualizations). As expected, we find the Uni Ree phase disappears in this case, since Bi-Ret is both superior on the training set and (now) the simpler solution.
Overall, our results shows that the downstream effect of design choices can be well understood at the algorithm level. Please see App. F for additional perturbations, including positional embeddings, model depth, and number of attention heads.
5 CONCLUSION
In this study, we introduced finite Markov mixtures as a model system of ICL which reproduces a myriad of phenomena discovered in recent studies of ICL, hence offering unified setting for study- ing the concept. This setup also allowed us to write down four algorithmic solutions, each with their peculiarities, that can explain the trained model's behavior. We then decomposed trained models into a combination of these solutions, revealing a competition dynamics between the algorithms to dictate model behavior. These dynamics result in algorithmic phase diagram of in-context learning spanning data diversity and optimization, and can be interpreted as the model finding the best algorithm on the training data, leading to both sudden and slow transitions towards better solu- tions. These transitions of algorithms can offer insights into ICL's phenomenology. e.g., offering a mechanism that leads to the transient nature of ICL (Singh et al., 2023). More broadly, we claim our findings challenge the traditional "more is better" view of scaling laws by showing that ICL emerges from competing algorithmic behaviors rather than a single mechanism. This insight suggests fresh perspective how we should approach model development: instead of solely focusing reduc- ing the loss through scaling, can we promote desired algorithms over competing alternatives that may achieve lower training loss but generalize poorly? Through careful design of data composition, model architecture, and training duration, we can potentially guide models toward implementing more robust and generalizable algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
CFP and HT gratefully acknowledge the support of Aravinthan D.T. Samuel. CFP acknowledges the support of Cecilia Garraffo and Douglas P. Finkbeiner. IP was supported by BERI. The computations in this paper were run on the FASRC cluster supported by the FAS Division of Science Research Computing Group Harvard University. The authors thank Gautam Reddy, Pulkit Gopalani. Robert Kirk, Andrew Lee, Daniel Wurgaft, Maya Okawa, Cole Gibson, Alex Nguyen, Sadhika Malladi, Zechen Zhang. Helena Casademunt, Yongyi Yang, and Wei Hu for useful discussions.
CONTRIBUTIONS
CFP and ESL independently defined the setup, ran preliminary investigations, and converged on bulk of the experiments, evaluation protocols, and phenomenology; CFP ran extensive experiments to verify the latter. CFP ran the final experiments in Section 3 in collaboration with ESL identify the algorithmic phases and uncover transience of ICL. This formed the basis of the paper. ESL and CFP proposed the LIA protocol in Section 4, which they used to develop explanations for ICL's phe- nomenology; CFP led the experiments. ESL and CFP performed first version of the mechanistic interpretability analysis, which IP significantly expanded. also proposed the memorization anal- ysis and the analysis of attention maps at phase boundaries. ESL defined the project narrative and wrote the paper, with inputs from all authors. CFP, ESL, and HT designed the conceptual diagrams. HT supervised the project.

---

Published as a conference paper at ICLR 2025
REFERENCES
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm in-context learning? investigations with linear models, 2023. URL https:// atg/abs/// aaaaab/22111 15661.
arxiv. www.oor/aaaee
Ekin Akylrekk, Bailin Wang, Yoon Kim, and Jacob Andreas. In-context language learning: Archi- tectures and algorithms, 2024. URL httph:: http://xxivvvrro org. abap//bs/21111 12973.
Suraj Anand, Michael A Lepori, Jack Merullo, and Ellie Pavlick. Dual process learning: Con- trolling use of in-context vs. in-weights strategies with weight forgetting. arXiv preprint arXiv:2406.00 00053, 2024.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36, 2024.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harm- lessness from ai feedback. arXiv preprint arXiv:2212.0807.. 2022.
Eric Bigelow, Ekdeep Singh Lubana, Robert Dick, Hidenori Tanaka, and Tomer Ullman. In-context learning dynamics with random binary sequences. arXiv preprint arXiv:2310. 17639,
2023.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws, 2024. URL https: /ttp///xivv//..////v//e.////aava org/orgg////ooo abs www.a/////222 2402.01092
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot leamners Advances in neural information processing systems, 33:1877-1901, 2020. 2020.
Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang. Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learn- ing in transformers. Advances in Neural Information Processing Systems, 35:18878 188181811881, 2022a.
18891,
Stephanie CY Chan, Ishita Dasgupta,Junkee Kim, Dharshan Kumaran, Andrew Lampinen, and Felix Hill. Transformers generalize differently from information stored in context vs in weights. arXiv preprint arXiv:2210.05673 2022b.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, and more. The Ilama 21783.
herd of models, 2024. URL ptttps://axxiv..ott wttpaaiiwi.....///aa/aaaaaaaaa/e
Benjamin L. Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The lution of statistical induction heads: In-context learning markov chains, 2024. URL https:
//arxiv. orw.v.orrgaara abs /ttpb///2222000000 11004.
Nelson Elhage. Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Doda Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. mathematical framework for transformer circuits. Transformer Circuits Thread, 2021.
Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposi- tion. arXiv preprint arXhv:2209.106533 2022.
Jaden Fiotto-Kaffman. Alexander R Loftus, Eric Todd, Jannik Brinkmann, Caden Juang, Koyena Pal, Can Rager, Aaron Mueller, Samuel Marks, Arnab Sen Sharma, Francesca Lucchetti, Michael Ripa, Adam Belfki, Nikhil Prakash, Sumeet Multani, Carla Brodley, Arjun Guha, Jonathan Bell, Byron Wallace, and David Bau. Nnsight and ndif: Democratizing access to foundation model internals, 2024. URL RRLLhttss:///xiiee http://wwww.rgg///////////////// 14561.
12

---

Published as a conference paper at ICLR 2025
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes, 2023. URL httpsts////xxiv.. /bs/ 2208. 01066.
Gemini Team. Gemini: arXiv:2312. 1800, 2023.
family of highly capable multimodal models.
arXiv preprint
Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer feed-forward layers are key-value memories, 2021. URL https: /arxiv org/ abwa/bss1221 14913.
Akhilesh Goumare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. closer look at deep learning heuristics: Learning rate restarts, warmup and distillation, 2018. URL https:
13243.
Dean S. Hazineh, Zechen Zhang, and Jeffery Chiu. Linear latent world models in simple transform- ers: case study othello-gpt, 2023. URL https: //arx/vaaav//////////a//eaaaaaaa ott/vvoorr/aaaaa /topg//bb////// 0.1..000.550... 07582.
Tom Henighan, Shan Carter, Tristan Hume, Nelson Elhage, Robert Lasenby, Stanislav Fort, Nicholas Schiefer. and Christopher Olah. Superposition, memorization, and double descent. Transformer Circuits Thread, 6:24, 2023.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Train- ing compute-optimal large language models. arXiv preprint arXiv:2203. 15556, 2022.
Jesse Hoogland, George Wang, Matthew Barrugaa-Robert Liam Carroll, Susan Wei, and Daniel Murfet. The developmental landscape of in-context learning, 2024. URL https://arxiv. org/abst 02.02.22 02364.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, al. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207.05608 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361. 2020.
Andrej Karpathy, nanogpt.
https///g..ttta.ooo//sssttttaaat 2022.
Louis Kirsch, James Harrison, Jascha Sohl-Dickstein, and Luke Metz. General-purpose in-context learning by meta-learning transformers. arXiv preprint arXiv:22/22004458. 2022.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathe- matical statisties, 22(1):79 86, 1951.
Kenneth Li, Aspen Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wat- tenberg. Emergent world representations: Exploring sequence model trained synthetic task. In The Eleventh International Conference on Learning Representations, 2023a. URL
https:/ openreview net/ forum?id=DeG07 -___TT
Shuai Li, Zhao Song, Yu Xia, Tong Yu, and Tianyi Zhou. The closeness of in-context learning and weight shifting for softmax regression, 2023b. URL WtLLhttss///axiv org. 13276.
Yingcong Li, M Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers al- gorithms: Generalization and implicit model selection in in-context learning. arXiv preprint arXiv:2301.07067, 2023c.
Ziqian Lin and Kangwook Lee. Dual operating modes of in-context learning, 2024. URL https:
//arxiv.. www./rrg/aaoooo htrg/abb/2402. 18819.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint N00i:1908.0366 2019.
13

---

Published as a conference paper at ICLR 2025
Iyy Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08788 087866 2021.
Yue M Lu, Mary 1 Letey, Jacob A Zavatone-Veth, Anindita Maiti, and Cengiz Pehlevan. Asymptotic theory of in-context learning by linear attention. arXiv preprint urXiv:2405./175/ 2024.
Arvind Mahankali, Tatsunori B. Hashimoto, and Tengyu Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention, 2023. URL
arxiv. org/ aws//2300000 03576..
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202. 12837, 2022.
Neel Nanda, Andrew Lee, and Martin Wattenberg, Emergent linear representations in world models of self-supervised sequence models, 2023. URL httphttpps.... /ttp:///aaaaii/ .or.iiooor................ooooo. org.
00941.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac HatfieldDoodds Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kermion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads, 2022. URL https:/ heatttss//aaxiv..... waw.iv.vvv........ abs/ 2209 11895.
OpenAl. Gpt-4 technical report, 2024. URL httpst URLLAtttss//araav..or///b//////
Jane Pan, Tianyu Gao, Howard Chen, and Danqi Chen. What ietootextt "learns""""" Disentangling task recognition and task learning, 2023. URL https:///axxv..orgg
"learns" in-context:
2305.00 09731.
Madhur Panwar, Kabir Ahuja, and Navin Goyal. In-context learning through the bayesian prism, 2024. URL https: /ttp://aaxivvvivo abs / /2006 04891.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang, Zach De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- gigh-performance deep learning library, 2019.
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307. 16789, 2023.
Allan Raventós, Mansheej Paul, Feng Chen, and Surya Ganguli. Pretraining task diversity and the emergence of non-bayesian in-context learning for regression, 2023. URL https://arrxe org/ org/abs//
abs / 2306. 15063.
Gautam Reddy. The mechanistic basis of data dependence and abrupt learning in an in-context classification task, 2023. URL hattps://arxxt org/abs/ /212.. 03002.
Melanie Sclar, Yejin Choi, Yulia Tsvetkov, and Alane Suhr. Quantifying language models' sen- sitivity to spurious features prompt design or: How learned start worrying about prompt formatting, 2024. URL https: arxii. org/ aa/aabbs/233 11324.
Aaditya K. Singh, Stephanie C. Y. Chan, Ted Moskovitz, Erin Grant, Andrew M. Saxe, and Felix Hill. The transient nature of emergent in-context learning in transformers, 2023. URL https: //arxiv. wwwiii.orr//a. org. abs/ /11./311.1000 08360.
Aaditya K. Singh, Ted Moskovitz, Felix Hill, Stephanie C. Y. Chan, and Andrew M. Saxe. What needs to go right for an induction head? a mechanistic study of in-context learning circuits and their formation, 2024. URL https:ttpt... / wrgg/or//sss... 2404 07129.
14

---

Published as a conference paper at ICLR 2025
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: En- hanced transformer with rotary position embedding, 2023. 2023. 2104. 09.
/
William L. Tong and Cengiz Pehlevan. Mlps learn in-context regression and classification tasks, 2024. URL https:://// /ttp:///aaiiv.i/.a www.iiiii.o..ab.ooooooeeeaeeaeae /a/zg//bb/224.... 156188......
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13977, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need, 2023.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, 35151-35174, PMLR, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903, 2022.
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, and Tengyu Ma. Larger language models do in-context learning differently, 2023.
http:://axvvvvo/oo org. abs//bb///// 2303. 6.846.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXi:2211..0000, 2021.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
CONTENTS
Introduction
2
Problem Setup: Simulating a Finite Mixture of Markov Chains
2.1
Reproducing ICL's phenomenology
3
Algorithmic Phases in finite Mixture of Markov chains
3.1
Algorithms to simulate finite mixture of Markov chains
3.2
Isolating Algorithmic Phases
Linear Interpolation of Algorithms: A Competition Picture of Non-Monotonic Gener-
alization Dynamics in ICL
4.1
Linear Interpolation of Algorithms (LIA)
4.2
Understanding non-monotonic OOD performance with LIA
8
4.3
Model Analysis Using Algorithmic Phase diagrams
5
Conclusion
10
A
Experimental Details
18
A.I Data Generating Process
18
A.2 Training Details: Model & Optimization
19
A.3
Evaluation Details
20
A.3.1
KL Divergence
................................
20
A.3.2
Estimating Transition Matrices
20
A.3.3
Bigram Utilization and Retrieval Proximity
A.3.4
Linear Interpolation of Algorithms
21
A.4
Learning curves
22
More About Solutions
23
B.1
Inference Approaches are "Bayesian" with relaxed prior
23
B.2 Unigram Posterior Solutions
23
C Phenomenology of In-Context Learning: Summary of reproduced results and im-
proved understanding
24
C.I List of phenomena reproduce
24
C.2 Improved understanding of ICI.: Insights into Transience and effects of model scaling
25
C.2.1 Transient Nature of In-Context Learning..
25
C.2.2 ICL and Model-Size Scaling
25
C.2.3 Effects of Model-Size Scaling, Revisited
26
16

---

Published as a conference paper at ICLR 2025
D High Dimensional Distances
28
Mechanistic Analysis
29
E,1
Reconstructing Markov Chains from MLP Neurons in Retrieval Phases
29
E,2 Dynamics of Memorization
E.2.1
Superposition of neurons with increase in data diversity
31
E.3
Attention Maps: Implementing Inference approaches
34
E,4
Attention Pattern Evolution Corroborates LIA
37
E.4.1
Validating LIA: Attention heads in different phases
37
E.4.2
Validating LIA: Attention heads phase boundaries
39
Additional Results
E1
Additional plots from the main experiments
41
E1111
High Quality Version of Fig. subplots
F.1.2
KL Divergence Heatmaps
42
F11.3
KI. Divergence vs. (Steps, Diversity, Context)
43
E.1.4
KL divergence between the model and solutions
46
F2
Architecture Changes
47
G Generalization to chains from different prior
48
H In-Context Learning of Markov Chains in Real Large Language Models
49
Further validation of LIA
50
L1 Does LIA fit the model well?
50
I.2 Robustness LIA to arbitrary algorithms
Importance of sequence-space structure to study transformers
52
K Discussion and Future Directions
53
Code Availability
53
17

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL DETAILS
A.1 DATA GENERATING PROCESS
The Data Generating Process (DGP) is defined by crucial hyperparameters:
1. k: The number of states in the Markov chain, fixed 10 unless mentioned otherwise.
2. I: The length of the sequence generated, fixed to 512 unless mentioned otherwise.
3. N: The number of training matrices, N E {2², 23 ................................ 2 for the main experiments.
The set of Markov chains used for training is constructed by drawing N transition matrices. We draw each row of each transition matrix from Dirichlet distribution with parameter a 1g. We index individual transition matrices via subscript, i.e., Tn and use square brackets to index the matrix elements, e.g., Tka] Thus, the next state probability is p(æ++1 = j f i) Ti. The probability of selecting a chain is also drawn from a Dirichlet distribution with parameter this prior as pr, in equation Eq. 4, although its precise values did not yield any interesting effects in experiments. To generate data, first choose transition matrix from the prior probability Pr. define a Markov chain with that transition matrix, and then sample sequence of length I.
1v. We denote
Each transition matrix Tn naturally defines single stationary distribution denote Tn. We draw the first state from this stationary distribution to initialize a sequence. By definition, this distribution should remain the same when moving forward in the chain, i.e., it satisfies the relation Tn T, we calculate the stationary distribution analytically from this relation. Please see the in the code snippet below.
function get iotaary dii sistrr ritrrbutt..
To make the dataset clear we attach a minimal PyTorch (Paszke et al., 2019) implementation. We generated this code with the help of GPT4o (OpenAI, 2024). The code is for clarity only and is not optimized for speed or compatibility.
import torch
from torch. wut.tstl........................ data import IterableDataset import numpy as np
class MarkovChainDatasee (Iterablefataset)
def init (self, k, 1, n, seed=None)
seli.k k Numper states self.1 I Output sequence length self.n - # Number of transition matrices self.seed seed Seed for reproducibility
12
if seed is not None:
13
np. random, seed (seed) torch. march.manualssced (sced)
seed
14
16
Generate n transition matrices, each with states self.transition catoonnmtticeesssee for in range (n)
17
18
matrix np.array ([np. random dindom.diriie dirichlet ([1] * k) for in range (k)
20
self self.transie transitinnn
cotassitioommttiiiss... www.waattttt.i.....e append (matrix)
21
22
Prior distribution over transition matrices
self.prior np. wp.random.dirrchhle..
24
25
def
get
(self,, matrix)
26
# Compute the stationary distribution of the transition matrix
eigvals, eigvecs = mp.linalg.eti (matrix. (matrrixx.7
staticnary np. rear (eigvecs [: I np.isclose (eigvals, 1)])
29
staticnary stationaryli, 0]
30
staticnary /= Stationary.sumf return stationary
def sample_chain(se11 transition transition_matriz)
18

---

Published as a conference paper at ICLR 2025
Sample the first state frem the stationary distribution stationary sel.
35
traneition_matrik,
36
first_state = np. www.raddo..cciceessee
p=stattoonary_diistibbttttt
Generate the sequence
39
sequence [first_state]
40
for in range (1, self.1):
current_state sequencel-11
next_state np, www.emnem.com choice (self.k, pstransition / current_state)
43
sequence, append (next_state)
44
return sequence
47
def itter
itte__seef)) (self):
48
while Truc:
49
# Choose a transitien matrix based on the prior matrix_index np randem. choice (self.n, p=sclf.prior)
chosen_matrix sta.rriiiss.....iissitittti seIF.cranssttonnnaaiiieee (marrxxxideat
52
53
# Generate a sequence using the chosen transition matrix sequence = sample chain (chosen_mmassae yield torch.tenser (sequence)
56
57 Example usage:
58 k 3 (states), 1 10 (sequence length), (transition matrices),
seed 42
dataset MarkovChainDataset (k=3, 1=10, n=5, seed=42)
60 iterator iter (dataset)
61
62 Get a sample sequence
sample_sequence next (iterator)
64
print (sample_sequen)) #e.g. tenser (18, 8, 9, 5, 3, 8, 81)
Listing 1: Markov Mixtures Data Generating Process
A.2 TRAINING DETAILS: MODEL & OPTIMIZATION
Model Architecture We train a Transformer model with softmax attention (Vaswani et al., 2023) sequence data generated by the DGP described above in Sec. A.1. We adapted code from nanoGPT (Karpathy, 2022), and implemented Rotational Positional Embedding (RoPE) (Su et al., 2023) instead of the default learning positional embedding, which significantly delayed the emer- gence of Bi -Inf. Further discussion about these results are in App. F.2. All matrix weights are ini- tialized A (O initialized zero. The embedding layers for Sec. F.2 are initialized from AO,, 0.02). We trained our models on NVIDIA A100 80 GB GPUs, running experiments in parallel on the same GPU, and hence yielding a wallelock time 3.5 hours.
All biases (0,0.02 0.02) except residual projections which are initialized /O, 0.02/ /2 Mayar)
Tokenization We tokenize each state a single token. Since do not have task tokens or separator tokens, the model is trained on & tokens. The only exception is the transition encoding tokens experiments in Sec. 4.3 and Fig. where we include the last transition into all tokens. In this case, we define 222 + l tokens where 12 tokens are used to represent all transitions while tokens are used only to indicate the first state, for which the last transition is not defined.
Optimization We trained the model above using sequences from the DGP in Sec. A.I with an autoregressive next-token prediction cross-entropy loss. We used the AdamW optimizer (Loshchilov & Hutter, 2019) with learning rate 6 x 10-4 We kept the estimated FLOPs constant to x 16 where we estimate the compute by 6DN (D denotes the number of tokens seen during training and N denotes the number of model parameters). This compute estimate is not proportional to wall time, especially since operate with small models, but kept for consistency when scaling the model
19

---

Published as a conference paper at ICLR 2025
in order normalize for faster optimization of bigger models (Kaplan et al., 2020; Hoffmann al., 2022: Bordelon et al., 2024). See App. C.2.3 for further details on scaling. Using a batch size of 128 resulted in training of 107978 steps. Changing the batch size to 64 or 256 had significant changes to results to the hest of our knowledge. We experimented with a learning rate warmup and cooldown, sometimes pointed out to be crucial (Liu al., 2019; Gotmare al., 2018) 8), but found no significant difference.
A.3 EVALUATION DETAILS
Our evaluation process involves two scenarios: In-Distribution (ID) and Out-Of-Distibuttion (OOD). For ID evaluations, we select transition matrix ' from the set Tuain. i.c. the set of transition matrices used to sample sequences for training; for OOD evaluations, we sample a novel transition matrix 7", using again the Dirichlet prior over the row elements?. We next define Markov chain using 7 and sample a sequence of length leval to feed as input to the trained model; unless mentioned otherwise, leval 400. The model then computes probability distribution over possible next tokens given this sequence as context. Repeating this process, we can collect pairs of last tokens from the in-context sequence and the model's 's predicted next token probabilities. This allows us construct an empirical transition matrix, T,, that denotes the model's inferred state transitions based on the provided context and the prior knowledge it may have internalized during training (e.g.. Tuain)- To assess how accurate this predicted transition matrix is, we calculate the expected KL divergence between i and T by marginalizing over the stationary state distribution of T (denoted x*). Details are below.
A.3.1 KL DIVERGENCE
We compute the Kullback-eebler divergence (Kullback & Leibler, 1951) between a model or method's predicted probabilities and the GT probabilities from transition matrix rows quantify performance. We draw an evaluation transition matrix 7 from either the training set or the Dirichlet prior respectively to quantify the ID and OOD performance. Given sequences drawn from T*, we estimate the transition matrix T inferred by either a model checkpoint or one of the two retrieval approaches proposed in Sec. 3.1 (which depend on the context). Given this T, the average KL. divergence for distribution of transition matrices T is then quantified by:
PaJl Bill log
(KI(TITTT)) TEET
Σ T
(8)
T TTET
A.3.2 ESTIMATING TRANSITION MATRICES
To estimate a transition matrix, we need sequences which end with all states in the state space, so that every row of the estimates transition matrix T can be filled. Thus, for each context length, we generate k sequences which end with the states 1 to k. The exact way the estimated transition matrices 7 for the model and the methods are computed is as follows.
We draw sequences from T ending in states from 1 to k, controlling for the desired context length loval (= 400, unless mentioned otherwise). Given sequence ending with a certain state, F2 = i, we can evaluate the next state probability p(z++1 j x1=+) by forward pass through the model and taking the softmax of the logits to obtain estimate of the matrix element iii for all simultaneously. We iterate this process for all last states j E [1, -.....A. k| to estimate the whole transition matrix.
Model
i T : We the same procedure draw evaluation sequences as above, and use Eq. and Eq. 4 to estimate the next state probability.
T We the same procedure draw evaluation sequences above, and use Eq. and Eq. to estimate the next state probability.
We use the Dirichlet prior to define OOD Markov chains primarily for consistency with the training prior. We do note that preliminary experiments show that there are certain phases of training configuration wherein the model generalizes essentially arbitrary prior distributions (see App. and Fig. 37).
20

---

Published as a conference paper at ICLR 2025
Toni-Ing We use equation Eq. 5 to estimate the transition matrix directly.
Bi-ine: We use equation Eq. to estimate the transition matrix directly.
We repeat this process Ree = 30 times for statistical power. For ID evaluations, choose T from the training set Tirin using the task prior P., defined App. A.1. For OOD evaluations, we draw each row of 7 directly from the Dirichlet distribution
in App. A.1.
A.3.3 BIGRAM UTILIZATION AND RETRIEVAL PROXIMITY
We quantify Bigram Utilization and Retrieval Proximity using the following procedure:
Bigram Utilization quantify Bigram Utilization as described in the main text: we shuffle the context and measure the increase in KI.. We normalize this value by the stationary KI. divergence given by simply predicting the stationary distribution over the whole training set.
LL
Shuffiee (T*) - (L( model T model
Utilization = clip
0001
(9)
KL (T
Stationary! [T
where <> is an ensemble average over different samples of ID sequences, T is the model es- timated transition matrix when we shuffle states in the context randomly, and T Stationary describes the transition matrix corresponding to the perfect stationary solution, i.c..
T Stationary [i.j] Tj.
(10)
Proximity to Retrieval Approach We quantify proximity to retrieval approach by constructing a set transition matrices, denoted Trandom. with the same number of matrices as the training set. a model has no bias towards the training set, T miodel inferred from a sequence drawn from 7 (which itself has no bias towards the training set) should be closer Trandom with 50% chance, and thus the expected value of the fraction in Eq. 11 should be unity, yielding null proximity. If the model generates sequence precisely from one of the training set matrices, the demoninator will vanish yielding unity proximity.
Proximity clip ((1
minre K [(TT|] (Todel)) ) ,0, )
minTTTTa Timi K [TT][[TToda model)
(11)
<> is an ensemble average over different samples of ID sequences.
A.3.4 LINEAR INTERPOLATION OF ALGORITHMS
Recalling the main text, defined LIA as:
LIA: arg min Exi:. W..aEA
Prondel (x1:) - Σ Wa * Pa (x
where
Σ Wa w 2 0.
(12)
aEA
aEA
where we are interested in extracting Wa from the model output probabilities and individual algo- rithm's 's probabilities. The positivity constraint exists so that methods can not destructively compen- sate. used the squared error in probability space instead of, e.g. KL divergence, since we found similar results when the fit was successful, while avoiding numerical subtleties.
In practice, we used 300 independent chains to optimize for LIA and find the method weights. To use the method weights for OOD prediction, simply apply:
LIA prediction: Ppred (X1:))
Σ Wa (x(xx.))
(13)
where X14 is the context sequence.
We note that analyzing the deviation of model outputs to single analytic solution has been explored in a linear regression setting (Raventós et al., 2023). contrast, LIA extracts the weights of each member solution in set of solutions using Eq. 7.
21

---

Published as a conference paper at ICLR 2025
A.4 LEARNING CURVES
Fig. 9 shows the learning curves (loss) and ID / OOD KL divergence through training. The data is the same in Fig. but shown plot.
a)
2.4 x 10
2.3 x 10
C.E. Loss
2.2 109
2.1
10
N (data diversity)
109
1.8
22-4
10
10a
10'
10a
b)
23
24=16
10-2
ID KL
2
10-2
26=64
27-128
10
28=256
10a
10a
10
10'
c)
29=512
10a
210=1024
OOD KL
211=2048
10-1
10
10a
10
10²
Training Steps
Figure 9: Online Training loss, ID KI. divergence and OOD KL divergence We show the loss and the ID/OOD KI. divergence. a) The next-token cross entropy loss averaged over the whole sequence. At high data diversity, head. After loss drops, sometimes we find slower further decrease of the loss. We have shown that this dynamics is behind the transient nature of ICL. b) In-Distribution KI divergence. The ID KL divergence monotonically decreasing as expected. This a simple re- re-parametrization of the loss. e) Diitr---Dittiittionnn KL divergence. The OOD KL divergence simply rises for low data diversity (See Sec. D) while suddenly drops for high data diversity. However, we find that this drop be transient, discussed in Sec. 2.1 and explained in Sec. 4.2.
find sudden loss drop with the formation of induction
22

---

Published as a conference paper at ICLR 2025
B MORE ABOUT SOLUTIONS
B.1 INFERENCE APPROACHES ARE "BAYESIAN" WITH RELAXED PRIOR
The inference approaches, i.c., Uni-Inf Inf and Bi-Inf, can be interpreted as a Bayesian inference operation with relaxed hypothesis space. This relaxed hypothesis space is the infinite dimensional space of all transition matrices drawn from Dirichlet distribution. This relaxed prior is in fact required to set up the Uni-Inf and Bi-Inf transition matrices, since without it some matrix elements will be strictly zeros for small context length (specifically, for unobserved transitions). This interpretation thus sets prior distribution that all transition matrix elements even a transition is not observed. This can be seen by setting the second term of the numerator to zero in Eq. 6. The solution is still Bayesian, but only has a "memory" of the distribution of transition matrices and not the distribution of the sequences itself (i.e., the precise transition matrices during training). However, quickly dominate the estimate of as we increase the context, hence yielding a frequentist solution. Specifically, this be seen in the distributional OOD example in Fig 37, where the context is drawn from a distribution extremely far from the Dirichlet prior.
non-zero
expect the context dependent part of Eq. and Eq. 6 very
B.2 UNIGRAM POSTERIOR SOLUTIONS
Other than the four algorithms discussed in the main text (see Sec. 3), we formalized two more algorithms but found that they did not significantly contribute to the model explanation in the linear combination of algorithms analysis. Thus we focused our analysis on the four solutions in the main text. Nevertheless, we describe these two solutions and their properties here.
Unigram based Retrieval with Unigram Posterior. This algorithm is similar to Uni-Ret in Sec. 3.1, however it draws the next token from the stationary distribution corresponding to the cho- sen training set chain. This algorithm expected to be less expressive than Uni-Ret, but we nevertheless observe small contribution from it (overlapping with Uni- Inn,,nf), especially high N. This is expected as a large number of N can easily span the full distribution of stationary distri- butions from Dirichlet distributed transition matrix.
This algorithm is similar to Bi-Ret in Sec. 3.1, however it draws the next token from the stationary distribution corresponding the chosen train- ing set chain. Although the likelihood is sharper than unigram posterior retrieval, exactly the way Bi-Ret's 's likelihood sharper than Uni-Ret, this algorithm again not expressive due to the nature of its output distribution.
Bigram based Retrieval with Unigram Posterior.
23

---

Published as a conference paper at ICLR 2025
C PHENOMENOLOGY OF IN-CONTEXT LEARNING: SUMMARY OF REPRODUCED RESULTS AND IMPROVED UNDERSTANDING
C.I LIST OF PHENOMENA WE REPRODUCE
We first provide short summary of ICL phenomenology we reproduce in this work.
Emergence of Non-Bayesian ICL with data diversity: Prior work exploring linear regression tasks shows that ICL performance drastically improves on OOD data with increase in data di- versity Raventós et al. (2023); Kirsch et al. (2022); Lu et al. (2024). In specific, Raventós et al. (2023) shows that there is threshold needed for a "non-Bayesian" ICL to emerge. Here, we reproduce this data diversity threshold in We reproduce this phenomena as seen Fig. 1 (a), Fig. 3 (a,c) and Fig. 27 (a). We show that this transition happens because of an "inference" ap- proach (see See. 3.2) becoming better than the available "retrieval" approach at this data diversity, echoing the results of Lu et al. (2024). Furthermore we show that in order to observe this transi- tion we need a certain optimization threshold to be reached before a Bayesian circuit (Bi-Ret) dominates. We also show that this threshold can further increase with more optimization the transpose effect of the transient nature of ICL.
2. Formation of induction heads and variants: Induction heads are a specialized attention head that help infer next-token predictions in a context-conditionee manner Elhage et al. (2021); Ols- son et al. (2022); Reddy (2023); Edelman et al. (2024); Akyürek et al. (2024). Often, there is a sudden loss drop that correlates with induction head formation, and we find consistently find this drop occurs in our results with training time: this drop, in fact, is the cause of sudden tran- sition from unigram to bigram dependence in the model. We reproduce this phenomena seen in Fig. 1 (b), Fig. (a.c) and Fig. 27 (b). Interestingly. we find that data-diversity has almost no effect to the formation of this circuit. In App. K, we discuss that this transition is likely an "Optimization Limited Emergence" as opposed to the Bi Bi-Inn Inf vs. Bi Bi-Res Ret transition which is mostly data limited.
3. Transient Nature of In-Context Learning: Recently researchers have found that ICL can be transient during pre-training Singh et al. (2023); Anand et al. (2024); Panwar et al. (2024). In this work we show that this happens when a solution performing better on the training set emerges later in optimization, likely due to its complexity. We reproduce this phenomena when there is enough data diversity to allow Bi- Bi-Inf
emerge before Bi-Ret. implemented, largely between N = 2 and N = 20 This is demonstrated in Fig. 1 (c), Fig. 27 (c). See also Fig. 10) for direct comparison with Singh et al. (2023).
4. Task Retrieval to Task Learning transition: Researchers have classified the operation of ICL. as either "task retrieval" or "task learning" (Min et al., 2022; Pan et al., 2023). To this end, such papers explore effects of, e.g., shuffling next-token predictions in few-shot tasks and finding that one can still achieve almost similar performance as the scenario when exemplars are matched with the correct labels (Min et al., 2022; Lu al., 2021). In our work, the unigram retrieval approach to ICL captures this phenomenon: since shuffling the tokens does not affect stationary distribution of a sequence, we can retrieve the relevant transition matrix regardless of the states being matched next-state transitions with the correct probabilities. In other words, in context learning performance might not need correct labels if the circuitry to correctly use the question- answer relation has not developed during training. We show that this happens in our setting when the model is under-trained and thus the bigram circuit has not formed yet (see Fig. 5 a).
Early Ascent: Early ascent describes the phenomena where the erron/risk on an ICL. task initially increases before decreasing. This phenomena is empirically observed in Xie et al. (2021) while Lin & Lee (2024) suggests an explanation with the linear regression setting. In this work, we show that this phenomena be reproduced when training with intermediate data diversity N = 2 chains with sufficient optimization to enable Bi-Ret to dominate at small context length. In these settings, the model uses context length dependent superposition of Bi-Ret and In as seen in Fig. 1 (e), Fig. 27 (e).
6. Bounded Efficacy: Bounded efficacy of biased label ICL is observed empirically in Min et al. (2022) and coined as a term in Lin & Lee (2024). In this work, show that this happens when the model's algorithm is a superposition of a retrieval solution and an inference solution, as seen in Fig. (f), Fig. 27 (f). In this case, at short context length the model mostly uses Un Ret,,
24

---

Published as a conference paper at ICLR 2025
and thus retrieving the right task even though the context is shuffled (biased labels) while at long context length it uses Bi-Inf, thus inferring a wrong transition matrix
C.2 IMPROVED UNDERSTANDING OF ICL: INSIGHTS INTO TRANSIENCE AND EFFECTS OF MODEL SCALING
We highlight two specific insights on understanding ICL drawn from our experiments: the dynamics of transience and the effects of model size scaling.
C.2.1 TRANSIENT NATURE OF IN-CONTEXT LEARNING
We reproduce the transient nature of ICL in Fig. 10, making a clear comparison to Singh et al. (2023). Then, applying LIA (see Sec, 4.1), we find precise dynamic that underlies transience: an algorithm that performs better on the training set (and hence ID), but perhaps is more complex to represent, slowly and steadily comes dominate the algorithm that performs well OOD. This yields severe performance degradation on OOD data and leads us to the conclusion: if the best solution on the training set one that does not generalize OOD, but slowly learned due to learning signal from the training loss, ICL can be transient. We also find an interesting memorization dynamic underneath this result. Specifically, as we show in App. E, we can find neurons which are responsible for encoding specific state transitions (i.e., they have low KL divergence with respect to transition probabilities) in the Bi-Ret phase of learning in Fig. 10, but not in the Bi-Inf phase of learning!
a)
Singh at al. 2024
b)
Singh et al. 2024
Phenomena
1.0
peak hright
Porformance
decay clype
trahi
chance
peak awset
oransts steps
2n7
stop
Explanation Phenomena
Ours
d)
Ours
Performance
cooe
000 performance loss
dlow performance gain
2018
"mmthhdd
W "method
Steps
Steps
Figure 10: Explaining the Transient Nature of In-Context Learning Our setup and LIA allows clear understanding of the transient nature of In-Context Learning. a,b) are panels from Singh et al. (2023). a) shows that the training loss slowly decreases after initial drop. b) shows that during the slow drop of training loss the ICL accuracy decreases. c) We find the same phenomenology in experiments. The ID KL divergence, directly related the model's 's loss (see App. A.4), slowly decreases after an initial drop. Our setup has two initial drops due to the formation of induction heads. d) Just like b), we find performance loss (KL increase) in the OOD evaluations during the slow decrease of ID KL. We have very clear explanation to this phenomena in the panels below. The ID KL decreases the Bi-Ret solution, optimal on the training set. slowly replaces Bi-Inf. This change causes the OOD performance to degrade.
C.2.2 ICL AND MODEL-SIZE SCALING
Kirsch et al. (2022) analyzed Transformer models trained to meta-learn, i.e., to learn tasks in-context (aka ICL). Therein, the authors run experiments by changing the model size and find that bigger models can develop a "General Purpose ICI." solution. Here, produce similar results, as shown in
25

---

Published as a conference paper at ICLR 2025
Fig. 11. However, on further investigation, found evidence that results confounded by the faster learning speed of bigger models (Kaplan et al., 2020; Hoffmann et al., 2022; Bordelon et al., 2024). We thus properly normalized the training by FLOPs, shown in the next subsection, and found no model scale dependent emergence. We believe this finding also explains the results by Kirsch et al. (2022), i.e., claim their results confounded by lack of PLLOPS-normalization!
a)
Kirsch et al. 2024
b)
Ours
Transformar
(b)
3.0c-03
10
6.0e-03
Parameters
21
08
29
2.0e+04
006
2.5e+06
21
1.0e-05
4.0c+05
16 32 800400400990
Training Chains
Figure 11: Effect of Model Scaling? We find results similar to Kirsch et al. (2022), where we observe both data diversity and model size threshold. a) Figure from Kirsch et al. (2022). b) OOD KL depending model scale, when training for 10000 steps. However, we believe that these results are caused by keeping the number steps constant and not FLOPs. See Sec. C.2.3.
C.2.3 EFFECTS OF MODEL-SIZE SCALING, REVISITED
As argued above in App. C.2.2, we found model size threshold to ICL emergence. However, here we refute our own findings (and hence those of Kirsch et al. (2022)). To this end, we study the effects of model-size scaling at the algorithmic phase diagram level (see Sec. 3).
Effects of equi-FLOPs training while varying model size. First, we train models with equal estimated FLOPs, calculated as 6DN (Hoffmann al., 2022), where D is the number of kens passed through the model and N is the number of parameters in the model. This results a much bigger wall-time for smaller models as they will run for vastly more steps. However, proceed with this normalization for analogy real systems where training is bottlenecked by actual GPU compute unlike our smallest models. The resulting phase diagrams for widths of (32, 48, 64, 96, 128, 192, 256) shown in Fig. 12. Generally, find that Bi-Inf, the gener- alizing ICL solution, is fact suppressed up to higher data diversity. This is well aligned with the intuition that bigger models have more memorization capacity and thus develop memorizing solution more easily.
Effects of equi-FL.PP. training while varying model size. Next, construct diagram spanning data diversity and model width, and show for different amount of FLOPs. This result is shown in Fig. 13. We now see that the effect of model size threshold for Bi- Inf entirely removed! In fact, smaller models are more robust at developing the Bi Inf solution given the same amount of FLOPs. This highlights that normalizing for FLOPs and steps can yield very different qualitative conclusions about the role of model scaling for ICL.
26

---

Published as a conference paper at ICLR 2025
width
width 48
width
width 96
24
N Training Chains
6L3
013 00338
width 128
width 192
width 256
201
Bilrl
Training
Figure 12: Algorithmic Phase diagrams depending on model width We show algorithmic phase diagrams as we increase the model's embedding dimension from to 256. Larger models seem to enhance the memorization solutions.
Training
0.22 %
1.06 %
2.33 %
24.41 %
IN Training Chains 223 3 Sww.
Lid Rie 8-Pat
Figure 13: Algorithmic Phases spanning data diversity and model scale. We see the algorith- mic phases of models depend data diversity and their width. We find that smaller models form Bi-In solution more efficiently, when properly normalizing for FLOPs.
27

---

Published as a conference paper at ICLR 2025
D HIGH DIMENSIONAL DISTANCES
At first glance, could be confusing why a retrieval approach would perform worse with more context on OOD chains. Both retrieval approaches discussed in the main paper (see Sec. achieve lower KL on ID sequences when given more context, as they can determine the transition matrix with higher precision, i.e., sharper likelihood. However, not only their performance on OOD sequences is worse in general, the KL becomes higher with more context. This can be confusing, as even for OOD sequences they are still choosing the "closest" transition matrix a process that should become precise with increasing context.
This counterintuitive result originates from properties distances in higher dimensions. Fig. 14 compares the KL of a freshly drawn 7 to the distributional mean and the nearest neighbor from big set of draws, representing the training set. the nearest neighbor will be closer to novel draw compared to the distributional mean. However in higher dimensions, it is increasingly the case that the distance to the distributional mean is closer than the nearest neighbor. We quantify this in Fig. 14 (b,c,d) using 30 different seeds. For different values of N, i.e., number of Markov chains in training data, we find consistently that as k increases, the KI to the distributional mean increases much more moderately than the nearest neighbor KI.. This is the reason why retrieval approach could perform worse with more context: as more context added, retrieval approach chooses transition matrix with a higher precision. However, as seen from the tests in Fig. 14, choosing the nearest neighbor transition matrix is in fact worse than averaging over all transition matrices seen in training uniformly.
dimensions, as seen Fig. (a), it clear that
a)
Training Set
Moan of Distribution
Distance to Mean
Distance to Nearest Neighbor
k-10
b)
c)
d)
N=25
N=27
N
KL
0.5
0.5
0.5
0.0
0.0
0.0
2
16
16
64
8
32 64
k
k
Figure 14: High Dimensional Distances We show that the distance of point the nearest neighbor within a set of points increases faster than the distance to the distributional mean as the dimension increases. (a) Schematic of the distances. In 2 dimensions, it is much more intuitive think that the nearest neighbor of set of points is closer than the distributional mean. (b, c, d) However, show that in higher dimensions the nearest neighbor distance increases quickly while the distributional mean stays relatively constant. This relation is only mildly affected by changes in the number of elements in the nearest neighbor pooling set (n).
28

---

Published as a conference paper at ICLR 2025
E MECHANISTIC ANALYSIS
In this section, we perform preliminary mechanistic analysis provide further evidence for the claims from main paper. Specifically, we perform the following experiments.
Reconstructing Markov Chains from MLP Neurons in Retrieval Phases. In Sec E.1, attempt to directly retrieve the transition matrices of Markov chains used during training by ana- lyzing the MLP weights of the model, demonstrating successful retrieval in low diversity settings.
Dynamics of Memorization. In See E.2, quantify the extent to which individual neurons memorize transition matrices by measuring the minimum KL divergence between neuron outputs and in-distribution transitions across training, showing greater memorization in retrieval phases.
Attention Maps: Aggregating Context Statistics. In Sec E.3, we further visualize attention maps to infer the specific algorithms implemented by the model during different training phases.
Attention Maps' Evolution Corroborates LIA. In See E.4, we investigate the evolution of attention maps throughout training, finding evidence for shifts in algorithms predicted by LIA.
E. RECONSTRUCTING MARKOV CHAINS FROM MLP NEURONS IN RETRIEVAL PHASES
In Sec. 3.2, we claim that for certain experiment configurations, the model relies on a fuzzy re- trieval approach to perform the finite mixture of Markov chains task. Specifically, this corresponds to the phases wherein the model is involved in the Uni-Ret and Bi-Ret algorithms. To pro- vide further evidence towards these algorithms explaining model behavior in these phases, we try to reconstruct the Markov chains seen during training (denoted Train in the main paper) from its internals--pecfffccllly from the MI.P neurons. This analysis builds on the approach for knowledge localization by Geva et al. (2021).
Model Setup. Based on our analysis in See. 4.1, we know that fully trained models with data di- versities N = 2 and N 2 should possess mechanism that is behaviorally equivalent to the Bi-Ret algorithm; meanwhile, for
2" the model should implement something akin to the Bi-Inf solution. Ideally, this implies,
reconstruct the Markov transition matrices used to generate training sequences directly from the model weights in the retrieval phases, whereas for inference-based phases we should yield less accurate (if any) reconstructions. Note the reconstruc- tions may still be feasible in the inference-based phases since the model generally arrives at them after going through a retrieval-basee phase.
Approach. In the following, we use the term neuron to refer to an entry in the second fully con- nected layer of an MLP of the second (i.e., last) Transformer block. For each neuron, we compute its next-token distribution (called neuron output) by applying the final LayerNorm, multiplying by the Unembedding matrix, and applying Softmax. We then randomly sample Markov chain seen during training, and compare the rows of its transition matrix to neuron outputs. We then select the neurons with the smallest KI. divergence to form a row the "reconstructed matrix".
Results. We provide visualizations of the reconstructions in Fig. 15. Note that the Markov chains are redefined for different experiments, and hence the transition matrices targeted for reconstruction are different for different experimental settings. To assess the accuracy of the reconstruction more quantitatively, we also report the average KL divergence between the reconstructed and the targeted ground truth transition matrix, averaging over 100 randomly selected rows from different transition matrices." We also report the average KI. between the stationary distributions of a randomnly sam- pled chain's 's transition matrix and its reconstruction (see Table 1). To contextualize these quantitative experiments, we report two baselines as well.
1. Random model's ability to reconstruct a transition matrix: We take a randomly initialized model and report the KL it achieves when trying reconstruct transition matrix.
2. Trained model's ability to reconstruct an unseen transition matrix: We take a trained model, sample unseen transition matrix, and analyze whether we can reconstruct such unseen
'Performing this analysis over all seen matrices can be prohibitively expensive, requiring analysis of as many as 20480 transitions, and hence we focus on only 100 randomly-sampled transitions instead of all seen matrices.
29

---

Published as a conference paper at ICLR 2025
matrix. Since random model's neurons likely to be arbitrary in their weights, believe this baseline offers a more meaningful comparison.
Using Weights
Diversity laras
Gread fueeiie Mere
cemetraten burat Merie
Using Direct Nouron Waigtt Recanstruct Tranistion Matrix For Data Divensity 2-11 (KL)
Gwel Tuesbee Meve
Breeicater bursiie Mont
Figure 15: Reconstructing Markov Chains from Neuron Weights. We show that transitions from Markov chains seen in training (left column) can be directly reconstructed from neuron weights (right column). As expected, results are especially good low data diversity settings (top row). Reconstructions in the medium data-diversity are structurally sound (more or less the same tran- sitions have highest probability mass as ground truth), the precise magnitudes are off (middle row). Mcanwhile, the reconstructions for high data-diversity quite poor, barely capturing the structure of the transition matrix and almost uniformly spread magnitudes (bottom row).
Table 1: Reconstruction similarities for IDD and OOD transitions.
Category Random model
Avg KL
Stationary KL
0.34
0.30
Seen chains
N = 22
0.09
0.09
N = 26
0.11
0.11
N 211
0.17
0.17
Unseen chains
N 22
0.17
0.16
N 26
0.13
0.13
N = 211
0.18
0.22
30

---

Published as a conference paper at ICLR 2025
E.2 DYNAMICS OF MEMORIZATION
In the previous section, we posthoc analyze trained models to assess signatures of memorization. We now perform this analysis over time, hence yielding the dynamics of memorization.
Approach. To demonstrate that neurons store transition matrices as part of retrieval solutions, we evaluate their outputs for both in-distribution and out-of-distribution transitions. Specifically, we repeat the analysis from previous section across time: we randomly select 100 in-distribution state transitions from the training data (sampling chains and transitions with replacement) and compute the outputs of all neurons in the second MLP layer. For each transition, we identify the neuron with the minimum KL divergence from the target transition distribution and record the average minimum KL across all 100 transitions. This process is repeated at every training checkpoint.
Baseline. As baseline, we apply the same procedure to 100 unseen transitions. Additionally, we create a second baseline by sampling 256 random vectors (matching the number of neurons in the MLP layer) from Dirichlet distributions with a = 1ş (k = 10). For each of these random vectors, we compute the minimum KL divergence with the 100 in-distribution transitions. This baseline assesses whether the observed neuron behaviors reflect structured learning of training-specific distributions merely random mappings.
Results. As shown in Fig. 16, neurons closely align with the specific transitions observed during training in lower data diversity settings. This is especially the case when the model enters the Bi-Ret phase, where the KI. from seen transitions starts to substantially diverge from that of unseen transitions. This pattern partially shows up for medium data diversity N 26, consistent with LIA's prediction that the model continues to perform bigram retrieval. However, for large data diversity N 2 the neurons show greater dissimilarity the training transitions compared to random transitions, suggesting that the model is no longer memorizing transitions in this regime.
E.2. SUPERPOSITION OF NEURONS WITH INCREASE IN DATA DIVERSITY
In Sec. 3, we claim models in high data diversity scenarios rely on inference-based algorithms. Consequently, as data-diversity increases and the ability to rely a retrieval approach goes down, we hypothesize that predicting the correct next-token distribution likely requires a complex linear combination of neuron outputs. If this were not the case, we would need to scale the number of neurons in proportion with data diversity to witness a retrieval based solution. To circumvent this, the model then likely represents transitions across several neurons akin the superposition effects discussed by, e.g., Henighan et al. (2023); Elhage et al. (2022).
Results. To quantitatively investigate the hypothesis, we analyze neuron activity across different data diversity regimes. As shown in Fig 17a, the distribution of neuron activity is sharply concen- trated in lower data diversity regimes and is smoother as data diversity increases (with the most active distribution observed at data diversity 2 This supports our hypothesis that representations are distributed across neurons. In panel (b), we examine linear combinations neuron outputs and their similarity to the ground truth transition. Neurons first sorted by their GeLU activations on in-distribution samples. For the k-th linear combination, the top neuron outputs are aggre- gated, weighted by their respective GeLU activations, and summed to form a composite output. Our findings reveal that as data diversity increases, more neurons are required to reconstruct the ground truth transition. This suggests that higher data diversity leads the model to adopt more distributed representations, providing more support for our hypothesis.
31

---

Published as a conference paper at ICLR 2025
Avg Min Neuron KL ID
Uni-Ret.
Avg Min Neuron OOD
Ret.
Random Dirich
Bi-Inf.
0.
Algorithm Probability
KL Divergence
0:25
(a)
0.20
10
107
16
35
Aug
Min Neuron 00D
Bi-Ret.
Random Dirich et Baseline
Uni-Inf.
Algorithm Probability
Divergence
0.
(b)
100
20
324
Min Neuron ID
Uni-Ret.
Avg Min Neuron KL 00D
Bi-Ret.
0.30
Random Dirich et Baseline
Uni-Inf.
Algorithm Probability
0.25
Divergence
(c)
0.20
0.4
10a
10a
16*
Training Step
Figure 16: Memorization as Training Progresses. Minimum KL of transitions from training and neuron outputs, averaged across 100 randomly selected transitions. a) N = 22. b) N = 29, c) N 211, Lower data diversity settings display much greater degree of similarity with training transitions than higher data diversity settings.
32

---

Published as a conference paper at ICLR 2025
2n2
05
2n2
2
2>11
2-11
08-
Mean KL with GT Transition
Mean GeLU Activation
024
08-
02-
86
Sorted Neuron Ranking
of Neurons in Linear Comb.
(a)
(b)
Neural Activity Across Increasing Data Diversities. a) Sorted GeLU activations of neurons, normalized by their maximum activation, are shown for increasing levels of data diversity. the Bi-Ret regime, significantly fewer neurons are active compared to the Bi-Inf regime. b) Similarity of linear combinations of top neuron outputs to the ground truth transition. As data diversity increases, a larger number of neurons are required to reconstruct the correct ground truth transition.
Figure 17:
33

---

Published as a conference paper at ICLR 2025
E.3 ATTENTION MAPS: IMPLEMENTING INFERENCE APPROACHES
We visualize attention maps to provide further evidence for our algorithmic solutions. Specifically, train model with single attention head to avoid the ambiguity of choosing the most relevant attention head for model behavior or an algorithm being implemented over different heads. While in this section we focus on only single value of data-diversity (N 29), App. E.4, we will show the effects of data-diversity as function of number of iterations, contextualizing the results in light of different algorithmic phases to provide evidence in support of the validity of L.A.
Analysis of first layer's attention head. Fig. 18 shows the first layer attention matrix when context sequence is input to the model. This model is trained using N 2 training chains, and the dominant algorithm changes from Uni -Inf Bi Innf to Bi Rett.
Fig. (a) shows that the attention map is uniform at model initialization.
Fig. 18 (b) shows the attention pattern at step 189, corresponding to Uni-Int solution. Each position attends to most tokens in the context, enabling a frequency count. This is consistent with the hypothesis that the model is simply computing the unigram distribution.
Fig. 18 (c) shows the attention pattern step 855, corresponding to our analysis in Sec. 3. Each position attends almost only to the previous token. This is a characteristic of induction head (Elhage al., 2021; Olsson et al., 2022; Edelman et al., 2024; Akyürek et al., 2024) for copying or gathering statistic from a context. This consistent with the hypothesis that the model is performing a statistical induction enable computation of the bigram statistics, as theoretically characterized by Edelman et al. (2024).
Bi-Int solution according
Fig. 18 (d) shows the attention pattern at step 10133, corresponding to a B Bi Ree solution. Each position now attends to the previous token and partially the current token. This is consistent with the hypothesis that this head is forwarding transitions to upper layers of the model, where upper layers are expected count them.
Analysis of second layer's attention head. Fig. 19 shows the second layer attention maps for the same sequence input as in Fig. 18.
Fig. 19 (a) shows the uniform attention at initialization.
Fig. 19 (b) shows that the attention pattern for Uni-Inf is mostly uniform, again consistent with the hypothesis that it computes histogram. Note that it is unclear of yet how much of the histogram computation is delegated to layer or 2.
Fig. 19 (c) shows that the second layer attention pattern for the model performing Bi-Inf is consistent with our hypothesis. We draw a red cross wherever the query state matches the previ- ous state of the key state. These red crosses precisely overlap where the attention pattern peaks: alongside the first layer head, this head combines to form the induction head as in Edelman et al. (2024).
Fig. 19 (d) Interestingly, the second layer attention again becomes uniform as the model drifts from Bi-Inf to Bi-Ret. This is again consistent with the hypothesis that the first layer at- tention presents transitions into the residual stream so that the second layer attention can count these transitions.
By visualizing the attention patterns, we find that the observed patterns are consistent with how we would expect the 2 layer transformer model to implement the solutions in Sec. 3.1. While these results are strongly suggesting our algorithms are implemented, causality experiments (Nanda et al., 2023; Li et al., 2023a; Hazinch et al., 2023) attention patching could help confirm these results in the future.
34

---

Published as a conference paper at ICLR 2025
a)
Init (step=0)
b)
Uni-Inf (step-189)
0.5
0.5
Query Index
0.4
Query Index
0.4
10
0.3
0.3
15
15
20
20
0.1
0.1
25
25
10
20
0.0
10
0.0
Key Index
Key Index
Bi-Inf (step-855)
d)
Bi-Ret (step- 110p-31
0.5
01
0.4
0.4
Query Index
Query Inder
0.3
0.3
15
0.2
0.2
20
20
25
25
Key Index
Key Index
Figure 18: First layer attention maps from the = 26 run. We visualize the first layer attention maps from different points in the checkpoint. Each query normalized by the maximal value present in the row for visualization purposes. The title shows the number of training steps elapsed as well as the dominant strategy at the checkpoint. a) The attention map initialization. The attention pattern is mostly uniform. b) The attention map during Uni -Inf. The attention map attends to most tokens in the context. The attention map during Bi Inf. The attention pattern clearly implements an induction head, where the first layer attends to the previous token It-1 and thus provides potential copy the current token H, given the same token as Ft-1 appears. d) The attention map during Bi-Ret. The attention pattern develops non-zero values for the diagonal entries. This suggests that this head might be combining information from two subsequent tokens for be available for the next layer to We trained model with single attention head to avoid the ambiguity of choosing the most relevant attention head for model behavior or an algorithm being implemented over different heads.
35

---

Published as a conference paper at ICLR 2025
a)
(step-0)
b)
Uni-Inf (step- 189)
0.5
Query Index
Query Index
10:
10
0.3
15
0.2
0.2
0.1
0.1
25
20
0.0
10
0.0
Key Index
Key Index
Bi-Inf (step=855)
d)
Bi-Ret (step= 1ttep=100133) 110133)
0.5
0.5
0.4
0.4
Query Index
Query Index
0.3
0.3
1.5
15
0.2
20
20
25
25
0.0
0.0
10
Key Index
Key Index
Figure 19; Second layer attention maps from the N = 26 run. We visualize the second layer attention maps from different points in the checkpoint. Each query normalized by the maximal value present in the row for visualization purposes. The title shows the number of training steps elapsed well as the dominant strategy the checkpoint. a) The attention map at initialization. The attention pattern is mostly uniform. b) The attention map during Uni Uni-Inf. The attention map attends to most tokens in the context. с) The attention map during Bi-Inf. The red crosses are locations where we find that the query state matches the previous state of the key state. We find that the attention pattern clearly implements this logic. d) The attention map during Bi-Ret. The attention pattern is again mostly uniform.
36

---

Published as a conference paper at ICLR 2025
E.4 ATTENTION PATTERN EVOLUTION CORROBORATES LIA
Our analysis of MLP neurons in App. E.I, E.2 helps provide mechanistic evidence in support of retrieval-based approaches by demonstrating the memorization of Markov chains during train- ing. Meanwhile, the analysis in App. E.3 demonstrates different attention head patterns that provide evidence for unigram vs. bigram strategies, especially ones that finally aid an inference-bare eaaeeeeeeeeeddddd algo- rithm. These analyses thus demonstrate the model possesses components necessary for implement- ing four of our identified algorithms. We now contextualize these results by analyzing the evolution of attention heads for different data-diversity values the model makes its way through different algorithmic phases, providing evidence for LIA's validity. this end, we first plot results points where the model is in different algorithmic phases, and then when the model is at the phase bound- aries, where, if LIA is an accurate methodology, we would expect a simple linear interpolation of attention maps from different phases would approximately match the actual attention head retrieved from running a forward pass on the model.
E.4.1 VALIDATING LIA: ATTENTION HEADS DIFFERENT PHASES
Figs. 20, 21, and 22 show attention maps for different data diversities and different checkpoints specifically, checkpoints that correspond to particular phases in the learning dynamics. As we can see, LIA effectively predicts algorithmic shifts in the model across training steps and data diversi- ties. For N = 29, the model transitions from induction head configuration to bigram statistical pattern, consistent with the prediction that it relies on an inference-bart based solution (Fig. 21). Simi- larly, for N 22, the model begins using bigram statistics only when in the bigram retrieval state (Fig. 20). Finally, for N 211, the model demonstrates induction behavior in the bigram inference state, which was evident earlier (Fig. 22).
2
Algorithm Probabilitee
2 Query Indlex
Biire
Biinr
Query Index
Query Index
Key Index
Key Index
Training Step
Figure 20: Attention Maps At Key Checkpoints Across Training For N 2a. a) Training checkpoint with maximal likelihood of Uni-Inf according to LIA. b) Training checkpoint with maximal likelihood of Uni-Ret according to LIA. Training checkpoint with maximal likelihood of Bi-Ret according to LIA.
37

---

Published as a conference paper at ICLR 2025
Layer
Layer 2
Algorithm Probabilitins
Urd
Query Index
Query Index
Query Indlex
Key Index
Key Index
Training Step
Figure 21: Attention Maps At Key Checkpoints Across Training For N = 2 a) Training checkpoint with maximal likelihood of Uni Oni-Inf according to LIA. b) Training checkpoint with maximal likelihood of Bi Inf according to LIA. c) Training checkpoint with maximal likelihood of Bi-Ret according to LIA. red indicates the position after previous occurrences of the current tokens during Bi-Inf.
Algorithm Probabilitee
Query Index
Bi-ter
Querr Index
Key Index
Index
Training Step
Figure 22: Attention Maps At Key Checkpoints Across Training For N 2 a) Training checkpoint with maximal likelihood of Uni-Inf according to LIA. b) Training checkpoint with maximal likelihood of Bi-Inf according to LIA. A red indicates the position after previous occurrences of the current tokens during Bi-Inf.
38

---

Published as a conference paper at ICLR 2025
E.4.2 VALIDATING LIA: ATTENTION HEADS AT PHASE BOUNDARIES
We next want explore the model's mechanisms when LIA predicts the dominant algorithm is changing. Figs. 23, 24, and 25 show that the attention patterns during these states appear to inter- polate between those observed when LIA predicts each algorithm as the most likely. For instance, during the transition from Bi Inf to Bi Bi-Ret, the attention pattern resembles an interpolation of the two.
To validate this observation, we manually interpolate between the attention patterns of the last two algorithms the model implements during training across data regimes. As shown in Fig 26, the interpolated attention maps are highly correlated with the ground truth attention maps, supporting hypothesis that the model transitions between the algorithms at this point.
Layer
Algorithi Probabilites
Briee
Query Index
Query Index
Key
Training Step
Figure 23: Attention Maps At Predicted Transition Points For N = 2 First predicted transition checkpoint according to LIA. b) Second predicted transition checkpoint according to LIA.
Layer
Algorithm Probabilitee
Query Index
Query Index
Key Index
Training Step
Figure 24: Attention Maps At Predicted Transition Points For N 25. a) First predicted
transition checkpoint according to LIA. b) Second predicted transition checkpoint according to LIA.
39

---

Published as a conference paper at ICLR 2025
Layer
Layer 2
Aggorithm Probabilities
Query Index
Key Index
Index
Training Step
Figure 25: Attention Maps At Predicted Transition Points Across Training For 2
Comparing GT Actencion Pattors Trasition Interpo acted Attention Pattems
Comparing GT Athenion Pattems "Pansiiion interpo ates Attent Retterns GT Layer Attension at Trancitoon on IST Layer 2 Attention Tansiton
GT Layer Attention at Tardtton GT Layer 2 Alter tion at Transition
(b)
Uniftt Si-tet Bayer
Uni-ten Bileet Rayer
Bent Bitut Happrr
Schi B-Bell
Camparing Attenties
Transiion tnderpoiated Albention
Layer Allention Panstion Layer Altention
(c)
Uni int x IPT (Layer
Uni XII In. Gayer 21
Figure 26: Attention Interpolation. Manually interpolating between attention patterns correspond-
ing to different algorithms closely matches the attention patterns observed during training when model predicted to be transitioning between these algorithms. This supports the hypothesis
that the model is implementing these two algorithms during training. (a) N 2 (b) N 2 (c)
N 21
40

---

Published as a conference paper at ICLR 2025
F ADDITIONAL RESULTS
F.1 ADDITIONAL PLOTS FROM THE MAIN EXPERIMENTS
In this section, we visualize our main experiments more detailed manner. Specifically, we first show a high quality version of the subplots in Fig. 1. Next, we show 2D and 3D heatmaps of KL divergence on OOD vs ID sequences. Third, we show different slices our of experiment to show the evolution of the KI. divergence as we change the optimization steps, data diversity, and context length independently. Finally, we directly evaluate the KL divergence between the model and each solution to verify our findings in Sec. 3.2 and Sec. 4.1.
F.1.1 HIGHI QUALITY VERSION OF FIG. SUBPLOTS
We reproduce the small subplots of Fig. I here in Fig. 27. The color of every subplot corresponds to their algorithmic phases, except (d), where the color represents OOD KL divergence. Each plot has other fixed axes annotated. These subplots corresponds the phenomena discussed in App. C.I.
a) Data Diversity Threshold
b) Induction Head Emergence
c) Transient Nature of ICL
steps-best Context-400
N-211 Context-400
N-27
Context-400
0.5
0.4
= 0.05
0.2
bakel
0.2
0.1
0.0
2'
2"
2
2
2
0.05
Training Chains
Sheps
Steps
d) Task Retrieval vs Task Learning
Early Ascent
Bounded Efficacy
N=26
N=25 steps=26355
N=210 steps=839 839
Context Stza
310
110
0.50
0.55
063
0.8
Stufted
250
Varickent:
0.6
235
0.50
0.4
0.45
0.2
0.40
100
200
400
10
10
10a
Steps
Context Size
Context Size
Uni-Ret
Bi-Ret
Uni-Inf
Bi-Inf
Figure 27: Subplots of Figure 1 We reproduce the subplots of Figure here for visibility. a) Data diversity threshold (Raventós et al., 2023); b) Emergence of induction heads (Edelman et al., 2024); c) Transient nature (Singh et al., 2023; Anand et al., 2024; Panwar et al., 2024); d) Task retrieval and task learning phases (Min et al., 2022); Early ascent of risk (Xie et al., 2021); and f) Bounded efficacy (Lin & Lee, 2024).
Fig. 27 (a). We reproduce the data diversity threshold (Raventós et al., 2023), where certain num- ber of task (here 26) is required for the model to learn an optimally OOD- N0D-generalizing ICL solution (Bi-Inf).. Note that selected the checkpoint with the best OOD performance throughout train- ing.
Fig. 27 (b). We reproduce the emergence of induction heads (Edelman al., 2024), where the model transitions from Uni-Inf to Bi-Inf
Fig. 27 (c). We reproduce the transient nature of ICL (Singh et al., 2023; Hoogland et al., 2024), where an DOD-generalizing solution inf is learned, but disappears with more training as a retrieval solution (Bi (Be))et) slowly replaces it.
41

---

Published as a conference paper at ICLR 2025
Fig. 27 (d). We reproduce the findings Task Retrieval Task Learning. Please see App. C.1 for a detailed discussion.
Fig. 27 (c). We reproduce the Early Ascent phenomena where small amount of exemplars harm the ICL performance. This has been observed in Xie et al. (2021). Our explanation is from the phase diagram. The model implements Bi Bi-Ret for small context length and this causes wrong task retrieval, as explained in App. D. This lost performance is recovered as the model performs Uni-Inf when more context is given.
Fig. 27 (f). We reproduce bounded efficacy shown in (Min et al., 2022; Lin & Lee, 2024). When we shuffle labels, analogy the perturbation in Min et al. (2022), the OOD KI. first decreases since it finds roughly the right algorithm via Uni -ett. However with more context the Bi - IInf strategy kicks in, and as the model learns transitions from a wrong context, the KL does not improve (and in fact slightly increases). This is similar to the explanation of bounded efficacy in Lin & Lee (2024).
F.1.2 KI. DIVERGENCE HEATMAPS
In Fig. 28, show 3D plot of the KL divergence for ID sequences and OOD sequences. We find that the ID KL always decreases with less data diversity (since the task simpler), more context (more information), and with more training. OOD KL divergence, monotonicity in two axes: steps and context. Especially, with more optimization steps the OOD KL divergence shows up-down non-monotonicity (2 similar double descent), down-up monotonicity (n = 26, transient ICL) and up-down-up non-monotonicity (n = 2 explained by 3 mechanisms).
the other hand, shows non-
In-Distribution
Out-of-Distribution
Tommnng Chains
20
2.
28
25
2
2
cek- size
40
2
cck size
2"
100
2
100
49
49
613
7525
160
613
7525
160
Steps
92318
N Steps
92318
Figure 28: 3D heatmap ID/OOD KL divergence. (left) KI. divergence on ID sequences. (right) KL divergence on OOD sequences.
In Fig. 29 (a), we show the ID KL corresponding to Fig. 3. We find that the ID KL divergence drops with the induction head formation for high data diversity, but drops earlier for lower data diversity. We explain this by a Uni Ret solution developing for small data diversity, as seen in Sec. 4.1. Fig. 29 (b) is equivalent to Fig. 3 (a). Fig. 29 (c) shows the difference between the ID KI. and the OOD KL, clearly highlighting regions where the model follows retrieval approach.
Fig. 30 illustrates the ID and OOD KL divergence depending on context size and optimization steps for N = 22, a low data diversity. Fig. 30 (a) shows that the ID KI. divergence always decreases with more context and more training. Fig. 30 (b) shows that unlike the IDD KI., the OOD KI. has an ascent and decent in both optimization steps and context size. As we increase the concext size at step=26357, we find that the KL divergence first rises before falling. This is precisely the early ascent phenomenon Xie et al. (2021). Fig. 30 (c) shows the difference between the ID KL and the OOD KL, clearly highlighting regions where the model follows a retrieval approach.
Fig. 31 illustrates the ID and OOD KL divergence depending on context size and optimization steps for = 26, a medium data diversity. Fig. 31 (a) shows that the ID KL divergence again always decreases with context and more training. The only qualitative difference from Fig. 30 (a) is
42

---

Published as a conference paper at ICLR 2025
ID
b)
OOD
KL Difference
Traiinn Me ma 1 3
67
Trikiing Chaiee
07
644 F
04 P
Trahhing
63
03
62
201
100 2012
403
210 TOL
307 wiee
2-1 201 1000 101a
Training Steps
Training Steps
Training Steps
Figure 29: KL divergence depending on data diversity and optimization. a) ID KL divergence. b) OOD KL divergence. c) Excess KL divergence on OOD sequences.
2
b)
OOD
KL Difference
400
0.79
666
Context Size
113 2011 52. Training Steps
Ja0 1018
197 (N31 M70 Training Steps
218
2013 R20 J60 1014
Training Steps
Figure 30: KL divergence depending on context size and optimization steps for N = 24, a) ID KL divergence. b) OOD KL divergence. c) Excess KL divergence on OOD sequences.
that there is much sharper evolution near step ~ 6 102. Fig. 31 (b) shows that the OOD KL shares this drop, but only to increase KL again the training proceeds. This is exactly the transient nature of ICL revisited. Fig. 31 (c) shows the difference between the KI. and the OOD KI., highlighting regions where the model follows a retrieval approach.
N
a)
ID
b)
OOD
KL Difference
Contert 00000
Content Sire
Contoxt
02
023
Training Steps
Training Steps
Training Steps
Figure 31: KL divergence depending on context size and optimization steps for = 29, a) ID
KI. divergence OOD KI. divergence. Excess KI. divergence OOD sequences.
F.1.3 KL DIVERGENCE vs. (STEPS, DIVERSITY, CONTEXT)
Recall that we showed model's ID and OOD KL divergence vs. N 839 steps of training in Sec. 2.1 (Fig. 3 (b)). This specific value was used as representative setting as it clearly demonstrates the data diversity threshold "inference" solutions to emerge. For completeness, we now show similar plots for different number of training steps Fig. 32. Additionally, plot the four different solutions' ID and OOD KL divergence as well. We can clearly observe the transition from Uni E to Bi Inf for high N, while, at low N, the ID and OOD KL divergences split because of retrieval solutions.
Recall also that we showed the model's ID and OOD KL divergence for N 27 in Sec. 2.1 (Fig. (c)). This value was chosen transient nature ICL. However, for completeness, we show similar plots for many different values of in Fig. 33. Again, plot the four different solutions' ID and OOD KI. divergence well. We
representative setting since it clearly demonstrates the
43

---

Published as a conference paper at ICLR 2025
a)
step 49
b)
step 383
c)
step 613
0.5
0.0
0.8
0.6
0.6
0.5
0OD
ID
6.2
0.2
0.2
0.0
0.0
0.0
10
10
10
10
10
10
10
10
10
step 2148
e)
step 10294
f) step 107978
Uni-Ret
Bi-Ret
0.5
0.8
0.8
Uni-Inf
0.6
0.6
Bi-Inf
62
0.2
0.2
10
10
10 10 10
10' 301 10
10
N
N
N
Figure 32: KL vs. N at fixed step. We show the effect of data diversity at fixed number of gradient steps. We plot the model's KL divergence with respect to ground truth for both ID and OOD chains in black. We also plot the ID and OOD KL for each of the 4 solutions. Note that while the solutions' expected KL divergence is, in theory, smooth, we estimate them numerically from Eq. 5 and Eq. over 30 transition matrices, thus resulting in some noise. In each plot, the number of training steps fixed, as denoted in the title, and the KI. divergence is averaged over a context size of 400 and over 30 random transition matrices.
can clearly see the emergence of B Bn and the transient nature driven by Uni -Ret or Bi- BieR... Notable phenomena we observe are as follows.
1. Panel (a): We observe very robust Bi Ret solution for 22, very low data diversity,
2. Panel (c): We observe highly con-monotonic OOD KL divergence for N = 25, medium data diversity.
3. Panels (d, e): We observe at high data diversity
26, 2 the transient nature of ICL. Specifically, the model first finds the Bi -if solution and then moves to a retrieval solu- tion which harms the OOD KL.
4. Panel (f): At very high data diversity (N = 211,, we observe that the Bi-Ret solution does not show up (at least not noticeably) within the compute budget.
We show both the ID and OOD KL divergence the model and different solutions at fixed N, step, and across context length in Fig. 34. Each subplot marked on the phase diagram. We find that, as expected, the model's KL divergence, both ID and OOD, follows that of the dominant solution in each phase. Notably, the agreement with Bi is very strong.
44

---

Published as a conference paper at ICLR 2025
a)
N=22
b)
N=24
c)
N=25
1.0
0.6
00D
0.4
ID
0.0
0.0
d)
N
N=28
f)
N N 211
Uni-Ret
0.6
Bi-Ret
Uni-Inf
Bi-Inf
0.2
0.0
0.0
Training Steps
Training Steps
Training Steps
Figure 33: KL vs. Steps at fixed N. We show the effect of optimization at each fixed data diversity, N. We plot the model's KL divergence with respect to ground truth for both ID and OOD chains in black. We also plot the ID and OOD KL for each of the 4 solutions in horizontal colored lines. In each plot, the data diversity N fixed, as denoted in the title, and the KI. divergence is averaged over context size of 400 and over 30 random transition matrices.
step 280
210 step 2148
N Treining Chains
Pio
0.6
20
0.4
23
0.0
0.0
013
2248
1525 28157 a210
Training Steps
2 step 1147
step 107978
0.8
1.0
Uni-Ret
0.6
Bi-Ret
OOD
0.6
Uni-Inf
0.4
Bi-Inf
0.2
0.2
100
200
300
400
100
Context Size
Context Size
Figure 34: KL vs. context size at fixed N and step. We show the effect of context size at fixed data diversity N and gradient steps. We plot the model's KL divergence with respect to ground truth for both ID and OOD chains. We also plot the ID and OOD KL for each of the 4 solutions. As explained Fig. 32, the solution KLs have a noise contribution. In each plot, the data diversity N and the number of training steps fixed, denoted in the title, and the KL divergence is averaged over 30 random transition matrices. In the left side of the figure, we show where in the phase diagram each of these plots live in.
45

---

Published as a conference paper at ICLR 2025
F.1.4 KL DIVERGENCE BETWEEN THE MODEL AND SOLUTIONS
In Fig. 35, show the KL divergence between the algorithmic solutions and the model timated transition matrix. First, we find that (T KL I Moda) in Fig. 35 are very similar. As discussed in Sec. 3.2, we again find that all four solutions indeed show small KL divergence from the model exactly where we expect them to from Fig. 5 (c). These findings further confirms our findings in Sec. 3.2 and Sec. 4.1 are indeed accurate characterizations of the model's behavior.
quantified in Fig. 5 and
Uni Ret
Bi-Ret
N Training Chains
Uni-Inf
Bi-Inf
0.3 5
0.1
0.0
Training Steps
Figure 35: KI. divergence between algorithmic solutions and the model. We quantify the KI. divergence of each algorithmic solution from the model estimate of the transition matrix, across optimization steps and data diversity. We find nearly identical low KL regions as in Fig. 5 (d). The axes same in Fig. 5.
46

---

Published as a conference paper at ICLR 2025
F.2 ARCHITECTURE CHANGES
Similarly to our analysis in Sec. 4.3, we analyze the effect of different architectural changes to the algorithmic phase diagram. These results shown in Fig. 36.
a) Learned Pos. Embed.
b)
Head
c)
16 Heads
20
24
24
N Traininng Chains
210
21
24
2
21
21
21
21
27
2
2
21
21
2
21
24
2
2
2
24
29 79 212 566
1508 401710697
79
212
536
1508 4017 401730697 10097
20
79
212
556
1505 4017
Training Steps
d)
rMLP 0.25
e)
rMLP 16
2t1
Birl
Figure 36: Algorithmic Phase diagrams for different architectures. Results with a Transformer using learned positional embeddings; b) single attention head; e) using 16 attention heads; d) using an MLP fan-out ratio of 0.25; and e) using an MLP fan-out ratio of 16.
Fig. 36 (a) shows results when using learned positional embedding. A learned positional embed- ding significantly biases the learning dynamics towards the Uni Uni-Res Ret algorithm. We suspect that this is because the formation of precise induction head for B Bi-Ret (See App. E.3) is more difficult with learned positional embeddings without passing through an intermediate Uni -Re solution. As result, the observed data diversity threshold increased from 2 2
Fig. 36 (b,c) shows the phase diagram when using, respectively, single head and 16 heads. We originally expected that more heads would be able to support more solutions simultaneously and a single head will yield sharper transitions. However this did not result in a significant phase diagram change. We speculate that multiple algorithms can exist within one head by dividing up the residual stream's subspace (similar to the argument by Elhage et al. (2021); )); Olsson et al. (2022)). An inter- esting future direction mechanistically analyze the checkpoints after the emergence of Bi-Inf but where Bi-Ret dominated to find out if the Bi Inf circuit still exists but is unused.
Fig. 36 (d,e) shows the phase diagram when changing the MLP fan-out ratio (from the default of 4) to 0.25 or 16. Our prior hypothesis was that MLP layers carry memorization (Geva et al., 2021). This experiment validated our findings. Reducing the MLP layers hidden dimension width significantly suppressed Uni-Ret and Bi-Ret, resulting in Bi-Inf available with 2 chains only. On the other hand, increasing the hidden dimension to 16 caused the run with N = 26 to never show Bi-Inf, as the "memorizing" retrieval solutions are promoted.
47

---

Published as a conference paper at ICLR 2025
G GENERALIZATION TO CHAINS FROM A DIFFERENT PRIOR
In the main experiments, we generally drew the test matrix 7 from the same Dirichlet prior gener- ating the training set. As discussed in App. A.I and App. this evaluation is already OOD, since the Dirichlet prior is only shared between the matrices and not the sequences themselves. However, here we verify that our OOD-gen DoD-generalizing solutions can indeed go far of their training distribu- tions. In particular, we design context which is highly unlikely to be drawn from Dirichlet prior and evaluate different model checkpoints.
Fig. 37 illustrates these results. We fed in context consisting of a repeating pattern of 0, 1,2 and we generate a sequence from the model. We generate the sequence with zero temperature, i.e., select the state with the highest predicted probability. We visualize the next token probability as pixel value intensities. For model implementing mostly the Uni-Inf Inf strategy, we find, as expected, stationary distribution not depending on the last token, and thus not evolving. However, when the model in the Bi-Inf phase, we find that the model can learn in-context to generate this totally out-of-disttn -it-tri-iitiittiinnn chain. Finally, when the model is implementing mostly Bi-Ret, the model implements a completely different chain, which is the training set chain having the most similar transitions. The model now generates different sequence. We find that the non-linear evolution of accuracy reproduced here again, as we see the next token accuracy to rise to 100% when Bi Bi-Inf implemented only fall back to 1/3 when Bi Ret takes over.
T=0.0 Generations
Context
Probabilities
1a--va B L000- wwn- 1000 Joco-ooraaa WN
Uni-Inf
Accuracy:
State
(step=204)
33.3%
Bi-Inf
Accuracy: 100%
State
(step=839)
Bi-Ret (step=107978)
Accuracy:
State
33.3%
0
5
10
15
20
Context
Figure 37: Testing model's ability to generalize far out of the training distribution. We feed a completely out of distribution sequence to the model that consists of repeats of 0, 1,2. The left side shows the sequence and the right side shows the output probabilities for different settings. We generate tokens with temperature T=0.0, and continue to show next-token probabilities conditioned on the generated tokens. (Top) We find that the model in the Uni Uni-Inf dominant phase indeed implements a unigram solution. (Middle) We find that the model in the Bi Inf dominant phase leams the transition pattern in the context successfully generate adequate sequence. The accu- racy rises accordingly. (Bottom) As the pre-training phase is continued, the Bi-Inf solution gets wiped out by the Bi-Ret solution seen in Sec. 4. We find that the model now selects the best Markov chain in the training data, and thus generates a different sequence, resulting in an accuracy drop.
48

---

Published as a conference paper at ICLR 2025
H IN-CONTEXT LEARNING OF MARKOV CHAINS IN REAL LARGE LANGUAGE MODELS
Real language models trained on complex patterns including human languages, code and structured documents are known to acquire general in context learning abilities (Brown et al., 2020). Thus, we expect these models to deliver non-trivial performance at learning to continue a Markov sequence given in-context even though they haven't i been explicitly trained on this task. Furthermore, Wei et al. (2023) showed that larger language models "do in-context learning differently". rougly speaking, in more context- -eeenetdee way. To this end (and also motivated by curiosity) we evaluate the ICL ability of Llama-3.1 (Touvron et al., 2023; Dubey et al., 2024) across model scales: 8B, 70B and 405B. Since LLMs are known to be prompt sensitive (Sclar et al., 2024), we test three different prompts which differ by how precisely the Markovian nature of the sequence is described. We use NNsight and NDIF (Fiotto-Kauun Kaufman et al., 2024) to run these experiments.
Fig. 38 illustrates the results of inputting a sequence from a Markov chain as tokens of digits from 0 to 9. More precisely, we drew transition matrix T from the DGP in App. A.I, and generated 300 sequences to collect next token probabilities to construct I as in App. A.3. We used separator token, "" and we constrained the outputs to the digit tokens.
In Fig. 38 (left) used simple prompt without mentioning "Markov process". Interestingly, found a performance in between Uni-Inf and Bi-Inf, demonstrating Llama is able to model the sequence better than purely predicting random probability from the stationary distribution (histogram), without even being instructed that the sequence is Markovian. Furthermore, bigger models (405B 70B >
8B) are able to model the Markov sequence better (lower KL).
Fig. 38 (center, right) respectively used a prompt which mentions the process is Markovian and a prompt which additionally and explicitly states that next state probabilities only depends on the last state. We find significant KI. divergence improvement on the 70B model when adding these specifications, revealing that LLMs can, to some extent parse a natural language instruction and reflect it into its sequence modeling process.
Prompt 1:
Prompt 2:
Prompt "Continue the given sequence of digis between O and 9. The comes from Markov process, only depends the last The follows!n"
"Continue the given sequence of digit between and 9, The sequence followstnn
"Continus the given secuance of digits between and The sequence from Markov protaes. sequence follows/y"
6.6
52
0.2
0.0
100
200
200
400
0.0
100
2000
330
400
0.0
100
2003
3:0
400
Context
Context Size
Context
Uni
Bilnf
3.770
Ulemae3311 1-40BB
Figure 38: In-context learning Markov chains Llama-3.1. We input sequences generated from the DGP in App. A.1 into LLama-3.1 8B, 70B and 405B and measure the KL divergence on the next state probability between the model predictions and the ground truth transition matrix. Each state is tokenized into a single token, from "0" to "9". The tokens are separated by the "." token to avoid the tokenizer merging states together. The output space was constrained to the state tokens. (left) Prompt 1, not explicitly stating the Markovian nature of the sequence. (center) Prompt 2, stating the Markovian nature of the sequence. (right) Prompt 3, additionally stating that the next state probability will only depend on the last state.
An interesting future direction would be to reverse engineer what algorithmic solutions are imple- mented by these models to generate the next state, e.g. by decomposing the logit outputs as in Sec. 4.
49

---

Published as a conference paper at ICLR 2025
1 FURTHER VALIDATION OF LIA
1.1 DOES LIA FIT THE MODEL WELL?
Fig. 6 and Fig. 7 showed that the linear interpolation of algorithms from Sec. 3 (i.e., LIA) achieves similar performance the trained model: the empirical transition matrix identified from either systems yields similar ID KL, and in fact LIA predicts the trained model's ' OOD performance fairly accurately. Here, show that in fact both the trained model and LIA produce similar predictions by comparing them to each other.
LIA L2 Residual
0.005
2
1
Training Chains
0.004
29
28
0.003
27
2
26
2
0.002
2a
2
23
0.001
2
0.000
49
175
613
2148 7525 8635792318 Steps
Figure 39: Residual L.2 of LIA fit. We show the residual probability space L2 (the argument of arg min in Eq. 7) for the LIA fit shown in Fig. 6. Note the color-scale, which is much smaller than the order of magnitude of probability vectors, which is unity.
a)
KL ( Model II LIA)
b)
KL ( [II Model)
24
211
210
0.5
210
0.5
chains
29
0.4
2
0.4
2a
2
0.3
27
0.3
29
24
28
0.2
25
0.2
24
2
0.1
23
0.1
2
2²
0.0
0.0
Steps
Steps
Figure 40: KL divergence between the model and LIA fit. (Left) KL divergence between model predictions and LIA across data diversity and optimization. (Right) KL divergence between LIA and model predictions across data diversity and optimization.
L2 distance between model and LIA predictions. The L2 Euclidean distance between the trained model and LIA predictions defines the optimization problem used to define weights in LIA (see the argument arg min in Eq. 7). To demonstrate LIA identifies an interpolation of algo- rithms that in fact does minimize this distance, we report the residual (i.c., excess error) from this optimization problem. Results are shown in Fig. 39 across different settings of data diversity and optimization. We clearly see that the residual is consistently low across all on the order of 10-3 Note that since the target of this optimization problem is a probability vector (i.e., its elements sum to 1), this low order of an error clearly demonstrates LIA solves the problem almost perfectly in most settings. Moreover, we note that the landscape of this residual error is quite intriguing: the slightly high error (which is still very low in absolute sense: around 0.005) occurs at the phase boundaries! This suggest that the models very slightly deviate from a linear combination during transitions, but the nonlinear effects relatively ignorable.
50

---

Published as a conference paper at ICLR 2025
KL between model and LIA predictions. We also show the KL divergence of the model predic- tions to the ones predicted by LIA (and vice-versa) in Fig. 40. While Fig. 6 is already suggestive that LIA fits the model'ss predictions accurately, these KL divergence plots give yet another quantitative validation of the results alongside our 1.2 Euclidean distance plots in Fig. 39. In particular, we again find the KI. is very low in regions we ascribed to precise phases in our analysis in Sec. 3; meanwhile, the phase boundaries have some (very minimal) deviation from linearity.
1.2 ROBUSTNESS OF LIA TO ARBITRARY ALGORITHMS
Does LIA give rises phases even when the solutions are arbitrary? Sec. 4.1, we used Linear Interpolation of Algorithms (LIA) to demonstrate that we can decompose the model's next token probability into a linear combination of the probability predicted from the four algorithms. Here conduct two simple experiments assess the robustness of these findings. In Fig. 41 perform LIA for the same model used in Fig. 6 (a), but with 4 arbitrary solutions, described in the figure caption. We do not see the algorithmic phases seen in Fig. (a) and each solution's 's weight remains largely constant throughout model training.
(b)
(d)
1.0
1.
M
Sapa
10 07 SUD DO01UIT
Stea
20838
02 2000
Figure 41: Applying LIA with 4 arbitrary solutions LIA is optimized with 4 arbitrarily chosen solutions (a) weight for the first solution, which outputs next state probability using frozen transition matrix drawn from the Dirichlet prior. (b) weight for the second solution, which outputs next state probability using frozen stationary distribution drawn from the Dirichlet distribution. (c) weight for the third solution, which outputs a 0.2 probability for even states and 0.0 probability for odd states. (d) weight for the fourth solution which outputs 1.0 probability for state 0 and 0.0 otherwise.
Are the same algorithmic phases extracted from LIA when arbitrary solutions are mixed with algorithmic solutions? In Fig. 42, we combine the 4 arbitrary solution with the 4 solutions de- scribed in the main text. We find that the 4 algorithmic solutions indeed show high weight in the same way as in Fig. 6 (a). The arbitrary solutions get assigned a near zero weight everywhere. These experiments in Fig. 41 and Fig. 42 confirms that LIA extract meaningful phases only when the solutions are indeed relevant to the task and the model.
(a)
(b)
(c)
(d)
1.2
10
10
6.1
8R
08
06
0.6
56
0A
02
Srece
Strpe
433
SINCE
3E SUSTETT
(e)
(f)
(g)
(h)
1.3
1.0
10
08
08
06
06
AA
100 300 2012
Stppe
2011
432 32
Supts
Figure 42: Applying LIA with the 4 algorithmic solutions and arbitrary solutions (a) weight for Uni-Ret. (b) weight for Bi Bi-Ret. (c) weight for Uni-Inf. (d) weight for h) weights corresponding to, respectively, solutions (a, b. c, d) in Fig. 41.
(c. f, g.
51

---

Published as a conference paper at ICLR 2025
J IMPORTANCE OF SEQUENCE-SPAGE STRUCTURE TO STUDY TRANSFORMERS
In this work, we focused sequence modeling task consisting of mixture of Markov chains. We argue that there are unique properties of sequence modeling which makes phenomena qualitatively different. Sequence modeling tasks involve the integration of information embedded in individual tokens and their positions. In order to compose this information, a sequence-space computational structure should be learned. This is not the case for many synthetic tasks used to study transformers.
More specifically, many ICL studies focus on Linear regression (Garg et al., 2023; Akyürek et al., 2023: Li et al., 2023c: Von Oswald et al., 2023; Mahankali al., 2023; Raventós et al., 2023; Li et al., 2023b; Lu et al., 2024; Lin & Lee, 2024), where exemplars are presented in pairs as (#4, y:). Following (Garg et al., 2023), many works do not use a tokenized representation. Thus, the only spatial computational structure needed to be implemented is fixed template which recognizes pairs of (zi, 3/) from the context. Furthermore, a recent paper (Tong & Pehlevan, 2024) showed that multi layer perceptrons (MLPs) can learn linear regression and classification tasks in-context, sometimes competitively to transformers.
Motivated by lack of language structure in synthetic studies of ICL, some recent studies have begun analyzing transformers trained on probabilistic formal languages (Edelman et al., 2024; Akyürek al., 2024). In such a setting, Edelman et al. (2024) found statistical induction heads which is probabilistic variant of a copying induction head (Elhage et al., 2021; Olsson et al., 2022). Akyürek al. (2024) study in-context learning of deterministic finite automata (DFA), and find n-gram heads which perform copying similarly to induction heads but based on n-grams. These studies showed that studying ICL on formal languages helps develop rich training dynamics (Edelman et al., 2024) and a complex relation to model architectures (Akyürek et al., 2024). It is also the case that, to the best of our knowledge, there does not exist a study equivalent to Tong & Pehlevan (2024) for linear regression but applied to formal languages. We suspect MLPs will struggle to learn formal languages requiring dynamic spatial computational structure.
The unigram solutions vs bigram solutions discussed in our work highlights that even the simplest form of spatial computational structure, counting states vs. counting pairs (transitions), introducing a new axis of analysis: the circuit complexity of solutions. In our work, the bigram solutions, Bi Ret and Bi Bi-Inf, arguably need a more complex circuit structure. The attention maps visualized in Fig. 18 and Fig. 19 support this argument, though there is substantial work to be done to confinm this intuition (e.g.. by properly defining circuit complexity). Nevertheless, well aligned to this intuition, both bigram solutions always follow after unigram solution in our experiments.
In Sec. 4.2 and Sec. 4.3, we demonstrated how a varying circuit complexity can result in significantly different learning time for different algorithms. We have also demonstrated that different learning speeds can cause an algorithm to be hidden or suppressed (Fig. 8 (a,c)). Additionally, we have demonstrated that change of tokenization, which does not change the task but only alters how the task is presented to the model, can remove solution from emerging by closing the circuit complexity gap.
Overall, we believe that studying in-context learning with setups requiring non-trivial sequence- space computation, e.g., formal languages, will be crucial to advance our understanding of ICL. in LLMs at scale.
52

---

Published as a conference paper at ICLR 2025
K DISCUSSION AND FUTURE DIRECTIONS
Distributional Adaptation An interesting phenomenon observed in Sec. 4.1, Fig. 6 is that the predicted OOD KL is always slightly higher (worse) than the model's actual performance. This signifies that our algorithmic decomposition does not explain the model's behavior perfectly, and the model likely applying a combination of solutions slightly better fit for sequences it has not observed. A possible future direction would be to understand how such behavior is possible. We lay down hypothesis: Bi-Ret emerges on top of the Bi-Inf solution, but there is a circuit triggering this solution preferentially for ID sequences.
Parallel or Interacting Circuit Evolution? An interesting question raised by our analysis is whether different algorithms evolve in parallel or not. This question is especially motivated by the extremely stable emergence of the Bi-Inf solution with respect to optimization steps. As seen in Fig. 6, the Bi-Inf solution emerges very stably even for data diversity levels different by 2 One natural question is whether it could emerge with data diversity under 26, but is just not ob- served due Uni tei-Ret and Ret being found first. Another question with slightly different implication is whether the circuit supporting the solution did in fact already emerge, yet is not used.
Thus, an explicit and interesting future direction is try to ablate the Bi-Re solution (via careful design, which we do not know yet) and see if Bi In- can be observed from data diversity level it observed in the current experiment.
Optimization Limited Emergence Data Limited Emergence We find many algorithmic tran- sitions in our study. The formation of an induction head (Fig. (b)) and the rise of Bi-Ret (Sec. 4.1) two of them. Here, argue that these transitions carefully looks at Fig. 6, one can notice (as discussed in the paragraph above) that the emergence of B is largely independent of data diversity. We thus suggest this emergence is only limited by optimization. However, the emergence Bi Bi-Ret is limited by data diversity (usually limited means that a higher data diversity is needed, however for Bi-Ret. lower data diversity makes easier to emerge). We thus propose classification of emergence of mechanisms into two classes: one driven by the introduction of sufficient compute and another driven by sufficient data diversity.
different in nature. If one
L CODE AVAILABILITY
All code used run the experiments and analysis are available http://sshhaaaamm////uoooottttnn
53


Reviews:
[{"review_id": "YR6ebTGH4X", "reviewer": "Reviewer_vTGM", "summary": "This paper introduces a new synthetic task, namely finite Markov mixtures, to study the properties of in-context learning (ICL) in Transformers. The authors present several analyses on top of finite Markov mixtures. First they show that this task alone can effectively recover known phenomena which were originally discovered on several different tasks like linear regression, classification, and finite automata. Then they contribute new insights, and argue that ICL is best thought of as a convex combination of several learning algorithms which emerge or vanish during training.\n\nOverall I found this work a well-written and interesting read, with several novel observations which are very relevant to the ICLR community. In particular, I appreciated the insight that ICL is best thought of as a mixture of learning algorithms, and that these algorithms are transient throughout training. It’s main weakness is that It lacks a clear takeaway message for readers to act upon — see my questions below.", "questions": "See my questions in the weaknesses section above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- **Well-written**. This expository work is well written and enjoyable to read. The authors do a good job at holding the reader by the hand through their analyses and provide adequate context even for non-ICL experts. The figure are easily understandable (mostly, see below for a nit) and the flow of the paper makes sense.\n- **Sound, novel, and unifying benchmark.** The benchmark is novel in the context of ICL studies and it is soundly derived (eg, using the expected KL as quality measure in Eq. 1). Some of the choices are arguable (eg, why Dirichlet?) but that’s splitting hair. What’s more interesting is that it reproduces known phenomena from the literature while also uncovering novel insights.\n- **Strong analysis revealing new insights**. The insight that ICL can be decomposed into several algorithms *at any point in training* is novel and deserves further thinking. Some may argue that the transient nature of ICL was known (the authors say so themselves) but this work goes one step further, showing the algorithms are not forgotten but rather superposed with different weighting coefficients (Fig. 6.b).", "weaknesses": "- **Lack of actionable takeaway message**. Because the benchmark is synthetic, it’s unclear how much it says about ICL for real-world LLMs. This is the main flaw of the paper. For example, l.81: it’s good to know that Transformers can learn different algorithms — but which is it for LLMs / VLMs? Certainly not the unigram or bigram of l. 301, right? Similarly, I liked the flavor of paragraph on l. 301 but it’s unclear how to replicate this study on real-world LLMs. This limits the insights into how real-world ICL really works, and so we’re left with the question: what do we do with the discovery that ICL is best thought of as a mixture of algorithms? This work doesn’t say which are the algorithms for real-world ICL, so we can’t, e.g., prescribe which algorithm to surface and when.\n- **The Bayesian vs non-Bayesian discussion is unclear**. On l. 226 the authors argue that ICL first has a Bayesian and then a non-Bayesian behavior (they intentionally don’t use the term frequentist), and that the Bayesian overfits to the training Markov mixtures. I think this distinction could be explained better. For example, one could make the argument that ICL is always Bayesian — otherwise what is transferred? — but the prior weakens as the model sees more diverse chains. In fact, the experiments support this line of thought: Fig. 5.b shows that as we increase the number of training chains, the prior weakens. In fact, I think believe this weakening of the prior is a property of how the Markov mixtures are constructed, and we would see a different behavior if the test chains where chosen differently. Note that this point  doesn’t take away from the superposition analysis but it needs clearer explanations.\n- **Minor presentation issues**. The paragraph on l. 341 is not detailed enough, and doesn’t explain what the Fig. 5 shows. It also doesn’t help that Fig. 5 doesn’t have clear legend on the heat map scales — is darker more Bayesian or less Bayesian for 5.b? Finally, some parameter choices in the analysis are weird: l. 187, why plot at train step 839 specifically? l. 192, why at n = 2^7? Can we have similar figures for later training steps and for larger n’s in the Appendix?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zjpemnyYtf", "reviewer": "Reviewer_Pv6r", "summary": "This paper investigates the mechanisms of ICL under a unified framework. The authors developed a synthetic sequence modeling task using finite mixtures of MCs and studied various phenomena in this setting, including the task retrieval vs. learning dichotomy and emergence of induction heads. They were able to simultaneously reproduce most of these well-known results. Additionally, the authors proposed that ICL is best understood as a combination of different algorithms rather than a single capability -- model configurations and data diversity impact transitions between these algorithms. This shows that ICL behavior can shift based on training data properties.", "questions": "The Bayesian vs. Non-Bayesian comparison: Generally, I think of Bayesian learning as a form of \"learning to learn,\" where a posterior is updated based on observed data according to Bayes' rule, with a prior typically established during pre-training. Therefore, it is unclear why the comparison between ID and OOD performance specifically reflects a shift between Bayesian and non-Bayesian paradigms. In particular, the analogy between \"task-retrieval\" vs. \"task-learning\" and Bayesian vs. non-Bayesian, in my view, does not fully capture the essence of Bayesian inference.\n\nIn a Bayesian approach, one would ideally follow Bayes' rule to update an implicit or explicit posterior or posterior predictive distribution. Given this, shouldn’t the KL divergence be examined between the model prediction and the true posterior or posterior predictive distribution (according to Bayes' rule and the correct prior) at each context length (so given the same context of length $l$, examine at each step from $1,\\dots, l$)?\n\nI understand that you may be viewing task-retrieval vs. task-learning as a contrast between in-weight learning (IWL) and meta-learning. However, this distinction could also be seen as reflecting a finite, discrete prior versus a continuous or uniform prior. The true Bayesian vs. non-Bayesian distinction, perhaps, is whether the model has learned to correctly update a posterior (i.e., learned Bayes' rule) and has fitted an accurate prior.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Very detailed and sound study of the ICL mechanism: varying task diversity, training steps, context length, and evaluating on various metrics. This is a very empirically rigorous study that verifies previous literature by reproducing various well-known results within a single setting.\n\n2. Some analysis on how model design affects downstream performance on various metrics.", "weaknesses": "My main concern with this paper is its novelty: as the authors have correctly noted, many of the results presented here have already been explored in existing literature. While this paper offers a valuable unifying study that synthesizes and reproduces previous findings in a single framework, the setting itself has also been examined in prior work (e.g., Edelman et al.). Consequently, the overall message lacks new insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mBCpoqUiFh", "reviewer": "Reviewer_tKrP", "summary": "The authors introduce a new ICL synthetic task that consists of sampling from a finite mixture of Markov chains. Their setting reproduces several ICL phenomena, and through extensive analyses, the authors also report results on phase transitions between different algorithms.", "questions": "This paper identifies a number of these interesting phenomena, but it would be nice if the authors could discuss a bit more about why these phase transitions occur. For example in the LCA analysis, why is there rich structure in these phase transitions when you might (naively) expect a smooth increase in the weights on the optimal solution (e.g., Bi-ICL) and roughly uniform weight on the other solutions? Can you study the properties of the loss function (e.g., Hessian) at these different phase transition points?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think this is a nice, comprehensive paper that introduces a simple setting that unifies many recent papers on ICL and captures analogous phenomena (task diversity thresholds, transience of ICL). For example, Figure 3 basically reproduces the results of two previous papers. \n\nThe experimental protocols for assessing bigram utilization and proximity to the Bayesian solution were thoughtful and creative.\n\nI like the idea of approximating the transformer’s behavior as a mixture of algorithms. It’s interesting that this can be used to predict OOD and that it highlights a sort of “persistent competition” between implementing different algorithms. This potentially provides a compelling explanation for phenomena like transience. \n\nThere’s also a comprehensive set of ablations that study the impact of width and data complexity etc…\n\nOverall, the paper was fairly clear.", "weaknesses": "First of all, I want to emphasize that I think this line of work is valuable and scientifically meaningful. However, it would be nice to discuss how these insights translate into practical design choices (e.g., predicting OOD performance using a similar approach to this paper). \n\nI think one major premise of the paper is that there’s a transition between different algorithms. \nI think this is convincing. However, I think I want some kind of control condition where you use 3 or 4 different “silly” algorithms just to confirm that these kinds of phase transitions aren’t some artifact of fitting some linear combination of algorithms and that, if your algorithms are not related to the task, you don’t always see these interesting algorithm phase transitions. \n\nI think I also wanted a bit of better understanding on how well LCA predicts the performance of the transformer relative to some naive baselines just to confirm that LCM well approximate the transformer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xTkpGvPUqb", "reviewer": "Reviewer_medY", "summary": "With this paper the authors contribute the following:\n\n* The authors propose a new sequence modelling setting, namely learning to\n  predict sequences sampled from a Markov chain sampled from a finite mixture\n  of Markov chains.\n  * This is similar to the variable 'task-diversity' in-context linear\n    regression setting from Raventos et al., but using Markov chains rather\n    than a regression model to generate sequences following Edelman et al.\n\n* The authors list four idealised algorithms for solving this sequence\n  modelling setting, along two axes of variation, namely:\n  * observing either unigram statistics (states) or bigram statistics\n    (transitions), and then\n  * making predictions by leveraging knowledge of the latent mixture of\n    Markov chains, or based solely on the observed frequencies in the\n    context.\n\n* The authors devise a pair of tests for distinguishing a learned predictor\n  along these two axes, and in doing so reveal that depending on the degree\n  of task diversity, the sequence length, and the number of training steps,\n  small transformers trained for this task will behaviourally resemble each\n  of these four algorithms. This creates the titular 'algorithmic phases'.\n\n* The authors propose a behavioural analysis method, \"Linear Combination of\n  Algorithms (LCA)\" whereby they decompose a transformer's outputs (given\n  in-distribution inputs) into a mixture of the outputs of the four idealised\n  algorithms. The decomposition is made by projecting the outputs onto the\n  probability simplex spanned by the four algorithms in function space.\n  The authors track this decomposition over training and observe a close\n  alignment between trends in the weight of certain algorithms and trends in\n  out-of-distribution generalisation including the \"transience\" phenomenon.\n\n* This phase isolation methodology and auxiliary metrics replicates a number\n  of phenomena reported in prior works on ICL in similar and disparate\n  settings, and some new phenomena. In the main text, the emphasis is on the\n  following three phenomena:\n  * The authors find a 'task diversity threshold' at which transformers\n    switch from learning to leverage knowledge of the pre-training task\n    distribution to learning to generalises to unseen Markov chains. This\n    finding is analogous to that of Raventos et al. for in-context linear\n    regression.\n  * The authors find that in certain phases transformers develop statistical\n    induction heads, replicating the finding of Edelman et al. in a similar\n    setting based on infinite mixtures of Markov chains, but for finite\n    mixtures of Markov chains.\n  * The authors show that with increased training time individual\n    transformers shift from initially adopting a generalising method to\n    eventually preferring one that leverages information of the training\n    mixture. This is somewhat analogous to the \"transience\" phenomenon\n    reported by Singh et al.\n  * The authors also claim to replicate other phenomena, but I am less\n    familiar with these other phenomena and the details are excluded from the\n    main text, so I have not been able to evaluate them.\n\n* The authors argue that their finite mixture of Markov chains setting\n  offers a unified setting in which to study the emergence of in-context\n  learning, which has previously been studied in disparate settings.\n\n**Summary of my review:**\nI was impelled to write a long review. So, I also include a summary of my\nreview here.\n\n* I think the authors have made a strong contribution in an important area of\n  the science of deep learning. Their setting is elegant, expressive, and\n  permits an interesting variety of idealised solutions. The results from\n  their phase isolation and LCA analyses are interesting and informative.\n\n* However, I think the claims made in the paper at times overstate the\n  results or are overly confident given the limitations of the methodology,\n  which are not adequately discussed. In particular:\n  * The phase isolation methodology is incapable of ruling out plausible\n    alternative algorithms undermining the authors' claims that they have\n    knowledge of what algorithms the transformer is implementing.\n  * The \"linear combination of algorithms\" methodology, while revealing\n    interesting behavioural dynamics, does not seem to me to be worthy of\n    being called \"mechanistic\" nor an \"explanation\" of the transience of\n    particular algorithms or other phenomena.\n  * The motivation for proposing a new setting is to unify disparate studies\n    on the emergence of ICL, however the proposed setting is not uniquely more\n    appropriate for this purpose than alternative settings.\n\n* I believe that the framing is sufficiently misleading that I cannot\n  recommend the paper for acceptance in its current state. However, if the\n  authors are able to back up their confidence or if they commit to tempering\n  their claims then I would be happy to recommend the paper for acceptance\n  because I didn't note any major technical flaws and I think the work is\n  important and interesting.\n\n* In addition, I note a number of additional questions and more minor\n  concerns including about the naming of the \"-ICL\" algorithms and some\n  details of the setting and results, detailed in the questions section of\n  this review.\n\nI look forward to the discussion period.\n\n**EDIT TO ADD:** Summary of discussion:\n\n* The authors addressed all of my concerns about the paper's framing.\n  * The authors no longer claim that the phase isolation methodology rules out alternative similar algorithms or identifies the precise mechanisms of the learned transformer implements.\n  * The authors talk more precisely about the LCA (now: LIA) methodology as revealing only behavioural dynamics.\n  * The authors now motivate their work in more moderate terms.\n* In addition, the authors added new preliminary mechanistic experiments providing further interesting insight into learning dynamics in their rich setting.\n* I believe that the framing is now acceptably accurate. Therefore because of the paper's strengths I am pleased to raise my rating from 5 to 10.", "questions": "I collect various questions, minor concerns, or suggestions that occurred to\nme while reading the paper. Given the length of my review I don't expect the\nauthors to respond to all of these questions (though I would be happy for\nthem to do so). If the authors are interested in me revising my decision and\nhave limited capacity in the discussion period I would recommend that they\nengage with me on the three weaknesses before the contents of this section.\nMore importantly I hope that they might consider my questions and suggestions\nand consider revising the paper to improve the presentation as they find most\nappropriate.\n\n**Q1. The four algorithms have unclear and misleading names.**\nAs I said, I am a believer in the importance of names. I felt strongly that\nthe choice to use '-ICL' as a suffix in the names of 'Uni-ICL' and 'Bi-ICL'\nis a mistake that undermines the quality of the paper. By selecting these\nnames the authors have at the same time created the following two problems.\n\n1. They have conflated one half of their list of algorithms with the concept\n   of in-context learning, entrenching a false connotation that these two\n   algorithms are more exemplary instances of ICL algorithms than others, in\n   fact that the Bayesian solutions are not classified as ICL.\n   This contradicts the authors' stated message in the abstract and\n   conclusion, that ICL is an umbrella concept that encompasses multiple\n   concrete algorithmic instantiations. Recalling again the paper's title,\n   all four phases are supposedly 'of in-context learning'.\n   I do not think that the authors mean to hold up Uni-ICL and Bi-ICL as\n   'truer' examples of ICL than the 'Bayesian' algorithms, yet this is what\n   their naming choice achieves.\n\n2. They have missed an opportunity to communicate what is unique about these\n   particular ICL algorithms. This is the role played by 'Bayes' in the names\n   'Uni-Bayes' and 'Bi-Bayes' (in my reading this helpfully conveys that the\n   methods use Bayesian averaging). I leave it to the authors to decide what\n   would be an appropriate analogue of 'Bayes', but I invite them to consider\n   using the term 'frequencies' or 'induction' and I urge them to avoid\n   anchoring on induction *heads* themselves (a feature of transformers\n   rather than ideal algorithms) or using the misleading 'non-Bayesian'\n   terminology of Raventos et al.\n\nI respect the right of the authors to name the algorithms. I can't say this\nconcern alone would prevent me from recommending the paper's acceptance.\nHowever, in this case I feel strongly enough to register my protestation\nabout the names given my fresh perspective on the algorithms and the authors'\nchosen takeaway message.\n\n\n**Q2. Inconsistent summary of algorithms between main text and figure 4\ncaption:** In the figure caption, the Uni-Bayes and Bi-Bayes descriptions\ntalk about selecting a 'closest task' from the mixture. Based on the main\ntext, my understanding is that they do not select a single task but rather\nthey form a posterior distribution over all tasks and use the posterior\npredictive distribution to make their prediction. Using the 'closest\ndistribution' sounds more akin to using a maximum likelihood distribution,\nrather than using the posterior predictive distribution.\n\n**Q3. Questionable choice to use a nonuniform task prior:** If I understand\ncorrectly from the setting description, the authors sample a prior vector\nfrom a uniform Dirichlet distribution over task priors. The resulting prior\nwill be almost certainly non-uniform and with high likelihood for high task\ndiversity it will have a small number of tasks with quite large\nprobabilities and a large number of tasks with very small probabilities. It\nfollows that after a reasonable amount of pre-training there may be some\ntasks that have barely been sampled at all.\n\nThis seems to me to be a significant departure from the use of task diversity\nby of Raventos et al., for whom, if I remember correctly, the task prior is\nalways uniform. I believe that having a skewed task distribution may confound\nexperiments since what I would call the 'effective task diversity', meaning\nroughly the number of tasks the transformer has to 'memorise' in order to get\ngood performance on in-distribution evaluation (assuming tasks are sampled\nfrom the same skewed prior for ID evaluation) will be smaller than the\nspecified task diversity, since the transformer can get away with not\nremembering low-probability tasks.\n\nThe inclusion of this additional complication appears to be unjustified by\nany particular argument in the manuscript. I would be curious if the authors\nhave a strong reason for including this detail. Of course, it is a virtue of\nthe setting that one can consider different distributions of tasks, since\nthis might be an interesting direction for future work, but such work would\nsurely involve *systematically* varying the prior rather than abdicating\ncontrol over the prior by sampling it from a high-dimensional Dirichlet\ndistribution.\n\nFinally I note that it is regrettable that this detail appears to be\ndocumented only in the appendix.\n\n**Q4. Convoluted phase isolation tests:** These test seems very intricate. It\nis not clear to me that they are the clearest ways of isolating phases, and I\nwonder if you have considered and ruled out simpler alternatives.\n\n1. For the bigram utilisation test, it occurs to me that the predictions of a\n   model paying attention exclusively to unigram patterns would not vary much\n   depending on the current state (at least late in the sequence). On the\n   other hand, bigram-based models would vary their prediction based on the\n   state. Therefore, I wonder if you have considered a simpler test of\n   somehow quantifying uniformity in the set of rows of the revealed\n   transition matrix?\n2. For the proximity test, I wasn't able to think of a simpler test, beyond\n   the idea that perhaps something with generalisation performance could be\n   used.\n\n**Q5. Missing details for proximity test:** I was left wondering about some\ndetails of the proximity test. Unless I missed something, I would recommend\nclarifying the following points, if possible in the main text or otherwise by\nexpanding on the 'additional details' in the appendix.\n\n1. How is distance to a set of tasks defined? Is it the distance to the\n   closest member of the set?\n2. Does the measurement of distance to the training task set account for the\n   task prior at all? I am concerned that for example if the closest task in\n   the training set happens to be a task with very low prior probability,\n   then this task will not draw the model's posterior towards that closest\n   task, and the posterior may be more likely to be falsely detected as\n   closer to a random task than if the closest training task happened to be\n   one with higher prior probability.\n3. How is the chain that is not part of the training set or the control set\n   sampled?\n4. I think I can guess how you turn the procedure you outlined into a single\n   number used to colour your phase diagram, perhaps it involves repeating\n   this procedure several times, and estimating an empirical probability of\n   the closest task being from the training set, giving a number between 0\n   and 1. If this is correct, I think it is worth spelling out in the text,\n   as well as noting somewhere how many trials you take. If this is wrong\n   then it's definitely worth spelling out in the text.\n\n**Q6. Missing details about figure colour schemes:** \nThe phase isolation methodology and the LCA analysis are two distinct methods\nfor colouring a point on a phase diagram. I realised that it is not always\nclear which of these methods you are using in each of the diagrams. It is\nclear in Figure 4 and figure 5 where these techniques are explicated. For the\nremaining figures, I am not sure which methodology you use, and I couldn't\nfind it documented anywhere. Please consider clarifying this in each figure's\ncaption.\n\n\n**Q7. Why is LCA formulated in terms of L2 distance for probabilities?** It\nwould seem more natural to minimise cross entropy or KL as is used elsewhere\nin the paper, and this would allow a clearer comparison to other quantities\nsuch as model KL vs. LCA KL and so on. I don't think this is necessarily a\nmajor issue but I just wondered if the authors had a good reason for it.\n\n\n**Q8. What is the relationship between LCA and delta metrics from Raventos et\nal.?** Raventos et al. consider two setting-specific metrics, they denote\nthem 'delta ridge' and 'delta dMMSE', measuring the L2 distance between the\npredictions of their pre-trained transformer and those of their idealised\nlinear regression algorithms (ridge regression and dMMSE). These are\nessentially measures of how close in function space the transformer is to one\nof the algorithms. Have you thought about the relationship between these\nmetrics and LCA?\n\n\n**Q9. How close is the LCA fit?** LCA weights are defined via a least squares\noptimisation problem. In figures 6 and 7 the authors plot the argmin weights.\nWhat is the min? In other words, how large is the irreducible component of\nthe least squares loss representing the distance of the transformer from the\nsimplex spanned by the four algorithms in function space?\n\nIt is important that this metric remains low in order to believe that the LCA\nhas captured something meaningful about the behaviour, rather than a very\nlossy projection of the behaviour. Therefore I believe the authors should\nreport this metric in the paper, if not in the main text then at least in an\nappendix.\n\nA somewhat related metric appears to be the comparison between the LCA KL and\nthe Model KL in figure 6. However, if two models have similar KL from the\nground truth sequence that does not necessarily imply that they have low KL\nbetween them. It would be informative to add the KL between the LCA and the\nmodel to the two lines in these figures. This would play a similar role to\nthe residual.\n\n\n**Q10. Non-ICL algorithms early in training:** Figure 6 shows shifts in the\nmodel's development across training. One lesson from Hoogland et al. (a paper\ncited by the authors in the appendix) is that the choice of algorithms early\nin training might be even more unsophisticated than those that eventually\narise at convergence for a given task diversity and sequence length\nconfiguration.\n\nFor example, early in training, I hypothesise that some of these transformers\nmight behave in a way that is well-described by an algorithm that does not\ninvolve any in-context learning at all. Some particular algorithms that I\nwould consider searching for include the following:\n\n* **Unigram prior:** Learning the average stationary distribution from all\n  tasks and predicting tokens based on this distribution without looking at\n  context.\n* **Bigram prior:** Learning the average transition matrix and predicting\n  based on this without looking at context.\n\nHave the authors considered adding such non-ICL algorithms into the LCA\nanalysis? I would be curious whether doing so reduces the residual at all.\n\n\n**Q11. Questions about evaluation:** Two small questions about the methodology\nfor evaluation.\n\n1. During ID evaluation, what prior do you use for sampling the tasks from\n   the set of tasks? Do you use the training prior or a uniform prior? You\n   just say you 'choose one from a set.'\n2. During evaluation (for both ID evaluation and OOD evaluation), how many\n   tasks do you sample?\n\n**Q12. Sample implementation of data generating process:**\nCould the authors please clarify the relationship between the sample\nimplementation of the data generating process and the actual code used in\nexperiments?\n\nI take the description of the implementation to imply that this is not the\nimplementation used in the experiments. This opens the possibility that it\nmay actually differ in important ways from the actual methodology used in the\nexperiments. There are certain details, such as the fact that the sequences\ndrawn from each chain are initialised with a sample from the stationary\ndistribution of the chain, do not appear to be noted in the\nmanuscript in any form other than in the reference implementation.\n\nIf the authors intend to open source their codebase after the peer review\nprocess as noted in appendix J then I wonder if they intend to keep this\nreference implementation in the paper?\n\nHave the authors considered mentioning any details such as the initialisation\nof sequences in text form as well as in code form?\n\n\n\n**Q13. Paper structure:** On first read I found it slightly difficult to\nfollow the paper's first few sections. There is a lot going on in the paper,\nbetween the problem, the phenomena, the phases, and the explanations.\n\nI personally found understanding the phases helpful to my understanding of\nthe remainder of the paper. I wonder if the authors have considered promoting\nsection 4 to come before section 3? Of course, this is up to the authors.\n\n\n**Q14. Terminology and notation:** A small number of minor notes.\n\n1. Have you thought about whether the 'phases' are indeed phases in the sense\n   of physics?\n2. A bold \"1\" is overloaded as both a vector of ones (when describing the\n   configuration of the Dirichlet distribution) and also an indicator\n   function (line 232). I wonder if the authors have considered for example\n   using blackboard bold for indicators, to avoid any potential confusion,\n   not that I think the risk of confusion is particularly severe.\n\n**Q15. Typos:** (just the ones I happened to notice):\n\n1. Line 186/187: I think there is a stray closing parenthesis.\n2. Line 422: \"more experiments on this sorts\".\n3. Line 870--: The variables in this list look like they should be typeset in\n  math mode.\n4. Line 1638: unfinished sentence.\n5. Line 2024: \"BICL\", is this meant to be Bi-ICL?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "As I said I think this is a strong paper. I note at least the following\nstrengths.\n\n1. The paper is well-motivated by the importance of of understanding the\n   emergence of algorithmic structure inside transformer sequence models,\n   which is a priority for the science of deep learning.\n\n2. To this end the authors contribute a neat setting with a clean and flexible\n   data generating process and an interesting and rich collection of idealised\n   solutions.\n   * This setting can also serve as a solid basis for future work, experimenting\n     in the same setting or extending it to (for example) higher-order,\n     non-Markovian sequence modelling tasks, hidden Markov models, etc., all\n     of which are immediately suggested by the authors' framework.\n\n3. The authors have also conducted a comprehensive study of the numerous axes\n   of variation in this setting.\n   * The replications of phenomena found in prior work is valuable.\n   * The classification of the configuration space into qualitatively distinct\n     behavioural 'phases' is quite striking.\n   * The LCA analysis is thought-provoking.\n \n4. The LCA technique, carefully interpreted, is an elegant idea for\n   behavioural analysis of models in general, when plausible candidate\n   algorithms are known. I like it and I think I would use it (I have noticed\n   several opportunities to use this in my research since seeing it in this\n   paper.)\n\nOverall I think the paper makes a valuable contribution that enriches our\nunderstanding of ICL phenomenology and creates a rich framework for future\nresearch that can continue exploring this important topic.", "weaknesses": "### W1. Insufficient evidence for confidence in algorithmic phase identification\n\nThe authors chose to name their paper 'algorithmic phases of in-context\nlearning'. I am a believer in the importance of names and I think this gives\nme grounds to assume that the authors view their labelled phase diagrams as a\nmajor element of their contribution.\n\nI consider this labelled phase diagram to have two distinct parts. The first\nof which is the division of the hyperparameter space into regions where a\ntrained transformer displays distinct modes of behaviour as quantified by the\nbehavioural classification metrics outlined in section 4.2 'isolating\nalgorithmic phases'. I am impressed by this part of the contribution.\n\nI am concerned about the second part, namely the labelling of phases with\nspecific algorithms. The authors confidently association of each of the four\nbehavioural phases with one of the four algorithms described in section 4.1\n'the Bayesian and non-Bayesian solutions of finite Markov mixtures'. I am\nconcerned that the authors have not secured sufficient ground from which to\nconfidently present these algorithms as uniquely accurate descriptions of the\ntransformer's behaviour in each phase.\n\n**Phase isolation is not exhaustive:**\nThe phase identification methodology appears to assume a priori that these\nare the only plausible algorithms, as if that were the case, then it would be\nsufficient to associate these algorithms to each phase. However, these\nalgorithms do not appear to me to be *uniquely* principled ideal models of\nhow a sequence model might solve the Markovian prediction task, so I do not\nthink it appropriate to rule out *a priori* the many other possible\nalgorithms that could explain similar behavioural patterns and would be a\nbetter 'label' for each phase.\n\nA short list of other algorithms I can think of is as follows:\n\n* **Unigram- or Bigram-likelihood Bayesian Averaging with a different\n  prior:** An algorithm that functions like Uni-Bayes or Bi-Bayes, but uses a\n  different task prior probability vector as a starting point for formulating\n  its posterior predictive distribution.\n\n* **Unigram- or Bigram-likelihood MLE or MAP:** An algorithm that functions\n  like Uni-Bayes or Bi-Bayes in weighing the likelihood of each task for\n  describing the sequence in front of it, but then rather than performing\n  Bayesian averaging to make predictions, simply predicts based on the\n  most likely task (possibly accounting for the task prior).\n\n* **Slight modifications of frequency counting approaches:** An algorithm\n  that functions like Uni-ICL or Bi-ICL but uses slight modifications to\n  frequency counting such as starting the count for each unigram from epsilon\n  instead of zero or similar for bigrams, or increasing the predicted\n  proportions non-linearly in the counts.\n\nThese algorithms are close in function space to the proposed algorithms so\nthat it were the case that these were more accurate descriptions of a\ntransformer's behaviour, this would not show up in the phase isolation\nmetrics (nor in the LCA analysis which is based on projections in function\nspace---the above algorithms would be nearby in function space and so\nprojections would be similar). The only ways to rule out these alternatives,\nalong with every other algorithm, would be to devise specific tests to probe\nthe behavioural differences between these algorithms and the proposed\nalgorithms, or to probe the internal computational structure of the\ntransformers to seek to distinguish the mechanisms underlying their\nbehaviour.\n\n**On appendix E and mechanistic analysis:** I did notice that the authors\nalso include additional experiments in appendix E that investigate the\nactivation patterns in various locations inside the transformer. However,\nthese experiments are insufficient to rule out the alternatives to Bi-Bayes\nand Uni-ICL I have listed above, since for example counting transitions is\nalso consistent with these alternative algorithms. There are no mechanistic\nexperiments into Uni-Bayes. It appears the authors have more evidence\nconsistent with Bi-ICL than the other algorithms including the presence of\nstatistical induction heads, but the broader point stands.\n\n**Overall:**\nTo be clear, I believe that the algorithms proposed by the authors and their\nexperiments are novel and significant. Given the infeasibility of uniquely\nassociating a particular principled algorithm with a phase, it seems fine to\nme to start with approximate behavioural resemblance. I think this is what\nthe authors have grounds to claim they have contributed---a 'fuzzy' label for\neach phase that serves as an initial proxy for what the transformer is going,\nand this is worth sharing with the research community.\n\nHowever, I also strongly believe that the authors have an essential\nresponsibility to clearly articulate the status of their labels. I am\nconcerned that in the current form the reader will draw the as-yet\nunwarranted conclusion that, for example, transformers perform Bayesian model\naveraging (in the appropriate phases). While the algorithmic variations I am\nproposing are also deviations from 'optimality' as the authors have framed\nthe problem, it seems an open question to what extent transformers implement\n'optimal' algorithms and to me, modelling the specific variations from\noptimality in the pre-trained transformer is an important direction for\nfuture work and it is not yet time to declare that the algorithms have been\ndefinitively identified even in this simple setting.\n\n**Requested revisions:**\nI would be welcome the authors to correct my understanding of their\nmethodology and its limitations, or correct my reading of their confidence.\nOtherwise, until this framing issue has been addressed the paper is unfit for\npublication in my judgement. I would suggest that the authors commit to the\nfollowing revisions.\n\n1. The authors should amend their presentation to refrain from claiming that\n   the transformer implements these particular algorithms. Some examples of\n   language I think is unwarranted include (not exhaustive):\n   * Generally in the abstract and introduction any mention of the finding\n     that the transformer uses specific mechanisms such as \"use of unigram\n     vs. bigram context statistics\", though it is unavoidable that some\n     qualifications must be left to subsequent pages and this is not\n     necessarily a sufficient priority in the introduction.\n   * Line 222 \"we ... show ... the model selects between these solutions ...\"\n   * Line 295 \"We now demonstrate the four algorithms proposed above\n     perfectly delineate models trained on our task into explicit phases\".\n   * Line 345 (emphasis in original) \"*Based on these results, we claim our\n     proposed algorithmic solutions successfully explain the different\n     mechanisms employed by the model to solve our finite mixture of Markov\n     chains task.*\"\n   * Generally section 5 continues under the presumption that the transformer\n     \"is implementing\" the algorithms from section 4.\n   * Line 527/528: \"to write down four algorithmic solutions ... and identify\n     their existence in a trained model\".\n\n2. The authors should note prominently and explicitly in the paper (for\n   example when introducing their methodology, in the conclusion, or in a\n   dedicated 'limitations' section) that their methodology is insufficient to\n   rule out other algorithms as being a more accurate description of each\n   phase.\n\n\n\n### W2. LCA is not mechanistic and does not offer a new explanation\n\nThe proposed LCA techniques is described in the abstract, introduction and\nfigure 1 caption as a \"mechanistic analysis\" offering a \"new\" \"causal\nexplanation\" of transient OOD generalisation. The terms \"mechanistic\" and\n\"explanation\" are repeated throughout section 5. I do not see grounds for any\nof the terms \"mechanistic\", \"causal explanation\", or \"new explanation\" to be\nused in describing this methodology.\n\n**On \"mechanistic\":** It is inappropriate to call LCA a mechanistic\ndecomposition. The tool is clearly based on analysing (in-distribution)\nbehaviour, and it does not reliably reveal internal mechanisms (though it may\ndo so, or approximately so, in this case). Accordingly, this analysis should\nbe called \"behavioural\" rather than \"mechanistic\".\n   \nI suppose the authors are using the word \"mechanistic\" because they believe\nthat LCA has identified the algorithm implemented by the transformer, and\nthat this is confirmed by the fact that the in-distribution behavioural\ndecomposition is predictive of out-of-distribution behaviour. It may very\nwell be the case that the transformer implements a coherent mechanism and\nthat LCA has, in this case, identified it (or approximately identified it).\nHowever, LCA is incapable of revealing the mechanistic nature of a general\ntransformer, and so this reasoning is not sound.\n\n1. As I argue in the previous section I do not believe they have grounds for\n   this, and have only roughly categorised the behaviour rather than\n   identified the precise algorithm. LCA will find a decomposition in terms\n   of any list of algorithms given to it. If the true mechanisms inside the\n   transformer are not represented, it will identify the behaviourally\n   closest algorithms as comprising the behaviour.\n\n2. LCA actually makes it clear that the transformer in some sense implements\n   multiple algorithms, not one algorithm, at many points during training,\n   since the mixtures are not concentrated. While the authors call this a\n   'competition' between algorithms, they have not given any mechanistic\n   model of this apparent competition. There are many possible internal\n   mechanisms that would lead to such an apparent 'competition' appearing in\n   the LCA decomposition, some of which would not even correspond to a proper\n   competition but would rather be artefacts of the projection in function\n   space.\n\n3. In this case that the transformer's (lack of) reliance on pre-training\n   task statistics is recoverable from in-distribution behaviour and then\n   this prediction is validated on out of distribution behaviour, this does\n   indicate that the tool happens to have uncovered part of the transformer's\n   mechanism in this case. However, LCA would make the same predictions for a\n   transformer constructed or trained to follow one mechanism in-distribution\n   while following another mechanism out of distribution.\n\nBecause it only measures behaviour, LCA should not be called mechanistic. The\npredictive power in this case is not coming from LCA but rather from the\napparent fact that the transformer happens to have roughly the mechanism the\nauthors expect.\n\n**On \"new explanation\":** The authors also claim that tracking the LCA\ndecomposition over training reveals an explanation of the phenomenon of the\ntransience of out-of-distribution generalisation posed by Singh et al. This\nexplanation is described in the abstract as a \"new insight\".\n\nAs far as I can tell (the authors can correct me here if I have missed\nsomething), by \"explanation\", the authors refer to their observation that\nthe shift in generalisation coincides with a shift in the transformer's\nalgorithm from predominantly resembling Bi-ICL to gradually increasingly\nresembling Bi-Bayes later in training. The authors also observe that Bi-Bayes\nis a better solution according to the training distribution, so this shift is\nin turn explained by the learning algorithm pursuing better on-distribution\nperformance.\n\nI think there are a number of problems with the framing of these observations\nas a new explanation of Singh et al.'s transience derived from LCA.\n\n1. First, it is not clear to me that the observations go beyond what was\n   already reached in Singh et al.'s original paper. In that paper, they\n   already talk about one algorithm, ICL, being replaced with a different\n   algorithm, \"in weight learning\" (IWL) with worse generalisation\n   performance. The authors of the present paper are pointing to a similar\n   trend arising in their replication, but they now have slightly more\n   specific models of the algorithms.\n\n2. Second, note that actually there is an important difference between this\n   setting and that of Singh et al.'s transience. Namely, in Singh et al.,\n   the ICL and IWL algorithms by construction are equally performant on the\n   training distribution. This is a crucial difference in this case. As the\n   authors note, in this case, Bi-ICL giving way to Bi-Bayes is even less\n   mysterious than ICL giving way to IWL in Singh et al., beacause this is\n   driven by the in-distribution performance.\n\n   A closer analogy to the setting proposed in the present paper comes from\n   related work on in-context linear regression. Hoogland et al. (cited by\n   the authors) and (slightly earlier and in more detail under the name of\n   \"forgetting\") in the paper by Panwar et al. \"In-context learning through\n   the Bayesian prism\" (from 2023, on arXiv before Singh et al. was published\n   actually). These works observe that in the Raventos et al. setting, a\n   generalising algorithm gives way in favour of a training-task-dependent\n   algorithm, driven by improved in-distribution performance and with a\n   concomitant drop in out-of-distribution generalisation performance.\n\n3. Third, given this prior work, upon reading the abstract I was expecting\n   perhaps some deeper explanation for what actually drives this phenomenon.\n   For example, some insight into why the transition occurs at a given period\n   during training or at a given rate, or why the generalising performance\n   was preferred in the first place. I could not find any such deeper result\n   in this paper.\n\n4. Finally, I do not see a connection between LCA specifically and this\n   explanation. The transition from Bi-ICL to Bi-Bayes would also show up as\n   a shift in the proximity to Bayesian solution metric from the phase\n   isolation methodology in section 4. I see no reason to attribute this\n   explanation to LCA.\n\nI certainly believe LCA offers a particularly crisp behavioural perspective\non this transition. But given all this, I think a more appropriate framing\nfor the authors' contribution would be to say that in addition to replicating\nthe transience phenomenon, the authors have used LCA to offer a new and\ndetailed perspective on the (behavioural) competition between algorithms\nalready thought to underlie the phenomenon of transient generalisation.\n\n**On \"causal explanation\":** As far as I can tell, \"causal\" is only mentioned\nin the introduction. I don't see any grounds for its inclusion here at all. I\nsuggest it should be removed.\n\n**Overall:** I believe LCA is an interesting and useful behavioural\ntechnique, but unless the authors can persuade me otherwise I am strongly\nopposed to the framing in the introduction and throughout section 5 that the\ntechnique is capable of offering mechanistic insights or that it has offered\na new explanation of the phenomenon of transient generalisation in in-context\nlearning.\n\n\n### W3. The motivation in terms of unifying and generalising phenomena is inaccurate\n\nUpon first reading the abstract and introduction I understood this paper to\nbe claiming that there is a need for:\n\n1. an assessment of whether existing phenomenology are specific to the\n   settings in which they were first found or whether they generalise to\n   other settings and are thus more likely to be inherent features of ICL,\n   and \n2. a unified setting in which the various phenomena of ICL that have been\n   studied in prior work can all be studied in one place.\n\nThe authors don't seem to be positioning this as a motivating vision toward\nwhich they are contributing a 'first step' or something 'in this direction'.\nRather, they say for example in the abstract that their work \"enables a\nunified framework for studying\" ICL. In the introduction they claim that\nfindings from prior work may be \"disparate findings that manifest in specific\nscenarios\".\n\nI think this motivating story is not an accurate description of the state of\nthe field and I think the degree of unification achieved in the paper is\nstrong but not as strong as the authors claim on this first page.\n\n**On generalisation:** It appears to me that the authors have indeed provided\na novel contribution by 'generalising' several prior phenomena by exhibiting\nthem in a new setting. This is indeed a valuable contribution. However, it\nappears that most of these phenomena have already been exhibited in multiple\nsettings, so it is inaccurate to claim that the phenomena were previously\nonly known to hold in isolated settings.\n\n* In the case of the task diversity threshold, the authors have generalised\n  this to the Markovian sequence modelling setting. Previously, it was shown\n  for in-context linear regression (Raventos et al.), along with image\n  classification (Kirsch et al.) as cited by the authors. The same phenomenon\n  has recently been shown in a multi-task modular addition setting by He at\n  al. in a recent preprint \"Learning to Grok: Emergence of in-context\n  learning and skill composition in modular arithmetic tasks\".\n\n* In the case of the emergence of statistical induction heads, there is only\n  a very minor generalisation taking place since statistical induction heads\n  were already shown by Edelman et al. to arise in Markovian sequence\n  modelling with infinite mixtures of Markov chains. The generalisation to\n  finite mixtures of Markov chains is, in my opinion, valuable but not very\n  surprising especially given that the original exhibition of induction heads\n  by Elhage et al. and Olsson et al. was in the completely distinct setting\n  of language modelling.\n\n  Moreover, I am not aware of induction heads being found in other settings\n  such as in-context linear regression. If any ICL phenomenon is isolated to\n  certain settings, this suggests that induction heads represent such a\n  phenomenon.\n\n* In the case of transience, it's true that Singh et al. study a specific\n  scenario that is designed specifically to isolate this phenomenon, but it's\n  not true that their findings have not been replicated in other settings.\n  In the previous section I already noted work noting transient\n  generalisation for in-context linear regression including Hoogland et al.\n  (already cited by the authors) and the earlier work by Panwar et al.\n  Beyond in-context linear regression, He et al. \"Learning to grok\"\n  (mentioned above) have also demonstrated transience in in-context modular\n  arithmetic.\n\n  These examples actually seem more relevant to the present work than Singh\n  et al., as they concern transitions between two different ICL algorithms,\n  rather than between ICL and pure memorisation as in Singh et al.\n\n* (I have not evaluated the novelty of generalising the other phenomena, as I\n  am less familiar with these parts of the literature, and moreover the above\n  three phenomena are the ones the authors discuss in the main text.)\n\nOnce again, I believe the authors have made a strong contribution, but my\nconcern is that they have not accurately described it in their abstract and\nintroduction, and they need to reframe their contribution in a more accurate\nmanner in my opinion.\n\n**On unification:** Moreover, I did not find the motivation in terms of\nunification compelling.\n\nTo me it seems like the extent of a 'unification' achieved by the authors is\nthat they have combined multiple interesting axes of experimental variation\n(e.g. studying models at varying task diversity and training time) previously\nvaried individually in prior work. They have created one setting rich enough\nto include these axes of variation, and they have demonstrated that along\neach of these axes previously studied phenomena are replicated in their\nexperiments. I will repeat that I find this comprehensive investigation of\nthe axes and their combinations is a strong contribution.\n\nHowever, in describing this contribution, 'unification' seems too strong of a\nword. When I read the word unification, I think the prior settings should be\nrecoverable as special cases of a more general setting. Operationally, the\nfield should be able to continue forward by discarding previous settings in\nfavour of using a truly 'unified' setting. I think this standard has not been\nmet by the proposed setting. Rather, if the field universally adopted the\nproposed setting, at least the following research directions would be\nprecluded.\n\n1. Different settings encourage different mechanistic solutions in the\n   transformer's internals. For example, while the Markovian setting allows\n   one to study statistical induction heads, one does not have the ability to\n   study the particular mechanisms that emerge in order to perform in-context\n   linear regression or modular arithmetic. For the field to make progress on\n   mechanistic analysis of in-context learning in transformers, it seems\n   useful to be able to take advantage of the various constructions that have\n   been proposed for specific implementations of in-context linear\n   regression, for example. I don't see why we shouldn't try to keep our\n   range of interesting synthetic settings as broad as possible.\n\n2. Another example comes from the quite specialised setting studied by Singh\n   et al., where, by construction, ICL and IWL are equally performant on the\n   training distribution. Nevertheless, there is still an algorithmic\n   transition between these algorithms at some point in training. This gives\n   rise to questions that can't be asked or answered in a setting where the\n   main four algorithms achieve quite different performance in-distribution,\n   such as what drives the transition even in this case (when the need for\n   better in-distribution performance is ruled out as an explanation for\n   driving this transition).\n\nThe authors have included appendix G with some discussion on the perceived\nbenefits of studying Markovian sequence modelling tasks rather than modular\narithmetic or linear regression due to the lack of \"sequence space structure\"\nin these alternative settings.\nI must admit unfortunately I did not follow the discussion despite trying to\nsee their point of view. It is not immediately clear to me what sequence\nspace structure means. But if the authors refer to the fact that in Markovian\nsequence modelling in order to count bigrams the transformer must look at\npairs of tokens, I note that even though modular arithmetic and linear\nregression are usually formulated in-context using an i.i.d. sequence of\ninputs, it is still necessary for example in Raventos et al.'s setting for\nthe transformer to look at pairs of sequence items (one containing the x and\nthe next the corresponding y). It is not clear to me how this is less rich\nthan looking at bigrams.\n\n**Overall:** I can't emphasise enough, I really like the setting and the\ncomprehensive analysis along multiple axes. I am only concerned that the\nintroduction does not provide an accurate motivation for the work, and I\nwould like to respectfully challenge the authors to lay out a stronger case\nfor their contributions in their introduction. Doing so, in my opinion,\nshould not be too hard, because the authors have made some strong\ncontributions on an important topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)