PaperlayerView exact revision on arXiv

Source-linked AI summary

The Learnability of In-Context Learning

Noam Wies, Yoav Levine, Amnon Shashua

arXiv:2303.07895v1cs.CL

TL;DR

The paper studies why frozen pretrained language models can learn downstream tasks from concatenated examples despite the mismatch with their pretraining distribution. It introduces a PAC framework separating pretraining from in-context prediction and proves efficient learning for latent-task mixtures under mild assumptions, while leaving extensions to new tasks outside pretraining open.

  • Problem

    In-context learning is practically important but lacks a formal learning definition and theoretical explanation, especially when prompts diverge from pretraining data.

  • Method

    The paper defines PAC in-context learnability for a frozen model pretrained on a distribution, then evaluates predictions from concatenated downstream examples.

  • Results

    Under mild assumptions, latent tasks in a pretraining mixture are efficiently learned in-context without modifying model weights, with finite sample-complexity guarantees.

  • Takeaways & Limitations

    The analysis indicates that in this setting in-context learning is more about identifying a task already learned during pretraining than learning it anew.

  • Takeaways & Limitations

    The results do not yet extend to tasks absent from the pretraining distribution, and the connection between model size and in-context efficiency remains open.

Abstract

from arXiv · show

In-context learning is a surprising and important phenomenon that emerged when modern language models were scaled to billions of learned parameters. Without modifying a large language model's weights, it can be tuned to perform various downstream natural language tasks simply by including concatenated training examples of these tasks in its input. Though disruptive for many practical applications of large language models, this emergent learning paradigm is not well understood from a theoretical perspective. In this paper, we propose a first-of-its-kind PAC based framework for in-context learnability, and use it to provide the first finite sample complexity results for the in-context learning setup. Our framework includes an initial pretraining phase, which fits a function to the pretraining distribution, and then a second in-context learning phase, which keeps this function constant and concatenates training examples of the downstream task in its input. We use our framework in order to prove that, under mild assumptions, when the pretraining distribution is a mixture of latent tasks (a model often considered for natural language pretraining), these tasks can be efficiently learned via in-context learning, even though the model's weights are unchanged and the input significantly diverges from the pretraining distribution. Our theoretical analysis reveals that in this setting, in-context learning is more about identifying the task than about learning it, a result which is in line with a series of recent empirical findings. We hope that the in-context learnability framework presented in this paper will facilitate future progress towards a deeper understanding of this important new learning paradigm.

1 INTRODUCTION

In-context learning lets pretrained language models specialize from concatenated examples without weight access, but its effectiveness lacks a formal learning theory. This paper introduces a PAC framework and proves efficient learning when pretraining mixes latent downstream tasks.

  • 1 INTRODUCTION: In-context learning specializes large language models using task examples in the input, without modifying or accessing model weights.This provides a practical alternative to fine-tuning, often requiring relatively few examples.
  • 1 INTRODUCTION: The paper addresses the lack of a formal definition and theoretical understanding of why in-context learning works.A central puzzle is that concatenated input-output pairs diverge from the natural pretraining distribution.
  • 1 INTRODUCTION: The proposed PAC framework provides the first finite sample-complexity results for in-context learning in a general mixture setting.This contrasts with prior theoretical work limited to infinite in-context examples or specific HMM mixtures.
  • 1 INTRODUCTION: Under mild assumptions, latent downstream tasks in a pretraining mixture are efficiently learned through in-context examples without changing model weights.The assumptions include positive mixture and token probabilities, task distinguishability, and sufficient label margins.
  • 1 INTRODUCTION: Recent empirical findings support interpreting in-context learning as identifying a task already represented during pretraining rather than learning it from scratch.Randomizing example labels can barely affect performance, consistent with latent task identification.

2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING

The paper formalizes in-context learning as PAC learnability for a frozen pretrained model that predicts labels from prompts of labeled examples. The framework separates pretraining from downstream prompting and requires low loss across multiple tasks with polynomial sample complexity.

  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: The framework defines PAC learnability for in-context learning capabilities of large language models.It is designed to capture few-shot learning while keeping the pretrained model fixed.
  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: In-context learning constructs a prompt by concatenating downstream input-label pairs, then predicts the label maximizing the model’s likelihood after the prompt and new input.The prompt prefix differs from inputs encountered during ordinary pretraining.
  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: The formal setup uses a frozen probabilistic model pretrained on a distribution D and evaluates zero-one loss on downstream tasks sampled from their distribution.The same model must achieve low loss for multiple downstream tasks simultaneously.
  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: Efficient in-context learnability requires both pretraining and downstream sample-complexity functions to be polynomial in ǫ^-1 and δ^-1.The definition explicitly separates the number of pretraining examples from the number of in-context examples.
  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: The framework assumes the pretraining distribution belongs to a learnable hypothesis class and that sufficient pretraining data approximates token conditional distributions within ǫ with probability at least 1−δ.This formalizes imperfect but controlled pretraining accuracy.
  • 2 A PAC LEARNABILITY FRAMEWORK FOR IN-CONTEXT LEARNING: The framework asks how frozen pretrained models can learn from prompts that do not resemble their pretraining distribution.This question motivates the subsequent latent-task analysis.

3 GUARANTEES ON IN-CONTEXT LEARNING

