From Unstructured Data to In-Context Learning: Exploring What Tasks Can Be Learned and When

Authors: kevin christian wibisono
yixin  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:03:11

Abstract: Large language models (LLMs) like transformers demonstrate impressive in-context learning (ICL) capabilities, allowing them to make
predictions for new tasks based on prompt exemplars without parameter updates. While existing ICL theories often assume structured training data resembling ICL tasks (e.g., x-y pairs for linear regression), LLMs are typically trained unsupervised on unstructured text, such as web content, which lacks clear parallels to tasks like word analogy. To address this gap, we examine what enables ICL in models trained on unstructured data, focusing on critical sequence model requirements and training data structure. We find that many ICL capabilities can
emerge simply from co-occurrence of semantically related word pairs in unstructured data; word analogy completion, for example, can provably arise purely through co-occurrence modeling, using classical language models like continuous bag of words (CBOW), without needing positional information or attention mechanisms. However, positional information becomes crucial for logic reasoning tasks requiring generalization to unseen tokens. Finally, we identify two cases where ICL fails: one in logic reasoning tasks that require generalizing to new, unseen patterns, and another in analogy completion where relevant word pairs appear only in fixed training positions. These findings suggest that LLMs' ICL abilities depend heavily on the structural elements within their training data.

Main paper: 
 introduction: 
 Large language models (LLMs) such as transformers demonstrate remarkable in-context learning (ICL) abilities [10] : without any parameter updates, they can recognize tasks and generate predictions from prompt examples. For instance, given the prompt dog anjing, cat kucing, lion singa, elephant, a well-trained LLM should detect the English-to-Indonesian pattern in the prompt and predict gajahthe Indonesian translation for elephant-as the most likely next token. The ICL capabilities of LLMs are surprising for two main reasons. First, these models are trained in an unsupervised manner on unstructured natural language data through next-token prediction, without any loss function specifically designed for ICL. Second, the training data for LLMs likely lacks sequences resembling typical ICL prompts, i.e., of the form c 1 d 1 • • • c K d K , where (c k , d k )'s represent word pairs with specific semantic relationships.Many efforts have sought to understand ICL from theoretical and empirical perspectives, e.g., gradient descent in regression and Bayesian inference. While insightful, these analyses often rely on structured training data that mirrors ICL tasks. For instance, they train on sequences of x-y pairs from various linear regression tasks and test on similar data. In practice, however, LLMs are trained in an unsupervised manner on unstructured text data, such as web content, which bears little resemblance Figure 1 : This paper identifies essential components for in-context learning (ICL) from pre-training on unstructured natural language data. Left sub-panels, right sub-panels, and boxed letters denote NLP examples, our abstractions, and expected outputs, respectively. Section 2 shows that ICL for word analogy tasks can arise via modeling co-occurrence information using classical language models like continuous bag of words (CBOW) (violet represents relationship-specific nuisance tokens). Section 3 establishes the necessity of modeling positional information and blocked nuisance structure for ICL tasks, enabling pattern recognition and generalization to novel tokens (violet represents nuisance tokens). Section 4 presents scenarios where ICL fails, providing theoretical explanations that underscore the critical role of training data structure in enabling ICL in language models. to typical ICL tasks like word analogy. Consequently, these analyses may only partially capture the complexities of ICL. This work. We investigate common ICL tasks to identify what tasks can be learned in context by a model trained on unstructured data. Specifically, we examine essential components of sequence modeling that enable in-context learning, along with requirements on the unstructured training data.The first set of (theoretical and empirical) results focuses on ICL for word analogy completion using frequently co-occurring tokens [10, 50] . This task involves identifying relationships between word pairs, such as (country)-(capital) and (English word)-(Indonesian translation), then applying the same relationship to complete a sequence. For this task (see left of Figure 1 ), we explore cases where training sentences contain one or two types of word pairs with distinct semantic relationships. We prove that, in most cases, ICL can arise by simply modeling word co-occurrence using classical (pre-transformer) language models like continuous bag of words (CBOW) [36] , without needing positional information or attention mechanisms.The second set of results involves ICL for logic reasoning tasks that require recognizing patterns that do not commonly co-occur in a sentence, such as (word)-(first letter) [13, 62] . For this task (see middle of Figure 1 ), we investigate scenarios where training sentences contain one or two distinct patterns, as well as a more realistic scenario where nuisance tokens are present. We prove that positional information and blocked nuisance structure (e.g., pqrs in Figure 1 ) are crucial for the success of ICL in these tasks. This finding aligns with Chen et al.'s [2024] observation that parallel structures in pre-training data support ICL. We also find that learned positional embeddings generally perform better, except in scenarios where the nuisance tokens are not clustered in blocks.Finally, we present two scenarios where ICL fails regardless of model architectures (see right of Figure 1 ). In the first scenario (left example), we consider a logic reasoning task that involves identifying and completing meta-patterns within sequences. Here, each training sequence repeats the pattern established by its starting tokens; the ICL task sequence then requires the model to recognize this meta-pattern of repetition and generalize it to a novel, unseen starting pattern. In the second scenario (right example), we examine a word analogy completion task in which relevant word pairs appear in the unstructured training sentences but are restricted to specific fixed positions. These findings, along with their empirical and theoretical explanations, underscore that LLMs require specific structures in the pre-training data to exhibit ICL ability. stop words). We first introduce Theorem 1, which states that ICL can arise if each sentence consists of exactly one (c i , d i ) pair, as long as the number of in-context examples (ℓ) is not too large. To simplify calculations, we replace the cross-entropy loss with squared loss by removing the softmax activation and comparing outputs against the one-hot encoding of target words. The proof is in Appendix B. Theorem 1 (ICL on single-relationship word analogy tasks). Let K, L ≥ S ≥ 3. Suppose each training sentence of length S is generated by selecting one (c i , d i ) pair and S -2 distinct r i 's uniformly at random. We train a CBOW model with the squared loss and a sufficiently large embedding dimension on these sentences. Given a prompt c i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1 with distinct i k 's, the model correctly predicts d i ℓ+1 if and only if 2ℓ + 1 < KL(S-1) 3 (K+L)(S-2) 2 (S-1)+K(S-2)(S-1) 2 -2(S-2) 4 .As an example, when each training sentence contains exactly one country-capital pair (i.e., (c i , d i )), Theorem 1 says that a trained CBOW model will correctly predict d i ℓ+1 (i.e., the capital city of c i ℓ+1 ) given an ICL prompt of the form c i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1 , provided that the prompt length is not too large. Intuitively, this behavior is due to the presence of c i ℓ+1 in the ICL prompt, leading the model to correctly predict d i ℓ+1 given the frequent occurrences of the pair (c i ℓ+1 , d i ℓ+1 ) in the training data. However, when the prompt length is too large, the model will instead predict one of the r i 's (see Theorem 1's proof in Appendix B for more details). Moreover, if we let L → ∞ and fix K and S, the condition in Theorem 1 becomes 2ℓ + 1 < K(S -1) 2 /(S -2) 2 . This inequality trivially holds if the prompt length is set to be S -1 to match the length of the training sentences. Furthermore, it is possible to adapt the proof of Theorem 1 to handle the case when each sentence comprises exactly two (not one) different (c i , d i ) pairs. In this case, letting L → ∞ and fixing K and S, the model correctly predicts d i ℓ+1 given the same ICL prompt if and only if 2ℓ + 1 <K(K-2)(S-1) 2 (K-2)(S-2)(S-4)-K. This upper bound is strictly larger than K(S -1) 2 /(S -2) 2 : when each sentence contains exactly two (c i , d i ) pairs, ICL under the squared loss holds for longer prompts.Experiments. To empirically verify Theorem 1 and its generalizations, we conduct experiments using the cross-entropy loss with S = 8, K = 10, L = 20, and ℓ = 3. We explore multiple (p 0 , p 1 , p 2 ) values, where p k denotes the probability of having exactly k pairs of (c i , d i ) in the sentence. For each (p 0 , p 1 , p 2 ) triple, we also introduce a more realistic setting where c i and d i do not always appear together by considering its corrupted version. In this setup, each (c i , d i ) pair has a 25% chance of being replaced with (c i , r j ) and a 25% chance of being replaced with (d i , r j ) for some j ∈ [L]. More details are provided in Appendix K.Table 1 : ICL on different single-relationship word analogy tasks, averaged over 10 repetitions, demonstrates stable, good performance across embedding dimensions (d E ), as Theorem 1 suggests. The corrupted setting also demonstrates excellent ICL ability under certain scenarios.CorruptedEQUATIONResults. Table 1 displays the average accuracy for each scenario, calculated over 10 repetitions. Notably, when (p 0 , p 1 , p 2 ) is (0, 1, 0) or (0, 0, 1), ICL under the cross-entropy loss achieves zero accuracy, in contrast to perfect accuracy with the squared loss as shown in Theorem 1. We believe this difference in accuracy is an artifact of the loss functions used, although its relevance is limited by the fact that it is unlikely for every sentence to contain at least one (c i , d i ) pair, in reality. On the other hand, perfect ICL performance is observed in other settings (e.g., when the training sentences contain either zero, one, or two (c i , d i ) pairs) in both the clean and corrupted scenarios. For an in-depth comparison of ICL performance using both the squared and cross-entropy loss across various numbers of demonstration examples, see Appendix C. 
