What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization

We thank the reviewer for the careful reading and the valuable feedback. We address the major concerns in the following.

Added Experimental Results

We conduct five experiments to verify our theoretical findings, including the Bayesian view (Proposition 4.1 and Eqn. (4.7)), the regret upper-bounded in Corollary 4.2 and Theorem 6.2, and the constant ratio between $\mathtt{attn}_{\dagger}$ and $\mathtt{attn}$ in Proposition 4.3. The results and implementation details are provided in Appendix C and D in the revised manuscript. We will list a part of numerical results as table below.

• Verification of the Bayesian View

Table 1:

To verify the Bayesian view that we adopt in the paper, we implemented two experiments. In the first experiment, we explicitly construct the hidden concept vectors that are found by LLMs. Motivated by (4.7) and Proposition 4.3, we construct the hidden concept vector as the average sum over prompts of the values of twenty selected attention heads, i.e., we compress the hidden concept into a vector with dimension $4096$. To demonstrate the effectiveness of the constructed hidden concepts, we add these hidden concept vectors at a layer of LLMs when the model resolves the prompt with zero-shot. In Table 1, "zs-hc" refers to the results of LLMs that infers with learned hidden concept vectors and zero-shot prompt, and "ICL-$i$" refers to the results of LLMs prompted with $i$ examples. This table report the accuracy of LLMs under different prompts. We consider the tasks of finding antonyms, finding the capitals of countries, and finding the past tense of words. The results indicate that the LLMs with learned hidden concept vectors have comparable performance with the LLMs prompted with several examples. This indicates that the learned hidden concept vectors are indeed efficient compression of the hidden concepts, which proves that LLMs deduce hidden concepts for ICL. This result strongly corroborates with (4.7).

Table 2:

In the second experiment, we aim to verify that LLMs implement inference with the Bayesian framework, not with gradient descent [1,2,3] on some tasks. We prompt the LLMs with the history data of a set of similar multi-armed bandit instances with $100$ arms, and let LLMs indicate which arm to pull in a similar new bandit instance. In these similar bandit instances, there is an informative arm, whose reward is exactly the index of the arm with the highest rewards. We also provide the side information that "Some arm may directly tell you the arm with the highest reward, even itself does not have the highest reward". In each example provided in the prompt, there are the rewards of six arms, including the informative arm and the best arm, in one bandit instance. As shown in Table 2, the LLMs can efficiently implement ICL even with only $6$ examples. We note that the gradient descent algorithms in the previous works cannot explain this performance, since the gradient descent algorithms need at least $100$ data points, where each data point is the reward of one arm, to learn. In contrast, the Bayesian view can clearly explain Table 2, where LLMs make use of the side information to calculate a better posterior for the bandit instance. Thus, LLMs have good ICL performance in this setting.

• Verification of the Regret Bound

Table 3:

To verify Corollary 4.2 and Theorem 6.2, we implement experiments to evaluate the regret in two settings. In the first setting, the LLMs is trained for the linear regression task from scratch, which is a representative setting studied in [1,4]. The examples in the prompt are $\lbrace(x _i,y _i)\rbrace _{i=1}^{N}$, where $x _i\in\mathbb{R}^d$, $d=20$ and $y _{i}=w^{T}x _{i}$ for some $w$ sampled from Gaussian distribution. Given the Gaussian model, we adopt the squared error to approximate the logarithm of the probability. Then the $t\times \text{regret}$ of the LLMs can be well approximated by the sum of the squared error till time $t$.

Explanations of Details in the proof of Proposition 5.4

We would like to provide detailed calculations for the exponential decaying error on $D$, and we have modified the revised manuscript accordingly. The main idea is that: (1) the later modules will amplify the approximation error in the previous modules (2) we will balance the depths of different modules to handle the amplification.

• For the problems regarding Step 2:

Lemma I.9 indicates the approximation error $\varepsilon$ of a fully-connected network will depth $D$ can be upper bounded as

$

\varepsilon\leq \exp\bigg(-\sqrt{\frac{D-\log B}{B}}\bigg).

$

We denote the depth of $\Psi _{\phi^\ast}$ and $\Psi _{\rho^\ast}$ as $D^\prime$ and $D^{\prime\prime}$, respectively. Then the total approximation error is

$

\text{approx err}&\leq d _y \exp\bigg(-\sqrt{\frac{D^{\prime\prime}-\log B}{B}}\bigg) +d _y B _{A,1}^{D^{\prime\prime}}\exp\bigg(-\sqrt{\frac{D^{\prime}-\log B}{B}}\bigg)\\

$

where the inequality follows from the triangle inequality in our manuscript, $B _{A,1}^{D^{\prime\prime}}$ comes from the fact that the later modules will amplify the error in the previous modules in transformers, and $B _{A,1}$ is the lipschitz constant for each layer.

Fact: For any $l>0,c>0$, we have $\exp(-l\sqrt{x-c})=O(\exp(-l\sqrt{x}))$.

Proof: Basic calculations shows that $\exp(-l\sqrt{x-c})\leq m\exp(-l\sqrt{x})$ for any $m>3$ is equivalent to

$

\frac{l\cdot c}{\sqrt{x}+\sqrt{x-c}}\leq \log m.

$

This trivially holds when $x$ is large.

Thus, we have that

$

