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

1.1 Setup

• A Compositional Attribute Grammar combines a probabilistic context-free grammar with a yield operation that recursively maps derivation trees to strings.CAGs also support attributes shared across subtrees and operations that repeat subtrees with different attributes.Source: §1.1 · pp. 3, 5
• The analysis assumes regularity conditions on the CAG, including finite expected document length and nonzero generation probability for all strings.These conditions ensure that the idealized predictor makes well-defined next-token predictions on any input.Source: §1.1 · p. 5

1.2 Learnability Bound

• Theorem 1 bounds demonstration-learning errors for functions expressed by derivation trees, with the analysis applying to an idealized information-theoretic predictor.The bound depends on the task’s description length and the generative process’s iteration complexity; smaller values favor a structured explanation of the prompt.Source: §1.2 · pp. 6–7
• When iteration complexity grows sublinearly with prompt length, the idealized predictor’s error on prompts converges to zero.The bound depends on how complex it is for the generative process to repeat an operation across different objects.Source: §1.2 · p. 7
• The theory predicts that naturalistic prompts receive higher probability and support faster ICL convergence, while sufficiently strong predictors can override semantic priors.Prompt likelihood is connected to the cross-entropy incurred in predicting the prompt.Source: §1.2 · pp. 7–8

1.3 Chain-of-Thought Prompting

• For composed functions, chain-of-thought prompting yields separate error bounds for the two steps, each depending on the description of one function.The stated bound is pointwise for one component and on-average for the other; the proof extends to longer composition chains.Source: §1.3 · p. 8
• In the worst case, disjoint component errors can erase the chain-of-thought advantage, while errors that decline after task identification leave overall error governed by the larger component error.The theoretical benefit applies to intermediate steps provided before the answer, not steps supplied afterward as explanations.Source: §1.3 · pp. 8–9

1.4 Comparison to Xie et al. [2022]

• Unlike Xie et al. [2022], who analyze recovery from a fixed HMM hypothesis space, this framework models tasks as open-ended recombinations of training operations.It also covers tasks with varying complexity and structure, including chain-of-thought prompting.Source: §1.4 · p. 9

2.1 Training Datasets

• The training datasets range from prompt-based function examples and finite-state HMM variants to a minimal compositional language with loops, attribute relations, outputs, and conditionals.The compositional documents lack systematic vocabulary, grammar, and function words, compensating with increased within-document repetition.Source: §2.1 · pp. 10–11

2.2 Training Setup

• GPT2-like next-token predictors ranged from 14M to 85M parameters; each data-generating procedure supplied 500M training tokens per world, with models trained for up to 20 epochs.The main setup used |Ω| = 30 and |F| = 10, with additional variations in world size and function count.Source: §2.2 · pp. 11–12

2.3 Test Tasks

• The test suite covers function evaluation, inverse and other propositional tasks, composed functions, and binary relation classification, all evaluated through prompts with uniquely determined answers.Models must infer prompt structure without markup, and tasks vary in formula complexity and number of literals.Source: §2.3 · pp. 12–13

2.4 Results

• Longer prompts help, higher-literal tasks need more examples, increasing |F| makes ICL harder, and increasing |Ω| does not; larger models especially improve high-literal tasks, with accuracy sometimes emerging suddenly after chance-level performance.On propositional tasks, increasing |Ω| to 100 or 300 improved accuracy, and tasks with eight literals were learned at almost perfect accuracy at the same prompt length. Recombining functions never seen together had a small accuracy effect, with significant drops limited to some eight-literal tasks.Source: §2.4 · p. 14
• COMPOSITIONAL training yields near-perfect accuracy on function evaluation and simpler tasks, while HMM5 fails, FVPROMPT generalizes only to function evaluation, and HMMPERDOC supports some propositional tasks.With COMPOSITIONAL data, binary tasks reach above-chance accuracy, but binary tasks and tasks with many literals remain hardest.Source: §2.4 · p. 14, Figure 4 · p. 15
• Chain-of-thought prompting enables difficult function compositions, including unseen function pairs and compositions of three or four functions, whereas direct prompting can fail even for the largest model.Producing an intermediate step before the answer helps even the smallest model; producing it after the answer helps only large models. InstructGPT results on synthetic tasks likewise show chain-of-thought helps composition more than explanation prompting.Source: §2.4 · pp. 18–19
• Ablating loops or variable introduction makes ICL impossible, but ablating conditions has no discernible negative effect; removing valid prompt substrings from training documents leaves evaluation accuracies highly correlated.The heldout-data exclusion affected less than 0.02% of documents.Source: §2.4 · pp. 18–19

