Towards Auto-Regressive Next-Token Prediction: In-context Learning Emerges from Generalization
Authors: Zixuan Gong
Xiaolin Hu
Huayi Tang
Yong Liu
Venue: ICLR 2025 Poster (2025)
Keywords: In-context learning
Auto-regressive next-token prediction
Generalization performance
PAC-Bayesian
Primary area: learning theory

Abstract: Large language models (LLMs) have demonstrated remarkable in-context learning (ICL) abilities. However, existing theoretical analysis of ICL primarily exhibits two limitations: \textbf{(a) Limited \textit{i.i.d.} Setting.} Most studies focus on supervised function learning tasks where prompts are constructed with \textit{i.i.d.} input-label pairs. This \textit{i.i.d.} assumption diverges significantly from real language learning scenarios where prompt tokens are interdependent. \textbf{(b) Lack of Emergence Explanation.} Most literature answers \textbf{\textit{what}} ICL does from an implicit optimization perspective but falls short in elucidating \textbf{\textit{how}} ICL emerges and the impact of pre-training phase on ICL. In our paper, to extend (a), we adopt a more practical paradigm, \textbf{\textit{auto-regressive next-token prediction (AR-NTP)}}, which closely aligns with the actual training of language models. Specifically, within AR-NTP, we emphasize prompt token-dependency, which involves predicting each subsequent token based on the preceding sequence. To address (b), we formalize a systematic pre-training and ICL framework, highlighting the layer-wise structure of sequences and topics, alongside a two-level expectation. In conclusion, we present data-dependent, topic-dependent and optimization-dependent PAC-Bayesian generalization bounds for pre-trained LLMs, investigating that \textbf{\textit{ICL emerges from the generalization of sequences and topics}}. Our theory is supported by experiments on numerical linear dynamic systems, synthetic GINC and real-world language datasets.

Published as a conference paper at ICLR 2025
TOWARDS AUTO-REGRESSIVE NEXT-TOKEN PREDIC- TION: IN-CONTEXT LEARNING EMERGES FROM GEN- ERALIZATION
Zixuan Gong", Xiaolin Hu', Huayi Tang, Yong Liu Gaoling School of Artificial Intelligence
Renmin University of China Beijing, China
{zxgong, xiaol inhu, huayitang, Muuyonggsai eereggssssrrue...e.o...
ABSTRACT
Large language models (LLMs) have demonstrated remarkable in-context learning (ICL.) abilities. However, existing theoretical analysis of ICI. primarily exhibits two limitations: (a) Limited i.id. Setting. Most studies focus supervised function learning tasks where prompts are constructed with i.i.d. input-label pairs. This i.idd assumption diverges significantly from real language learning scenarios where prompt tokens are interdependent.
(b) Lack of Emergence Explanation. Most literature answers what ICL does from implicit optimization perspective but falls short in elucidating how ICL emerges and the impact of pre-training phase on ICL. In our paper, to extend (a), adopt more practical paradigm, auto-regressive next-token prediction (AR-NTP). which closely aligns with the actual training of language models. Specifically, within AR-NTP, we emphasize prompt token-dependency. which involves predicting each subsequent token based on the preceding sequence. To address (b), we formalize a systematic pre-training and ICL framework, highlighting the layer-wise structure of sequences and topics, alongside a two-level expectation. In conclusion, we present data-dependent, topic- dependent and pppimization-deeenneee
PAC-Bayesian generalization bounds for pre-trained LLMs, investigating that ICL emerges from the generalization of sequences and topics. Our theory is supported by experiments numerical linear dynamic systems, synthetic GINC and real-world language datasets.
INTRODUCTION
Large language models (LLMs) have exhibited intriguing emergent capabilities in-context learning
(ICL) (Brown et al. 2020), which allows effective predictions downstream tasks only based
short context without any parameter fine-tuning (Black et al.) 2022 Rae et al. (022T) Since then,
more scholars have increasingly focused on the intrinsic mechanisms of ICL (Chan al. 2022 Garg
et al. 2022 Von Oswald et al. 2023), aiming to gain a better understanding of LLMs.
For simple supervised function learning tasks, the analysis framework for ICL has been well- established, where independently and identically distributed (i.i.d)) input-label pairs are stacked into a prompt so that the model directly gives the predicted label for query input without parameter updates. Following that, empirically, Garg et al. (2022) demonstrates that pre-trained LLMs can approximate linear functions with a performance that nearly equivalent the least squares estimator. Theoretically, many studies reveal that ICL implicitly employs optimization algorithms. Among these, prominent viewpoint demonstrates that pre-trained LLMs performing ICL equivalent to mimicking single step of gradient descent on linear regression tasks (Ahn et al.] (024, Akyürek ct al. 2022: Dai et al. 2023 Nichani et al. 2024 Von Oswald et al. 2023) [Zhang et al. 2023a). However, there are two main limitations in this literature: (a) Limited i.i.d. Setting. The i.i.d. assumption prompt tokens potentially strong and unrealistic in language tasks where prompt
"Equal contribution.
1 "orresponniig author.

---

