Research map / Architectures and efficiency / Attention and transformers
Competition Dynamics Shape Algorithmic Phases of In-Context Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a finite mixture of Markov chains sequence task for studying ICL, reproduces known ICL phenomena, and decomposes trained 2-layer Transformers into four competing algorithms (unigram/bigram x retrieval/inference) via linear interpolation.
Problem
ICL studies rely on disparate synthetic setups (linear regression, classification, probabilistic automata), making it unclear which ICL phenomena are general; a unified, sequence-modeling testbed and mechanistic account of ICL are lacking.
Approach
Train small Transformers autoregressively on sequences from a finite mixture of Markov chains, vary data diversity (number of chains), training steps and context size, and explain behavior as a mixture of four algorithms (unigram/bigram retrieval and inference) whose competition yields algorithmic phases and transient ICL.
Key results
- Four algorithms (uniret, biret, uniinf, biinf) explain trained model next-token predictions with near-zero KL via linear interpolation (LIA).
- Increasing data diversity beyond N=2^6 yields an abrupt drop in OOD KL, and at N=2^7 OOD performance degrades after induction-head emergence (transient ICL).
- Widening the embedding dimension 4x raises the data diversity needed for biinf by 16x.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase data diversity past the reported threshold | Transformer on finite Markov mixtures · OOD chains | KL divergence | Helped |
| Increase data diversity | Transformer on finite Markov mixtures · ID chains | KL divergence | Hurt |
| Continue training after the emergence of the bigram inference solution, allowing bigram retrieval to take over | Transformer on finite Markov mixtures · OOD chains, N=2^6 | KL divergence | Hurt |
| Increase model embedding dimension to 256 (ablation) | Transformer on finite Markov mixtures · Algorithmic phase boundary for biinf | Data-diversity threshold: 16$\times$ | Hurt |
| Reduce the state space to k=2 (ablation) | Transformer on finite Markov mixtures · Algorithmic competition | Emergence of biinf | Hurt |
| Encode the last state and transition in each token (ablation) | Transformer on finite Markov mixtures · Algorithmic phases | Unigram retrieval phase presence | Hurt |
| Use learned positional embeddings instead of the baseline positional setup (ablation) | Transformer on finite Markov mixtures · N=2^7, algorithmic phases | Time until biinf and biret emerge | Hurt |
| Use RoPE positional embeddings (ablation) | Transformer on finite Markov mixtures · Algorithmic phases | Emergence of biinf | Hurt |
| Shuffle the context while retaining its stationary distribution (ablation) | Bigram-dependent model solutions · Finite Markov mixtures | KL divergence | Hurt |
| Increase context length when using a retrieval approach | Retrieval algorithms · OOD chains | KL divergence | Hurt |
| Fit LIA weights on ID sequences and use them to predict OOD performance | Linear Interpolation of Algorithms (LIA) · OOD chains | Prediction of OOD performance dynamics | Helped |
| Increase training steps at high data diversity until induction heads emerge | Transformer on finite Markov mixtures · ID and OOD chains, N=2^7 | KL divergence | Helped |
Surprising findings
- Transient ICL arises because a retrieval solution that fits the training set better slowly supersedes the OOD-generalizing inference solution.
- Learned positional embeddings delay the emergence of bigram-inference, while RoPE was used in the main setup.
Limitations
- Small 2-layer Transformers and a synthetic Markov task limit generalization to real LLMs.
- Four algorithms are identified as sufficient explanations for predominant behavior; other algorithms (e.g., unigram posterior variants) contributed little but are not exhaustive.
Experimental setup
Datasets: synthetic finite Markov mixture sequences (k=10 states, length 512)
Benchmarks: ID and OOD KL divergence on synthetic Markov chains
Metrics: KL divergence bigram utilization retrieval proximity LIA fit weights
Baselines: Retrieval algorithms (unigram/bigram) Inference algorithms (unigram/bigram)
Builds on: induction heads Bayesian averaging account of ICL transient ICL nanoGPT RoPE
Closest papers by meaning
- The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains (NeurIPS 2024 · similarity 0.90)
- In-Context Learning Dynamics with Random Binary Sequences (ICLR 2024 · similarity 0.90)
- In-Context Language Learning: Architectures and Algorithms (ICML 2024 · similarity 0.90)
- Beyond Induction Heads: In-Context Meta Learning Induces Multi-Phase Circuit Emergence (ICML 2025 · similarity 0.90)
- In-Context Learning Strategies Emerge Rationally (NeurIPS 2025 · similarity 0.89)
- Strategy Coopetition Explains the Emergence and Transience of In-Context Learning (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.