2.5 Representation learning supports ICL

• The authors examine the 21M-parameter model’s activations and attention patterns as evidence about whether it induces the compositional structure of documents and prompts.They focus on this model because it has relatively few heads and layers while succeeding on almost all tasks.Source: §2.5 · p. 19
• Across prompts and 300 training documents, lower-layer heads attended to recent tokens while top-layer heads focused on structurally corresponding positions.The third-layer heads attended to corresponding positions in prompts and to tokens generated by executing the same script line in documents; this pattern persisted without a recurring separator.Source: §2.5 · p. 20
• Masking top-layer attention to non-structurally-corresponding positions improved pretraining cross-entropy and chain-of-thought accuracy, especially for short prompts.The same intervention hurt pretraining performance when applied to other layers; the chain-of-thought intervention changed no other part of the trained model.Source: §2.5 · p. 20, Figure 11 · p. 21
• The proposed algorithm first identifies document structure in lower layers, then uses top-layer analogical reasoning to predict the structurally required token.Once structure is induced, both function evaluation and chain-of-thought prompting reduce to predicting f_i(x) for the final input token, which the authors say helps explain chain-of-thought emergence in small models.Source: §2.5 · p. 20
• A second-layer probe decoded local functional-relation graphs with highest accuracy, and probe accuracy rose rapidly at about 70M training tokens.Probe complexity was about 50% of that for a control task with randomized functions, indicating the layer encoded nontrivial information.Source: §2.5 · p. 20

Qualitative Properties of ICL

• The discussion identifies intermediate-step prompting and description-length task complexity as theoretical predictions, and reports evidence for the latter from InstructGPT.It also reports that controlled transformers recombine function knowledge and that ICL gets harder as |F| increases.Source: §3 · p. 22

Theoretical Guarantees for In-Context Learning

• The bounds characterize ICL for an optimal predictor in terms of task description length, but extending them to finite-capacity models trained on finite data remains open.They cover an open-ended hypothesis space that recombines compositional operations, and support the benefit of intermediate-step prompting.Source: §3 · p. 22

ICL in Controlled Setups

• Unlike prior controlled setups, this study models compositional recombination, inducing ICL on tasks of varying complexity and accounting for the benefit of intermediate steps.Earlier transformer studies directly meta-trained on candidate function classes, while other setups used fixed tasks or held-out classes.Source: §3 · p. 22

Emergence and Grokking

• Many tasks emerged suddenly despite continuously decreasing pretraining loss, and their emergence coincided with improved structural representations.The authors note commonalities with grokking in supervised learning.Source: §3 · p. 23

Mechanisms of ICL

• In the controlled setup, ICL relied partly on attention heads attending to structurally related earlier positions, allowing behavior to be copied.The authors suggest this may relate to hypothesized induction-head roles.Source: §3 · p. 23

Pretraining Data and Natural Language

• The miniature pretraining data repeats structure within documents but cannot model natural language’s cross-document repetition or shared grammatical and lexical conventions.The authors describe the dataset as a minimal CAG and identify more realistic CAGs as future work.Source: §3 · p. 24

Limitations and Future Work

• The analysis covers functions over a fixed finite universe and fixed sequences of functions, not open-ended inputs or input-dependent reasoning chains with multiple acceptable answers.Quantifying description-length task difficulty for naturalistic tasks is also left for future research.Source: §3 · p. 24

4 Conclusion

