Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The submission studies the phenomenon of the "in-context learning" behavior of large language models (LLMs). Two results are presented: First, the submission argues that in-context learning can be formalized as Bayesian inference in a mixture of Hidden Markov Models (HMMs). Second, the submission introduces small-scale settings in which the in-context learning behavior of LLMs is reproduced empirically.
main_review: ### Main Review

#### Strengths

1. Significance: The paper studies a timely question: Why does in-context learning (in particular in LLMs) take place? The small-scale reproduction and theoretical model of this phenomenon may lead to new understanding.

2. Novel empirical phenomenon: The existence proof of in-context learning in small-scale models is new and surprising, to my knowledge.

#### Weaknesses

1. I am not sure of the novelty of the theoretical results. The theoretical model considered in the paper seems to be a mixture Hidden Markov Model (HMM). Helske & Helske (2019) demonstrate that such a model can be expressed as a standard HMM, for which inference is known to be possible and moreover efficient. Given this, it is not clear to me what Theorem 1 adds, which shows that the "in-context predictor" (ie. Bayes) infers the latent mixture variable. Theorems 2 & 3 seem novel to my knowledge, as they tie this inference to the expected 0-1 loss, but further clarification on the significance of these results would be helpful to understand the contribution.

1. Broadly, I think the paper should more clearly distinguish ideal performance (ie. Bayes) from models picked out by their behavior (eg. "in-context predictor," Transformer, LSTM) from datasets (ie. pretraining distribution, downstream task). As examples:
    - In Theorem 1, 2, & 3, Bayes is shown to recover latent variables and make accurate predictions in the mixture HMM; i.e., these theorems describe ideal performance. However, in some cases, this ideal performer is described an "in-context predictor" ("....we have that the in-context predictor infers prompt concept..."). Elsewhere in the paper, "in-context predictor" is used to describe a behavior (ie. learning a task from a small context). Using "in-context predictor" widely in this way is problematic, because stating that the ideal model is an in-context predictor is circular with respect to the claim that in-context predictors can be modeled as a Bayesian ideal (which is one of the central claims of the paper).
    - In Section 4, the pretraining distribution is modelled as a mixture HMM, and data generated from this model is used as training data for scaled-down versions of LLMs . This is a distinct use of the mixture HMM formalism (ie. as a data-generating process) from its use to derive the ideal performance described in Theorems 1-3. This distinction could be made clearer in the paper.

1. The results in Section 4 are claimed to demonstrate that in-context learning is taking place in this small-scale setup. However, if in-context learning just refers to improvement in the number of test examples (ie. the behavioral definition), then these results are quite distinct from the theoretical results. Can the asymptotic performance also be plotted to demonstrate that empirical performance approaches the ideal performance described in Section 3? This would more closely tie the "in-context" phenomenon to the theoretical model.

1. The paper should more clearly discuss scope & limitations, and, in particular, which assumptions in the theoretical results and data model may not match reality. For example, the topic-model/mixture assumption; the enumerable token set; the assumption that the "language model fits this pretraining distribution exactly with enough data and expressivity."

1. The paper is a little light on take-aways for LLMs. It has reproduced the in-context learning phenomenon in smaller models, but there lacks a strong connection to argue that the same mechanisms are at play for larger-scale models.

### Minor comments

#### Minor, specific sections:

