The Learnability of In-Context Learning
Authors: Noam Wies
Yoav Levine
Amnon Shashua
Venue: NeurIPS 2023 poster (2023)
Keywords: in-context
PAC
language models
foundation models
LLMs
TL;DR: Mathematical theory for in-context learning.

Abstract: 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.

The Learnability of In-Context Learning
Noam Wies, Yoav Levine & Ammon Shashua The Hebrew University of Jerusalem (noam. wies, yoav. levine, shashua fcs. huji. acc... il
Abstract
In-context learning is a surprising and important phenomenon that emerged when modern language models were scaled to billions learned parameters. Without modifying large language model's weights, it can be tuned to perform various downstream natural language tasks simply by including concatenated training ex- amples of these tasks in its input. Though disruptive for many practical applications large language models, this emergent learning paradigm is not well understood from theoretical perspective. In this paper, propose based framework for in-context learnability, and use it to provide the first finite sam- ple 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 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 prove that, under mild assumptions, when the pretraining dis- tribution is 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 '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 in line with 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 this important new learning paradigm.
trrst-of-its-kin PAC
Introduction
The practice of pretraining language models (LMs) over massive general purpose text corpora has revolutionized natural language processing in recent years (Radford et al., 2019; Devlin et al. 2019 Brown et al. 2020). After LM has been pretrained, the common approach for applying to specific downstream natural language task is to further train it on task-specific data, in a procedure referred to fine-tuning (Howard & Ruder 2018 Radford et al. 2018 Devlin al., 2019). In
their influential GPT3 paper, Brown et al. (2020) showed that a non-trivial alternative to fine-tuning emerges when the LM is large enough: an LM can be specialized
downstream natural language task by simply receiving in its input string composed of concatenated training examples of this task. Importantly, while the LM's weights are unchanged in this procedure, some form of learning evidently takes place; the performance on the downstream task was shown to significantly improve with the number of concatenated training examples, for disparate variety of natural language tasks.
This phenomenon, referred to as in-context learning, has had a profound practical impact on the applicability of large LMs: one does not need to have any access to the model weights in order to specialize the model for a certain task. Instead, a string of training examples provided even via API access to the model is enough, and often not many examples However, despite its growing popularity in a multitude of use-cases (Bommasani et al. 2021). the reasons for the effectiveness of in-context learning in pretrained LMs not well understood from
required (Brown et al. (020).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a theoretical perspective. In particular, this new learning paradigm still lacks formal definition of learning.
In this paper, we propose a PAC learning (Valiant 1984) definition for in-context learning, along with the first finite sample-complexty learning results for in-context learning. Our results shed light on the mysterious question of why in-context learning works even though a string of concatenated input-output pairs does not resemble the natural distribution of pretraining examples. Our framework is based on an interpretation of pretraining as unsupervised multi-task learning of many natural language tasks, which dates back to the GPT2 paper (Radford et al. (019), one of the instigators of the LM pretraining era. This view, which has since been widely adopted, was supported by experiments that revealed non-trivial zero-shot capabilities of pretrained LMs on a variety of natural language tasks. In other words, an LM pretrained only to maximize the likelihood of unlabeled text from the web, was able to perform reasonably well on a variety of downstream natural language tasks without learning from any additional training examples post pretraining, implying that many different natural tasks are directly learned during pretraining.
Following this interpretation, we prove our in-context learning results in a setting in which the pretraining distribution is a mixture of downstream tasks. Importantly, the pretraining examples are not explicitly associated with downstream tasks, but rather they are drawn from a mixture of tasks and the association between examples and tasks is latent. We prove that under mild assumptions, in-context learning is guaranteed to happen for a model trained by such multi-task pretraining. We show that the in-context learning mechanism of concatenating input/output pairs of a certain task allows the pretrained LM to uncover the latent task and improve its performance without modifying its weights. Our assumptions are quite general, namely that there is lower bound on the probability of any mixture component and of any token, and that the downstream tasks are both distinguishable and have sufficient margin between different labels. See Section 3.1 for a formal definition of our assumptions.
The interpretation of in-context learning as uncovering tasks that were already learned during pretraining is also supported by empirical evidence. For example, both Min et al. (2022) and Lyu et al. (2023) showed that replacing the labels provided in the in-context training examples with random task labels barely affects the performance of in-context learning, implying that the in-context learning mechanism more about identifying the task than about learning it. Similarly, both Webson & Pavlick (002) and Lampinen et al. (2022) studied whether LMs truly understand the text of the in-context examples, and found that irrelevant text that mimic the task can have a similar effect as learning with true training examples.
Finally, the latent task inference perspective of in-context learning was also examined theoreti- cally. Xie et al. (2022) study a language-inspired toy distribution for pretraining. Specifically, they analyze a pretraining distribution consisting of a mixture of Hidden Markov Models (HMMs), where each HMM factor corresponds to a single task. They showed that in this setting in-context learning was guaranteed, however, unlike our work, their analysis confined only to the infinite limit of the number of in-context examples. We provide polynomial sample complexity guarantees for in-context learning, which are much more relevant to its efficiency in practice (often referred to as "few-shot"). Furthermore, Xie et al.) (2022) limit their analysis only to a certain class of mixture of HMMs as pretraining distribution, while our results are for any mixture distribution under mild assumptions (see above). Lastly, their analysis assumes perfect learning of the pretraining distribution while our PAC approach captures imperfect pretraining. Beyond Xie et al. (2022), several recent papers (Akyürek) et al. 2023 Dai et al. 2022; von Oswald et al.) 2022) showed that from an expressivity point of view, self-attention architectures can implement a gradient descent algorithm with in-context examples. However, these works do not justify why pretraining on natural data will converge weights that im- plement gradient decent, nor do they provide finite sample-complent
results for in-context learning. Overall, our presented PAC framework for in-context learning (Section ( allows to prove the first finite in-context learning sample-complexity results, in a quite general setting (Section 3). We hope that this framework will facilitated further expansions of the understanding of in in-context learning as a new learning paradigm.
2

---

2 A PAC Learnability Framework for In-Context Learning
In this section, we define a Probably Approximately Correct (PAC) learnability framework (Valiant 1984) for in-context learning. Conceptually, we aim to adjust the PAC learnability framework, in order to capture the in-context few-shot learning capabilities of large language models (Brown et al. 2020
Wei et al. 2022a Sanh et al. 2022 Ouyang et al. 2022).
We begin by describing the in-context learning paradigm. Let fo be function fitted massive general purpose pretraining distribution. In order to apply So for a specific downstream task, it is common to further train So on pairs of the task's inputs 2:,,-..: 32k with their corresponding labels y1...., yk. in a procedure referred to as fine-tuning. In-context learning is an alternative, simpler technique, which "teaches" fe the task at hand by constructing prompt comprised of concatenated training examples. Specifically, denote the string concatenation operator by 4 and let "\n" be special delimiter token. Then, the in-context learning technique to construct a prompt p by concatenating pairs of the task's 's inputs along with theirs labels:
p == 21 ① y1 @ "nn" C I& + yk + "nn"
(1)
Given this prompt, the prediction is made by choosing the label y that is the most likely continuation for the prefix p i x according to the function fo- other words, by predicting the label y that maximizes fo (p @ x @ y). Notably, the prefix p & x does not resemble inputs that fo has trained on. Note that we used the newline symbol "nn" for clarity. However, in practice the delimiter token might depend on implementation and could, for instance, be two successive newlines "(n)n" as done in the few-shot learning evaluation framework Evaluation Harness (Gao et al. 2021).
We now present our in-context learning learnability definition. Let 'D be a pretraining distribution over strings of characters from an alphabet 2. And let D be a downstream task's 's distribution over pairs of strings x E "* and theirs corresponding labels y E Σ* We aim define petriiuutionddepeddee learnability in the in-context learning setup, for frozen probabilistic model fo that originally trained to maximize the likelihood of the pretraining distribution D. Then, given prompt p ~ D which consist of k pairs of inputs and theirs corresponding labels, each independently sampled from D, the model fe is tested on the zero-one loss of the in-context predictor:
In D = E E 11-1 (argmax.// fo (p @ x @ v.)).))
Since we are interested in frozen models as opposed to models that are fine-tuned, we will require that the same fa model achieves low Lnn-coeext D loss for multiple downstream tasks simultaneously. The following is our PAC learning definition for in-context learning of model that was pretrained to maximize the likelihood of the pretraining distribution.
Definition 1. Let H. and H. be hypothesis classes of pretraining distributions and downstream distributiooss respectively. We say that H. is in-context learnable after pretraining on a pretraining distribution D E H. if there exist a pretraining algoritlum A and pair of functions mH, mü (0, 1)² + N with the following property: For every 6,6 6 >> O and every D E H. if the number of pretraining examples is greater than my (e, 8), and if the number of the downstream tasks' examples k is greater than m& (e, (, then with probability of at least 1 - 5 (over the choice of the + k examples) the following holds:
in-comtent D Bayes Error Rate Se
(3)
In addition, we will say that collection of downstream tasks H is efficiently in-context learnable after pretraining on D. if both my and m. in the above definition are polynomial in log -1, log 8-1
and log H
In order focus in-context learning questions that relevant for the natural language processing setup, and avoid complications that are not necessary for answering them, we will assume that the pretraining distribution D belongs some hypothesis class H that is learnable by some pretraining algorithm:
Assumption There exists a learning algorithm A. and a sample complexity function m.p (0, 10 N, with the following property: for any pretraining distribution D E H and any e, > the number of pretraining examples is greater than mD (e, 8), then with probability at least 8
3

---

over the pretraining examples. for any T 2 1, the total variation of the conditional distributions of the T 'th token at most E:
max OL.OTEE EZ
ITD 0r--) - fo (r)) <E
(4)
where fo denotes the model yielded by the pretraining algorithm A and fo (orlor 0r-1) denotes for the conditional likelihood folor...0r-107 10r) In addition, m'p is polynomial in both e and 8-1
fo(o:
With the above formal definition of in-context learning, we aim to shed some light the mysterious in-context learning abilities of large LMs. Specifically, in the next section, we will shed light on the following major question: How do frozen pretrained models learn from prompts that do not resemble their pretraining distribution?
3 Guarantees on In-Context Learning
In this section, we will demonstrate the use of the above learnability framework for in-context learning and analyze a setting in which pretraining a simple language model provably leads to in-context learning capabilities. For doing so, we follow previous work and view the language modeling task as an implicit multi-task setup. Indeed, creating human-like text involves many different skills, from grammar world knowledge,
learning language model inevitably develops variety of
skills (Gulordava et al. 2018 Zhang & Bowman 2018: Weber et al. (02T). The implicit unsupervised
multi-task view of language modeling can be traced the GPT2 paper (Radford et al. 2019), which revealed that pretrained LMs are capable of a wide variety of natural language tasks without the need for further training. Since then, this view has been reinforced for example by Hendryeks et al. (202T). They showed that on a diverse massive set of 57 real world text understanding tasks, the largest GPT-3 (Brown et al.) 2020) language model improves over random chance by almost 13 percents points on average. Importantly, these results were obtained in zero-shot learning setting, i.e. in setting where the language model had only been pretrained to maximize the likelihood of unlabeled text. Accordingly, these results suggest that many different natural tasks are directly learned during pretraining-
We reflect the above implicit multi-task nature of language modeling by assuming that the pretraining distribution contains latent variable that represents the task at hand. We show below that for such pretraining distributions, adding training examples to the in-context learning prompt implicitly reveals the already learned latent task. In Subsection 3.1 we present a multi-task pretraining hypothesis class, for which Subsection 3.2 shows that in-context learning reveals what task is currently being performed.
3.1 The analyzed latent concept hypothesis class
In this subsection, we describe the analyzed multi-task pretraining hypothesis class, as well as the corresponding downstream task hypothesis class that can be learned in-context after pretraining. To begin, we define the pretraining distribution as mixture of multiple downstream tasks. Importantly, during pretraining the downstream task of each example is unknown, i.e. it is a latent variable, and thus pretraining is not equivalent to fine-tuning on the task since the model cannot simply ignore pretraining examples of irrelevant tasks. Specifically, we generate a length-T' pretraining example Ii...., 2T E Σ from the pretraining distribution 2 by first sampling a concept é from a family of concepts according to a prior IP (o). We then sample the tokens according to the concept's 's specific distribution Po TTT)
Moving to the downstream tasks, we will prove in in-context learnability results for tasks where the underlying inputs distribution is a component é in the pretraining mixture distribution D. Formally, we generate a length T downstream task example x and the corresponding label y from DD by first sampling T tokens 01,..., . or according to the downstream task distribution Pe (01,..., or). Then we assemble x using all tokens except the last one, and set the label to be that token i.e. we set that I, = 0r for any t < T and that y = or. Note that in principle the concatenation of independent examples in p causes a distribution drift from the pretraining distribution]] In this sense, the analyzed
Formally, the distribution drift is caused by the fact that the concatenation of the "An" after y ignores the marginal probabilities of R2,".