• The analysis gives a general error bound for in-context learning of functions under linguistically motivated assumptions about the pretraining corpus.It explains how generic next-token prediction can enable learning from demonstrations in context.Source: §4 · p. 24
• A second theoretical result proves a benefit from prompting models to provide intermediate steps toward an answer.The experiments also find the theoretically predicted benefit of intermediate-step prompting.Source: §4 · p. 25
• In a controlled miniature setup, in-context learning emerges when parameters and data scale, alongside recombination of abilities from different parts of pretraining data.These findings are presented as a step toward understanding emergent properties in large language models.Source: §4 · p. 25

E Attention Maps

• Figure 14 shows full attention maps for chain-of-thought prompting in the 21M-parameter model, with heads as columns and layers as rows.The bottom-right corner is shown in Figure 11A.Source: Figure 14 · p. 33
• Figure 15 shows attention maps for the last 15 tokens under chain-of-thought prompting with the separator removed, again with heads as columns and layers as rows.The corresponding version with the separator is shown in Figure 11A.Source: Figure 15 · p. 34
• Compare Figure 15's separator-removed maps with the corresponding separator-included version in Figure 11A.Figure 14 also directs readers to Figure 11A for its bottom-right corner.Source: Figure 14 · p. 33, Figure 15 · p. 34

A Task Definitions

