Research map / Large language models / Language, safety and interpretability
Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions
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.
Studies in-context learning of Boolean function classes by training sequence models from scratch (Transformers, LSTM, DSS, Hyena, RetNet), teaching-sequence prompts, and direct/frozen evaluation of GPT-2, GPT-4, GPT-3.5-Turbo and LLaMA-2-70B against nearest-neighbor baselines.
Problem
Understanding the limits of Transformers' in-context learning of algorithms, whether attention is necessary, whether models exploit teaching sequences, and whether pretrained LLMs implement learning algorithms in-context on discrete (Boolean) tasks.
Approach
Extends the meta-learning in-context framework to Boolean function classes with known learnability, where discrete inputs let pretrained LLMs be evaluated directly; shows attention-free models match Transformers on most tasks, Transformers can learn two algorithms for one task and select by prompt, and LLMs compete with nearest neighbor.
Key results
- Transformers reach 100% on Conjunctions and Disjunctions, matching the PAC learner, but stay near chance (~50%) on Parity-(20,3) and Parity-20 with 140 examples.
- Transformers trained on a mixture of teaching-sequence and vanilla prompts achieve near-optimal accuracy on both task variants, implementing two distinct algorithms for Conjunctions.
- In direct evaluation, GPT-4 and other LLMs perform as well as or better than nearest neighbor for dimensions up to 7 on Conjunction and Majority tasks; GPT-4 slightly outperforms NN even at n=15.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a Transformer rather than chance-level prediction | Parity and Sparse Parity in-context learning · Parity-20 | accuracy: 50.6 | No clear effect |
| Use a Transformer rather than gradient-trained FFN | Parity-(10, 2) · Parity-(10, 2) | accuracy: 100.0 -> 53.7 | Hurt |
| Provide a teaching sequence | Transformer in-context learning · Teach Conjunctions, Teach Disjunctions, Teach CNFs, Teach DNFs, and Teach Sparse Parities | accuracy | Helped |
| Train on teaching-sequence examples instead of the vanilla distribution | Transformer on Conjunctions · Conjunctions without teaching sequences | accuracy | Hurt |
| Train on a mixture of teaching-sequence and vanilla examples | Transformer on Conjunctions · Conjunctions and Teach Conjunction | accuracy | Helped |
| Train with 10% of labels flipped | Sequence architectures on Conjunctions and Disjunctions · Conjunctions and Disjunctions | accuracy | No clear effect |
| Evaluate on functions with expected literal count changed from n/3 to 2n/3 | Transformer trained on Conjunctions · Conjunctions with out-of-distribution functions | accuracy | No clear effect |
| Evaluate on functions with extreme literal-distribution shifts | Transformer trained on Conjunctions · Conjunctions with out-of-distribution functions | accuracy | Hurt |
| Train on 0-1 Threshold functions and evaluate on Conjunctions | Transformer · Conjunctions | accuracy | Helped |
| Use attention-free architectures instead of Transformers | In-context Boolean function learning · Most Boolean function tasks | accuracy | No clear effect |
| Use RetNet or DSS instead of Transformer | 0-1 Threshold learning · 0-1 Threshold | accuracy: 85.3 -> 72.9; 85.3 -> 72.4 | Hurt |
| Use Hyena instead of Transformer | Nearest Neighbor task · Nearest Neighbor | accuracy: 100.0 -> 85.5 | Hurt |
Surprising findings
- Frozen pretrained GPT-2 with only input/output layers trained implements nearest neighbor with induction-head-like attention patterns, while a randomly initialized model of the same size does not.
- Transformers trained on 0-1 threshold functions generalize better to Conjunctions than to their in-distribution threshold task.
Limitations
- Parities remain unlearned by all architectures, leaving the difficulty unexplained.
- LLM direct evaluation cannot identify the underlying algorithm; claims are limited to competitiveness with nearest neighbor.
- Experiments restricted to Boolean functions and small dimensions due to prompt-size and combinatorial constraints.
Experimental setup
Datasets: Synthetic Boolean function classes (conjunctions, disjunctions, DNF/CNF, parities, threshold, majority, nearest neighbor Linear regression task from prior work
Benchmarks: Boolean function classes test-bed (conjunctions, disjunctions, sparse disjunctions, 3-CNF, 3-DNF, majority, 0-1 threshol
Metrics: accuracy on last prompt example
Baselines: Null classifier Averaging estimator Nearest neighbors Feedforward network GPT-3.5-Turbo Randomly initialized Transformer
Builds on: Garg et al. in-context learning framework of function classes induction heads
Closest papers by meaning
- How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations (ICLR 2024 · similarity 0.92)
- In-context Learning on Function Classes Unveiled for Transformers (ICML 2024 · similarity 0.92)
- Technical Debt in In-Context Learning: Diminishing Efficiency in Long Context (NeurIPS 2025 · similarity 0.91)
- In-Context Learning through the Bayesian Prism (ICLR 2024 · similarity 0.91)
- Transformers are Minimax Optimal Nonparametric In-Context Learners (NeurIPS 2024 · similarity 0.90)
- The Closeness of In-Context Learning and Weight Shifting for Softmax Regression (NeurIPS 2024 · similarity 0.90)
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.