# A Theory of Emergent In-Context Learning as Implicit Structure Induction

arXiv: https://arxiv.org/abs/2303.07971 · HTML: https://mlsanity.com/paper/2303.07971/

## Key facts

- Cited by 86 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 88 references that are in the map.
- First posted on arXiv 14 Mar 2023.

## Builds on (most cited first, 27 of 27)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://mlsanity.com/paper/2202.12837/) (2022)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Designing and Interpreting Probes with Control Tasks](https://mlsanity.com/paper/1909.03368/) (2019)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Larger language models do in-context learning differently](https://mlsanity.com/paper/2303.03846/) (2023)
- [Data Distributional Properties Drive Emergent In-Context Learning in Transformers](https://mlsanity.com/paper/2205.05055/) (2022)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Can language models learn from explanations in context?](https://mlsanity.com/paper/2204.02329/) (2022)
- [Information-Theoretic Probing with Minimum Description Length](https://mlsanity.com/paper/2003.12298/) (2020)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Demystifying Prompts in Language Models via Perplexity Estimation](https://mlsanity.com/paper/2212.04037/) (2022)
- [Large Language Models Are Latent Variable Models: Explaining and Finding Good Demonstrations for In-Context Learning](https://mlsanity.com/paper/2301.11916/) (2023)
- [A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operations](https://mlsanity.com/paper/2302.03025/) (2023)
- [On the Effect of Pretraining Corpora on In-context Learning by a Large-scale Language Model](https://mlsanity.com/paper/2204.13509/) (2022)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Iteratively Prompt Pre-trained Language Models for Chain of Thought](https://mlsanity.com/paper/2203.08383/) (2022)
- [Visually Grounded Compound PCFGs](https://mlsanity.com/paper/2009.12404/) (2020)
- [Coloring the Blank Slate: Pre-training Imparts a Hierarchical Inductive Bias to Sequence-to-sequence Models](https://mlsanity.com/paper/2203.09397/) (2022)
- [Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars](https://mlsanity.com/paper/2212.09140/) (2022)

## Built on by (most cited first, 30 of 86)

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Function Vectors in Large Language Models](https://mlsanity.com/paper/2310.15213/) (2023)
- [Challenges and Applications of Large Language Models](https://mlsanity.com/paper/2307.10169/) (2023)
- [Visual In-Context Learning for Large Vision-Language Models](https://mlsanity.com/paper/2402.11574/) (2024)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [Are Emergent Abilities in Large Language Models just In-Context Learning?](https://mlsanity.com/paper/2309.01809/) (2023)
- [Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Tasks](https://mlsanity.com/paper/2402.04248/) (2024)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [In-Context Learning through the Bayesian Prism](https://mlsanity.com/paper/2306.04891/) (2023)
- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [Boosting Theory-of-Mind Performance in Large Language Models via Prompting](https://mlsanity.com/paper/2304.11490/) (2023)
- [Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions](https://mlsanity.com/paper/2310.03016/) (2023)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Uncertainty in Natural Language Generation: From Theory to Applications](https://mlsanity.com/paper/2307.15703/) (2023)
- [Is In-Context Learning in Large Language Models Bayesian? A Martingale Perspective](https://mlsanity.com/paper/2406.00793/) (2024)
- [What Makes and Breaks Safety Fine-tuning? A Mechanistic Study](https://mlsanity.com/paper/2407.10264/) (2024)
- [Universal Vulnerabilities in Large Language Models: Backdoor Attacks for In-context Learning](https://mlsanity.com/paper/2401.05949/) (2024)
- [In-Context Learning Learns Label Relationships but Is Not Conventional Learning](https://mlsanity.com/paper/2307.12375/) (2023)
- [A Latent Space Theory for Emergent Abilities in Large Language Models](https://mlsanity.com/paper/2304.09960/) (2023)
- [Generalization to New Sequential Decision Making Tasks with In-Context Learning](https://mlsanity.com/paper/2312.03801/) (2023)
- [In-Context Learning with Representations: Contextual Generalization of Trained Transformers](https://mlsanity.com/paper/2408.10147/) (2024)
- [Temporal Knowledge Graph Forecasting Without Knowledge Using In-Context Learning](https://mlsanity.com/paper/2305.10613/) (2023)
- [Which Examples to Annotate for In-Context Learning? Towards Effective and Efficient Selection](https://mlsanity.com/paper/2310.20046/) (2023)
- [Emergent Abilities in Large Language Models: A Survey](https://mlsanity.com/paper/2503.05788/) (2025)
- [How are Prompts Different in Terms of Sensitivity?](https://mlsanity.com/paper/2311.07230/) (2023)
- [The Mystery of In-Context Learning: A Comprehensive Survey on Interpretation and Analysis](https://mlsanity.com/paper/2311.00237/) (2023)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Understanding In-Context Learning from Repetitions](https://mlsanity.com/paper/2310.00297/) (2023)
- [Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods](https://mlsanity.com/paper/2408.14511/) (2024)
- [Out-of-distribution generalization via composition: a lens through induction heads in Transformers](https://mlsanity.com/paper/2408.09503/) (2024)

## Abstract (arXiv)

Scaling large language models (LLMs) leads to an emergent capacity to learn in-context from example demonstrations. Despite progress, theoretical understanding of this phenomenon remains limited. We argue that in-context learning relies on recombination of compositional operations found in natural language data. We derive an information-theoretic bound showing how in-context learning abilities arise from generic next-token prediction when the pretraining distribution has sufficient amounts of compositional structure, under linguistically motivated assumptions. A second bound provides a theoretical justification for the empirical success of prompting LLMs to output intermediate steps towards an answer. To validate theoretical predictions, we introduce a controlled setup for inducing in-context learning; unlike previous approaches, it accounts for the compositional nature of language. Trained transformers can perform in-context learning for a range of tasks, in a manner consistent with the theoretical results. Mirroring real-world LLMs in a miniature setup, in-context learning emerges when scaling parameters and data, and models perform better when prompted to output intermediate steps. Probing shows that in-context learning is supported by a representation of the input's compositional structure. Taken together, these results provide a step towards theoretical understanding of emergent behavior in large language models.