\text{approx err}=O\bigg( d _y \exp\bigg(-\sqrt{\frac{D^{\prime\prime}}{B}}\bigg) +d _y \exp\bigg(\frac{1}{\sqrt{B}}\big[D^{\prime\prime}\sqrt{B}\log B _{A,1} -\sqrt{D^{\prime}}\big]\bigg)\bigg).

$

To handle the second term in the right-hand side of this inequality, we require that

$

k\cdot D^{\prime\prime}-\sqrt{D^{\prime}}\leq -\sqrt{D^{\prime\prime}},

$

where $k= \sqrt{B}\log B _{A,1}$. This is equivalent to

$

D^{\prime}\geq (k\cdot D^{\prime\prime}+\sqrt{D^{\prime\prime}})^2.

$

Since $D^{\prime}+D^{\prime\prime}\leq D$, where $D$ is the depth of the whole network, we can set

$

D^{\prime\prime}=\sqrt{D}/(2\sqrt{B}\log B _{A,1}),\quad D^{\prime}=D-1-D^{\prime\prime}\geq D/2+D^{3/4}

$

when $D$ is large ($C=4$ in our original manuscript). This assignments ensure that $D^{\prime}\geq (k\cdot D^{\prime\prime}+\sqrt{D^{\prime\prime}})^2$. Thus, we have that

$

\text{approx err}=O\bigg( d _y \exp\bigg(-\sqrt{\frac{D^{\prime\prime}}{B}}\bigg)\bigg)=O\bigg(d _{y}\exp\bigg(-\frac{D^{1/4}}{\sqrt{C^{2}B^{2}\log B _ {A,1}}}\bigg)\bigg)

$

for some constant $C>0$. Here we relax the dependency on $B$ a little for the notational clearness, and the relaxation results from the fact that $B\geq 1$ usually.

• For the problem regarding Step 3:

We note that the TV bound is exactly the $l_1$-norm, whose upper bound is derived in Step 2.

We thank the reviewer again for reading our response. We appreciate it if the reviewer could consider raising the score, if our rebuttal has addressed your concerns.

Reference

[1] Akyürek E, Schuurmans D, Andreas J, et al. What learning algorithm is in-context learning? investigations with linear models[J]. arXiv preprint arXiv:2211.15661, 2022.

[2] Von Oswald J, Niklasson E, Randazzo E, et al. Transformers learn in-context by gradient descent[C]//International Conference on Machine Learning. PMLR, 2023: 35151-35174.

[3] Bai Y, Chen F, Wang H, et al. Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection[J]. arXiv preprint arXiv:2306.04637, 2023.

[4] Garg S, Tsipras D, Liang P S, et al. What can transformers learn in-context? a case study of simple function classes[J]. Advances in Neural Information Processing Systems, 2022, 35: 30583-30598.

[5] Gruver N, Finzi M, Qiu S, et al. Large language models are zero-shot time series forecasters[J]. arXiv preprint arXiv:2310.07820, 2023.

[6] Zaheer M, Kottur S, Ravanbakhsh S, et al. Deep sets[J]. Advances in neural information processing systems, 2017, 30.

[7] Wang X, Zhu W, Wang W Y. Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning[J]. arXiv preprint arXiv:2301.11916, 2023.

[8] Jiang H. A latent space theory for emergent abilities in large language models[J]. arXiv preprint arXiv:2304.09960, 2023.

Explanations of The Proof of Proposition 4.1

We thank the reviewer for the suggestions and modified the revised version accordingly. We provide detailed calculations of the first and the third equality here.

• For the first equality, we have

$

\mathbb{P}(r _{t+1}| \text{pt} _t) &= \int \mathbb{P}(r _{t+1}| h _{t+1},\text{pt} _t) \mathbb{P}(h _{t+1}| \text{pt} _t)\mathrm{d}h _{t+1} \ &= \int \mathbb{P}(r _{t+1}| h _{t+1},\tilde{c} _{t+1}) \mathbb{P}(h _{t+1},|, S _t)\mathrm{d}h _{t+1},

$

where the first equality results from the Bayes’ rule, and the second equality results from the fact that $r _{t+1}$ is conditionally independent with the previous history given $h _{t+1},\tilde{c} _{t+1}$ and the fact that $h _{t+1}$ only parameterizes the transition kernel of $r _{t+1}$ given $c _{t+1}$. Thus, $h _{t+1}$ and $c _{t+1}$ are independent.

• For the third equality,

$

&\int \mathbb{P}(r _{t+1} | c _{t+1}, h _{t+1}) \mathbb{P}(h _{t+1} | S _t, z)\mathbb{P}(z | S _t) \mathrm{d} h _{t+1} \mathrm{d} z \ &\quad= \int \mathbb{P}(r _{t+1} | c _{t+1}, h _{t+1},S _t, z) \mathbb{P}(h _{t+1} | S _t, z) \mathrm{d} h _{t+1} \mathbb{P}(z | S _t) \mathrm{d} z \ &\quad= \int\mathbb{P}(r _{t+1}|c _{t+1}, S _t, z)\mathbb{P}(z | S _t) \mathrm{d} z,

$

where the first equality results from the fact that $r _{t+1}$ is conditionally independent with the other variables given $h _{t+1},\tilde{c} _{t+1}$, and the second equality results from the Bayes’ rule.

Explanations of the Proof of Corollary 4.2