in-context learning on dual-connected-relationship word analogy tasks: 
 Building on the scenario that contains only a single type of relationship between frequently cooccurring word pairs, namely (c i , d i ), we now explore ICL on dual-connected-relationship word d E = 10 d E = 100 d E = 10 d E = 100 d E = 10 d E = 100 (0, 1, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0, 1) (0, 0) (0, 0) (0, 0) (0, 0) (0.07, 0.10) (0, 0) (1/2, 1/2, 0) (0.(1/2, 0, 1/2) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (0, 1/2, 1/2) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1/3, 1/3, 1/3) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1)analogy tasks. Here, some words frequently co-occur with two different types of words in the training data, represented by the relationships (c i , d i ) and (c i , e i ). For instance, c i might represent a country, d i its capital city, and e i its currency. The vocabulary is comprised of c 1:K , d 1:K , e 1:K , r 1:L , where r i 's represent other words. Moreover, the corresponding ICL tasks take the form c i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1 and c i1 e i1 • • • c i ℓ e i ℓ c i ℓ+1 ,d i1 • • • c i ℓ d i ℓ c i ℓ+1 (c i1 e i1 • • • c i ℓ e i ℓ c i ℓ+1 ) with distinct i k 's,• • c i ℓ d i ℓ c i ℓ+1 .Here, the output is more likely to be d i ℓ+1 than e i ℓ+1 since d i ℓ+1 co-occurs with the other d ij 's in the training data (and e i ℓ+1 does not). Note that in Theorem 2, we unrealistically require each sentence to contain either two distinct (c i , d i ) pairs or (c i , e i ) pairs. However, this condition is not necessary as we empirically show next.Experiments. We use the cross-entropy loss with S = 8, K = 10, L = 60, and ℓ = 3. Each training sentence is equally likely to be a cd sentence (i.e., containing (c i , d i ) pairs) or a ce sentence (i.e., containing (c i , e i ) pairs), but not both. We explore multiple (p 0 , p 1 , p 2 )'s, where p k is the probability of having exactly k pairs of (c i , d i ) for a cd sentence, or k pairs of (c i , e i ) for a ce sentence. Additionally, we introduce three different scenarios: balanced, where all L random words are equally likely to occur in both cd and ce sentences; imbalanced, where L/3 words are more likely to occur in cd (ce) sentences; and extreme, where L/3 of the words can only occur in cd (ce) sentences. More details are provided in Appendix K.Results. Table 2 shows the accuracies of both tasks for each scenario, averaged over 10 repetitions. We observe a perfect accuracy when (p 0 , p 1 , p 2 ) ∈ {(1/2, 0/1, 2), (0, 1/2, 1/2), (1/3, 1/3, 1/3)} across all embedding dimensions and scenario types. The near-zero accuracy when (p 0 , p 1 , p 2 ) or (0, 1, 0) or (0, 0, 1) is again an artifact of the cross-entropy loss, as discussed in Section 2.1.Interestingly, ICL works in the imbalanced and extreme scenarios when (p 0 , p 1 , p 2 ) = (1/2, 1/2, 0), where sentences do not contain more than one (c i , d i ) or (c i , e i ) pair. To see this, consider the balanced scenario where each r i is equally probable to appear in both types of sentences. Given a prompt of the formc i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1, it is easy to see that the model should output d i ℓ+1 or e i ℓ+1 with equal probability. On the other hand, in the imbalanced and extreme scenarios, the information from the r i 's can allow for task selection, thus contributing to the success of ICL. (0, 1, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0, 1) (0, 0) (0, 0) (0.16, 0.14) (0, 0) (0.21, 0.29) (0, 0) (1/2, 1/2, 0)(1, 1) (0.82, 0.83) (0.28, 0.27) (0.95, 0.95) (0.83, 0.85) (0.91, 0.91)(1/2, 0, 1/2) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (0, 1/2, 1/2) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1/3, 1/3, 1/3) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1)We next replicate the experiments in Section 2.2, but with disjoint word pair relationships of two distinct types with no overlapping tokens, i.e., (c i , d i ) and (e i , f i ). For example, (c i , d i ) represents a country and its capital city, and (e i , f i ) represents a company and its CEO. Our vocabulary consists of c 1:K , d 1:K , e 1:K , f 1:K , r 1:L , where r i 's represent other words; see Appendix K for details.Results. Table 3 summarizes the accuracies of the ICL tasksc i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1 and e i1 f i1 • • • e i ℓ f i ℓ e i ℓ+1for each scenario, averaged over 10 repetitions. Similar to the connected setting in Section 2.2, we observe a perfect accuracy when (p 0 , p 1 , p 2 ) ∈ {(1/2, 0/1, 2), (0, 1/2, 1/2), (1/3, 1/3, 1/3)} across all embedding dimensions and scenario types. However, when (p 0 , p 1 , p 2 ) = (1/2, 1/2, 0), ICL already works well in the balanced scenario. Intuitively, this is because the two relationships are disjoint, thus making task selection easier.In addition, we consider a contaminated version of the training data where cd (ef ) sentences can contain some e i 's and f i 's (c i 's and d i 's). We also obtain a perfect accuracy when (p 0 , p 1 , p 2 ) ∈ {(1/2, 0/1, 2), (0, 1/2, 1/2), (1/3, 1/3, 1/3)} across all embedding dimensions and scenario types.We conduct experiments on a synthetic corpus consisting of (country)-(capital) and (country)-(IOC code) relationships. Each sentence in the corpus is categorized into exactly one of six possible categories: (1) exactly one country-capital pair; (2) exactly two country-capital pairs; (3) exactly one country-IOC pair; (4) exactly two country-IOC pairs; (5) exactly one country without any pair; and (6) no country. In sentences with country-capital pairs, each capital city can appear in any position relative to the country. Conversely, in sentences with country-IOC pairs, each IOC code must directly follow the country. The data source and corpus generation process are detailed in Appendix K.Two models are trained on this corpus: a CBOW and a five-layer two-head autoregressive transformer. Both models have an embedding dimension of 100. We then compare the ICL accuracies for both relationships given one to five in-context examples. For the CBOW model, the country-capital accuracies are (0.81, 0.82, 0.78, 0.73, 0.65) and the country-IOC accuracies are (0.15, 0.38, 0.59, 0.71, 0.79).Here, the i-th number corresponds to the accuracy given i in-context examples. For the transformer, the accuracies are (0.00, 0.15, 0.34, 0.22, 0.07) and (1.00, 0.77, 0.78, 0.97, 0.99), respectively.When using the transformer, we find that the accuracies for the country-IOC task are significantly higher compared to those for the country-capital task. This is likely because each IOC code consistently follows the corresponding country in the corpus, similar to ICL prompts. On the other hand, ICL fails to work on the country-capital task, where there is no consistent pattern in how each pair occurs in the corpus. Meanwhile, ICL works decently well on both tasks under the CBOW model. 3 The essential role of positional information in enabling in-context learning We examine another common example of in-context learning (ICL), where the task involves predicting the first (or second) token in a sequence. This task resembles general logic reasoning tasks that require recognizing patterns that do not typically co-occur in a sentence, such as (word)-(first letter) [13, 62] . While Section 2 shows that positional encoding is irrelevant for ICL in word analogy tasks, positional information proves essential for such logic reasoning tasks. Specifically, we consider a simpler task of modeling x i1 x i2 x i3 x i1 . Theorem 3 underscores the importance of positional information to correctly predict x i1 from x i1 x i2 x i3 in a single-layer model, and provides a construction of an attention-based model achieving zero loss and perfect accuracy on this task. Its proof is in Appendix E.Theorem 3 (Necessity of modeling positions). Let the vocabulary be V = {1, 2, • • • , |V |} and the training sequences take the form x i1 x i2 x i3 x i1 , where x i1 ̸ = x i2 ̸ = x i3 ̸ = x i1 are chosen uniformly at random from V. Consider a one-layer model that predicts the last x i1 via a learned function f ({x i1 , x i2 }, x i3 ) using the cross-entropy loss. In this case, it is not possible to achieve pefect accuracy or zero loss. On the other hand, we can achieve zero loss (and thus perfect accuracy) by incorporating positional information, i.e., via a learned function f ({(x i1 , 1), (x i2 , 2)}, (x i3 , 3)).Here, f ({x i1 , x i2 }, x i3 ) represents a scenario where the model lacks positional information (e.g., f is a one-layer autoregressive transformer without positional embeddings). Note that the output of this function is identical for inputs x i1 x i2 x i3 and x i2 x i1 x i3 , which leads to the impossibility of attaining zero loss. In contrast, f ({(x i1 , 1), (x i2 , 2)}, (x i3 , 3)) refers to a scenario where the model has access to positional information. We provide a construction of f that achieves zero loss in Appendix E.Experiments. We validate Theorem 3 by training transformers with causal masking to autoregressively learn sequences of the form x i1 x i2 x i3 x i1 , and assessing their accuracy in predicting the last token on a separate test data of the same pattern. We use |V | = 20 and an embedding dimension of 10. We consider these settings: (i) number of layers: 1, 5; (ii) positional embeddings: learned, sinusoidal, no positional embeddings; and (iii) train-test split: each token in the vocabulary is the first token in both the training and test sets (Both), each token in the vocabulary is the first token in either set, but not both (Either). More details are provided in Appendix K. Results. Table 4 summarizes the results. Two main findings emerge: (1) for the model to generalize to unseen sentences, each token in V should be present as the first token in both the training and test sets;(2) positional embeddings are crucial when using only one attention layer. Note that in practice, the condition in ( 1) is likely met due to the vast size of LLMs' pre-training data.Multiple layers. Proposition 1 shows that multi-layer models can encode positional information without explicit positional embeddings.Proposition 1 (Multi-layer models can encode positions). Consider the sentence x i1 x i2 x i3 x i1 . Using a two-layer autoregressive model, the model's final output for predicting the last x i1 is given by t(x i1 x i2 x i3 ) := g 3 ({f 1 ({x i1 }), f 2 ({x i1 }, x i2 )}, f 3 ({x i1 , x i2 }, x i3 )) for some f 1 , f 2 , f 3 , and g 3 .The proof is in Appendix F. Proposition 1 shows that we generally have t(x i1 x i2 x i3 ) ̸ = t(x i2 x i1 x i3 ), unlike in the one-layer case. Consequently, high accuracy is achievable without positional embeddings, as shown in Table 4 . This result parallels findings in Haviv et al. [26] that autoregressive transformers implicitly encode positions, even without positional embeddings.Roadmap of Section 3. In the rest of this section, we consider settings where each sentence contains repeating patterns. [1] | c ∈ S 1 } = {c[1] | c ∈ S 2 } = V, where c[i] is the i-th element of c.In other words, each token in V can be the first token in both the training sentences and ICL prompts. We consider three scenarios: We set the vocabulary size |V | = 20, the number of nuisance tokens N = 20, and use only one attention layer as additional layers do not improve performance. See Appendix K for more details.Results. Table 5 reveals interesting phenomena. First, under the clean data scenario, ICL performs exceptionally well, with an observed performance increase with learned positional embeddings and a larger embedding dimension. However, ICL is notably challenging under the one-noisy scenario. In the block-noisy scenario, learned positional embeddings are crucial for satisfactory ICL performance. Theorem 4 formalizes these findings. Theorem 4 (Blocked nuisance token structure facilitates ICL). Consider a sufficiently large autoregressive position-aware model that can achieve the minimum possible theoretical loss. Training this model in the one-noisy (block-noisy) scenario results in zero (perfect) ICL accuracy.The proof is in Appendix G. Theorem 4 says that ICL works perfectly under the block-noisy scenario, yet fails to work under the one-noisy scenario. However, as shown in Table 5 , the use of sinusoidal positional embeddings significantly enhances prediction accuracy in the one-noisy scenario. This may be due to the fact that sinusoidal embeddings can encode relative positional information [53] . For example, training sentences of the form nabacdc, where n ∈ N , may help in predicting the most likely token following the ICL prompt abacd. 