The paper models pretraining as learning a mixture of latent downstream tasks and shows that concatenated examples can identify the relevant task, yielding PAC in-context learning under mild assumptions. Its analysis provides polynomial sample-complexity guarantees despite imperfect pretraining and distribution drift.

  • 3.1 THE ANALYZED LATENT CONCEPT HYPOTHESIS CLASS: Pretraining is modeled as a mixture of downstream task distributions whose task identity is latent rather than explicitly provided.Each pretraining sequence is generated by sampling a concept and then tokens from that concept-specific distribution.
  • 3.1 THE ANALYZED LATENT CONCEPT HYPOTHESIS CLASS: In-context examples are sampled from one mixture component, with the final token held out as the downstream label.Concatenating independent examples creates a prompt that can diverge from the pretraining distribution.
  • 3.1 THE ANALYZED LATENT CONCEPT HYPOTHESIS CLASS: Approximate independence and positive token and task probabilities control concentration, prompt likelihood, and recognition of the relevant latent task.The assumptions address dependence between concatenated strings, zero-likelihood prompts, and arbitrarily rare concepts.
  • 3.2 GUARANTEES ON IN-CONTEXT LEARNING VIA LATENT CONCEPT INFERENCE: For sufficiently separated label likelihoods, polynomially many in-context examples make predictions converge to the correct label with probability at least 1−δ.The guarantee tolerates imperfect pretraining, and the theorem states that it still holds when prompt labels are randomly flipped.
  • 3.2 GUARANTEES ON IN-CONTEXT LEARNING VIA LATENT CONCEPT INFERENCE: As prompt examples accumulate, likelihood ratios favor the ground-truth mixture component at a rate exponential in example count and minimum KL divergence.The prompt reweights mixture-component priors, allowing latent concept inference from concatenated examples.
  • 3.2 GUARANTEES ON IN-CONTEXT LEARNING VIA LATENT CONCEPT INFERENCE: Under the stated margin, divergence, and regularity assumptions, the downstream hypothesis class is efficiently in-context learnable after pretraining.The result formalizes in-context learning as task recognition rather than learning a new task from scratch.

4 RELATED WORK

Related work studies PAC generalization, concatenated-context learning, mechanisms such as induction heads and gradient descent, and latent-task explanations. The paper distinguishes its guarantees by covering broader mixtures, finite polynomial sample complexity, and imperfect pretraining.

  • PAC LEARNING: Distribution-dependent PAC theory relaxes adversarial generalization requirements by restricting attention to distributions with specified statistical properties.This line of work provides more realistic sample-complexity analyses.
  • CONCATENATED-CONTEXT LEARNING: Several studies show that Transformers can discover in-context algorithms for function classes including neural networks, decision trees, and least-squares learning.These results concern architectural expressivity and learned algorithms in synthetic or structured settings.
  • MECHANISMS FOR IN-CONTEXT LEARNING: Other work proposes induction heads as a possible mechanism and shows that self-attention can implement gradient descent with in-context examples.These studies do not explain why pretraining on natural data should converge to such behavior.
  • LATENT-TASK EXPLANATIONS: Compared with Xie et al., this paper handles any mixture satisfying mild assumptions, gives polynomial rather than infinite-example guarantees, and allows imperfect pretraining.Xie et al. analyze a mixture of HMMs and assume perfect learning of the pretraining distribution.

5 CONCLUSION

The paper develops a PAC-based framework that gives finite sample-complexity guarantees for in-context learning in pretrained models under a latent multitask pretraining framework. Its results establish efficient, polynomial in-context learning while identifying extensions to new tasks and links to model size as open questions.

  • The PAC-based framework provides the first finite sample complexity results for in-context learning in pretrained models.
  • Under a common latent multitask pretraining framework, the theory explains how pretrained models can use concatenated downstream task examples despite their distributional mismatch.
  • The results indicate efficient, polynomial in-context learning, reflecting the behavior of this setting in practice.
  • The connection between model size and in-context learning efficiency remains an open question.
  • Extending the results to new tasks absent from the pretraining distribution is another open question.

A PROOF OF LEMMA 1

The proof of Lemma 1 controls prompt-probability deviations using approximate independence, distribution-drift assumptions, and concentration. It then shows that sufficiently many in-context examples make the ground-truth task component distinguishable from competing mixture components with polynomial sample requirements.

  • Assumption 2 provides approximate independence among in-context examples, enabling Hoeffding’s inequality to bound deviations from expectation.The expectation is related to a Kullback–Leibler divergence between mixture components.
  • Assumption 3 bounds distribution drift caused by the artificial newline token and potential label flipping.The proof introduces a corrected label when analyzing label-flipping drift.
  • As the ground-truth task component becomes sufficiently distinguishable from the other mixture components, the competing prompt-probability ratio converges to zero.
  • A sufficiently large number of in-context examples yields the required probability bound with confidence at least 1 −δ.The proof selects the sample requirement to combine the concentration and approximation terms.

B PROOF OF THEOREM 1

The proof of Theorem 1 combines approximate prompt–test independence with mixture-component likelihood comparisons. Under the stated assumptions, it establishes a sufficient in-context sample size whose bound is polynomial in T.

  • Assumption 2 makes the prompt approximately independent of the test example for each mixture component.
  • The proof separates numerator and denominator terms into contributions from the ground-truth component and all other mixture components.
  • The argument uses positivity and probability identities together with Assumption 4’s lower bound on the ground-truth component prior.
  • A sufficient number of in-context examples guarantees the target bound with probability at least 1 −δ.
  • The resulting sample requirement is polynomial in T.
Loading 2303.07895v1…