*In the first formula, since the hidden variable $z$ only parameterizes the conditional probability of $r _t$ given $c _t$, $c _t$ and $z$ are independent.

• In the third formula, the most outer sum is $\sum _{t=0}^{T}$. For the telescoping argument, we follow the convention that $\sum _{t=1}^{0}\cdot = 0$. In fact, when $t=0$,

$

\mathbb{P}(r _{t+1}|c _{t+1},S _{t})= \frac{\int \mathbb{P}(r _1|c _1,z)\mathbb{P}(z)\mathrm{d}z}{1}.

$

Since $\log 1 =0$, this term just disappears. Thus, the telescoping argument only leaves one term.

• The last equality follows from the direct calculations. Here we present the calculation process for the finite $\mathfrak{Z}$. For any function $f:\mathfrak{Z}\rightarrow \mathbb{R}$ and distribution $p\in\Delta(\mathfrak{Z})$, we will calculate

$

\min _{q\in\Delta(\mathfrak{Z})} -\sum _{z}f(z)q(z)+\sum _{z}q(z)\log\frac{q(z)}{p(z)}.

$

Define the lagrangian function

$

g(q,\lambda) = -\sum _{z}f(z)q(z)+\sum _{z}q(z)\log\frac{q(z)}{p(z)}+\lambda (\sum _{z}q(z)-1).

$

By solving the equations

$

\nabla _{q} g(q,\lambda)=0,\quad \frac{\partial}{\partial \lambda}g(q,\lambda)=0,

$

we have that the minimizer is

$

q^{\ast}(z) = \frac{p(z)\exp(f(z))}{\sum _{z^\prime}p(z^\prime)\exp(f(z^\prime))}.

$

Plugging this into the objective function, we have

$

\min _{q\in\Delta(\mathfrak{Z})} -\sum _{z}f(z)q(z)+\sum _{z}q(z)\log\frac{q(z)}{p(z)} = -\log \sum _{z}p(z)\exp(f(x)).

$

This justifies the last equality of our proof.

Explanations of The Details in the Proof of Theorem 5.3

• In the last inequality of (F.2), we note that there should be no expectation for the first term. The reason is that the left-hand side of (F.1) takes conditional expectation with respect to $\tilde{\mathcal{D}}$ conditioned on $\mathcal{D}$. Since $S _t^n$ is a part of $\mathcal{D}$, taking the conditional expectation with respect to $\tilde{\mathcal{D}}$ conditioned on $\mathcal{D}$ of the first term is trivial. Thus, there is no explicit expectation over the first term.

• The bound in (F.6) originates from the last softmax layer in transformers, which is defined below (5.1). Here $B_A$ is the bound of each component of the softmax input. To derive the lower bound of the output probability of transformers, we calculate the minimal output component of softmax given the bound of each component.

• The TV bound located between (F.6) and (F.7) originates from Proposition F.1 and the distribution assignment (F.5). As discussed in the revised manuscript, we set the distribution $P$ as the uniform distribution on the neighborhood on a parameter with radius proportional to $1/NT$. The corresponding approximation error measured in $l_1$ distance,i.e., the TV distribution, is bounded by $1/NT$. Thus, Proposition F.1 shows that the approximation error is $O(1/NT)$ a.s. We also added a figure in the appendix of the revised manuscript to highlight this.

Explanations about the Distribution Construction in the Proof of Theorem 5.3 and the Network Construction in the Proof of Proposition 5.4

We thank the reviewer for the suggestions. We have modified correspondingly in the revised version, and we added two figures in the revised manuscript to illustrate these two constructions. Here we provide the explanations about the details in the proofs of Theorem 5.3 and Proposition 5.4.

• For Theorem 5.3, we adopt the Pac-Bayes framework to derive the generalization error bound, i.e., Lemma I.2. We restate the main equation in the lemma

$

    \bigg|\mathbb{E} _{Q}\bigg[\mathbb{E} _{X}\big[ f(X) \big]-\frac{1}{n}\sum _{i=1} ^{n}f(X _{i})\bigg]\bigg|\leq \lambda c\mathbb{E} _{Q}\big[\mu(f)\big]+\frac{1}{n\lambda}\bigg[\text{KL}(Q\|P _{0})+\log\frac{2}{\delta}\bigg].

$

To derive the uniform generalization bound for the transformer function class, we need to set $Q$ and $P_0$ such that the left-hand side of the inequality is close to the generalization error of any function and the right-hand side remains bounded. To achieve this goal, we set $Q$ as the uniform distribution on the neighborhood of any function, and the difference between the left-hand side of the inequality and the generalization error of any function can be upper bounded via Proposition F.1. We set $P_0$ as the uniform distribution on the whole function class, which guarantees that the right-hand side of the inequality can be upper bounded by $O(\log (NT))$.

• For Proposition 5.4, we bound the approximation error with the help of Theorem 2 in [6], which states that for any permutation-invariant function $g^{\ast}(X):\mathfrak{X}^{L}\rightarrow \mathbb{R}^{d _{y}}$, we have that

$

g^{\ast}(X)=\rho^{\ast}\bigg(\frac{1}{L}\sum _{i=1}^{L}\phi^{\ast}(x _{i})\bigg),

$