in-context learning on dual-pattern tasks: 
 We next examine the case where training data and ICL prompts contain two different patterns occurring equally likely: abcadefd and abcbdefe, where a, b, c and d, e, f are distinct. We consider the clean and block-noisy scenarios as in Section 3.1, and set |V | = N = 20 (details in Appendix K).Results. Table 6 outlines the ICL performance for both scenario types across different model configurations. Unlike the single-pattern scenario, there is an improvement in performance with five layers compared to one layer, particularly with learned positional embeddings.This phenomenon is related to the notion of induction heads, where at least two layers may be necessary to distinguish the two patterns [38] . This is reflected in Figure 2 , which compares the accuracy trajectories of one-layer and five-layer models. While the five-layer setup effectively differentiates the two patterns, the one-layer configuration fails to do so. Meanwhile, in both clean and block-noisy scenarios, learned positional embeddings lead to notably higher accuracies as compared to sinusoidal ones, similar to the single-pattern case. • Randomly select 10 countries and obtain their capital cities and IOC codes. Justification: There is no societal impact as this work is foundational. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
scenarios where in-context learning fails: 
 In this section, we consider two scenarios where in-context learning (ICL) fails, irrespective of architectures. In Section 4.1, we consider a logic reasoning task requiring identification and generalization of a repetition meta-pattern within sequences. In Section 4.2, we explore a word analogy task where relevant word pairs appear in unstructured training sentences but are limited to fixed positions. Section 4.3 concludes with a synthetic data experiment supporting the theory.In this meta-pattern recognition and generalization task, each training sequence follows a repeating pattern based on its starting tokens, and the ICL task sequence requires the model to identify this repetition and extend it to a new, unseen starting pattern. Specifically, our training data comprises sentences in the form of abacdcefe, where a ̸ = b, c ̸ = d, and e ̸ = f . Note that each sentence is structured into three blocks, each consisting of three tokens with the same pattern. For the ICL task, we consider predicting f from the prompt abbcddef , where a ̸ = b, c ̸ = d, and e ̸ = f . Given the repeated pattern within each training sequence, a well-trained model might be expected to output f to continue the pattern established in the in-context examples: abb and cdd. However, as seen in Table 7 , all models fail to recognize and apply the pattern, resulting in incorrect predictions. Results. Theorem 5 and Table 7 demonstrate that ICL achieves zero accuracy irrespective of the number of in-context examples (ℓ -1). This insight sheds light on the ICL capacity of autoregressive models. Simply put, if the pattern in the in-context examples differs significantly from any pattern in the training data, ICL may not occur. These results align with the findings of Raventós et al. [42] and Yadlowsky et al. [63] on the importance of data diversity for ICL. 7 shows none of the models can identify the patterns and predict the correct token.Formalization. We now formalize a generalization of this scenario. Let the vocabulary be Results. Theorem 6 highlights the finding that the success of ICL relies heavily on how the patterns appear in the training data. In this scenario, the (a i , b i ) pairs consistently appear at the beginning and end of each training sentence, and we anticipate the model to recognize this relationship for ICL to occur. However, as shown in Theorem 6 and Table 7 , this is not the case.{(a i , b i )} i∈[I] ∪ V, where V = {1, 2, • • • , |V |}We conduct an experiment on a synthetic corpus featuring (country)-(capital) relationships. Each sentence falls into one of four categories: (1) exactly one country-capital pair, (2) exactly two country-capital pairs, (3) a single country without a pair, and (4) no country. In sentences with one country-capital pair, the capital appears in the first position, the country in the last, and each sentence contains six words (as in Section 4.2). The corpus generation process is detailed in Appendix K.We train a five-layer two-head autoregressive transformer on this corpus, with an embedding dimension of 100. Similar to Section 2.4, we evaluate the ICL accuracies using prompts involving countries and their capitals. The results show zero ICL accuracy across varying in-context examples (one to five), supporting our theory. 