Published as a conference paper at ICLR 2025
tokens are dependent, making it challenging to easily extend the aforementioned analysis framework for supervised learning tasks to language modeling. (b) Lack of Emergence Explanation. Most literature answers what ICL does from optimization algorithm perspective but falls short in explaining how pre-trained LLMMs can be good enough to emerge ICI, ability as well as the impact of pre-training phase on ICI., Therefore, the following fundamental questions remain relatively underexplored:
(a) How can we model language tasks with token-dependenncy, going beyond the i..d. limitation?
(b) How can ICL emerge from pre-trained LLMs?
eager to explore research on the auto-regressive next-token prediction (AR-NTP) paradigm, which is key to the success of modern LLMs (Achiam al.) [023] Brown al. 2020 in practical language tasks. Specifically, there are generally successive tokens in both training sequences and ICL prompts, which are drawn from the unsupervised corpus. Through AR-NTP, each subsequent token in sequences
For question (a), in extending existing work supervised function learning,
or prompts is generated based on the preceding tokens. Drawing inspiration from the Bayesian
perspective in statistical field, we utilize conditional probability distribution (Han et al., 2023 [iang
2023 Li et al. 2023, Wang et al. 2023 Wei et al. 2022 Wu et al., 2023 Xie et al., 2021 ) to theoretically model AR-NTP. the line of Bayesian research, most view ICI as process of implicit
Bayesian inference, where the pre-trained LLM is thought to subconsciously deduce a concept while generating a prediction. These works assume tokens are generated from Hidden Markov Models. In our paper, consider more relaxed generation mode, AR-NTP, where each token depends on all the preceding tokens rather than just one preceding token. Consequently, our core task is to model language tasks, and the core challenge of modeling language tasks is to consider prompt token-dependency.
To analyze question (b), we intuitively recognize that the prompt sequence may be new or unseen and the corresponding ICL topic for the sequence is generally unknown. We desire well well-pretrained in-context learner, i.e., the LLM can effectively utilize ICL to generate high-quality responses to any sequence under any topic, regardless of whether the sequence and topic are seen or unseen during pre-training. This necessitates examining population loss by considering expectations over distribution, rather than focusing solely on empirical loss. A low population loss indicates that the model possesses strong generalization ability for diverse sequences and topics, thereby facilitating the emergence of ICL. Therefore, it is natural to explore the origin of ICL. from the perspective of measuring generalization ability. Specifically, we formalize a systematic pre- pre-training and ICL framework that incorporates data distribution and topic distribution, allowing us to establish the population loss with a two-level expectation. By adopting PAC- PAC-Bayesian generalization analysis techniques, we gain clearer understanding of how ICL emerges.
Based on the above analysis, we summarize our main contributions as follows.
1. Pre-training and ICL Framework under AR-NTP Paradigm. Towards practical AR-NTP paradigm rather than i.idd. setting, we establish a systematic pre-training and ICL. framework considering layer-wise structure of sequences and topies (Section B.Tp. Meanwhile, we propose two-level expectation over data and topic distribution to link pre-training and ICL phase, thereby providing well-defined population loss based on empirical loss (Section 3.2 and 3.3).
2. ICL Emerges from Generalization. Our theoretical results of population loss reveal that model generalization, tightly with ICL abilities, is influenced by model size, optimization iterations, pre- pre-training data and prompt length. This further demonstrates that ICL emerges from the excellent generalization of sequences and topies (Section 4.1 and Section 4.2).
3. Generalization Analysis. By dealing with prompt token-dependency and employing continuous mathematical techniques such as Stochastic Differential Equation (SDE), we present data-dependent and sopic-dependent, as well as aepimization-dependeer PAC-Bayesian generalization bounds for population loss (Section 4.1 and Section 4.2)
4. Empirical Verification of Theory. We perform experiments on numerical linear dynamic system, synthetic GINC and real-word language datasets (Section (5and Appendix DD). By discussing the effects of pre- pre-training data, optimization process and prior model initialization, we verify our theoretical results and offer practical implications (Appendix E
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
Optimization Perspective on ICL. The field of ICL in transformers has been extensively explored from various analytical perspectives. A prominent approach is to view ICL as implicit execution
of gradient descent algorithm (Akyürek et al. 2022: Von Oswald et al. 2023 Dai et al.
2023
Zhang
et al. 2023a). This concept is well-illustrated (Akyürek et al. 2022 Von Oswald et al. 2023 which demonstrates that pre-trained
can mimic a single step of gradient descent on linear regression tasks. Huang al. (2023); Zhang et al. (2023a) specifically provide evidence that learning linear models via gradient flow aligns with transtormers learning in-context, based on optimization convergence analysis. However, all this literature falls short in explaining how LLMs develop the ability of ICL and the connection between the pre- training and ICL phases.
Bayesian Perspective on ICL. There is some existing work from Bayesian view enriching the understanding of ICL (Han et al., 2023 Jiang 2023; Wang et al.) 2023 Wies et al.] 2023] Xie et al. 202T). Xie et al. (2021) interpreter ICL as implicit Bayesian inference, where the pre-trained LLM is seen as intuitively deducing concept during prediction. Following Xie et al. (202 1). the assumption that the pre-training distribution is Hidden Markov Model, is relaxed in Wies et al. (2023). Further, Zhang et al. (2023a) consider the pre- pre-training and ICL phase and assume that prior and posterior satisfy a uniform distribution. In our study, we adopt data- deleedeennddnn and topic- appc-dependent prior without relying some predetermined distribution assumptions. A topic distribution is considered in our pre-training and ICL. framework, which weakens the assumption that the pre-training topic distribution covers the ICL topic distribution in Zhang et al. (2023a) to some extent.
From Multi-Task Learning to Meta-L Learnne. Training LLMS to perform ICL can be viewed as an approach for addressing the wider tasks of meta-learning or learning-to-lenn
(Naik & Mammone 1992, Schmidhuber 1987). y. In pre-training phase, the LLM is trained on multiple tasks. We expect that a well prel-ppet LLM serves as a good meta-learner possessing the ICL ability to generalize to new unseen tasks, not only as a multi-task learner (Radford et al. 2019). Theoretical analysis of meta-learning has received significant attention (Chua et al. [021] Denevi et al. 2018 Ji et al. 2020) Tripuraneni et al., 2020). Drawing inspiration from the assumption of an unknown task distribution in meta-learning analysis, we establish a pre-training and ICI. framework with topic/task distribution and data distribution, to describe the model's generalization ability to new test prompts and unseen topics (Details in Section 3.T). However, it is worth emphasizing that our ICL generalization analysis meta-learning generalization, since the expectation over sequence would be specially spilt into two parts due to the prompt token-dependency (Details in Section 3.3
under AR-NTP cannot be equivalent
We defer more discussion in Appendix C
3 PROBLEM SETUP
In this section, for question (a), Section 3.1 establishes the pre-training and ICL framework under
AR-NTP paradigm. Following that, to address question (b), Section 3.2 and 3.3 formalize the
optimization objective and generalization of pre-trained LLMs, to illustrate how pre-trained LLMs can be good enough to emerge ICL ability.
Notations. Let [[]] be the expectation of random variables. The KL divergence between distribution and is DKI (M v) Ee [log (()) and total variation (TV) distance is Drv(H, 1/2 Eeee (1) (()). The detailed notations is shown in Appendix Table
3.1 AR-NTP PARADIGM AND PRE-TRAINING AND ICL FRAMEWORK
We model the practical AR-NTP paradigm language learning tasks, where any training sequence or ICL prompt consists of successive tokens drawn from the unsupervised corpus. Within AR-NTP, each subsequent token in the sequence is generated based on the preceding tokens, referred to as prefix sequences. Thus, the data distribution of each token is represented as a conditional probability distribution in statistics. From the analysis to question (b), it's necessary to consider the impact of pre- pre-training and formalize a systematic pre- tra-trainin and ICL framework to facilitate the generalization analysis where ICL emerges. The overview of pre- training and ICL framework, including topic distribution and data distribution, is shown in Figure
3

---

Published as a conference paper at ICLR 2025
train
Seguence
Pre-train Auto-rogressive LLM
Pre-training Topics
Sequence
Sequence
Me Wir
gea ~ Pos (sa))
Topic Distribution
Data Distribution
Pa be close P
we
Po
ultilies
Pre-trained Auto-regressive LLM P.
ICL Topics
Learnable
Frowen
Figure Overview of Pre-training and In-context Learning Framework.
Pre-training Phase. In pre-training phase, the training data typically encompasses sequences from various topics. To model the training process more realistically, it's essential characterize and distinguish the training sequences and their respective topics in detail. In the following, we describe the generating process of all training sequences.
1. Generate One Training Sequence Under a Pre-training Topic: of topic distribution Pw and fixed topie wik ~ Pww, n-th sequence E satisfies the true data distribution generating process, (t 1)-th token 4,+1 in E is generated depending on the prefix
Under the assumption
P wes denoted by IP(- wx). According the auto-regressive kn
sequence E = {x/ ki kn .22 ,... kin }. It also means 2441 IP(- Lo wx). When the A.n
Tk. is already formed. token count reaches Tk.n. the sequence E {(E xz =(+1)) Da
2. Generate N₂ Training Sequences Under a Pre-training Topic: Repeat step I, N2 training sequences following the same data distribution P.,,, or P(. wx), are i.i.d. sampled. The pre-training sequences under topic wa can be denoted by E [Ek.") Ju=
3. Generate Complete Training Sequences Under K Pre-training Topies: Considering that the set of topies used for pre-training is Wpee which contains K topics, then repeat Step the complete pre-training sequences can be denoted by = {Eb) K == {F K,N,, Jk
Note that the number of sequences for different topics (N₂)) and sequence length (Tk,n) vary from each other. We give more discussion for N₂ and Te,,, in Remark F2 For theoretical convenience, we unify N and T in our main analysis. Using pre-training data E containing a total of KN sequences, the model gives predictions that still follow the AR-NTP methods. Then the LLM FP parameterized by 0 E θ is pre-trained by establishing AR-NTP loss.
Note: Throughout our paper, the subscripts or superscripts k, n, and represent the topic index, sequence index and token index, respectively.
ICL Phase. In ICL phase, for any ICL topic w that satisfies the same topic distribution Py as pre-training topics, prompt { ,TT, is generated from data distribution F., (or P(- w)). Similarly the above generation process of pre-training sequence F.k.n Iz TP( prompt,-11 w). The goal for an ICI, learner is to make the prediction Po(eT, promptr, 11, w), given by the pre-trained LLM Po, as close as possible to P(IT, prompty,-1- w). To test the performance of ICI. on different topics, set of ICL topics WICI is adopted. Note that different numbers of demonstrations may be used in standard ICI. In our theoretical modeling, we consider directly concatenating demonstrations into ICL prompts. The distinction between zero-shot ICL and few-shot ICL is reflected in the prompt length Tp, and our theoretical results reveal the impact prompt length on model generalization and ICL emergence.
4

---

Published as a conference paper at ICLR 2025
3.2 OPTIMIZATION OBJECTIVE: EMPIRICAL LOSS
Considering the pre-training phase, finite topics and finite sequences are i..d. sampled from topic distribution Fw and data distribution Pw, P(: wx). During the training process, for any sequence E under topic Wi, each token 2++1 can be predicted depending on the prefix sequence E optimizing the negative log-likelihood loss log (x k.m. E wkk in practice. When with fixed the true data distribution P(: wx), minimizing - log (o EE wx) is equivalent to minimize the log F( ".m)) Fa(a [,, ..,))
k.n
It expected that the prediction of LLM could be close to the true sequence.
Under k-th topie, we average the prediction loss of all tokens for the n-th sequence and then average this over N sequences, with the definition of Lg* (0, w&). Finally, averaging over K topics, the optimization objection (empirical loss) of the pre-training phase defined as
P(a Rin 11
E wk)
1 K
(0, Wpre)
log
NT
knn DE WKk Po Fo
Le (0,wL)
where Lgx... (0, wk) = + E log [
/ PP (a 1E, [E wk),, represents the average
T
loss of one sequence. Define the minimum of empirical loss as
i argming LE Weee
In our theoretical analysis, LLMs perform Stochastic Gradient Descent (SGD) an optimization algorithm to update parameters 0 in order to get the minimum Ó. We formalize optimization error copt with the logarithmic distribution distance between the pre-trained model Pa and the ideal model Fo.
k. [E,"", wx) log Po (1 (1 wx)) log P3 (a
KNT Io
3.3 GENERALIZATION ANALYSIS: TWO-LEVEL EXPECTATION
We expect a good ICL learner, which means that the pre-trained LLM has the ability to identify new topics and predict new sequences. As introduced in Section 3.1 we hope that the pre-trained LLM can infer unseen sequences under unseen ICL topics with the assumption of data distribution and topic distribution. Therefore, it's natural to define a two-level expectation, aiming to minimize the expected population loss.
The First-level Expectation over Sequence. The first-level expectation (i.e. inner expectation) taken over sequence Elkin, indicating sufficient number of sequences for each topic to facilitate comprehensive learning in the ideal case so that the pre-trained model can perform excellently when faced with new sequences under seen topics. In Equation | rather than using Lgs (0, wx) with N sequences, we define L(O, Wpre) with sufficient sequences as
P( E wk) (+1
1 K
L(0, Wprc)
Σ 1=
Egg.. log
Po
kin
E k wk)
More concretely, the prompt token-dependency in AR-NTP (i.e. the tokens are dependently generated in sequence E#im) motivates that the first-level expectation Egg. needs be divided into two parts: expectation over each token when given prefix sequences E. E.tin Ex" wax) and expectation over prefix sequences Ext.. Then combining the definition of KL divergence, it can be transformed
into 1 E DKL (P(- E. wk) P Ef""" , Using any prefix sequence P to replace Erh"", we simply the representation and the first-level expected loss finally becomes
1 K K
L(0, Wpre)=
Σ
Ep (DIL. (P(:) wx) Fa P, wx))]]
(4)
A=1
5

---

Published as a conference paper at ICLR 2025
The Second-level Expectation over Topic. The second-level expectation (i.e. outer expectation) is taken over topic Wi. A well-trained LLM with the objective of minimizing the population loss over infinite topics will demonstrate good generalization of topics, which will be directly reflected in the model's accuracy in predicting ICL. prompts under unseen topics during the ICL. phase, provided these unseen ICL topics satisfy the assumption of topic distribution. Therefore, rather than using K topics in Equation
we define L()) with sufficient topics as
L(0) = E.,, Ep [DRr. (P(( P, w)) |l P.(-l
which is called population loss with two-level expectation. To specifically align to the ICL phase and test the impact of different prompt lengths, we calculate the average loss over each token, similar to pre-tree pre-training, i.e.,
Tp End promps, [DRL (PP() prompt,, w) || Pa(- prompt, w))]
((0)
(5)
Tp
4 ICL EMERGES FROM GENERALIZATION OF PRE-TRAINED LLMs
In this section, we sequentially present Theorems for the generalization of sequences and topics. Specifically, Theorem 4.3 considers the generalization of sequences, providing the upper bound of the first-level expected loss defined in Equation 4 Theorem 4.6 further considers the generalization of topics and provides the upper bound of the two-level expected loss (i.e. population loss defined in Equation 5) by integrating Theorem 4.3 Thus, answer question (b) that ICL emerges from the excellent generalization of sequences and topics.
Summary of Challenges. Before diving into the details of Theorems, we summarize the challenges in both modeling and theoretical proof, in comparison to previous research.
(1) The consideration of two-level expectation. In contrast to focusing solely on the ICL process, model the entire process of training and utilization. aiming to mirror weal-world training scenarios and explore the origin of ICL from the perspective of generalization. The consideration two-level expectation sequence and topic under reasonable pre-training and ICL framework significantly amplifies our workload.
(2) The dealment of prompt token-dependency. Under the setting of AR-NTP, make great efforts to address the dependency between the current token and its preceding tokens by constructing ghost sequences (see the detailed construction in Appendix G.2.1 where summarize the proof sketch), thereby enabling the possibility of taking expectation over each token within all possible sequences. It's worth noting that such dependency is not present in the supervised function learning tasks in other ICL research.
(3) The connection of negative logarithm likelihood, KL divergence and TV distance. We examine the primary optimization objective: negative logarithm likelihood. Naturally, this leads to connection with KL divergence, thereby formalizing the expression of population loss. Furthermore, in addressing the aforementioned token-dependency, we establish connections between TV distance and the expectation over single token when given its predecessors. Therefore, it's necessary to establish connections between the two key distribution metrics: TV distance and KL divergence (see in Lemma G.7). to obtain our final generalization bounds. The AR-NTP setup necessitates the establishment of the above series of connections, which are not considered in the previous ICL work.
4.1 GENERALIZATION OF SEQUENCES: THE FIRST-LEVEL EXPECTATION
Under finite (K) pre-training topics, L(0, Wpre) defined in Equation represents the first-level expected loss where infinite sequences per topic are utilized. It describes comprchensive learning for each pre-training topic in the ideal case that the pre- pre-trained model can give excellent answers for new sequences on the seen topics in ICL phase. In the following theorem, we present the upper bound of ((0, Wine).
Based on basic notations of general PAC-Bayesian theory, in our discussion, we define the posterior distribution of model parameters as y(0),, which is obtained by training the LIM using K topics

---

Published as a conference paper at ICLR 2025
and N sequences per topic. Define the prior distribution v(0), which is assumed probability distribution before some evidence is taken into account. In the formal Theorem for L(0, Wae). derive the KL distance between the posterior and prior in the upper bound, specifically with data-dependent prior (Li et al. 2019). Furthermore, continuous mathematical analysis tools such as SDE are used to detail the KI. divergence between posterior and data-dependent prior, which further considers the optimization algorithm. Since then, we can provide data-dependent and optimization- dependent generalization bound of the first-level expected loss.
Data-Dependent Prior. We employ the following method for generating a data-dependent prior et 2019). Let J/ include N' indexes uniformly sampled from [N] without replacement and I is [N] J, splitting pre-training sequences under fixed topic wy into two parts E and Eý. Under all pre-training topics, we have Ej = { K ]k=] and E', = {b The prior distribution of model parameters 0 depends on the subset E,, which denoted by vy and the posterior distribution of 0 depends on E, denoted by μ. Thus, parallel training process with E, are conducted, and after that, dlta-deeendeent prior V/ will be obtained. We emphasize that extracting a portion of training data to learn the prior distribution of model parameters has significant implications. Specifically, this approach allows the prior to adapt to specific features and trends the data, enhancing the model's ability capture and learn from these nuances. Even if we sacrifice portion of the training data, the prior will lead to a posterior distribution that is better aligned with the actual data distribution. In high-dimensional spaces, data-dependent prior provides more informed starting point.
Assumption 4.1 (Bounded Loss Function). Given fixed topic wy and prefix sequence E for the true data distribution PP( wy. (or IP i and pre-trained LLM Pg. we have
P( K.n km
E.""" ,.k) 1+1 E wx) S S.
log
Po(a
This assumption shows that the logarithm ratio of P(- wx)) and Po is bounded suggesting that the learned model is expected to closely approximate the true data distribution. According to the true data distribution, the probability of x441 tends to 1. Thus by scaling law (Kaplan et al., 2020), the training where N Nurram represents
k.n
loss for specific tokens - log Fo
(2
k.. (z
8. E wg) equals to
N
the number of parameters the model, N2 and aN are constants obtained through statistical fitting. Thus, can further be measured with N. a,y
Assumption 4.2 (Bounded Gradient). Suppose that for topic wP and model parameters Og at step t (for any 0 < t T", T" is the total iteration steps), we have LLV (0,, w S L.
Assumption 4.2 is the classical L-Lipschitz continuous condition, which is widely used in generaliza- tion analysis (Elisseeff et al., 2005 Li et al., 2019). This suggests that the gradient of average loss of one sequence (see in Equation I is bounded.
Theorem 4.3 (Data-Depende De--ndentddd and Optimization Dependent Generalization Bound of the First-level Expected Loss). Let the auto--egressiin regressive LLM I&g be the empirical solution of Equation 1 and IP( w) denotes the true data distribution under topic Under Assumptions |.Iaand 4.2 for any 0 <<< 1. with probability at least 1 5, the first-level expected loss with K topics and infinite sequences per topic, denoted by L(0, Wpre) (see in Equation 4) satisfies,
o,v log 1/8
(KKL |I v) + log 2) Caps
Ey, [L Wpreel =0
+ +V
KNT
KNT
then considering data- depa-dependent prior v and detailing the term DRI(H ll vs). L(0, Wore) is further bounded by
log 1/8
1 K(N N'YT
12C T')
1 8 + +log
K(N -NTYT +
Eopt
(6)
N
where C( (x T') 82S
(1-c- (1-e-aaples eAp(BB33 ). Copt is the optimization error (see in Equation 3
K, (N') and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation] I T' denotes the total training iterations.
Npanan denotes the number of model parameters.
7

---

Published as a conference paper at ICLR 2025
Remark 4.4. Theorem 4.3 reveals that when considering the first-level expectation over sequence, the expected loss achieves O[I/VKNT) rate. This indicates that increase in the number of training topics (K), the number of sequences per topic (N), and the sequence length (2) leads to a reduction in the first-level expected loss, aligning with both intuitive understanding and empirical Neenn.
evidence. Furthermore, from the term C( 1 ), the expected loss is smaller with a larger model
size (i.e., larger Naram). It reveals why LLMSs outperform small language models in emerging ICL, even though they adopt a similar AR-NTP paradigm. T" is related to the optimization process. As T" increases, ((3, T increases, i.e., the generalization error increases. This reflects the influence of total training iterations T' on testing loss, corresponding to the classical viewpoint 'train faster, generalize better' (Hardt et al.) 2016)] Lei & Ying/ 2020 Zhang et al. 2022). We defer more detailed discussion to Appendix F.4 and proof to Appendix G.2. and G.2.2
4.2 GENERALIZATION OF SEQUENCES AND TOPICS: TWO-LEVEL EXPECTATION
Up to now, we have analyzed the first-level expected loss with K topics and infinite sequences per topic. With small first-level expected loss, the pre-trained LLM can perform excellently on the new test prompt under seen topies in ICL phase. In this section, we use similar techniques to further consider the second- expectation with infinite topics, so that the pre-trained LLM with small population loss can perform well on unseen topics. At this moment, ICL emerges from the generalization of sequences and topics.
In the following theorem for the two-level expected loss (population loss) L(0),, similarly, we derive the KI. distance between the posterior fr and prior v in the upper bound, specifically propose topic-dependent prior whose core idea comes from data-dependent prior (Li et al. (019). i.e., a portion of K topics will be used for calculating model prior and other topics will be used for obtaining posterior. Based on SDE analysis, we detail the KL divergence between posterior and topic-dependent prior. Since then, we can provide data- deta-dependent, dopie-dependent and optimization- dependent generalization bound of the population loss.
Hopic-Dependee Prior. We employ the following method for generating a topic-dependent prior, similar to data-dependent prior (Li et al. 2019). We split topics into two parts and let J include K" indexes uniformly sampled from K without replacement and let I be [K] J, then the total sequences are divided into E = =EE* JNEWpe. and E = {E* JeEW Assume that the posterior distribution of model parameters 0 depends on F denoted by ll and the prior distribution of 0 depends on the topic subset F. denoted by vJ. A parallel training process is performed with E based on the same LLM architecture, and after that, lopic-dependent prior y/ will be obtained. Assumption 4.5 (Bounded Expected Gradient). Suppose that for topic wik and model parameters 0, at step & (for any 0 < < T", T" is the total iteration steps), we have | gt... [ (0,, ]]l S
Note that L = denotes the average loss of one sequence (Equation D. Then Egg.. Lg (0z, wx)) denotes the gradient averaging over all possible sequences # therefore or is less than the common Lipschitz constant L. which bounds the gradient at individual sample points.
Theorem 4.6 (Data- Dettndeet,,,,,,, Copic-Dependent and Optimization- of the Two-level Expected Loss). Let the auto-regressive LLM Fg be the empirical solution of Equation ! and IP( w) is the true data distribution under topic w. Under Assumptions 4.1 4.2 and
Generalization Bound
4.5 for any 0 < 5 < 1, with probability at least - 5, the two-level expected loss (population loss)
with infinite topics and infinite sequences per topic, denoted by L(A) (see in Equation 5 satisfies,
[ [
Eg 100) [000]=0[1
|DRL || v)++ + log 1t) + U(Wpe: K, N ,T)
(V. KT,
then considering data-dependent and topic-dependent prior y and detailing the term DRI(E || vy). L() is further bounded by
o
O2C( N
,T)
log 1) + UWWrre K, K,N,N', m
(7)
(K- - K'YIT
K'
U(Wpre: K,N,N',) denotes the right hand of Equation 6 K(K"), N(N') and T denote the number of topics, the number of sequences per topic
where O( C( OL11 T") -2883 11-e
explaaae
8

---

Published as a conference paper at ICLR 2025
and the sequence length utilized in the optimizattin process of Equation training iterations. Nparam denotes the number of model parameters.
T" denotes the total
Remark 4.7 (Optimality Analysis), The term pwe N,N, N", T) comes from Theorem 4.3 whose
analysis can refer to Remark 4.4 As for the first term in the result, with order O /TTp: ). it illustrates the impact of training with a finite number of topics on the model's predictive ability for unseen topics in ICL. In addition, by directly concatenating demonstrations into the ICL prompt in our setting, ICL prompt length reflects the distinction between zero-shot ICL. and few-shot ICL. Our theorem exhibits that longer prompts (i.e. larger Ipp) with more demonstrations lead to smaller population loss, facilitating the emergence of ICL. In total, our guarantees reveal the impact of pre-training on the generalization performance on unseen topics and sequences in ICL, with order O(C( N Npuann (2/////TT 1/VKKT))) comparison, Li al. (022)) derive generalization
bound on unseen topics based on algorithm stability technique, with order O(1/vT+ 1/V where n, M, I denote the sequence length, number of sequences per topic and number of source topics. Our bound is tighter than Li et al. (2023) in the first term, with a compatible second term. We defer the proof to Appendix G.3.1 and G33.2
More Insights Beyond Recent ICL Research. Our PAC- PAC-Bayesian approach offers statistical insights into model performance, emphasizing the impact of pre- pre-training topics, sequences and sequence length. The data-dependent and topic-dependent prior uniquely enhances optimization and may provide more practical guidance model training, data selection and deduplication, distinguishing our work from related generalization studies (Li et al. 2023 Zhang et al. 2023b). Detailed practical implications are discussed in Appendix E
EXPERIMENTS
In this section, we primarily provide some typical experiments verify our theory, observe the optimization process and prior model initialization. We defer more experiments on linear dynamic systems, synthetic language dataset GINC and real-world language datasets to Appendix D
Experiments on Synthetic Language Dataset GINC. Inspired by Xie et al. (2021) we first perform experiments the synthetic language dataset GINC verify our theory. GINC is small- scale language dataset generated from uniform Hidden Markoy Models (HMMs) over topics, where distinct state transition matrices represent the unique topics for each HMM, without defining topics explicitly. We train the GPT-2 model with GINC dataset using a single 24GB NVIDIA GeForce RTX 3090. Detailed data-generating process, model and Hyperparameter settings are provided in Appendix D.2
In the following, we arrange groups of comparative experiments to explore the separate effects of the number of topics (K), number of sequences per topic (N), sequence length (T') and prompt length (Tp). We also provide an interesting case where ICI. failed.
Observation (1): Separate Effects of K, N, T and Tp- In Figure we first present four groups of experiments 2(a) 2(d) to analyze the impact of different factors on generalization. In Figure 2(a) For pre-training, take K 10 topics and generate N E {20, 40, 60, 80, 100] pre-training sequences per topic with varying sequence length ε { (1280, 2560, 5120, 10240). The ICL performance of pre-trained model is then tested with Tp 128 prompt length. Each line exhibits a growing trend, indicating a better generalization performance with increasing sequences per topic. Comparing the four lines, larger sequence length also brings better generalization. From Figure 2(b) 2(d) vary K E {10 (10, 20, 30). Under each K, keep T = 10240, adjust N E (20, 40, 60, 80, 100 and T2 (48, 80, 128, 160). Combining these experiments, we validate the effects of K, N, T, on generalization to emerge ICL ability, closely aligning our Theorems.
Observation (2): An Interesting Case that ICL Fails. In Figure 2 when the pre-training data contains random transitions, the model observes all token transitions, yet ICL fails. This suggests that the pre- pre-trained models cannot extract information when data distributions do not match the topic. thus failing to achieve ICL.
Our code is available at http::///gthhbbboom////oog/////p

---

Published as a conference paper at ICLR 2025
Paquuros sipl
Dequeroee sigte
Saqarcca sepl
Saquarcel per Sople
23
(a)
(b)
(c)
(d)
400
Trile
2007 2000
dbabal stop
(e)
(I)
(h)
Figure 2: Experiments on GINC and Real-world Language Datasets.
Experiments on Real-world Language Dataset. We further perform experiments on real-world language datasets, inspired by (Min et al., 2021; Wang et al. (023). We train the GPT2-large model over 20 diverse pre-training datasets covering sentiment analysis, question answering and reasoning tasks. We defer the detailed description of datasets, model and Hyperparameter settings, and observations on the effects of training data, to Appendix [D3 Here, we focus on more insightful experiments regarding the effects of optimization on generalization, well as potential benefits of effective prior model initialization, guided by the KI. term generalization bounds.
Observation (1): Optimization Process. Through continuous analysis of optimization trajectory. our generalization bounds are optimizatioondeeeddee.t extending beyond the influence of training data. In Figure 2( we present four training processes with varying N E {2 2nd 2 214), while keeping K = 20 and T 256 fixed. We observe that larger N brings faster convergence in addition to better performance. Similarly, in Figure 2(g)) we take varied T E {48, 64, 128, 256} and keep K = 20 and N = 2 fixed. All these observations align with our Theorems that faster training leads to better generalization.
Observation (2): Prior Model Initialization. Building on our generalization results with data- dependent and topic-dependent prior, we design experiments to observe the effects of prior model initialization on training and performance (detailed designation is deferred to Appendix D.3 Our results show that in the random initialization regime, where all pre-training data is used, training for 30.000 steps takes nearly 7 hours on four A100 GPUs. In contrast, under the prior model initialization regime, where smaller model is used for warmup and serves as the prior for initializing the larger model, training the GPT2-large model takes only 4 hours for the same 30,000 steps on four A 110 GPUs, with 0.5 hours required for training the GPT2--mall model for 15,000 steps. Furthermore, as shown in the optimization loss curve in Figure 2(h) prior model initialization not only accelerates training but also stabilizes the training process (especially in the early stages), leading to comparable model performance. This approach demonstrates the effectiveness of leveraging prior knowledge in enhancing both training efficiency and model performance, supporting the KL term in generalization bounds and offering more practical insights.
6 CONCLUSION
In this paper, under the AR-NTP paradigm, we propose a systematic pre-training and ICL. framework with a layer-wise structure of sequences and topics, alongside two-level expectation. By employing PAC-Bayesian analysis and continuous mathematical techniques like SDE, we provide comprehen- generalization bounds,
sive analysis of data-dependent, topic-dependent and ceuimization-dependee demonstrating that ICL emerges for the excellent generalization of sequences and topics. Ultimately, our work aims to take an initial exploration of the origin of ICL ability from the perspective of generalization, supported by both theoretical and experimental results.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This research was supported by National Natural Science Foundation of China (No.62476277), Na- tional Key Research and Development Program of China (NO.2024YFE020322) CCF-ALIMAMA TECH Kangaroo Fund (No.CCF-ALIMMMA OF 2024008), and Suawei-Renming University joint program on Information Retrieval. We also acknowledge the support provided by the fund for building worldclass universities (disciplines) of Renmin University of China and by the funds from Beijing Key Laboratory Big Data Management and Analysis Methods, Gaoling School of Artificial Intelligence. Renmin University of China, from Engincering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education, from Intelligent Social Governncce Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the 'Dou- bleFirst Class' Initiative, Renmin University of China, from Public Policy and Decision-making Research Lab of Renmin University of China, and from Public Computing Cloud, Renmin University of China.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-200 201007, 2020.
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning, Advances in Neural Information Processing Systems, 36, 2024.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.1566) 2022.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems, 36, 2024.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. dpectrallynnormaliin margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference machine learning, pp. 531-540. PMLR, 2018.
Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, et al. Gpt-neox-20b: An open-source autoregressive language model. arXiv preprint arXiv:2204.06745, 2022.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 526, 2002.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprint arXiv:07/2..2245 2007.
Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang, Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learning in transformers. Advances in Newral Information Processing Systems, 35: 1888-, 2022.

---

Published as a conference paper at ICLR 2025
Kurtland Chua, Qi Lei, and Jason D Lee. How fine-tuning allows for effective meta-leaming. Advances in Neural Information Processing Systems, 34:8871- 18844, 2021.
Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Shuming Ma. Zhifang Sui, and Furu Wei. Why can gpt learn in-context? language models implicitly perform gradient descent as meta-optimizers. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
Victor H de la Peña, Evarist Giné, Victor H de Peña, and Evarist Giné. General decoupling inequalities for tangent sequences. Decoupling: From Dependence to Independence, pp. 291-324, 1999.
Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Brau,Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, al. Language modeling is compression. arXiv preprint 23XX::2309.1066. 2023.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. arXiv preprinl 1rXxv:/803.08000 2018.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703. 2017.
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. Advances in Neural Information Processing Systems, 31, 2018.
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30599 -0588, 2022.
Chi Han, Ziqi Wang, Han Zhao, and Heng Ji. In-context learning of large language models explained as kernel regression. arXiv preprint arXiv:2305. 12766, 2023.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234 PMLR, 2016.
Yu Huang. Yuan Cheng, and Yingbin Liang. In-context convergence of transformers. arXiv preprint arXiv:2310.05249, 2023.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters, Advances in Neural Information Processing Systems, 33:1 1490-199111 11500, 2020.
Hui Jiang. A latent space theory for emergent abilities in large language models. arXiv preprint arXiv:2304. 09960, 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint PxXi:20011.083// 2020.
S Kwapien and WA Woyczynski. Semimartingale integrals via decoupling inequalities and tangent processes. Probab. Math. Statist, 12(2): 200, 1991.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization enror bounds of noisy gradient methods for non-convex learning. arXiv preprint arXiv: 1902. 00621, 2019.
12

---

Published as a conference paper at ICLR 2025
Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pp. 19565-19594. PMLR, 2023.
Xuanyuan Luo, Bei Luo, and Jian Li. Generalization bounds for gradient methods via discrete and continuous prior. Advances in Neural Information Processing Systems, 35: 35:10000-10614, 2022.
David A McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pp. 230-234, 1998.
Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi. Metaicl: Learning learn in 2021.
context. arXiv preprint
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pp. 605-638. PMLR, 2018.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Devang K Naik and Richard J Mammone. Meta-neural networks that learn by learning. In [Proceed- ings 1992] IJCNN International Joint Conference on Neural Networks, volume 1, pp. 437-442 IEEE, 1992.
Eshaan Nichani, Alex Damian, and Jason Lee, How transformers learn causal structure with gradient descent. arXiv preprint w7Xiv:2402.14735, 2024.
Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electron. J. Probab, 20(79):1-32, 2015.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, et al. Scaling language models: Methods, analysis & insights from training gopher. arXiv preprint 2rXiv:21 2021.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-325 2019.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-... hook. PhD thesis, Technische Universität München, 1987.
Shai Shalev- Shwarv-S Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2677 -6700, 2010.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852-7862, 2020.
Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the vc-dimension of a learning machine. Neural computation, 6(5):851-876, 1994.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pp. 35151-35174, PMLR, 2023.
Xinyi Wang, Wanrong Zhu, and William Yang Wang. Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning. arXiv preprint arXiv:2301. 1916, pp. 3, 2023.
Ziqiao Wang and Yongyi Mao. Two facets of sde under an information informaaiin--heoretie theoretic lens: Generalization of sgd via training trajectories and via terminal states. arXiv preprint urXiv:2211.1069/ 2022.
13

---

Published as a conference paper at ICLR 2025
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities large language models. arXiv preprint arXh::2206.0760 2022.
Noam Wies, Yoav Levine, and Amnon Shashua. The learnability of in-context learning. arXiv preprint arXiv:2303.07895, 2023.
T Wolf. Huggingface's transformers: State-of-ther tftt-offthheart natural language processing, arXiv preprint arXiv:1910.03771, 2019.
Jingfeng Wu, Difan Zou, Zixiang Chen, Vladimir Braverman, Quanquan Gu, and Peter Bartlett.
How many pretraining tasks are needed for in-context learning of linear regression? arXiv preprint arXiv:2310.08391, 2023.
Sang Michael Xie, Aditi Raghunathan. Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:2111.0000 2021.
Aolin Xu and Maxim Raginsky. tnformation-theoretiic analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Ruiqi Zhang, Spencer Frei, and Peter Bartlett. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.0999 2023a.
Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty in artificial intelligence, pp. 2364-2373, PMLR, 2022.
Yufeng Zhang, Fengzhuo Zhang, Zhuoran Yang, and Zhaoran Wang. What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization. arviv preprint arXiv:2305. / 19420, 2023b.
14

---

Published as a conference paper at ICLR 2025
Appendix
A
Table of Notations
16
B
Overview Two-Level Expectation
16
C
More Related Work
19
D
More Experiments
20
D.1
Experiments Linear Dynamic System
20
D.2
Experiments on GINC Synthetic Language Datasel
22
D.3
Experiments on Real-world Language Datasets,
E
Practical Implications
25
F
Complete Theorems: ICL Emerges from Generalization of Pre-trained LLMs
26
F.1
Generalization of Sequences: The First-Level Expectation
26
F.2
Generalization of Sequences and Topics: Two-Level Expectation
28
G
Proof of Theorems
29
G.1
Useful Definitions, Lemmas and Propositions
29
G.2
Generalization of Sequences: The First-Level Expectation
G.3
Generalization of Sequences and Topics: Two-Level Expectation
15

---

Published as a conference paper at ICLR 2025
A
TABLE OF NOTATIONS
Table Table of Notations.
Notation
Description
K
Number of pre-training topics
K'
Number pre-training topics used to compute topic-dependent prior
N
Number of pre-training sequences per topic
N'
Number pre-training sequences per topic used to compute data-
dependent prior
T
Pre-training Sequence length
T
ICL Prompt length
Wk
A pre-training topic with index
A ICL topic
Wpe
The set of pre-training topics
WicL
The set of ICL topics
Pw
Topic distribution, each topic W/ E Wpres w E WICL. is ii.d drawn from the topic distribution.
E
The л-th pre-training sequence under k-th topic
F
The subsequence consisting of the first / tokens of E
E
The set of pre-training sequences under the k-th topic, |E* N. The set of all pre-training sequences, = [ {Ek, kaa=1
E
[ = KN.
Er,
ICL prompt under ICL topic
FieE or IP( wx)
Data distribution, each pre-training sequence E Ek is i.i.d. drawn from the data distribution. Data distribution, ICL prompt Er, is drawn from the data distribution.
F. P(. (w)
k.n Fr+1
The 1-th token of pre-training sequence Ekmn, generated depending the prefix sequence E.."" The t-th token of ICL prompt ET
0
The parameters of the pre-trained LLM
0
The optimal parameters of the pre-trained LLM
P(
k.n
EN wk)
The true data distribution of token 2441 when given topic wy and the prefix sequence E."""
R.n.
Fo kmn
Lb wp)
k.n The prediction of token z441, made from the pre-trained model, when given topic wy and the prefix sequence Eth...
Pg Fo
B wk)
The prediction of token 2/4h, made from the optimal pre-trained model, when given topic wy and the prefix sequence E*K.
(f, Wpre)
The empirical loss of all pre-training sequences in E, see in Equation The loss of sequences in E* see in Equation
Lyg (0, wa)
L w)) L(0, Wpre) I(())
The loss of sequence E see in Equation
The first-level expected loss, take expectation over sequence, see in Equation 4
The population loss, take expectation over topic and sequence, see in
Equation 5
B OVERVIEW OF TWO-LEVEL EXPECTATION
Decomposition of Population Loss. No matter the inner outer expectation, the expected loss L()) incalculable since the data distribution P.,, and topic distribution Pw are both unknown (as introduced in Section 3.2 finite sequences and topies utilized optimize the empirical loss in
16

---

Published as a conference paper at ICLR 2025
Population
(Uppet Boand 260) Sez Theasnn 3.6) (Upper Misea Therrems
((() L(Ø) L(B, Wom) + L(B, Were) (8, Wpre)
(e, Wgm) LR(8, Wgen)
(8 Wpo Post emplrical loss
Port IV ge0
Part IIII g00...
Pact DI g00we
Ajd): The seyedl expectation ove
100 Wiril: Ancrupina 110, soy over rupies.
1/99 Wanl Aeee:.veennuaa 12.00, (0.00 tppess
Luf Avenging e toples K topics sequenoes
infinite topics & infinite sequinees [See Equatie
A topics & infinite sequences (Sez (q
K topics sequences
L(8 sog The finellodd expecatioo over sequence g as).
U/ga ua)) ua) sequences
Avenuins
12 my) jver
Rgel8,on) Avenging l6 vuj over N sequemers per uppic sqqunee lnngh
(8, suy:: The pantial fest-level expectation of 1209
[See Eustiser
L.]8, Avenging legenthmm likiiheed loss
Oprimization Objective (See Equxtie
Figure Overview of Two-Level Expectation. From a horizontal perspective: The first box (from top to bottom): according Equation g the population loss is decomposed into four parts. We ultimately obtain the upper bound of the population loss by separately defining the upper bound for each part. Combining Part I, Part and Part IIII we obtain Theorem 4.3 further combining with Part IV, we obtain Theorem 4.6 The second box: comparing L(Ø) and L(O, Wpe), we aim to describe the second-level expectation defined over topic. The third box: comparing L(0, wx) and (,, Wa), we aim to describe the complete first-level expectation defined over sequence. The fourth box: comparing L'g (0, wx) and Lg (0, wx). L' ( (0, wx) is a partial
first-level expectation likelihood loss, the optimization objective for token. From a vertical perspective, the formulas
k.n. conditioned EKK" The fifth box: Negative logarithmic token E
described in the four columns can be found in Equation 15
13 and 9 respectively. The first
column: the chain of T((A) > I(O0, wk). - I wx)
O w.). The second column: the
Tep (0, wk.. The third column: the chain of L' Wpre) 7 L'u (0, wk) 7 L'( wx) + (0,0,w)) The fourth column: the chain of
chain of [0,, Wpre) - T((A, wk)
(0, (w)
LE Wpre) + Lga (0, wx) + La (0, w))
practical). ICL ability can be measured by population loss, which can be decomposed by simply adding and subtracting three terms (0, Wpe). L'( Wpre) and L(0, Wpre) in Equation 8 A good ICL learner means a small population loss, i.e. small value four parts. The overview of two-level expectation is shown in Figure and the table of notations is shown in Table 2
L(0) L(0)- ((, More) + L(0, Wpre) - L'(0, Wpre)
genaoii
gen
L' L' Wpre) Le(0, Wpre)
LE(0, Wpre)
(8)
Part II: gen
Part I: empirical loss
Part I: empirical loss. For Part I, the training the LLM takes into account K topics and N sequences per topic. In this setting, finite topies and finite sequences could affect the performance
17

---

Published as a conference paper at ICLR 2025
of model that the training loss is called empirical loss (optimization objective). For detailed explanation empirical loss, the same as Equation !1
Lg Wpne
Σ
Lg wx):
N
LE (0, (0,wk)
Lgain n wk),
(9)
N
n=1
I. (0, (k,
Σ t=1
T (0, ux),
T
P(
F. wp)
L0, wk) logg
(o E Rnn
km
wk)
Part II seg-- Through Part I, we have obtained the empirical loss with finite sequences and finite topics. To address the first-level expectation, it's necessary to evaluate the expected loss over sequence, that is, utilizing an infinite number of sequences for each pre-training topic. Given that the sequential dependence token generation or prediction, where each subsequent token relies on the preceding tokens, our approach involves initially calculating the expectation of token #4+1 conditioned on Ex in this Part II. It's a partial generalization error for the first-level expected loss. This is followed by taking expectation over Ek in the Part III, thereby achieving the comprehensive first-level expectation over sequence Ek.".
According to the definition of KL divergence, the partial first-level expectation over sequences E, PC , (6, wx)] can be related to DKL (P(- EV"". wx) PP(- E"""" wx) i.e.
E kin (P-1e"- (0,, wx]] = = -P log P(1 km
E wk)
Po (a
kin El""" w.)
DRi. (P(. En ww)
[- E ww))
A L',(0, wk).
(10)
Then, taking average of all tokens in a sequence, N sequences per topic and K topics and combining with Equation 10 we define a partial first-level expected loss L' L'0 Wpre)
L'(0, Wpre)
Σ
L' (0, wx),
K
k=1
L/gz (6, (k)kk) = N
Σ
L'g (0, wk).
(11)
n=1
(0g (0,ww) T
(0, wk).
I' (6, wk) DKL (P(. E."", wk) Po EK""" wxx)
Finally, a partial generalization error for the first-level expected loss can be described as
gen L'(0, Wpre) LE(0, Wpe).
(12)
Part III gen Through Part II, we derived a partial first-level expected loss T'(0,, Wpe).. Subsequently, in this part, by taking expectation over E we will achieve a comprehensive first- level expectation prefix sequence F. Utilizing infinite sequences per topic rather than N
18

---

Published as a conference paper at ICLR 2025
Table 2: Table of Notations in Figure
Notation
Description
(f, Wpre)
(0, Wrre)
Averaging Lg (0. wx) over K' topics, see in Equation 9
Lgu (0, wx)
Averaging Lgt.. (0, w&) over N sequences per topic.
L (0, wx)
Averaging (0, wx.) over sequence length.
P( E .wk)
L (8, wk)
Negative logarithmic likelihood loss log
Fo (a [E _ua)""
(0, Wprre
L', Wire)
Averaging L/ (0, wx) over K topics, see in Equation 11
E (8, wk)
Averaging Lgg... (8, w&) over N sequences per topic.
T. ge. (0, wx)
Averaging (0, wx.) over sequence length.
(0, wk)
kin Taking the partial first-level expectation over token 1441 Fr w.).
IP(
I(O, Wpre)
L(O, Wpee) L(0, wk)
Averaging L(0, w&) over K topics, see in Equation 13 Taking the complete first-level expectation over prefix sequence
E E and token 2++1 ~ P- E wy).
(0, wk)
The partial first-level expectation over token 1++1
knn
L(O)
L(0)
Taking the second expectation over topic wn of L(0, ws), see in Equation T5
L(0, wxk
The first-level expectation over sequence E
sequences, the first-level expected loss L(0, Wpre) can be more concretely described as
1
L(0, Wpre)
L(0, wk),
K
k=
L(0,, mx) TE pt [T' (0, wx)]
(13)
Compared with L(, Wire) and (0, Wpee,, the difference lies in the second line Equation 13 and II with infinite sequences N sequences. This difference represents the complete generalization error of sequences which can be denoted as sen
gen L(0, Wpre) L'(0, Wpre).
(14)
Part IV topic In this part, we further consider the second-level expectation over topic, that is, considering the population loss with infinite sequences and infinite topics. According to the difference between Equation 13 and population loss lies in the number of topics with infinite K, we have the population loss,
L(l) E,,, [L(0, wx)]
(15)
After which ICL will emerge from the good generalization of sequences and topics. It can be denoted as gonie
gen logic
I(()) T.(0, Wpre).
(16)
C MORE RELATED WORK
From Multi- Mulki-Task Learning Meta-Learning. Although drawing inspiration from the assumption of an unknown task distribution in meta-learning analysis, it is worthy to emphasize that ICL generalization analysis under auto-regressive next-token prediction cannot be equivalent to meta- learning generalization. We conduct our analysis under the unique setup of auto-regressive pre-trained LLMs. The prompt token- -eeendddeyndnccy issue brought by auto reggrssgeee language modeling implies that cannot directly apply the general meta-learning analysis to ICL generalization analysis. For instance, the study in Bai et al. (2024) directly applied the general approach meta-learning, assuming that prompt consists of N i...d. samples, which is unreasonable for AR-NTP problem
19

---

Published as a conference paper at ICLR 2025
investigate. For prompt (Z1, .T) under AR-NTP, do not require 21 IT to be independent of each other; instead, subsequent tokens depend on previously generated tokens. As mentioned in Section [42 addressing prompt dekenddden is one of the significant contributions and challenges compared to other works, including meta-learning works in non-ICI. domains. This is the key distinction from traditional meta-learning approach.
Generalization Analysis. Understanding the generalization error in learning algorithm which meansures the model performance unseen data with population loss, has led to the development of several classic methods for establishing its upper bounds. Among these, uniform convergence (including VC dimension, Rademacher complexity) (Bartlett et al. 2017 Shalev-Shwartz al.
2010:Vapnikk et al.] 1994), algorithm stability (Bousquet& & Hlisseeff [2002] Feldman & Vondrak
|eldmma
2018 Hardt al. [2066] Lei & Ying 2020; Zhang al. 2022), information cemmmtiion-thoretice bounds (Russo & Zou| 2016 2019; Xu & Raginsky (017). and PAC-Bayesian (Catoni 2007, Dziugaite & Roy
2017, McAllester 1998) are prominent techniques. For VC dimension, depends solely on the
hypothesis class which offers the worst-case analysis. For Rademacher complexity, it depends both on the hypothesis class and on the unknown distribution which can be understood as an average-case analysis. The above obtained bounds almost depend on the size of hypothesis space, and become vacuous hence may be unable to explain generalization deep learning with over-parameterized neural network (Nagarajan & Kolter 2019: Zhang al. 202I). Additionally, compared with algorithm stability theory, it considers worst-case and fails in analyzing the relationship between input data and output model. Therefore, turn to the PAC-Bayesian approach for its unique data-dependent and hypothesis space-independern analysis. In our work, we specifically incorporate topic-dependent prior within the PAC-Bayesian framework, adding a novel dimension to this analysis. Furthermore, by detailing the KL divergence when considering the optimization process, we obtain optimization gegoorthm--eppeddee generalization bound, naturally combining the advantage of algorithm stability technique.
D MORE EXPERIMENTS
D.1 EXPERIMENTS ON LINEAR DYNAMIC SYSTEM
We conduct numerical experiments of linear dynamic system. Our experimental setup follows Li ct al. [ ICL experiments are trained and evaluated using the same GPT-2 architecture with 12 layers, 8 attention heads, and 256 dimensional embeddings, on NVIDIA 3090 GPUs.
For eartially-observed dynamical system, the mathematical model can be represented by state and observation equation. Consider the state equation x++1 Wr, + G. where xe represents the state vector at time f in a d-dimensional space. This is analogous to the tokens in our analysis. W denotes the state transition matrix and G. is the process noise satisfying (N, La). The observation equation is given by Vt+1 = C where C' is the observation matrix, indicating that only partial dimensions of the state vector observable. The uniqueness of different topics is reflected in the parameters W and C. Within this linear dynamic system setting, we examine how the number of pre-training topics (K), the number of sequences per topic (N), and the sequence length (T) significantly affect the generalization performance of auto-regressive LLMs. Additionally, we highlight the advantages of both deta-deeendent and topic-dependent priors.
The Comparison of Overall Loss and In-context Learning Loss. Before embarking on our main experiments, we conduct a preliminary comparison between the absolute values of the overall loss and the in-context learning (ICL) loss. In the pre-training phase, we predict all tokens in sequence and consider the average of these predictions as the overall loss. According to our theoretical proof, this average prediction loss can be naturally generalized to the ICI. phase to represent the ability of ICI. Although in more scenarios, the focus often shifts to the predicted outcome of the last token, here the prediction loss of the last token is denoted as ICL loss. In the left of Figure 4 our observations reveal that the ICL loss is consistently lower than the overall loss with a different number of sequences per topic. It's because the prediction loss decreases as the sequence length increases, corresponding to our theory. Consequently, our theoretical bounds hold validity and significance under both overall and ICL loss assessments.
Separate Effects of K, N and T. In our experimental design, we manipulate the variables K, N, and T' independently and the experimental results are shown in Figure In Figure 5(a) with fixed
20

---

Published as a conference paper at ICLR 2025
0.33
Overa Icas
0.
Complets net oftecie eg)/ihcion11
sitestof iop lggatppiiies
0.24
0.0
0.7
0.23
0.6
0.15
0.69
0.3
0.28
0.2
0.53
0.53
0.3
15
2000
4/00
6035
Sequences per topic
Global stop
Figure 4: Experiments on Linear Dynamic System. Left: The comparison of overall loss and in- context learning loss. Right: The comparison of experiments conducted on complete topic set and subset of topics.
3.59
10% 1ese
IoglaTogical
So Snnguencce per topk
Soquintce lnngth
(a) Vary number of topics.
(b) Vary number of sequences per topic.
(c) Vary sequence length.
Figure 5: Experiments on Linear Dynamic System: The effect of the number of pre-training topics (K), the number of sequences per topic (N) and sequence length (T).
number of sequences per topic and sequence length (T 11) for each line (N 10, 20, 30, 40), we vary the number of topics within the range of K = 210 ~ 2!? As K increases, it's noticeable that the ICL loss consistently show a downward trend across all four lines. Furthermore, the sharp drops in ICL loss observed in these cases suggests that LLMs exhibit emerging abilities when the accumulated topic count reaches certain thresholds. In Figure 5(b] holding the number of topics and sequence length (T 11) constant for each line (with topics set at K 2 21,4222, 221), we adjust the number of sequences per topic, varying it within a range of N = 5 ~ 40. Comparing the four cases, the ICL, loss diminishes as N grows. Notably, in cases with less sufficient topies (like K K=213 213 and 214), a larger N leads to significant reductions in ICL loss. Specially, the decrease trend of ICL loss is particularly evident in the magnified view of the case where K = In Figure 5(c) maintaining a constant number of topics (K = 214) and sequence per topic (N = 40). we modify the sequence length, allowing vary within range of T 11 ~ 51. We can find that ICL loss clearly decreases as the sequence length grows.
The Advantages of Both Data-dependent and Topie-dependent Priors. As introduced before. data-dependent and topic-dependent priors provide a chance to make the generalization bound computable. To illustrate this, we take the example of topic-dependent prior and two experiments are conducted: one with a complete set of topics (K = -21) and another with its subset (K' = 215). Observing the results in the right of Figure 4 both training processes eventually converge to nearly identical steady states. This suggests that using subset of topics to obtain topic-dependent prior in preliminary experiments yields a prior that is closer to the posterior than a randomly selected prior. Then for the KL divergence between prior and posterior distribution of model parameters in our generalization bounds, assume these distributions are either uniform or Gaussian allows us to derive the closed-form expressions for the KI. divergence.
21

---

Published as a conference paper at ICLR 2025
sipl
Dequeroes sigle
Saparcoa tepl
Saggarcaa par Sipl
13
(a)
(b)
(c)
(d)
CAR
Tymi
680
Soepancenperteet
Sequances partept
Secpetcas our malt
(e)
(f)
(g)
Figure 6: Experiments on GINC Synthetic Language Dataset.
D.2 EXPERIMENTS ON GINC SYNTHETIC LANGUAGE DATASET
Inspired by Xie et al. 22021), we perform experiments on a synthetic language dataset GINC to verify our theoretical results.
GINC Dataset. GINC is a small-scale language dataset generated from a uniform mixture of
Hidden Markov Models (HMMs) over a family of topies/concepts (Xie et al.) 202T). The generation steps are as follows: (1) Prepare transition matrix for HMMs: The topic/concept determines the state transition matrix in HMM. For simulation, the transition matrix is randomly generated for each topic (each HMM), respectively; (2) Prepare vocabulary: The vocabulary is generated combinations of letters starting from 'a' to 'z,, 'aa' to 'az', and so on. We can obtain vocabularies with different sizes; (3) Prepare memory matrix: A unique matrix is created that records the mapping of vocabulary and state; (4) Generate sequences: Given a fixed topic and an initial state, generate the next state based on the transition matrix, and then obtain the observed token using the memory matrix. In total, each sequence is sampled from a random HMM in the family.
Model and Hyperparameter Settings. Our transformer model based on the GPT-2 architecture with 4 layers, 12 attention heads, and 768-dimensional embeddings (Wolf) 2019). We train the model for 20 epochs using the A optimizer with a batch size and linear learning rate schedule. The schedule includes a warmup phase of 1000 steps, up to the learning rate of 8e-4. Notably, we adopt a large portion of the code from Xie et al. (2021). All experiments on GINC are conducted using a single 24GB NVIDIA GeForee RTX 3090.
In the following, We empirically explore the separate effects of the number of topics (K), number of sequences per topic (N), sequence length (T) and prompt length (Tp). We detail K {10, 20, 30), N E (20, 40, 60, 80, 100}. T E (1280, 2560, 5120, 10240), T, E {48, 80, 128, 160], where ranging T with directly masking the token that exceeds the specified length and do taking special consideration. In totoal, we arrange groups of comparative experiments to verify that increasing N.N.T, T, individually improves the model's generalization performance as demonstrated in our Theorems. Additionally, we discuss the effect of vocabulary size and provide an interesting case involving with failed ICL.
Observation (1): Separate Effects of K, N,, and and
Tp. We first present four groups of experiments ((a)))(d) in F In Figure 6(a) For pre-training data, take = 10 topics and generate N e {20, 40, 60, 80, 100 pre-training sqquences/documents per topic, in addition with varying sequence length E {1280. 2560, 5120, (22 Then with the pre-trained model, test ICL performance on the prompt with Тр 128 prompt length. Each line exhibits growing trend, indicating better
22

---

Published as a conference paper at ICLR 2025
00
Arournyy
yime
200n pirsvet
poRy, JeESTar
10
11
175
155
201
Topica
logie Sequences per topici
Sequence langth
(a)
Nurcors
5.0
lighti4
Triiting
3.00
5004
1000
3000
2000
vide
seea 1981 idda mabe 2000 1990
(d)
(e)
Figure 7: Experiments on Real-world Language Dataset.
generalization performance with increasing sequences per topic. Comparing the four lines from bottom to top, a larger sequence length also brings better generalization. From Figure b(b)oord we vary K E {10, 20, 30}. Under each K, keep sequence length T = 10240, with varying N E {20, 40, 60, 80, 100} and T. (48, 80, 128, 160). Combining these three groups of experiments, we validate the effects of K, NN, Tp on generalization, closely aligning our Theorems.
Observation (2): Effect of Vocabulary Size and an Interesting Case that ICL Fails. In Figure
6(b) (((e) and 6() We vary the vocabulary size within (50, 100, 150]. With fixed K = 10 topics, we vary N E 220, 40, 60, 80, 100} and Tp E {48, 80, 128, 160]. Apart from the observations similar to Figure 6(b) 6(d) about N. we surprisingly find that a larger vocabulary size leads to higher ICL prediction accuracy. This aligns with our understanding that the number of possible token combinations in sequences grows with increased vocabulary size. It also implies that more diverse training data improves ICL performance. This is further implicitly supported by our theory, which suggests increasing the training sample size as much as possible ensure sample diversity. Furthermore, we conduct an interesting experiment in Figure [o(g) When the pre-training data contains random transitions, the model observes all token transitions, yet ICL fails. This suggests that the pre-trained models cannot extract information when data distributions do not match the topic, thus failing to achieve ICL.
D.3 EXPERIMENTS ON REAL- WORLD LANGUAGE DATASETS.
We further perform experiments on real-world language datasets, inspired by (Min al. 2021
Wang
et al. 2023).
Datasets, Model and Hyperparameter Settings. In the pre-training phase, we consider a mixture of a series of language tasks, mainly including 20 datasets. Classified by task types, including sentiment analysis (glue-sst2, pooemsenntment pola-polarity and emotion), linguistic analysis (glue- cola, blimp), text classification (ag deg_eews, db ethos), question answering (tweet_qa) and commonsense reasoning (swag). Different datasets are considered as different topics (reflected in K from our framework). In ICL phase, test ICL performance with different datasets. All the datasets are obtained from Hugging Face. We train the GPT2-large model with a batch size of 16 and learning rate of le-4 for total 30,000 iterations. Notably, we adopt large portion of the code from
23

---

Published as a conference paper at ICLR 2025
Wang et al. (2023). All experiments are conducted using four 24GB NVIDIA GeForce RTX 3090 and 40GB A10 GPUs.
empirically explore the separate effects of the number of topics (K), num- ber of sequences per topic (N) and sequence length (2). By detailing K E (5, 10, 15, 20}. N {2$, 2 2 214), T E {48, 64, 128, 256), we arrange groups of comparative experiments to verify that increasing K, ., T individually improves the model's generalization performance as demonstrated in our Theorems. Additionally, we observe the impact of optimization process and prior model initialization.
In the following,
Observation (1): Separate Effects of K, N and T. Figure 7(a) we investigate the impact of varying the number of topics K. Specifically, varying K E (5, 10, 15, 20), keeping fixed N = 24 sequences per topic and sequence length T = 256. The results show that for ICL test prompts from different datasets, increasing K consistently improves ICL accuracy, expected from our theoretical analysis. In Figure 7(b) we examine the effect of varying N E f2 2 ,21),, with fixed K 20, T 256. We observe that increasing N leads to better performance in ICL phases, reinforcing the idea that more sequences per topic enhances model generalization and further benefits ICI., Similarly, in Figure 7(c) explore the impact of varying T {48, 64, 128, 256) while 2 Increasing I" also brings better ICL performance.
keeping fixed K = 20 and N
Observation (2): Optimization Process. Through continuous optimization trajectory analysis, our generalization bounds are also optimizationndependemn Thus beyond the influence of training data, we investigate whether optimization properties align with our theory. Figure 7(d) we present four different training processes where N {2 20 22,, is varied, with fixed K 20 and T = 256. This setting mirrors Figure 7(b) where we have demonstrated that increasing N leads to better generalization performance. Furthermore, we observe that larger N also brings faster convergence during training. This aligns with our Theorems that with a smaller number of training iterations to converge, i.e., the model trains faster, and further generalizes better. Similarly, Figure takes same configuration with Figure 7c)), which also exhibits the connection between optimization and generalization that 'trains faster, generalize better'.
takes the
Observation (3): Prior Model Initialization. Based on our generalization analysis with a data- dependent prior, we propose that leveraging prior model initialization could accelerate model training. Specifically, consider the following setup: our training data consists of K 20 pre-training topics, N 214 training sequences per topic and sequence length = 256.
Step 1: Train the GPT2-small model for 15,000 steps using K 5 pre-training topics,
N = 24 training sequences per topic and sequence length T = 256.
Step 2: Transfer the weights from GPT2-small model to the corresponding weight matrices of GPT2-large, ensuring dimension compatibility. Initialize the weights randomly for the additional transformer layers in GPT2-large.
Step 3: Train the GPT2-large model for an additional 30,000 steps using the full pre-training data (K 20, N 214, T 256)
According to our experimental results, the random initialization regime with all pre- pre-training data requires nearly 7 hours on four A100 GPUs to complete 30,000 steps. However, under the prior model initialization regime, where smaller model is used for warmup and serves as the prior model initialization for the larger model, training the GPT2-large model takes only 4 hours for 30,000 steps on four A100 GPUs under the same setting of K, N,T (with 0.5 hours needed for training the GPT2-small model for 15,000 steps).
Furthermore, as shown in the optimization loss curve in Figure 7(1) the prior model initialization not only accelerates training but also stablizes the training process (cspecially at the carly stage), leading to comparable leveraging prior knowledge can contribute to the training process and performance, supporting the KL term in generalization bounds and presenting more practical insights.
improved model performance. This approach demonstrates how effectively
24

---

Published as a conference paper at ICLR 2025
E PRACTICAL IMPLICATIONS
We first provide guidance for the quantitative selection of K, N and T based on the upper bound of expected loss described by theoretical results.
Increase the Number of Pre-training Topics. For the ICI. ability of LLMs, it relies on examples within given prompt to adjust its behavior, so more topics (or tasks) provide richer information and learning opportunities. As the number of tasks increases, the model able to learn from a broader range of contexts, thereby enhancing its generalization ability. This is different from general multi-task learning that aims to learn multiple tasks simultaneously and if the tasks are too different unrelated, it may lead to task interference, thereby reducing overall performance (i.e.. under multitask learning, having more topics does not necessarily lead to better model generalization performance). Instead, our defined topics satisfy the assumption of topic distribution, implying correlation between pre-training and ICL topics. This also leads to our conclusion that 'more topics lead to better model generalization performance', which differs from general multi-task learning. Furthermore, when increasing the number of topics, our goal is to cover as many different types of topics as possible, to guarantee the diversity of topics, which will enrich the model's 's learning experience and help the model better understand new contexts with unseen topics. It potentially explains why one can improve ICL performance by selecting appropriate kind of 'few-shot" examples or exemplars to optimize performance (i.e. retrieving shots best suited to the topic/task).
Expand the Scale of Pre-training Sequences. Using large amount of training sequences per topic can provide more topic information, which helps the model better understand the language patterns for this topic. This guarantees the ability to perform well on the new sequences with a topic. This opinion is similar to the classical machine learning problem, where more training data helps the model perform excellently the test data.
Increase Sequence Length or Prompt Length. Training the model process longer sequences can enable it to better understand the context and details of lengthy texts, especially for topics or tasks that require in-depth understanding of long articles, such text summarization and extended question answering. We hold that longer sequence length help the model maintain coherence and completeness of information when dealing with complex problems.
Furthermore, in our PAC-Bayesian generalization bounds, the key term (K v) surely offers possibilities quantify the information contained in the model and data, thereby providing practical guidance for model training, training data selection and deduplication.
Practical Guidance for Model Training Prior Model Initialization. Typically, randomly initialized parameters follow uniform or standard normal distributions, which lack any specific information about the data. In contrast, during pre- pre-training, we begin with small-scale subset of data to train a prior model. The parameters of this prior model can then serve as an informative starting point for longer and more sufficient training with greatly-large-scan pre-training data. When using a data-dependent prior rather than random initializations, this results in a smaller D (u || v). which in our theorems represents the distance between model posterior μ and prior contributing to a better generalization. Furthermore, a lower DKL (μ || v) also enhances the optimization, by detailing this term with continuous optimization trajectory analysis. Specifically for example in Theorem 4.6 when with lopic-depended prior vJ, D (p vy) RS o²C Nparamm T/K/ where
C( N(N T = 8 c38 - "apless)). ). A smaller DKL(H4 || vy) means that this favorable initialization brings a stable training (with reduced gradient norm σ) and avoids exploring the entire parameter space (with fewer optimization iterations T"). This aligns with our understanding that data patterns guide the model toward appropriate directions during training, reducing the likelihood of encountering unsuitable local minima or saddle points.
In total, using a data-dependent and topic-dependent prior for model initialization can significantly improve training stability, model convergence, and generalization. This approach is particularly useful in multi-task learning, where it helps establish relevant priors for each task/topic in advance. Although employing more strategies to choose the subset K' can further refine the prior, excessive refinement may introduce new computational costs and efficiency trade-offs. We emphasize that even
25

---

Published as a conference paper at ICLR 2025
without careful data selection for prior model learning, data-dependent prior generally outperforms random initialization. Particularly, when random initialization does not yield good performance, a data-dependent prior model may provide new opportunity.
Practical Guidance for Training Data Selection and Deduplication. is well-known that the vast amount of data obtained from the internet serves input for compressing world knowledge into LLMs (Delétang et al., (023). The data quality among redundant data determines the upper limit of the performance of LLMS. Therefore, considering data-dependent pre-training and ICL generalization framework has immense potential for guiding data. In our theory, to explicitly show the impact of data, we adopt data-dependent and topic-dependent prior V. and further detail DKI(# vJ) with optimization analysis. We have discussed this in detail before: in PPractical Guidance for Model Training' part, we emphasize the advantages of prior model initialization over random initialization in model training. Here, we aim to further explore its guidance for training data from the perspective of compression.
Specifically, we select a subset of size K' from the K pre-training topics to estimate prior distribu- tion. If a smaller K" can estimate prior that is very close to the posterior distribution, it indicates that the information from the K topics can actually be compressed into smaller subset of K" topics. This reflects the compressibility of the data, and can thus backward guide pre-training data to further undergo data selection and deduplication, such as through topic clustering, data diversity, or information gain metrics (e.g., DKL( (D( || (D))), ), this value is small, the data block D; is considered redundant and can be reduced in weight or removed to decrease the model's reliance on redundant information.) The reprocessed pretraining data may exclude some noise interference, further improving model performance, saving computational resources, and facilitating training for new models.
F COMPLETE THEOREMS: ICL EMERGES FROM GENERALIZATION OF PRE-TRAINED LLMS
In Section 4 we have introduced Theorem 4.3 and 4.6 Here, in the following Section F. we divide
Theorem 4.3 iint two parts: Theorem F.1 and Theorem F3 Similarly, in the following Section F.2
we divide Theorem 4.6 into two parts: Theorem F.5 and Theorem
F.1 GENERALIZATION OF SEQUENCES: THE FIRST-LEVEL EXPECTATION
Under finite (K) pre-training topics, we consider the first-level expectation where infinite se- quences per topic are utilized. It describes comprehensive learning for each pre-training topic the ideal case so that the pre-trained model can perform excellently on the seen topics in ICL phase. For this first-level expected loss L(0, Wire) with two partial expectation, it's represented
as K -4=1 E E DKI. (IP(- B ww) PP EA""" ,ww)] (details see in Equation 13 The
following Theorem will give the upper bound of L(0, Wp.e).
In the following Theorem, we first give an general result that KL distance between posterior μ and prior is kept in the upper bound of the first-level expected loss. Here, the prior is a general prior distribution rather than data-dependent prior.
Theorem F. (Generalization Bound of the First-Level Expected Loss). Let the auto-regressive LLM Fo be the empirical solution of Equation D and P(- w) denotes the true data distribution under topic w. Under Assumptions 4.11 for any 0 < 8 < 1, with probability at least 1- - 8, the first-level expected loss with K topics and infinite sequences per topic, denoted by L(0, Wpre) (see in Equation
4 or Equation 13, satisfies,
E, [L Wpxe 1000=00 O log log1/5
KNT + +V KNT DKL 1) + log 1
Copt
where Copt is the optimization error (see in Equation 3 μ and v are the posterior and prior distribution of model parameters 6, respectively. K, N and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation 1
26

---

Published as a conference paper at ICLR 2025
Remark F.2. Theorem F.1 reveals that when considering the first-level expectation over sequences, the expected loss achieves VKNT rate. This indicates that an increase in the number of training topics (K), the number of sequences per topic (N), and the sequence length (T) leads to a reduction in the first-level expected loss, aligning with both intuitive understanding and empirical evidence. Note that the length of different sequences Tk,n vary from each other which implies the potential for sampling imbalanced sequences from various topics. Moreover, the number of sequences Nu per topic can also be different. If sequences under specific theme are notably short, balancing can be achieved by sampling a greater number of these sequences, i.c. increasing Ng. ensuring that the product of Nr, for all themes maintains a level of equilibrium. This approach ensures that the final representation of N7 conveys an averaged meaning. If certain themes yield fewer sequences, it indicates lower probability of occurrence for those themes. Under the framework of theme distribution (as defined by the second level expectation), the contribution of such themes (smaller n.) NT won't be dominant. In conclusion, themes with higher occurrence probabilities are predominant and more sequences can be more readily sampled. Even if these sequences are shorter, we can compensate by sampling more sequences achieve an average level NT which corresponds to our result.
In the next Theorem, we carefully consider data-dependent prior (Li et al., 2019), replacing (K || 1) with (1 || Uy) in Theorem F.1 and further deriving a more detailed upper bound.
Data-Dependent Prior. We employ the following method for generating a data-dependent prior et. 2019). Let J include N' indexes uniformly sampled from [N] without replacement and I is [V] J, pre-training sequences under fixed topic Wg into two parts E and E Under all pre-training topics, we have E₁ = { [E) K
I==1 and E, = ={ { The prior distribution of model parameters @ depends the subset F,,, which is denoted by Vy and the posterior distribution of 9 depends on Ej denoted by μ.. Thus, a parallel training process with E, are conducted, and after that, data-dependent prior V/ will be obtained. We emphasize that extracting a portion of training data to learn the prior distribution of model parameters has significant implications. Specifically, this approach allows the prior adapt specific features and trends in the data, enhancing the model's ability to capture and learn from these nuances. In addition, even if we sacrifice portion of the training data, the prior will lead posterior distribution that better aligned with the actual data distribution. In high- dinee-iiensional spaces, a data-dependent prior provides a more informed starting point.
Theorem E3 Data-Dependent and Optimization- Diiiiizzttioo-eeeddeentt Generalization Bound of the Lerst-Level Expected I Loss). Under the conditions maintained in Theorem F. Aand Assumption 4.2 when con- sidering date-dependent prior μ.,, for any O < d 1, with probability at least 6, the first-level expected loss with K topics and infinite sequences per topic, denoted by L(0, Wpre) (see in Equation 4 or Equation 13). satisfies,
By [L Wprc =0
1/8 K(N - N'YT V
1
(DKelA [1))) + log 1) Caps
K(N
then detailing the term DKI(U |1 uz). L(0, Wmn) further satisfies,
K(N -N'TT +
log 1/8
\
K(N- N
1
L2C
Npman
N
T")
+ log
1 8
- Capt
(17)
where C(( 1 .T') T 2 (1-c (1-c-mep(es) (xp(oF5)
Ny
). Capt is the optimization error (see in Equation
3
K. N N(N') and T denote the number of topics, the number of sequences per topic and the sequence
length utilized in the optimization process of Equation I T" denotes the total training iterations. N Nparam denotes the number of model parameters.
Remark F.4. The PAC-Bayesian generalization bound of the first-level expected loss can be bounded by the KL divergence between the distribution of the model obtained by the real training process and data-dependent prior, i.e. DKL(H (14 || p.). Analyzing the continuous Langevin dynamic of model parameters 8. Fokker-Planck Equation is used to describe the KL distance between two probability density function of two optimization processes, furthermore, referring to the proof of Lemma G.5 in Li et al. (2019) we demonstrate that the integral of the gradient difference of
27

---

Published as a conference paper at ICLR 2025
L2 . Nppan NO
VLL, (O,, Wpree VLE, (0,, Wpre) Consequently, we bound DKL (n us) with which is related to optimization algorithm. As T" increases, C(3, T*) increases, i.e. the generalization error increases. This reflects the influence of total training iterations T" on testing loss, corresponding to the classical viewpoint 'train faster, generalize better' (Hardt et al. 2016 Lei Ying. 2020 Zhang et al., ) In addition, the constant I, related to optimization reflects that the upper bound of the gradient of AR-NTP loss also impacts the generalization performance. Observing the derived
upper bound, we notice that the last term, V
log 1/8
VK(N-NIT' provides similar insights to
VKNT in Theorem F.1 In total, by detailing the KL divergence, we establish more refined bound
which is data-dependent and optimization-deeendeen..
In summary, the proof of Theorem 4.3 is provided in Appendix G.2.1 and Appendix G.2.2
F.2 GENERALIZATION OF SEQUENCES AND TOPICS: TWO-LEVEL EXPECTATION
Up now, we have analyzed the first-level expected loss with K topics and infinite sequences per topic. In this ideal case, the pre-trained LLM can perform excellently on the new test prompt under seen topies in ICI, phase. In this section, we use similar techniques to further consider the second level expectation with infinite topics, so that the pre-trained LLM could perform well on unseen topics under the topic distribution assumption. At this moment, ICL emerges from the generalization of sequences and topics.
We first give general result in Theorem F.5 with DKL (p(0) | F3 by incorporating infinite topics.
x (0)), which extends beyond Theorem
Theorem F.5 (Data- aata-Deeenndet and Optimization-Dependee
Generalization Bound of the Two-Level
Expected Loss). Let the regressive LLM Pa be the empirical solution of Equation [ and IP w) is the true data distribution under topic w. Under Assumptions 4.7 4.2 a.d 5) for any 0 < 1,
with probability at least 1 - 6, the two-level expected loss (population loss) with infinite topics and infinite sequences per topic, denoted by L(0) (see in Equation 5). satisfies,
By([(0)= (0(00)101 ol KT,
+ +ogg :) + UWW pre, K,N,N',T)
T) denotes the right hand of equality O or equality 17 I and v are the posterior and prior distribution of model parameters 0, respectively. K, N N(N" and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation !]
where UWW
Remark F.6.
The term U'Wrre N,,,N', T) comes from Theorem F.3 whose analysis can refer J. illustrates the impact of
to Remark F.4 As for the first term in the result, with order O
VKT,
training with finite number of topies on the model's predictive ability for unseen topics in ICL. In addition with larger prompt length, ICL emerges much casier from the generalization of pre- pre-trained
LLMs.
Next, we propose topic-dependent prior whose core idea comes from data-dependent prior (Li et al. 2019), i.e., portion of K topics will be used for calculating model prior and other topics will be used for obtaining posterior. (K || T) in Theorem F.5 will be replaced by DRL. (p I| TJ) and further derives more detailed upper bound. Since then, we can provide data-dependent, topic-dependent and optimization algorithm- dependent generalization error bound of the two-level expected loss.
We employ the following method for generating a topic-dependent prior, similar to data-dependent prior (Li et al. 2019). We split topics into two parts and let J include K" indexes uniformly sampled from K without replacement and let be [K] J, then the total sequences are divided into E E* hew,,., , and EJ = (E*) kkEW Assume that the posterior distribution of model parameters 9 depends on E' denoted by p and the prior distribution of 9 depends on the topic subset F.J, which is denoted by π. A parallel training process is performed with E based on the same LLM architecture, and after that, tepic-dependent prior π, will be obtained.
Yopic-Dependent Prior.
Theorem E.7 Patta-Depeddett of the Two-Level Expected Loss). Under the conditions maintained in Theorem F5 and Assumption
and Optimization Appimization-Depeedentt Generalization Bound
28

---

Published as a conference paper at ICLR 2025
when further considering topic-dependent prior, for any 0 < 6 < 1, with probability at least 8, the two-level expected loss (population loss) with infinite topics and infinite sequences per topic, denoted by L(0) (see in Equation D satisfies,
4.5
B [I()]] (2(0))]=11 =o
1 (K (L-K'S (KYK' (DRL I| (s) + log 1) UWW K K,N,N'
then detailing the term DRI(K Us), further satisfies,
olV (K K'YT
(Q²C( MAmme: T + log 8
1
U(Wpre K, N.N,N,T)
K"
where C( C(
T") c (1-E captop2)
U K, K,N,N' denotes the right hand of
equality 6 or equality 38 I and VJ are the posterior and topic-dependent prior distribution of model parameters 0, respectively. K(K"), (N') and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation | T denotes the total training iterations. Nporom denotes the number of model parameters.
Remark F8. In Theorem
F.7 we establish a comprehensive upper bound of population loss combin-
ing the results in Theorem
and F.5
In summary, the proof of Theorem 4.6 is provided in Appendix G.3. and Appendix G.3.2
G PROOF OF THEOREMS
G.1 USEFUL DEFINITIONS, LEMMAS AND PROPOSITIONS
Definition G.1 (Entropy). For random variable which takes value in and its probability distribu- tion is the entropy of random variable 0 is
H(0)
Σ ((0) log ((0) Eggz [- log (+))
dE
Definition G.2 (Kullback-Leibler Divergence). The Kullback-Leibler (KI.) divergence between two probability distributions y and v is defined by
m(0)
DKL (p v) Ea-n log
v(0)
Lemma G.3
representation in Belghazi et al. (0188) Theorem 1). The KL
divergence between probability distribution μ and obeys the following dual representation:
(RI( v) sup T:A-2
[Tp log(EE((??))
where the compact set A C Rd is the support of distribution μ and and the supremum is calculated across all functions for which both expectations are finite.
Let F be any class of functions T A R satisfying the integrability constraints of the lemma.
Then for any defined function T, it's straightforward to get the lower-bound of the KI. divergence between μ and w
(k || v) 2 E. [r] [og((E,(e")))
which would be used the proof of Theorem F.I
Definition G.4 (Total Variation Distance in Levin & Peres (0077). The total variation (TV) distance between two probability distributions and on events set B is defined by
Drv v) = max In( B) v(B).
BEB
This definition is explicitly probabilistic: It quantifies the divergence between μ and v as the maximum disparity in the probabilities assigned single event B by the distributions.
29

---

Published as a conference paper at ICLR 2025
Proposition G.5 (Total Variation Distance in Levin & Peres (2017). Let μ and be probability distributions on A. Then
1 Drv(u, 2 aed
(u(a) v(a)).
Proof. Let be any event and event B {a : (uaa) 2 v(a)). Since An (AN B9), then we have
p(A) v(A - ( B) v(An B)
Since including more elements B cannot decrease the difference in probability, have
(AABB v(An B) $ ((B) v(B)
Combine the above two inequality, we have
((A) v(A) S PBB) v(B)
Similarly,
((A) m(A) Sv(B) m(B)).
Thus
Drv(n,)) [m(B) - vBB) + xBB) MBB)) = 2
Σ
(m(a) - v(a))
aEA
Lemma G.6 (Lemma 22 in Agarwal et al. (2020)). For any two conditional probability distribution and v, we have
log ((3)1z) 2 (r) )
Drv (((-)), S -2oog E ()) exp
2
This lemma provides an upper bound on the total variation distance, which is related the expectation of the logarithmic ratio of two conditional probability distributions. It would be used in the proof of Theorem
M
Lemma G.7 (Upper Bound of KL divergence). For any conditional probability distribution μ and v, if p(a)
v(a) S C, we have
2C log C (KL(H(a) v(a)) < C-1 Drv(H(a),
This lemma provides the relationship between KI. divergence and TV distance.
Proof. Let ft) logt t, g(t) = = - 1/. According to the definition of KL divergence and TV distance (see in G.2 and G.5), have
(KL(H(a) p(a)) = Eo-n log u(aa) v(a)
(((a)
= Eary
f
v(aa
= Σ u(a) 1 v(a)
(u(a)
((y)) =
2 Σ u(a) v(a))
= E
Eany
2
u(a))
2
v((a)
For < <1tg C( 1), we have
f(t) sup OC1sC.111
logt
Hlgg
sup OC g(t)
| -1
sup 1<t5
Based on the derivative chain rule, we have that if 1 <t C, that
glogt t-1
Clog < c-1-
Thus, we conclude
2C C
(KL(u(a) v(a))
C-1 v(a))
30

---

Published as a conference paper at ICLR 2025
Definition G.8 (Fokker-Planck Equation in Mou et al. (2018)). Let स. be the probability density function of distribution Pt, then Tokker-Planck Equation describes the evolution of Ty.
Om, 1 A Ot A.. V (Te V..VVe(0011 Wpee)
where V is gradient operator and A is Laplace operator.
Definition G.9 (Gradient Langevin Dynamics and Continuous Langevin Dynamic Li et al. (2019) ).
LLMs perform Stochastic Gradient Descent (SGD) optimization algorithm to update parameters in order get the minimum ò. SGD can be viewed gradient descent addition with gradient noise
between full batch gradient and singlc/mini-batch gradient (Wang & Mao (022). The full batch
gradient with 0 can be denoted 1gg(0=> Wpre), and assume that the gradient noise follows an isotropic Gaussian distribution NO, ( thus the training dynamic of LLMs can be defined as
- 5 1 WVL Wpre) V The N Ia),
(18)
which is called Gradient Langevin Dynamics (GLD). When the step size ne in GLD (see in equation [8) approaches zero, the Continuous Langevin Dynamics (CLD) is defined by the following Stochastic Differential Equation (SDE),
d0,- (L (. + vB dB, 0o po
(19)
where B, is the standard brown emotion on Rdd
Lemma G.10 (Log-Soboles Inequality (LSI) for Continuous Langevin Dynamic (CLD) in Li et al. (019)) Lemma 16). Under Equation 19 let qi be the probability density function of parameter O, in CLD and the initial state obeys 0g No, 44). Let be any probability density function which is absolutely continuous with respect to qu- Assume that the optimization objective (g Wpre) is C-bounded, then we have
exp(835) 28
/ Rd (0) p(0)d0.
V log
p(0)
|
DKL (1
Many existing LSIs primarily focus on characterizing the stationary distribution of the Markov process. Contrastly, as shown in this lemma, we try to establish a LSI for 14,, which denotes the parameter distribution at each time step > 0. It would be used in the proof of Theorem F.3 3 and F.7 which explores the upper bound of KL divergence carefully to get data-dependent and topic-dependent generalization bound. According to -lanckk Equation in Definition G.8 the KL divergence between two probability density function can be built so that Lemma G.10 can be applied naturally.
Lemma G.11 (McDiariid's Inequality Variants for Markov Chains in Paulin (015) Theorem 2.1). Consider a Markov chain X (X1,-.. -.. .. which is not necessarily time homogeneous, taking values in Polish state space A A1 x AN, with mixing time 7(c) (for 0 I $ 1). Let
2
Twin = infuge<1 T())
1--c) 1-c)
C RN fff:A. R satisfies f(x) - f(y) < E c1 # vil.
Then for any I, we have
X2 ||ll Tmin
log Ex exp -(X) 5
Proposition G.12 (Refer to Zhang et al. 2023b)). Define f(X) (X,...., ,xx) is a Markov chaun. With the condition in Lemma G.1l if
f(X.) where X
I C and E F.
given a prior distribution v on F. with probability at least 1-8
C Tmin
DKI(H [) + log 2
Ex(((X) f(X)
V
2N log log
8
31

---

Published as a conference paper at ICLR 2025
Proof. With the assumption [f(X)) I C, we have c₁ N
2C
in f(x) f(y) Ex= G1 + Vil.
Then using Lemma
G.11
2²C². Tmin
log Ex exp (A(Ex[f(X) - -
2.V
x² Tmin
v Ex
exp (A(ExIf(X) f(X1))
exp
2NV
A²0 Tmin
Ex
En exp (A(Ex[](X) s(X)))
exp
(20)
2N
According to Markov inequality P(x- 21) _[X] for random variable X and any t O, we have
Ex Ev exp -
P Eg exp XXEx {
21)
(21)
then substitute inequality into 21
C2 Timin
P P(Bo[en exp (A(Ex [f(X)] [((X)] 21) <
exp
2N
(22)
Let
V
2N log and for any 0 < 8 < 1, inequality 22 can be transformed into C -win
2
p Ev exp (A(Exf((X) ((x)))
According to Lemma G.3
DKL (p 11 2 Ep, [T] log
Let T = ((Ex(((X)) - f(X)). then with probability at least 6, we have
E, [X(Ex - f(x))] s DR || 2) + log E,, exp ([XEx
Ep (Ex((() - f(x)) 1 DKI(H
log 5
E, [xx(((()) - / 2N log
C2 Tmin
DKI(H || v) + log 2
V
Lemma G.13 (McDiarmid's Inequality Variants Luo et al. (022 Consider a function f [N]N' + R- that is inder-independent, where (S(J f(J') S holds for any adjacent sets E E [N] such that there is only one different elements in the two sets. Let J consist of N indices sampled uniformly without replacement from [N]. Then, for any Z O,
-212 N'C
P(J(J)- - [E]((() 2 1) S exp
Proposition G.14.
Define f(X)
N ΣN 1 f(X.) where = (X1,..., .N. is a Markov chain.
With the condition in Lemma 1.1l
and if [XX:)]
C, then with probability at least 6
Tmin log 1
Ex [x] f(x) S
N
Proof. With the assumption [f(X)] < C. we have c, Then using Lemma G.Il
20 N
in f(x) f(() EN c1/2, * vil.
12C2 Tiin
log Ex exp (A(Ex]((X)] - (MIXX1((x)11((X0))
2N
2220 Tmin
Ex exp (A(Ex[](X) ((x)))
exp
(23)
2N
32

---

Published as a conference paper at ICLR 2025
FlcAx] exi
According to Chernoff bound P(X 21) v
random variable and any 0, we have
Ex exp -
P(Bx[f(X)] f(X) 2 I
(24)
exp (At)
then substitute inequality
into 24
C2 A2 2NV
Tmin
exp
(A²C²
P(Ex 1(X) 2)
exp
Tmin
21
(25)
exp (At)
2N
Let
Nt Tiin
inequality 25 can be transformed into
- N22
P(Ex(J(X) f(x) 1) s exp
2C Tiin
20 Tmin log
Let f =
for any 0 <<d <<²1,
202 Tmin log
P Bx1s(X))- 2
S
N
Finally, with probability at least 1- d
2C Tmin log 1
[[][(x))-((X)) - S
N
G.2 GENERALIZATION OF SEQUENCES: THE FIRST-LEVEL EXPECTATION
G.2.1 PROOF THEBOREM
Theorem (Generalization Bound of the First-Level Expected Loss). the auto-regressive L.M Pa be the empirical solution of Equation [ and P(- w) denotes the true data distribution under topic w. Under Assumptions
for any < 1, with probability at least 1- 8, the first-level expected loss with K topics and infinite sequences per topic, denoted by L(0, Wpre) (see in Equation or Equation (3). satisfies,
E, [L, Wpre)l = - log 1/5
KNT + +V KNT DKL 11 + log /
Copt
where Copt is the optimization error (see Equation 3 μ and are the posterior and prior distribution of model parameters 0 respectively. K, N and T denote the number of topics, the number of sequences per topic and the sequence length utilized the optimization process of Equation]
Proof sketch. Before the formal proof, we introduce the processing route to obtain the generaliza- tion error bound with handing the prompt dependeeyy issue. First, elaborate the con- struction of ghost sequences Ex, which constructed auto-regressively depending on the original se- quence Fs. thus tokens in ghost sequences are independent. Additionally, we define the function T
Piz Eef. wwn) Pa (u [i "..)" "wx)"
g(0, wx) log Egg [exp(g(0, wx)) F+]], where g(0, wx) Σ Σ log
It can be observed that this function links the original sequence Eg (with dependent tokens), with the ghost sequences Eg (with independent tokens). Substituting them into the Donsker- Varadhan Inequality facilitates establishing a connection between 'data' and the KL distance between 'model prior' and 'model posterior based training data'. Furthermore, regarding the coupling term log gve [exp(g((. wx)) E the function T. we handle this part using the lemma provided in Agarwal et al. (2020). where this part is further transformed into distribution measure of Total
33

---

Published as a conference paper at ICLR 2025
Variance distance (TV distance). As mentioned in Section the primary optimization objective 'negative logarithm likelihood naturally leads to 'KL divergence' thereby formalizing the expression of population loss. Therefore, it's necessary introduce a relationship between TV distance and KL divergence (See in Lemma (.7). for obtaining our generalization bound. Overall, the processing Donsker-Varadhan route can be summarized as: "original sequences E - ghost sequences Ex - Donsker- Varadhan Inequality - TV distance KL divergence + the upper bound of population loss based KL divergence'.
Proof. As we introduced before, all the pre-training sequences set is E = -{E K,N k.n
k,n= each
sequence is denoted as E = {(E . /r
k.n ~ P(- E. wx). To decouple To,n- where rt+1
K,N JR,==1 and each the dependence between tokens, we construct tangent/ghost sequences E {E 1
sequence is -th"" {(Et = where z4+1 is generated depending on the partial original sequences E The construction process of tangent/ghost sequences can be understood simply as duplicate sequences generated based on the original sequences. This proprictary term has been previously utilized in /Agarwal et al. (2020); de la Peña et al. (1999); Kwapien & Woyczynski (1991). Therefore, by introducing the ghost sequences into our analysis, this will help decouple the loken-dependency in auto-regressive sampling of sequences.
Notice that the following proof is first established under a fixed topic Wk-
According to Donsker- Varadhan Inequality (Lemma G.3). let F be any class of functions T - R satisfying the integrability constraints of the lemma. Then for any defined function T, it's straightforward get the lower-bound of the KL divergence between μ and
(4 v) 2 E.
log()E.(e")),
Under fixed topic Wk, the posterior distribution of model parameter 0 is depending on E (see in Section (.1) denoted by f and the prior distribution of is denoted by v. Then, a simple deformation of Lemma G.3 leads to
Ep [T] ( (M v) I log Ec(pp(()
exp E [T] - DKL (# v)) (x(exp(T)]
Taking expectation data distribution E* P(( wk), we have
Eg exp [T] (K (1 || w}}] S Eg E. (exp(T))
(26)
Let = =g(0, wx) log E [exp(g(0, wx)) E*] where
N
T
P(a E wx)
500 wh =
log
(2 L wk)
n=1 1=1
Then for the right hand of inequality 26
we have
E Egx E, [exp((T) =IE E,, (exp (g(0, wx) log E g+
[exp(e(0, wx)) E*]]]
=E
[exp (g(0, wK) log TE B [exp(g(A, wx)) F.
exp (g(0, wk))
EE g+
Egs [exp(g(0, wx)) E+]
Similarly to Agarwal et al. 2020)) the last equality follows that the token in tangent se- quence L is independent conditional on Ed So we have Eys [exp(e(0, wx)) ) E*]
P. (o Me ,0re) ] Thus, inequality 26 can be trans- m00)
E *14 -PCp-P((F "eeE"" formed to
ITT 1==1 exp
log
2
Ega Texp [T] DRI(U v)]] S
(27)
With Markov Inequality P a) [[]] probability at least 1 8,
we get the following high probability representation with
Ele^1 Ea
1 PPX < log ) 1 -
let X [T DRI(H v) = Plex ed
ea
1
E, 1g(0, wx)] - E,, [log [exp(s(0, wx))
E+]] < DRI. v) + log
(28)
34

---

Published as a conference paper at ICLR 2025
For inequality 28 mainly deal with the left hand in this Theorem and make detailed analysis of KL divergence Theorem F.3 to get data-dependent and optimization PAC-Bayesian generalization bound.
B (0, wx)) N
En loggEs [exp(e(8, wx)) E*)
P( F wx) log
Po Po
R.n ok. w.k)
N
T
Po (o k.n E wk) E
E,
log
E
E
exp
log
(29)
2
P( E wy)
Using Lemma G.6 the second term in the right hand can be transformed the total variation distance (TV distance) of distribution Pg and F.
E. (0, wk)] Ey Eg+ [exp(g(0, (()),w))))))))))))))))))))))(( [*]]
T
P I wa) Pg P wx) knn ER". wx) Po km [ wx)
E
log
(30)
Po Po Mi
FL
N
Div (Po(- E. wx). ww)) PP- El."" wx)) 2
+ E
2
1
Plat n wK)
P Pa k.n
++1
Ey wx) [ wx)
log
E
log
2
A.n k.n wk) Po 241
B
Po Po 241
ken
t=1
n=1 t=1
E
DTV (Po( E. wx). TP(+
Eliin wxx))
N
T
Po Pa kin Lit wik
log
2
p
Po (2
knn ERt." wxk)
11
t=1
+
Bp
Drv (Po(-
E."" wy PP( Eka wx))²
(31)
1=1
t=1
where i the minimum of empirical loss
Thus, substitute inequality into 28
I
E
DTv (Po(- Et ww), IP(- Ei wx))
N
P Pa k.n Eft"" wK) kin E. wx) Po (a
1
Ep
log
< DEL(H || v) + log (32)
2
n=1
The result of inequality 32 is analysised under fixed topic wk. then combining all wk Wpre and taking average
K
N
T
E
Drv (Po(- ER wx), PP. E. wxx))
KNT
#=1
[KKL(M |l v) + log 1) KNT k= m=
K ΣΣΣ
P (x k.n Enk. wk)
E
log
(33)
KNT
Po (x pokin wa)
where the second term the right hand is denoted as Copt measuring the logarithmic distribution distance between the ideal minimum and the trained model 0 with empirical loss. Specially, defer the analysis of optimization error to future work. Here, we assume that the results of the actual models obtained closely approximates the ideal minimum for empirical loss, implying that cog is
35

---

Published as a conference paper at ICLR 2025
very small value that this item will be kept in the upper bounds of the first-level expected loss and two-level expected loss. Thus,
B
Dry (Po(- Ef"" w.), P(- EV wx))
KNT
A=
t=1
N T K
E
Prv(PPo E. wx), IP( Ehii wxx) 2
KNT
1=
2 (DEL(H v) + log 2
Copt
(34)
KNT
Using Assumption 4.1 assume log P(-EE, aan), is upper bounded by C. Thus using Proposition Po(-) A.""", with probability at least -
G.
E
(Po( Ex wx). P(- E."" wk])]
KNT
N
T
20 -Tiin log
DTv (Po( Elt", wx),, IP(. Pe wxx) s
(35)
KNT
KNT
Finally, according to Equation
14
13
and
the generalization error bound of the first-level expected
loss is gen sey L0, Wme) can be bounded by
LF
W
pre)
Combining inequality 34 35 and Lemma G.7 L(0, Wpre)
K
N
T
E wk) Po(. E,"", wnn]]
E,
DKL (P(:
KNT
pok.n
==1
20 log C' C-1
E,,
K
N
E ggii
DTV E wx), IP( E wx))
KNT
k=1
tm
20 2Clog C C-1
202
Tmin log B
2 (DKI v) + log 1t
Enp1
KNT
KNT
log 1h KNT
DRL(H II v) + log
=0
Copt
(36)
KNT
Naturally, simplify, for given any prefix sequence P. we have
K
E
Ep
[DKL (PP(- P,, wx) Po(- P. w.ww)]]
K
log 1/2
(KKLlH |l v) + log 1 3) Copt
=0
+ V KNT
(37)
KNT
G.2.2 PROOF OF THEOREM
Theorem Data-Dependent and Optimization Optinizzatoon-Deeeedeentt Generalization Bound of the First-Level Expected Loss). Under the conditions maintained in Theorem and Assumption 4.2 when con- sidering data-dependent prior J1J. any 0 < ă 1, with probability least 6, the first-level
36

---

Published as a conference paper at ICLR 2025
expected loss with K topies and infinite sequences per topic, denoted by L Wpre) (see in Equation 4 or Equation 13). satisfies,
By (pm) -
of
log 1/6
1 K(N- N'yT
(Deelu vs) log 5)) Eaps }.
).
K(N N'YT
then detailing the term DKL(H vJ), L(B, Wpre further satisfies,
1 K(N - NOTT + K(N - N'yT
log 1/8
12C
Npaw
T + log
1 8
Eapt
(38)
N
where C(
EBS (1-e- (1-e-<ep005e (xp(685) ). Copt is the optimization evvor (see in Equation 3
K, (NN) and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation 1 T' denotes the total training iterations.
N paaam denoles the number of model parameters.
Proof sketch of the use of continous mathematical analysis techniques. We analyse the training dynamic of transformer via Continuous Langevin Dynamics (CLD) which is the continous form of Gradient Langevin Dynamics (GLD). To bound the KL divergence of two distribution, we transform the problem into measuring the KI. divergence of pdfs. We first derive the derivative of KI. divergence w.r.t time f. This derivative can be decomposed into two parts, corresponding to the time derivatives of the two pdfs, which can be described by the Fokker-Planck Equation. Next, using Log-Sobolev Inequality, we bound the logorithm distance of two pdfs. By solvin the SDE, we obtain an upper bound for the KL divergence. Finally, referring to the proof of Lemma G.5 in Li et al. (2019). we
demonstrate that the integral of the gradient difference of VL,,, (0r, Wpre) VLg, (0,, Wpee Consequently, get data-dependent and optimization-dependce generalization bound.
Proof. In this Theorem, we analysis KL divergence to get data-dependent and optimization algorithm- dependent generalization bound. First, we analyse the training dynamic of transformer via Continuous Langevin Dynamics (CLD),
d0,- = - -VLE (0.-1, Wpre)dk dl + 3-1 dBe, Og ~ μ40
where LE, (0, Wnee
N-N' k= == 11=1
log
PlatniE mxx) and B, is the standard
K(N N
Po(atin L [e ww,)
brown emotion.
Split pre-training sequences under fixed topic wk into two parts Ej and E (where J is a random sequence including N' indexes uniformly sampled from [N] without replacement and T is [N] J). k=1- Assume that the prior
Under pre-training topies, we have E, (E) K l==1 and F,, (F.) )
distribution of model parameters 9 depending on the subset E which denoted by v. and the posterior distribution of is depending on E denoted by p.
Let θ (0.) and O' = (0))120 be the trajectory trained on sequences E and Eÿ for fixed topic WR. which are the parallel training process based on the same model architecture. Let and y be the distribution of and O respectively, Pe and qe be the pdf of θ and O' and the total steps of iteration is T'. ( {p] || vy) is equal to DKL (pr || qT To bound DKL (pr, || gr ), we first apply Leibniz's rule and the chain rule on it:
de DKI(Pillat)
/ Rd
log
Pddo
di.
at
dp
log
Pt
Pt
9t
dp.
di
dg: Pt
de
d0
dt
gt
Pt
42
dp
log
Pt
d0
dqs
d0,
dt
Jt
Ra
Qt
Pr.
37

---

Published as a conference paper at ICLR 2025
where the last equality follows from that f de: d0 dt [pdd 0, since pt is probability measure. dt
By Fokker-Planck Equation for pt. 0t Apr + V (pr LE, (0, Wpe)).
Op.
Then we bound term A,
dp:
=
log
9t
Apt + V (pr T,,, (0, Wow))
log Pt do
Ape log
Pt do qi
+
V
(peLE, (0, Wiee) log do qt
3d
kd
Vp log
Pt
log
pt
vp.)dd
q1
Rd
qi
pe V Lx, (0,
Wien)
loy
Pt
| (V loy Pt
L,, (0. Wino))d0
22
qi
| Rd
(
log
Pt.
[ (V
log
Pr. PLLE, (0, )
41
Bound term B.
Pt dee
B
dw
2d
qt dt
Age + V. (2: VLE, Wool) dw
Rd
Jdd Ph
Aqidw
+ Sau P'v (2: V LE, Wya))dw
8
pt
V
Jed
(V
Pt
Vai)dw
Pt 2: VL (8, Woee -See (V q. .2 VL,,,, (0, W 1)
8
9:
qi
q:
1
( Pt
Va)ddw
/
(V
VLE (0, Wor))dw
3
gd
qi
In summary, the deviation of (p.lle) can be bounded,
d DKL (pellæ)
dt
(V log qi
Pt. Vp.ddw
log Pt (Vlog
P V.,,,E (0, ))
8
2d
qt"
(V
Pt
Vaiddw
(V a VL, (0, Wpme))du
gd
qi
Rd
V
log
Pt
Vpc)
- Vg.)
dw
8
9
log
Pc V LE, (0, Wire))
(V Pt
q. LE, (0, Wooe) dw
Vpr.
Vq.
Vp:
Va.
Vp.) -
Vq.)
dw
B
P1
qr
41
di
(V log
Pt
V LE, (0, Wrre)
Pt
( log
Pt
9. LL, (0, Wmm")) dw
4t
-1
[ pel V log
pt dw +
pe ( log
pt L (0, Wpx) VLE, (0, Ww)))dw
B 2d
qe
Since for any constant * 0. vector and B, we have the inequality (5,, Bv transform the last equality into
||ll1
clla!
then we
d (pclle) < 28
[ P: log Pt [[ de + B f pcl VLE, (0,, Wpe) V LE, (0c, [I
dt
2
According to Lemma G. (Log-Sobolev Incquality for CL.)) and Assumption
4.1 then [T=(P, Wle)ll S S
and 0u ~ NO0 B Ta), we have Jga P:
V log d0 exp(ass)
29
DKL (pe lg). Transform the first term in the
38

---

Published as a conference paper at ICLR 2025
right hand with the LSI inequality,
dt (pille)) S exp(8855 DKL (pellae) + L.. V.LE, (0t, Wpme
VI.E, (0e, Wine
((() = (pellellg)) ((t = 2 Ev. the following difference equation:
VLE, (0z, Wixe) VL (0,, Ward a exp(s03]. then we get
(1(1) = (1) + 8()), 6(0)
Solve the equation:
8 ("d 2 et Es, [I, (0,, Wga) VLE, (0,, Waa) dl, a exp(835)
DKL (pr || 4T 1
Furthermore, in order to get the upper bound of integral in the right hand, we first define that
Es. Se calc-rr) LI (0,, Wmm) VLE (0c, Wone )12 dt
G(J)
Let and J' be two neighboring collections, we first prove that G(J) G(J) small. VI,, (f,, Wpr) VLEE (o,, Wpn), Y, = VL,,,(e,, Wpe) VLE (0c, Wmn). Then,
G(J')² =Eo,
ca(t-r") ||x+ + Voll dt
1' cale-T)x x Yidl
-Eo
ca(t-r")
X X, + vi) dt
+ 2E,
<En
(11x,113 11
Eo: 1o ca(t-T") ||
2
Eo.
ca(t-19)
||x, de
Es.
+ ca(c-IT) 1
Bo, ca(t-TT) ||v:l1
G(J)+ +
Bs. ca(t-T') |E
For any fixed and 8., under Assumption 4.2 that L. (0,, Ware
L, then
[- clt-TT) || dt < {" catt-T") 4L2
dt 4L - aa
(KN1)
(KN')²a
Then,
2L
1-e-oT
[C()- <
KN
Applying Lemma G.13 of concentration incquality and there are indexes or J',
2c
Py [G() [,(G(J) 2 exp
N
(121----- (KN'
21,(1 c-a
We also have,
NK=N'
Pj [GJ)>> (B) + + < exp
22L2 e--oT")
39

---

Published as a conference paper at ICLR 2025
Then referring et al. Ey [[|V, (0,, Wpee VI (0e, Wl NT. thus
2019), easily get the upper bound of variance of VL (0z, Wiee) which
E,[C(J)] = Es Ee,
[I, (0,, Wm) VLE, (0,, Wm 1121 dt calt-I")
Bd,
ea(t-T))E [IV Wpe) VLE, Wpre ) dt
ca(t-21) T 4L2
N
e a-
VN
Let exp
N2
6, then
21.2(1---00) 1lg
It follows that with probability at least 1 8
212(1---a7))
K²N'a
G(J)
2L
1 1-c-aT'
+
212 e -T"' " 1n
VN
K2N'a
Then,
Es,
(t (1-TT")
[ , (0c, Wpee) LL (0c, Woe)l dt
2L
1-e-aT
21 - c-aa' log
VN V
K2N'a
AL.
log
(1 e'a
1
N'
2K
4L
log
888 (1 e-x
T"
N
1
2K
exp
e808
We bound the KL-divergence.
log 8 2K2
2L MpS (1
exp(-
(-,00)
-688
DKL. (pr
(or))
1
(39)
N'
log 1h 2K²
4L Npxan
1 T")
(40)
where C(
Npuna (.. = 2 385 8885
T')
(1-c
As introduced before, the prior distribution of model parameters 0 is depending the subset E which denoted by yy and the posterior distribution depending on E denoted by μ.. Then Theorem F.1 can be transformed to (modify to N N')
E
Ep [DLL (P(- w)) ll Po(- P, p,,x))]
K
log
DRL(U vJ) + log 1
K(N - -N'YT cxp. (41)
K(N NOT
40

---

Published as a conference paper at ICLR 2025
Finally, with inequality 41 and 39 get data-dependent and optimization algorihhn-dependent PAC-Bayesian generalization error bound of the first-level expected loss.
K
E
[PL P. we) Po(. P. wx))]]
k=1
log 1/8
(1+
log 1/6
4LLC 1, D
Npmm
1
K(N -N'YT
K(N NYT -NYT
x²
N
log 8
Eape
log 1/8 K(N N.yT
LAC T
Pipeem
=0
K(N-No NNNT N'TT
N
log 0
Cupt
(42)
where C(
T) =
1 1 g
T ixp.aita
G.3 GENERALIZATION OF SEQUENCES AND TOPICS: TWO-LEVEL EXPECTATION
G.3.1 PROOF THEOREM E.5
Theorem DData-Dependent and pppinization-Dependaes Generalization Bound of the Two-Level Expected Loss). Let the auto-regressive LLM I&g be the empirical solution of Equation and IP w) is the true data distribution under topic w. Under Assumptions 4.7 4.2 a.5 for any 0 < 1, with probability at least 1 the two-level expected loss (population loss) with infinite topics and infinite sequences per topic, denoted by L(0) (see in Equation] 5) satisfies,
Eg [x[ = KT, (DKL(H 11 + log 8 )) + UWWrr K,N,N',))
where U(Wpre: K, N, T) denotes the right hand of equality 6 equality 38 I and the posterior and prior distribution of model parameters 6, respectively. K, NNN" and T denote the number of topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation
Proof. In this part, since we have gotten the generalization error bound when considering infinite sequences in Theorem [.I] and Theorem F.3 Our analysis is based on that there will be sufficient number of sequences for each topic to enable thorough learning so that in the ideal case, the well- pretrained model can perform excellently on the seen topics. We try get the upper bound of the two-level expected loss (population loss) so that the pre-trained model can also perform well on the unseen topies under the assumption topic distribution.
For an ICL prompt prompt, we also establish auto-regressive loss based on the prefix sequence prompt, Then according to Theorem 4.6) for topic w, we first have
Tp
E Eyccmpi, [DKL (P(- (: prompt,, wa) || Po prompt, wx:)]]
KT
log 1/6 K(N N'TT
1
LPC l")
Naem
log 1
K(N - N'T
N¹
Eupt
O (U( K, N,N," ,T)
(43)
41

---

Published as a conference paper at ICLR 2025
Using Proposition G.1 2 and Assumption 4.1 of log PC-EE, .wx) is upper bounded by C, thus with probability least
Pot-1 11-11,""..r wx)
o, we consider the generalization of topic so that ICL. emerges,
Tp
E. pomp, [Drt,(F() prompt,; w) PP( prompt,, w))]
K
Pprcmpe, (DEL (P(:) prompt,, ws) Po(- prompt, wxh))
KTp
p
Timin 2 log
C
DKL || v) + log =0 1 KT, DRu(H ll v) + log 5
(44)
Finally, we measure the generalization error of an auto-regressive pre-trained LLM, after which the ability of ICL will emerge with good generalization. It can be denoted gen L(0)- Wpre), then the two-level expected loss (population loss) (0) can be bounded by
B
Eng prompt, [DL (P(. prompt, w) || Po(- prompt,, w))l
p
=o =o
1 ]
+ +WWWee K, NNN mm) (45)
PKI(H D) + log
KTp
where U(Were K, N,,, N. the right hand of inequality 6
G.3.2 PROOF OF THEOREM
Theorem (Data-Dependent, DeiiedDepnndntt and Cilmiization-Deenndde Generalization Error Bound of the Two-Level Expected Loss.). Under the conditions maintained in Theorem F. and Assumption 4.5 when further considering topic-dependent prior, for any 0 < & < 1, with probability least 6, the two-level expected loss (population loss) with infinite topics and infinite sequences per topic, denoted by L(0) (see in Equation 5). satisfies,
Ey [L(0)) -0
=o
(K-KKY) DRI.I || vs) + log 1) UUWWpe K, K,N,N', T)
1
then detailing the term DKL(U ps). further satisfies,
oly (K (K-TT
a²C(( 1 T")
1 8 + log
U(Wpm, K, N,
K"
where C( C T") = 22888 (1-E (1x6xxx()00)) ). U(W K,N,N',T denotes the right hand of
Tpd
equality 6 or equality [7] Ia and V. are the posterior and sopic-depender prior distribution of
model parameters 0, respectively. K(K"), N(N') and T denote the number topics, the number of sequences per topic and the sequence length utilized in the optimization process of Equation] 1 T denotes the total training iterations. Nyarom denotes the number of model parameters.
Proof. In this Theorem, we to give detail analysis of DRL( v) to get data-dependent, topic-dependent and ppiiiizatoonddepeddenn generalization bound. Similarly, we analyze the training dynamic of transformer via Gradient Langevin Dynamics (GLD)
0g + 0 7). V (( Wp ) + o,, Ia).
when the step size approaches zero,
d0: -V. Wpne. )dlt + VB-L dB, Oo 14
42

---

Published as a conference paper at ICLR 2025
where (O, Wpre.) (K-RITT
RK-K" kml Σt=
E popi
[log P(a [,,""" .wa)
and B, is the stan-
Fo (x 1, arr)
dard brown emotion.
Split pre-training topics into two parts Wpe./ and Wyre.J (where a random sequence including K" indexes uniformly sampled from [K] without replacement and I is [K] J). Then the total sequences are divided into Ex {E* kkEW,e. and E = {E* keEW Assume that the prior distribution of model parameters 0 is depending on the topic subset E which is denoted by My and the posterior distribution of is depending on E' denoted by μ..
Let é = (0s ):20 and θ' (6))c20 be the trajectory trained on Wpr. and Wpt., (the total sequences are divided into E = {E> JREW and E' {E* JeEW....). Let μ and My be the distribution of θ and O' respectively, Pt and qi be the pdf of é and O' and the total steps of iteration is TV. (p πT)) is equal to DKL (r=). To bound DKL. (pT (QT))) ) we first apply Leibniz's rule and the chain rule on it:
d dt
DKI(Pillar
d
/ Rd
Pt log
Pt do qt
Rd dt
dp
log
qt.
+
Pt
Pt
Qt
dp dr
9t
q8
- Pr
due
de
)d0
dpt
log
Pt
Pr. dge de +
Jge dt
/ dp d0
dt
Q1
dpe
Pt
Pt dge d0,
log
do
dt
Ft
Rd
qt Pt.
(A)
(B)
where the last equality follows from that By Fokker-Planck Equation for Pt.
dp
d8 ʃ p:d0 = 0, since Pe is probability measure.
de
de
Ops
3 Apt V -ppp Wpr..)).
Then we bound term A,
dpt
Pt
A
=
log
db
Rd
dt
9r
1
Ap: + V L(,, Wpne.)))
log
Pt do 2
Rd
Pt de
Pt de
Apt log
+
V
(pe (LO, Mpr..))
log qt
8
Rd
qt
Ra
1
Pt log
Voo
V
Pt
vp.:d0
3
Rdd
+
pt V (0, Wpee.1)
log
Pt
(V log
Pt
.P V ((,
Wpe. ))
Bd
qi
/ Rd
V log
Pt
Vp.)
d0
(V
log
Pt
Pt
L(, Wpre. ))
B
Bd
Bound term B,
Pt dqi
B
dw
Rd
Qt dt
Pt 1
Age + A (g: VI. Wine,))) dw
Rd
qi
Pt Aq.dw
+
/ Pt
(qe LL Wpre.)))
Rd ai
Ba ge
Pt Vtt
(
Pt Vacddw
+
Pt. q: LLO Wpre.1) )-
/ (V (V qi
q. L W Wpre.)))du
Rdd
qi
gt
-1
(V Pt.
Vg.)dw - / (v
qs V (0, W ))
3
gg
qi
qi
43

---

Published as a conference paper at ICLR 2025
In summary, the deviation of (pell))) can be bounded,
(KL
|l q))
dt
-1
V
log
Pt
Vp:
V
log
Pt qr
Pt V L(O, 1)re.)))de
3
gt
1
<V
Vq
<V
Pt
9 LL
W p)w
B
qt
91
-1
log
Pt
Vpt)
(V Pt
Vut
dw
B
Rd
qt
qt
V
log
Pt v VLLEE (0, Wpre))
(V Pt
qt L(0, Wpre.))) dw
Rd
qt
Gr
Pp
Va
Vpc
pt V
Vpr)
Vy.)
dw
Rd
Pt
qt
91.
v log
Pt
Pe (0, I)),
Pt
V
log
qi L(, Wpee.))) dw
Rdd
qt
gr
qt
Pt
11 dw + /
Pt
Pt
V log
V
log
L W pr..1) - VLO0, (poc
B
Rd
q:
R2d
qt
||ll 2c
Since for any constant c # 0, vector a and 3, we have the inequality (5= Vcl we can transform the last equality into
<
+
then
2
d (RL(Pe ll (r) S / Pt V log 28 ///""
Pt 2 dw
B / pell Pel|VI(6 Wpre,1) LI Wpre.))
dt
qi
According to Lemma G.10 we have faa Pt the first term in the right hand of the above inequality.
v log qt
dw
28 (xp(8
DEL (pellae), then transform
8 _E.. di PRi(Pollad S exp(835) DRL (p:llae)
[VL VL, Wpr..))
2
Let (()) (pell))))) 5(1) Fe, [| Wpe.1) (0, Mpre...) 1|12] exp(80S) then we get the following difference equation:
o'(t) = axp(t) + 8(t), 6(0) =
Solve the equation:
DEL (pT (r)))
< 3 T'
1-'
et T'),,, [| L Wpe. - VL(O, W Wpn.))ll] dt, exp(885)
2
We first define that
T
ca T") [| Wpn.r) - VL(O, Wpc..) de
G(J)
Ea,
44

---

Published as a conference paper at ICLR 2025
Let J and J' be two neighboring collections, first prove that G(J) G(J) is small. Let Xt V L(0 Wpe.i) VL(0, Mp...), VL(8, Wpe. VL(8, Wm. Then,
G(J')² =F.0.
aatt-T") ||x, + Vell2 de
Yyyd + 2F. I' cale-T)x Yddf
F..
a(t--"" (x. X, + Y2 v.T dt
T
R..
ca(t-I") (11x,11² + (1
Eol Jo T
+ 2
Eo.
ca(t-Ir) 1|x.112 dt
ea(t-TT) ||
Eo.
ca((-3") | ||xall2
+
To.
ca(c-T))
||:il de
Bs, 'o" ca(c-T)) |Yalli dt
G(J)+
G(J) +
For any fixed and 6s, using the Assumption 4.5 that |L wx S o, then
So" mil-T) [ril di & J(" ca-- 10
40 --
R
Kiaa
Then,
20
1-e-a7
((J)-G(J)) <
K'
a
Applying lemma of concentration incquality and there are K' indexes in J Jor J'
2c
K'exe
Ps -b)())) 2 exp
(ide2(1---0T') K
exp
20 e-
We also have,
K' oe
P3 [G()] 2 (B]G()))+ exp
22 c-att)
then
Ey(G(J) = E,, Eo. 10 et T*) [I/VI Wpn.)) VI Mpr. [| dt
ea(t - T/ [|] L Wpe.1) L( Mps. de
' eu(t-Tr)
4
K"
20
r-
VK
Let exp
- Rc?
= 5, then
402(1- o7" log
It follows that with probability at least 5
(
2N
40 e-
log 1
G(JR S
VK
2K'a
45

---

Published as a conference paper at ICLR 2025
Then,
Eg
e (t [[),, Wpe,1) (L Wie dt
2x
c-
4 (1 c-aT") log
v VK
2k'a
4o²
(1 e
1
log
K'
a
4
898 (1 exep
T"
1 +
log
K
EB88
We bound the Kl--divergence.
DEL (pr (1r)) $
1
log
1
2
20 Be 838
(1 exp(
2333 )}
1
y log
2
- T") *100O(
K'
K'
(46)
Tm (xp()25)
where C( Myro T" (")
7 8ins
e
As introduced before, the prior distribution of model parameters depending on the subset E which denoted by vy and the posterior distribution of is depending on E' denoted by μ.. Then Theorem F.5 slightly changed.
can be
12
Rew Expcmps, [DLL (P(- prompt,, w) II PP( prompt, w])]
Tp
C² Tmin
(KL v) log 2)
(47)
2(K
K'YT, log
Tp Eprcmpe, [DiI (P(. prompt, wa) || Pa(- prompt, wx))
+ E,.
(K - K'
1 (H || v) + log $3 UWW K.N,M,KNNNN. K,N,N.T)
(48)
(K K'
get data-dep,ndent, topic-dependent and optimizationn-dpeeddent PAC- Bayesian generalization bound of the two-level expected loss, Le., L(0) is bounded by
Finally, with inequality 46 and 48
Tp
E
Eaw Eepromes, [DL (P(-) prompt,, wx) || (P( prompt,, (0kmpt,..kk))) wx))]]
Tp
1=1
1o02 2000(( P Mymn T')
1
+ log 1
0
V - (K-K')
1+ V log
K¹
+ +UWPee K, K,N,N',,
0
{ (K - K'TT,
1
o²0(
Nprm 1")
log 1
+ U(Wee, K.N,N.T)
(49)
K"
where C( Npmma 1') = 3 aBs
exp(5337
46


Reviews:
[{"review_id": "eufo2u0LdI", "reviewer": "Reviewer_y9tb", "summary": "This paper derives generalization bounds for in context learning using a topic-dependent and data-dependent view of pre-training,", "questions": "- From what I can tell, the experiments in Appendix C.2 on GINC with varying number of topics are far more relevant than those in Section 5 which just show better ICL performance with more context length. Why did the authors choose to organize the paper in such a way? If there is a reason, I think the authors should highlight it, as it definitely stood out to me that the experiments in section 5 are common knowledge from existing in-context learning literature.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper looks at in-context learning through a new lens of generalizing over topics and sequences, which is a novel contribution.\n- The generalization bounds arrived at in Theorem 4.3 are similar but tighter than the bound from [Li et al](https://proceedings.mlr.press/v202/li23l.html), which is valuable.\n- The paper has a comprehensive appendix that readers will find helpful while grokking the paper.\n\nOverall I think the paper has a new view that adds to recent work on the theory of in context learning.", "weaknesses": "- I am not entirely certain of the impact of this paper. Sure the bounds derived are new and tighter than previous similar ones in [Li et al](https://proceedings.mlr.press/v202/li23l.html), but I am not sure this contribution (alongside the view of modeling pre-training topics) is significant enough for ICLR. Perhaps a more fleshed out discussion section in the paper could remedy this, I am open to changing my opinion given a solid argument of why this result is significant compared to bounds from adjacent literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ad3D8SaW4b", "reviewer": "Reviewer_fg9c", "summary": "- This paper seeks to provide a theoretical understanding of in-context learning for language models.\n - A simple topic model is assumed, where a set of topics are drawn independently and a sequence is generated given each topic; this is done both for the pretraining data as well as the in-context learning data; note that the pretraining and in-context learning topics are different in general, but are drawn i.i.d. from a shared topic distribution.\n - The main result is a PAC-Bayes bound that controls the log-loss on new in-context learning instances, as a function of the number of topics, number of sequences per topic, and sequence length. (There are actually two results - one conditioned on a single topic, and one that averages over topics).\n - A few experiments demonstrate that accuracy improves as the sequence length increases.", "questions": "- It seems like Theorem 4.3 is optimization-dependent, but it seems like we are just analyzing the solution to Equation 1, so does the choice of optimization algorithm come in? Assumption 4.2 bounds the gradient by S, which I see appears in (6). But what is assumed on the optimization algorithm? How can we even guarantee that it converges to the global optimum?\n - Theorem 4.6: If you have a topic at ICL time that you didn't see at pretraining time, it seems like your loss could be arbitrarily bad (since I don't see any other distributional assumptions). How does this manifest in the bound? Indeed, I think this is the interesting part of ICL (which one can think of as a transfer learning problem).\n - In general, it seemed like a lot of the paper defines fairly basic things, and it's only at page 7 when things get interesting. But by that time, there's really no space in the paper to discuss the actual theorems (not to mention that the experiments are very abbreviated).\n - I'm not sure what insight to take away from the experiments (other than that increasing sequence length helps). It would have been nice to see some even more synthetic experiments that try to test the theory (how things actually scale with K, N, T).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Obtaining theoretical analysis of in-context learning is a worthwhile goal, given the general lack of rigorous theory in this area.\n - The actual result that's derived is non-trivial (analyzing both sample complexity and optimization); and sensible in the sense that the bound scales fairly cleanly with the typical quantities (sequence length, number of sequences, number of topics).", "weaknesses": "- Some of the claims/framing in the paper seemed a bit odd. For example, 'emergence' is highlighted a few times, but I don't think it's necessary to invoke that: the setting here is a much more conventional transfer learning + domain generalization.\n - The paper contrasts previous analyses's i.i.d. approach compared to the autoregressive one in this paper, but this paper still assumes that we have i.i.d. sequences (it's just that the tokens in each sequence are not independent, which is not remarkable).\n - The essence of in-context learning as it manifests in LLMs is that the pretraining data is meant to just be raw text from the Internet, and that the in-context data is supposed to be examples of some task. The surprising part of ICL is that the pretraining and in-context distributions are very different. The fact that this paper assumes the two are the similar I think misses the spirit of in-context learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dbGvt5RebH", "reviewer": "Reviewer_ARXg", "summary": "This paper gives a generalization bound of sequences for in-context learning in a language model under the auto-regressive next-token prediction paradigm. It models the practical AR-NTP paradigm for an In-context Learning Framework, considering the two-level expectation loss over sequence and topic. Then it presents Theorems for the generalization of sequences and topics, provides the upper bound of the two-level expected loss. Thus, it indicates that ICL emerges from number of topics, number of sequences and sequence length, and demonstrated by limited numerical experiments.", "questions": "1. Can this result be directly adapted to the in-context learning paradigm in recent large language models? Since the difference in the empirical loss, is there still a gap between them?\n2. Is the Bounded Gradient a strong assumption for the Transformer and recent large language model? After multiple layers of nonlinear superposition in the Transformer, the network output may be highly sensitive to input changes.\n3. How do you define the topic examples in your experiments? Can you give some examples of the topic in linear dynamic systems and GINC?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper considers the Auto-Regressive Next-Token Prediction paradigm, which models token dependencies more realistically in actual language models, addressing a limitation in previous ICL studies.\n2. This paper presents data-dependent and topic-dependent PAC-Bayesian generalization bounds for auto-regressive next-token prediction loss.\n3. This paper presents a theoretical view about ICL emergence, and demonstrates that ICL emerges from the generalization of sequences and topics.", "weaknesses": "1. Some motivation of the paper is confusing and not clarified enough. The author claims that the i.i.d. setting is unrealistic in language tasks, but Section 3 directly shifts the paradigm towards the language model without an explanation of how to break through the i.i.d. limitation.\n2. The experimental setting is not fully discussed, including the detailed information about GINC datasets (number of entries; example; split;), the initialization of GPT-2 (from-scratch or pretrained), the method to change sequence length on real-world datasets (directly mask the token that exceeds the specified length, ignoring the semantic?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hWsMX1mfm0", "reviewer": "Reviewer_x2ai", "summary": "The paper critiques existing ICL theoretical analyses for relying on unrealistic i.i.d. (independent and identically distributed) assumptions and lacking an explanation of ICL emergence. To address these issues, the authors propose an auto-regressive next-token prediction (AR-NTP) framework, which mirrors real-world language learning by considering token dependencies within prompts. The paper introduces a pre-training and ICL framework, analyzing generalization bounds using PAC-Bayesian techniques and exploring how ICL arises through generalization of sequences and topics. The findings are validated through experiments on synthetic and real-world datasets, concluding that ICL capabilities emerge from the strong generalization of LLMs trained on diverse sequences and topics.", "questions": "Why particularly choose PAC-Bayesian framework for ICL? There are numerous works study ICL using statistical frameworks like [1]\nWhy not based on uniform convergence or algorithmic stability, could help situate the results within a broader landscape of generalization theory?\n\n[1] Transformers as statisticians: Provable in-context learning with in-context algorithm selection", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents an original contribution to the understanding of in-context learning (ICL) by introducing the auto-regressive next-token prediction (AR-NTP) framework. The paper seek to addresses two major limitations in the current literature: the i.i.d. assumption in prompt tokens and the lack of an explanation for how ICL emerges from pre-trained large language models (LLMs). By shifting the focus to token dependencies in AR-NTP and offering a novel pre-training and ICL framework, the authors provide a fresh perspective on ICL emergence through generalization. The originality stems from the use of PAC-Bayesian generalization techniques, and the proposed framework opens up new avenues for exploring token dependencies and generalization beyond previous work that relied on supervised function learning. The authors also provide theoretical results that are supported by empirical experiments on both synthetic and real-world datasets, enhancing the quality and rigor of their contributions.\n\nthe paper is well-structured and flows well, guiding the reader through complex concepts such as generalization bounds, topic-dependent priors, and PAC-Bayesian techniques without overwhelming them with technical jargon. The theoretical framework is detailed yet accessible, and the results are presented in a way that is easy to follow, particularly with well-placed diagrams and examples. The significance of the work lies in its ability to explain ICL as an emergent property of pre-trained LLMs, which has strong implications for both academia and industry. The results contribute to understanding why larger models exhibit better ICL performance and provide concrete recommendations for improving model generalization.", "weaknesses": "While the paper makes significant strides in addressing limitations in existing ICL literature, there are several areas where the work could be strengthened. One key weakness lies in the assumptions behind the AR-NTP paradigm. Although the shift from i.i.d. settings to token-dependent sequences is crucial, the paper could have provided a more thorough discussion on the potential challenges this poses for practical implementation. For example, the dependency between tokens may introduce computational inefficiencies in scaling to larger datasets or more complex sequences, which could affect the generalization results. A more detailed exploration of how to handle these challenges efficiently during training would improve the practical applicability of the proposed framework. \n\nAltough the paper is mostly theoretical, there is no enough experiments in the main paper. Especially the claim that topic prior in pre-training would affect the ICL does not get justification. Appendix contains some synthetic topic results using GPT-2 but that is a bit too hand-wavy. \nThe authors validate their theoretical claims with experiments on synthetic and real-world datasets, which is commendable, but the diversity of the real-world datasets could be expanded. For example, the selection of datasets appears limited to common language tasks like sentiment analysis and topic classification. Including a wider variety of tasks such as training on Zipfian data but test on distributions like MMLU and GSM8k would better demonstrate the generalization and applicability of the proposed AR-NTP paradigm across different domains. Moreover, while the results show that increasing the number of pre-training topics, sequences per topic, and sequence length improves model performance, the experiments would benefit from more ablation studies. \n\nLastly, while the paper provides theoretical insights into how ICL emerges from pre-training, the connection between theory and practice could be more tightly integrated. The authors propose that ICL arises from excellent generalization of sequences and topics, but the specific impact of pre-training data diversity, model size, and optimization iterations could be made clearer. The paper could explore more explicitly how different pre-training regimes—such as training on more complex or diverse datasets [1] —might affect ICL performance in practice. This would provide practitioners with clearer guidelines on how to optimize their pre-training procedures for better ICL outcomes. In particular, the paper could explore limitations of their generalization bounds when models are applied in low-resource environments, where generalization may suffer in no enough ICL examples are given or the pre-training FLOPs are constrained.\n\n[1] Data Distributional Properties Drive Emergent In-Context Learning in Transformers Stephanie C.Y. Chan, Adam Santoro, Andrew K. Lampinen, Jane X. Wang, Aaditya Singh, Pierre H. Richemond, Jay McClelland, Felix Hill", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "or6v2ljor0", "reviewer": "Reviewer_JqeP", "summary": "The paper proposes theoretical analysis to explain the ICL abilities exhibited by LLMs. The analysis establishes data-dependent, topic-dependent and optimization dependent generalization bounds for pre-trained LLMs, investigating that ICL merges from the generalization of sequence topics. The paper also present empirical evidence to support the theoretical implications.", "questions": "1. Did you control the training size for various topic size, sequence length and sequence amount?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The breakdown of pre-training loss into data and topic level optimization is interesting and inspiring. It is capable of identifying two sources of pre-training loss, sequences and topics. \n\n2. The theoretical bounds and empirical evidence are aligned: with longer sequence length, more number of sequence and more number of topics, the ICL loss is smaller and performance is better.", "weaknesses": "1. One concern centers around the controlled experiment of the empirical investigation. Given the data is sampled from the topic and token distribution, with more topic or more sequence, or longer sequence, it implies more training data, so it is expected that the ICL loss drops and that performance increases. It is unclear that the loss change can be attributed to the three sources or simply data size, under the current experiment setup.  \n\n2. Although the theoretical analysis establish the bounds of ICL loss, but the results apply to general prompt, rather than in-context examples only. It also implies that the ICL loss should be lower and performance should be better with more training data (in terms of topic and sequence). But only well-structured in-context samples work empirically. I am uncertain if the presented theory is sufficiently tailored to address the problem of ICL. \n\n3. Now the empirical investigation is omitted from the main paper but experiment setup discussion remains. I suggest to put the main analysis of empirical result into main paper and defer some theoretical analysis into appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)