where $\rho^{\ast}: \mathbb{R}\rightarrow \mathbb{R}^{d _{y}}$ and $\phi^{\ast}:\mathfrak{X}\rightarrow \mathbb{R}$. Thus, to approximate a permutation-invariant function, we only need to approximate $\phi^\ast$ and each component $\rho_i^*$ of $\rho^\ast$. In the proof, we first state that if we already have $\phi^\ast$ and $\rho^\ast$ approximated by submodules of transformer, then we can approximate $\rho^{\ast}\bigg(\frac{1}{L}\sum _{i=1}^{L}\phi^{\ast}(x _{i})\bigg)$ by combining these submodules with a single attention (Step 1). In the second step, we indicate how to approximate $\phi^\ast$ and $\rho^\ast$ with the modules in transformers (Step 2).

Where Assumptions 5.2 and F.3 are used

We point to where Assumptions 5.2 and F.3 are used in the revised manuscript. In fact, we construct $\phi^\ast$ and $\rho^\ast$ with the help of Lemma I.9, which requires Assumption F.3. In Step 3, we bound the ratio between $\mathbb{P}(x|S)$ and $\mathbb{P} _{\theta^{\ast}}(x|S)$, which requires the denominator to be larger than $0$. We use Assumption 5.2 here to derive the bound.

Explanations of (4.1)

We highlight that our model in (4.1) indicates that $r _t$ depends on the true hidden concept $z _\ast$ through $h _t$, but $c _t$ does not depend on $z _\ast$. In fact, $r _t$ directly depends on some hidden variable $h_t$, whose distribution is determined by $z _\ast$. When $h _{t}=z$ for $t\in[T]$ degenerates to the hidden concept, this recovers the casual graph model in [7] and the model in [8].

Motivation for the Regret Definition and Why $t\cdot \text{regret}$ is Upperbounded by a Constant

We define the regret in the form of an average to indicate the average regret of each example in the prompt. In the classical supervised learning task, it is common to take mean square error as the performance metric. In the Gaussian model, our regret degenerates to the mean square error. It is also reasonable to consider the cumulative regret, which can be upper bounded by a constant. It originates from the fact that LLMs can identify the correct hidden concept with the error exponentially decaying in the number of samples $t$, which is shown in Proposition 6.3. The intuition can be seen from the following approximate calculations under a simpler model. Now we assume that $\lbrace(r _t,c _t)\rbrace _{t=1}^{T}$ are i.i.d. samples generated from $P(r|c,z _\ast)\cdot P(c)=P(r,c| z _\ast)$ . Then we have

$

\frac{1}{T}\sum _{t=1}^{T}\log\frac{P(r _t, c _t|z _\ast)}{P(r _t, c _t|z)}\rightarrow \text{KL}(P(\cdot|z _\ast)\|P(\cdot|z)).

$

It implies that

$

\frac{P(z| S _T)}{P(z _\ast| S _T)}=\frac{P(z)P(S _T|z)}{P(z _\ast)P(S _T|z _\ast)}\rightarrow \frac{P(z)}{P(z _\ast)}\exp(-T\cdot\text{KL}(P(\cdot|z _\ast)\|P(\cdot|z))).

$

Since $\sum _{t=1}^{T}\exp(-kt)<O(1)$ for $k>0$ can be upper bounded by a constant, LLMs achieve the constant accumulative regret. It is also verified by our simulation results in the revised manuscript.

Explanation of Word "Sequentially"

The word "sequentially" comes from the fact that we view the ICL from the online learning perspective. We would like to understand how the ICL performance scales with an increasing number of examples in the prompt. For example, in Corollary 4.2, we prompt the LLMs with the $\text{prompt}_{t}$ that has $t$ examples in time $t$. We evaluate the regret in this setting. This is the iterative prompting.

Explanation of Wrong Input-Output Mapping

The word "wrong" refers to the fact that input-output pairing is not correct. We would like to give an example of the wrong input-output pairing. Assume that we want LLMs to predict the classification of biological categories. The prompts with correct input-output mapping can be "Cats are animals, pineapples are plants, mushrooms are", while the prompt with wrong input-output mapping can be "Cats are plants, pineapples are animals, mushrooms are". Empirically, LLMs are able to derive the correct answer even with random labels, and the input-output pattern in the prompt is essential for efficient ICL[6]. Here we provide the theoretical understanding for these phenomena under the distinguishability assumption. We show that the pretrained LLMs can perform efficient ICL even with wrong labels, including the random label as a special case, when the distinguishability assumption holds.

Why we use KL divergence

Since we adopt the cross-entropy loss to train the LLMs, KL divergence is a natural choice for it. When quantifying the training performance, we measure it via the total variation distance of the conditional probability in the token space, not in the embedding space. We leave the exploration of other divergence metrics as the future works.

The Discussion of Finetuning

We note that the LLMs learned from the pretraining are powerful enough. For example, LLMs are able to efficiently implement the time-series tasks in a zero-shot manner[5]. Then we will discuss the influence of two kinds of finetuning.

The first kind of finetuning is to optimize the parameters of LLMs on a specific task. We note that our performance guarantee in Theorem 5.3 takes expectation with respect to the pretraining distribution. After the fine-tuning process, the distribution here will be closer to the token distribution of the desired task. This will improve the performance of LLMs on this task.