discussion: 
 This paper examines how in-context learning (ICL) arises from pre-training on unstructured language data, with three key findings: (1) ICL for word analogy tasks can emerge from simple co-occurrence modeling, using models like continuous bag of words (CBOW) without positional encoding or attention; (2) positional information and structured nuisance tokens are essential for ICL in logic reasoning tasks that require recognizing rare patterns and generalizing to new tokens; and (3) the structure of training data significantly impacts ICL effectiveness.Large language models (LLMs), such as transformers, are widely recognized for their outstanding performance in in-context learning (ICL) [10] . ICL refers to the capability of LLMs to discern specific tasks and generate predictions based on prompt exemplars without needing any parameter updates. A multitude of studies have been dedicated to exploring this intriguing phenomenon from various theoretical and empirical perspectives. In this section, we provide a brief summary of some of these studies. Some studies adopted a Bayesian approach to studying ICL. Xie et al. [60] posited that ICL can be viewed as implicit Bayesian inference. They demonstrated that LLMs can infer a latent documentlevel concept for next-token prediction during pre-training and a shared latent concept across inputoutput pairs in an ICL prompt, under the assumption that documents are generated from hidden Markov models (HMMs). Wang et al. [56] and Zhang et al. [67] expanded on this idea by exploring more realistic latent variable models beyond HMMs. Wang et al. [56] argued that large language models function as latent variable models, with latent variables containing task-related information being implicitly inferred. Zhang et al. [67] showed that without updating the neural network parameters, ICL can be interpreted as Bayesian model averaging parameterized by the attention mechanism. Panwar et al. [39] provided empirical evidence that transformers behave like Bayesian predictors when performing ICL with linear and non-linear function classes. Dalal and Misra [18] proposed a Bayesian learning framework to understand ICL through the lens of text generation models represented by multinomial transition probability matrices. Chiang and Yogatama [14] proposed the pelican soup framework to explain ICL without relying on latent variable models. This framework incorporates concepts such as a common sense knowledge base, natural language classification, and meaning association, enabling the establishment of a loss bound for ICL that depends on the number of in-context examples.Garg et al. [21] formulated ICL as learning a specific function class F from prompts of the form (x 1 , f (x 1 ), . . . , x n , f (x n ), x n+1 ) and their corresponding responses f (x n+1 ). Here, f ∈ F, where F is a function class. In this context, ICL refers to the capability of a transformer to output a number close to g(y n+1 ) given a prompt of the form (y 1 , g(y 1 ), . . . , y n , g(x n ), y n+1 ), where g ∈ F. Many studies adopted this regression formulation of ICL, with some linking ICL to gradient descent. Akyürek et al. [5] , Von Oswald et al. [55] , and Dai et al. [17] proved that transformers are capable of implementing gradient descent, which results in their ICL ability. Bai et al. [7] established generalization bounds for ICL and proved that transformers can perform algorithm selection like statisticians. Zhang et al. [66] showed that the gradient flow dynamics of transformers converge to a global minimum that enables ICL. Huang et al. [27] investigated the learning dynamics of single-layer softmax transformers trained via gradient descent to perform ICL on linear functions. Ahn et al. [3] explored the optimization landscape of transformers and proved that the optimal parameters coincide with an iteration of preconditioned gradient descent.In a related exploration, Li et al. [31] showed that softmax regression models learned through gradient descent are similar to transformers. Ren and Liu [44] related ICL with softmax transformers to contrastive learning, where the inference process of ICL can be viewed as a form of gradient descent. Mahankali et al. [35] proved that minimizing the pre-training loss is equivalent to a step of gradient descent in single-layer linear transformers. Vladymyrov et al. [54] established that linear transformers execute a variant of preconditioned gradient descent by maintaining implicit linear models. On the other hand, some studies argued that the ICL ability of transformers cannot be attributed to gradient descent. Fu et al. [20] showed that ICL for linear regression tasks arises from higher-order optimization techniques like iterative Newton's method rather than gradient descent. Wibisono and Wang [57] demonstrated that transformers can perform ICL on unstructured data whose prompt exemplars lack explicit pairings, with softmax attention playing an important role especially when using a single attention layer. Shen et al. [46] provided empirical evidence that the equivalence between gradient descent and ICL might not be applicable in real-world scenarios. In contrast to these studies, our work provides a connection between ICL and classical language models like continuous bag of words (CBOW). Specifically, we show that ICL for word analogy tasks with semantically related word pairs can arise by modeling co-occurrence patterns via CBOW.Numerous studies focused on the pre-training aspects (e.g., data distribution and task diversity) of ICL. Min et al. [37] showed that the input-label mapping in the in-context examples does not significantly affect ICL performance. Chan et al. [11] demonstrated that the ICL capabilities of transformers depend on the training data distributions and model features. Kossen et al. [30] established that ICL considers in-context label information and is capable of learning entirely new tasks in-context. Li and Qiu [32] introduced an iterative algorithm designed to enhance ICL performance by selecting a small set of informative examples that effectively characterize the ICL task. Qin et al. [41] proposed a method based on zero-shot chain-of-thought reasoning for selecting ICL examples, emphasizing the importance of choosing diverse examples that are strongly correlated with the test sample. Han et al. [25] studied ICL by identifying a small subset of the pre-training data that support ICL via gradient-based methods. They discovered that this supportive pre-training data typically consist of more uncommon tokens and challenging examples, characterized by a small information gain from long-range context. Peng et al. [40] proposed a selection method for ICL demonstrations that are both data-dependent and model-dependent. Van et al. [52] introduced a demonstration selection method that enhances ICL performance by analyzing the influences of training samples using influence functions.In a similar vein, Wu et al. [59] demonstrated that pre-training single-layer linear attention models for ICL on linear regression with a Gaussian prior can be effectively accomplished with a minimal number of independent tasks, regardless of task dimension. Raventós et al. [42] emphasized a task diversity threshold that differentiates the conditions under which transformers can successfully address unseen tasks. Yadlowsky et al. [63] attributed the impressive ICL capabilities of transformers to the diversity and range of data mixtures in their pre-training, rather than their inductive biases for generalizing to new tasks. Ding et al. [19] compared the ICL performance of transformers trained with prefixLM (where in-context samples can attend to all tokens) versus causalLM (where in-context samples cannot attend to subsequent tokens), finding that the latter resulted in poorer ICL performance. Chen et al. [13] discovered that the ICL capabilities of language models rely on the presence of pairs of phrases with similar structures within the same sentence. Zhao et al. [68] proposed a calibration scheme that modifies model parameters by adding random noises, resulting in fairer and more confident predictions. Abbas et al. [1] demonstrated that the ICL predictions from transformer-based models often exhibit low confidence, as indicated by high Shannon entropy. To address this issue, they introduced a straightforward method that linearly calibrates output probabilities, independent of the model's weights or architecture. Similar to these works, our work highlights the importance of co-occurrence, positional information, and training data structure for ICL to arise.Other studies analyzed ICL from a learning theory perspective. Hahn and Goyal [23] proposed an information-theoretic bound that explains how ICL emerges from next-token prediction. Wies et al. [58] derived a PAC-type framework for ICL and finite-sample complexity results. Jeon et al. [28] introduced a novel information-theoretic view of meta-learning (including ICL), allowing for the decomposition of errors into three components. They proved that in ICL, the errors decrease as the number of examples or sequence length increase. Other studies focus on the mechanistic interpretability component of ICL. Olsson et al. [38] argued that transformers can develop induction heads that are able to complete token sequences such as[A][B] • • • [A] → [B], leading to impressive ICL performance. Bietti et al. [9] examined a setup where tokens are generated from either global or context-specific bigram distributions to distinguish between global and in-context learning. They found that global learning occurs rapidly, while in-context learning is achieved gradually through the development of an induction head. Ren et al. [43] identified semantic induction heads that increase the output logits of tail tokens when attending to head tokens, providing evidence that these heads could play a vital role in the emergence of ICL. Yu and Ananiadou [65] showed that the ICL ability of transformers arises from the utilization of in-context heads, where each query and key matrix collaborate to learn the similarity between the input text and each demonstration example.A number of works delved into specific data generating processes to provide insight into the emergence of ICL. Bhattamishra et al. [8] examined the ICL ability of transformers by focusing on discrete functions. Specifically, they showed that transformers perform well on simpler tasks, struggle with more complex tasks, and can learn more efficiently when provided with examples that uniquely identify a task. Guo et al. [22] investigated ICL in scenarios where each label is influenced by the input through a potentially complex yet constant representation function, coupled with a unique linear function for each instance. Akyürek et al. [6] studied ICL of regular languages produced by random finite automata. They compared numerous neural sequence models and demonstrated that transformers significantly outperform RNN-based models because of their ability to develop n-gram heads, which are a generalization of induction heads. Sander et al. [45] analyzed simple first-order autoregressive processes to gain insight into how transformers perform ICL to predict the next tokens. On the other hand, our work focuses on data generating processes containing semantically related word pairs and repeated token patterns to better understand several components that are crucial for ICL to occur from training on unstructured data. Some studies explored how different components of transformers affect their ICL abilities. Ahuja and Lopez-Paz [4] compared the ICL performance of transformers and MLP-based architectures under distribution shifts. Their findings demonstrate that while both methods perform well in in-distribution ICL, transformers exhibit superior ICL performance when faced with mild distribution shifts. Collins et al. [15] showed that softmax attention outperforms linear attention in ICL due to its ability to calibrate its attention window to the Lipschitzness of the pre-training tasks. Xing et al. [61] focused on linear regression tasks to identify transformer components that enable ICL. They found that positional encoding is crucial, along with the use of multiple heads, multiple layers, and larger input dimensions. Cui et al. [16] proved that multi-head attention outperforms single-head attention in various practical scenarios, including those with noisy labels and correlated features. Chen et al. [12] investigated the ICL dynamics of a multi-head softmax attention model applied to multi-task linear regression. They proved the convergence of the gradient flow and observed the emergence of a task allocation phenomenon, where each attention head specializes in a specific task.Finally, several studies proposed various hypotheses on the emergence of ICL and provided theoretical justifications. Swaminathan et al. [49] introduced clone-structured causal graphs (CSCGs) to explain how ICL can generalize to unseen sentences via a mechanism called rebinding. Li et al. [33] viewed ICL as an algorithm learning problem where a transformer implicitly constructs a hypothesis function at inference time. Han et al. [24] argued that the ability of transformers to execute ICL is attributable to their capacity to simulate kernel regression. Singh et al. [47] explored the interaction between ICL and in-weights learning (IWL) using synthetic data designed to support both processes. They observed that ICL initially emerges, followed by a transient phase where it disappears and gives rise to IWL. Yan et al. [64] studied ICL from the perspective that token co-occurrences play a crucial role in guiding the learning of surface patterns that facilitates ICL. Abernethy et al. [2] showed that transformers can execute ICL by dividing a prompt into examples and labels, then employing sparse linear regression to deduce input-output relationships and generate predictions. Lin and Lee [34] developed a probabilistic model that can simultaneously explain both task learning and task retrieval aspects of ICL. Here, task learning refers to the ability of language models to identify a task from in-context examples, while task retrieval pertains to their ability to locate the relevant task within the pre-training data.Proof. Let |V | = 2K + L denote the vocabulary size. Consider a sentence X represented by its one-hot encoding (i.e., X ∈ {0, 1} |V |×S ). For every position i ∈ [S], the loss for predicting the word in the i-th position given all the other words is given by ||AX(1 S -e i ) -Xe i || 2 2 , whereA = U ⊤ V S-1 ∈ R |V |×|V| and e i ∈ R S is a zero vector with 1 on its i-th entry. Here, U (V ) is a matrix consisting of the center (context) embeddings of all tokens, and A is a matrix summarizing the similarity between each pair of words (one as a center word and the other as a context word). Our objective is to find A that minimizes the sum of losses for each position in each sentence. Lemma 1 gives a closed-form expression of the minimizer.A = B ((S -2)B + C) -1 .Here, B is a matrix whose (i, j)-th entry is p(i, j), the probability that for a given (center, context) pair, the center is i ∈ |V | and the context is j ∈ |V |. Moreover, C is a diagonal matrix whose i-th diagonal entry isp(i) = j∈|V | p(i, j). Proof. Let L(X) = S i=1 ||AX(1 S -e i ) -Xe i || 22 denote the sum of the losses corresponding to all tokens in sentence X. By direct calculation,∂L(X) ∂A = 2AX S i=1 (1 S -e i )(1 S -e i ) ⊤ X ⊤ -2X S i=1 e i (1 S -e i ) ⊤ X ⊤ . Note that S i=1 (1 S -e i )(1 S -e i ) ⊤ = (S-2)1 S×S +I S×S and S i=1 e i (1 S -e i ) ⊤ = 1 S×S -I S×S . Now, let our sentences be X 1 , X 2 , • • • , X N .EQUATIONWe denote the number of (center, context) pairs across all sentences in which the center is i and the context is j by #(i, j). Moreover, we define #(i) = j∈|V | #(i, j). It is easy to see that Equation (1) can be rewritten asA (S -2) B + C = B,where B is a matrix such that its (i, j)-th entry is #(i,j) N and C is a diagonal matrix such that its i-th diagonal element is #(i) N . As N → ∞, an application of the law of large numbers yields#(i,j) N→ S(S -1)p(i, j) almost surely and #(i) N → S(S -1)p(i) almost surely, where p(i, j) is the probability that for a given (center, context) pair, the center is i and the context is j, and p(i) = j∈|V | p(i, j).A = B ((S -2)B + C) -1 ,where B and C are defined in the statement of Lemma 1.We now define• p 1 = p(c i , c j ) = p(d i , d j ) = p(c i , d j ) = p(d i , c j ) for any i ̸ = j;• p 2 = p(r i , r j ) for any i ̸ = j;• p 3 = p(c i , d i ) = p(d i , c i ) for any i; • p 4 = p(c i , r j ) = p(d i , r j ) = p(r j , c i ) = p(r j , d i ) for any i, j,where the equalities in the probabilities are a consequence of the data distribution.For ease of presentation, we denote a square matrix with α on the diagonal and β off the diagonal as X α,β , and a matrix with all entries γ as Y γ . We then have EQUATION(S -2)B + C = X e,a X c,a Y d X c,a X e,a Y d Y d Y d X f,b.Moreover, its inverse can be written as((S -2)B + C) -1 = X q5,q1 X q3,q1 Y q4 X q3,q1 X q5,q1 Y q4 Y q4 Y q4 X q6,q2, where∆ = 2a(K -1)(b(L -1) + f ) + b(L -1)(c + e) + cf -2d 2 KL + ef , q 1 = --abL+ab-af +d 2 L (2a-c-e)∆,q 2 = 2ab(K-1)+b(c+e)-2d 2 K (b-f )∆ , q 3 = -     -2a 2 b(K -1)(L -1) -2a 2 f (K -1) + 2abc(K -2)(L -1) + 2acf (K -2) + 2(a -c)d 2 KL + bc(c + e)(L -1) + cf (c + e) + d 2 L(c -e) (c -e)(2a -c -e)∆     , q 4 = -d ∆ , q 5 = -     -2a 2 b(K -1)(L -1) -2a 2 f (K -1) + 2abe(K -2)(L -1) + 2aef (K -2) + 2(a -e)d 2 KL + be(c + e)(L -1) + ef (c + e) + d 2 L(e -c) (e -c)(2a -c -e)∆     ,andq 6 = -2a(K-1)(b(L-2)+f )+b(L-2)(c+e)+cf -2d 2 KL+2d 2 K+ef (b-f )∆.By computing A = B((S -2)B + C) -1 , given the following center words, the similarities between them and all possible context words are as follows:• Center word = c i for any i c i : 2(K -1)p 1 q 1 + p 3 q 3 + Lp 4 q 4 ; c j : 2(K -2)p 1 q 1 + p 1 q 5 + p 3 q 1 + p 1 q 3 + Lp 4 q 4 (j ̸ = i); d i : 2(K -1)p 1 q 1 + p 3 q 5 + Lp 4 q 4 ; d j : 2(K -2)p 1 q 1 + p 1 q 3 + p 3 q 1 + p 1 q 5 + Lp 4 q 4 (j ̸ = i); r j : 2(K -1)p 1 q 4 + p 3 q 4 + p 4 q 6 + (L -1)p 4 q 2 (for any j).• Center word = d i for any i d i : 2(K -1)p 1 q 1 + p 3 q 3 + Lp 4 q 4 ; d j : 2(K -2)p 1 q 1 + p 1 q 5 + p 3 q 1 + p 1 q 3 + Lp 4 q 4 (j ̸ = i); c i : 2(K -1)p 1 q 1 + p 3 q 5 + Lp 4 q 4 ;We now check when these conditions are simultaneously satisfied. The first condition is equivalent to p 3 > 0 and K > 2(S-2) 3 (S-1) 2 (2S-3) , which always hold. The second condition reduces to p 3 > 0 and 2(S -2) 4 + K(S -2) 2 (S -1) 2 > 0, which is also true. The third condition can be written as p 3 > 0 and K(S -2)(S -1) 3 > 0, which always hold. The last condition becomes(2ℓ + 1)((K + L)(S -2) 2 (S -1) + K(S -2)(S -1) 2 -2(S -2) 4 ) < KL(S -1) 3 , which is equivalent to 2ℓ + 1 < KL(S -1) 3 (K + L)(S -2) 2 (S -1) + K(S -2)(S -1) 2 -2(S -2) 4 ,completing the proof.Note that this condition ensures that the model predicts d ℓ+1 instead of one of the r i 's.Proof. We show that given a prompt of the form c i1 d i1 • • • c i ℓ d i ℓ c i ℓ+1 with distinct i k 's, a trained CBOW model is more likely to predict d i ℓ+1 than e i ℓ+1 . If this is established, the other part of the theorem follows analogously. We now define• p 1 = p(c i , d j ) = p(d i , c j ) = p(d i , d j ) = p(c i , e j ) =p(e i , c j ) = p(e i , e j ) for any i ̸ = j;• p 2 = p(r i , r j ) for any i ̸ = j;• p 3 = p(c i , d i ) = p(d i , c i ) = p(c i , e i ) = p(e i , c i );• p 4 = p(d i , r j ) = p(r i , d j ) = p(e i , r j ) = p(r i , e j ) for any i, j;where the equalities in the probabilities are a consequence of the data distribution. By direct calculation, we havep 1 = 1 K(K-1) , p 2 = (S-4)(S-5)L(L-1) , p 3 = 1 K , and p 4 = S-4 KL , where each p i is multiplied by S(S -1) > 0 (without loss of generalization) to make calculations easier. Moreover, it is easy to see that p(c i , r j ) = p(r i , c j ) = 2p 4 for any i, j and p(c i , c j ) = 2p 1 for any i ̸ = j. Lastly, we define a = (S -2)p 1 , b = (S -2)p 2 , c = (S -2)p 3 , d = (S -2)p 4 , e = 2(K -1)p 1 + p 3 + Lp 4 , and f = 4Kp 4 + (L -1)p 2 .The next step the proof is to use Lemma 1 in Appendix B to obtain the similarity matrix A. As previously, we denote a square matrix with α on the diagonal and β off the diagonal as X α,β , and a matrix with all entries γ as Y γ . We then haveEQUATIONMoreover, its inverse can be written asEQUATIONfor some q 1 , q 2 , • • • , q 10 . Recall that our task is show that given context wordsc i1 , d i1 , • • • , c i ℓ , d i ℓ c i ℓ+1 with distinct i k 's,the center word is more likely to be d i ℓ+1 than e i ℓ+1 . In other words, we need to establish thatd ⊤ i ℓ+1 c i1 + d ⊤ i ℓ+1 d i1 + • • • + d ⊤ i ℓ+1 c i ℓ + d ⊤ i ℓ+1 d i ℓ + d ⊤ i ℓ+1 c i ℓ +1 > e ⊤ i ℓ+1 c i1 + e ⊤ i ℓ+1 d i1 + • • • + e ⊤ i ℓ+1 c i ℓ + e ⊤ i ℓ+1 d i ℓ + e ⊤ i ℓ+1 c i ℓ +1 ,where ϵ ⊤ δ indicates the similarity between the word ϵ in the center and the word δ in the context. This similarity can be obtained from the matrix A = B((S -2)B + C) -1 . By symmetry, the inequality reduces to d ⊤ i d j > e ⊤ i d j for any i ̸ = j. By computing the matrix A, we haved ⊤ i d j = p 3 q 1 + p 1 q 3 + (K -2)p 1 q 1 + (K -2)p 1 q 6 + Lp 4 q 4 + p 1 q 5 and e ⊤ i d j = p 3 q 1 + p 1 q 3 + (K -2)p 1 q 1 + (K -2)p 1 q 8 + p 1 q 7 + Lp 4 q 4 .Thus, our problem again reduces to showing (K -2)q 6 + q 5 > (K -2)q 8 + q 7 as p 1 = 1 K(K-1) > 0. Upon multiplying (3) and ( 2) and equating the result with the identity matrix, we have the following equations: a(K -1)q 1 + cq 3 + dLq 4 + eq 5 + a(K -1)q 6 = 1 (4) (c + a(K -2))q 1 + aq 3 + dLq 4 + aq 5 + (e + a(K -2))q 6 = 0(5) a(K -1)q 1 + cq 3 + dLq 4 + eq 7 + a(K -1)q 8 = 0 (6) (c + a(K -2))q 1 + aq 3 + dLq 4 + aq 7 + (e + a(K -2))q 8 = 0.Comparing ( 5) and ( 7) yields a(((K -2)q 6 + q 5 ) -((K -2)q 8 + q 7 )) = e(q 8 -q 6 ).As a = (S -2)p 1 > 0 and e = 2p 1 (K -1) + p 3 + p 4 L > 0, we now only need to show that q 8 > q 6 . Comparing ( 4) and ( 6) as well as ( 5) and ( 7), we have a(q 5 -q 7 ) = (e + a(K -2))(q 8 -q 6 ) e(q 5 -q 7 ) = a(K -1)(q 8 -q 6 ) + 1, which reduces to (q 8 -q 6 )(e 2 + ae(K -2) -a 2 (K -1)) = a. The conclusion follows since a > 0 ande 2 +ae(K -2)-a 2 (K -1) = (e-a)(e+a(K -1)) = S -1 K - S -2 K(K -1) (e+a(K -1)) > 0.Proof. Consider the instance of predicting a from abc, i.e., f ({a, b}, c). By the assumption on the data distribution, it is equally likely that the task is predicting b from bac. In this case, the corresponding function is also f ({a, b}, c). Thus, the sum of the cross-entropy losses corresponding to these two tasks is lower bounded by 2 log 2 > 0. Also, it is easy to see that we cannot achieve perfect accuracy since the predictions for abc and bac must be the same.We now show that it is possible to attain zero loss and perfect accuracy when the model includes positional embeddings, so that f ({(a, 1), (b, 2)}, (c, 3)) ̸ = f ({(b, 1), (a, 2)}, (c, 3)). As a special case, we consider a simplified version of the transformer architecture, wheref ({(a, 1), (b, 2)}, (c, 3)) = k∈{a,b,c} (x k + p 1 ) exp((x k + p 1 ) ⊤ (x c + p 3 )) k∈{a,b,c} exp((x k + p 1 ) ⊤ (x c + p 3 )). andp(d | abc) ∝ exp x ⊤ d f ({(a, 1), (b, 2)}, (c, 3)) .for any token d. Here, x i and p j represent the embedding of token i and position j, respectively.Let p ⊤ 1 p 3 = p, p ⊤ 2 p 3 = q, p ⊤ 3 p 3 = r, x ⊤ i x i = s, x ⊤ i x j = t for any i ̸ = j, p ⊤ 1 x i = u for any i, p ⊤ 2 x i = vfor any i, and p ⊤ 3 x i = w for any i. Note that this holds due to the assumed data generating process. We consider the following construction:p 1 = b1 |V | , p 2 = p 3 = 1 |V | ,and x i = ae i , where e i is a zero vector with 1 on the i-th entry. This implies p = b|V |, q = r = |V |, s = a 2 , t = 0, u = ab, and v = w = a.By direct calculation, the cross-entropy loss of predicting a from abc is given by-log exp(α 1 a 2 ) exp(α 1 a 2 ) + exp(α 2 a 2 ) + exp(α 3 a 2 ) + |V | -3 ,whereα 1 = exp(ab + b|V |) exp(ab + b|V |) + exp(a + |V |) + exp(a 2 + a + |V |) , α 2 = exp(a + |V |) exp(ab + b|V |) + exp(a + |V |) + exp(a 2 + a + |V |) , α 3 = exp(a 2 + a + |V |) exp(ab + b|V |) + exp(a + |V |) + exp(a 2 + a + |V |).Letting b = a 2 and a → ∞, it is easy to see that we can bring the cross-entropy loss arbitrarily close to zero. Consequently, we also have a perfect prediction accuracy.Proof. The intermediate representation of the first layer is given by f1 ({x i1 }), f 2 ({x i1 }, x i2 )}, f 3 ({x i1 , x i2 }, x i3), and f 4 ({x i1 , x i2 , x i3 }, x i1 ), for some functions f 1 , f 2 , f 3 , and f 4 . To predict the last x i1 , we use the third coordinate of the second layer representation, which is given by t(x i1 x i2 x i3 ) := g 3 ({f 1 ({x i1 }), f 2 ({x i1 }, x i2 )}, f 3 ({x i1 , x i2 }, x i3 )), for some function g 3 . It is easy to see that in general, t(x i1 x i2 x i3 ) ̸ = t(x i2 x i1 x i3 ).Proof. In the one-noisy scenario, each sentence takes one of the following forms: nabacdc, anbacdc, abnacdc, abancdc, abacndc, and abacdnc, where n ∈ N . In order to achieve the minimum possible theoretical loss, we minimize each loss term separately. Concretely, the minimum loss of predicting the sixth token given the first five tokens is attained by the following rule:• When the first five tokens do not contain any nuisance token, output a uniform probability vector over N .• Otherwise, output the conditional probability of c [2] given x, where (x, c [2] ) ∈ S 1 . Here, x represents the last non-nuisance token.Under this rule, the predicted output for any in-context example abacd is never c, since c / ∈ N . In the block-noisy scenario, each sentence takes one of the following forms: n 1 n 2 n 3 abacdc, aban 1 n 2 n 3 cdc, and abacdcn 1 n 2 n 3 , where n 1 , n 2 , n 3 ∈ N . The minimum loss of predicting the ninth token given the first eight tokens is attained by the following rule:• When the seventh token is not a nuisance token, output the seventh token with probability one.• When the seventh token is a nuisance token, output a uniform probability vector over N .Under this rule, the predicted output for any in-context example abacdcef is e, resulting in perfect ICL accuracy.Proof. Recall that each training sentence is of the form x 11 x 12 x 11 x 21 x 22 x 21 • • • x N 1 x N 2 x N 1 . Note that we can decompose the total loss L intoL 1 + L 2 + • • • + L 3N, where L g denotes the loss of predicting the g-th token given all the other previous tokens. As the x i1 x i2 x i1 blocks are generated independently, the optimal loss should satisfyL 1 = L 4 = • • • = L [3N -2] = L [1] , L 2 = L 5 = • • • = L [3N -1] = L [2], andL 3 = L 6 = • • • = L [3N ] = L [3]. Therefore, it is sufficient to minimizeL [1] + L [2] + L [3] .In order to achieve the minimum possible theoretical loss, we need to minimize L [1] , L [2] , and L [3] separately. It is easy to see that L [1] is minimized by outputting the marginal probability of c [1] , where c ∈ S 1 . Similarly, L [2] is minimized by outputting the conditional probability of c [2] given x i1 , where (x i1 , c [2] ) ∈ S 1 . On the other hand, it is possible to achieve an L [3] value of zero by outputting x i1 with probability one. Now, given an ICL prompt x 11 x 12 x 12 x 21 x 22 x 22 • • • x ℓ1 x ℓ2 where ℓ ≤ N , the trained model should predict x ℓ1 with probability one since {c [1] | c ∈ S 2 } = V and our ICL prompt corresponds to L [3] . This completes the proof.Proof. We proceed similarly as the proof of Theorem 5. Concretely, we separately minimize L g for g ∈ [2k + 2], where L g denotes the loss of predicting the g-th token given all the other previous tokens. It is easy to see that L 1 is minimized by outputting a uniform probability vector over a 1:[I] , whereas L h (for any 2 ≤ h ≤ 2k + 1) is minimized by outputting a uniform probability vector over V. Moreover, it is possible to achieve an L 2k+2 value of zero by outputting b i with probability one.From here, given an ICL prompt of the form a i1 b i1 a i2 b i2 • • • a i ℓ , the trained model should predict a uniform probability vector over V if ℓ ≤ k, and b i1 if ℓ = k + 1. In all cases, the model does not predict b i ℓ , completing the proof.This study has several limitations. Firstly, the experiments are conducted on a relatively small scale. However, they still provide sufficient evidence to support the theoretical findings. Secondly, the focus of this study is on specific types of in-context learning (ICL) tasks, as described in Section 1.Thirdly, the pre-training data considered in this work may not match the valid grammatical sentences that language models are usually trained on. Nonetheless, our co-occurrence results still apply to grammatical sentences, as the co-occurring pairs can appear naturally within them (e.g., "Beijing is the capital of China," or "the city of Beijing is located in China"). Lastly, real data sets are not utilized due to the lack of alignment with the study objectives.Despite these limitations, we believe this work provides valuable understanding of the key factors enabling ICL to occur from training on unstructured natural language data, supported by both theoretical and empirical evidence from experiments involving prompting and synthetic data. Further analyses on other ICL tasks and their reliance on model architecture can be fruitful avenues for future work.All experiments utilize the Keras package in Python, employing the Adam optimizer [29] with a learning rate of 0.01. Early stopping is applied based on validation loss with a patience threshold of 5, utilizing a randomly selected subset representing 50% of the original data set. Each transformer layer uses two heads, as we empirically demonstrated that increasing the number of heads does not impact performance in our experiments. Each layer consists of the following components (in order):(1) Keras' multi-head causal self-attention block, with key_dim = value_dim = embed_dim/2; (2) Skip connection and layer normalization; (3) One hidden layer feed-forward network using the ReLU activation with dimension = 2× embed_dim; and (4) Skip connection and layer normalization.The world_population.csv data set, used for the experiments in Section 2, is obtained from Kaggle.According to the author, this data set is created from World Population Review.The us-state-capitals.csv data set, used for the experiments in the beginning of Section 2, is obtained from this Github repository. Its source is unclear.The uscities.csv data set, used for the experiments in the beginning of Section 2, is obtained from Simple Maps, with a CC 4.0 license.Below we provide additional details regarding the synthetic data used in our experiments.1. For experiments in Table 1 , the training data consists of 50,000 sentences. In the clean version, sentences are generated uniformly as described in Section 2.1. In the corrupted version, sentences are generated in a similar manner, but each (c i , d i ) pair is replaced by The ICL prompt formats are also described in the same subsections. 9. For experiments in Section 4.3, the corpus generation process is as follows:(c i , r j ) or (d i , r j ) 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: We believe this paper poses no such risks as we do not train large-scale language models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] .Justification: The existing models used in this paper (e.g., LLaMA) are properly credited. The sources of the data sets used in our experiments are mentioned in Appendix K.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] .Justification: This paper does not include any new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] .Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] .Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Software that replicates the empirical studies can be found at https://github.com/yixinw-lab/ icl-unstructured. Details on implementation, experiments and data sets are provided in Appendix K.We can also theoretically show that ICL works (up to a certain number of training examples) in this scenario, but the calculations are extremely tedious. Therefore, we only present empirical evidence in Table2. 
 
 Appendix:  