- Intro & Figure 1: I think the example in the introduction is better served in the caption of Figure 1, and the introduction should describe just the abstract problem and reference Figure 1.
- "Thus, in-context learning can be thought of as implicit Bayesian inference." I think this should be more explicitly explained as "we model in-context learning as Bayesian inference with this particular HMM."
- "Ideally, the posterior predictive distribution should concentrate" Is this referencing prior result? Or an assumption that would be beneficial for the framework? Explain further.
- "During in-context learning, the prompt is presented as a contiguous sequence rather than IID examples and are thus “out-of-distribution” to the language model." I'm not sure I follow why this fact makes the test prompt OoD.
- "The canonical asymptotic tool in Bayesian methods..." The reason for introducing this should be much more elaborated. What is the purpose of looking for a "tool" like this? What does the tool do?
- "We take the prompt concept $\theta^*$ to be unique in this paper to simplify the notation of the prompt distribution $p_\text{prompt}$." I'm not sure why this would be just to "simplify the notation;" is it not in place to ensure that the test prompt does not occur in the pre-training set? Perhaps "unique" is unclear.
- "The target distribution differs from the pretraining distribution p on the distribution of $h_\text{start}^\text{test}$." And not $\theta^*$ as well?
- In Eq. (4), $p_\text{prompt}$ is overloaded---it represents the joint, whereas before, it represented only the conditional. 

#### Minor, general comments:
- The paper should discuss work on overparameterization (e.g., Zhang et al. (2017)) and overtraining (e.g., Power et al. (2021)), which do not change the train error significantly but do affect downstream performance. These lines of work are relevant to the observation that "the inductive bias of scale may improve in-context learning beyond memorizing the training data better."

### References

Helske S, Helske J (2019). “Mixture Hidden Markov Models for Sequence Data: The seqHMM Package in R.” Journal of Statistical Software, 88(3), 1–32. doi:10.18637/jss.v088.i03

Power, Alethea, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. "Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets." In ICLR MATH-AI Workshop. 2021.

Zhang, Chiyuan, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. "Understanding deep learning requires rethinking generalization (2016)." arXiv preprint arXiv:1611.03530 (2017).
summary_of_the_review: The question (S1) is highly relevant, and I think the small-scale reproduction (S2) could be meaningful. However, the implications of what is shown in the paper for LLMs is not sufficiently clear (W5), so the significance of the work in answering the question (S1) is not clear. The paper also has a few other weaknesses that prevent me from recommending acceptance in its current form (W1-4).

### Update after discussion

Thanks to the authors for their detailed response. My concerns have been largely addressed and I appreciate the greater empirical connection to LLMs via the additional experiments; I have updated my score to reflect this. I do have recommendations to the authors to increase the clarity of the paper, which I do think should be improved for the next revision:

- I agree with Reviewer BHn6 that the title overclaims and does not reflect the contributions of the paper. The current version is suggestive of something like "An Explanation of In-context Learning [in Large Language Models like GPT-3] as Implicit Bayesian Inference," which is *not* the contribution of the paper, because the paper explains in-context learning in a simplified theoretical model, and provides some  empirical evidence that this captures important aspects of the same in LLMs, but does not strictly "explain" the same in LLMs.
- Related to the above, everywhere in the text where the term "language model" is used should have greater precision on the distinction between the idealized setting and the practical setting, because this term is used interchangeably for both the theoretical model and a large language model. 
- I find the terms "in-context predictor" (theoretical notion) and "in-context learning" (behavioral notion) confusable. It would be worth writing "*ideal* in-context predictor" and "*behavior of* in-context learning" to make this less so.
-  OOD = low probability is an imprecise notion and one that does not seem to be connected to how the structure of the prompts is used in the analysis. I think the authors can improve on this point by clarifying what they mean by "we can no longer factorize the examples under the pretraining distribution."
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the question of why few-shot prompting works for large language models (LM) such as GPT? The paper is mainly focused on understanding why prompting works given that concatenating multiple examples separated by a delimiter introduces out-of-distribution prompts that the LM would most likely not have seen during its pre-training. The paper shows that when the pre-training distribution is a mixture of HMMs, prompting works as a result of Bayesian inference. The authors show the validity of their theoretical results by training transformers and LSTM on synthetic datasets sampled from some HMMs that they devised.
main_review: I think the paper does a good job in explaining why concatenating independent examples as a sequence and prompting a LM trained on HMMs gives good results, considering the prompt sequence can be OOD. I have some questions about practicality of the approach and the observation generation process for the prompting.