The other kind of finetuning is instruction finetuning, which aims to align the behavior of LLMs to the human preference. People first learn a reward function from the human feedback and use the learned reward to tune LLMs with reinforcement learning techniques. The analysis of this process requires the additional techniques about reinforcement learning, and we leave this as future work.

How to get the hidden concept in the LLMs

First, we would like to specify the reasons why LLMs can generate the hidden concepts. There are two main reasons: 1. The pretraining data of LLMs comes from the multiple tasks. There are a sufficient number of concepts presented in the pretraining data. 2. The LLMs are large enough to extract the hidden concepts from the prompt. In Proposition 4.3, we theoretically show that the attention head contains the hidden concept information in Gaussian linear model.

Second, we would like to discuss how to get the hidden concept in the LLM in experiments. In our experiment section in Appendix C, we extract the hidden concept vector as the average sum over prompts of the values of twenty selected attention heads, i.e., we compress the hidden concept into a vector. This is motivated by Proposition 4.3. To demonstrate the effectiveness of the constructed hidden concepts, we add these hidden concept vectors at a layer of LLMs when the model resolves the prompt with zero-shot. The experimental results show that the LLMs with hidden concept vector in the zero-shot setting have comparable performance with the LLMs prompted with several examples. This verifies that the constructed hidden concept vector indeed contains the essential information about the hidden concept. This method is recently proposed and tested in [7]. We note that there are other methods to extract the hidden concept vectors. According to [8], we can also learn the hidden concept deduced by LLMs as token values. We can represent the hidden concept as some special tokens. The value of these tokens are trained by maximizing the probability of the correct answer when the LLMs are prompted with some examples. These learned tokens are shown to be effective in the prompt design.

We thank the reviewer again for reading our response. We appreciate it if the reviewer could consider raising the score, if our rebuttal has addressed your concerns.

The results in Table 3 strongly corroborate our theoretical findings. First, the results verify our claim in Corollary 4.2 and Theorem 6.2 that $t\cdot \text{regret}$ can be upper bounded by a constant. Second, the line of squared error indicates that the ICL of LLMs only has a significant error when $T\leq d$, i.e., the regret only increases in this region. Thus, the regret of the ICL by LLMs is at most linear in $O(d/T)$. From the view of our theoretical result, discretizing the set $\lbrace z\in\mathbb{R}^{d} | \|z\| _{2}\leq d \rbrace$ with approximation error $\delta>0$ will result in a set with $(C/\delta)^{d}$ elements, where $C>0$ is an absolute constant. Corollary 4.2 and Theorem 6.2 imply that the regret is the sum of the $\log |\mathfrak{Z}|/T = d\log (C/\delta)/T$ and the pretraining error, which matches the simulation results.

Table 4:

In the second experiment, we directly evaluate the regret of pretrained LLMs on the function value prediction task. The prompt consists of the values of a function on the points with fixed intervals. Since the values are real numbers, we adopt the method in [5] to transfer a real number to a token sequence. For the pretrained model, we cannot calculate $\mathbb{P}(r _{i}|\text{prompt} _{i-1},z)$ due to the unknown nominal distributions. Thus, we calculate the cumulative negative log-likelihood $\text{CNLL} _{t}=-\sum _{i=1}^{t}\hat{\mathbb{P}}(r _{i}|\text{prompt} _{i-1})$, and $\text{CNLL} _{t}/t$ is an upper bound of the regret. In Table 4, we indicate the cumulative negative log-likelihoods of predicting the values of three functions. The results show that the cumulative negative log-likelihoods are stepped, which means that the cumulative negative log-likelihoods are upper-bounded by constants in a long period. This corroborates with Corollary 4.2 and Theorem 6.2.

• Verification of the Constant Ratio between $\mathtt{att}_{\dagger}$ and $\mathtt{att}$

Table 5:

To verify Proposition 4.3, we directly calculate the ratio between $\mathtt{att} _{\dagger}$ and $\mathtt{att}$. We consider the case $d _v = 1$ and $d _k=d$ for some $d>0$. The entries in $K$ of (4.8) are i.i.d. samples of Gaussian distribution, and the $i-$th entry of $V$ is calculated as the inner product between a Gaussian vector and the $i-$th column. Table 5 shows the results for $d=2$ and $d=3$. It shows that the ratio between $\mathtt{att} _{\dagger}$ and $\mathtt{att}$ will converge to a constant. This constant depends on the dimension $d$, which originates from Proposition F.1.

Validation Performance of ICL

We are not very clear about the meaning of “validation performance” in the questions. We would like to ask the reviewer to clarify the question. Here we attempt to answer this question with some potential explanations of it.

If “validation performance” means validating the theoretical findings in the empirical results, our simulations in the modified manuscript provide a detailed response to it. Our simulation results verify the Bayesian view (Proposition 4.1 and (4.7)), Corollary 4.2, and Proposition 4.3. The detailed analysis is provided in Appendix C of the revised manuscript.

If “validation performance” means that we would like to validate the ICL performance of a given LLM, then we can measure the ICL performance of the LLM by splitting the data. Given a set of sentences, we can split them into a training set and a testing set. During the training process, we could implement cross-validation to tune the parameters. The performance of LLMs can be tested on the test set.

We thank the reviewer for the valuable feedback. We address the major concerns in the following.

Added Experimental Results