Decision: This paper examines how in-context learning ability can emerge from training on data containing particular types of simple patterns and some distributional assumptions. The authors explore a progression of increasing complex settings, finding that even a CBOW-style bag-of-words model can exhibit ICL-like behavior on some, while others require models to have access to positional information, multiple layers, or the presence of specific “blocked” noise structures in the data.

Reviewers agreed that this paper made a strong theoretical contribution to our understanding of how ICL can emerge, and appreciated that it was empirically validated in synthetic, controlled settings. They also highlighted how the analysis identified particular components that were necessary for ICL in these settings.

As weaknesses, reviewers nuMz, cRrU, and xShA all noted the limited scope of experiments, being limited to small models and simple architectures. For a theoretical contribution, this shouldn’t be a deal-breaker, although (as suggested e.g. by reviewer cRrU) the paper could benefit from more discussion that connects this to more natural settings, such as grammatical sentences.

While the substance of the contributions is strong, reviewer xShA also noted that it oversells the scope a bit; with the simplified settings studied, it could perhaps benefit from a more narrow framing. The authors noted in the response that they plan to update the title, and I would encourage them to highlight in the discussion how the setting either departs from, or represents a distillation of patterns that are likely to be found in real-world data.

Reviews: review: paper_summary: paper_summary: The paper investigates the emergence of ICL from training on unstructured data. It explores two types of ICL tasks: the first involves input-output pairings that frequently co-occur within sentences, and the second comprises recognizable patterns that do not commonly co-occur. The authors demonstrate that the first task can be addressed by modeling co-occurrence information, and highlight the importance of positional information and blocked noise structures through the second task. Additionally, the paper discusses scenarios where ICL fails. Both theoretical and experimental evidence are provided in the paper.
strength_weakness: strength_weakness: - There is a lack of experiment details in the paper, such as the number of training sentences used, the frequency of each input-output pair's repetitions within training sentences, and the methodology for generating training and evaluation data.
- The scope of the experiments is limited, using small datasets and simplistic model architectures. Moreover, there is an absence of real-world data.
- There is uncertainty about whether the findings would scale well to complex real-world data, larger models and higher embedding dimensions.
questions: questions: Can you add examples of training sentences and prompts for experiments?
limitations: limitations: Limitations are discussed in the paper.
paper_summary: paper_summary: The paper studies the emergence of ICL using a synthetic setting. Particularly, it focuses on the importance of concurrence statistics to ICL, and shows that under some simplified conditions, a CBOW-styled model is proven to complete the correct completion for an ICL example. The paper additionally proves the importance of position encodings in the studied setting, showing that when the ICL task is inherently task dependent, position encodings is necessary for good performance.
strength_weakness: strength_weakness: The main weakness is that the paper studies a very synthetic setting. I understand some simplification are needed for the derivation of theoretical results, and this is OK. But, for example, it would be interesting to try deriving results on cases where the input consists of valid grammatical sentences, rather than a concatenation of tuples. If that is not possible, the paper should clearly state the disparity between "real" ICL setting and this setting. While LMs can be presented with tuples in inference time, they are usually not trained on such tuples, but rather on free form language.
questions: questions: The experimental results use cross entropy loss rather than the squared loss used in the theory. Why?
limitations: limitations: See above.
paper_summary: paper_summary: This paper studies the emergence of in-context learning (ICL) in both CBOW (Mikolov et al,. 2013) and Transformer models. The focus is on simple synthetic settings that can be studied both theoretically and through synthetic experiments with small models. The paper identifies co-occurence as a key ingredient for ICL to emerge in CBOW. Then the paper considers how positional information is critical for a Transformer (or any) model to identify certain order-dependent patterns. Finally, the paper presents two sythetic scenarios involving repetition in which ICL fails with a simple model.
strength_weakness: strength_weakness: - The paper states that "ICL is achievable by only modeling co-occurrence information using [CBOW]". However, this seems to miss the generality with which the term ICL is used. That is, ICL is commonly used for generation tasks such as full-sentence machine translation (not just the simple token-level translation examples in this paper). So to say that "ICL is achievable" seems like a misuse of the terminology. Without a more careful definition of ICL, this statement is invalid.
- After showing that Llama 2 is unable to use ICL to translate the word English words "soon" and "main" to Indonesian, the paper claims that "these models should be equally likely to produce the correct answer for any given [word], irrespective of its relevance to the in-context examples. However, our experiment demonstrates that this is not the case". This is a huge leap for a poorly designed experiment. Llama 2 was trained on 98.08% English data. The amount of Indonesian language data may have been miniscule. As such, co-occurence may offer an explanation for the result, but adjacency might be equally informative. To speak of co-occurrence without any discussion of adjacency seems a bit odd here. This same issue appears later in the paper's claim "This suggests ICL may arise from co-occurrence information", whereas a claim that it is informed by co-occurrence might be more apt.
- It is not clear to this reader why one would expect the setting in Section 4.1 to succeed via ICL in the first place. For example, we also wouldn't expect these settings to suceeed if they were presented to a supervised learner either because of the mismatch between the training examples and the prompt example.
- The paper relegates the entire 2.5 page related work section to the appendix. It would be better to include more in the main paper; at present only lines 25-32 in the Intro address prior work making it difficult to position this paper early on.
questions: questions: - In line 258, the paper claims that "each token in V should be present as the first token in both the training and test sets." But shouldn't we be interested in whether this is really required in the largest of LLMs? Is there any way to connect this result back to larger models?
limitations: limitations: Yes
paper_summary: paper_summary: The paper basically presents three theoretical analyses related to ICL. The section 2 shows that we can use CBOW to do the (country)-(capital) kind of ICL. The section 3 shows that positional embeddings, multiple layers in autoregressive LM, and blocked noise structures are important for ICL. The section 4 shows that ICL could fail when there are systematic and consistent mismatches between the training sequence and testing sequence.
strength_weakness: strength_weakness: I think the main weakness of this paper is the mismatch between scope it seems to cover and its actual scope. The title and abstract suggests that this paper tries to study why the ICL works well given the unstructured training data in practice, but what the paper actually did is thoroughly studying 3 toy situations. 