1- I think there is a significant gap between simulated experiments and real sequential data. Showing that the theory holds for the simulated data as the initial step is useful, but HMMs are far from capturing real data and results with existing LMs would be needed to understand the gap. For example, GPT-3 zero-shot results are actually better than GPT-3 one-shot results on LAMBADA and HelloSwag datasets (Table 3.2) [1] and few-shot results are also lower for smaller networks (Figure 3.2). 

- There is an additional result in the appendix related to GPT-3 but it is not clear if using longer examples gives better results or because the overall prompt sequence is longer. Can you also present results where you use more short examples that gives the same prompt length as that of longer examples (such as using 10 short vs 5 long examples)?

- GPT-3 uses an additional task description, which would be similar to the concept in your paper, could you explain how this can be incorporated?

2- The example sequence (O_i) is generated using the same pre-trained language model. In this case, OODness of the prompt sequence only comes from the fact that examples are concatenated. I think having prompt distribution not necessarily sharing the same pre-training data distribution could be important.
- Could you train an additional language model on your corpus and generate prompt observations from that?


3- How sensitive is your results to different orders of the same set of examples?

[1] Language Models are Few-Shot Learners. OpenAI.

summary_of_the_review: I think the theory behind the paper is really interesting to understand in what conditions few-shot prompting might work. I also think that there needs to be more experiments with real data to understand the gap between their simulated experiments and real language.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose to study the phenomenon of "in-context learning" through the lens of Bayesian prediction. They introduce a framework in which the data generating distribution is given as a mixture of HMMs parameterized by a latent "concept," and they show that under suitable conditions the posterior predictive distribution over a completion given a structured prompt asymptotically selects the "concept" behind this particular structure. They illustrate this framework and reproduce the phenomenon in a simplified language modeling example.
main_review: This paper proposes and analyzes a framework under which "in-context learning" can be studied from a statistical perspective. Despite the potential limitations of the framework and assumptions, this is an original perspective that allows for theoretical investigation of a complex empirical phenomenon. My main comments are focused on three topics:

1. It would be useful for the authors to give a more robust account of why we need a specific account of "in-context learning" in the first place. Put differently, why should we not just consider these examples to be relatively straightforward cases of next-word prediction for a model that has learned an accurate approximation to the distribution over sequences of words? In the first paragraph of $\S$1, the authors write, "Given that the distribution of prompts are quite different from real text..." - but is this really true, particularly given the enormous breadth of modern training corpuses? The prompt that precedes the quote seems reasonably close to natural (if somewhat simple) language in this case, certainly enough for a reader to reasonably ask whether there is anything particularly special here that needs explaining. How do we distinguish between "recognition and continuation of a specific concept / pattern / construction" and just "good next-word prediction conditioned on a relatively plausible sequence?"

2. The overall strategy of the analysis is clear, particularly the high-level walkthrough that precedes the theorem statements and proofs. It is also clear that the analysis depends at several points on specific, technical aspects of the problem formalization, including the mixture-of-HMMs model for the pretraining distribution (Eq. 5) and the specific structure of the HMM transitions around delimiter tokens (Eqs. 9-10). The paper could be improved by some discussion of these assumptions. In particular, what is critical to this framework, and what is required merely for technical purposes in some proofs? Why does the mixture-of-HMMs model seem to be the right choice for this analysis?

3. The experiments are carefully documented and results include estimates of uncertainty where appropriate. The prediction performance as a function of $n$ and $k$ generally supports the theoretical results, and the ablations indicate the importance of the specific mixture-of-HMMs structure of the pretraining distribution for this task. However, some aspects of the experimental approach could use more discussion. One main question is: how does this toy setting help us understand the emergence of "in-context learning" in models trained on vast corpuses whose contents are very unlikely to be well-modeled by a mixture of HMMs corresponding to well-separated "concepts?" We see that this phenomenon disappears when the LSTM and transformer models are trained on "random" data, but the real-world data on which language models are trained clearly lives between these extremes of rigid concept structure and meaningless sequences. Some lower-level questions: Does the theory explain why performance seems to be relatively more sensitive to $k$ than $n$? Why do we observe "in-context learning" in these relatively small LSTM and transformer models, when previously it was observed that even models as large as GPT-2 fail to demonstrate this phenomenon? 

