# A Mechanism for Sample-Efficient In-Context Learning for Sparse Retrieval Tasks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 24 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (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)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Data Distributional Properties Drive Emergent In-Context Learning in Transformers](https://mlsanity.com/paper/2205.05055/) (2022)
- [In-context Reinforcement Learning with Algorithm Distillation](https://mlsanity.com/paper/2210.14215/) (2022)
- [Online Meta-Learning](https://mlsanity.com/paper/1902.08438/) (2019)
- [The Learnability of In-Context Learning](https://mlsanity.com/paper/2303.07895/) (2023)
- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [On the Effect of Pretraining Corpora on In-context Learning by a Large-scale Language Model](https://mlsanity.com/paper/2204.13509/) (2022)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)

## Built on by (most cited first, 17 of 17)

- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Challenges and Applications of Large Language Models](https://mlsanity.com/paper/2307.10169/) (2023)
- [Supervised Pretraining Can Learn In-Context Reinforcement Learning](https://mlsanity.com/paper/2306.14892/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [Linear attention is (maybe) all you need (to understand transformer optimization)](https://mlsanity.com/paper/2310.01082/) (2023)
- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiency](https://mlsanity.com/paper/2309.17382/) (2023)
- [Towards Efficient LLM Grounding for Embodied Multi-Agent Collaboration](https://mlsanity.com/paper/2405.14314/) (2024)
- [Toward Understanding In-context vs. In-weight Learning](https://mlsanity.com/paper/2410.23042/) (2024)
- [In-context Exploration-Exploitation for Reinforcement Learning](https://mlsanity.com/paper/2403.06826/) (2024)
- [One-Layer Transformer Provably Learns One-Nearest Neighbor In Context](https://mlsanity.com/paper/2411.10830/) (2024)
- [How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regression](https://mlsanity.com/paper/2408.04532/) (2024)
- [SymDPO: Boosting In-Context Learning of Large Multimodal Models with Symbol Demonstration Direct Preference Optimization](https://mlsanity.com/paper/2411.11909/) (2024)
- [How Far Can In-Context Alignment Go? Exploring the State of In-Context Alignment](https://mlsanity.com/paper/2406.11474/) (2024)
- [Transformers versus the EM Algorithm in Multi-class Clustering](https://mlsanity.com/paper/2502.06007/) (2025)
- [From Unstructured Data to In-Context Learning: Exploring What Tasks Can Be Learned and When](https://mlsanity.com/paper/2406.00131/) (2024)
- [Optimization-Inspired Few-Shot Adaptation for Large Language Models](https://mlsanity.com/paper/2505.19107/) (2025)

## Abstract (arXiv)

We study the phenomenon of textitin-context learning (ICL) exhibited by large language models, where they can adapt to a new learning task, given a handful of labeled examples, without any explicit parameter optimization. Our goal is to explain how a pre-trained transformer model is able to perform ICL under reasonable assumptions on the pre-training process and the downstream tasks. We posit a mechanism whereby a transformer can achieve the following: (a) receive an i.i.d. sequence of examples which have been converted into a prompt using potentially-ambiguous delimiters, (b) correctly segment the prompt into examples and labels, (c) infer from the data a textitsparse linear regressor hypothesis, and finally (d) apply this hypothesis on the given test example and return a predicted label. We establish that this entire procedure is implementable using the transformer mechanism, and we give sample complexity guarantees for this learning framework. Our empirical findings validate the challenge of segmentation, and we show a correspondence between our posited mechanisms and observed attention maps for step (c).