I understand that we often have to simplify the situations in order to get strong theoretical conclusions. I also think that, at least to me, it is difficult to derive those theoretical results in such simplified situations and all the toy situations are relevant to the ICL. Nevertheless, I think these situations are not very representative to most of the practical ICL settings. After all, most ICL is beyond just relying the co-occurrence statistics of the sentences like CBOW, finding the first letter of the word, and repeating some words in the context. 

I understand that nowadays, one paper often needs to oversell its scope in the title and abstract to get attentions. Hence, although I suggest that the authors can revise the main storyline to reduce the overselling, I am fine with the current title and abstract if this paper is accepted at the end. I am also not a researcher who studies theory, so I do not know how significant or novel these theoretical results are. Therefore, I would like to let other researchers who have better theoretical background to rate this paper.
questions: questions: I have no specific question to the authors, so I think the rebuttal won't change my opinion. I won't lower my score if the authors choose to skip the rebuttal to my comments.
limitations: limitations: The limitation discussion in the appendix K is fair.

Comments: title: Reply to rebuttal
Response
Response to the Rebuttal
Reponse
Thank you for willing to revise the title and abstract
comment: Thank you for your response! We completely agree with your point and will make the necessary revisions to lines 75-77.
Thanks for the thorough response. You've mostly addressed my concerns, but one of the small (but still important!) odd claims you make is not, and that is raised again below -- hopefully more clearly this time. 