• The task definitions include logical function-relation statements, with the listed formulas specifying distinct combinations of function evaluations.The first listed formula is marked MISSINGLINK (#2).Source: A Task Definitions · p. 35
• Additional task definitions give longer disjunctive combinations of function evaluations.These include the statements numbered 8–10.Source: A Task Definitions · p. 35

Composed

• The composed-task extension uses a chain of three functions connecting x and y, with z as the target and another intervening object unobserved.Its formula introduces the unobserved object a.Source: Composed · p. 36

Binary Classification

• Binary-classification task formulas define labels using function relations, including a version with an existentially quantified intermediate object.The quantified version appears in task 15.Source: Binary Classification · p. 36

B Example Documents

• Example document scripts assign each print statement a color and color document tokens according to which statement produced them.The examples are presented as document scripts.Source: B Example Documents · p. 36

B.1 Example 1

• The cited script fragments show a loop over x1 such that f0(x1) = x0, alongside print statements and conditional markers including ELSE and ENDIF.Source: §B.1 · p. 36

B.2 Example 2; B.3 Example 3

• The passages show script fragments combining PRINT statements with control-flow markers such as ELSE, ENDIF, END, and ENDFOR, plus loop constructs conditioned on f7, f0, or f2.Source: §B.2 · p. 37, §B.3 · pp. 37–38

B.4 Example 4: Representability of Test Tasks

• The function-evaluation script uses a free variable for the input, and its syntax tree has three nodes with the function defined by one literal.The script introduces a variable and prints within a block.Source: §B.4 · p. 38
• The MISSINGLINK script has nine syntax-tree nodes and defines its function using four literals; a 2-DNF with d disjuncts can use at most 6d −3 nodes.The stated construction uses d FOR SOME statements, d −1 IF-THEN-ELSE statements, 3d −2 blocks, and d PRINT statements.Source: §B.4 · p. 39
• The section also expresses binary tasks and function composition as scripts, and distinguishes CHAINOFTHOUGHT and EXPLANATION versions.The cited text introduces the respective task expressions but does not provide their outcomes.Source: §B.4 · p. 39
• Because functions fi are not generally invertible, the representation is sometimes only approximate; experiments exclude inputs without unambiguous solutions, partly mitigating this.This limits the experimental inputs to cases with unambiguous solutions.Source: §B.4 · p. 39

C Training Details

• 1% of the dataset was reserved for development.Source: C Training Details · p. 40
• Training used AdamW with a learning rate of 1e-4 and a batch size of 64.Source: C Training Details · p. 40
• A cosine schedule used 1000 warmup steps and 2e6 training steps; settings were chosen to minimize pretraining cross-entropy before evaluating ICL.Source: C Training Details · p. 40

D Stability to World

• Results remained consistent across four additional worlds sampled by retraining the medium-size model.Source: D Stability to World · p. 40

F.1.1 A Standard PCFG Generating Derivation Trees

• The PCFG backbone generates derivation trees using finite terminals, nonterminals, and production rules with probabilities.Source: §F.1.1 · pp. 41–42

F.1 Formal Definition of Compositional Attribute Grammars

• A Compositional Attribute Grammar (CAG) combines a PCFG that generates derivation trees with a yield operation that maps trees to strings.CAG yields can pass attributes between subtrees and recombine or repeat subtree yields, capabilities beyond simple concatenation.Source: §F.1.2 · p. 43

F.1.2 A yield operation mapping derivations to strings

• The yield operation can order and repeat daughter trees, assign them attributes, and use randomness to vary their composition.Repeated use of a daughter tree with different attributes supports loop-like constructions.Source: §F.1.2 · p. 43, Figure 19 · p. 44

F.2 Regularity Assumptions

• The regularity assumptions require closure under projection, concatenation, marginalization, and constants, alongside conditions ensuring trees are used and expected document length is finite.Source: §F.2 · pp. 45–46

F.3 Preparatory Lemmas

• Iteration complexity Rn measures the additional complexity of generating repeated instances of an operation; sublinear growth guarantees ICL errors converge to zero as prompt length increases.Source: §F.3 · pp. 46–47

F.4 Proof of Theorem 1

• Theorem 1’s proof bounds ICL loss using iteration complexity Rn and task description length D[τφ], with constants tied to grammar probabilities and expected document length.The proof bounds prompt description length, lower-bounds its probability under the predictive model, and then derives an error bound; the result applies to prompts of the form xφ(x).Source: §F.4 · pp. 47, 48, 51

F.5 Extension to Stochastic or Noisy Functions

• For stochastic or noisy functions, the paper gives an analogous regret bound comparing ICL loss with the optimal loss from output entropy.The bound’s constants depend on the PCFG, separator, and average document length, but not otherwise on |Ω|, φ, or n.Source: §F.5 · p. 52

F.6 Necessity of Dependence on Rn

• An adversarial production rule can make the Rn dependence necessary and slow ICL, but cannot prevent it; the guarantee remains stable when other data-generating rules are mixed in.Source: §F.6 · pp. 52–53

F.7 Broad ICL Skills Require Non-Context-Free Generative Process

• Broad ICL guarantees require more than a PCFG: repetition costs grow with n in a PCFG, and hard-coded prompt rules work only for the specific function encoded.The CAG guarantee persists when extended with other, possibly adversarial, production rules, which affect only the bound’s constants.Source: §F.7 · p. 54

G Proof of Theorem 2

• The proof reduces Theorem 2 to Theorem 1 by constructing prompts that repeat derivation trees for two functions.The resulting zero-one error on each of the two prompts is bounded by O(Rn + D[τφ1]).Source: G Proof of Theorem 2 · pp. 54–55
• Averaging over arbitrary functions φ2 makes the constructed prompt distribution match the distribution used in the theorem, completing the reduction.Source: G Proof of Theorem 2 · p. 55

H Linguistic Grammar Formalisms and Design Choices

• CAGs condense mathematical ideas from formal grammar research into a minimal formalism for analyzing what next-token prediction on compositional data entails for ICL.They are not intended as a competing full-fledged grammar formalism.Source: H Linguistic Grammar Formalisms and… · p. 55

H.1 Role of Yield Function

• CAGs use a PCFG backbone to generate derivation trees and a yield function to map them to strings, while GCFGs allow more general string functions and tuple-valued yields.Concatenation recovers the context-free case; CAGs use string-valued yields for simplicity.Source: §H.1 · pp. 55–56
• Attributes can carry semantic referents through derivation trees, and keeping them separate from nonterminals preserves compositional structure without bounds that deteriorate as the universe grows.CAGs represent attributes as fixed-length lists; compiling them into nonterminals can inflate grammars and obscure generalizations.Source: §H.1 · pp. 56–57
• Additional randomness in the yield function avoids expanding production rules for alternative attribute assignments, while attributes and randomness decouple ICL bounds from world size.The bounds' constants remain unchanged as the world grows, including for arbitrarily long prompts.Source: §H.1 · p. 57
• Applying Theorems 1–2 requires a GCFG-style description, rules that abstract over attributes, a grammar modeling the full generative distribution, and the ability to repeat derivation trees.The repetition condition is nontrivial and requires generative power beyond context-free grammars.Source: §H.1 · pp. 57–58

H.2 Derivation Trees with Infinitely Many Node Types

• For TAG and CCG with infinitely many node labels, the analysis can adapt by measuring description length using both tree size and node complexity.The finiteness assumption is used in Proposition 5 to bound probability in terms of description length.Source: §H.2 · p. 58

H.3 Repeating Structures in Grammar Formalisms

• Some grammars support repetition directly, while others simulate loops; restricted loop nesting suffices for the paper's tasks, whose functions contain no loop operations.The paper also notes that bounded nesting can support bounds for functions containing loops.Source: §H.3 · pp. 58–59
• An MCFG can be extended with parallel copies and a repeat rule so any function definable in the original grammar can receive ICL bounds, though compiling attributes into nonterminals inflates the grammar.The extension iterates a definable function up to |Ω| times; separating attributes avoids the inflation.Source: §H.3 · p. 60

Correspondence to CAG

• The theory predicts ICL accuracy decreases with |F| but not |Ω| because the script grammar's production rules depend on |F|, not the object universe.Free variables correspond to attributes in the CAG representation.Source: I Details for Document Scripts · p. 62

Sampling Document Scripts

• Training scripts use a compound PCFG prior with sampled production probabilities constrained to keep expected document length at most 64 tokens.The distributions are mixed because the authors lack prior expectations for command-production probabilities.Source: I Details for Document Scripts · p. 63

Variables

• The script grammar enforces available-variable scope and blocks productions requiring more open variables than are available.The CAG translation automatically enforces these constraints.Source: I Details for Document Scripts · p. 63

Enforcing termination

• Depth-dependent downweighting of recursive rules enforces rapid termination but breaks the PCFG assumptions and may reduce compositional bias.The recursive-rule probabilities are scaled by (depth)^-2 and renormalized.Source: I Details for Document Scripts · pp. 63–64

J HMM5 Training Datasets

• HMM5 samples documents from a randomly selected mixture of five HMMs whose states pair entities with properties and emit the corresponding property-value symbol.The HMMs share an entity transition matrix but have separate property transition matrices.Source: J HMM5 Training Datasets · p. 64
• HMMPERDOC samples entity and property transition matrices separately for each document, with Nperm = 1; preliminary experiments found ICL much less successful at Nperm = 10 or 100.Its constraints exclude either f2 or f3 from transition dynamics.Source: J HMM5 Training Datasets · p. 64

K Effect of |Ω|

• For fixed N, increasing |Ω| can make prompts more distinctive by making it less likely that another low-description-length function matches them.The paper reports improved accuracy on some tasks as |Ω| increases, despite the theoretical bound being independent of |Ω|.Source: K Effect of |Ω| · p. 64

L Ablations

• The ablations remove loops, “for some” variable introduction, or if-then-else conditions and train 21M-parameter language models.When loops are removed, a randomly set free variable is added to retain a variable.Source: L Ablations · p. 65

• Prompts separate inputs from labels with single newlines and separate examples with double newlines; about 14 prompts were sampled per task and prompt length.Source: O GPT-3 Experiment · p. 65
• Ablating loops and “for some” makes ICL impossible, whereas ablating “if-then-else” barely affects performance, if at all.Source: Figure 24 · p. 66
• Experiments vary prompt length and evaluate models with |Ω| = 30 or |Ω| = 300 at 85M parameters.Source: O GPT-3 Experiment · p. 68
• Accuracies are highly correlated between full-data pretraining and pretraining with documents containing valid test prompts removed.Source: Figure 29 · p. 69