From Unstructured Data to In-Context Learning: Exploring What Tasks Can Be Learned and When
Authors: Kevin Christian Wibisono
Yixin Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: in-context learning
large language models
unstructured data
continuous bag of words
co-occurrence
Primary area: safety_in_machine_learning
TL;DR: We demonstrate the significance of co-occurrence, positional information, noise, and data structures for in-context learning from training on unstructured data.

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.

From Unstructured Data to In-Context Learning: Exploring What Tasks Can Be Learned and When
Kevin Christian Wibisono University of Michigan, Statistics kwib@umi ch, edu
Yixin Wang University of Michigan, Statistics yixinvoumi ch. edu
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 tasks like word analogy. To address this gap, we examine what enables ICL in models trained on unstructured critical sequence model requirements and training data structure.
data, focusing We find that many ICI. capabilities can emerge simply from co-occurrence 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 unseen tokens. Finally, we identify two cases where ICL fails: one in logic reasoning tasks that require generalizing 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.'
Introduction
Large language models (LLMs) such 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, well-trained LLM should detect the Englishhto-nndonesian pattern in the prompt and predict gajah- the 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,d, ...d....dde dx where (Ck, dx.'s represent word pairs with specific semantic relationships.
Indonesian
Many efforts have sought understand ICI. 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
Software that replicates the empirical studies can be found at icl-unstruee ucI-unstructured Details on implementation, experiments and data sets are provided in Appendix K.
com/yixinx-lab/
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Section 2: ICL from CBOW
Scction 3: ICL from modeling positions
Scction 4: Failures ICL
Example:
Training data:
Example:
Training data:
Example:
Training data:
The cagital city of
pqc, pqe,TWxZe rWxZd,
5233,5 the next
abca pqrs def d
PEX the arport
G, sprrss,,
Indonesis Jazurt.
number: U.A.
pzzm becb dacd
code for Beijing.
G2 m
Bejjing finctions the
capital China.
Ste
What number comes nextr 2,1,,,2, 5,76,5 Guess
yart aded boac
ORD uniquely idautides the
airport serving Chicagn.
C mpprtdd
are acound 100 Rupees per liter
Gus pricce
wro.AB
number 1,2,2,2 4.67.6. 2,9.79 1,3,6,3. Extend the parem please.
deae bfcf tqzn.
SIN denotes the primary airport for Singagore. DEN sirport located Derver.
c. polqwd,
Coll, the cormency of (ihans,
ICL prompts::
ICL prompts:
JCL prompts:
facing depreciation.
d
abda edec bdle
abulb cded bdodd
ICL prompt:
ad
Ghant, Accra Nigeria Lagos
ICL prompts:
ICL prompt:
Japan Yea
Chino Beijing]
India Kupge China Yoon
Patterns:
(c, (c)
2,6.2, 8.9.18,
6,9.299 1,2,222 5,12
Patierns:
Repeat o*or 2 token
PEK Beijing ORD
Chicago SIN Singspond
Pattern:
4)
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 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, 50J. This task involves identifying relationships between word pairs, such as (country)-(capital) and (English same relationship to complete sequence. For this task (sce left of Figure 1), 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 prre-rranfoommer language models like continuous bag of words (CBOW) [36], without needing positional information attention mechanisms.
translation), then applying the
The second set of results involves ICL for logic reasoning tasks that require recognizing patterns that do not commonly co-occur in 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 positional information and blocked nuisance structure (c.g.. pqrs in Figure 1) are crucial for the success of ICL in these tasks. This finding aligns with Chen et al.'s '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 not clustered in blocks.
present. We prove that
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 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 ICI. task sequence then requires the model to recognize this meta-pattert of repetition and generalize it to a novel, unseen starting pattern. In the second scenario (right example), we examine 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.
Summary of contributions. We (1) theoretically and empirically show that ICL for word analogy tasks with semantically related word pairs can arise from modeling co-occurrence patterns using CBOW, (2) prove that, to recognize token patterns and generalize them to novel tokens, ICI. requires modeling positional information and blocked nuisance structure, and (3) present scenarios where ICL. fails, highlighting the crucial role of training data structure for ICL.
2

---

Related work. Below, we highlight some of these studies and explain how our research aligns with, yet differs from, these approaches. We include a detailed discussion of related work in Appendix A. Numerous studies have connected ICI. to classical methods, including gradient descent 53 17, 55, 66), Bayesian inference [14, 56, 67], and Newton's method [20]. In contrast, our work links ICL. to the continuous bag of words (CBOW) model, showing that ICL for word analogy tasks can be achieved by learning co-oceurrence patterns. Several studies have examined the pre-training aspects of ICL, such as data distribution [11, 30, 37] and task diversity [42, 63]. By comparison, our work emphasizes the importance of co-occurrence, positional information, and training data structure for ICL to arise. Other research has explored ICL in specific data-gen aata-generating processes, such as discrete functions [8] and autoregressive processes [45]. In contrast, our work centers on data characterized by semantically related word pairs and repeating token patterns.
2 In-context learning can arise by modeling co-occurrence via CBOW
In this section, we focus on in-context learning (ICL) for word analogy tasks involving word pairs that frequently co-occur in training sentences; Figure 1 (left). To motivate the discussion, present two experiments using the LLaMA 2 model [51] involving countries (or US states) and their capital cities (see Appendix K for data sources). The prompts follow the format e₁ cjd1, cyd2,... , Cgds; C7, where G is a country (or US state) and de is its capital city. In this scenario, we consider ICL successful if the model outputs d7 the capital city of c7-as the most likely token.
Experiment 1. We consider all 160 countries with a population exceeding one million in 2022. Among these countries, 31 have capital cities that are not their most populous cities, denoted by type A. The remaining 129 countries fall under type B. Each ICL prompt includes three type A countries among C1, Gg to emphasize that the desired relationship is (copntry))ccapittl) rather than (country)- city). Subsequently, we randomly generate 1,000 prompts, with 500 having a e7 being type A country and 500 having e7 being type B country. The model's ICL accuracy is 0.58 for type A and 0.96 for type B.
Experiment 2. We consider all 50 US states, among which 33 are of type A and 17 are of type B, similarly defined. Following the setup in Experiment 1, we generate prompts for these states. The ICL accuracy is 0.69 for type A and 0.84 for type B.
In both experiments, LLaMA performs better on type B prompts (i.e., the capital city as the largest city). Since larger cities tend to appear more frequently as compared to smaller ones in the model's pre-training data, this naturally raises the question: Can/does ICL with frequently co-occuring word pairs arise purely from modeling co-occurrence patterns?
ICL via classical non-transformer-beee based language models. We prove that, for word analogy tasks with frequently co-occurring word pairs, ICL can be achieved by modeling token co-occurrence- without needing positional encoding attention mechanisms using classical, con-transformer language models such as the continuous bag of words (CBOW) model [36]. (It does not imply that ICL in transformer-based models arises through learning co-occurrence patterns.) We utilize CBOW variant where each center word is modeled conditional on all other words in a sentence, not just neighboring words. Specifically, each word has center and context embeddings Whe and Ew of the same dimension. Given a sentence IiI9 ... Z1, the i-th word (zz) is distributed (2,4))2)// 1/,) 1)), with uww 's and Uw learned by minimizing
as p(z; k x=+) x exp((u) Ej4t cross-entropy losses across all positions.
Roadmap of Section 2. In Section 2.1, we begin by considering a simple ICL task of the form C; di, Ci,di, Cies1 where (c;, (c) represents frequently co-occuring word pair (e.g., a country and its capital city) and i1, ......, i.,41, are all distinct. The focus is to investigate whether a trained CBOW model can correctly output d, We also explore two other scenarios: ICL tasks of the form c, de, ... Cr Copa and G, Ct, ... Ci,4 in Section 2.2 (two connected word relationships), as well as C, d; ... di,,, G2 and fr. ei,, fi (two disjoint word relationships) in Section 2.3. Section 2.4 concludes with synthetic experiments supporting the theory.
2.1 In-context learning on
word analogy tasks
We investigate ICL in single-relationshipp word analogy tasks, where the training data contains only one type of relationship between frequently co-occurring word pairs. This task takes the form of e; dl, .......... Ci de Ge41 where (c,, de) pair represents frequent co-oceurrence, such as country and its capital city. The vocabulary consists of Ci:K, d1:k, Fi:L, where ris represent other words (c.g..
3

---

stop words). We first introduce Theorem I, which states that ICL can arise if each sentence consists of exactly one (c,, d,) pair, as long as the number of in-context examples (E) 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
Appendix B.
Theorem 1 (ICL
relatiosnoi word analogy tasks). Let K, 2 S 2 3. Suppose each training sentence of length is generated by selecting one (c,, di) pair and S -2 distinct ri uniformly at random. We train a CBOW model with the squared loss and a sufficiently large embedding dimension on these sentences. Given a prompi Ci2 di, ... Ci Ci,di, Cie+1 with distinct ig 's, the KL(S-1)²
model correctly predicts dietn if and only 2f + < (I-
As an example, when each training sentence contains exactly one country-capital pair (i.c., (ci, d:)), Theorem says that a trained CBOW model will correctly predict di (i.e., the capital city of 41,41) given an ICL prompt of the form Ci d,, Ct, di, Ci provided that the prompt length is not too large. Intuitively, this behavior is due to the presence of Ciz+, in the ICL prompt, leading the model correctly predict die given the frequent occurrences of the pair (Ciey die in the training data. However, when the prompt length too large, the model will instead predict one of the ri 'ss (see Theorem I's proof in Appendix B for more details). Moreover, if we let I. - oo and fix K and S, the condition in Theorem becomes 28 + < K(S - 1)2/(5* (S- 2) This inequality trivially holds if the prompt length is set be S to match the length of the training sentences.
Furthermore, it is possible to adapt the proof of Theorem to handle the case when each sentence and fixing
comprises exactly two (not one) different (c, d:) pairs. In this case, letting L
K and 5, the model correctly predicts diet, given the same ICL prompt and only if 28 + 1
25--2) This upper bound is strictly larger than K(S - 1)² /) - 2) when each ((-2)(8-21(8-4))
sentence contains exactly two (c,, d;) pairs, ICL under the squared loss holds for longer prompts.
Experiments. To empirically verify Theorem and its generalizations, we conduct experiments using the cross-entropy loss with S = 8, K 10, L - 20, and & 3. We explore multiple (Pu, P1, P2) values, where P&: denotes the probability of having exactly i pairs of (c,, de) in the sentence. For each (Po, P1.P2) triple, we also introduce a more realistic setting where e; and d: do not always appear together by considering its corrupted version. In this setup, each (c,, de) pair has 25% chance of being replaced with (c,, r2) and a 25% chance of being replaced with (de, r5) for some j E [T.. More details are provided in Appendix K.
Results. Table 1 displays
the average accuracy for each scenario, calculated over 10 repetitions. Notably, when (Po. P1. P2) is (0, 1,0) or (0, 0,), 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 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,, di) pair, in reality. On the other hand, perfect ICL. performance observed in other settings (e.g., when the training sentences contain either zero, one, two (c, d;) 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.
Table 1: ICL on different single-relationship word analogy tasks, averaged over 10 repetitions, demonstrates stable, good performance across embedding dimensions (dg), Theorem I suggests. The corrupted setting also demonstrates excellent ICL ability under certain scenarios.
Clean
Corrupted
(po,Pi, Pi, P2)
dF
10
dF
100
dp
10
de 100
(0, 1,0
0
0
(0,0,1)
0
0
0
0
(1/2, 1/2,0)
0.99
0
(1/2,0,1/2)
1
1
1
1
(0.1/2,1/2)
1
1
0
0.01
1//3,1/3,1/3)
1
1
1
2.2 In-context learning duallcoomeeded-relatiinsstt word analogy tasks
Building on the scenario that contains only a single type of relationship between frequently co- occurring word pairs, namely dc,, now explore ICL monal-commeteed-rllttonssss word

---

Table 2: ICL on dual-ccomeetee-rellaionnni tasks, averaged over 10 repetitions, achieves perfect
accuracy when (Po.Pr, P1) E (11/2,0/1,2) 10.1/211/2), (1/3. 1/3, 1/3)] regardless of architec- tures and embedding dimensions (dæ), as Theorem 2 suggests. When (Po: Pl, PI,P2) = (1/2, 1 0), ICI. performs better under imbalanced or extreme scenarios and with larger dg.
Balanced
Imbalanced
Extreme
(Po,Pi,P2)
dg = 10
dg = 100
d== 10
dr= 100
dg = 10
dg = 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)
11/2.1/2.0)
(0.53, 0.47)
(0.51, 0.50)
(0.69, 0.68)
(1, 1)
(0.94, 0.93)
(1,1)
(1/2.0,1/2)
(1,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
11/3.1/31/33)
(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 (ci, d:) and (c;, ez). For instance, e; might represent a country, di its capital city, and e; its currency. The vocabulary is comprised of Cı.K, di.K,, EI.K, FI:L, EI.K,FI:L. ry's represent other words. Moreover, the corresponding ICL tasks take the form Giy di, ... Cip Ci,di Giess and Ot 6/1 C. C,, where the model is expected to output d and Ciues respectively. These can be regarded as task selection since the model should use the in-context examples to infer the
where
tasks. We present Theorem 2, stating that a trained CBOW model can perform task selection if each sentence contains exactly two distinct (c,, d:) or two distinct (G,, e;) pairs with uniform probability.
Theorem 2 (Task selection in CBOW). Let K, L 2 2 and S 2 5. Suppose each training sentence of length S is generated by selecting two distinct (Ct, de) pairs or (ca,es pairs, and S - 4 distinct r; uniformly at random. We train a CBOW model with the squared loss and a large enough embedding dimension. Given a prompt Ci2 di, ''-Ca Ci,di is more likely to predict dietz (Pig-1) than Gieyz (dietz). (The proof is in Appendix D.)
Ciesi Siddiiie.
(c ..,Ci, Cxe Ciets) with distinct in 's, the model
According to Theorem 2, when each training sentence includes two (c, d;) pairs two (c,, e,) pairs, a trained CBOW model is capable of performing task selection. To intuitively understand this result, consider the ICL prompt of the first type, i.e., G, d,, ... C. C,,d, d,, Ciz.: Here, the output is more likely to be dic+: than Ci.+, since diy,, co-occurs with the other d,, 's in the training data (and eit+, does not). Note that in Theorem 2, we unrealistically require each sentence to contain either two distinct (cz, d4) pairs or (c, e4) 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 l = 3. Each training sentence is equally likely to be a cd sentence (i.e., containing (c,, d,) pairs) (i.e., containing (q, 6 pairs), but not both. We explore multiple (Pu. Pl. P2)'s, where ps is the probability of having exactly i pairs of (c.d,) for ed sentence, or k pairs of (c,,e,) for 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 ed (ce) sentences; and extreme, where I./3 of the words can only occur in cd (ce) sentences. More details provided in Appendix K.
sentence
Results.
Table 2 shows the accuracies of both tasks for each scenario, averaged over 10 repetitions.
We observe perfect accuracy when (Po. (Po.PI.P) P2) E (1/2,00112) (0, 1/2, 1/2), (1/3, 1/3, 1/3)) across all embedding dimensions and scenario types. The zero- accuracy when (po, P1. P2) or 1,) (0, 0, 1) is again an artifact of the cross-entropy loss, discussed in Section 2.1.
Interestingly, ICL works in the imbalanced and extreme scenarios when (Po- P1. (1/ 0). where sentences do not contain more than one (c;, de) or (G,,e) pair. To see this, consider the balanced scenario where each r; is equally probable to appear in both types of sentences. Given a prompt of the form cs di, ... Ci di Cie41 it is easy to see that the model should output diey or Cieti with equal probability, On the other hand, in the imbalanced and extreme scenarios, the information from the r 's can allow for task selection, thus contributing to the success of ICL.
We can also theoretically show that ICL works (up to a certain number of training examples) in this scenario, but the calculations extremely tedious. Therefore, only present empirical evidence in Table 2.
5

---

Table ICL on dual-ddisjoint--elatoonnhii tasks, averaged over 10 repetitions, achieves perfect aceu- (1/3, 1/3, 1/3) regardless of architectures
racy when (Po, Pro.Pi. PI.P2) E and embedding dimensions (d When (Po,P1,P2) = (1/2, 12,20)) ICI. already performs well
under the balanced scenario.
Balanced
Imbalanced
Extreme
PL,
dx = 10
de = 100
dr = 10
dg = 100
dØ = 10
dg = 100
(0, 1,0)
(0, 0)
(0, 0)
(0, 0)
(0, 0)
(0, 0)
(0, 0)
(0,0.) 0,
(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)
01/2,0,1/2)
(1,1)
(1,
(1, 1)
(1,
(1. 1)
(1.
(0.1/2,
(1.1)
(1.1)
(I,
(I,
(1,
(L. 1)
11/3.1/3./33)
(1.1)
(1.1)
(1.1)
1I,
11,
(1.
2.3 In-context learning
poal-ddisoont-rllationsshh tasks
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., (ct, d4) and (ei, Ji). For example, (c,, d4) represents country and its capital city, and (ei, fi) represents a company and its CEO. Our vocabulary consists of Ci:K, d1.k. Ci:K, fI:K. .ILL. where r3's represent other words; see Appendix K for details.
Results. Table 3 summarizes the accuracies of the ICL tasks C, di, ...,,, C,,d, G4. and e,, fi, f..ee. for each scenario, averaged over 10 repetitions. Similar to the connected setting in Section 2.2, we observe a perfect accuracy when (po. Pl, P2) E (1/2,0011, 2), (0, 1/2, 1/3, 1/3)} across all embedding dimensions and scenario types. However, when (po.PI.P2 P..P1 P2) = (1/2,1/2, 0), 0), ICL already works well 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 ed (ef) sentences can contain some e, 's and fi's (c, 's and d, (s). We also obtain a perfect accuracy when (Pu. (Po.P1, P1.P2) P2) E {(1/2,0/1,2), (0, 1/2, 1/2), (1/3, 1/3, 1/3)) across all embedding dimensions and scenario types.
2.4 Experiments on a synthetic corpus
We conduct experiments on a synthetic corpus consisting of (country)(ccapiaal) and (country)-1OC 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 trained on this corpus: CBOW and five-layer two-head autoregressive transformer. Both models have an embedding dimension of 100. We then compare the ICL accuracies for both rela- tionships given to five in- in-context examples. For the CBOW model, the country-capite 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-capita 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 a sentence, such as (word)-(frsst 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 simpler task of modeling Ti " Theorem underscores the importance of positional information to correctly predict 2i, from Fi, Tig in single-layer model, and provides a construction of an attention-based model achieving zero loss and perfect accuracy on this task. Its proof in Appendix
Theorem (Necessity of modeling positions). Let the vocabulary be V = 2 ,IVI} and the training sequences take the form 24, Ligh where In & Σiz & Iis # Iiz are chosen uniformly at random from V. Consider a one-layer model that predicts the last Ii, via a learned function f(Ar,, Fig J, Fig) 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(((2s, 1), (Zeg 2)}, (Zig, 3)).
Here, I [( , ] [igg represents a scenario where the model lacks positional information (e.g. S is a -layer autoregressive transformer without positional embeddings). Note that the output of this function is identical for inputs 24, Tig and 21, which leads to the impossibility of attaining zero loss. In contrast, f(f 1), (Iiz. 2)}. (Ii,:3) 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 autore- gressively learn sequences of the form I;, FigTing and assessing their accuracy in predicting the last token on 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 embed- dings: learned, sinusoidal, no positional embeddings; and (iii) train-fest 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 cru- cial 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.
Table 4: Prediction accuracy with single/multi-layer mod- els. For ICL to occur, the first tokens of training sentences should cover the entire vocabulary (Both). Also, positional embeddings are essential, especially in one-layer models,
Both
Either
Pos. emb.
1-layer
5-layer
1-layer
5-layer
Learned
1
1
0
0
Sinusoidal
1
1
0
0
No pos. emb.
0.30
0.89
0
0
Multiple layers. Proposition 1 shows that multi-layer models can encode positional information without explicit positional embeddings.
Proposition (Multi-layer models can encode positions). Consider the sentence Ii, FigT Using a two-layer autoregressive model, the model's final output for predicting the last Tí, is given by (ig == 99 (1f ((F((())))))))))(()))))))))))( (2((2
( )F1), ((i)) for some f1, S2, J3. and gs-
The proof is in Appendix F. Proposition shows that we generally have (xx, Fig 4 ((r (i,ggg) Wig). 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, consider settings where each sentence contains repeating patterns. Section 3.1 focuses on a simple scenario where training sentences follow the form abacdc, where a * b and # d, or noisy variation of it. The ICL prompts maintain the same pattern but use different combinations of ab and cd from those in the training data. Our goal is to understand what types of training data facilitate ICL in clean noisy scenarios. Section 3.2 explores a more realistic case where two possible patterns are present: repeating the first letter (abca) and repeating the second letter (abeb).
3.1 In-context learning on pattter tasks
In this section, we examine the case where the training sentences follow the pattern abacde. To replicate real-world training scenarios, we also analyze how incorporating nuisance tokens into the training sentences affects the ICI. capability of autoregressive models. To formalize the discussion. let our vocabulary be V UW,, where A represents the nuisance tokens. We define S [(aaa) b) a, a
7

---

Table ICL on the clean data scenario regardless of architectures and embedding dimension (dp). The one-noisy scenario is the most challenging, with sinusoidal embeddings giving a higher accuracy. In the block- noisy scenario, learned positional embeddings result in significantly better ICL performance.
tasks, averaged over repetitions, achieves near-perfect accuracy in
dg =
dg 100
Pos. emb.
Clean
One-noisy
Block-noisy
Clean
One-noisy
Block-noisy
Learned
0.97
0.00
0.95
1.00
0.00
1.00
Sinusoidal
0.66
0.10
0.01
0.96
0.00
0.55
RoPE [48]
0.31
0.00
0.03
0.48
0.00
0.00
V.a * b) and partition S into S₁ (for training sentences) and Sg (for ICL prompts). This is to ensure that training sentences are distinct from ICL prompts. Furthermore, we assume {c[[] E S {d[]] C } = V. where c[i] is the i-th element of c. other words, each token in can be the first token in both the training sentences and ICL prompts. We consider three scenarios:
Clean: Training data follow the form abacde where ab, ed E S1. ICL prompts follow the form abacd where ab, cd E S2.
Training data follow the form abaede where ab, od E S1, with one nuisance token E N randomly inserted anywhere except the last position (to ensure ICL prompts do not resemble the training data). ICI. prompts follow the form abacd where ab, ed E S2.
One-noisy:
3. Block-noisy: Training data follow the form abacde where ab, ed E St, with three consecutive nuisance tokens 71 T2; ng N randomly inserted while preserving the aba and cdc blocks. ICL prompts follow the form abacdcef where ab, cd, ef S2.
We set the vocabulary size [V] attention layer as additional layers do not improve performance. See Appendix K for more details.
20, the number of nuisance tokens N = 20, and use only one
Results. Table 5 reveals interesting phenomena. First, under the clean data scenario, ICL. performs exceptionally well, with observed performance increase with learned positional embeddings and 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 formalizes these findings.
Theorem (Blocked nuisance token structure facilitates ICL). Consider a sufficiently large autore- gressive nosition-awart 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 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 nabaede, where n E N, may help in predicting the most likely token following the ICL prompt abacd.
3.2 In-context learning 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, and d, e, are distinct. We consider the clean and block-noisy scenarios as in Section 1. 1, and set [V]
= 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 an improvement in performance with five layers compared to one layer, particularly with learned positional embeddings.
This phenomenon 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 one-layer and five-layer models. While the five-layer setup effectively differentiates the two patterns, the lne-l 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-pane pattern case.

---

Accuracy over epochs (5 layer)
Accuracy over epochs (1-layer)
0.600
Pattern 1
0.575
0.8
0.500
0.525
0.4
02
0.25
100
100
Epoch
Epoch
Figure 2: One-layer models fail to differentiate the two patterns in Section 3.2, as evidenced by the accuracy trajectory graph on the left. On the other hand, five-layer models are capable doing so.
Table 6: ICL on dual-pattern tasks, averaged over 10 repetitions, achieves notably better accuracy using learned than sinusoidal embeddings. Near-pe Near-perfect accuracy is attained in the clean scenario by a 5-layer transformer with an embedding dimension (dg) of 100 and learned positional embeddings. The block-noisy scenario is challenging: the same model attains the best performance.
g 10
dg = 100
Pos. emb.
Clean
Block-noisy
Clean
Block-noisy
Learned
(0.33, 0.33)
(0.15, 0.16)
(0.51, 0.49)
(0.49, 0.50)
1 1-layer
Sinusoidal
(0.12, 0.66)
(0.03, 0.03)
(0.51, 0.48)
(0.06, 0.10)
Learned
(0.39, 0.39)
(0.23, 0.22)
(0.97, 0.98)
(0.87, 0.70)
5-layer
Sinusoidal
(0.32, 0.34)
(0.04, 0.04)
(0.83, 0.82)
(0.04, 0.07)
4 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 general- ization of a repetition meta-patten within sequences. In Section 4.2, we explore a word analogy task where relevant word pairs appear unstructured training sentences but are limited fixed positions. Section 4.3 concludes with synthetic data experiment supporting the theory.
4.1 Failed scenario 1: Sentences with repeating patterns
In this meta-pattern recognition and generalization task, each training sequence follows a repeating pattern based 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 F 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 from the prompt abbodde where a j b, j d, and e + f. Given the repeated pattern within each training sequence, a well-trained model might be expected to output continue the pattern established in the in-context examples: abb and edd. However, as seen in Table 7, all models fail to recognize and apply the pattern, resulting in incorrect predictions.
Formalization. We formalize generalization of this scenario. Let the vocabulary be V {1, ... .V]], and define S {(a, b) a, b E V, a & b}. To ensure training sentences are distinct from the ICL prompts, first partition S into S and S2, where {c[1] | S1} {c[1] 52] - V. Here, cli) denotes the i-th element of c. Suppose we autoregressively train a sufficiently achieve the minimum possible theoretical loss.
model that it is possible The training sentences take the form I 2 2 [ 221 ... INN NN where I; * x22 and (132 independently selected from S for every Appendix H, states that ICL fails regardless of the number of in-context examples.
large position-awar
[N]. Theorem 5, whose proof is in
Theorem 5 (Failure of ICL: Different repeated patterns), Consider the generalized scenario in Section 4.1. For any 1 < & S N, given an in-context prompt of the form D2g ... " D22
where Fs1 + I2 and [11, T22) S2 for every E [e], the model predicts zzi instead of xr2.

---

Results. Theorem 5 and Table 7 demonstrate that ICL achieves zero accuracy irrespective of the number of in-context examples (E 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 ICI.
4.2 Failed scenario 2: Sentences with co-oceurring word pairs restricted to fixed locations
We revisit the word analogy task in Section 2. The training data now comprises sentences of the form of appgrsbi, where (a;, (a) represents a frequently co-occurring word pair and p.q.r.8 represent other words. For the ICL task, we consider predicting big from the prompt as, bi, as, by, aig. where i1 ig, is are distinct. As each training sentence always contains an (a,, b.) pair at fixed location, we model to output bi, to maintain the pattern in in-context examples: as, 6,, and aszbi Yet Table 7 shows none of the models can identify the patterns and predict the correct token.
Table 7: ICL in failed scenarios, averaged over 10 repetitions, achieves zero accuracy for any architecture and embedding dimension (dg).
Failed scenario
1
Failed scenario 2
Pos. emb.
dæ 10
dr 100
dØ 10
dr = 100
Learned
0.00
0.00
0.01
0.00
1-layer
Sinusoidal
0.01
0.00
0.00
0.00
Learned
0.00
0.00
0.00
0.00
5-layer
Sinusoidal
0.00
0.00
0.00
0.00
expect
Formalization. We now formalize a generalization of this scenario. Let the vocabulary be {(a (o),,,)))ej)) U V. where V (1....... [VI represent other words. As in Section 4.1, autoregressively train a sufficiently large position-awar model that can achieve the minimum pos- sible theoretical loss. The training sentences take the form 0,81 02 .......0 U224; where i and v1:28 are independently chosen from [/] and V. respectively, uniformly at random. Theorem 6, whose proof is in Appendix I, states that ICL fails regardless of the number of in-context examples.
Theorem 6 (Failure of ICL: Different pattern structures). Consider the generalized scenario in Section 4.2. For any 1 S S & + 1, given an in-context prompt of the form a,, b,, as,b;, ... aiz with distinct ij 's the model never predicts big: it predicts uniform probability vector over V when 1 S l & k and bi, when { = +
Results. Theorem highlights the finding that the success of ICL relies heavily on how the patterns appear in the training data. In this scenario, the (a;, b,) 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.
4.3 Experiment on synthetic corpus
We conduct an experiment on a synthetic corpus featuring (country)-(capitu)) 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 five-layer two-head autoregressive transformer on this corpus, with an embedding dimen- sion 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- 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.
10

---

Acknowledgements. This work was supported in part by the Office of Naval Research under grant number N00014-23-1-2590, the National Science Foundation under grant numbers 2231 174 and 2310831, No. 2428059, and a Michigan Institute for Data Science Propelling Original Data Science (PODS) grant.

---

References
[1] M. Abbas, Y. Zhou, P. Ram, N. Baracaldo, H. Samulowitz, T. Salonidis, and Chen. Enhancing in-context learning via linear probe calibration. In Artificial Intelligence and Statistics, 2024.
[2] J. Abemnethy, A. Agarwal, T. V. Marinov, and M. K. Warmuth. A mechanism for sample-efficine in-context learning for sparse retrieval tasks. In Algorithmic Learning Theory, 2024.
[3] K. Ahn, X. Cheng, H. Daneshmand, and Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. In Neural Information Processing Systems, 2024.
[4] K. Ahuja and D. Lopez-Paz. A closer look at in-context learning under distribution shifts. In Workshop on Efficient Systems for Foundation Models at ICML, 2023.
[5] E. Akyürek, D. Schuurmans, J. Andreas, T. Ma, and D. Zhou. What learning algorithm is in-context learning? Investigations with linear models. In International Conference Learning Representations, 2022.
[6] E. Akyürek, B. Wang, Kim, and J. Andreas. In-context language learning: Architectures and algorithms. arXiv preprint arXiv:2401.12973, 2024.
[7] Y. Bai, F. Chen, H. Wang. C. Xiong, and S. Mei. Transformers statisticians: Provable in-context learning with in-context algorithm selection. In Neural Information Processing Systems, 2023.
[8] S. Bhattamishra, A. Patel, P. Blunsom, and V. Kanade. Understanding in-context learning in transformers and LLMs by learning to learn discrete functions. In International Conference on Learning Representations, 2023.
[9] A. Bietti, V. Cabannes, D. Bouchacourt, H. Jegou, and L. Bottou. Birth of transformer: A memory viewpoint. In Neural Information Processing Systems, 2023.
[10] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- Hesbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, Clark, C. Berner, S. McCandlish, A. Radford. I. Sutskever, and D. Amodei. Language models are few-shot learners. In Neural Information Processing Systems, 2020.
[11] S.C. C. Chan, A. Santoro, A. K. Lampinen, J. X. Wang, A. K. Singh, P. H. Richemond, J. Mc- Clelland, and Hill. Data distributional properties drive emergent in-context learning in transformers. In Neural Information Processing Systems, 2022.
[12] Chen, H. Sheen, T. Wang, and Z. Yang. Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality, arXiv preprint 44X14:2402.19442. 2024.
[13] Y. Chen, C. Zhao, Z. Yu, K. McKeown, and H. He. Parallel structures in pre-training data yield in-context learning. arXiv preprint 2XXv:2442.115300 2024.
[14] T.-R. Chiang and D. Yogatama. Understanding in-context learning with a pelican soup frame- work. arXiv preprint 24X. 10424, 2024.
[15] L. Collins, A. Parulekar, A. Mokhtari, S. Sanghavi, and S. Shakkottai. In-context learn- ing with transformers: Softmax attention adapts to function Lipschitzness. arXiv preprint arXiv:2402.1 1639, 2024.
[16] Y. Cui, J. Ren, P. He, J. Tang, and Y. Xing. Superiority of multi-head attention in in-context linear regression. arXiv preprint arXiv:2401. 174.2 2024.
[17] D. Dai, Y. Sun, L. Dong, Y. Hao, Z. Sui, and Wei. Why can GPT learn in-context? Language models secretly perform gradient descent as meta optimizers. In Association for Computational Linguistics, 2023.
[18) S. Dalal and Misra. The matrix: Bayesian learning model for LLMs. arXiv preprint 200.02402.03115. 2024.
12

---

[19] N. Ding, T. Levinboim, J. Wu, S. Goodman, and R. Soricut. CausalLM is not optimal for in-context learning. In International Conference on Learning Representations, 2024.
[20] D. Fu, T.-Q. Chen, R. Jia, and V. Sharan. Transformers learn higher-order optimization methods for in-context learning: study with linear models. In Workshop on Mathematics of Modern Machine Learning at NeurIPS, 2023.
[21] S. Garg, D. Tsipras, P. S. Liang, and G. Valiant. What can transformers learn in-context? A case study of simple function classes. In Neural Information Processing Systems, 2022.
[22] T. Guo, W. Hu, S. Mei, H. Wang, C. Xiong, S. Savarese, and Y. Bai. How do transformers learn in-context beyond simple functions? A case study on learning with representations. In International Conference on Learning Representations, 2023.
[23] M. Hahn and N. Goyal. A theory of emergent in-context learning implicit structure induction. arXiv preprint arXiv:2303.07977 2023.
[24] C. Han, Z. Wang, H. Zhao, and H. Ji. Explaining emergent in-context learning as kernel regression. arXiv preprint arXiv:2305.12766, 2023.
[25] X. Han, D. Simig, T. Mihaylov, Y. Tsvetkov, A. Celikyilmaz, and T. Wang. Understanding in- context learning via supportive pretraining data. In Association for Computational Linguistics, 2023.
[26] A. Haviv, O. Ram, O. Press, P. Izsak, and O. Levy. Transformer language models without positional encodings still learn positional information. In Empirical Methods in Natural Language Processing, 2022.
[27] Y. Huang, Y. Cheng, and Y. Liang. In-context convergence of transformers. In Workshop on Mathematics of Modern Machine Learning at NeurlPS, 2023.
[28] H. J. Jeon, J. D. Lee, Q. Lei, and B. Van Roy. An innoommtiiontthorree analysis of in-context learning, arXiv preprint arX5v:2401.15530, 2024.
[29] D. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[30] J. Kossen, Y. Gal, and T. Rainforth. In-context learning learns label relationships but is not conventional learning. International Conference on Learning Representations, 2024.
[31] S. Li, Z. Song, Y. Xia, T. Yu, and T. Zhou. The closeness of in-context learning and weight shifting for softmax regression. arXiv preprint arXiv:2304.1322 2023.
[32] X. Li and X. Qiu. Finding support examples for in-context learning. In Empirical Methods in Natural Language Processing, 2023.
[33] Y. Li M. E. lldiz, D. Papailiopoulos, and S. Oymak. Transformers algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, 2023.
[34] Z. Lin and K. Lee. Dual operating modes of in-context learning. arXiv preprint arXiv:2402. 18819, 2024.
[35] A. V. Mahankali, T. Hashimoto, and T. Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self attention. In International Conference on Learning Representations, 2023.
[36] T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 1.:0:1130..30 1301.3781, 2013.
[37] S. Min, X. Lyu, A. Holtzman, M. Artetxe, M. Lewis. H. Hajishirzi, and L. Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Empirical Methods in Natural Language Processing, 2022.
13

---

[38] C. Olsson, N. Elhage, N. Nanda, N. Joseph, N. DasSarma, T. Henighan. B. Mann, A. Askell, Bai, A. Chen, T. Conerly, D. Drain, D. Ganguli. Z. Hatfield-Dodds, D. Hernandez, S. Johnston, A. Jones, J. Kernion, L. Lovitt, K. Ndousse, D. Amodei, T. Brown, J. Clark, J. Kaplan, S. McCandlish, and C. Olah, In-context learning and induction heads. Transformer Circuits Thread, 2022.
[39] M. Panwar, K. Ahuja, and N. Goyal. In-context learning through the Bayesian prism. In International Conference on Learning Representations, 2023.
[40] K. Peng, L. Ding. Y. Yuan, X. Liu, M. Zhang, Y. Ouyang, and D. Tao. Revisiting demonstration selection strategies in in-context learning. arXiv preprint arXiv:2401.1208) 2024.
[41] C. Qin, A. Zhang, A. Dagar, and W. Ye. In-context learning with iterative demonstration selection. arXiv preprint MxXiv2311000888/ 2023.
[42] A. Raventós, M. Paul, F. Chen, and S. Ganguli. Pretraining task diversity and the emergence of non-Bayesian in-context learning for regression. In Neural Information Processing Systems, 2023.
[43] Ren, Q. Guo, H. Yan, D. Liu, X. Qiu, and D. Lin. Identifying semantic induction heads to understand in-context learning, arXiv preprint arXiv:2402. /3055, 2024.
[44] R. Ren and Y. Liu. In-context learning with transformer is really equivalent contrastive learning pattern. arXiv preprint arXiv:2310. /3220, 2023.
[45] M. E. Sander, R. Giryes, T. Suzuki, M. Blondel, and G. Peyré. How do transformers perform in-context autoregressive learning? arXiv preprint arXiv:2402.05787, 2024.
[46] L. Shen, A. Mishra, and D. Khashabi. Do pretrained transformers really learn in-context by gradient descent? arXiv preprint arXiv:2310.085540, 2023.
[47] A. Singh, S. Chan, T. Moskovitz, F. Grant, A. Saxe, and F. Hill. The transient nature of emergent in-context learning in transformers. In Neural Information Processing Systems, 2023.
[48] J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputiing 2024.
[49] S. Swaminathan, A. Dedieu, R. Vasudeva Raju, M. Shanahan, M. EazzaroGGredilae and
D. George. Schema-learning and rebinding mechanisms of in-context learning and emergence. In Neural Information Processing Systems, 2023.
[50] E. Todd, M. Li, A. Sharma, A. Mueller, B. C. Wallace, and D. Bau. Function vectors in large language models. International Conference on Learning Representations, 2024.
[51] H. Touvron, Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. LLaMA: Open and efficient foundation language models. arXiv preprint arXiv: 1 13971, 2023.
[52] M.-H. Van, X. Wu, et al. In-context learning demonstration selection via influence analysis. arXiv preprini 24Xiv:2402.117555 2024.
[53] A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L. Jones, A. N. Gomez, Kaiser, and
I. Polosukhin. Attention is all you need. In Neural Information Processing Systems, 2017.
[54] M. Vladymyrov, J. von Oswald, M. Sandler, and R. Ge. Linear transformers are versatile in-context learners. arXiv preprint arXiv:2402.1441: 2024.
[55] J. Von Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. International Conference on Machine Learning. 2023.
[56] X. Wang, W. Zhu, M. Saxon, M. Steyvers, and W. Y. Wang. Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning. Neural Information Processing Systems, 2023.
14

---

[57] K. C. Wibisono and Y. Wang. On the role of unstructured training data in transformers' in- context learning capabilities. In Workshop on Mathematics of Modern Machine Learning at NeurlPS, 2023.
[58] N. Wies, Y. Levine, and A. Shashua. The learnability of in-context learning. In Neural Information Processing Systems, 2023.
[59] J. Wu, D. Zou, Z. Chen, V. Braverman, Q. Gu, and P. Bartlett. How many pretraining tasks are needed for in-context learning of linear regression? In International Conference on Learning Representations, 2023.
[60] S. M. Xie, A. Raghunathan, P. Liang, and T. Ma. An explanation of in-contexi learning as implicit Bayesian inference. In International Conference on Learning Representations, 2021.
[61] Y. Xing, X. Lin, N. Suh, Q Song, and Cheng. Benefits of transformer: In-context learning in linear regression tasks with unstructured data. arXiv preprint arXiv:2402.00744, 2024.
[62] Z. Xu. Z. Shi, and Y. Liang. Do large language models have compositional ability? An investigation into limitations and scalability. In Workshop on Mathematical and Empirical Understanding of Foundation Models at ICLR, 2024.
[63] S. Yadlowsky, L. Doshi, and N. Tripuraneni. Pretraining data mixtures enable narrow model selection capabilities in transformer models. arXiv preprint arXiv:2311.00871, 2023.
[64] J. Yan, J. Xu, C. Song, C. Wu, Y. Li, and Y. Zhang. Understanding in-context learning from repetitions. In International Conference on Learning Representations, 2023.
[65] Yu and S. Ananiadou. How do large language models learn in-context? Query and key matri- ces of in-context heads are two towers for metric learning. arXiv preprint arXiv:2402.02877, 2024.
[66] R. Zhang, S. Frei, and P. L. Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 2024.
[67] Y. Zhang, F. Zhang, Z. Yang, and Z. Wang. What and how does in-context learning learn? Bayesian model averaging, parameterization, and generalization. arXiv preprint arXiv:2305. 19420, 2023.
[68] Y. Zhao, Y. Sakai, and Inoue. NoisyICL: A little noise in model parameters calibrates in-context learning, arXiv preprint 5 2024.
15

---

Supplementary Material
A
Related work
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 latent document- level concept for next-token prediction during pre- pre-training and a shared latent concept across input- output 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 informa- tion being implicitly inferred. Zhang et al. [67] showed that without updating the neural network parameters, ICL can be interpreted 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.
Bayesian model averaging parameterized by the attention
Garg et al. [21] formulated ICL as learning a specific function class F from prompts of the form (21, (x1). Rn, fz,), In+1) ) and their corresponding responses f(xn+1). Here, f e F, where F is a function class. In this context, ICL refers to the capability of a transformer to output a number close 9 given prompt of the form (y1,9(11): ((v))..... Un. g (1n)), Un+1), where g F. Many studies adopted this regression formulation of ICL. with some linking ICL to gradient descent. 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 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.
Akyürek et al. [5]. Von Oswald et al. [55], and Dai et al. [17] proved that transformers
In related exploration, Li 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
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 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 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 co-occurrence patterns via CBOW.
16

---

Numerous studies focused on the pre- -reiiriin 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 ICI. performance. Chan et al. [11] demonstrated that the ICI. 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 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- tre-training data typically consist of more uncommon tokens and challenging examples, characterized by 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 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 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 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 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 munsformer-basee 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 '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-theereel 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 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-specifi bigram distributions to distinguish between global and in 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.
cettmattion-hhooreeee view of meta-learnin (including ICL), allowing for
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 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
17

---

transformers significantly outperform ENN-based models because of their ability to develop n- n-gram heads, which are a generalization of induction heads. Sander 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-base 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 the Lipschitzness of the pre-training tasks. Xing al. [61] focused on linear regression tasks to identify transformer components that enable ICL. They found that positional encoding crucial, along with the use of multiple heads, multiple layers, and larger input dimensions. Cui 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 the gradient flow and observed the emergence of a task allocation phenomenon, where each attention head specializes in specific task.
Finally, several studies proposed various hypotheses on the emergence of ICL and provided theoretical justifications. Swaminathan et al. [49] introduced sione-structured causal graphs (CSCGs) to explain how ICI. can generalize to unseen sentences via a mechanism called rehinding. Li [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 al. [2] showed that transformers can execute ICL by dividing a prompt into examples and labels, then employing sparse linear regression 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 the ability of language models identify task from in-context examples, while task retrieval pertains to their ability to locate the relevant task within the pre-training data.
18

---

B Proof of Theorem 1
Proof. Let V 2K + L denote the vocabulary size. Consider sentence represented by its one-hot encoding (i.e., X {0, 1j)sss)) For every position E [S], the loss for predicting the word in the i-th position given all the other words is given by [1s e4) Xeilla where A V R VIXIV and e, & is a zero vector with on its i-th entry. Here, (V) is matrix consisting of the center (context) embeddings of all tokens, and A is 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 of losses for each position in each sentence. Lemma 1 gives closed- form expression of the minimizer.
The minimizer of the overall loss is given by A - ( - 2)B Here, B is matrix whose (i. entry is p(i.j), the probability that for a given (center, context) pair. the center is i [V] and the context is E [V]. Moreover, C is diagonal matrix whose i-th diagonal entry is p(i) [sivip((.,))
Lemma 1.
Proof. Let ((X) = E ||X c.) Xe,llž denote the sum of the losses corresponding to all tokens in sentence X. By direct calculation,
ac(X) 0A
2AX
E1s - c1) (eiss-e)))
2X c1)) xT -
Σ (1s---eis)
8
ct) (c((s--c)))
XT
Note that (15 -6; = (S-2)1 sxs +Iss and Ei=
e=()==e;) = sxs - Tsxs.
Now, let sentences be X1, X2, . XN.. The minimizer of the overall loss thus satisfies
N N
- - + X 1=1
X
- -ssxs X
(1)
N
We denote the number of (center, context) pairs across all sentences in which the center is and the context is j by #(i,j). Moreover, we define # (ii) = Σjeivi #(,,)). It is easy to see that Equation (1) can be rewritten as
A ((S-))B+() =B
where B is matrix such that its (i. entry is #(,f) N and Ö' is a diagonal matrix such that its i-th diagonal element is #(O) As + cc, an application of the law of large numbers yields N
#(.j] S(S D)((, almost surely and #() S(S 1)p(i) almost surely, where p(i, j) N is the probability that for a given (center, context) pair, the center is and the context is j, and pii) Σ E p).
Thus, N 0o, have
A ((S 2)B + -) where and C are defined the statement of Lemma 1.
We now define
Pi p(c, cj) p(d;, = p(ci, d3) p(di, cj) for any i j:
P2 p(rarr)) ry) for any # j:
Pa p(c, d,) p(d: c;) for any i;
P1 p(c.r,) p(d,, p(r,,c)) p(r,, di) for any i.
19