> We have updated the paper to clarify that this statement applies to ICL tasks with known input-output pairings

Great. Qualifying definitions of ICL seems very important.

> the experiments in Section 2.4 do not involve any rare languages, and the same conclusion applies.

Sorry -- I think you latched on to my rare languages point and missed the broader question about poor experimental design. The paper still claims in lines 75-77 that "If ICL stems from the ability of LLMs to recognize consistent mappings in test prompts, these models should be equally likely to produce the correct answer for any given [word], irrespective of its relevance to the in-context examples. However, our experiment demonstrates that this is not the case". 

But why would anyone expect that a model should be equally likely to produce a correct answer for any given word irrespective of its relevance to the in-context examples? That is, your if/then statement does not seem like something most researchers would agree with. For example, decades of work on NLP and machine learning have shown that when learning through parameter estimation (instead of ICL), the relevance of the training examples to the test examples is of critical importance (i.e. the entire NLP literature on domain adaptation) (see [1] and [2]). Similarly, recent work on retrieval augmented ICL and the like has shown that large gains are possible when one retrieves a collection of in-context examples that are relevant (usually in an nearest-neighbor embedding sense) to the test instance (see [3] and [4]). In other words, the dominant view is that the when a model is learning (either via fine-tuning or ICL), whether the test instance is relevant to training examples is a critical factor. (Note that the citations here are just ones I could quickly find for MT. But I imagine you could find similar papers supporting this for, say, classification tasks closer to your experiment in Section 2.4 as well.)