Other comments:
- The first sentence of $\S$3, particularly "... conditioning the pretraining distribution on the prompt infers the prompt concept to enable in-context learning..." is unclear.
- What are $c_1$ and $c_2$ in Eq. (13)? What is $k$ in Eq. (14)?
- To avoid ambiguity, I'd suggest using some other symbol for the footnote in Thm. 2. 
- Typo in first paragraph of $\S$1: "Intuigingly"
summary_of_the_review: This paper contributes a framework for theoretical exposition of a complex empirical behavior observed in language models. This framework and its results offer useful insights, and these are corroborated by a clear set of experiments. There remain some questions as to the motivation for "in-context learning" as a specific phenomenon of interest, the potential limitations of some assumptions that seem critical to the proofs, and the gap between the toy setting and "in-context learning' as it arises in large language models. In my view the strengths outweigh the weaknesses, and my score could potentially be improved with some further discussion of the points above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper attempts to bring clarification to In-Context Learning (ICL) by relating it to Bayesian Learning over mixtures of HMMs. Each component of the mixture generates examples of facts of the same conceptual type, such as "Albert Einstein was German", "Marie Curie was Polish", etc (here the conceptual type is "nationality"). The first part of the paper addresses a theoretical question, namely whether the mixture model, on being given a prompt, that is, a prefix such as "Albert Einstein was German. Marie Curie was Polish. Isaac Newton was ", is able to implicitly identify the relevant component of the mixture (i.e. "nationality"), and consequently, whether it is able to correctly complete the prompt, here with "British".
The second part of the paper consists in simulations, where the mixture model is used to produce data on which a neural language model (LSTM or Transformer) is trained, and on evaluations of how well the neural LM is able to perform the completions, under different configurations and ablations.
main_review: __Strengths__: The main strength of the paper is in the connection (and differences) it raises between the ability of ICL to exploit prompts consisting of a sequence of examples of the same type and the Bernstein-Von Mises theorem in Bayesian theory that characterizes the convergence of the posterior to the true underlying parameter, given enough examples.

__Weaknesses__: While the paper goes into mathematical technicalities about certain formal details, it does not explain clearly certain high-level, core, aspects of the approach, which make it difficult for the reader to really understand what is actually claimed. My first question below raises this point in more detail. 

__Questions__:

* It is crucial for the reader to clearly understand how the "pretraining distribution" is actually constructed. Although I could not find it detailed in the paper (and actually found some statements that seemed to contradict each other, see below), my understanding is that, after a concept $\theta$ is drawn, a __sequence__ of examples of the concept is produced, separated by a special symbol. The total number of symbols produced is $T$ (is this correct?), a parameter which is not detailed. If this interpretation is correct, am I right to assume that it means that the pretraining distribution, for a given $\theta$, generates essentially the same sequences as the "prompt distribution" for that $\theta$ ?

	* Note: Another interpretation, slightly different from the one I just wrote, would also seem to be supported by the paper, namely that while the pretrained distribution is not _exactly_ the same as the prompt distribution, it does ensure that sequences of examples are generated in almost the same way, but I think the nuance is subtle.

    Assuming my interpretation is correct, the formal part of the paper essentially says that, (under some technical conditions), if we let the pretraining distribution generate a long sequence of examples (but without disclosing which concept $\theta^*$ was employed), and then rerun the (full) pretraining distribution conditionally from that prefix, then the next example generated will tend to be an example "associated" with $\theta^*$.
	
    If this is the main observation that the paper makes, it should be stated more openly, even if there is a danger that some readers may dismiss it as a bit "obvious" (which it is not really at the formal level).

    * Concerning statements that look to go in different directions relative to this point: the caption in Fig. 1 says "... and are thus 'out of distribution' ", but the example in Fig. 2 seems to concatenate several examples. The paragraph after assumption 3 on p. 4 says: "the prompt is still out of distribution", while the next "regularity" assumption seems to be there to avoid such a possibility... 
	* Related to these points, a clearer description of the way the GINC dataset is produced, in terms of whether and how it produces sequences of examples, would be very welcome. Also, the definition of the GINC should be related to the formal assumptions in section 2.1, which it is not.