We conduct five experiments to verify our theoretical findings, including the Bayesian view (Proposition 4.1 and Eqn. (4.7)), the regret upper-bounded in Corollary 4.2 and Theorem 6.2, and the constant ratio between $\mathtt{attn}_{\dagger}$ and $\mathtt{attn}$ in Proposition 4.3. The results and implementation details are provided in Appendix C and D in the revised manuscript. We will list a part of numerical results as table below.

• Verification of the Bayesian View

Table 1:

To verify the Bayesian view that we adopt in the paper, we implemented two experiments. In the first experiment, we explicitly construct the hidden concept vectors that are found by LLMs. Motivated by (4.7) and Proposition 4.3, we construct the hidden concept vector as the average sum over prompts of the values of twenty selected attention heads, i.e., we compress the hidden concept into a vector with dimension $4096$. To demonstrate the effectiveness of the constructed hidden concepts, we add these hidden concept vectors at a layer of LLMs when the model resolves the prompt with zero-shot. In Table 1, "zs-hc" refers to the results of LLMs that infers with learned hidden concept vectors and zero-shot prompt, and "ICL-$i$" refers to the results of LLMs prompted with $i$ examples. This table report the accuracy of LLMs under different prompts. We consider the tasks of finding antonyms, finding the capitals of countries, and finding the past tense of words. The results indicate that the LLMs with learned hidden concept vectors have comparable performance with the LLMs prompted with several examples. This indicates that the learned hidden concept vectors are indeed efficient compression of the hidden concepts, which proves that LLMs deduce hidden concepts for ICL. This result strongly corroborates with (4.7).

Table 2:

In the second experiment, we aim to verify that LLMs implement inference with the Bayesian framework, not with gradient descent [1,2,3] on some tasks. We prompt the LLMs with the history data of a set of similar multi-armed bandit instances with $100$ arms, and let LLMs indicate which arm to pull in a similar new bandit instance. In these similar bandit instances, there is an informative arm, whose reward is exactly the index of the arm with the highest rewards. We also provide the side information that "Some arm may directly tell you the arm with the highest reward, even itself does not have the highest reward". In each example provided in the prompt, there are the rewards of six arms, including the informative arm and the best arm, in one bandit instance. As shown in Table 2, the LLMs can efficiently implement ICL even with only $6$ examples. We note that the gradient descent algorithms in the previous works cannot explain this performance, since the gradient descent algorithms need at least $100$ data points, where each data point is the reward of one arm, to learn. In contrast, the Bayesian view can clearly explain Table 2, where LLMs make use of the side information to calculate a better posterior for the bandit instance. Thus, LLMs have good ICL performance in this setting.

• Verification of the Regret Bound

Table 3:

To verify Corollary 4.2 and Theorem 6.2, we implement experiments to evaluate the regret in two settings. In the first setting, the LLMs is trained for the linear regression task from scratch, which is a representative setting studied in [1,4]. The examples in the prompt are $\lbrace(x _i,y _i)\rbrace _{i=1}^{N}$, where $x _i\in\mathbb{R}^d$, $d=20$ and $y _{i}=w^{T}x _{i}$ for some $w$ sampled from Gaussian distribution. Given the Gaussian model, we adopt the squared error to approximate the logarithm of the probability. Then the $t\times \text{regret}$ of the LLMs can be well approximated by the sum of the squared error till time $t$.

We hope this message finds you well. As the rebuttal period will close soon, we would like to reach out to you and inquire if you have any additional concerns regarding our paper. We would be immensely grateful if you could kindly review our responses to your comments. This would allow us to address any further questions or concerns you may have before the rebuttal period concludes.

To test the performance of the estimate $\hat{f}$, if we sample a single point $x=0.5$, then there is no performance guarantee. However, we can sample a set of points $\tilde{x} _i\sim \text{unif}([0,1])$ for $i\in[\tilde{N}]$. Here $\tilde{x} _i$ for $i\in[\tilde{N}]$ are different from $x _i$ for $i\in[N]$ with probability $1$. Then we have that

$

\frac{1}{\tilde{N}}\sum _{i=1}^{\tilde{N}} (\hat{f}(\tilde{x} _i)-2\tilde{x} _i)^2\rightarrow 0 \text{ in probability as }\tilde{N}\rightarrow\infty.

$

We would like to inquire if you have any additional concerns regarding our paper, and we will try our best to address any further questions or concerns you may have before the rebuttal period concludes.

Reference

[1] Gregory Yauney, Emily Reif, David Mimno, Data Similarity is Not Enough to Explain Language Model Performance

[2] Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, Tengyu Ma, Larger language models do in-context learning differently

[3] Katerina Margatina, Timo Schick, Nikolaos Aletras, Jane Dwivedi-Yu, Active Learning Principles for In-Context Learning with Large Language Models

• Assumption 6.1: This assumption states the coverage of the pretraining data. We note that there will be an information-theoretic barrier without this assumption, the ICL learning problem presents an information-theoretic barrier. For example, if the pretraining data does not contain any material about a specific mathematical symbol in the ICL prompt. In this case, it will be extremely difficult for the LLM to derive the correct prediction, since the meaning of this math symbol is unclear to LLM.

• Assumption G.1: This assumption states that the input-output pairs are independent when conditioned on the hidden concept $z$. This assumption is relevant in many applications, since the inputs of demonstrations are independently sampled, and the output only depends on the input when the concept (task) $z$ is clear.