In other words, it seems reasonable that one should counter your statement "our experiment demonstrates this is not the case" by pointing out that the LLM could simply be learning to recognize consistent mappings in test prompts /and/ that the mappings it infers may be domain specific. That would better align with the fields current understanding of how learning, be it through parameter estimation or ICL, happens in most models (LLMs and other varieties too).

This is a relatively minor issue with the paper, but the claim seems so outlandish that I'm returning back to it here.

[1] "A Survey of Domain Adaptation for Neural Machine Translation"
[2] "Domain Adaptation and Multi-Domain Adaptation for Neural Machine Translation: A Survey"
[3] "Towards Robust In-Context Learning for Machine Translation with Large Language Models"
[4] "Efficient Machine Translation Domain Adaptation"

> We have expanded the Introduction section to better relate our work to existing literature and clarify its position in the ICL research landscape. 

Great!

> In practice, this condition is likely met due to the vast size of LLMs' pre-training data.

That seems reasonable.

-----

Under the assumption that lines 75-77 can be fixed easily, I'm bumping my score up to a 5.
Thanks for the clarification. I maintain my positive assessment.
I appreciate the authors' responses during the rebuttal. The experimental details are helpful for the comprehension of the work. I would like to maintain my original score as I am not very confident in my assessment over the theoretical contributions of this work.
Thanks for the clarification.

We confirmed that the experimental results with the squared loss align with the theoretical findings. However, we did not include it in the paper because the squared loss is rarely used in practice.

Concretely, in the context of Theorem 1, an accuracy of $1$ is achieved when $(p_0, p_1, p_2) = (0, 1, 0)$ or $(0, 0, 1)$ under the squared loss in the clean scenario, consistent with our theoretical results.

The full results with the squared loss are as follows:
- In the clean scenario, an accuracy of $1$ is achieved for each of the 6 $(p_0, p_1, p_2)$ tuples.
- In the corrupted scenario, an accuracy of $0$ is achieved when $(p_0, p_1, p_2) = (0, 1, 0)$, while an accuracy of $1$ is achieved for the remaining 5 tuples.

Under the setting of Theorem 2, the balanced accuracy when $(p_0, p_1, p_2) = (0, 0, 1)$ is $1$ under the squared loss, also confirming our theoretical results.
Thanks for your response.

Please note I asked why the squared loss was not *also* used  in the experiments.
I raise my presentation score from 2 to 3 and overall score from 5 to 6. 

Nevertheless, I remain my confidence to 2 because I think the main contribution of this paper is its theoretical analyses but I do not have sufficient background to judgement the this main contribution.