* Other questions:

    * Please explain why you need a special treatment for the first symbol of each example in the description of the prompt distribution in the first half of p. 3. Is this related with the different color used for "Albert" and "Einstein" in Figure 1 ?
	* In your simulations, the fact that neural LMs such as LSTMs or Transformers are able to recover the completion of examples should be sufficiently explained by their ability to well approximate the pretraining distribution underlying the GINC dataset, without having to invoke additional ICL abilities. However, your experiments indicate that their ability to do completions goes beyond their ability to approximate the underlying distribution. Do you think your theory could be extended to explain that phenomenon, or is it orthogonal to it?

__Comment on the title of the paper__: as a last comment, I feel that the title, claiming to provide an _Explanation_ of iCL in terms of Bayesian learning, exaggerates the current contribution. A true explanation would require to go into how _the hidden states of a pretrained Transformer model_ focus more and more onto a characterization of the task being illustrated by the sequence of examples in the prompt (and typically do so based on only a few examples) and are often able to solve that task even if these examples appear to be remotely related to the training distribution. This is not what the paper does, so I think the title could be reformulated in a more cautious way.
summary_of_the_review: The paper raises interesting connections between Bayesian learning and certain aspects of in-context learning, based on a simplified formal model exploiting mixtures of HMMs. While the formal developments are extensive, the take-home message is somewhat obscured in the description, making it difficult to assess the true impact of the paper.


*After reading authors' responses*: Thank you for your detailed answers and for the clarifications in the paper. I am not fully convinced by the large significance you put on the OOD nature of the prompts relative to the pretrained distribution --- technically true, but in a narrow and not very illuminating sense IMO ---, and still think your title is an exaggeration. However, I feel that your paper deserves to be discussed by the community and therefore I am raising my score, leaning towards acceptance.
review_title: null

Meta-review: This submission introduces a theoretical model to explain how "in-context learning" (i.e. the ability to output a correct prediction based on inputs for a task that the model was not explicitly trained on) is possible. The model uses a mixture of HMMs and shows that in-context learning is a natural consequence of Bayesian inference under that model. Overall, reviewers agreed that the contribution was useful and timely, and were somewhat convinced by the theoretical arguments. However, there was some broad concern with the framing of the paper. Namely,
1) The paper claims that prompted data is OOD w.r.t. the pre-training distribution. In fact, this is almost certainly not the case for many tasks and datasets. Indeed, it is highly plausible that data very similar to the example given by the paper (identifying the nationality of different celebrities) appears in the pre-training dataset of large LMs. Other examples include the popular "tldr;" task format for summarization which is incredibly common on the internet, etc.
2) The paper does not sufficiently distinguish between insights gained in the toy setting considered by the theoretical model and insights that can be applied to large LMs. Most reviewers were concerned that there might not be any reason to think that the insights gained from the theoretical model would apply to large LMs. The paper, however, very much frames itself as developing insight into the behavior of large LMs.

I will recommend acceptance of this paper, but will stipulate that the above two issues should be fixed in the camera-ready version. Namely, I would suggest that the authors do not refer to prompted forms of tasks/datasets as "OOD", and I would suggest that any claims about different insights are not applied to large LMs.
Decision: Accept (Poster)