• Assumption G.2: This assumption states the coverage of the hidden concept $z _\ast$. If $P(z _\ast)=0$, this concept never appears in the pretraining dataset. It will be very difficult for LLMs to complete this task as explained in the previous response. Compared with Assumption 6.1, this assumption is stronger since the coverage is in the hidden space, and it will be used to handle the wrong outputs.

• Assumption G.3: This assumption states the distinguishability of the current concept $z _\ast$. When there are only wrong outputs in the prompt, the concept $z _\ast$ itself should be distinguishable enough to identify from the wrong input-outputs pairs. This assumption is also stated in [9,17].

We thank the reviewer again for reading our response. We appreciate it if the reviewer could consider raising the score, if our rebuttal has addressed your concerns.

Reference

[1] Akyürek E, Schuurmans D, Andreas J, et al. What learning algorithm is in-context learning? investigations with linear models[J]. arXiv preprint arXiv:2211.15661, 2022.

[2] Von Oswald J, Niklasson E, Randazzo E, et al. Transformers learn in-context by gradient descent[C]//International Conference on Machine Learning. PMLR, 2023: 35151-35174.

[3] Bai Y, Chen F, Wang H, et al. Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection[J]. arXiv preprint arXiv:2306.04637, 2023.

[4] Garg S, Tsipras D, Liang P S, et al. What can transformers learn in-context? a case study of simple function classes[J]. Advances in Neural Information Processing Systems, 2022, 35: 30583-30598.

[5] Gruver N, Finzi M, Qiu S, et al. Large language models are zero-shot time series forecasters[J]. arXiv preprint arXiv:2310.07820, 2023.

[6] Todd E, Li M L, Sharma A S, et al. Function vectors in large language models[J]. arXiv preprint arXiv:2310.15213, 2023.

[7] Min S, Lyu X, Holtzman A, et al. Rethinking the role of demonstrations: What makes in-context learning work?[J]. arXiv preprint arXiv:2202.12837, 2022.

[8] Hollmann N, Müller S, Eggensperger K, et al. Tabpfn: A transformer that solves small tabular classification problems in a second[J]. arXiv preprint arXiv:2207.01848, 2022.

[9] Xie S M, Raghunathan A, Liang P, et al. An explanation of in-context learning as implicit bayesian inference[J]. arXiv preprint arXiv:2111.02080, 2021.

[10] Jiang H. A latent space theory for emergent abilities in large language models[J]. arXiv preprint arXiv:2304.09960, 2023.

[11]Ahn K, Cheng X, Daneshmand H, et al. Transformers learn to implement preconditioned gradient descent for in-context learning[J]. arXiv preprint arXiv:2306.00297, 2023.

[12] Dai B, He N, Dai H, et al. Provable Bayesian inference via particle mirror descent[C]//Artificial Intelligence and Statistics. PMLR, 2016: 985-994.

[13] Raskutti G, Mukherjee S. The information geometry of mirror descent[J]. IEEE Transactions on Information Theory, 2015, 61(3): 1451-1457.

[14] Hendel R, Geva M, Globerson A. In-context learning creates task vectors[J]. arXiv preprint arXiv:2310.15916, 2023.

[15] Black S, Biderman S, Hallahan E, et al. Gpt-neox-20b: An open-source autoregressive language model[J]. arXiv preprint arXiv:2204.06745, 2022.

[16] Touvron H, Martin L, Stone K, et al. Llama 2: Open foundation and fine-tuned chat models[J]. arXiv preprint arXiv:2307.09288, 2023.

[17] N. Wies, Y. Levine, A. Shashua. The learnability of in-context learning. arXiv preprint arXiv:2303.07895 (2023).

The results in Table 3 strongly corroborate our theoretical findings. First, the results verify our claim in Corollary 4.2 and Theorem 6.2 that $t\cdot \text{regret}$ can be upper bounded by a constant. Second, the line of squared error indicates that the ICL of LLMs only has a significant error when $T\leq d$, i.e., the regret only increases in this region. Thus, the regret of the ICL by LLMs is at most linear in $O(d/T)$. From the view of our theoretical result, discretizing the set $\lbrace z\in\mathbb{R}^{d} | \|z\| _{2}\leq d \rbrace$ with approximation error $\delta>0$ will result in a set with $(C/\delta)^{d}$ elements, where $C>0$ is an absolute constant. Corollary 4.2 and Theorem 6.2 imply that the regret is the sum of the $\log |\mathfrak{Z}|/T = d\log (C/\delta)/T$ and the pretraining error, which matches the simulation results.

Table 4:

In the second experiment, we directly evaluate the regret of pretrained LLMs on the function value prediction task. The prompt consists of the values of a function on the points with fixed intervals. Since the values are real numbers, we adopt the method in [5] to transfer a real number to a token sequence. For the pretrained model, we cannot calculate $\mathbb{P}(r _{i}|\text{prompt} _{i-1},z)$ due to the unknown nominal distributions. Thus, we calculate the cumulative negative log-likelihood $\text{CNLL} _{t}=-\sum _{i=1}^{t}\hat{\mathbb{P}}(r _{i}|\text{prompt} _{i-1})$, and $\text{CNLL} _{t}/t$ is an upper bound of the regret. In Table 4, we indicate the cumulative negative log-likelihoods of predicting the values of three functions. The results show that the cumulative negative log-likelihoods are stepped, which means that the cumulative negative log-likelihoods are upper-bounded by constants in a long period. This corroborates with Corollary 4.2 and Theorem 6.2.