---

where the equalities in the probabilities are consequence of the data distribution.
For ease of presentation, denote square matrix with the diagonal and ,3 off the diagonal as We then have
X and a matrix with all entries as Y--
X0.p1 X Xp3.Pi
Xpa.p1 X0.p1
Ypu
B
Yp
Xpu
X0.p2
p4
Now, define a = (S-2)p1, = (S-2) c == (S5-2)p3. d = (S-2)p4, e 2(K +ps Lpt. and f (L 1)p2 + 2K It is easy to that
Xa,a
Xe.
Yd
(S 2)-
Xe. Ya
Xe.a
Yd
Ya
Xf,b.
Moreover, its inverse can be written as
X 11
X93.91
Y
((S-2)B+C)-
Xgy.11
Xgs.91
Yyu X gu.
Y
Y
where
= 2a(K - 1)(b(I- -( KL + ef.
-abb-abbaff+d"L
91
(20-c-e)3
2nb( - 1)+b(ote) -212
42
16-1)A
-2 - 1I(L - - - -1) + 2abe -)
- 1) 2ac 2)
+ 2(aa c)d2KT KT. be(c -I. +f(c
1T +
43
(c - (2a c e)A
(2),
44
-2u - 1]([I - -K -K -)- 1) 2ae -) + eed 1XL++ + be(c + e)(L -)f & cc)
4s
(e (2a c)
(20(K- - 26 (b-f)4
and 96
By computing == B((S B
C) given the following center words, the similarities between
them and all possible context words are follows:
Center word = 6; for any
4 2(K 1)pig: + P343 Lp494:
Gj :((K 2)pigi + Pids + Pagı + P1 + Lp49s (j + i);
d, :((K 1)pıq + Pals + Lp4q4;
dj 2(K 2)pigi + Pi + Paqı +P4s + Lp4gs (j 4 i);
-ry 2(K 1)p144 P344 + Pads (T. - 1)p442 (for any ÿ)
Center word d; for any
- -d K 1)P101 + P313 + Lp444
2 22)1191 + P1 Pagı + Pigs + Lpaga (j # 0);
-21 -1)p191 + P3gs + Lpiqii
20

---

- 2((K - -2)p19 + P19s + P391 + P14s + Lpi9s (j # i);
rj 2((K 11pp194 P344 P496 (L 1)p4 (for any j).
Center word ri
Gj 2((K 1)p441 p44s p493 + (L- 1)p244 (for any j):
d 2(K - -1)paq1 + p44s p493 (L. 1)p244 (for any f);
r.: 2Kp444 + - 1))222;
ry 2KP491 (L 2)p242 p296 + i).
Recall that the ICL problem of interest is the following: given context words C₁ di ...,,, Ci Cie11 we aim to predict die+1- Without loss of generality, we can rewrite the problem to predict de+1 given context words C₁ c1d1 c.d4Ce+1- We now compute the total similarity for each possible center word, where e 5 indicates the similarity between the word in the center and the word á in the context.
Cj (or any of c2.-....)) of e2 - + (8- 1)c d2:
dj (or any of d2, ... d + (c] d2 + - -e 1)c C2
ri (or any other r (s) 1)r + + (20 1)r ci
ce+1 LeT 02 + Ec d2 c.
de+1 (e] d2 + to 02 cj d1:
ce+2 (or any cx 's not in the context prompt) (6 1)c c2 tcj d2;
d (or any de 's not in the context prompt) : (e + 1)cc d2 + Ec] c2.
Note that correctly predicting de+1 is equivalent to the following conditions being simultaneously satisfied:
T > cf c1, equivalent to P34s > Psqs;
c > cfc and c| C2 of c1 equivalent P1 P3th P1 2p191 Psssi
J > >d and c d1 > c d2, equivalent to 2p141 + P3gs 2 P19s + P1 + P391:
280 02 + > (26 1)rT ct equivalent to 26(2(K 2)p141 + p1 + ps7 + pig3
Lp4q4) + + - 1)p1q + pa7s + Lp4q > (2f+ 1)(2(K - 1)p44 + p44s P403 + (L 1)p2g4);
In our data generating process, easy to see that P1 = 0, P2 = (S-2)(S-3)
L[L-1) P3 = +. and
p4 k where each ps is multiplied by a constant S(S 1) > (without loss of generalization)
to make calculations easier. From here, we have a 0, (S-2)
4(--) c 5x2. d KL
(S-2)²
S-1 e K and f = (S-1)S-2) 2) Substituting to the above, we have
(S-2)*
11 AKL(2S-3)
83
AKL(2S
44
AKI(28- 3)
K(S-2)(5 (1S-2)(8-1)*+ AKL(2S-3)
45
where A (8-1)(S-- 2) 0.
KL
21

---

We now check when these conditions are simultaneously satisfied. The first condition is equivalent
to Pa > 0 and > 2(8-2)"
(3-1)-22-3) which always hold. The second condition reduces to p3 > 0 and 2(S 2) + K(S - - 1)2 > 0, which is also true. The third condition can be written as Ps > and K(S - () - 1)3 > O, which always hold. The last condition becomes
(28+ + 1X(( () 2)* 1) + K(S 2)(5 1)2 2(5 2) < KL(S 1)²,
which is equivalent to
KL(S-1)a (K + - 2) 2 2(S 2)44
28 +2+10 <
completing the proof.
Note that this condition ensures that the model predicts de+1 instead of one of the 's..
22

---

C Comparison of ICL performance using squared and cross-entropy loss across different numbers of examples
Table 8: ICL performance in the clean scenario, evaluated with both squared and cross-entropy loss functions across different numbers of examples (0 8) with dæ 100, averaged over 10 repetitions.
Squared
Cross-entropy
(Po, P2)
2
8
0
6
8
1,)
0
0.87
0
(0,0,1)
1
1
0
0
1
0
0
0
0
(1/2,1/2.0)
1
1
0.34
0
0
(1/2,0.1/2)
1
1
1
1
1
1
1
(0.1/2.1/2)
1
1
0
0
1/3,1/3,1/3)
1
1
1
1
0
Table 9: ICL performance in the corrupted scenario, evaluated with both squared and cross-entropy loss functions across different numbers of examples (0 to 8) with dg 100, averaged over 10 repetitions.
Squared
Cross-entropy
(Pa, P2)
0
2
4
6
8
0
2
4
6
8
1,,1,0)
0
0
0
0
0
0
0
0
0,)
0.97
0
1
0
0
0
(1/2,1/2.0)
1
1
0.53
0
1
0
0
0
0
(1/2,0,1/2)
1
1
1
1
1
10,1/2,1/2)
1
0.76
0
0
1
0
0
(1/3,1/3,1/3)
1
0.18
0
From Tables 8 and 9, we observe that ICL with CBOW on single-relationship tasks performs better with squared loss compared to cross-entropy loss and with fewer demonstration examples. Also, ICL tends to deteriorate after certain number of in-context demonstrations. As detailed in Appendix B, smaller number of examples (e.g., zero) allows the model to produce the correct output instead of one of the ry's This in contrast with transformer-base LLMs,, which achieve better ICL. performance the number of demonstrations increases. On the other hand, ICL dual-relationship tasks as described in Section 2.2 requires at least one demonstration example to distinguish between the two tasks.
23

---

D Proof of Theorem 2
Proof. We show that given prompt of the form Gi di, .....c Ci, Ci, Cie41 with distinct trained CBOW model is more likely to predict dieta than Eiet If this is established, the other part of the theorem follows analogously. We now define
* Pi = p(c, d,) = p(d,, c2) = p(d,, = p(c,, p(er, cy) = ples, eÿ) for any i # j:
p(r.,) rj) for any i j;
Pa = p(a. d,) = p(d;, = p(c, e,) = p(e; G):
p4 - p(d, r2) - p(r,,d)) = p(e,,))) = p(ri, ej) for any i,j;
where the equalities in the probabilities (5-4)-55) Ps ºें and P1 R where each p; is calculation, have P1 kīK-1j* P2 [[
consequence of the data distribution. By direct
multiplied by S(S - 1) > (without loss generalization) to make calculations easier. Moreover, easy see that p(c; rj) p(ri, Cj) 2p4 for any i, and p(c, cj) 2p1 for any + j. Lastly, we define a = (S 2)P b = (S 2)p c (S 2)p3. = (S 2)p4, 2(K - p1 + Lp4, and f = 4Kpu p4 + 1)p2.
The next step the proof to use Lemma Appendix B to obtain the similarity matrix As previously, denote square matrix with on the diagonal and 3 off the diagonal as Xa, and matrix with all entries as Yy. We then have
X0,2p1 X p3.P1 X Ppa.p
X Pa.P1 X0,m Yo
X Pn.P1 Yo
Y2p4 pt Yp Xo,
X0,91 Yps
Y2p4
and
X2e
Xe.a
Xo.a
Yza
Xa.a
Xe,a
Yo
Ya
(S 2)=
(2)
Xe.a
Yo
Xe.a
Ya
Y2d
Yu
Ya
Xy.b
Moreover, its inverse can be written
X
X Xas.o
X X9a.91
You
Xge
Xgr.ga
Ygu
2)S-2BB- 2)--2)BCC)+
X Xgs.9
X9r.4n Yg.
Xay-qe
Y
Ygg
X Xgu.910_
91
for some Q11 92. -100 Recall that our task is show that given context words Gy "....... Gig di, with distinct in 's, the center word is more likely to be di than 6ig In other words, need establish that
dT Ci + die, dig +... dieas Ci, + dlec dis + dien Ciet1
e G1 + TeT di, +... e Cit + eT die + e Cie-1s
where T 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 B)B - C)-1, 11 By symmetry, the inequality reduces to d. dj > e, dy for any + j. By computing the matrix A, we have
d. d = Panl + Piqs + (K - 21)p1q + (K - 2)p + Lpıg1 + P1g5
and
e, d, P391 P193 (K 2)p11 + (K - 22)p11 Pi9r + Lp4g1
24