---

model captures the fact that fhw-shot prompts are unnatural since they are not encountered during pretraining.
Now we describe assumptions about the pretraining distributions, for which we will prove our in-context learnability results. Our first assumption requires that given a delimiter token "\n", two successive strings $1 and $2 that are concatenated with "n are approximately independent according to p::
Assumption 2. There exists constant 0 < c1 S 1 such that for any two strings $1, 82 in V" and any concept & the following holds:
( @ " P (52) P8 @ "nn" @ 82)
1
(5)
61
Note that when the two successive strings $1 and $2 are exactly independent, the probability ratio in Equation is equal to one, and the constant Cj quantifies the deviation from this situation. While this assumption might sound restrictive, it is reasonable to assume that two consecutive paragraphs are not highly dependent according the distributions in the pretraining mixture. Intuitively, will use this assumption in order to apply concentration inequalities to the likelihood of the in-context prompt, and we will deduce that the role of the in-context prompt is reweight the prior regarding the different mixture components. It is important to note that the approximate independence assumption for any component in the mixture does not imply approximate independence of the mixture distribution itself. Hence this reweighting is possible, since the assumption does not imply that the in-context prompt is ignored.
Beyond this approximate independence, we will also require that there exist a lower bound on the conditional probability of any single token:
Assumption 3. There exist a constant > O such that for any string s in E", any character a E E, and any concept & the following holds:
P (o
(6)
Basically, we need this assumption in order to avoid the harm of zero likelihood due the unnatural concatenation of input and output pairs in the prompt p (where the prompt p is defined in Section 2 Note that without such an assumption, in-context learning impossible since the probability of
prompt might be zero and hence the prediction of the model in such cases becomes meaningless. Finally, we assume that the prior distribution strictly positive. In other words, we will assume that there is lower bound higher than zero the likelihood of any concept appearing in the pretraining distribution.
Assumption 4. There exist constant C3 >> 0 such that for the prior PD (Ø) of any concept d, is at least C3.
Clearly, without such an assumption, the prior of the downstream task can be arbitrarily low, which means it will be nearly impossible to recognize the task. In the next subsection, we will use the above assumptions in order to provide in-context learning guarantees via the mechanism of task recognition.
3.2 Guarantees on In- In-Context Learning via Latent Concept Inference
In this subsection, we analyze the prediction of an in-context learning model in the setting described in Subsection 3.. We show that in this setting, there a polynomial sample complexity that guarantees in-context learning is Probably Approximately Correct. At a high level, since the pretraining is not precise and can only approximate the pretraining distribution D up some error prerraining (see Assumption] [. we will split the in-context prediction analysis into two parts. The first part will involve the simpler case of test examples x and corresponding label candidates y and ÿ for which the margin between the conditional likelihoods of the labels Pp, (y) 2) and P.5. (ū (x) is large enough. In this scenario, we show that both the deviation due to imperfect pretraining and due to imperfect task recognition is negligible. Therefore, we will conclude that such deviations do not have any impact on the loss of in-context learning. In the second scenario, when the difference between ground-truth likelihoods is small, the error rate of the Bayes optimal classifier must be high. Accordingly, even though the in-context predictor might confuse between labels, the loss any case will be small because only compare it to the error rate of the Bayes optimal classifier.
5

---

Starting with the first scenario, where the margin between label candidates is sufficiently large, we will prove that as more examples are added to the prompt, the in-context predictions converge to the correct label. As preliminary step, we prove a lemma regarding the ratio of the prompt likelihoods P (p) (where the prompt p is defined in Section 2 according to the ground-truth task versus the other mixture components. In other words, we ask how likely it is that the prompt of concatenated examples was sampled according to one of the tasks distributions versus the other tasks distributions. We will use this lemma in order to estimate the effect of the in-context prompt, on the prior regarding the different mixture components. Specifically, we denote by 4KL the minimum Ballback-Leiblle divergence between the ground-trute component, and the other mixture components. Then, we prove that the ratio of the prompt probabilities according to the ground-trune components converge zero, with rate that is exponential in both the number of in-context examples k, and in the minimal Kullback-Leibler divergence AKI. Intuitively, the exponential rate with regard to the number of examples comes naturally from the fact that each example in the prompt is sampled independently of the others. As a result, their effect is a multiplicative one. Additionally, the Kullback-I Leibler divergence between the ground truth component and the other mixture components measures log probabilities, while we are interested in the probabilities themselves. Hence the rate is also exponential in the above Kullback-Leibler divergence. Formally, we have that:
Lemma 1. Let D be a pretraining distribution for which assumptions a downstream task mixture component from 'D such that DEL > 8 c1-e2" Then, there exists
23 hold, and let 6= be
ms : (0, + N with the following property: for any 6, > 0 and any of + 6², if the number of in-context examples k is at least m (c, then, (p) c &with probability of at least 1 1-6 5 (over the choice of the k in-context examples). Moreover. the above still holds when the labels in p are randomly 1 flipped, and m can be chosen such that it will be polynomial in log },4 log log a 2 KL
Fs(p)
and T.
Proof. In essence, we prove this lemma by using the approximate independence assumption in order Assumption for bounding the distribution
to apply concentration inequalities. In addition, drift that is caused by the artificially inserted newline token. In particular, the log of the ratio of prompt probabilities according to different mixture components is concentrated around its expectation. Importantly, this expectation is equal to minus one times the Kullback-Leibler divergence between the components, plus a term that is caused by the mentioned distribution drift. Thus, we conclude that the ratio of the prompt probabilities according to the ground-truth task distribution and the other pretraining components converges to zero. Moreover, the rate of that convergence is exponential in both the number of in-context demonstrations, and the minimal Sullback-Leibleee divergence between different mixture components. See full details in Section A of the appendix.
Now we will use the above Lemma Io analyze the in-context predictions, namely the labels ÿ that maximize the likelihood of the concatenation of the in-context prompt y. with the example x @ ğ according to the pretrained model fe. Essentially, we will aim to understand when these predictions are identical to the Bayes Optimal Classifier predictions. That it, when these predictions align with the labels y that maximize the likelihood of the example x + y as determined by downstream task distribution F F. Since we are in the first scenario, where the margin between label candidates is large enough. We will prove that in this case, for large enough k. the ground truth in-context predictor also has margin that is at least half of the original margin. Hence, we will conclude that for such & the ground truth in-context predictor is equal to the Bayes Optimal Classifier. Moreover, we will prove a lower bound on the margin of the in-context predictions, so the above still holds for any distribution that approximates the pretraining distribution sufficiently well.
Formally, for a test example input æ. we define the margin A (x., y, () between two label candidates y and ÿ as the difference between their conditional likelihoods IP, (y xx) and P. (ū x:) according to the downstream ground-truth distribution. Similarly, for a test example input x and in-context prompt p. we define the margin A (p, x, y, 3) between two label candidates y and ğ as the difference between their conditional likelihoods PP (y) O r) and Pp (ū) p @ 2) according to the pretraining distribution conditioned on the prompt p. Using these definitions, we consider triplets of test example input x and two labels candidates y. ÿ with margin at least two times the pretraining error Ppearriiing as the first scenario. In this case we will prove that for large enough the ground truth in-context predictor also has margin of at least the pretraining error Apretraining. This means that deviations arising from imperfect task recognition will be negligible in this situation. Moreover, the margin will remain larger than the pretraining error, which means the pretrained model fe handles this case well.

---

Theorem 1. Let D and DD be pair of pretraining distribution and downstream task, for which Assumption 4 as well as the assumptions in Lemma / Jupholds. Then, there exists m-B (0, 2)² - N with the following property: for every test example I and two label candidates y, 9 with positive mar- gin A (z. M, D) O and ó > 0, if the number of in-context examples k is at least mz (A(z.8.81/2, 6), then 4 (p, Z. ) > A(sw.5)/2 + ci - 1 with probability of at least 1 - 5 (over the choice the k in-context examples). Moreover, the above still holds when the labels in p are randomly flippdd P. and 1 and T. m- can be chosen such that if will be polynomial in log 1 log e log 01 75 KI. 8:
Proof. We begin by writing the difference between the ground truth label likelihood, and the likeli- hood of other another label y explicitly. Specifically, by the definition of conditional probabilities we have that:
(ulpp002) PD (1 (0)p))) E. P (6) PP (p Dr y)
Po (p 1 ū)
(7)
Σ PD (0) (p
Now, denote by 6² the mixture component of DD then Assumption 2 assures us that for each component in the mixture, the textual prompt approximately independent of the test example. So we can use Lemma D and get that in both the numerator and the denominator, the d' term is the dominant term in the sum. Thus, we will get that the difference of the labels' likelihoods is approximately the fraction of the ø² terms, which is equal to the original downstream task margin. So we will conclude that the margin of the in-context predictor is at least half of the downstream task original margin. See full details in Section of the appendix.
We denote by AB the minimal margin of the Bayes Optimal Classifier predictions in downstream task D i.e. the minimal margin between the Bayes Optimal Classifier prediction and another labels. With the above definitions and theorem, we can combine the scenario of large margins, which are preserved by the in-context predictor, with the scenario of small margins, in which the loss is minimally affected by the wrong prediction, and prove our main in-context learnability results:
Theorem 2.
Let H be hypothesis classes of downstream distributions, and denote by D mixture 4 uphold. Further assume that the margin Dp of any downstream task D E H is at least 4 (1 et), and the minimal Kullback-Leible divergence
distribution on H for which assumptions 2 and
between different distributions is greater than log e1-02' Then H. is efficiently in-context learnable after pretraining on D (see Definition T7.
Proof. Assumption [ Jassures us the existence of the pretraining algorithm with a polynomial sample complexity. So we will prove the theorem with pretraining sample complexity that is derived from this algorithm, where the accuracy required from pretraining is a-(1-a) times the accuracy required from in-context learning (see analysis below). In addition, Theorem I assures us that for large enough k the ground truth in-context predictions are equal to the Bayes Optimal Classifier predictions, we will prove the thcorem with downstream sample complexity that is derived from Theorem !
Let c, > 0 and denote by fo the model that was learned during the pretraining process. We will prove that the contribution of any x to the loss IIn-coomex, D (see Equation 2 is at most e and hence complete the proof. Given x, let y be the Bayes Optimal Classifier prediction for that x. Then, we will split the analysis into two cases.
The first case is of examples x. such that theirs margin A (Ir, y, from any alternative label candidate ÿ is at least 8 Apretaining In this case, Theorem T assures us that for large enough & the ground truth in-context predictor also has margin A (p, x. y. 7) that is greater than A (I. y. δ) +
o 1. Now since A (zz y, 3) 2 AD > 4- (1 -1-ctt of) we have that A (p, x. 9) is at least 2- Aperrainnng Thus, we conclude that this case, the predictions of the ground truth in-context prediction and fo are the same. Furthermore both of them are identical to the Bayes Optimal Classifier prediction, and hence r does not contribute to the loss.
While theorem | provides label label-insentn inseeniiseeiieve results, it also predicts sensitivity to the labels in cases where the labels are the primary causes for the distinction between different tasks, as measured by the Kullback-Leibhe divergence.
7

---

Moving to the second case, and denote by ÿ the in-context prediction of fe. Then, the arguments
from the previous paragraph assure us that Po (y =) - F (ÿ [)]z)= 8 Apermining since otherwise we will get that fo (y x) So (ūl a:). Finally, we will choose that A Aretraining = g. and hence get
that also in the second case, the contribution of x to the loss is less than c.
4 Related Work
Since the Probably Approximately Correct (PAC) learning framework was introduced in Valiant (1984), a rich line of works has extended the framework to distribution-dependent bounds (Benedek & Itai 1991 Vayatis & Azencott 1999 Sabato et al., 2013) inter alia. These works relax PAC's adversarial requirement of generalization for all input distributions, and only consider distributions that satisfy certain statistical properties. Consequently, these papers provide more realistic sample complexity bounds. In this paper we present a framework for in-context learning learnability that uses self-supervised pretraining to assist in solving downstream tasks. In this framework, we follow the above line of distribution-speciii works with the distinct feature of a self-supervised pretraining phase, and of learning with frozen models through their input context. The advantages of such pretraining have been studied from a theoretical perspective before. For example. [Saunshi et al. (202T) and Wei et al. (20TT) demonstrate that language modeling can benefit downstream tasks either by prompt tuning or head tuning. However, unlike our work, in their analysis some weights are learned. In contrast, we focus on frozen models that can learn only from their input context, which includes the concatenation of few inputs and outputs pairs.
Returning to in-context learning, a recent line of work study learning paradigms that are based on concatenating several inputs into a single input context. For example, Garg et af. (2022) show that Transformer architecture is able discover in-context learning algorithms for simple function classes, such as two-layer neural networks, and decision trees. Similarly, [Akyürek et al. (2023) show that a Transformer architecture is able discover efficient Bayes optimal least square learning algorithms, and and Laskin et al. (2022) show that Transformer architecture is able to discover efficient in-context reinforcement learning algorithms. Additionally, Levine et al. (2022) studied the inductive bias of in-context learning, and proved that Transformer based language models can model much stronger dependencies between text segments that appeared in the same training example. Finally, Li et al. (2023) proved multi-task generalization bound for in-context learning with the Transformer architecture. However, unlike our work, the pretraining distribution in all of the above works designed to include input context that includes few-shot demonstrations explicitly. As a consequence, these methods do not answer the mysterious question of how frozen pretrained models can learn from in-context prompts that do not resemble their pretraining distribution.
Another recent line of work investigates possible mechanisms that enable in-context learning. For example. Olsson et al. (2022) provide indirect evidence that induction heads might constitute the mechanism for in-context learning in large transformer models. In addition, several recent pa- pers (Akyürek et al.) 2023 Dai et al. [2022] vvo Oswald et al. (2022) showed that from an expressivity point of view, self-attention architectures can implement gradient descent algorithm with in-context examples. Finally, Chan et al. (2022) provided empirical evidence that some data distributional properties encourage in-context learning even when the frozen models do not see prompts during pretraining. However, unlike our work, all of the above works does not provide theoretical guarantees of in-context learnability.
Finally, Xie et al. (2022) are the closest to our work. They studied a language-inspired toy distribution for pretraining and analyzed pretraining distribution consisting of mixture of Hidden Markov Models (HMMs). Unlike their results, our results are applicable to any mixture distribution that meets our mild assumption. In addition, unlike our polynomial sample complexity guarantees, their analysis guarantees in-context learning only for an infinite number of in in-context examples. Lastly, their analysis assumes perfect pretraining distribution learning. but our approach captures imperfect pretraining
Conclusion
The discovery of in-context learning in large LMs, made by Brown et al. (2020), was surprising to many in our field. A model that was pretrained to maximize the likelihood of natural text was able
8

---

to make use of concatenated training examples of downstream natural language tasks inputs that do not resemble its pretraining distribution, and moreover these inputs improved the model's ability to perform the task. Our theoretical results, based on common latent multitask framework for the pretraining phase, shed light on the above surprising mysteries. With our PAC-based framework, we were able to provide sample complexity guarantees for in-context learning in such pretrained models, which are not only the first finite sample complexity results for this framework but they also indicate efficient (polynomial) in-context learning, which reflect the behavior of this setting in practice.
We hope that our framework can be used deepen the understanding of the in-context learning phenomenon. In particular, we mark the connection between model size and the in-contex, learning efficiency as an interesting open question (Wei et al., 2022b). Additionally, in-context learning has shown to be capable of learning new tasks not included in the pre- trainini distribution (Wei et al. 2023). The extensions of our results to such situations, as well as input-dependent bounds that capture the sensitivity of few-shot in-context learning to the order of the few-shot examples is an interesting open questions.
While we assume that the pre-training distribution perfectly matches a mixture of downstream tasks, we acknowledge that the pre-training data in real-world LLMs is often noisy and imperfect. Our results represent an idealized scenario with perfect pre- pre-training data. Extending our analysis to account for limitations of real-world pre- gre-trainin data remains an important direction for future work.
Limitations:
Acknowledgments and Disclosure of Funding
The authors would like to thank Yotam Wolf and Oshri Avnery for their assistance and advice. This research was supported by the ERC (Furopean Research Council) and the ISF (Israel Science Foundation).
References
Ekin Akyürek, Jacob Andreas, Dale Schuurmans, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In International Confer- ence on Learning Representations, 2023. URL
net/ wttprreviewwnne/oorue.... forum?id
DQCX4H8yN4II
Gyora M Benedek and Alon Itai. Learnabilityy with respect to fixed distributions. Theoretical Computer Science, 86(2):377-388 1991.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx. Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint wxXiv:2108.07221 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information PtcholonoPPoooo Processsig Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL htttpsss//procceenngg..sto 96741 0114444480808811144644000-000-00
Stephanic C.Y. Chan, Adam Santoro, Andrew Kyle Lampinen, Jane X Wang. Aaditya K Singh, Pierre Harvey Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learning in transformers. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL net https://epenreviie http:ew.eeetttueeeeeeeeeee Eorumoorioio. For./ooommm---H--pSS-
Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei. Why can gpt learn in- context? language models secretly perform gradient descent as meta optimizers. arXiv preprint 12X1:22212.1059, 2022.

---

Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACI-HLLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019. doi: 10.18653/v1/11--444 URL http://0..16633//////// 1423
Leo Gao, Jonathan Tow, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Gold- ing, Jeffrey Hsu, Kyle McDonell, Niklas Muennighoff, Jason Phang, Laria Reynolds, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. A framework for few-shot language model evaluation, September 2021. URL/tttps: doi org/10. 10. 5281/ zenodo. 5371628 628
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? case study of simple function classes. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022. URL
net /iret/fooee Eorum? id f fiN2J2e0et
Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. Colorless
green recurrent networks dream hierarchically. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume (Long Papers), pp. 1195-1205, New Orlcans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/1I/1181111 URL https://
aclanthology Bww.anttooooo.ooo//-B--------- org/N18-1100
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Confer-
ence on Learning Representations, 2021. URL http:::
net/ forum?id-
d7KB jmI 3GmQ,
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pp. 409-426. Springer, 1994.
Jeremy Howard and Sebastian Ruder. Universal language model fine-tuning for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 328-339, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 18.18653/v I/P18- 1031.
http///acclathoooy.....o. wwwp/o/-/////...
Andrew Lampinen, Ishita Dasgupta, Stephanie Chan, Kory Mathewson, Mh Tessler, Antonia Creswell, James McClelland, Jane Wang, and Felix Hill. Can language models learn from explanations in context? In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 537-563, Abu Dhabi, United Arab Emirates, December 2022, Association for Computational Linguistics. URL wttp:httt://e //atts::/aclll wnt.eanaath.....o ogy..gy......................oo. org/ 2022. wwwninignneemiiiee
Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Stenberg Hansen, Angelos Filos, Ethan Brooks, Maxime Gazeau, Himanshu Sahni, Satinder Singh, and Volodymyr Mnih. In-context reinforcement learning with algorithm distillation. In Deep Reinforcement Learning Workshop NeurIPS 2022, 2022. URL https //openreview net wtw.moormmiooooooommoo iiraamiidii 9jssWJtk3WX
Yoav Levine Noam Wies, Daniel Jannai, Dan Navon, Yedid Hoshen, and Amnon Shashua. The inductive bias of in-context learning: Rethinking pretraining example design. In International Conference Learning Representations, 2022.
Id=InEaqbTJIRe
Yingcong Li, M Emrullah Iidiz, Dimitris Papailiopoulos, and Samet Oymak, Transformers as algorithms: Generalization and implicit model selection in in-context learning. arXiv preprint arXiv:2301.07667, 2023.
Xinxi Lyu, Sewon Min, Iz Beltagy, Luke Zettlemoyer, and Hannaneh Hajishirzi. Z-ICL: Zero-shot in-context learning with pseudo-demonstratiooss. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023. URL Wtl.https.... : /ttps::///peevvveeeeeee ew.
Eorum? id-pV oqkv2CH
10

---

Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11048-11064, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL https:tppp...........
ogy. wrg.02200002....... emn ammnl-pmaaa 759.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et In-context learning and induction heads. arXiv preprint arXiv: 1895, 2022.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman. Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models follow instructions with human feedback. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL petttps://openreee
net/ forum? Id=TGBAACXEON
Alec Radford, Karthik Narasimhan, Tim Salimans, Ily Sutskever, et al. Improving language understanding by generative pre-training. 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
Sivan Sabato, Nathan Srebro, and Naftali Tishby. Distribution-dependent sample complexity of large margin learning. Journal of Machine Learning Research, 14(7), 2013.
Victor Sanh, Albert Webson, Colin Raffel, Stephen Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Amaud Stiegler, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szezechla, Taewoon Kim, Gunjan Chhablani, Nihal Nayak, De- bajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj. Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Fevry, Jason Alan Fries, Ryan Teehan, Teven Le Scao, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M Rush. Multitask prompted training enables zero-shot task generalization. In International Conference on Learning Representations, 2022. URL
net. hww.://wwwwtttrrraaaaa-aa-100000
Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. A mathematical exploration of why language models help solve downstream tasks. In International Conference on Learning Representations, 2021.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11:: 1984.
Nicolas Vayatis and Robert Azencott. Distribution-dependdnt vapnik-chervonenkis bounds. In European Conference on Computational Learning Theory, pp. 230-240. Springer, 1999.
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. arXiv preprint 22X.::22/2.000000 2022.
I Lucas Weber, Jaap Jumelet, Elia Bruni, and Dieuwke Hupkes. Language modelling as a multi- task problem. In Proceedings of the 16th Conference of the European Chapter of the As- sociation for Computational Linguistics: Main Volume, pp. 2049-2006 Online, April 2021. Association for Computational Linguistics. doi: 18.18653/v https://aclanthon
leacl-mmin..11 URL
wrgg//22..accl.eccc ma1 176
Albert Webson and Ellie Pavlick. Do prompt-based models really understand the meaning of
their prompts? Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 2344, Seattle, United States, July 2022. Association for Computational Linguistics. URL. https
//aclanthology.o org/ 2022.02222 naacl main.167
11

---

Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 16158-16170, Curran Asso- neurips cc pcc/paper/2021/F1le. pdf
ciates, Inc., 2021. URL
Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V Le. Finetuned language models are zero-shot learnrr.. In International Conference on Learning Representations, 2022a.
id=qEZrGCozdqR
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large lan- guage models. Transactions on Machine Learning Research, 2022b. ISSN 2835-8856. URL Survey Certification.
net. Forum?id=yzzsu552..
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang. Denny Zhou, et al. Larger language models do in-context learning differently, arXiv preprint arXiv:2303.0388.
2023.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning implicit bayesian inference. In International Conference Learning Representations, 2022. /ett::://oeenreelee..eeeeeeee
ARRD JUMT
Kelly Zhang and Samuel Bowman. Language modeling teaches you more than translation does: Lessons learned through auxiliary syntactic task analysis. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 359-361, Brussels, Belgium, November 2018, Association for Computational Linguistics. doi: 18.13v///v/ W18-5448 /
5448
12

---

A Proof of Lemma 1
We begin by explicitly writing Po (p). Specifically, Assumption 2 assure that each in-context example @ gr + "n" " is approximately independent from the other in-context examples:
o S I Po (cx G + (\"
(8)
(p(
In addition, Assumption 3 bounds the distribution drift that caused by the artificial new line token:
P (z, @ y:) S P (z, @ y, " n\n") S P. (z, + yi) C2
Similarly, we can use Assumption again to bounds also the distribution drift that caused by potential label flipping:
(ar ( Ps (z) - yi)
(10)
where i/s denote the "corrected" label. So overall, we got that:
(c)))) & Po (r, D < (c10²)
(11)
(p())
Now, write the ratio of the prompt probabilities according to the ground-truth component and the other mixture components explicitly and get that:
Ps (p) P (p)
log (o 4k log Pa. (x, + Us)
log
(12)
C1
Intuitively, as each term in the sum is independent of the other, and equals (in expectation) to the Kullback-Leibler divergence between 6" and d:
k
Po (a + (A) P
Ep
log
= KK (IP (P) Po)
(13)
K i=1
(xt + 9:)
Equation 12 assure us that as long as the ground truth downstream task component Ø² distinguish enough from the rest of the mixture components, Pa- (p) converge zero. Formally, Assumption assure us that
(x(e)
P& (Ir e 0:) log Ps. (z, + 3c)
log C2
(14)
for any P, d. o² Hence, we can use Hoeffding's inequality (Hoeffding 1994) to estimate the deviation of this variable from its expectation (see Equation [3). More specifically, together with
Equation 12 we get that with probability of at least ô over the choice the examples in p we have that:
Po (p)
< exp (- k: (KL.
KL. (Po., 8 8log
(15)
P p- (p)
C102
(log ()666 9) (log' 7/
for l
Finally, Lemma follows by choosing that m. is the maximum
(log (16T (log" +z)
2 log 1
between k probability, and the second term term take care of the c-approximation.
and Au 8 88 log रा
r. since the first term take care of the 1
KL PP)
B Proof of Theorem 1
We begin by writing the difference labels likelihood explicitly. Specifically, by the definition of conditional probabilities we have that:
Po (vlp@ Po pppp)= E.
PD (P)
o P. (16)
Σ PD (p
13

---

Now, Assumption 2 assure us that for each component ø in the mixture the prompt p is approximately independent from the test example:
1 (p) (p
C1 P (p) Spa -
(p
(17)
91
1
(p -
Pa (p) (T)
(18)
So substituting this inequalities in Equation give us that:
(e) Po (p) En PD
c P (x - P(r
PD (p(vlp0z) - PD (ū p
(19)
(0) Po (p) P& (I)
Now, we will separate the sums in the denominator and the numerator to term that contain the mixture component @* that corresponds to DD and term that contain the other mixture components. So for clarity we will denote by A, B, C, D the different sums:
A = PD (0*)
Pa. (p)
G Po. (x (x
Po. (x + 0)
(20)
द
1 ス
B = Σ PD (6) P& (p) P.
Pp (x 1
(21)
C = Pp (6)) Po (p) Po. (z)
(22)
D = Σ (o) P6 (p) (z)
(23)
And get that:
A
B
PD
+
(24)
C C+D
C+D
Now we know that both C' and D are non-negative and hence that:
A
A
AD
A
D
<
(25)
C+D
D
C
C² DC
C
C
B
B
BD
B
D
(26)
C+D
C
C² DC
C
C
And by definition we have that:
A = (x, - (ci -
1) (v) +
1 -1
-1)
1
Po (ū ()) > A (x. - 1
+ of
(27)
C
So it is enough to show that
| < 1
A
(I, v. 7) and that
c
D
<
q.
1 in order to prove that:
3
5
B
Pp (p Po
>
2 (z. 0) + o -1
(28)
4
c
4
C
2
Starting with / by the triangle inequality have that:
B
Po (0)
Po (p)
1
(29)
PD ( Po- (p)
o Po (x)
In addition, Assumption 3 assure us that P (x)
hence conclude that:
B
PD (0)
Po (p)
1
<
(30)
PD
(0+)
P (p) Oे.
Similarly, we also have that:
D
Po (0)
Po (p) 1 P (p) og
(31)
Pd (6+
d
14

---

Now, the sum of the concepts' prior is at most one, and by Assumption 4 we have that PD (Φ*) 2 cs+ so enough to show that Po(p)
for any concept Φ # Φ¹, in order to complete the proof. Finally, Lemma assure us that under the conditions of Theorem 1, there exist m. (0, 1)² N such that if the number of in-context examples ls is least m. (ê.8), then with
A(2,119)
Pa- (p)
probability of at least 1 - å we get exactly that Pa(p)
F5- (p) < é. Importantly, m² is logarithmic in the
accuracy level ē
( and hence polynomial in T. b.o -0g
C Technical lemmas
Denote by A (x, y. V) the ground-truth margin between two label candidates y and ÿ. And also denote by Db the minimal margin between the Bayes Optimal Classifier prediction and another labels, and by (p, x. y: () the ground-truth margin between two label candidates and conditioned on the prompt p. Assuming that Ap is greater than 1 - of and given the assumptions of the following inequality holds:
Lemma 2.
Theorem 7
A (p, n. y. 5) A (v. (1 a)
(32)
1-4 A5
where = V
Proof. By Theorem I we have that A (p, V.9) is larger than (1 a)) A (x. V. 0) + - 1. Now we can substitute the definition a and get that
(p, (1 a) - (Z,
(33)
= = - a) A (0, Ap (1 - a))²
(34)
Since, U.)) is at least An we get that:
A (p, (1 a) - - a)²
(35)
And Equation 32 follow from algebraic manipulations.
15


Reviews:
[{"review_id": "XJ1lzKsNuu", "reviewer": "Reviewer_o2CM", "summary": "In-Context Learning (ICL) allows large language models (LLMs) to be easily specialized to natural language downstream tasks. When users input a concatenated string of examples of a particular downstream task, modern LLMs often perform successfully without changing their weights, providing an effective new angle to tackle multiple NLP tasks immediately without fine-tuning.\n\nThis paper defines ICL within the PAC learning framework. The authors find that pretrained LLMs learn a mixture distribution of downstream tasks (though these models maximize the likelihood of self-supervised next tokens or masked tokens on the training corpus). Under the mild assumptions, they show that ICL is provably guaranteed for LLMs to uncover the latent task, improving their performance without modifying any weights.", "questions": "There are two questions mainly for the Assumption 2 and 3.\n\n\n(Regarding the Assumption 2)\n\nIt is true that we can always find a positive c_1 that can easily bound the fraction in Equation (5) given $s_1$ and $s_2$. One concern is that users of LLM often use the newline character either trying to distinguish different shots of examples or differentiate consecutive paragraphs. \n\n-\tFor the former case, would it be better to bound min and max of the fraction provided with two different orders $(s_1, \\n, s_2)$ and $(s_2, \\n, s_1)$? This is because the order of few-shot examples actually matter for the ICL performance. \n\n-\tFor the latter case, it is difficult to say that two consecutive paragraphs would be relatively independent. It could be independent in a particular task, but not generally in most NLP tasks. For example, Coreference resolution is barely runnable without the previous paragraphs.\n\nIn addition, it seems $c_1$ is defined as a strongly uniform constant (rather than depending on the choice of $s_1$ and $s_2$, and even including any possible NLP task). Would it be too strong? All in all, $c_1$ is likely to be extremely small number, thus making the bound less practical.\n\n\n(Regarding the Assumption 3)\n\nIf the size of vocabulary is very large (typically 50k tokens), it becomes easier to find such $c_2$ (likely another uniform constant), but the $c_2$ would be very small yet requiring computational costs to handle large vocabulary. If the size of vocabulary is not large, it becomes harder to guarantee the existence of such $c_2$. Overall, $c_2$ would likely become a tiny positive number though the assumption would hold.\n\n\n(Regarding the Lemma 1)\n\nHow to justify the last line of Lemma 1, where $m_{\\hat{D}}$ can be chosen to be polynomial in both $\\log \\frac{1}{c_1 \\cdot c_2}$ and $\\frac{1}{\\Delta_{KL}}$ within the context of Equation in Line 252? If so, would be the polynomial time both lower- and upper-bounded by the $\\log \\frac{1}{c_1 \\cdot c_2}$?\n\n\n(Minor questions)\n\n-\tSection reference in Line 266 is broken.", "limitations": "No specific points are described or probed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The papers accept the crucial observations while providing theoretical guarantees. \n\n-\tEven if pre-training is assumed to be a process of learning mixture distribution of downstream tasks, it could never be equivalent to fine-tuning on a target task due to other irrelevant tasks.\n\n-\tProviding concatenation of independent examples is not natural for pretrained LLMs because they have never encountered such examples while pre-training.", "weaknesses": "While some assumptions are claimed mild for learnability context, there are other assumptions which could not be easily acceptable given the practical behaviors of LLMs. \n\n-\tTo make the provable bounds practically useful, both $c_1$ must be close to 1. However, the two strings delimited by the newline are not necessarily on paragraph levels. See the more details on the questions.\n\n-\tIf we increase the size of vocabulary, it would be easier to guarantee the existence of positive $c_2$, but there would be a computational bottleneck while $c_2$ could be still very low, making the bound less practical. See the more details on the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful feedback. \n\n### Regarding Assumption 2\nOur PAC-style guarantees are worst-case in nature and do not depend on the sampled $s_1$ and $s_2$. That being said, your suggestion is a promising direction for extending our framework to input-dependent bounds, which will elucidate the sensitivity of few-shot in-context learning to the order of the few-shot examples, as well as other input specific characteristics. We will add a discussion on this avenue for expansion in the camera read version. \n\nIn addition, your comment encouraged us to tighten the analysis in Theorem 1. We were able to relax the requirement that $4\\cdot(1-c_1^2) < \\Delta_{\\tilde{\\mathcal{D}}}$ into the weaker requirement that $1-c_{1}^2<\\Delta_{\\tilde{\\mathcal{D}}}$. Please see the updated proof below. Note that with this tighter analysis our bounds are meaningful for any $c_1>0$, and the effect of $c_1$ on the bounds is only logarithmic.\n\nFurthermore, note that our approximate independence assumptions are used merely for simplicity. In fact, the results remain valid even when we relax the approximate independence assumption to a weaker one, namely that the log-ratio of likelihoods according to different tasks is a martingale. Importantly, this weaker assumption will allow the propagation of information essential for coreference resolution, albeit at the cost of clarity. Please find below a proof sketch for Theorem 1, which relies solely on the relaxed assumption. This proof will be added to the camera-ready version.\n\n### Regarding the question about Assumption 3\nWe agree that this assumption becomes less restrictive as the vocabulary grows larger. Please note that while in practice $c_2$ may be relatively small, the effect of $c_2$ on our bounds is only logarithmic. Therefore, even a small $c_2$ will not significantly impact the bounds. \n\n### Regarding Lemma 1\nWe apologize for our mistake in line 256, it is not the correct expression, the exact form of the sample complexity in Lemma 1 is the maximum between $\\frac{\\left(\\log\\frac{1}{\\delta}\\right)\\left(16T^{2}\\right)\\left(\\log^{2}\\frac{1}{c_{2}}\\right)}{\\left(\\bigtriangleup_{\\text{KL}}\\right)^{2}}$ and $\\frac{2\\log\\frac{1}{\\epsilon}}{\\bigtriangleup_{\\text{KL}}-8\\log\\frac{1}{c_{1}c_{2}}}$  (see line 20 in the supplementary materials). As you can see, the exact form of the sample complexity in Lemma 1 does not contradict the equation on line 252, and these equations are consistent with each other.\n\n### Updated proof with the approximate independence assumption\nLet $\\alpha\\coloneqq1-\\sqrt{\\frac{1-c_{1}^{2}}{\\Delta_{\\tilde{\\mathcal{D}}}}}$. Since we assume that $\\Delta_{\\tilde{\\mathcal{D}}}>1-c_{1}^2$, it follows that $0<\\alpha \\le1$.  Importantly, Theorem 1 guarantees that $\\Delta\\left(p,x,y,\\tilde{y}\\right)>\\left(1-\\alpha\\right)\\cdot\\Delta\\left(x,y,\\tilde{y}\\right)+c_{1}^2-1$ after a minor modification. We just need to adjust the term $\\frac{\\Delta\\left(x,y,\\tilde{y}\\right)}{5\\cdot c_{!}^{-2}\\cdot c_{2}^{-T}\\cdot c_{3}^{-1}}$ in line 39 of the supplementary materials to $\\frac{\\Delta\\left(x,y,\\tilde{y}\\right)}{\\left(1-\\frac{\\alpha}{2}\\right)^{-1}\\cdot c_{!}^{-2}\\cdot c_{2}^{-T}\\cdot c_{3}^{-1}}$. \n\nNow, we can choose $\\Delta_{\\text{pretraining}}=\\frac{1}{2}\\cdot\\alpha\\cdot\\left(1-\\alpha\\right)\\epsilon$. The proof of Theorem 2 follows the same logic as the original proof, except we separate into cases based on whether the margin is at least $\\frac{2\\cdot\\Delta_{\\text{pretraining}}}{\\alpha\\cdot\\left(1-\\alpha\\right)}$. In the first case, Theorem 1 assures us that for large enough $k$ the ground truth in-context predictor also has margin $\\Delta\\left(p,x,y,\\tilde{y}\\right)$ that is greater than $\\left(1-\\alpha\\right)\\cdot\\Delta\\left(x,y,\\tilde{y}\\right)+c_{1}^{2}-1$.\nNow since $\\Delta\\left(x,y,\\tilde{y}\\right)\\ge\\Delta_{\\tilde{\\mathcal{D}}}$ and since $\\frac{1-c_{1}^{2}}{\\Delta_{\\tilde{\\mathcal{D}}}}=\\left(1-\\alpha\\right)^{2}$, we have that $\\Delta\\left(p,x,y,\\tilde{y}\\right)>\\Delta\\left(x,y,\\tilde{y}\\right)\\left(1-\\alpha\\right)\\cdot\\alpha$. From here the proof remains unchanged.\n\n### Proof sketch with the relaxed assumption\nOur goal is to find an alternative to Hoeffding's inequality in Equation 8 of the supplementary materials. To accomplish this, we will replace the approximate independence assumption with a weaker one that still enables a concentration inequality. Specifically, we will assume the following sequence of random variables forms a submartingale:\n$\\log\\frac{\\mathbb{P_{\\phi^{\\star}}}\\left(p\\right)}{\\mathbb{P_{\\phi}}\\left(p\\right)}-\\left|p\\right|\\cdot\\text{KL}\\left(\\mathbb{P_{\\phi^{\\star}}},\\mathbb{P_{\\phi}}\\right)$\nwhere $p$ is a concatenation of $n$ in-context examples. With this more relaxed assumption, we can utilize the Azuma inequality rather than Hoeffding's inequality, thus avoiding the approximate independence assumption. Importantly, this new assumption implicitly includes Assumption 3, as it handles the distribution drift caused by the artificial new line token in an implicit way, rather than the explicit treatment we currently have in Equation 2 of the supplementary materials. \n\nSo far, we have successfully adapted the proof of Lemma 1 to incorporate the relaxed assumption. To prove Theorem 1 under this relaxed assumption as well, we must quantify the efficacy of the Bayes optimal classifier that classifies inputs based on the ground truth **prompted** mixture component. For simplicity, we will assume that this classifier performs at least as well as the Bayes optimal classifier that classifies inputs according to the **unprompted** ground truth mixture component. Note that this is a natural assumption when the downstream task is a learning algorithm such as linear regression. Finally, note that with the approximate independence assumption, predictions made using the prompted ground truth mixture component can be associated with those of the unprompted ground truth mixture component, rendering this assumption unnecessary.\n"}, {"review_id": "mz3AN4XzOo", "reviewer": "Reviewer_xztc", "summary": "This paper aims to explain the learnability of in-context learning. The main idea is that the pretraining tasks learn multiple downstream tasks and the prompt specify a particular task.", "questions": "See the weakness section.", "limitations": "This is a theory paper. Societal impact is irrelevant.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses the learnability of the in-context learning. It's a hot topic and very few theories are constructed from my knowledge.\n2. The authors made several assumptions on in context learning and explain why they make the assumptions clearly. ", "weaknesses": "Though I am positive towards the paper, I think the main weakness is that the theoretical framework is too far away from the practice. The paper tells a good story but I am not sure what kind of guidance can the theory provide for the in-context learning in practice. \n\nFor example, it looks that if we provide larger number of examples in prompts, the bound may be tighter. Is this really true for in-context learning? The authors can totally claim that there is computation limitation so we cannot make the number of examples to be as large as possible in practice. But if so, we also do not need in-context learning. The authors kind of explain the mystery of in-context learning. But kind of not. If we can make the number of examples infinity, supervised learning should also work well. I think the gap here is that the authors do not explain why this kind of in-context learning is better than supervised learning.\n\nOverall, I think the contribution is interesting but not significant.\n\nMinor:\nThere are some ??'s in the paper. The authors probably want to fix them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful feedback.\n\n1. Increasing the number of in-context examples has been shown to be beneficial in practice. Evidence for this can be traced back to the GPT-3 paper [1], in which Figure 1.2 clearly demonstrates that performance improves as the number of in-context examples increases. Moreover, these observations have inspired works such as [2] to invent techniques to overcome the computational limitations of using a large number of in-context examples, their figure 1 clearly shows this improvement trend.\n\n2. Your thoughtful feedback has inspired us to prove a simple corollary of Theorem 2, establishing a case where the sample complexity of in-context learning is provably better than that of supervised learning. Specifically, the downstream tasks will involve learning parity functions over unknown subsets of input bits. To reflect that concatenating independent examples is unnatural in pre-training, the pre-training distribution will mix two distributions corresponding to the downstream parity functions. Importantly, new line tokens will usually not follow labels, and successive examples in pre-training will usually share inputs rather than be independent. The VC dimension of this hypothesis class scales linearly with the number of bits, so supervised learning's sample complexity does too. In contrast, since pre-training reduces the hypothesis class to two relevant parity functions, Theorem 2 gives a constant sample complexity regardless of the number of bits. Thus, this is effectively **few-shot** learning. In essence, the corollary shows pre-training followed by in-context learning can significantly reduce sample complexity compared to supervised learning. This demonstrated advantage is notably stronger than existing results like [3] on pre-training benefits for supervised fine-tuning. Please find below a proof sketch for this corollary.\n\n### Proof sketch for a corollary of theorem 2 on the advantage of in-context learning over supervised learning:\n\nTo utilize Theorem 2, we employ Algorithm 2 from [4] as our pretraining algorithm. Importantly, Theorem 2 from that paper provides strong formal guarantees, ensuring Assumption 1 of our paper holds. Now, since we allow successive examples in pretraining to be independent with low probability $c << 1$, successive examples are approximately independent given the new line token. Therefore, Assumption 2 also holds. Similarly, we will allow incorrect labels and spontaneous new line tokens to occur with the small probability of $c$. This ensures Assumption 3 holds. To overcome distribution drift, we repeat the parity label one hundred times. This results in the Kullback-Leibler divergence between distributions being exactly $\\frac{100}{2}\\cdot\\log\\frac{1-2c}{c}$. Consequently, for small enough $c$, the divergence is greater than $8\\cdot\\log\\frac{1}{c\\cdot\\left(1-c\\right)}$. Overall, we have satisfied all conditions for Theorem 2. Therefore, we can conclude that parity functions over unknown input bit subsets are in-context learnable, with sample complexity independent of the number of bits. Rather, the sample complexity depends only on $c$, which determines the similarity between pretraining and downstream tasks. In contrast, the VC dimension of this hypothesis class scales linearly with the number of bits. Consequently, the sample complexity of supervised learning scales linearly with the number of bits, thus completing our proof. \n\n### References:\n\n[1] Brown, Tom, et al. \"Language models are few-shot learners.\" NeurIPS 2020.\n\n[2] Ratner, Nir, et al. \"Parallel Context Windows for Large Language Models.\" ACL 2023.\n\n[3] Ge, Jiawei, et al. \"On the provable advantage of unsupervised pretraining.\" arXiv preprint arXiv:2303.01566 (2023).\n\n[4] Mahajan, Gaurav, et al. \"Learning Hidden Markov Models Using Conditional Samples.\" COLT  2023.\n"}, {"review_id": "9cE4OuPhwG", "reviewer": "Reviewer_yYWi", "summary": "This paper studies the PAC-learnability of in-context learning when the pretraining distribution is a mixture of latent tasks, and the downstream task belongs to one of them. In addition to this mixure-of-tasks assumption, the other non-trivial assumptions the authors make include: the pretrained model can approximate the pretraining distribution arbitrarily close with a polynomial number of examples, and that the adjacent strings to be concatenated are approximately independent. Based on these assumptions, the author provides sample complexity results to demonstrate in-context learnability. Particularly, the correctness of the downstream task labels does not affect the validity of the conclusions.", "questions": "Is the framework extendable to explain the observation where in-context learning can do label-sensitive linear regression?", "limitations": "The authors have not discussed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem addressed in this paper, namely theoretical understanding of in-context learning, is undoubtedly important and timely.\n* The author addresses the PAC-learnability of in-context learning, which has not been well-studied. The problem formulation and results proposed by the authors are also interesting and novel.\n* The overall presentation is clear, with clear motivations and summaries for each part (although several details need to be improved, see Weaknesses).", "weaknesses": "* The validity of the overarching mixture-of-tasks assumption for the pretraining distribution may need more justification. It appears to oversimplify the problem given the messy pretraining corpora and the novel downstream tasks used in practice (although it generalizes the similar assumption made by Xie et al. 2022, this limitation still exists).\n* The insensitivity to the correctness of in-context examples' labels may contradict recent observations. For instance, Wei et al. 2023 demonstrate that LLMs can do linear regression in in-context learning, which is clearly dependent on labels and thus cannot be directly explained by this paper.\n* There are some issues with the current presentation and writing that impede readability, such as:\n    - The input and output of function $f_\\theta$ should be made clearer. Based on the context, its input seems to be a string, but in equation (4) it has a conditional-style input which is not explained in the main text.\n    - The meaning of $x$, $o$, and $s$ should be made clearer, preferably with some examples. The Kleene star symbol should also be clarified.\n    - Typos, for instance run-away references to the appendix, Line 297 \"other another\", Line 362 \"works designed\" -> \"works are designed\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful and supportive feedback. \n\n1. We agree that pre-training data in the real world is often messy, and we will acknowledge that as a limitation in the camera-ready paper. Note that we already discussed some limitations of our work in the last paragraph of Section 5. Specifically, beyond the capability of learning new tasks, our framework also lacks a formal explanation of the connection between model size and the efficiency of in-context learning. \n\n2. Regarding the ability to perform label-sensitive linear regression, our results do not fully explain the capability of learning new tasks not included in the pre-training distribution, as acknowledged in the conclusion. However, since our results also hold under weaker approximate independence assumptions (see our response to o2CM), they cover the ability of large language models to infer latent learning algorithms like linear regression from a mixture of algorithms learned during pre-training. Importantly, when the different mixture components are learning algorithms, the labels become the dominant contributors to the Kullback-Leibler divergence between components, rendering Theorem 2 ineffective. In such cases, one could prove a similar theory relying solely on correct labels, resulting in more relaxed conditions than the conditions in line 252 ($\\Delta_{\\text{KL}}>8\\log\\frac{1}{c_{1}\\cdot c_{2}}$). We will clarify the distinction between label-sensitive and label-insensitive results in the camera-ready version. Finally, when a mixture component is a learning algorithm, it is reasonable to assume the appearance of the delimiter token after labels does not constitute a distribution drift from pre-training. Thus, together with the weaker independence assumptions, one could potentially eliminate the condition in line 252 completely. \n\n3. We apologize for the unclear notation. We will make the notation cleaner for the camera version.\n\n    *  As you correctly inferred $f_\\theta$ is a probabilistic model that gets strings as its inputs, and output the likelihood of the input string. Regarding, Equation 4, we apologize  for the abuse of notation, the intended meaning of the conditional notation is $f_{\\theta}\\left(o_{T}\\,|\\,o_{1}\\dots o_{T-1}\\right)\\coloneqq\\frac{f_{\\theta}\\left(o_{1}\\dots o_{T-1}o_{T}\\right)}{f_{\\theta}\\left(o_{1}\\dots o_{T-1}\\right)}$.\n    * The meaning of $x$ is the task inputs (see line 99). For example, “What is the name of the first president of the United States?”.\n\n    * The meaning of $o$ is a single token (see line 182). For example, “What”.\n\n    * The kenner star in $\\Sigma^{\\star}$ stands for the set of sequences over the alphabet $\\Sigma$.\n\n    * The meaning of $s$ is a string in $\\Sigma^{\\star}$  (see line 206).\n"}, {"review_id": "VUsjBzAGhc", "reviewer": "Reviewer_42uY", "summary": "The paper presents a theoretical framework for in-context learnability. The framework is grounded in the Probably Approximately Correct (PAC) learning theory and provides the first-ever finite sample complexity results for the in-context learning setup. The authors' approach involves a pretraining phase followed by an in-context learning phase where the training examples of the downstream task are concatenated in the input. The paper argues that, under specific conditions, latent tasks in the pretraining distribution can be effectively learned via in-context learning without changing the model's weights, even when the input significantly deviates from the pretraining distribution. This finding aligns with recent empirical results and suggests that in-context learning is more about task identification than learning.\n", "questions": "- What if the downstream task is OOD from the pretraining data (which is common to see in terms of the generalization ability of instruction-tuned large language models), will the assumption, and conclusion still hold in Lemma 1?\n", "limitations": "- The PAC framework employed may not cover all aspects or scenarios of in-context learning with LLMs (order, variance in prompts, chain-of-thought prompting, generalization, emergent abilities, and so on).\n- Some inconsistencies in line 266, 305 with the appendix could be improved.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is well-written and clearly presented; \n- The paper tackles an important and underexplored theoretical aspect of in-context learning in LLMs.\n- It presents the first-of-its-kind PAC-based framework for in-context learnability, which could pave the way for further theoretical investigations.\n. The paper links its theoretical analysis to recent empirical findings, providing a sound validation for its results.\n", "weaknesses": "- While the paper discusses a pretraining phase and an in-context learning phase, it doesn't clearly address how the transition between these phases is managed or optimized. Also, the instruction-tuning phase might be missing to ensure the success of in-context learning and mixture of tasks as defined in the paper; \n- Some empirical valuations including flipping labels could also be valuable to add [1, 2]; \n\n\n[1] Min, Sewon, et al. \"Metaicl: Learning to learn in context.\" arXiv preprint arXiv:2110.15943 (2021).\n\n[2] Wei, Jerry, et al. \"Symbol tuning improves in-context learning in language models.\" arXiv preprint arXiv:2305.08298 (2023).\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful and supportive feedback. \n\n1. Regarding the transition between the pretraining phase and the in-context learning phase, please note that we analyzed vanilla in-context few-shot learning as introduced in the GPT-3 paper [1], which does not have an instruction-tuning phase between the two phases. That said, our Definition 1 of in-context learning is general enough to potentially incorporate an instruction-tuning phase. Analyzing the effect of such a phase is an exciting open problem that we leave for future work.\n\n2. Regarding the ability to generalize to out-of-distribution downstream tasks, our results do not fully explain the capability of learning new tasks not included in the pre-training distribution, as acknowledged in the conclusion. However, since our results also hold under weaker approximate independence assumptions (see our response to o2CM), they cover the ability of large language models to infer latent learning algorithms like linear regression from a mixture of algorithms learned during pre-training . Importantly, inferring the right learning algorithm among already learned algorithms might provide generalization to out-of-distribution downstream tasks. Please see our answer to yYWi for more details about the ability to infer latent learning algorithms.\n\n3. Regarding variance and order variation see our first answer to o2CM.\n\n4. Regarding emergent abilities, see our answer to 86vc.\n\n[1] Brown, Tom, et al. \"Language models are few-shot learners.\" NeurIPS 2020.\n"}, {"review_id": "mWDSB1qTk7", "reviewer": "Reviewer_xPBs", "summary": "\nThis paper attempts to formalise the few-shot in-context learning phenomenon observed in large language models. To that end, they make a set of assumptions about the underlying data-generating distributions, pretrained models, etc and try to formalise the task of in-context learning in the PAC framework.\n \nThe main empirical phenomenon that is the subject of study is the ability of LLMs to predict a query input accurately after receiving a sequence of pairs of inputs and labels. Broadly, they prove that if the distributions over strings for pretraining and providing in-context examples are defined in a certain way and satisfy a set of assumptions, then for large enough k, f(y | x_1, y_1, …, x_k, y_k) will be approximately correct with high probability (in the PAC sense) where f is the language model.\n \n \nIn their framework, they assume that the target task during in-context learning is part of the pretraining distribution based on prior observations in empirical works. The hypothesis class for pretraining is a set of mixture distributions of downstream distributions. The downstream distributions can be seen as a distribution over pairs of inputs and labels. The sampling from the pretraining distribution can be decomposed into sampling a task from a prior distribution over the set of tasks and then sampling from the respective downstream distribution corresponding to the task. They assume that we have an accurate language model (in the PAC sense) where the error with the target distribution is bounded in terms of TVD of the conditional next word distribution -- based on the fact that we have LMs that are accurate in modelling the underlying distribution. Given such an accurate probabilistic LM and inputs from such distribution, they show that given a prompt, for large enough k, the error for f(y | x_1, y_1, …, x_k, y_k) with respect to the Bayes optimal predictor is less than ε with high probability.\n \n ", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n (S1) I think the formalisation is interesting to some extent, and their analysis provides some intuition as to why few-shot learning, as observed in GPT-3, works to some degree. I think the key idea is to use the fact that the ratio P_A(p) and P_B(p) converge to zero as k gets larger, where B is the target task, and A is a different task. This helps distinguish the tasks and improves the margin between the correct label and incorrect label for the LM as the size of the prompt goes larger.\n \nAnother interesting part about their framework is that they treat it as a distribution modelling task, unlike some other recent efforts to formalise in-context learning [2, 3] and derive sample complexities [1].\n \nThey have taken a more physics-like approach, where they have assumed and defined the models and data-generating distributions in a certain way based on empirical observations and tried to work out why prompts could lead to correct answers if the pretraining data was not of that form. The four assumptions are not completely unrealistic. At least within their framework, it is somewhat clear why flipping some labels is not as detrimental as one would expect.\n \n(S2)  In-context learning has been an intriguing phenomenon, with multiple works seeking to understand it. I think this paper takes a step towards that and could be useful to other researchers working in this area.\n \n(S3) The paper is well written, easy to follow, and the arguments are clearly presented.\n \n ", "weaknesses": "While the analysis and the framework are interesting, I think there are a few issues with the framework that limits its applicability in helping us understand in-context learning. \n\n(W1) The way the pretraining distribution is defined is not necessarily reflective of the real-world data. To be clear, it need not always be and depends on the nature of the theoretical work. For instance, the setup [1-3] is quite simplified, but they still allow us to train Transformers on those specific tasks and test how well the theory predicts the sample complexities in the simplified setting. In the case of this paper, the theory seems to be an attempt to directly model in-context learning in the real-world scenario, and the way the pretraining distribution is defined seems a bit detached from real-world text. \n\nAdditionally, if my understanding is correct (correct me if I am wrong), each example from the pretraining distribution seems to be an input example followed by a label from a downstream task. This seems a bit far from the way LLMs are trained as well. To some extent, it seems like the pretraining and downstream distributions are designed to satisfy some properties favourable for the end result but not necessarily reflective of the real data. I understand that it is not possible to precisely define real-world data, but given the goal of the paper, it seems like the value of results does depend on how well the data-generating distribution reflects real-world data. \n\n(W2) It seems like the sample complexities are not necessarily predictive of the number of few-shot examples needed for in-context learning. I think it stems from the way the framework is defined and the disconnect with practice. Standard learning theoretic frameworks such as PAC models are entirely formal abstractions and do not contain assumptions about the real world (apart from train and test being the same distribution) -- hence allowing worst-case sample complexities to be meaningful. It also allows us to analyse new algorithms and learning problems. In this scenario, however, it is difficult to see how this framework can be used to analyse the problem or new algorithms further. The framework used in [1] is simplified but is still within a setting where models can be trained and tested to evaluate how well the sample complexities reflect the true performance within the simplified setting. \n\n[1] Transformers as Algorithms: Generalization and Stability in In-context Learning  \n[2] What Can Transformers Learn In-Context? A Case Study of Simple Function Classes  \n[3] Transformers Learn In-Context by Gradient Descent. 2022  \n\n------------------------------------------- \nTypos:  \nL266: Section ??   \nL270: That it -> That is  \nL305: Section ??  \n\nI have given a score of 6 for now, but I am open to changing my score based on the authors' responses and discussions with other reviewers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful and supportive feedback. \n\n1. We agree that in real world data there is an additional distribution shift which is caused by the fact that tasks in the pre-training mixture distribution usually use more soft labels and more flexible input formats. That being said, to the best of our knowledge the analyzed data distribution is still the most realistic one that has been analyzed so far. For example, the analyzed setting includes as a special case the mixture of HMMs that is analyzed in [2]. Moreover, note that the underlying mechanism behind our results is Lemma 1, which can be modified easily for other input formats. Hence, one needs to assume that input examples are followed by a label from downstream tasks, only for bounding the zero-one loss, but soft in-context learning as defined in [1] is guaranteed also with soft inputs formats.\n\n2. Furthermore, our framework allows for an empirical evaluation of how accurately the sample complexities reflect true performance within the rather realistic simplified setting. In particular, since the analyzed setting includes as a special case the mixture of HMMs examined in [2], we can apply our bound to the GINC simulations they conducted in Section 4 of their paper, as shown in the attached figure our bounds correlate well with the trends of real world in-context learning performance, even though they deviate significantly from the exact accuracies. Notably, the analysis in [2] is only asymptotic and does not provide finite sample complexity guarantees. Additionally, our theoretical definitions permit analyzing novel in-context learning algorithms such as CSCGs [3].\n\n#### Details regarding our guarantees for the GINC dataset\n\nThe estimation of the KL divergence between the different HMM components significantly influence our bounds and is somewhat unreliable, since the GINC dataset from [2] violates their Assumption 5 and assign zeros probabilities to some strings. To overcome this issue, we cliped the lowest probabilities to $10^{-32}$, and during the Monte Carlo estimation of the KL divergence we omitted samples that violate this lower bound. As a result, we estimate that the KL divergence between the different components to be approximately $15$ and substitute this value into our bounds. For reproducibility, we provide an implementation of our bounds below.\n\n```python\ndef our_bound(kl = 15., delta = .99, lowest_prob=1e-32, task_length=5, mixture_size=5):\n    accuracy = np.linspace(1, 99.9, 100)\n    epsilon = 1 - (accuracy / 100)\n    a = -16 * np.log(delta) * (np.log(lowest_prob) ** 2) / (kl ** 2)\n    b = -2 * np.log(2 * epsilon / mixture_size) / (kl + (np.log(lowest_prob) / task_length))\n    return np.maximum(a, b), accuracy\n```\n\n### References:\n\n[1] Olsson, Catherine, et al. \"In-context learning and induction heads.\" arXiv preprint arXiv:2209.11895 (2022).\n\n[2] Xie, Sang Michael, et al.  “An explanation of in-context 541 learning as implicit Bayesian inference.” ICLR 2022.\n\n[3] Swaminathan, Sivaramakrishnan, et al. \"Schema-learning and rebinding as mechanisms of in-context learning and emergence.\" arXiv preprint arXiv:2307.01201 (2023).‏\n"}, {"review_id": "sPMINER3uA", "reviewer": "Reviewer_86vc", "summary": "The authors propose a PAC framework to analyze the expressiveness power of in-context learning in a finite sample complexity scheme. The framework consists of largely two parts, first is the initial pretraining of the next token prediction phase, and the second is the in-context learning phase. Regarding the pertaining data distribution as a mixture of latent tasks. authors provide an understanding that polynomial sample complexity guarantees in-context learnability.", "questions": "- In line 143, the authors say they aim to provide an analysis of in-context learnability of “large model”. With the specified sample complexity, what is the guideline for that “large model”?", "limitations": "- Lack of experimental evidence to support the theory (at least experiments on synthetic data would be helpful)", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Define a PAC framework to investigate in-context learning\n- Reduce the sample complexity needed for in-context learning to polynomial complexity, which is confined to infinite samples in previous work", "weaknesses": "- The number of the model parameter is also a crucial factor for in-context learning, but it seems that there is not enough handling for model complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful and supportive feedback. \n\n1. Regarding the model size, intuitively the learning algorithms in Assumption 1 is a large language model that fits the pre-training distribution well enough. By assuming a scaling law behavior with respect to the model size, one might get an emergent phenomenon in which the capability of recognizing certain downstream tasks with in-context learning is emergent from a certain model size which depends on the margin of the downstream task. We will add a discussion on this avenue for expansion in the camera read version. \n\n2. Following your request, we promptly conducted an experiment to support our theory. In particular, the analyzed setting includes as a special case the mixture of HMMs examined in [1]. Therefore, the GINC simulations already conducted in Section 4 of their paper lend support to our theory. Moreover, as shown in the attached figure, our PAC bounds provide finite sample complexity, unlike the asymptotic analysis in [2]. We were thus able to apply these bounds to the GINC dataset. This demonstrates that the analyzed framework predicts the in-context capabilities of pre-trained LLMs. \n\n3. Regarding guidelines for large language models (LLMs), our analysis reveals that the accuracy of in-context learning for large language models (LLMs) is determined by three key factors. First, the ability to recognize relevant tasks among those learned during pretraining. Second, the ability to overcome distribution drift caused by the unnatural concatenation of in-context examples. And third, the performance of the LLM once it identifies the right task. Importantly, our bounds suggest that as the number of in-context examples increases, improvements from the first two factors plateau (Theorem 1). Thus, for further gains, one must utilize a better pretrained LLM (Theorem 2 proof). We will discuss these implications of our theorems in more detail in the camera-ready version. \n\n[1] Xie, Sang Michael, et al.  “An explanation of in-context 541 learning as implicit Bayesian inference.” ICLR 2022.\n"}]

Author rebuttal:
We thank all the reviewers for their thoughtful feedback. We apologize for the broken links to the appendix. The link in line 266 should point to section 1 in the appendix, while the link in line 305 should point to section 2 in the appendix.

Meta-review: This paper proposes a theoretical framework for understanding in-context learning through the lens of PAC-learning. Under the assumption that the pre-training distribution contains a mixture of latent tasks, the authors derive a polynomial sample-complexity bound for learning to perform these tasks in-context.

The consensus is quite positive on this paper, and all of the reviewers agree that this is a useful contribution to understanding in-context learning. The overarching theme in the concerns is that the theory relies on assumptions which may not always reflect the practice. 

However, the positive outweigh the negative, especially given that the authors acknowledge these limitations in the paper. I recommend acceptance.
Decision: Accept (poster)