• Verification of the Constant Ratio between $\mathtt{att}_{\dagger}$ and $\mathtt{att}$

Table 5:

To verify Proposition 4.3, we directly calculate the ratio between $\mathtt{att} _{\dagger}$ and $\mathtt{att}$. We consider the case $d _v = 1$ and $d _k=d$ for some $d>0$. The entries in $K$ of (4.8) are i.i.d. samples of Gaussian distribution, and the $i-$th entry of $V$ is calculated as the inner product between a Gaussian vector and the $i-$th column. Table 5 shows the results for $d=2$ and $d=3$. It shows that the ratio between $\mathtt{att} _{\dagger}$ and $\mathtt{att}$ will converge to a constant. This constant depends on the dimension $d$, which originates from Proposition F.1.

Summary of the mathematical content and the Reproducibility of the Results

We would like to highlight that our main contributions are the theoretical analysis of ICL. Our theoretical results mainly have three parts:

• The first part of our results explains how the perfectly pertained LLMs implement the ICL via Bayesian model averaging (Proposition 4.1) and how the attention structure enables BMA (Proposition 4.3), where the regret of ICL is also analyzed based on Proposition 4.1 (Corollary 4.2). These results are all validated by our experimental results.
• The second part of our results is the analysis of the pretraining error of the transformers, which is decomposed as the sum of the generalization error and the approximation error(Theorem 5.3). The convergence rate of the approximation error is also provided ( Proposition 5).
• The last part is the ICL performance analysis of the pre-trained LLMs. We provide the ICL regret analysis of LLMs with correct input-output prompts (Theorem 6.2), which is verified by our experiments in Appendix C. In addition, we derive the analysis of LLMs when it is prompted with wrong input-output examples( Proposition 6).

We thank the reviewer for the valuable feedback. We address the major concerns in the following.

Added Experimental Results

We conduct five experiments to verify our theoretical findings, including the Bayesian view (Proposition 4.1 and Eqn. (4.7)), the regret upper-bounded in Corollary 4.2 and Theorem 6.2, and the constant ratio between $\mathtt{attn}_{\dagger}$ and $\mathtt{attn}$ in Proposition 4.3. The results and implementation details are provided in Appendix C and D in the revised manuscript. We will list a part of numerical results as the table below.

• Verification of the Bayesian View

Table 1:

To verify the Bayesian view that we adopt in the paper, we implemented two experiments. In the first experiment, we explicitly construct the hidden concept vectors that are found by LLMs. Motivated by (4.7) and Proposition 4.3, we construct the hidden concept vector as the average sum over prompts of the values of twenty selected attention heads, i.e., we compress the hidden concept into a vector with dimension $4096$. To demonstrate the effectiveness of the constructed hidden concepts, we add these hidden concept vectors at a layer of LLMs when the model resolves the prompt with zero-shot. In Table 1, "zs-hc" refers to the results of LLMs that infers with learned hidden concept vectors and zero-shot prompt, and "ICL-$i$" refers to the results of LLMs prompted with $i$ examples. This table report the accuracy of LLMs under different prompts. We consider the tasks of finding antonyms, finding the capitals of countries, and finding the past tense of words. The results indicate that the LLMs with learned hidden concept vectors have comparable performance with the LLMs prompted with several examples. This indicates that the learned hidden concept vectors are indeed efficient compression of the hidden concepts, which proves that LLMs deduce hidden concepts for ICL. This result strongly corroborates with (4.7).

Table 2:

In the second experiment, we aim to verify that LLMs implement inference with the Bayesian framework, not with gradient descent [1,2,3] on some tasks. We prompt the LLMs with the history data of a set of similar multi-armed bandit instances with $100$ arms, and let LLMs indicate which arm to pull in a similar new bandit instance. In these similar bandit instances, there is an informative arm, whose reward is exactly the index of the arm with the highest rewards. We also provide the side information that "Some arm may directly tell you the arm with the highest reward, even itself does not have the highest reward". In each example provided in the prompt, there are the rewards of six arms, including the informative arm and the best arm, in one bandit instance. As shown in Table 2, the LLMs can efficiently implement ICL even with only $6$ examples. We note that the gradient descent algorithms in the previous works cannot explain this performance, since the gradient descent algorithms need at least $100$ data points, where each data point is the reward of one arm, to learn. In contrast, the Bayesian view can clearly explain Table 2, where LLMs make use of the side information to calculate a better posterior for the bandit instance. Thus, LLMs have good ICL performance in this setting.

• Verification of the Regret Bound

Table 3:

To verify Corollary 4.2 and Theorem 6.2, we implement experiments to evaluate the regret in two settings. In the first setting, the LLMs is trained for the linear regression task from scratch, which is a representative setting studied in [1,4]. The examples in the prompt are $\lbrace(x _i,y _i)\rbrace _{i=1}^{N}$, where $x _i\in\mathbb{R}^d$, $d=20$ and $y _{i}=w^{T}x _{i}$ for some $w$ sampled from Gaussian distribution. Given the Gaussian model, we adopt the squared error to approximate the logarithm of the probability. Then the $t\times \text{regret}$ of the LLMs can be well approximated by the sum of the squared error till time $t$.