---

Thus, our problem again reduces to showing (K - 2)96 + > (K q) + KIK- 0.
Upon multiplying (3) and (2) and equating the result with the identity matrix, we have the following equations:
a(K 1) + oq3 + dl.qs + eqs + a(K K
1)46
(4)
(c + a(K - 2))q: + aqs dL44 aqs + (e a(K 2))96
(5)
aKK - 1) + cqs + dl + eq7 + a(K 1)9s
(6)
(c + a(K - 2) + aq3 dL44 + 047 + (e a(K 2)) 0.
Comparing (5) and (7) yields
a a(((K - 2)16 + Q5) - ((K 2)gs + (7)) e(gs - -6))
As (8 22)p 0 and e 2p1 (K 1) Ps P.L 0, only need to show that qs > 96-
Comparing (4) and (6) as well as (5) and (7), we have
aggs - 97) = (e + a(K - 22) - 96) elgs (7) a( 1)((s -96) + 1,
which reduces (4s (6)( ae(K 2) a²(K -1)) a. The conclusion follows since and
(S-1 -
aatae(K-2)
(e+a(K- -1)) > 0.
K
K(K 1)
25

---

E Proof of Theorem 3
Proof. Consider the instance of predicting a from abc, i... f((a,b), b), 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(fa, b).c). c). Thus, the sum of the cross-entropy losses corresponding to these two tasks is lower bounded by 2 log2 2 > O. Also, it is easy to see that we cannot achieve perfect accuracy since the predictions for abe and bac must be the same.
We now show that is possible to attain zero loss and perfect accuracy when the model includes positional embeddings, so that f(((a, 1), (b, 2)), (c, ()) * f(((b, 1), (a, 2)}, (c, 3)). As special case, consider simplified version of the transformer architecture, where
f(lla, 1), (0,)),)), EkEjache) (3x + +1) (xp)(xx(<< + p1) (T)T((a (xe + Ps))
Ene(abee exp((xx + +P)) (xe + Ps))
and
p(d abc) exp (z] f(((a, 1), (6, (6, (b,2)),(c,,3))
for any token d. Here, I; and pj represent the embedding of token i and position j. respectively.
Let pl Ps p. 22 P3 = 9: p5 Ps = r, x.. H2 8, .r. xy = t for any * J. p x; = for any i, p2 h; = e for any i, and pa z; = w for any Note that this holds due to the assumed data generating process. We consider the following construction: pl bll [v). P2 p2 Liv. and x; aei where is zero vector with 1 on the i-th entry. This implies p b/V). q u = ab, and w a.
[V. = a². 0.
By direct calculation, the cross-entropy loss of predicting a from abc is given by
exp(ana²) exp(a)a?) + exp(aza?) + exp(a3a²) [V|
log
where
exp(ab + blVl
a1 exp(ab + b|V1) + exp(a VI) exp(a2 (a++v]
exp(a + [V])
22 exp(ab + b[V1) + exp(a + VV) + exp(a2 +
cxp(a² + [V]
03 exp(ab + b(Vl) + exp(a + Vi) + exp + a [V])
Letting 6 = a² and + 0o, it easy to see that we can bring the cross-entropy loss arbitrarily close to zero. Consequently, we also have perfect prediction accuracy.
F Proof of Proposition 1
Proof. The intermediate representation of the first layer is given by fi((,, H), fe((x,, a1,),
fa(Kzi, Jig Zig), and fa((zi, Tiy Tig ) I.,), for some functions fi, f2, fz. and f4. To predict the last Tiys we use the third coordinate ta Tis) = 9s (1fi(1z, f2 J F, fa(fi, Lig) x,,)), for some function Gs. It is easy to see that in general, t(2,, F., Tiy) + ((21,,5,
the second layer representation, which given by
26

---

G Proof of Theorem
Proof. In the one-noisy scenario, each sentence takes one of the following forms: nabacde, anbacde, abnacde, abanede, abacnde, and abacdnc, where E .. 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 uniform probability vector over A.
Otherwise, output the conditional probability of c|2) given x, where (x, E Si. Here, represents the last non-nuisance token.
Under this rule, the predicted output for any in-context example abacd is never c, since & N. In the block-noisy scenario, each sentence takes one the following forms: ni mgnggabadde aban g nggde and abacden, Rygtt, where R1, T22, Yty E ... The minimum loss of predicting the ninth token given the first eight tokens attained by the following rule:
When the seventh token is not nuisance token, output the seventh token with probability one.
When the seventh token a nuisance token, output a uniform probability vector over M.
Under this rule, the predicted output for any in-context example abacdcef is resulting in perfect ICL accuracy.
H Proof of Theorem 5
Proof. Recall that each training sentence of the form 111 ... IN1"N2"N N1. Note that decompose the total loss L into L1 + L2 ... LaN, where Cg denotes the loss of predicting the g- g-th token given all the other previous tokens. As the 22 blocks are generated independently. the optimal loss should satisfy Li L4
L(NN-2) Liu L2 Ls
L L22). and L3- = La = [(N = L(3)- Therefore, it is sufficient to minimize f() L2) + L/3--
In order to achieve the minimum possible theoretical loss, we need to minimize Ln,, C12). and L separately. It is easy to see that Lii minimized by outputting the marginal probability of c[1], where Sy. Similarly, Liz is minimized by outputting the conditional probability of c(2) given vhy where (Ii, ,(2)) c(2)) St. On the other hand, it is possible achieve G()) value of zero by outputting Ri, with probability one.
Now, given ICL prompt z 12 1 (2 | 12134 where é < N,N, the trained model should predict Ie1 with probability one since [c[1] c S2) = V and our ICL prompt corresponds to Cia- This completes the proof.
I Proof of Theorem 6
Proof. We proceed similarly as the proof of Theorem 5. Concretely, we separately minimize by for g E [2k + 2). where Eg denotes the loss of predicting the g-th token given all the other previous that C1 is minimized by outputting uniform probability vector over d1:[1]+ whereas Cn (for any 2 S h S 2k + 1) is minimized by outputting uniform probability vector over V. Moreover, it is possible to achieve an Lzk-2 value of zero by outputting 6, with probability one.
tokens. It is easy
From here, given an ICL prompt of the form a; by, Gig big ... aiys the trained model should predict uniform probability vector over V if f < k, and b,, if l = kc + 1. In all cases, the model does not predict b,, completing the proof.
27

---

Limitations and future work
This study has several limitations. Firstly, the experiments are conducted 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-oceurrence results still apply to grammatical sentences, as the co-occurring pairs can appear naturally within them (e-g.. "Beijing the capital of China," " or "the city of Beijing located in China"). Lastly, real data sets are not utilized due to the lack of alignment with the study objectives.
Despite these limitations, 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.
K
Details of experiments and data sets
K.1 Architecture and implementation
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_dimn seieeddddm///__ (2) Skip connection and layer normalization; (3) One hidden layer feed-forward network using the ReLU activation with dimension 2x embed dim; and (4) Skip connection and layer normalization.
K.2 Source and details of data sets
The world poorlddpopulation.com data set, used for the experiments in Section is obtained from Kaggle. According to the author, this data set is created from World Population Review.
The us-state-capitals.ew csv data set, used for the experiments in the beginning of Section 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.
K.3
Details of synthetic data used in experiments
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 similar manner, but each (c,, d,) pair is replaced by (c:, ry) or (dg,ry) with probability of 1 /4 each. Test sentences are generated according to the setup in Theorem Some examples are as follows:
Clean
Training: Gddrrerrraat or or
Prompt: cydicddocydsc??
Corrupted
Training: сиоиrrrииaeet or cud
Prompt: cydrczdccydzes?
2. For experiments in Table 2, the training data consists of 50,000 sentences. In the clean version, sentences are generated uniformly as described Section 2.2. the imbalanced and extreme versions, the 60 other words are divided into three categories: 20 for ed
28

---

sentences (red.), 20 for ce sentences ), and 20 for both types (r.). In the imbalanced version, ed (ce) sentences are 4 times more likely to sample a ed (ce) word than a ce (cd)
word. In the extreme version, ed (ce) sentences cannot contain any ce (ed) words. Test sentences are generated according to the setup Theorem Some examples are follows:
Clean examples
Training: o1da1122"3"'3" or (1c11112"
Prompt: c2d22222cyd or c1e1222003e
Imbalance examples
Training: radr or or Prompt: c1d1cdd2cdd3c4 or 1 011102220333C?
Extreme examples
-Taiinnn:: raderaddrd or erermrrrrgeeeeeeees
Prompt: ei c2d2c3d3d3 or 01110202033344
3. Experiments in Table 3 follow the setup of experiments in Table 2, except that the pairs are now of the form (c,, de) and (et, fi) instead of (c, d,) and e4).
4. For experiments in Section 2.4, the corpus generation process is as follows:
Randomly select 10 countries and obtain their capital cities and IOC codes.
Generate 30 sentences containing exactly one country-capital pair (3 for each country).
Example: Paramaribo is the vibrant heart of Suriname.
Generate 30 sentences containing exactly one country-IOC pair (3 for each country).
Example: Gabon (GAB) protects its diverse rainforests and wildlife.
Generate 30 sentences containing exactly one country without any pair.
Example: The banking sector is central to Liechtenstein' 's prosperity.
Generate 60 sentences without any country, capital city, or IOC code. Example: Every country has its unique cultural identity and heritage.
Generate 810 sentences containing exactly different country-capital pairs by con- catenating sentences generated in Step 2.
Example: The city of Dushanbe reflects Tajikistan's vibrant spirit. Roseau is the cultural tapestry of Dominica.
Generate 810 sentences containing exactly two different country-IOC pairs by concate- nating sentences generated in Step 3.
Example: Mayolle (MAY) feutures lush landscupes and peaks. Turkmenistan (TKM) features the fiery Durvaza Crater.
The ICL prompts follow the form used in the country-capital city and US state-capital city experiments in the beginning of Section 2, with to in-context examples.
5. For experiments in Table 4, the training and test data consist of all sentences in the form abca, where a, b, and the first scenario (both), the first tokens of the training sentences cover the entire vocabulary. In the second scenario (either), each token can be the first token in either the training or test. data, but not both.
distinct. Each test sentence is different from any training sentence. In
6. For experiments in Table 5, the training data consists of 50,000 sentences generated uni- formly as detailed in Section 3.1. The ICL prompt formats are also described in Section 3.1.
7. For experiments in Table the training data consists of 50,000 sentences. In the clean scenario, the training data are of the form abcade f and abcbde with ICL prompts as abcadef? and abobde,??. In the block-noisy scenario, the training data include sequences like nı mananaaeedde f and abobn, nongygdee with ICI. prompts as abcade fighi? and fbchde
8. For experiments Table 7, the training data consists of 50,000 sentences generated uni- formly according to the processes in Sections 4.1 and 4.2. The ICL prompt formats are also described in the same subsections.
9. For experiments in Section 4.3, the corpus generation process is follows:
Randomly select 10 countries and obtain their capital cities and IOC codes.
29

---

Generate 130 sentences containing exactly one country-capital pair (13 for each coun-
try).
Example: Paramaribo stands capital of Suriname.
Generate 30 sentences containing exactly one country without any pair.
Example: The banking sector is central to Liechtenstein' 's prosperity.
Generate 60 sentences without any country. capital city, or IOC code.
Example: Every country has its unique cultural identity and heritage.
Generate 1,000 sentences containing exactly two different country-capital pairs by concatenating sentences generated in Step 2. Example: Brazil functions as heart of Brasilia. Turkmenistan operates as center for Ashgabat.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: Abstract and introduction (Section clearly summarize the paper's motivation (relevance), scope, and contributions. A summary of contributions at the bottom of Section is provided re-iterate the contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes].
Justification:
Limitations this work are included in Appendix J.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes].
Justification: Assumptions of each theorem and lemma are clearly mentioned in the theo- rem/lemma statement. Correct and complete proofs of all theoretical results are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes].
Justification: Codes for each experiment are provided as a .zip file in the submission. Experimental details are also provided throughout the paper and Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
32

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes].
Justification: Open access to codes is provided (one folder for each result). File names are self- explanatola...
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. pppullicgguiee
www.aammmssiooooooooy..oooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes].
Justification: Enough details are provided throughout the paper and Appendix K. See code for more details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No].
Justification: We only repeat each experiment 10 times due to computational constraints. However, most experimental results are backed up by theoretical analyses.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No].
Justification: We do not include details on the type amd amount of compute required to run each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: httpp::///nurips... httpp/icc/tiicccdideelele...e
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes].
Justification: We have reviewed the NeurlPS Code of Ethics and concluded that this research conforms with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
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.
34

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

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.
37


Reviews:
[{"review_id": "knEYn209q2", "reviewer": "Reviewer_nuMZ", "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.", "questions": "Can you add examples of training sentences and prompts for experiments?", "limitations": "Limitations are discussed in the paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- It enhances understanding of how the structure of training data influences the emergence of ICL capabilities\n- the paper provides a mix of theoretical proofs and empirical validations to support its claims", "weaknesses": "- 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.\n- The scope of the experiments is limited, using small datasets and simplistic model architectures. Moreover, there is an absence of real-world data.\n- There is uncertainty about whether the findings would scale well to complex real-world data, larger models and higher embedding dimensions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We are pleased that you found our work valuable in enhancing the understanding of ICL on unstructured training data, and our theoretical and empirical results well-supported. Below, we address your comments.\n\n> lack of experiment details in the paper, ... number of training sentences used, the frequency of each input-output pair's repetitions ... methodology for generating training and evaluation data.\n\n> Can you add examples of training sentences and prompts for experiments?\n\nWe appreciate your comment. We have included more details about the experiments in the paper to strengthen our arguments. For convenience, we summarized them below:\n\n- For Table 1 exps, training data consists of 50K sentences. In the clean version, sentences are generated uniformly as described in lines 122-124. In the corrupted version, sentences are similarly generated, but each $(c_i, d_i)$ pair is replaced by $(c_i, r_j)$ or $(d_i, r_j)$ with a probability of $1/4$ each (lines 124-126). Test sentences are generated according to the setup in Theorem 1.\n\n    - Clean ex:\n        - Training: $c_1 d_1 r_1 r_2 r_3 r_4 r_5 r_6$ or $r_1 r_2 r_3 r_4 r_5 r_6 r_7 r_8$\n        - Prompt: $c_1 d_1 c_2 d_2 c_3 d_3 c_4 \\dots$\n\n    - Corrupted ex:\n        - Training: $c_1 r_1 r_2 r_3 r_4 r_5 r_6 r_7$ or $c_1 d_1 c_2 r_1 r_2 r_3 r_4 r_5$\n        - Prompt: $c_1 d_1 c_2 d_2 c_3 d_3 c_4 \\dots$\n\n- For Table 2 exps, training data consists of 50K sentences. In the clean version, sentences are generated uniformly as described in lines 166-169. In the imbalanced and extreme versions, the 60 other words are divided into three categories: 20 for $cd$ sentences ($rcd_{\\cdot}$), 20 for $ce$ sentences ($rce_{\\cdot}$), and 20 for both types ($r_{\\cdot}$). In the imbalanced version, $cd$ ($ce$) sentences are 4 times more likely to sample a $cd$ ($ce$) word than a $ce$ ($cd$) word. In the extreme version, $cd$ ($ce$) sentences cannot contain any $ce$ ($cd$) words. Test sentences are generated according to the setup in Theorem 2.\n\n    - Clean ex:\n        - Training: $c_1 d_1 r_1 r_2 r_3 r_4 r_5 r_6$ or $c_1 e_1 r_1 r_2 r_3 r_4 r_5 r_6$\n        - Prompt: $c_1 d_1 c_2 d_2 c_3 d_3 c_4 \\dots$ or $c_1 e_1 c_2 e_2 c_3 e_3 c_4 \\dots$\n\n    - Imbalanced ex:\n        - Training: $c_1 d_1 rcd_1 rcd_2 rcd_3 rce_4 r_5 r_6$ or $c_1 e_1 rcd_1 r_2 rce_3 rce_4 rce_5 r_6$\n        - Prompt: $c_1 d_1 c_2 d_2 c_3 d_3 c_4 \\dots$ or $c_1 e_1 c_2 e_2 c_3 e_3 c_4 \\dots$\n\n    - Extreme ex:\n        - Training: $c_1 d_1 rcd_1 rcd_2 rcd_3 r_4 r_5 r_6$ or $c_1 e_1 r_1 r_2 r_3 rce_4 rce_5 r_6$\n        - Prompt: $c_1 d_1 c_2 d_2 c_3 d_3 c_4 \\dots$ or $c_1 e_1 c_2 e_2 c_3 e_3 c_4 \\dots$\n\n- Table 3 exps follow the setup of experiments in Table 2, except that the pairs are now of the form $(c_i, d_i)$ and $(e_i, f_i)$ instead of $(c_i, d_i)$ and $(c_i, e_i)$.\n\n- For Section 2.5 exps, below is an ex. for each sentence type in Appendix D:\n\n    - Paramaribo is the vibrant heart of Suriname.\n\n    - Gabon (GAB) protects its diverse rainforests and wildlife.\n\n    - The banking sector is central to Liechtenstein's prosperity.\n\n    - Every country has its unique cultural identity and heritage.\n\n    - The city of Dushanbe reflects Tajikistan's vibrant spirit. Roseau is the cultural tapestry of Dominica.\n\n    - Mayotte (MAY) features lush landscapes and peaks. Turkmenistan (TKM) features the fiery Darvaza Crater.\n\n    The ICL prompts follow the form used in Section 2.4, with 1-5 examples.\n\n- For Table 4 exps, training and test data consist of all sentences in the form $abca$, where $a$, $b$, and $c$ are distinct. Each test sentence is different from any training sentence. In the first scenario (both), the first tokens of the training sentences cover the entire vocabulary. In the second scenario (either), each token can be the first token in either the training or test data, but not both (lines 255-256).\n\n- For Table 5 exps, training data consists of 50K sentences generated uniformly as detailed in Section 3.1 (lines 289-296). The ICL prompt formats are also described in Section 3.1.\n\n- For Table 6 exps, training data consists of 50K sentences. In the clean scenario, training data are of the form $abcadefd$ and $abcbdefe$, with ICL prompts as $\\underline{abcadef} \\dots$ and $\\underline{abcbdef} \\dots$. In the block-noisy scenario, training data include sequences like $n_1 n_2 n_3 n_4 abcadefd$ and $abcb n_1 n_2 n_3 n_4 defe$, with ICL prompts as $\\underline{abcadefdghi} \\dots$ and $\\underline{abcbdefeghi} \\dots$.\n\n- For Table 7 exps, training data consists of 50K sentences generated uniformly according to the processes in Sections 4.1 and 4.2. The ICL prompt formats are also described in the same subsections.\n\n> The scope of the experiments is limited, using small datasets and simplistic model architectures. … absence of real-world data.\n\n> uncertainty about whether the findings would scale well to complex real-world data, larger models and higher embedding dimensions.\n\nThanks for your comment. We recognize these issues as shortcomings of our paper, as already noted in the Limitations section. However, we believe that our thorough analyses with small data sets and simple model architectures provide valuable insights into some components of unstructured data that are crucial for ICL. Also, even though we did not train LLMs on real-world data sets in our paper, we empirically validated our co-occurrence arguments by probing LLaMA 2, which was trained on real-world data sets (see Section 2.4).\n\nRegarding larger models with higher embedding dimensions, our findings remain consistent with the theoretical conclusions. For example, even in larger models (embedding dimension up to 200 and number of layers up to 20), the test accuracies in Table 4 remain zero when each token in $V$ appears as the first token in exactly one of the training and test sets. Similarly, under the same models, the test accuracies in Table 7 also remain zero, in line with Theorems 5 and 6.", "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": "TfFuZbwyy8", "reviewer": "Reviewer_cRrU", "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.", "questions": "The experimental results use cross entropy loss rather than the squared loss used in the theory. Why?", "limitations": "See above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies an important problem. The approach---reconstructing LM behavior in much \"shallower\" models---is intriguing and can be applied to additional problems concerning LMs. The technical claims are well presented and the paper is overall very readable.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We are pleased that you considered the problem we addressed important and found the paper well-presented and very readable. Below, we address your comments.\n\n> 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.\n\nWe appreciate your comment. We have expanded the Limitations section to clearly emphasize the distinctions between our setting and the general ICL setting. That being said, it is worth noting that the results related to co-occurrence are applicable to valid grammatical sentences, as the co-occurring pairs can appear anywhere within the sentence (e.g., \"Beijing is the capital of China,\" \"the city of Beijing is located in China\").\n\n> The experimental results use cross entropy loss rather than the squared loss used in the theory. Why?\n\nWe thank you for this comment. While the cross-entropy loss is frequently used in practice, it does not yield a unique optimal set of parameters (due to the translation invariance of the softmax function), and obtaining closed-form expressions for the minimizers can be difficult. Therefore, we used the squared loss to make theoretical analyses more manageable. This simplification has been adopted in other theoretical works, such as in Li et al. (2023).\n\n**References**\n\nLi, Y., Li, Y., & Risteski, A. (2023). How do transformers learn topic structure: Towards a mechanistic understanding. International Conference on Machine Learning.", "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": "HMWXtwxmMi", "reviewer": "Reviewer_xEmA", "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.", "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": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper begins by identifying synthetic scenarios in which co-occurrence within a sentence is sufficient for a continous bag-of-worlds (CBOW) model to be able to perform ICL. The paper proves two theorems identifying when co-occurrence statistics are sufficient to ensure that CBOW could perform ICL. \n- The paper then proves that positional information is required to perform certain sythetic tasks related to the ordering of tokens.\n- Finally, the paper identifies two sythetic settings in which one might expect ICL to work.\n- Sythetic experiments support each of the above claims.", "weaknesses": "- 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.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper. Below, we address your comments.\n\n> 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. … 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.\n\nWe appreciate your comment. We have updated the paper to clarify that this statement applies to ICL tasks with known input-output pairings, like country-capital and word translations.\n\n> 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.\n \nWe thank you for your comment. Although LLaMA 2 and other LLMs are mostly trained on English corpus, we believe this does not invalidate our experiment, as the words involved in the experiments are common in both languages. If the models learn the English-to-Indonesian mapping, they should translate correctly regardless of context. \n\nHowever, it is worth noting that the experiments in Section 2.4 do not involve any rare languages, and the same conclusion applies.\n\n> 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.\n\nThanks for pointing this out. As per your suggestion, we have revised the wording in Section 4.1 to clarify that the failure of ICL in this scenario is not surprising and is instead related to the importance of tasks present in the training data, similar to findings of Raventós et al. (2023) and Yadlowsky et al. (2023).\n\nThe original phrasing that the setting in Section 4.1 should succeed via ICL was intended to differentiate ICL in LLMs from simple pattern recognition. In Section 4.1, the pre-training data and test prompts consist of sentences with different repeating patterns. A model (or human) that learns to recognize these patterns is expected to successfully perform ICL on the test prompts, even when the pattern is different. Similarly, in Section 4.2, a model (or human) that identifies consistent $(a_i, b_i)$ pairs at the start and end of each pre-training sentence should successfully perform ICL on the test prompts that contain in-context examples of the form $(a_i, b_i)$.\n\n> It would be better to include more (related work) 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.\n\nWe thank you for the comment. We have expanded the Introduction section to better relate our work to existing literature and clarify its position in the ICL research landscape. Specifically, we highlighted the following comparisons:\n\n- Numerous studies connected ICL with classical methods like gradient descent (e.g., Akyürek et al. (2022)), Bayesian inference (e.g., Xie et al. (2022)), and Newton’s method (e.g., Fu et al. (2023)). In contrast, our work links ICL to the continuous bag of words (CBOW) model, demonstrating that ICL involving known input-output pairings can be enabled through learning CBOW co-occurrence patterns.\n\n- While several studies examined the pre-training aspects of ICL, such as data distribution (e.g., Chan et al. (2022)) and task diversity (e.g., Raventós et al. (2023)), our work emphasizes the importance of co-occurrence, positional information, and training data structure for ICL.\n\n- Other research explored ICL in specific data-generating processes like discrete functions (Bhattamishra et al. (2023)) and autoregressive processes (Sander et al. (2024)). Our work focuses on data characterized by input-output pairs and repeating token patterns.\n\n> 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?\n\nThanks to your comment, we repeated the experiment with larger models by varying embedding dimensions (10, 50, 100, or 200) and transformer layers (1, 5, 10, or 20). We found that test accuracy remained zero when each token in $V$ appeared as the first token in exactly one of the training and test sets, regardless of model size. In practice, this condition is likely met due to the vast size of LLMs' pre-training data.\n\n**References**\n\nAkyürek, E. et al. (2022). ​​What learning algorithm is in-context learning? Investigations with linear models. ICLR\n\nBhattamishra, S. et al. (2023). Understanding in-context learning in transformers and LLMs by learning to learn discrete functions. ICLR\n\nChan, S. et al. (2022). Data distributional properties drive emergent in-context learning in transformers. NeurIPS\n\nFu, D. et al. (2023). Transformers learn higher-order optimization methods for in-context learning: A study with linear models. NeurIPS M3L\n\nRaventós, A. et al. (2024). Pretraining task diversity and the emergence of non-Bayesian in-context learning for regression. NeurIPS\n\nSander, M. E. et al. (2024). How do transformers perform in-context autoregressive learning? ICML\n\nXie, S. M. et al. (2022). An explanation of in-context learning as implicit Bayesian inference. ICLR\n\nYadlowsky, S. et al. (2023). Pretraining data mixtures enable narrow model selection capabilities in transformer models. arXiv", "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": "PiFfBlbDIw", "reviewer": "Reviewer_xShA", "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.", "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": "The limitation discussion in the appendix K is fair.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "I think this paper is easy to follow and most explanations are clear (One minor suggestion: it would be more clear to also illustrate the correct answer of each prompt and provide some brief explanations such as the prompt in section 3 tries to repeat the first letter of a word). I choose fair in the presentation rating because I feel that the paper oversells its contributions in the title and abstract.\n\nAll the claims are supported by both strong theoretical conclusions and empirical simulations. The theoretical contributions are novel to me but I am not a theoretical researcher. Since the situations/preconditions of the claims are extremely simple, I think its significancy is not high for practitioners, but the contributions might be significant for theoretical researchers and might inspire the follow-up work.", "weaknesses": "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. \n\nI 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. \n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper. We are delighted that you found it both easy to follow and supported by strong theoretical conclusions and empirical simulations. Below, we address your comments.\n\n> It would be more clear to also illustrate the correct answer of each prompt and provide some brief explanations such as the prompt in section 3 tries to repeat the first letter of a word.\n\nWe appreciate your suggestion. We have modified Figure 1 to include a brief description of each ICL task and the correct answer for each prompt. Please refer to the PDF file in \"Author Rebuttal\".\n\n> 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.\n\n> After all, most ICL is beyond just relying on the co-occurrence statistics of the sentences like CBOW, finding the first letter of the word, and repeating some words in the context.\n\n> I suggest that the authors can revise the main storyline to reduce the overselling.\n\nThanks for your comments. We have revised the title of the paper to “In-Context Learning from Training on Unstructured Data: The Role of Co-Occurrence, Positional Information, and Training Data Structure.” \n\nAdditionally, we have updated the abstract to better reflect that this paper identifies three components necessary for ICL to occur from training on unstructured data and provides both theoretical and empirical justifications for each component. For instance, we included the sentence “To this end, we thoroughly examined three ICL tasks and identified three components that are crucial for ICL to occur from training on unstructured data: co-occurrence, positional information, and training data structure.” We hope these changes will alleviate your concern regarding the discrepancy between the paper’s title and abstract and its actual scope.\n\nRegarding the content, we would like to emphasize that we did not claim that  this paper provides a complete explanation for why ICL works well with unstructured training data. While we fully agree that ICL encompasses more scenarios than those covered in the paper—as noted in the Limitations section of the original submission—our goal is to offer insights into some components of unstructured data that are crucial for ICL to occur.\n\nFurthermore, although the ICL tasks discussed in this paper are simple, they are firmly grounded in prior research. For example, ICL tasks involving known pairings—such as word translations and country-capital city pairs—have been analyzed in studies by Brown et al. (2020), Todd et al. (2024), and others. Similarly, ICL tasks like word-first letter pairings have been explored in works by Xu et al. (2024), Chen et al. (2024), and others. We believe that thoroughly examining ICL in these simplified settings offers an interesting perspective on ICL, particularly regarding the importance of co-occurrence, positional information, and the structure of the training data.\n\n**References**\n\nBrown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., ... & Amodei, D. (2020). Language models are few-shot learners. Neural Information Processing Systems.\n\nChen, Y., Zhao, C., Yu, Z., McKeown, K., & He, H. (2024). Parallel structures in pre-training data yield in-context learning. arXiv preprint arXiv:2402.12530.\n\nTodd, E., Li, M., Sharma, A., Mueller, A., Wallace, B. C., & Bau, D. (2024). Function vectors in large language models. International Conference on Learning Representations.\n\nXu, Z., Shi, Z., & Liang, Y. (2024). Do large language models have compositional ability? An investigation into limitations and scalability. ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models.", "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:
We would like to thank all reviewers for providing constructive and insightful reviews. Please find our response to each reviewer in the "Rebuttal" section. Also, the updated Figure 1 (as requested by Reviewer xShA) is attached here.

Meta-review: 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.
Decision: Accept (poster)