Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions
Authors: Satwik Bhattamishra
Arkil Patel
Phil Blunsom
Varun Kanade
Venue: ICLR 2024 oral (2024)
Keywords: In-context learning
Transformers
Large language models
Boolean functions
Primary area: general machine learning (i.e., none of the above)

Abstract: In order to understand the in-context learning phenomenon, recent works have adopted a stylized experimental framework and demonstrated that Transformers can match the performance of gradient-based learning algorithms for various classes of real-valued functions. However, the limitations of Transformers in implementing learning algorithms, and their ability to learn other forms of algorithms are not well understood. Additionally, the degree to which these capabilities are confined to attention-based models is unclear. Furthermore, it remains to be seen whether the insights derived from these stylized settings can be extrapolated to pretrained Large Language Models (LLMs). In this work, we take a step towards answering these questions by demonstrating the following: (a) On a test-bed with a variety of Boolean function classes, we find that Transformers can nearly match the optimal learning algorithm for 'simpler' tasks, while their performance deteriorates on more 'complex' tasks. Additionally, we find that certain attention-free models perform (almost) identically to Transformers on a range of tasks. (b) When provided a *teaching sequence*, i.e. a set of examples that uniquely identifies a function in a class, we show that Transformers learn more sample-efficiently. Interestingly, our results show that Transformers can learn to implement *two distinct* algorithms to solve a *single* task, and can adaptively select the more sample-efficient algorithm depending on the sequence of in-context examples. (c) Lastly, we show that extant LLMs, e.g. LLaMA-2, GPT-4, can compete with nearest-neighbor baselines on prediction tasks that are guaranteed to not be in their training set.

Published as a conference paper at ICLR 2024
UNDERSTANDING IN-CONTEXT LEARNING IN TRANSFORMERS AND LLMS BY LEARNING TO LEARN DISCRETE FUNCTIONS
Satwik Bhattamishra University of Oxford
Arkil Patel
Phil Blunsom ~ Varun Kanade
Mila and McGill University @ Cohere
ABSTRACT
In order to understand the in-context learning phenomenon, recent works have adopted a stylized experimental framework and demonstrated that Transformers can match the performance of gradient- based learning algorithms for various classes of real-valued functions. However, the limitations of Transformers in implementing learning algorithms, and their ability to learn other forms of algorithms are not well understood. Additionally, the degree to which these capabilities are confined to attention-bra based models unclear. Furthermore, remains to be seen whether the insights derived from these stylized settings can be extrapolated to pretrained Large Language Models (LLMs). In this work, we take a step towards answering these questions by demonstrating the following: (a) On test-bed with a variety of Boolean function classes, we find that Transformers can nearly match the optimal learning algorithm for 'simpler' tasks, while their performance deteriorates on more "complex' tasks. Additionally, we find that certain attention-fie models perform (almost) identically to Transformers teaching sequence, i.e. a set of examples that uniquely identifies a function in a class, we show that Transformers learn more sample-efficiently Interestingly, our results show that Transformers can learn to implement two distinct algorithms to solve single task, and can adaptively select the more sample-efficient algorithm depending on the sequence of in-context examples. (c) Lastly, we show that extant LLMs, e.g. LLaMA-2, GPT-4, can compete with nearest-neighhor baselines on prediction tasks that are guaranteed to not be in their training set.
range of tasks. (b) When provided a
INTRODUCTION
Transformer-basee large language models (LLMs) have shown remarkable ability to learn tasks in-context using a handful of demonstrations and without updating their weights (Brown et al. 2020).
Demystifying this 'in-context learning' ability theoretically and empirically is an intriguing direction. Since real-world language data and tasks are hard to define precisely, in-context learning has been studied in various simplified yet well-defined settings (Chan et al. 2022 Hahn & Goyal 2023).
Recently, Garg et al. 2022) proposed a framework to understand the in-context learning phenomenon, wherein the model receives prompt Ps (X1, y1..... - xx)) containing sequence of pairs of inputs and labels followed by a query input. Each input x; E Rd is sampled from a distribution Dx and is labeled by function f Rdd - IR sampled from distribution of functions Dr. The goal of the model is to accurately predict / (xx). Unlike works that study in-context learning on LLMss, in this framework, the model M is trained from scratch on various such prompts sampled according to distributions Dx and Dr. Thus, this framework could be understood as meta-lcarning approach, i.c., the models are trained to learn learning algorithms. Garg et al. (2022) show that such trained Transformers perform well on a range of prediction and regression tasks on inputs in IRd
Given the flexible and interpretable nature of the framework, several recent works (Li et al. 2023
Ahuja & Lapez-Paz 2023: Bai et al. 2023) have adopted it to further understand in-context learning.
Research Questions. Multiple works (Bai al., 2023 Ahuja et al.) 2023 von Oswald al. 2022)
have demonstrated that Transformers can learn various classes of real-valued functions in such in-
Corresponding Authors: bmishk, wwwun.knadde@es.com

---

Published as a conference paper at ICLR 2024
In Content Learning
9,
France
Parts
Tokyp
Canud
Completa1
|
Auto-repressive Model
In Contest Learning of Boolean Functions
G0 D1DG1DC11G11100
000101:01:01001
Pronpt
110111001000101
100101011010100
Conoletan
Figure 1:
In-context learning of Boolean functions in our setup. In an autoregressive manner, given k- points of the form yx) where x; 10,1)a and y; E {0, 1), a model has to learn to accurately predict the label yı for the htth point.
context settings. This naturally motivates further questions: (a) What are the limits of the in-context learning ability of Transformers? (b) Is the attention mechanism essential for in-context learning? (c) Can Transformers exploit high-quality and informative examples to learn more efficiently? (d) To what extent do LLMs that are not specifically trained for these tasks carry the capacity to implement non-trivial learning algorithms on in-context examples?
In this work, conduct an extensive empirical study with various classes of Boolean functions to make progress towards answering these questions. Since Boolean functions are widely studied in learning theory (O Donnell 202I), the sample complexity and learnability of various function classes are well understood which helps us in designing the experimental framework. Additionally, unlike real-valued functions, the discrete nature of the inputs allows to adopt the setting for LLMs and test their ability to implement learning algorithms. We give an overview of our contributions below.
In-context learning Boolean functions. Transformers trained from scratch perform well range of Boolean function classes, however, their performance does degrade on seemingly more 'complex' classes. In particular, when learning parities their performance is bad as random guessing, but known algorithms can perform near-perfectly with the same size dataset. We also evaluate the performance of recently proposed alternatives Transformers which were motivated by the desire to have sub-que qub-quadra inference. Our results indicate that while these models match the Transformer's performance on most tasks, there remain some gaps in others.
Teaching Sequences. For a class of functions, teaching sequence is sequence of examples that can uniquely identify the function. Our results show that Transformers have the capacity to learn more sample-efficient algorithms when trained on such highly informative sequences. For certain tasks, our results show that single Transformer can learn two different algorithms and dynamically choose between them depending the in-context sequence-it uses the sample-efficient version if the input has a teaching sequence, and falls back on the less sample-efficient algorithm otherwise.
Investigation with LLMs. The goal of recent work in stylized settings was primarily to understand whether LLMs can use in-context examples to learn novel tasks. However, it is still unclear if LLMs implement learning algorithms rather than simply indexing from list of tasks pretraining. To understand whether L.MS can learn in a manner similar to models in the stylized setting, investigate the performance of pretrained LLMs the same tasks, by adapting them in two different ways. First, we use a frozen GPT-2 model, only training the input embedding layer, so to be able to evaluate GPT-2 the same stylized framework. Second, working with discrete inputs enables us to use the bit tokens directly to test the performance of LLMs by providing them in-context examples. Our results show that these models achieve non-trivial performance, competing with nearest neighbor classification. As we are sampling learning problems from large combinatorial space, it is virtually guaranteed that these models are learning from in-context examples alone.
during
SETUP FOR IN-CONTEXT LEARNING
In-context learning. Our setup closely follows that of Garg et al. (022) and is similar to other recent works which study the ability of Transformers to learn implement learning algorithms in
2

---

Published as a conference paper at ICLR 2024
their forward pass (Ahuja et al. 2023 Li et al. 2023 von Oswald al. 2022). In this setup, sequence model M (such as Transformers) is trained using N sequences, each sequence consisting of m labeled examples, (x1, (x1,//... .i.............................. Xms Mmm). The model is trained for the next token-prediction task,
except that we only care about every alternate token: iı,... 9m are the m output labels predicted
by the model, where yix M(P)) is predicted using the prefix Pk- (X1, D1, -... X;-1; Uk-1, Xt:). the loss on this sequence is given by I Σx= EÜik; yk).
To generate the set of N training sequences, we do the following: We sample m points Xi,... X.n ii.d from some distribution Dx over X, we sample a function f E F from some distribution Dz over F, and obtain the sequence (x1.f(z) f(1)), ................................ Xm: fzmm). This is repeated N times, with fresh sample of m points and a freshly sampled f. For an appropriate loss function L, the empirical loss over N training examples defined as,
( (.(aa)))
We will primarily work with classes of Boolean functions f {0, 13" -00, vector of bits of fixed length and output either 0 or 1. We say that a model M can learn a class of functions F in-context if with high probability, for f ~~ Dy and for sufficiently large ky, for all
{0, 1}. which take as input
k 2 k PrpL-(Ds, D)) (P&s) f(xx)) S.
We would like to highlight the difference from the traditional statistical learning framework, where a single target function f E learned from a random sample of labeled examples. our setup, each sequence is learning problem and the model is learning a learning algorithm.
Models. We primarily focus on Transformers Vaswani et al. (017) but we consider five different types of architectures for the majority of the experiments. These include a recurrent model (LSTM) (Hochreiter & Schmidhuber 1997), a state-space model (DSS) (Gupta et al., 2022), a long convolu- tional model (Hyena) (Poli al. 2023), and a hybrid model (RetNet) (Sun et al. (023). We consider decoder-only GPT-like architectures containing causal masking (see Figure rright) Note that, each input X₁ is vector of dimension n. A linear map, {0, 1)" applied to each input and label vector to map it to a vector of the same dimension as the model width. The models receive as input (x1. V1. ................................ Xm 1, Vm-1. 1, Xm) sequentially and for each prefix Ps for 1 S k S m, they predict the label Yı which is provided as the next token as in language model.
Rd, with learnable parameters, is
Training.
The models are trained from scratch to minimize the objective defined in Eq. [ where cross-entropy is used as the loss function. The details of the hyperparameters and other as- pects of implementation are provided in Appendix We have made our source code available at https///gthbbboommssw//////nnonn
3 IN-CONTEXT LEARNING BOOLEAN FUNCTIONS
In this section, we investigate the abilities of autoregressive architectures to learn various classes of Boolean functions in-context. Our experiments are geared towards answering the following questions: (1) What classes of Boolean functions can Transformers learn in-context and what are their limitations? (2) Is attention necessary for in-context learning and what are the differences between the capabilities of Transformers and attention-free architectures?
Tasks. We explore several classes of Boolean functions with varying characteristics. We define some representative classes here; the rest are defined in Appendix C.I
(i) Conjunctions and Disjunctions. For the input domain X,, = {0, 13"h any input x E X, denotes possible assignment to n. Boolean variables 21,.... .u. A literal is either the variable x; or its negation F,. A conjunction simply an and (A) of some subset of the 2n literals. For example, for 10, one possible conjunction could be 22 A Zg A Æ7 which outputs I only when I2, x7 are 1 and Wig is O. The class of Conjunctions contains all such conjunctions over {0, 1)".. The class of Disjunctions is defined similarly with the or (V) operation (z V Zg V 27).
'The choice of ky may depend on the function class, as for more complex classes, more examples may need be before learning is possible.
3

---

Published as a conference paper at ICLR 2024
(ii) DNFs and CNFs. A Boolean function is in the class DNF if it is disjunction of one more conjunctions. Formally, for any x E {0, 10, a function f belongs to the class of DNFs, if it can be expressed in the form f(x) (21,1 A 21,2 A ... A 2 ,1, V... V 1 A 2m. A... A km, where zij are literals which are either the variables or their negation. Similarly, CNFs contain functions that are a conjunction of one more disjunctions. While only the simplest of classification rules may be defined using conjunctions/dijjunttiii representations. Since DNFs/CNFs are conjectured to be computationally hard to learn, we consider 3-term DNFs and 3-clause CNFs which are known to be efficiently learnable.
a richer family becomes available when using DNF/CNF
(iii) Parities is one of the most fundamental classes of Boolean functions: widely studied in learning theory and cryptography because of its intriguing properties(Blum et al.] 2003) Regev] (0100). A Parity function computes the XOR (() of some subset of the n variables. Each Parity function outputs 1 when an odd number of the variables are assigned the value 1 and outputs O otherwise. The
class PARITY-n contains all 2n possible Parity functions over {0, 1)". We denote the class of sparse parities with PARITY-(n, k) which contain functions with l relevant variables defined over {0, 1)".
Sampling data and functions. For each task such as Conjunctions or Parity, we sample a function and m. Boolean inputs to generate each training (or test) example. For the majority of the tasks, the inputs are sampled uniformly at random where each input bit is either or 1 with probability 1/2. However, for tasks such as Conjunctions and 3-term DNF the null accuracy under the uniform distribution will be close to 1, and hence we modify the input distribution to make the set more well-balanced. The details of the input distribution and the distribution over functions for each task are provided in Appendix
3.1 RESULTS
T the performance of various architectures on the Boolean function tasks considered in the paper. The numbers indicate the accuracy of prediction for the last example in a prompt sequence, averaged over 1280 sequences. The curves showing the accuracy as a function of the number of observed examples for all tasks are provided in Appendix C..4
Transformers show varied performance on Boolean functions. We find that on certain simple classes of functions such as Conjunctions and Disjunctions, Transformers achieve perfect accuracy within a relatively small number of examples. We observe that the performance of Transformers is close to that of feedforward networks (FFN) trained with gradient-descent as well as known PAC- learning al algorithms for the respective tasks (see Figure 13), in terms of sample complexity required to achieve perfect accuracy. On such tasks, we also find that they perform well on out-of-distributtio inputs and functions; they also exhibit robustness to the presence of noisy labels during the training process. (see Appendix [ for more details.)
While Transformers perform well on certain classes of Boolean functions, we find that their per- formance degrades across others. The tasks can be broadly divided into three categories. The first category contains tasks where Transformers can achieve near-perfece (> 95%) accuracy. The second category contains examples where the model performs better than baselines but its accuracy saturates below 95%. The last category consists of Parities and Sparse Parities where Transformers and other models do not improve beyond chance-level accuracy even with a large number of training examples. While prior works (Garg al., 2022, Ahuja al. 2023 Bai et al. (023) have observed that Transformers perform well on a wide range of tasks, our results highlight that there are certain classes of functions where they are imperfect (second category) and there are certain classes such as Parities where they seem incapable of finding any learning algorithm to solve the task. Note that, for PARITY-(10, 2). 140 examples are sufficient for feedforward networks trained with gradient-descen to achieve near-perfect test accuracy (see Figure 18). The tasks PARITY-20 and PARITY-(20, 3) could be PAC-learned within 140 examples if the models could learn to apply the Gaussian elimination algorithm (Fischer & Simon 1992). Hence, the failure of Transformers learn Parities does not arise due to the lack of a sufficient number of in-context examples. We discuss and further explore the difficulty of learning Parities in Appendix F
the tasks in lcarning to
Transformers vs. other Architectures. For the majority of the tasks considered in this work, we observe that attention free architectures perform almost as well Transformers. The efficacy of recurrent and long-cod convolutvlttion models on multiple tasks such as Conjunctions and Disjunctions indicates that the in-context learning phenomenon in the sense of implementing learning algorithms
4

---

Published as a conference paper at ICLR 2024
Table 1: The performance of different architectures on in-context learning Boolean functions. The numbers depict the accuracy of model while predicting the last input in the prompt. For instance, for prompts with m points, the number indicates the accuracy on the m-th input point based on the first 1 points and labels. The descriptions of the baselines are provided in Appendix C.3 For all values reported in the table, the standard deviation is within 0.5.
TASK
N.DIMS
POINTS
NULL
AVERAGING
NN
PEN
DSS
LSTM
RETNET
HYENA
TRANSFORMER
Conjunctions
28
70
69.9
68.2
81.3
94.0
97.2
100.0
99.4
100.0
100.0
Disjunctions
69.8
67.5
80.3
93.4
97.5
100.0
99.7
100.0
100.0
Sparse Disjunctions
50
70
63.9
70.4
71.7
91.2
99.5
100.0
98.2
100.0
99.9
3c
28
100
59.3
66.6
79.6
91.5
93.3
94.3
91.5
95.5
95.1
3--DNF
28
100
55.6
70.3
80.4
90.9
94.7
95.5
92.9
96.0
95.2
Majority
55.5
80.9
67.8
90.7
91.2
89.6
91.5
91.5
0-1 Threshold
28
50.5
70.7
77.1
89.6
72.4
83.9
72,9
85.0
85.3
Halsgee-
20
70
51.4
81.7
70.0
90.6
84.0
84.6
83.1
86.9
86.4
Purity-(10, 2)
10
140
50.6
48.5
81.7
100.0
49.7
51.1
48.7
52.0
53.7
........ -... -ee
w...............................
................................
Parity-(20,3)
20
140
50.0
50.7
55.3
50.2
51.2
50.0
51.1
47.6
49.1
Pa
49.2
50.6
49.2
49.6
50.3
51.1
50.6
Nearest Noighbor
10
100 49.6
66.6
100.0
N/A
81.5
79.1
90.6
85.5
100.0
is not particular to Transformers. At the same time, we find that certain differences between Transformers and their recently proposed alternatives evidently exist. On tasks such 0-1 Threshold functions, we find that RetNet and DSS perform worse than Transformers (see Table D. With further experiments on linear regression tasks proposed in previous works, we find that recurrent models such as DSS and LSTMs struggle to match the performance of Transformers (see Figure 8 in Appendix). The closest to Transformers in terms of performance is Hyena, which matches Transformer's ' performance on all tasks apart from the nearest-neighhor (NN) task. The NN task tests the ability of models to implement the nearest-neighhor algorithm as described in Appendix [ Our results indicate that while recently proposed architectures with sub-quadratic inference time can perform in-context learning, there still exists a minor performance gap between these architectures and Transformers.
4 IN-CONTEXT LEARNING WITH TEACHING SEQUENCES
Premise. Our experiments in the previous section as well as previous works investigate the abilities of models to perform statistical learning from arbitrary distributions in an in-context setting. Given that we are exploring the ability of sequence models to learn 'learning algorithms', one could wonder: Can sequence models find learning algorithms which are more cample-efficiee when they are provided with more informative sequence of examples? We explore this question in this section.
Teaching Sequences (Goldman Kearns 1995). For class of functions F, the teaching sequence of function / in F is sequence of labeled instances (X1, (X1+Y,... Yi...., Xm, such that it unambiguously identifies of in F only the function ff is consistent with the sequence of labeled instances. We are interested to see if architectures such Transformers can learn to identify the correct target function right after seeing the shortest teaching sequence of that function.
Experimental Setup. Every aspect of the experimental setup except the data distribution remains identical to the previous experiments. For each sequence during training and evaluation, the first t points are teaching sequence of the target function and the next m points sampled from the distribution Dx The sampling of functions, the training and the evaluation process remain the same. Although we primarily focus on Transformers, most results in this section hold for all architectures.
Tasks. We experiment with 5 tasks: Conjunctions, Disjunctions, CNFs and DNFs, and sparse parities. Every conjunction (or disjunction) has a teaching sequence of length k + 2 where k is the number of
From here onwards, by teaching sequence we will refer the shortest teaching sequence of function.
5

---

Published as a conference paper at ICLR 2024
Teach Conjunction dime 75
Teach DNF n_dimm 50
Teach Parity nn dims 20
0.3
6.3
1eamh AccUReO
66
Muan
Trandamw
MR 2-2 samppigg
In-cormedt eccrrptes
In-commed mamplee
Figure 2: Performance of Transformers on various tasks with Teaching Sequences. The plots depict the performance of models right after the teaching sequence. Refer to Section for more details.
literals in the function. Every 3-term DNF or CNF has a teaching sequence of length / + 3 where / is the total number of literals in all terms. The teaching sequence of each sparse parity function is of length k where k is the number of relevant bits upon which the Parity function is computed. For each task (such as Conjunctions), we refer to the version with teaching sequence as Teach <taak-name>> (e.g. Teach Conjunction). The details of the teaching sequences are provided in Appendix G
Transformers succeed in learning from Teaching Sequences. For all tasks, we find that Trans- formers achieve perfect accuracy on subsequent points after receiving the teaching sequence. Figure shows the accuracy curve of Transformers and baselines on three representative tasks after receiving the first & points containing the teaching sequence. Note that, the accuracy of Transformers stays (close to) 100% after receiving the teaching sequence. It is interesting to see that Transformers succeed in learning with teaching sequences for tasks like DNFs and sparse parities where they struggled to learn in the vamilla setting.
By definition, the teaching sequence is the smallest sequence required to learn the target function. Hence, it can often be much smaller than the sample complexity for a learning algorithm to learn from arbitrary distributions such as the ones considered in the previous section. Thus, our experiments show that models predict perfectly with much fewer examples when provided with these teaching sequences. This is not true for FFNs trained with gradient descent which fail to predict accurately given only the teaching sequence during training (see Figure rightt in Appendix). FFNs+GD is a more general-purpose purpose algorithm and is hence not the most optimal for specific problems.
Two distinct algorithms to learn one task. An interesting finding is that Transformers seem to learn two different algorithms to learn Conjunctions depending on the data distribution Dx during the training process. See that (Figure when Transformers are trained to perform in-context learning with Conjunctions in the vanilla setting (as in Section 3 without teaching sequences, and tested on examples (or Prompts) containing teaching sequences, they are not able to leverage the teaching sequence and require more examples to predict accurately. The algorithm learned with standard Conjunctions still works on examples with teaching sequences even if it is not as sample-efficient. On the other hand, when Transformers are trained with teaching sequences and are tested in the standard setting without teaching sequences, they do not perform well since the learning algorithm relies on using the first f examples containing the teaching sequence (Figure 3 center-left) These results indicate that models can learn two distinct algorithms depending on the distribution of inputs provided during training.
We conducted another experiment where we trained a Transformer on mixture of examples with and without teaching sequence. During training, we sample an example (or Prompt sequence) with a teaching sequence with probability 1. and without a teaching sequence with equal probability. We evaluate the model on both tasks separately, one which contains examples with teaching sequences and one without them. We find that the same Transformer model could achieve near-optimal performance for both tasks when provided with teaching sequences, it behaves like the model that is trained on just the Teach Conjunction task (Figure 3 Right) and when provided with examples without teaching sequences, it behaves like a model trained on just the Conjunction task (Figure 3Figure3]cente--tte centerriight This indicates that Transformers can learn two distinct learning algorithms for Conjunctions and implement the optimal one depending on the sequence of in in-context examples. This highlights the versatility of neural sequence models in being able to find separate learning algorithms with respect to the data distribution for solving the same task.

---

Published as a conference paper at ICLR 2024
Tranned en Corqusctios dime 10
Trained on Searh Carqunctio d,
Traksea Masiure d,
Triined on Mictur dins 24
Pocar marpls
connee compley
Figure 3: Left: depicts the performance of Transformers trained on examples with the vanilla distribution and tested in-context examples with Teaching Sequences. Center-left: Transformers trained with teaching sequences and tested on in-context examples without teaching sequences. Center-right and right: depict the performance of Trannsformess trained on mixture of Conjunction and Teach Conjunction and tested on the individual tasks. See Section for more details.
5 INVESTIGATIONS WITH PRETRAINED MODELS
Premise. While several works have investigated how well Transformers can be trained to learn various kinds of functions in-context, it unclear how these findings relate to LLMss, which was the primary motivation behind this line of work. This raises very natural and intriguing question: Can pretrained language models predict accurately by implementing any kind of learning algorithm when provided with prompts of the form (x1, Y1,, .......... xx))
While prior works focused on learning veluuv function classes, evaluating LLMs on those tasks is not straightforward since LLMs receive and produce discrete values. Our setup involves discrete Boolean functions, which enables us to analyze the performance of LLMs in applying learning algorithms for solving these tasks. Additionally, we are picking the target function randomly from an exponentially large set, we can be essentially sure that the learning is happening from in-context examples only, allowing us to remove confounding factors such as memorization during pre-training
Setup. Recall that, in our experiments in the previous sections, when a model is provided with a sequence of input-output pairs (x1, Yi..... Xm: Ym), each input x; is single token. Additionally, LLMs do not have embeddings for each of the Boolean inputs {0. 1)" as opposed to the linear map W {0, 13" + Rwidh learned by the models in the ICL setup of previous experiments. To address that, we experiment with pretrained models in two different settings, one which is closer to the ICL setup in previous experiments and another which very close to the practical usage of the L.Mss.
(a) Frozen GPT. In the first setting, we take GPT-2 model and add learnable input and output layers at the beginning and end of the Transformer architecture. The weights of the GPT-2 model are frozen while the embedding matrix is replaced by learnable function / : {0, 1 - Rwidth which is FFN with one hidden layer. Similarly, the output layer is replaced by an FFN experiments, we train the input and output layers to minimize the objective in Eq. [ while keeping the weights of the pre-trained GPT-2 frozen. We compare it with the performance of a randomly initialized Transformer model (same architecture as GPT-2) undergoing the same training process with learnable input-output mappings and frozen Transformer weights. The goal of this setup is to understand whether large-scale text pre-training imparts some ability to the Transformer model that enables it to implement learning algorithms in-context.
Rwidn - +00, 13. During
(b) Direct Evaluation. We directly evaluate several LLMs on the task of learning Boolean functions. In this setup, each input example x, E {0, 13" is provided as sequence of tokens 21...., Ix where r, E {0, 1}. None of the model's parameters are modified and the original embedding matrices are used to represent the tokens 0 and 1. We evaluate the models by providing them with a simple prompt containing two parts: the first part is simple instruction asking the model to act as learning algorithm and predict the label corresponding to the final input, and the second part consists of series of input sequences and their corresponding labels followed by the test input sequence (see Figure 21). We evaluate the predictions of the model at prompts of different lengths (i.e., different numbers of in-context examples). To estimate the accuracy for a particular number of in-context examples, we repeat the experiment 100 times (i.e., with 100 different functions of the same class). We experiment with state-of the LLMs GPT-4 (OpenAl 2023), RPT-3.5-Turbe (Brown et al. 2020 Ouyang et al. 2022) as well as the open-source model LLaMA-2-70B Touvron al. 2023)
7

---

Published as a conference paper at ICLR 2024
Conjunctions- GPT2 dims
No Reaarest Neighbours- GPT2 dims
axgmax
Artention
Near
No
hardan Thandamar
0712
Rondor Tranforeer
Prailitton
Figure 4: Experiments with frozen GPT: left: Performance of frozen GPT-2 on the Conjunction task, center: Frozen GPT-2 model learns to perfectly implement the nearest neighbors algorithm, right: Illustration of attention patterns in GPT-2 while solving the Nearest Neighbor task.
5.1 RESULTS: LLMS PERFORM AT LEAST AS WELL AS NEAREST NEIGHBORS
Results with Frozen GPT. We evaluate the performance of a frozen GPT-2 model on tasks such Conjunctions and Disjunctions. Figure 4 depicts the performance on Conjunctions (the behavior on Disjunctions is almost identical). We find that the GPT-2 model performs relatively better than the nearest neighbor baseline and much better than randomly initialized model on these tasks. However, it still does not come close to achieving the near-perfect accuracy obtained by fully trainable Transformer networks as in Section 3
GPT-2 can implement Nearest Neighbor. Given the observation that the performance of GPT-2 was close to the nearest neighbor algorithm. we examined if a frozen GPT-2 model can implement the nearest neighbor (NN) algorithm. We designed the NN task to test this hypothesis. In this task, each prompt contains 100 points where the first 20 points are labeled or uniformly random and the subsequent 80 points are labeled according to the nearest neighbor algorithm. We then evaluate the GPT-2 model the frozen-GPT setup described earlier and find that it can achieve near-perfect Moreover, accuracy on the 80 points labeled with the nearest-neighhor algorithm (see Tigure upon analyzing the attention heads we found heads which closely implemented nearest neighbors for input x,, the attention head attended over y, where X, is the nearest neighbor of x; among Xi...., x; (illustrated in Figure right). Further details about these experiments are provided in Appendix H These heads reminiscent of induction heads (Olsson al. 2022) where instead of matching prefixes, they can find the nearest neighbor over the input space. Since the weights of the Transformers are frozen and only the input embedding and output layers are updated during the training process, the mechanisms to solve tasks such as NN and Conjunctions must have been learned during pretraining on language data, Moreover, Transformer of the same size with randomly initialized weights is unable to perform much better than chance-level accuracy.
Results with Direct Evaluation. The performances of all LLMs for the Conjunction and Majority tasks with varying number of dimensions are provided in Figure 5 It is clear that all models are able to perform as well as or better than the nearest neighbor baseline when the number of dimensions is up to 7. Note that in this setup, the LLM is essentially unaware of the task (such as Conjunction) when is provided directly with the prompt at inference time. Even with n = 7, there are 2128 Boolean functions, and so the in-context learning problem remains challenging, and the observed performance of these models is impressive. LLaMA-2 model performs quite similar to GPT-3.5-Turbo. It is also particularly interesting to see the strong performance of GPT-4; apart from outperforming all other models, it also slightly outperforms the nearest neighbor baseline even in the 15-dimensional case.
is perhaps surprising to see that the open-source
RELATED WORK
In-Context learning in Stylized settings. Understanding the in-context learning (ICL) phenomenon has attracted significant interest in recent years. Since the ICL phenomenon was demonstrated in Brown et al.] (202)) numerous works have investigated the practical capabilities and limitations of LLMs perform ICL (see Dong et al. (2022) for survey). Since it is infeasible to precisely define real-world data and tasks, several works have studied it in stylized well-defined settings (Chan et al.,
2022 Hahn & Goyal 2023 Xie et al. 2021) Garg et al. (2022) presented meta-learning-like
8

---

Published as a conference paper at ICLR 2024
Conjunction n. dims=s
Conjunction n_dims=7
Conjunction n. 1ims==15
Majority dims=5
Majority dims-7
Majority dims=15
Vean
In-cinteat LaM--2-100 2m1-3 STute
Inctentst ccmpples
CPT4
Figure 5: Results with the direct evaluation of LLMs at inference time. The top row shows the performance across varying dimensions for the Conjunction task while the bottom row shows the performance for the Majority task.
framework and demonstrated that Transformers can match gradient-based learning algorithms for regression tasks. Subsequent works (Dai et al. 2022; Akyürek et al.] 2023] von Oswald et al. 2022) demonstrated that Transformers were expressive enough to represent gradient-descent and empirically verified that the learned weights indeed computed gradient- -ased algorithms. Li et al. (2023); : Bai al. (202)) studied the sample complexity of in-context learning regression and other real-valued functions with Transformers. More recently. (Ahuja et al. (2023) : Bai et al. (2023) explored (among other things) the efficacy of Transformers in learning mixtures of tasks in-context and showed that they could adaptively select appropriate algorithms for a given sequence of inputs and labels. Our work takes step forward in this direction by demonstrating that (a) some of these observed phenomena are not confined to attention bbaed architectures and (b) that neural networks can learn to implement multiple distinct learning algorithms for ICL of a single task depending on the in-context examples. Moreover, our results help bridge the gap between the stylized setup used in prior works and in-context learning of actual pretrained models.
Transformers and Sequence Models. The analysis of the capabilities and limitations of recurrent architectures dates back to a few decades ago (Kolen Kremer) 2001). Given the recent success of Transformers, several works have sought to investigate their theoretical expressiveness (Pérez et al.)
2019 Merrill et al. 2022 Chiang & Cholak 2022; Hahn 2020: Yun et al. 2020 Liu et al. (002)) as well as their empirical capabilities (Bhattamishra al. (023)] Ebrahimi et al. 2020) and limitations (Bhattamishra et al. 2020 Chiang & Cholak 2022). Delétang et al. (2022) conduct a comprehensive
study of the performance of various sequence models such as Transformers and RNNs on formal language tasks. While most of these prior works focus on classification or related tasks, our work complements these as we conduct comprehensive study on in-context learning tasks.
7 CONCLUSION
In this work, we highlighted certain limitations of Transformers in in-context learning and their ability to leverage more informative examples such as teaching sequences for learning more sample- efficient manner. Additionally, we showed that pretrained models also learn mechanisms to solve tasks in the stylized ICI. setting. Further, we show that L.LMs are also capable of performing as well as certain baseline learning algorithms in more practical setting. Our results raise several interesting questions for future work: (a) Can LLMs leverage more informative examples to sample-efficiently learn practical tasks in-context? (b) What aspects of the pretraining process of LLMs lead to their ability to implement learning algorithms since they are not primarily trained in the meta-learming-lin like framework? (c) What are the theoretical limitations behind the difficulty of learning Parities in the in-context learning setting? (d) What are the mechanisms that various architectures (attention, recurrence, and convolution) use learn tasks using different operations?

---

Published as a conference paper at ICLR 2024
REFERENCES
Kabir Ahuja, Madhur Panwar, and Navin Goyal. In-context learning through the bayesian prism. arXiv preprint arXiv:2306.0489) 2023.
Kartik Ahuja and David Lopez-Paz. A closer look at in-context learning under distribution shifts. arXiv preprint arXiv:2305.1670, 2023.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In The Eleventh International Conference on Learning Representations, 2023. URL http:///ppeeeeeeeee http://.eee//rrreoeeeeeeee dd=
0gUX4H8yN4I
Dana Angluin, David Chiang, and Andy Yang. Masked hard-attention transformers and boolean rasp recognize exactly the star-free languages. arXiv preprint wxxiv:2310.13897. 2023.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mci. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306. 04637, 2023.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Trans- formers to Recognize Formal Languages. In Proceedings of the 2020 Conference on Empir- ical Methods in Natural Language Processing (EMNLP), pp. 7096-71 16, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/w1/2020.oom wttp:/0000.mmmmmmmm....766. URL
https://aclantthology org/ 2320 mammpp-main..
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse Boolean functions. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 5767 5791, Toronto, Canada, July 2023. Association for Computational Linguisties. doi: 10. 10.11853/11/2033.cc aclllo/. 317. URL https::/p//t....... accl anthol wwwpchhho.o.orr.2222.3333 http://2...cccc. 1ong. 317
Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-33 51906555912220 2003.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Sys- tems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL 0111996676688888880 8bfb8ac P4a.aaaaa .df
ceurrps..c/paper..e
Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang, Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learning in transformers. Advances in Neural Information Processing Systems, 35: 18788888-1889, 2022.
David Chiang and Peter Cholak. Overcoming theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 7654-7664, Dublin, Ireland, May 2022. Association for Computational Linguistics. long
doi: 10. 00.18663/1//022222e-loo.....
URL
527
Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei. Why can gpt learn in- context? language models secretly perform gradient descent meta optimizers. arXiv preprini 22. 2022.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya. Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg. and Pedro A Ortega. Neural networks and the chomsky hierarchy. arXiv preprint 2200:222000009 2022.
10

---

Published as a conference paper at ICLR 2024
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui. A survey for in-context learning. arXiv preprint arXiv:2301.0023. 2022.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? arXiv preprint arXiv:2010.04333. 2020.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac HatfieldDDodds Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. https:/transsfrmmer cttp://raaaatorreeerrrirruussis wttpe/uissspuu/2222///aaeeeooooe
Paul Fischer and Hans- UIrih Simon. On learning tungssu--expasions. SIAM Journal on Computing, 21(1):181-192, 1992.
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30598, 2022.
Sally A Goldman and Michael Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50(1):20-3 31, 1995.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces, Advances in Neural Information Processing Systems, 35:22982-22994, 2022.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020. doi: 10.1 10000 URL
https: / ant logy org /320 wtt.:2tt...cc2..........ee... 1111
Michael Hahn and Navin Goyal. A theory of emergent in-context learning as implicit structure induction. arXiv preprint 27X10
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1066, 1998.
John F Kolen and Stefan C Kremer. A field guide to dynamical recurrent networks. John Wiley & Sons, 2001.
Yingcong Li, M Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and implicit model selection in in-context learning. arXiv preprint arXiv:2301.07067, 2023.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint 12X0::2210.10749, 2022.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for gpt-3? arXiv preprint arX1v:2101.06804, 2021.
Lovre. Who models the models that model models?
exploration of gpt-3's in-context
model fitting ability. https:://///. www.w/wwaaaaoom/.ooo aiw.aanet forum. www.mttrooooooooooooooooo http:////pp...//////aa....eeeeee
choo-modelsee thddeee-eeeeeeeelll model that model model s- an wxp.-eeeootraaooooooo.....o 2022.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting the Association for Computational Linguistics (Volume 1: Long Papers), pp. 8086-8098, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: URL htw.tttspp//aaaaataeeaeeeeeoooee wwtp:/olw.oyrrg/22..oooo wtwp://2...cc-----oo2... acl- 556
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-854 856, 2022. doi: 10. 1662tacl a 00493. URL /ttp://e..//aaaattooooo.o.///g/p

---

Published as a conference paper at ICLR 2024
Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannanch Hajishirzi. Metaicl: Learning to learn in context. arXiv preprint arXiv:2110.15904 2021.
Sewon Min, Mike Lewis. Hannaneh Hajishirzi, and Luke Zettlemoyer. Noisy channel language model prompting for few-shot text classification. In Proceedings of the 60th Annual Meeting of the Association for Compulational Linguistics (Volume I: Long Papers), pp. 53 5316-5330, Dublin, Ireland, May 2022a. Association for Computational Linguistics. doi: 10.18663/11/0022.addd 365. htt.:pp:e//cc.aattoooooo..o 2222 acl Long- 365
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202. 12837, 2022b.
Ryan O D'onnelll Analysis of boolean functions, 2021.
10386
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209. 1895, 2022.
OpenAL. Gpt-4 technical report, 2023.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Training language models to follow instructions with human feedback, 2022.
Ryan Lowe.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-peeformance deep learning library. Advances in neural information processing systems, 32, 2019.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019. URL
https::/cgeereeviee. wwt.:/oorrmmid-nygooooobo
Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. arXiv preprint arXiv:2302.10866 2023.
Yasaman Razeghi, Robert L Logan IV, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot reasoning. arXiv preprint arXiv:220..07206 2022.
Oded Regev. The learning with errors problem. Invited survey in CCC, 7(30):11, 2010.
Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models, arXiv preprint arXiv:2307.08621. 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami. Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and iune chat models, 2023.
Stojnic,
12

---

Published as a conference paper at ICLR 2024
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Autention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. arXiv preprint Xtx::2222.007777 2022.
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang. Denny Zhou, and Tengyu Ma. Larger language models do in-context learning differently, 2023.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Amthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, et al. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations, pp. 38 45, 2020.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning implicit bayesian inference. arXiv preprint arXiv:2111.02080, 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sqquence functions? In International Con- ference on Learning Representations, 2020. URL /ttt:s:///peneeveeew ew..iewwneee www.:nmmffoomm11 d-
Byx
13

---

Published as a conference paper at ICLR 2024
A ROADMAP
The appendix is organized as follows.
In Section we discuss clarifications related to some natural questions related to our results.
provide detailed descriptions of the tasks, the distribution of functions and inputs used in our experiments, and details of the baselines. Additionally, the detailed plots regarding some results reported in Section B are provided in this section.
In Section
In Section D discuss results with some additional experiments exploring the robustness tasks and to noisy labels as well as the sample complexity of models while learning tasks such as Conjunctions. We also discuss some factors that could determine the difficulty of tasks for sequence models.
of the models to
we compare the performance of Transformers with known algorithms for Conjunction and study their representational complexity.
In Section B
In Section
we discuss the difficulty of learning the Parity task in more detail.
In Section G we provide the details of the teaching sequences used for the experiments in
Section 4
In Section
we provide some additional details related to the experiments with LLMs in
Section 5
and also discuss some additional results.
In Section discuss the details of the implementation and hyperparameters used during the experiments.
Section we discuss some additional related work.
B CLARIFICATIONS
(1) Given that LLMs are trained on trillions of tokens, how can we be certain that LLMs such as GPT-4 are applying learning algorithms and not imitating any tasks seen during training? ? In prior works where in-context learning evaluated with natural language tasks such as sentiment classification, NLI, or some variations of them, LLMs are likely to have seen such tasks during training and can use in-context demonstrations for recognizing the target function learned during pretraining before making predictions (Min et al. 2022b). However, in our case where the model is provided with sequence of Boolean inputs and labels (in Section (5), the total number of possible target functions that can label the inputs over 10 even for dimension 7 it is virtually impossible for model to have seen sequences of examples labeled with such a large amount of functions. Hence, in order to predict accurately, the model has to rely the examples provided in-context a learning algorithm.
(2) When you say LLMs apply learning algorithms, is the claim that they implement gradient- bassed or nearest neighbor algorithm? No. We do not know how LLMs are learning based the in-context examples provided. Our results suggest that they are competitive with the nearest neighbor (NN) algorithm but do not have any evidence to claim that they are applying NN, gradient-descent, or any specific algorithm for that matter for learning tasks like Conjunctions.
(3) Are Transformers superior to other architectures in in-context learning in the sense of implement- ing learning algorithms? Not necessarily. Our results across various classes of Boolean functions and linear regression suggest that attention-free architectures match Transformers on most tasks and are slightly worse on a few tasks. The difference in the nearest neighbor task is particularly interest- ing because our results in Section D suggest that Transformers learn such mechanism during their pretraining process. At the same time, one could argue that the task is more suited to attention-based models. Given the similarity in performance between Transformers and Hyena on other tasks, would not be surprising if there are learning problems that are more suited to long convolutional models where Hyena could perform better.
(4) Why are the dimension of inputs (n_dims) and number of examples (n (n-points) different for different tasks in Section 3 Parameters such as the d_dims and n_points are chosen so as to ensure feasibility of the learning task to some degree based on known results about the learnability of the problem. For instance, for tasks such as Conjunctions and Disjunctions, since there exists known PAC learning algorithms |Valiant 1984) for solving the task with O(n) examples,
set the dims as 28
14

---

Published as a conference paper at ICLR 2024
and expect models achieve near- near-perfect accuracy within 70 examples. However, for tasks such as Parities, since gradient-based algorithms need n2(()) steps to learn them (Kearns) 1998), we consider the PARITY-(10, 2) task case Transformers can learn using a gradient- FFNs with gradient descent. On the other hand, since Parities can be learned within (n) examples with Gaussian elimination algorithm (Fischer & Simon 1992). we consider the PARITY-(20, 3) and PARITY-20 task where models will have to find a non con-graddent-baaan based algorithm to solve them.
algorithm similar to
Limitations. A caveat with empirical studies such as this is that the results depend on the hyper- parameters and other aspects of the experimental setup. While we have tried to be as thorough as possible with hyperparameter tuning, there is always a chance that the results or behaviour could differ for some hyperparameter.
C ADDITIONAL DETAILS OF EXPERIMENTS
C.I DESCRIPTIONS OF TASKS
Boolean functions have been widely studied in the field of theoretical computer science (O D'nnell 202I). Given that it is extensively studied in the field of learning theory, it is well-suited for our task, since the discrete nature of the domain allows us to also test actual LLMS apart from neural networks trained from scratch. Additionally, the learnability and the precise properties of each function class are well-understood which aids in experimental design choices (such as the number of in-context examples necessary for learning concept class) and in drawing inferences from the results.
For better readability, we redefine the function classes that are already described in the main paper.
Tasks 1-2 Conjunctions and Disjunctions. For the input domain X,, {0,, 1)", any input x E X, denotes possible assignment to Boolean variables 2...... In. its negation E A conjunction is simply an and (A) of some subset of the 2n literals, For examples, for n = 10, one possible conjunction could be 22 A Te A I7 which outputs only when 22, are 1 and 23 O. The class of Conjunctions contains all such conjunctions over {0, 1)".. The class of Disjunctions is defined similarly with the or (V) operation (z2 V Te V 27).
A literal is either the variable or
Task 3 Sparse Disjunctions is specific case of Disjunctions where the function over n variables depends on at most k variables where k < In other words, the function class contains all Disjunctions with at most l variables. In our experiments, we set variables, the total number of 3-sparse disjunctions is (2)33. Hence, in our experiments, set higher value for the n (n dims= 50) parameter so that the number of functions in the class is at least million.
3. For functions over n
Task 4-5 DNFs and CNFs. A Boolean function is in the class DNF if it is a disjunction of one or more conjunctions. Formally, for anyx (0, 10,1)", function f belongs to the class of DNFs, if it can be expressed in the form f(x) = (æ1,1 A 21,2 ....A
A 21,4,) V. V (Zm.1 A Zm.2 A... km..... A.... where zij are literals which are either the variables or their negation. Similarly, CNFs contain functions that are a conjunction of one or more disjunctions. While only the simplest of classification rules may be defined using conjunctiios//diijuneiinn representations. Since DNFs/CNFs are conjectured to be computationally hard to learn, we consider 3-term DNFs and 3-clause CNFs which are known to be efficiently learnable.
a richer family becomes available when using DNF/CNF
Task 6 Sparse Majority. A function in the class sparse majority is parameterized by subset of variables and outputs the majority value of those variables. For example, if the relevant variables are 22, T4, 2i and I7, then the output for any input x E (0, 1] }"" will be 1 if more than 2 variables have value 1 and will be 0 otherwise. Since each function is uniquely identified by a subset of variable S C [ni]. the total number of sparse majority functions is 2n.
Task 7 0-1 Threshold Functions are functions of the form sign (-,- W.J, - b) where Wi...., Wn, E {-1, 0, 0,1 and b E (-k,...,
1, k). Instead of the usual X, {0, 1)", the input space can be seen over {-1, +1}" which makes it easier to define the functions. In our experiments, we set k 3 and
28. Note that, Conjunctions and Disjunctions can be seen special cases of Integer threshold functions where is ||w||| - 1 or -(I[w=]) ] 1). See that the total set of functions in the class of Integer threshold functions is 2(33))
15

---

Published as a conference paper at ICLR 2024
Task 8 Integer Halfspace contains functions of the form sign 1 W,2;; 1 0.5) where w1..... Wn {-k,... k- 1--,,, -1, } and x E {-1,+1}". The total set of functions in the class is 12(3").
Tasks 9-11 Parity is one of the most fundamental classes of Boolean functions; widely studied in learning theory and cryptography. A Parity function computes the XOR (+) of some subset of the n variables. For example, Parity function could be 22 @ 3 O 255- Each Parity function outputs 1 when an odd number of the variables are assigned the value 1 and outputs 0 otherwise. The class PARITY-n contains all 2n possible Parity functions over {0. 1)". We denote the class of sparse parities with PARITY-(n, k) which contain Parity functions with exactly k relevant variables (or bits) defined over {0.1)*
Task 12 The Nearest Neighbour task is intended to evaluate the ability of architectures to learn to implement the nearest neighbour algorithm. Unlike, other tasks, doesn' involve a class of functions. For this task, each example consists of 100 points 2,,...,. 21 00 E {0, 1 where the first k points are labelled or uniformly at random. The labels for the next 100 le points are determined by their nearest neighbour in the preceding input points. More specifically, for any point z; where =F=,, Then the label yy corresponding to Iy
j E (k + 1,..,, 100), let p = arg mIx.e() [|==||||[=]]
is Up-
Size of Hypothesis set. Unlike regression problems considered in earlier works, the number of functions in these Boolean function classes is finite. However, see that, for inputs over {0, 10" the total number of possible Conjunctions (or Disjunctions) is 3". Hence, even for n = 30, the function class has over 100 trillion functions. Moreover, even for prompt with number of permutations is 50! for one set of inputs and a single target function. This implies that the likelihood of encountering the same training example twice is extremely low and that it is (almost) impossible for practical-sized model to memorize all examples during training unless n and m are quite small.
50 examples, the total
C.2 DETAILS OF INPUT AND FUNCTION DISTRIBUTION
For the majority of the tasks, the inputs are sampled uniformly at random over (0, 1]", For tasks such as Conjunctions, Disjunctions, and 3-CNF, a uniform distribution for the inputs over {0, 1]" will lead to most examples being either positive or negatively labelled. In that case, even the Null classifier which always produces the same output can achieve over 90% accuracy. While Transformers trained over uniformly distributed inputs for these tasks achieve near- peer--eefect accuracy, it is in some sense trivial since they do not necessarily need to learn any algorithms and can achieve near pear-perfect accuracy by learning a constant function. Hence, for such tasks, we modify the input distribution such that at least 30% of the input points in the prompt have a positive (or negative) label to make it more well-balanced. In the modified distributions, we first sample i points for the prompt uniformly at random and then pick 30% of the input points. For these points, we change a subset of bits to 0 or 1 so that they will labelled positively (for Conjunction) negatively (Disjunction) according to the target function. Note that, this doesn't 't change the proportion of Os and 1s in the modified inputs since the probability of literal being positive or negative (complement) in the Conjunction is the same.
Distribution over Functions. For tasks such as Sparse Disjunctions and Parities, the functions are sampled uniformly from the of all such functions. For both 0-1 Threshold functions and Integer halfspace, the w,S are sampled uniformly from their respective range and for 0-1 Threshold functions, the b parameter is sampled uniformly from { -K, .k....k k 1, k). For tasks such as Conjunctions and Disjunctions which are either AND (A) or OR (V) of some of the 2n literals, the function is sampled such that each literal 2; or its complement 3a has a probability of p in being in the sampled function. In other words, for each i E [n]. the literal z; has p/2 probability of being sampled, the literal T. has p/2 probability and with - P probability the literal or it's complement is not included. In our main experiments, we set p- 30% and also investigate the robustness of the trained model when evaluated on other distributions (other values of p) in Appendix D.I] Similarly, for the Sparse Majority class, the probability of each literal being in the sampled function is p (there is no complement). For sampling each 3-DNF (or 3-CNF), we first sample three conjunctions (or disjunctions) with = 20% and then take an AND (or OR) of those clauses.
16

---

Published as a conference paper at ICLR 2024
Conjuantions Wandomers- r.diins 28
Diqunctions - Tranoformers n, dimo 28
Sparse Disj. Transformers -n.dims
pM)
52
22
20
I-dattad: coupp
In4e7too czamplic
Iocettst searplia
2-ONF- Transfomers- B dims 20
3-CMF TTrnnformere-- n. dime 28
Majofity- Transformert- -R dinse 20
sverggng
exarging
60
66
90
54
40
Incertonl cosrple
osemples
0-1 Threthold- Trancfomees a. dims 28
Integer Halfspace Transfomeet- a. dims 20
Parity-110, 2)- Trancfrrmors dims
2
HH,
30
A0
30
23
1400
Figure 6: Performance of Transformers on in-context learning various classes of Boolean functions. The plots represent the mean accuracy of Transformers as a function of the number of in-context examples provided to the model. On certain classes of Boolean functions such Conjunctions and Disjunctions, Transformers perform in a near-optimal manner. On tasks such as 0-1 Threshold, Majority and Integer Halfspaces, they perform better than baselines but do not achieve near-perfect accuracy even after observing 70 examples. On the other hand, on Parities Transformers do not perform better than chance-level accuracy. Refer to Section for details.
Conjunction
Majority
(i-ciitend exrigges
In cuntrat exarrplec
Nourest Heighhour
Threshold- -n dims
Integer Hallspace- rraiims 29
1.0
Figure 7: Performance of different architectures on 6 representative tasks.
C.3 DETAILS OF BASELINES
Below, describe how each baseline model M predicts the label when provided with prompt Pa (I.,, X Yk-1, Xx).
Null classifier. This classifier always produces the same output, i.e. M(Ps) = 0, irrespective of Pt.
17

---

Published as a conference paper at ICLR 2024
Linear Regression
Squared arrrr
In-contexi examplee
Figure 8: Performance of various architectures on the Linear Regression task from Garg et al. 2022
Averaging estimator. This is an incremental learning classifier that captures the average relationship between input vectors and output labels for previously seen points. It predicts M w X₁- The weights w, are computed as the average of the product of input vectors and their corresponding outputs over all previous points, ie., w
x,y;-
Nearest neighbors (NN). This classifier aims to predict the output label based on the labels of the most similar input vectors in the previously seen points. It predicts M(P) - Eies Vr. Here, the set of indices of the nearest neighbors of x among X1 to X;-1- For k - 1 < n, average over all the y,s from to 1, and for = 1, we set (Px) 0.
Feedforward Networks (FFN). We train 1-hidden layer ReLU FFN the same number of exam-
ples as provided to sequence models Table 1 We tune the model across width E {100, 500, 1000). optimizer { "adam', "sgd') and learning rates (0.01, 0.005, 0.001, 0.0001). We report the accuracy of the best model based on 1280 examples after being trained on m examples where m given in Table I for each task.
C.4 ADDITIONAL PLOOSS FOR IN-CONTEXT LEARNING BOOLEAN FUNCTIONS
The accuracy curve of Transformers and baselines across all in-context examples is provided in Figure 6 The performances on Conjunctions and Disjunctions are almost identical in all the experiments we have conducted. Similarly, the performance on 3-CNF and 3-DNF well as among Parity tasks are almost identical. The accuracy curves of all 5 architectures on representative tasks are provided in Figure
D ADDITIONAL EXPERIMENTS ON BOOLEAN FUNCTIONS
D.1 ROBUSTNESS OF MODELS
In this section, we explore the robustness of Transformers to out-of-distribution (OOD) inputs and functions well as their robustness to noisy examples during training.
OOD functions. Transformers seemingly perform a near-optimal manner for tasks such as Conjunctions and Disjunctions. First, we evaluate the performance of Transformers trained on the Conjunctions task on functions from different distribution than the ones seen during training. As described in Appendix C. while training on the Conjunctions task, the functions are sampled in such a way that for any i [r)]. the probability of the literal z; or Σ being in the sampled Conjunctions is 30%. Hence, the expected number of literals in the Conjunctions seen during training is n1/3. We evaluated Transformers trained on such Conjunctions on examples where the functions are sampled in such way that the expected number of literals is 2n/3 and the probability of any literal being in the sampled functions is twice as compared to the ones seen during training. We find that Transformers perform effectively such examples well (see Figure 9 Right). However, we find that the
18

---

Published as a conference paper at ICLR 2024
OCD
1.
Haa
Transfomeer nalddaaaeer
04
HMLr=3
averapin
50
0.2
eaather
10
Corciot cnamppics
In-conto msamkk
Figure 9: Performance of Transformers on Conjunctions with out-of-distributiio inputs (left) and functions (right). Refer to Section D.I for more details.
Trained on 0-1 Threshold
Trained 0-1 Threshold
Tested on Conjunctions n_ dims 28
Tested on 0-1 Threshold -n_dims 28
0.4
0.4
022
ovtreping coaffir
20
26
68
78
28
33
40
50
Inscomeee Courmsls
11 tncontcntoremploo
Figure 10: Comparison between the performance of a Transformer trained to learn the 0-1 Threshold function on the Conjunction task (left) and the original 0-1 Threshold task, Refer to Section D. for more details.
performance degrades for extreme changes in distribution where the expected number of literals in the functions is above 80%.
Trained on Threshold and Tested on Conjunctions. We also evaluated the performance of Transformers trained on 0-1 Threshold functions on the Conjunctions task. As describe in Appendix C 0-1 Threshold Functions are functions of the form sign(E W.a, - b) where w Wn, {0, TJ simpler threshold functions where the function is of the form sign(>; Di= W - ([|w]], - 1)). At the same time, note that the 0-1 Threshold funetions task in our setting will not have functions which are exactly Conjunctions since h: = 3 in our experiments and [|] w I = n/3 where n is set to 28 for experiments with Threshold functions.
and 6 E {-k,...,k k 1, k}. In some sense, Conjunctions
We conduct experiment where train a Transformer on the 0-1 Threshold function task (with n = 28) and evaluate the model on the Conjunctions task. Perhaps surprisingly, we find that the model performs better on the Conjunctions task (achieving over 90% at the end) in comparison the in-distribution Threshold function task (See Figure 10). It is interesting to see that the algorithm learned during training generalises to higher values of b in sign(E W - b). These observations could perhaps be attributed to the fact that Conjunctions are one of the simplest Threshold functions and could be easier since the value of b dependent on w.
Robustness to noise. On tasks such as Conjunctions and Disjunctions where the models learn to perform in-context learning effectively, we explore whether they are robust to noisy labels during the training process. During training, for every example (X1, Y1,....... Xm, Nm). ), we flip 10% of the labels y,s. Hence, the examples seen during training are not perfectly labeled by a Conjunction (or Disjunction). During the evaluation, provide clean inputs (without noise) to test the performance of the models. We find that on these tasks, all architectures are robust to noise in the training process (see Figure IT..
Length Generalization. We explore the effectiveness of Transformers to generalize to a larger number of examples (in some sense length) in comparison to those during training. We consider Conjunctions and DNFs where they perform reasonably well in the in-distribution setting. For Conjunctions, train the model prompts with 60 examples and test their performance on prompts
19

---

Published as a conference paper at ICLR 2024
10
Hoi Accunood
04
Reclet
044
HMLr=3 averapin
50
Claaferr
0.2
caather
10
Inccariet cnampiics
In-conAoG mnamaka
Figure 11: Left: Performance of various architectures trained with noisy examples on the Conjunc- tions task. Right: Performance of Transformers trained with noisy examples on the Disjunctions task and performance of baselines. Refer to Section D.I for more details.
Conjunctions Length Gonaralization
DNF Length Ganeralization Trained 80 points
Trained points
0.6
Aos
hot
M. n-)
MV n-3 swenggr
svaragin nakdlasie
oearppics
Figure 12: Performance of Transformers on prompts with larger number of examples than seen during training. Left: Trained on Conjunctions with 60 examples and tested on 100. Right: Trained on DNFs with 80 examples and tested on 160. Transformers with no positional encodings and just masking generalize well whereas those with absolute encodings struggle higher lengths. Refer to Section D.I for more details.
with 100 examples. Similarly, for DNFs, we train the model on prompts with 80 examples and test their performance prompts with 160 (twice) examples. We compare two types of positional encodings: (a) absolute encodings and (b) no positional encodings with just causal masking. Figure 12 depicts the performance of Transformers on these tasks. Transformers with no positional encodings and just masking seem to generalize well whereas those with absolute positional encoding seem to struggle on higher lengths.
D.2 WHAT DETERMINES THE DIFFICULTY OF IN-CONTEXT LEARNING?
A natural question that arises from results is: what properties of task determine the difficulty of in-context learning for models such as Transformers and other architectures? First, it is interesting observe that capacity measures such VC dimension or the size of function class do not seem to correlate well with the performance of the models (See Table 2 While Transformers are able to perform well on Conjunctions which have VC dimension O and sparse Disjunctions which have VC dimension Olk n)), they fail on Parities and sparse Parities with similar VC dimensions. VC dimension one way to measure the complexity of class of functions which relates to the worst-case sample complexity required to learn functions from the class and it is related to several other measures which compute the capacity of the class in some manner.
Note that, measures such as VC dimension are not dependent either the distribution of inputs the functions. We explore some other measures in order to understand the properties that determine the difficulty of in-context learning. One measure which we found to correlate well with the performance of Transformers is the pairwise correlation between the functions in class. For Boolean functions of the form f {0, 13" + {+1, the pairwise correlation of class of functions P(F) is defined as,
P(F) B (x))))
2
20

---

Published as a conference paper at ICLR 2024
Classical Algo Conjunctions r_dims 28
classical Algo Disjunctions n nidims
0.8
3.8
Noin Accumscy
0.6
2.6
0.4
PACe Tanotimers AN n
M&C aggo Tarsformet
Nr. 1:33
oging
aecluptig
20
In-context examptes
In-contect examples
Comparison between the performance of classical PAC-learning algorithms for Conjune- tions and Disjunctions and the performance of Transformers. See Section EE for the description of the algorithm and other details.
Figure 13:
The measure P(F) computes the magnitude of the expected correlation between pairs of functions sampled over Dy. To estimate P(F) for the tasks considered in the paper, sample 1k functions according to the distribution used for training and sample 10k inputs from the uniform distribution over (0. 1). The estimated pairwise correlation of all function classes is provided in Table 2 See that the pairwise correlation between any two Parity functions is O. We observe that the value P ((F) is high for classes in which models perform well and decreases across categories with Parities having the minimum pairwise correlation.
While the pairwise correlation among functions has reasonably strong correlation with the degrada- tion of the performance of the models, it still has some weaknesses. As compared to properties of function classes such as VC dimension, it takes the distribution over functions into account. However, the input distribution is uniform over {0, 13" while computing P(F) whereas it is not uniform for some of the function classes during training. Having clearer understanding of the factors that determine the difficulty of in-context learning is an interesting open problem.
Table 2: Pairwise correlations of different functions classes computed according to Eq. 2 See Section D.2 for more details.
Conjenctions
Digunations
Sparee Dijunctions
JCCP
S-ONF
Majoriy
Inigge-Thrabeld
Imuger Halliqua
Parig-30
VC Dimmzniion
Dis]
Ols)
0(s)
0(n)
0(s)
O(e)
Ote
O(klogs)
Otw)
Parkise Conclaion
95.2 d: 0.07
36.3 0.08
77.1 d 0.01
$1.80 22 0.29
50.7 = 0.26
207 0.1
06 021
0.1 0.14
IJB a 0.03
0.00 = 0003
D.3 EXPLORING SAMPLE COMPLEXITY
In this section, we explore the performance of Transformers when the number of examples during training is fixed. Recall that each training (or test) example X (x1, (X1:Y1,.... Xm Ym) ) created by sampling m input points from the distribution Dx over inputs and sampling one target function from the distribution D over functions. For the experiments Section a fresh of input points and functions are drawn during each training iteration.
For example, while training Transformers for 20k steps for the task Conjunctions with batch size 64, the model essentially observes about 1.3M functions and input sequences. However, note that the likelihood observing the same function during evaluation extremely low since for 28 dimensions, the total number of Conjunctions is over 22 trillion.
An interesting question to understand how many examples Transformers need to generalize well in the in-context learning setting. Moreover, what is the effect of increasing the capacity of the model when the number of examples remains fixed? We explore these questions in this section.
We consider Conjunctions where Transformers are effective in the vanilla setting. During training, we first sample a fixed number of examples N of the form (X1.Y1.... Xm: ym) by sampling N functions from the distribution Dy and sampling N sequence of m input points from the distribution Dx. All training iterations over the N examples and during evaluation we sample fresh examples to estimate the accuracy of the model.
21

---

Published as a conference paper at ICLR 2024
Accumsy Samps Complecty Nun orDmmenstans
Accuracy ve Nam Layers dimenalore (Num Sample
-00
6.00
2.25
12
Numo
383
15
0.0
Nambor of Bamplis
Numbor of Laye's
Figure 14: Performance of Transformers on learning to learn Conjunctions with a finite number of examples. The figures show the change in performance across various axes such as depth, number of examples, and number of dimensions the input. Refer to Section D.3 for more details.
Accuracy Surpix Complenty Nun Dimoralors
Accuraacy Num Dimeralora (Nurn Surpits
-4
1.00
2.90
0.85
Num Diseintt
2.3
Uven Vile
0.00
0.7
0.75
2000 4009
2000 2000
1990
12000 14000 19000
12
Figure 15: Performance of LSTMs on learning to learn Conjunctions with a finite number of examples. The figures show the change in performance across various axes such as depth, number of examples, and number of dimensions in the input. Refer to Section D.3
D.3 for more details.
We evaluate the model with {128, 512, 1024, 2048, 4096, 8192, 16384] examples. We test the models across tasks with dimensions d E {14, 28, 42). We find that neural networks such as Transformers and LSTMs are quite sample-efficient in terms of solving Conjunctions task where they achieve close perfect accuracy even with 4096 examples. Figure (1eff)) and Figure 15 (left) depict the mean accuracy of Transformers and LSTMs across various number of examples task dimensions d. Note the mean accuracy during evaluation here is the mean of the accuracy of all m points in an example and not the accuracy on the last point. For instance, if we test on K = 1280 examples to estimate the accuracy and each example has m 70 points then the mean accuracy is computed R Σ
and
(P( f((x))). The mean accuracy across all in-context examples will always be lower than 100% since the model will make mistakes in the first half of the examples before converging to near-perfect accuracy for tasks like Conjunctions.
m
It is also interesting to see that increasing the capacity of the model has negligible effect on the performance of the model. Figure [4] (right) shows the mean accuracy of Transformers across different depths (number of layers) when trained on 4096 examples.
E TRANSFORMERS AS LEARNING ALGORITHMS
As described in Section in this line of work each sequence of examples or prompt fxx)), Xm (I can be seen as a learning problem. In the traditional statistical learning framework, while learning from examples labelled by a particular function f E F (Conjunction), the goal of a learning algorithm meta-learning stage, we are optimizing a Transformer (or other networks) to find learning algorithm rather than target function. Hence, that sense, the target function in this meta-learning-like setup the optimal learning algorithm for the class of functions. It is natural to wonder how Transformers fare against the optimal learning algorithms for the problems considered this work and moreover, if they theoretically capable of representing and learning such learning algorithms. While the optimal learning algorithms for classes considered here may not be known, there are some known algorithms for learning classes such as Conjunctions and Disjunctions which in some sense
find the target hypothesis function f F. In this case, during
22

---

Published as a conference paper at ICLR 2024
near-optimal. In this section, compare Transformers against those algorithms and also show that they are capable representing such algorithms.
Classes such Conjunctions and Disjunctions are known be efficiently PAC-Icarnable with ( examples. The classical algorithm (see Algorithm T for learning Conjunctions works as follows, starts with hypothesis h which has all 2n literals (h 21 A 31 22 A 82 .... A 2n A 2,). It goes through each example and only checks the positive examples. For each positive example, it finds the literal which are not satisfied and drops those literals from the hypothesis h. This because we know that if literal is not satisfied and the label of the input is then the target conjunction does not have that literal. For any of examples, this algorithm returns conjunction consistent with all examples and PAC-Iearns the class Conjunctions. A similar algorithm can be derived for Disjunctions as well. See Valiant (1984) for more details.
Algorithm CONJUNCTION Classical Algorithm
1: Input: n, S = ((X1, 11), ...., (xm, Vm))
2: Initialize: h 21 A 31 22 A B2 ... A Zn En
3: for i = , do
4: Pick (x,, 1/5) from $
5: if y/s 1 then
Ignore negative examples
6: for j = 1, 72 do
7:
if [.. 0 then
8:
Drop 2, from h
jth bit of 7th instance is 0
9:
else
10:
Drop 2, from h
5th bit of 7th instance is 1
11:
end if
end for
13: end if
end for
15:
Output: h
Figure 13 compares the performance of the classical algorithm for Conjunctions (Algorithm
and Disjunctions with the performance of Transformers. There are few things note here: (a) These classical algorithms are near-optimal and are guaranteed to work for any distributions over the input. They are optimal in the sense that the lower bound the sample complexity of learning Conjunctions/Disjunetti
is (n) and these PAC-learn these classes with O(n) samples. (b) Transformers can perform better on the first few examples because they have knowledge about the distributions of inputs and functions since they are exposed to it in the meta-learning stage. So in that sense, they are closer to the patrrs-ootmal--stmmmaat in their behaviour. However, unlike the provable PAC-learning algorithms, the algorithms learned by Transformers are not guaranteed to work for arbitrary distributions. (c) Both Transformers and the classical algo reach (near) perfect accuracy after observing almost the same number of ((n) examples.
(Ahuja et al., 2023) than the classical algo
E. REPRESENTATIONAL COMPLEXITY OF LEARNING CONJUNCTIONS
Interestingly, we can show that Algorithm can represented as a Boolean circuit AC The class AC contains Boolean circuits with constant depth and a polynomial number of AND (A), OR (V), and NOT (-) gates.
Lemma E.1. The classical PAC-learning algorithm for learning Conjunctions (Algorithm) can be represented as a Boolean circuit in AC
Proof. Essentially what the algorithm is doing is identifying which literal (z, or ž,) is definitely not in the target conjunction. The evidence for 2; not being in the target is positively labelled example x, where 2; 0, i.e. if the i-th bit is 0. any conjunction that has 24 a literal cannot be satisfied by that assignment. Similarly, 2, cannot be the target conjunction if there is a positively labelled example
x, with 24 1. So suppose ignore the negative examples, and let S (x (x,y) S.y 1).
23

---

Published as a conference paper at ICLR 2024
then the truth value of,
A
Tb
xESI
determines whether the literal 2, is in the hypothesis conjunction output by the algorithm. Likewise, the truth value of,
A
XES+
determines whether the literal Es is in the hypothesis conjunction à output by the algorithm. Thus, using one layer of AND gates, one can determine which literals the algorithm picks to be in the hypothesis conjunction h. Let Pi..... . ....... .N, denote the outputs of these AND gates, i.e. P. (N;) indicates whether the algorithm puts the literal 2; (2;) in its output hypothesis h. Then to make a prediction on new example æ, the prediction of the algorithm's 's output hypothesis on this new example is given by the truth value of,
1=1
1=1
Thus, the entire process of running the algorithm to obtain h, and using h to predict the label of new example x can be done using an AC circuit of depth at most 3.
Recent works (Angluin et al. 2023) have shown that hard-attention Transformers can represent functions in the class AC and since we find that the learning algorithm for Conjunctions is in AC (Lemma I. it follows that even hard-attention Transformers can represent the algorithm for learning Conjunctions.
E.2 HOW TRANSFORMERS LEARN CONJUNCTIONS?
We explore how Transformers could be (in-context) learning Conjunctions in this section. To simplify things, we will focus on Conotone-Coonunnttion which contain only positive literals and no negative literals. That is, function such f 21 23 is in the class of Monotone-Conjunetionn but A 23 not since & a negative literal.
Approach. The key observation behind approach to probing Transformers is the observation that Monotone Conjunctions can exactly learned by membership queries alone. In other words, there monotone--oojuunctionn f over (0, 1)" which is unknown but we query the label f(x for any input x, then we can exactly identify the Conjunction by querying n examples.
The examples ci...., C, will be such that the example e; has value at the ith coordinate and value 1 everywhere else. For instance, over 4 dimensions, the vector e [0111], [1011] and so on. See that for any unknown conjunction over {0, 1 1 if query the function for input e; and the label f(e,) = 0, then it implies that the literal 2; is in the conjunction f. Hence, by querying all such examples ei.... Cn, we can identify any unknown monotone conjunction.
Interpreting Transtormers. We train the Transformers for the class of monotone conjunctions by sampling prompts and optimizing the model similar to previous experiments (as described in Section [ We are interested in figuring out what kind of algorithm it applies to learn conjunctions in-context. During evaluation, the model
sequentially receives prompts of the form Ps. (x1, 9/ ...... -k-1; 1,,1, for < k S m. After receiving each prefix Pr. we evaluate the model M on the examples ..,..., e, to identify the function used by the Transformer model M. More specifically, let ((() = (x1, M1......... Xz, yk e;), then for each k E [0....,m], we evaluate the model on (()) (())
See that if the Transformer model M makes its prediction based some unknown Conjunction, then we can recover it during each step of in-context learning. However, is not necessary that conjunction and may be using some other form of function
the model M predicts according in which case this approach is not guaranteed to work. Note that, since Transformers reach perfect accuracy after observing certain number of examples (Figure top-llfft and also achieve that
24

---

Published as a conference paper at ICLR 2024
Conjunction Transforers- d_din
Mono Corjunction Transforers R__imms
Mono Conjunction Transformers n_
Mann
5
In-corfaod ocamples Aer
In-oontent examples
In-corisd enar plac
Mumber literds
Parment of Itersis
Paumarr of staraa atrate
= 12
In nn-conneut esarppees
Figure 16: Extracting the target (Mono) Conjunction from Transformer during in-context learning. The upper row depicts Transformer's performance across in-context examples and the lower row shows the number of literals in the conjunction extracted from the Transformer at that point. The values are averaged across Ik prompts. The three columns are for three different distributions over inputs (at test time). First column: x 30% of inputs in the prompt are positive, second: 70% of inputs are positive, third: x= 15% of inputs are positive.
uut-of-distributiin examples, it is reasonable expect it to predict according to some underlying conjunction as sees more examples. Nonetheless, we apply the approach described above to extract the target Conjunction at each step of the in-context learning process.
Learning Mono Conjunctions. For
Conjuuctii,,,,,,,ionnn, the PAC-learning algorithm is a simpler version of Alg. [1] It starts with conjunction with all literal h 21 A 22. 2n and while going through m examples, it only looks at the positive examples. For any positively labelled example xi, if any coordinate æi.j = 0, then drops the literal zj from the hypothesis h and outputs h after going through all m examples.
Results. We find that Transformers behave in manner very similar the algorithm described above but not in an cxact way. We evaluate the model on 1k prompts containing 70 examples each and extract the literals at each step beginning from no examples to all 70 examples. We observe that in the beginning, the target function has all literals similar to the classical algorithm. Moreover, as the model observes more examples, the number of literals decreases monotonically and finally converges to the correct target conjunction which was used to label the examples in the prompt. However, unlike the classical algorithm the Transformer model does not drop literals right after seeing a positive example, we find that it drops a larger number of literals together after observing series of positive examples.
Figure depicts the number of literals in the extracted conjunction across in-context examples for three different input distributions. The model was trained according to the first distribution where approximately 30% of the examples in the prompt are positively labelled and then tested three different distributions. Similar to the classical algorithm, the model seems to start with all literals and then gradually drops literals as it sees more examples. Upon manual inspection, model does not always drop literals right when it sees a positive example. At the same time, as can be seen from Figure [6] when the prompt contains more positive examples (second column), the model drops literals more quickly and reaches perfect accuracy with fewer examples overall. On the other hand, with fewer positive examples, the Transformer seemingly drops literals later (third column in Figure (6) and needs more examples to reach near- prar-perfect accuracy. This behaviour is similar to the classical algorithm. Additionally, we compute the number of times the Transformer model drops an incorrect literal (a literal which is present in the target conjunction) at any point in time during the in-context learning phase. We find that across all three input distributions, it drops a literal incorrectly in less than 0.1% out of 1k prompts containing 70 examples each. In over 95% of the prompts, converges to the correct target conjunction. Our results suggest that Transformers implement an algorithm akin to the classical one, initially starting with all literals and then progressively dropping
found that the
25

---

Published as a conference paper at ICLR 2024
Mean
ATTN Mean
Overall
4:14
6.00
4P%
Comundiion
Step
Figure 17: Left: Figure depicting the mean of the gradients of parameters such MLP and attention parameters across different iterations of training on Parity-(10, 2) and Conjunctions. Right: The loss of Transformers Conjunctions Parity-(10, 2) across different iterations of training.
them as they encounter more and more positive examples, However, deviations from the classical algorithms exist which remain to be understood.
F CURIOUS CASE OF LEARNING PARITIES
An interesting and somewhat surprising phenomenon is the failure of Transformers and other archi- tectures on the class of Parities and sparse Parities. contrast to other function classes where models are able to learn some learning algorithm, for Parities, they do not seem to be able to find any kind of learning algorithm that performs beyond chance-level accuracy.
We examine the gradients and the model parameters during the training process. In Figure 17 we show the mean of gradients for all parameters of attention and feedforward networks in the Transformer. Observe that the gradients are very close to 0 after a few iterations of training. Note that this in contrast to what we observe while training Transformers for tasks such as Conjunctions where gradients not so close O. However, the exact reason why Transformers fail to learn anything is unclear and is left as an open problem.
The problem of learning Parities and Sparse Parities have well-known hardness results Kearns (9988)
in the Statistical Query framework indicating that Parities require 20(()) queries and Sparse Parities require n (A)) queries (where k is the number of relevant bits). Gradient- based methods are considered be only as powerful as SQ-leaming algorithms Emite-preciste settings and hence any model such as Transformers applying a gradient-basee algorithm to learn in-context would require exponential number of steps to predict accurately. For sparse parities PARITY-(10, 2), we provide more than n" examples in the prompt and hence a model applying gradient- based learning such FFNs can solve it (see Fig. 18 Left). For instance, feedforward networks trained with gradient descent on the same number of examples as provided to Transformers for ICL are able to achieve near-perfect accuracy. However, Transformers and other architectures do not seem to make any progress during their training process. Also, note that the hardness of learning Parities primarily holds for uniform distribution over inputs and does not apply to input sets with teaching sequences which are no longer uniform.
Parities are PAC-lcarnable using the Gaussian elimination algorithm (Fischer & Simon 1992) with O(n) examples and if any of the architectures could learn implement the algorithm. then they would have been able to solve it with (n) examples.
Transformers vs LSTMs. An interesting difference we observed is that for the PARITY-(10,, 2) problem, LSTMs achieve 100% accuracy if the test examples are labelled by the same set of functions as the training examples. This not true for Transformers. For the PARITY-(10. problem. there are only 45 different functions. For the results in Table D we ensure that the training examples are labelled by 23 of those functions and the test examples are labelled by the remaining and unseen functions. However, if we uniformly sample function out of the 45 functions during both training and evaluation, then we observe that LSTMs achieve perfect accuracy during evaluation. This is interesting since the sequence of input points 21,..., .. Zy new during evaluation and hence is not clear case of memorization. On the other hand, since they do not generalize to unseen functions, is difficult to claim that LSTMs can learn sparse parities in-context.
Curriculum learning. For Sparse Parities, we also tried curriculum learning similar to Garg et al. (2022) but did not observe any improvement. In particular, trained Transformers for the problem
26

---

Published as a conference paper at ICLR 2024
Par 2)
FFN on Teach Conjunction n, n_dims 75
1.0
Recunsec
Accurasy
0.4
0.4
0.2
0.2
MR.n=3
Dvoraping
0.0
hall class
62
146
30
40
57
60
10
50
examples
In-contest essmples
Figure 18: Left: Performance of Feedforward networks (FFN) trained with gradient descent on Parity-(10, 2) with the same number of examples as provided to models in ICL setting. Right: Performance of FFN Teach Conjunction task.
of PARITY-(14, 2). In the curriculum learning setup, the input dimension is initially smaller, i.e., 9 and it increases incrementally by after every 50k steps. Hence, effectively for the first 50k steps, the model is trained for PARITY-(99 2). then PARITY-(10, 2) and so on eventually ending at 14 (trained 250k steps after reaching 14). The model is trained for 500k steps in total. The number of examples in the prompt m 120 in the beginning and increases by 20 every 50k steps and eventually stays at 200. We start at input dimension 9 because below that the total number of Boolean inputs is very small and the prompt will cover over half of all possible inputs. We do not find any improvement with the curriculum learning setup as well. The loss curve is identical to the one in Figure 17 (right) and is hence omitted.
Performance of Nearest Neighbours. In the case of sparse parities, nearest neighbour approaches can do quite well, particularly for relatively small values of k and n. For instance, suppose there only two relevant bits, say &- 2. then for any fixed point conditioned on the relevant bits matching, the expected distance to a random point is (n 2)/2. On the other hand, if the relevant bits don't I exactly match, then the expected distance a random point is at least (n 10-2) 2)/2 1. Since the probability that the two relevant bits match is 1/4, we expect with a relatively high probability that the nearest neighbour would match the relevant bits. As a result the nearest neighbour classifier will have reasonably high accuracy. We observe that the performance of LLMs on this task is better than random, and comparable to nearest neighbour.
G TEACHING SEQUENCE EXPERIMENTS: ADDITIONAL DETAILS
Teaching Sequences. The concept of teaching sequences and teaching dimensions was introduced in Goldman & Kearns [1995). For any class of functions F, the teaching sequence of a function f in_F a sequence of labeled instances (X1, V1, ......... X Ym) such that it unambiguously identifies f in F - only the function f is consistent with the sequence of labeled instances. Let T(f) be the set of all teaching sequences for the function f. The teaching dimension (Goldman & Kearns 1995 of function class is defined as, TD(F)= = max (minn-e(mii)ee)) [r]).
Conjunctions and Disjunctions. The teaching sequence for Conjunctions can be created follows. Suppose f is a conjunction of A literals. We will create k + 2 points. For the first two points, the variables corresponding
all literals in the Conjunction are to True, that is, they are for positive literals in the Conjunction and 0 for negative literals. In the first point, all variables that do not affect and in the second point, all of them are set to 1. The next
the output of the function are set points will correspond to each of the literal in f. For each literal z;, we create a point x: E {0. 1)" where the variable of x at is if 2; the Conjunction and is 1 is Σ is in the Conjunction. The variable corresponding to every other literal in is set to 1 if it is positive literal and is 0 if it is a negative literal. The variables which do not affect the output of the function are all set to O. Essentially, these examples show that even if the variables corresponding to every other literal in the function are set to true, the function value will still be because one of the literal values is set to false. The teaching sequences for Disjunctions created in similar manner.
See that since for every Conjunction or Disjunction, the length of the teaching sequence is + 2, the teaching dimension is n + and for each function with & literals, the exact function can be identified
27

---

Published as a conference paper at ICLR 2024
Teach Conjunction n. dims
Teach DNF -n. dima
Teach Parity n dims
1.0
3.0
Hoan Accumacy
Muat Accunacc
04
Moin
Trandfeme Wr.n-
Trandeeree J-33 nulkboaatee
Tondherer
RR p-1 nulchesfee
60
26
In-contest oxamples
In-conicat esampkes
In-carioet champss
Figure 19: Performance of Transformers various tasks with Teaching Sequences. The plots depict the performance of models on all examples. Note that, most examples in the teaching sequence have the same label and hence even the Nullclassifier has near-perfect accuracy. The plot values up the expected length of the teaching sequences are omitted to avoid confusion. Refer to Section G. for more details.
with 1: + 2 points in the prompt example or a training set. Note that the sample complexity of (m) for Conjunctions Disjunctions is with respect to PAC-learning in the sense that with (m)) points, one could guarantee that the error will be within some e for arbitrary distributions. However, the exact number of samples will depend on the value of and could be much larger than k when the error c is required to be very small.
DNFss and CNFs. For simplicity let's consider Monotone 3-DNFs which only have positive literals. For each clause or Conjunction in the DNF, we create k + 1 points. The first point is such that variables corresponding to every literal in the clause are set to and all other variables are O. The other k points are created as follows. For every literal in the clause, there is one point where the variable corresponding to the literal is and the variables corresponding to other literals in the clause are set to 1. The variables which are not in the clause are set to O. For instance if the input is over {0, 1]4 and the clause is x1 A Ø3, then the three points corresponding to the clause will be [1010], [0010], and [1000]. The teaching sequence for the 3-DNF is the union of the teaching sequence of its three clauses and hence will have size + 3 where I is the total number of literals in all clauses. The teaching sequence for 3-CNF can be created in similar manner.
For sparse parities with k relevant bits, the teaching sequence has k points where in each point the variable corresponding to one of the relevant bits is set to and every other bit in the input is set to O. Note that, this is a teaching sequence of the class PARITY-(n, k) which have exactly k relevant bits. This would not work as teaching sequence for the entire set of Parity functions PARITY-n.
Sparse Parities.
For further details on teaching sequences, see Goldman & Kearns 1995
G.1 ADDITIONAL DISCUSSION
Performance of FFN. Figure 18 (right) depicts the performance of feedforward networks trained with gradient descent on examples with the teaching sequence. FFNs require larger number of additional points apart from the teaching sequence to predict with high accuracy. This is not quite surprising as FFNs+SGD are quite general-purpose learning algorithms. At the same time, it is difficult to integrate such -specfffc knowledge into them so that they perform more optimally.
Additional Details of Plots. Figure 19 depicts the performance of Transformers and baselines on all examples including the tcaching sequences. Most examples in the teaching sequence have the same label and hence even the Nullclassifier obtains near-pere pear-perfect accuracy for some cases. the structure of the teaching sequence is known and it is known that the first & examples will be the teaching sequence, then it is also possible to predict the labels of the teaching sequence correctly. For sparse parity, all examples in the teaching sequence have the label 1. For Conjunctions and DNF's only a couple of examples have the label 1 and all other examples have the label O. Such examples visibly distinct and hence it is straightforward to predict their label if it is known that they are part of the teaching sequence. The plot values up to teaching sequences are omitted in the main paper to avoid confusion since they do not reflect the effectiveness of the model the baselines the tasks.
28

---

Published as a conference paper at ICLR 2024
Teach Conjunction
Teach Parity-120,
All Inputs permuted n dims 28
All inputs permuted
Moan Accursc
6.4
9.6
0.4
IF cemmuced
TF. peruuees
15 Varlls
TF- Vari
TP Tuach
T.. Teach
na ussiier
rulld Fir
10
20
60
62
20
100 320
Invcommtd
In-sortest
Figure 20: Performance of Transformers on prompts with permutation of teaching sequence examples and random examples. On Sparse Parities, the behaviour is the same as the vanilla case whereas for Conjunctions, the performance improves for prompts with 70 examples. The setting becomes closer to the vanilla case as the prompt length goes higher. See Section G. for more details.
Performance on OOD functions. We explored the performance Transformers on out-of- distribution prompts for Conjunctions where the teaching sequences are typically shorter or longer compared to the distribution during training. The distribution over Conjunctions during training is the same as the vanilla setting described in Section C.2 The probability of any literal (or its negation) being in the target conjunction is 30% and hence for inputs over n = 75 dimension, the expected length of the teaching sequence is 27. We evaluated the trained Transformer on prompts from two different distributions. In the first distribution, the probability of literals being in the Conjunction is 60% and hence the expected length of teaching sequences is 47. Similarly, in the other distribution, the probability of literals being in the Conjunction is 15% and hence the expected length of teaching sequences is 13. In both cases, the behaviour of the trained Transformer is identical to the in distribution setting. The evaluation curve is identical to Figure 19 and is hence omitted.
Permuted Examples. We have considered two types of prompts: (a) prompts with random examples sampled from some distribution and (b) prompts which begin with teaching sequence followed by random examples. We explore the performance of Transformers on another type of prompt which includes both examples from teaching sequences and random samples. In this third type (c) called "permuted', for a prompt with m total examples, we create the teaching sequence with examples and sample
examples from distribution (given in Section C.2 and permute the entire set of inputs to create the prompt. In other words, the examples in the teaching sequence are present in the prompt but not necessarily in the beginning anymore.
Figure 20 depicts the performance of Transformers on the three types of prompts respectively (a) prompts with random examples (marked vanilla), (b) prompts with teaching sequence in the beginning (marked teach) and (c) prompts with a permuted combination of teaching sequence and random examples (marked permuted). Without the teaching sequence in the beginning one would naturally expect the setting to be closer to the vanilla case which happens in the case of Sparse Parities (Figure 20 For Conjunctions, the behaviour is relatively more interesting. Unlike Sparse Parities, some examples of the teaching sequence of Conjunctions are more informative than others. With 70 examples, Transformers in the vanilla setting reach near-perfect accuracy with about examples. Since the likelihood of those couple of examples in the teaching sequence being in the first 30 examples reasonably high, Transformers with such permuted prompt examples seem to converge to high accuracy faster than the vanilla case. As the size of the prompt is increased from 70, the behaviour becomes closer to the vanilla case since the probability of the informative examples being in the first 30 decreases.
H ADDITIONAL DETAILS OF EXPERIMENTS WITH LLMS
H.1 ADDITIONAL DETAILS OF FROZEN GPT EXPERIMENT
In Section 5 we discuss the setup and results for experiments with pretrained models. We provide additional details of the experiments here.
29

---

Published as a conference paper at ICLR 2024
You are given some examples of inputs and their corresponding labels. You need to learn the underlying boolean function represented by these input-label examples. Predict the label (either 0 or 1) for the final input.
Input: 0.0.0
Label: 0
Input: 1000 1
Label: 0
Input: 0.0.0.0 I
Label: 0
(... more exemplars ...)
Input: 101
Label:
Input: 1 100
Label: 0
Input: 100
Label:
Figure 21: An example of a prompt provided to the LLM in the direct evaluation experiments. Here, the model has to learn function from the Majority class in 5 dimensions and predict the lahel for the last input. The prompt consists of a natural language instruction and k example points of the function.
In Section and as well as several prior works (Garg et al. 2022 Ahuja et al. 2023 Bai al. 2023), experiments were conducted in the meta-learning-lie setup in order to understand the in- context learning abilities of Transformers. With the experiments with frozen pretrained models, we aim to explore if pretrained models learn any mechanism that is useful for solving tasks in the meta-learning-likk stylised setup.
The experiments follow the same framework as described in Section 2 with the exception the weights of the Transformers are not modified or updated during the training process apart from the input embedding layer and the final output layer. We the GPT-2 XI. (1.5B parameters) model from Hugging Face (Wolf et al. 2020).
In the stylised setup, since each Boolean input x E {0, 13" is provided embeddings and tokenizer of the pretrained model cannot be used for prediction. Hence, we replace the original embedding layer with 1-layer ReLU FFN: {0, 1 - width which produces an embedding for each & E (0, } Similarly, we add an output FFN which predicts the final output given the vector produced by the pretrained model.
single token, the original
Similar to other experiments we train the model on Conjunctions and the nearest neighbour task by sampling functions and input points to create training examples. The training process is used to update the embedding and output layer and the weights of the Transformers are fixed.
H.2 DETECTING NEAREST NEIGHBOUR HEADS IN GPT-2
In Section 5.1 we discussed that were able to discover attention heads in the GPT-2 model that very closely implemented the nearest neighbours algorithm. In this section, we provide more details about that experiment.
Our methodology for detecting attention heads that directly implement the nearest neighbours algorithm is similar to the one used by Olsson et al. (2022) for finding induction heads. While training the model on the Nearest Neighbours task, for each attention head in the model, we compute a 'nearest- neighbours
(nn-score)'. After every 500 training steps, provide the model with batch of 100
examples, each example consisting of 80 points, i.c., e, Xx1Y1.
Xso. Yso). The nn-score
x Xa
the attention paid to y, for predicting yk (0 < j < k) where, j = arg max
is
|
[xx
the index of the nearest neighbour of Xg, averaged for the last 40 points (i.e., 40) over all 100
30

---

Published as a conference paper at ICLR 2024
Parity n. 5
Parity n_dims=7
Parity n_dims=15
MA--70
L-33--3333
Figure 22: Results with the direct evaluation of LLMs at inference time across varying dimensions for the PARITY-N task.
examples. If the nn-score for particular head is greater than 0.5, label that head 'nearest neighbour head'. In our experiments with frozen GPT on the Nearest Neighbours task, we were able consistently find 8-10 nearest neighbour heads across multiple runs.
H.3 ADDITIONAL DETAILS AND RESULTS OF DIRECT EVALUATION EXPERIMENT
In Section we described the setting of direct evaluation of LLMs. We provide additional details regarding the experimental setup below.
The main prompt (see Figure 21 for an example) comprises of instruction in natural language followed by series of k example points V:). where x; E {0, 1) is provided as sequence of tokens 21..... Fd I, E {0, 1} and y, E {0. 1] is also provided as single token. The model's goal is to predict the correct label y E {0, for the query point X For particular function, we sample a sequence of n points and prompt the model with the function. We call the model multiple times, increasing by a value of every time. The prompt in each call consists of the first points (5 < & < n) from the n-point sequence, and asks to predict the (A + 1hth point. We repeat this experiment with 100 different functions from the same function class.
points as in-context exemplars of
We experiment with three classes of functions: Conjunction, Majority, and Parity. We consider dimension d E 7, 15} and set the number of points n = 50 when < 10 and n = 100 when d > 10.
Additional Results. The results of evaluating LLMs directly on the Parity task are provided in Figure 22 We also experimented with LLaMA-2 models of smaller scale well GPT-2 as shown in Figure 23 Our results seem to indicate that model scale seems to play some role in the ability of LLMs implement learning algorithms. This be seen from the performance of the pre-trained GPT-2 model, which fails on both tasks even for 5 dimensions, and the (gradual) increase performance as we increase the size of the LLaMA models. Also, it quite surprising see that even smaller LLaMA models are also able to achieve nontrivial levels of performance for both tasks.
IMPLEMENTATION DETAILS
All of our implementations for experiments are based on PyTorch (Paszke al. 2019). For our experiments with Transformers trained from scratch, we use the Huggingtace Transtormers library (Wolf et al. (020) and our own custom implementation. For recurrent models such as LSTMs, we use PyTorch's inbuilt implementation. For Hyena (Poli et al. 2023) and DSS (Gupta et al. (022), we adapt the official implementation by the authors for our experimental setting. For RetNet Sun et al. 2023),
own implementation.
It is prohibitively expensive to experiment with a very high number of functions for the OpenAl models, so we limit the number of functions to 100. We average over 2000 different functions for the baselines and 1000 different functions for the I.LMA-2 models for more robust results.
31

---

Published as a conference paper at ICLR 2024
Conjunction dims=5
Conjunction n, dims-7
Conjunction dims
Majority n, dims=5
Majority n. dims-7
Majority n. dims=15
Moon ACCeRII
500
L 2008
Figure 23: Results with direct evaluation for LLaMA models of different scales and GPT-2. The top row shows the performance across varying dimensions for the Conjunction task while the bottom row shows the performance for the Majority task.
Hyperparameter
Transformer and others
LSTM
D ..mdee/Hiddenn Size
[256, 512]
[64, 512]
Heads
[4, 8
Order
[2, 3]
Number of Layers
[1, 16]
[1, 8]
Learning Rate
[le-2, le-5]
[le-2, le-5]
Position Encoding Scheme
[Learnalee, Absolute]
Table 3: Different hyperparameters and the range of values considered for each of them. The hyperparameter Heads is only relevant for Transformers and RetNets. The hyperparameter Order is only relevant for Hyena. See Section I for more details.
All our experiments were conducted using 16 NVIDIA Tesla V100 GPUs each with 16GB memory. For each dataset, we extensively tune across several hyperparameters and report the results based on the best-performing models. Table lists the hyperparameters used for tuning the models for Boolean function experiments in Section 3 We use a grid search procedure to tune the hyperparameters. For all results, we used Adam Optimizer and tuned the learning rates. For all architectures apart from LSTMs, we tuned across depths E (1, 2, 6, 12, 16] and for LSTMs we used depths {1, 21,2,3, 3, 8) primar- ily because LSTMs with large depths are harder to train. For LSTMs we tuned the width or hidden_ste size across {64, 256, 378, 512} and for other architectures we use {256, 512]. For Hyena, we tune the order hyperparameter across (2,3) and for Transformers and Retnets For all non-recurrent models, we try both learnable and absolute positional embedding schemes. For all models, we tune the learning rate across (0.01, 0.005, 0.001, 0. 0.0005, 0. 0.0001, 0.00005, 0.000001). We train the models for different numbers of steps/iterations [30k, 500k] depending on the task where each iteration with a fresh batch of in-context sequences. Note that in all these tasks apart from the experiments with finite samples in Section D.3 the training loss never reduces to 0 since each batch of examples is labeled by different function (with high probability). We train for large number of steps (200k) if the loss doesn't 't reduce train till the loss has reduced and converged for at least 20k steps. For instance, for tasks like Conjunctions models converge to low loss in 20k steps train the models to up 40k steps. For other tasks such Parities, we train for 500k steps. For the additional linear regression task (Figure g we follow the same setup and hyperparameters as described in Garg et al. 2022).
the heads across {4, 8).
32

---

Published as a conference paper at ICLR 2024
Based on the experiments, we find that Transformers and Hyena relatively much more robust across various hyperparameters than other architectures. Among most tasks and architecture, we find that the learning rate has the most influence the performance and the depth has nontrivial influence. For other hyperparameters such as heads and widths, we do not see any nontrivial difference in performance.
Direct Evaluation Experiments. For experiments with open-source models such as LLaMA-2, we use Huggingface Text-Geenrrtioo--nfeeenngg Experiments using GPT-3.5-Turbo and GPT-4 were performed using the OpenAl APP Experiments with locally deployed large models like LLaMA-2 were conducted using 2 A100 GPUs each with 80GB memory. For all experiments, we decode greedily and generate a maximum of two tokens (whitespace and the label")
J ADDITIONAL RELATED WORK
Our results on the adaptive selection of algorithms add to some observations in recent works, Ahuja ett al. 22023; ; Bai et al. (023) explored (among other things) the efficacy of Transformers in learning mixtures of tasks in-context and showed that they could adaptively select appropriate algorithms depending on the sequence of inputs and labels. In our case, the emphasis is on choosing between different algorithms for the same class of functions (e.g. Conjunctions). Hence, the target labelling function is still a Conjunction where the vanilla algorithm leads to near-perfect accuracy as well but models such as Transformers are able to choose the more sample-effieien algorithm which leads to near pear--erfect accuracy with fewer input examples. The fact that LSTMs can exhibit in-context learning phenomenon more systematic comparison of multiple architectures on test bed with a variety of tasks. Evidence from our experiments suggests that while attention may not be necessary and various attention-free models can solve multiple in-context learning tasks, they are not sufficient at the moment to match Transformers' performance on all tasks considered in our work.
observed in Xie et al. (202T) well. Our work attempts conduct
In recent years, there have been many empirical works (Liu et al. 2021 Min et al. 2021 Lu et al. 2022, Ruzeghi al. 2022 Min al. 2022a Olsson et al. 2022 Wei al. (023) that have analysed the capabilities and limitations of in-context learning (ICL) in large language models (LLMs). The
ability of L.LMs to solve simple prediction problems has been informally explored in Lovre (2022).
Liu et al. (2021) explored various strategies for selecting examples that improve in-context learning performance. Lu et al. (2022) demonstrated that the in-context learning ability of models is also sensitive to the order in which the samples are provided in the prompt. Raazghh et al. (2022) worked with numerical reasoning tasks and showed that in-context learning performance is stronger for instances whose terms models really learned new tasks in-context by showing strong ICL performance even when the prompt labels are chosen randomly. (Olsson al. (022)) and (Elhage al.) 2021) frame the in-context learning ability slightly differently by referring to any model that gets better (i.e., shows a decrease in loss) with more context (i.e., increasing token indices) as an in-context learner. They provide arguments for the existence of special circuits, which predict the next token by observing similar patterns previously seen in context, inside the Transformer model, that are responsible for in-context learning. More recently. Wei et al. (2023) showed that the ability of models to override semantic priors and effectively learn the task presented in-context emerges with scale.
prevalent in the training data. Min et al. (202aa) questioned whether
httpss//plaaffmm..o openai.com/
Iff the model does predict label in {0, 1}, consider the prediction incorrect.
33


Reviews:
[{"review_id": "m1fpGYur8v", "reviewer": "Reviewer_bf3N", "summary": "The paper investigates the task of training models to learn various boolean function classes in-context. While the prior work in this theme has mainly focussed on the Transformer architectures and real-valued functions (e.g. linear functions), this paper studies the performance of various architectures (LSTM, Hyena, a state space model etc.) and mainly focuses on boolean functions. Some notable results include:\n\n1) On all function classes where Transformers can learn in-context, other architectures considered also work. However, the performance of other architectures can be worse. For instance, for the nearest neighbor function class, Transformers achieve 100% accuracy whereas other architectures achieve an accuracy of around 90% or less. The Hyena architecture particularly stands out and matches the performance of Transformers for all function classes considered except the nearest neighbors function class.\n\n2) No architecture is able to perform better than chance on the task of in-context learning parities and sparse parities. This happens even in the setting where a feedforward neural network (trained on the in-context examples using gradient descent) is able to learn perfectly.\n\n3) The paper also tests existing LLMs like Llama and GPT-4 (that are not trained explicitly for in-context learning) on in-context learning tasks in small dimensions which are guaranteed to not be in the training set, and shows that these models perform at par with a nearest-neighbors baseline.", "questions": "Some questions/suggestions:\n\n1) It seems all the architectures considered (except LSTMs) have the number of hidden layers and latent dimensions in the same range. It would be good to include details of the number of parameters or compute used for each architecture so as to ensure that there is some normalizing factor among the architectures considered. This is to make sure that architectures like LSTMs and RetNets are not performing worse due to having a substantially smaller parameter count.\n\n2) It would be good to clarify in the Results section that the negative results only hold for the particular hyperparameter choices. In particular, these experiments don't rule out the possibility of substantially bigger models or models trained for much longer being able to perform better in certain cases. \n\n3) In the abstract, it is mentioned that Transformers can learn gradient-based learning algorithms. The prior works that I know of either claim that Transformers can represent such algorithms or that their performance matches gradient-based algorithms - none of these imply that the trained Transformers actually encode gradient-based learning algorithms. This line should be rephrased to avoid confusion.\n\n4) Here is a blog post that might be worth mentioning in the context of in-context learning abilities of real LLMs: https://www.alignmentforum.org/posts/c2RzFadrxkzyRAFXa/who-models-the-models-that-model-models-an-exploration-of\n\n5) Did you explore using a curriculum for training model to in-context learn parities (similar to Garg et. al.)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I enjoyed reading this paper. There are two results that I mentioned in the summary that stand out for me:\n\n1) No architecture considered is able to in-context learn parity. The problem instances considered can be solved perfectly with Gaussian elimination. This suggests that these models struggle to learn Gaussian elimination. This is the first interesting negative result that I know of in the in-context learning ability of these models (when explicitly trained for in-context learning), and deserves more investigation.\n\n2) The comparison between different architectures and their in-context learning performance on various function classes also seems interesting. Why do all architectures except Transformers struggle to some extent on Nearest Neighbors? Why do RetNets and state space models perform worse on 0-1 Threshold functions? Trying to find answers to such questions can shed light on the role of different architecture components.\n\nIn general, the paper is full of nicely executed experiments and many of them would be interesting to the community.", "weaknesses": "I don't see any major weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cEasYQk3TJ", "reviewer": "Reviewer_fGea", "summary": "This paper studies the ability of transformer models to perform various boolean functions. More specifically, the authors train from scratch transformers on Boolean functions and they observe that  the models can achieve very high accuracy for some of them, but for some other (parities) they correspond to a  random guess; then they add in the training process a prompt that uniquely identifies the function that the model is trying to learn and train in the same way. In this case the models are able to perform well given that the identifying sequence is given at test time in the first tokens of the prompt. Finally, they train in the same tasks with and without the identifier;  in this setting they observe that the transformer performs well when given the identifier and close to the random guess when is not. The paper also includes similar observations for pretrained transformer models. They either train the embedding layers of pretrained models like GPT2 and then prompt them, or they simply prompt GPT4.", "questions": "1. When the authors create the datasets, it seems like they always sample a function and $m$ Boolean inputs. At test time, is the prompt used also generated in the same way? Sampling one function an $m$ Boolean inputs?\nMy question is related to whether the authors observe that these models can ``generalize'' to the case that the sequence length is not the one that the models were trained on.\n\n2. How exactly the authors prompted GPT4? Is it just a sequence of examples? It seems that in the supplemental material there is a folder prompts that contains some algorithms. \n\n3. Could the authors specify, which are the insights that this paper provides compared to previous work?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is in general well written and the authors have performed multiple experiments with different models and baselines. The setting examined has some benefits, as it is discrete and it can be transferred to prompting models by changing the embedding layers. The experiments are consistent with what other authors have observed.", "weaknesses": "I am not sure which is the message of this paper compared to previous work. It has already been observed that transformers can \"choose\" between algorithms in [1], while we already knew that there are some tasks that transformers perform well and some others that they don't. \nI think that all the observations in this paper have been observed in different settings in other papers, thus I consider the contribution marginal. \n\n[1]: Bai, Yu, et al. \"Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection.\" arXiv preprint arXiv:2306.04637 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y3zDv2cXtI", "reviewer": "Reviewer_tbmK", "summary": "This paper studies Transformer's abilities to learn boolean functions. The main results are three-folds:\n\n- **Transformer's performance** on the boolean functions can be grouped into 3 categories:\n  - Perfect: this include conjunctions, (sparse) disjunctions, CNFs and DNFs, and nearest neighbors.\n  - Above random but not perfect: this include majority, threshold, and integer halfspace.\n  - Random-level: (sparse) parity. In particular, for Parity-(10,2), the fully connected network can learn to be perfect while Transformers are at chance-level.\n\n  The paper also checks the performance of difference models, including LSTM, DSS (a state-space model), Hyena (a long convolutional model), RetNet (a hybrid model). These models are all worse than Transformers on the in-context learning of boolean functions, with Hyena being the closest.\n\n- **Ability of learning from teaching sequences**: Transformers are able to leverage these teaching sequences well and learn the task with significantly fewer samples.\n  -  Teaching sequences refer to sequences of samples that are sufficient to uniquely determine the function from a given function class.\n\n- **Ability of pretrained models**: the paper studies two variants, 1) GPT2 with trained embedding and decoding layers (i.e. treating each $\\{0,1\\}^n$ as a sample to be embedded), and 2) direct evaluation of LLMs (i.e. treating $\\{0,1\\}^n$ as a sequence of 0,1 tokens). Transformers perform reasonably well in both setups. For the GPT2 experiments, the authors identified attention heads that closely implement nearest neighbors, similar to induction heads.", "questions": "- Parity-20: what if reporting the accuracy on every position, rather than the final position?\n  - i.e. whether the full-sequence accuracy is too harsh, and some more continuous progress measure might be more informative.\n- For OOD test results (Fig 10), how about the comparison to LSTM, especially under aggressive distribution shift where Transformers fail to preserve the in-distribution accuracy?\n\n- About teaching sequences: [_Update_: the questions have been addressed during the rebuttal. I hope the updated paper could include the clarifications in the discussions; for example, which specific aspects of the empirical results suggest \"two algorithms\", and that it's important for the teaching sequences to be at the beginning of the list of examples, rather than mixed in as an arbitrary order. ]\n    - Fig 2: what's the value of $k$? To better show the progression of performance, could you please start the x-axis from 1?\n    - I'm curious about the robustness of the teaching sequence results. For example, for different values of $k$ (with dimension fixed to 20), does Transformer always able to \n    - For the teaching sequence experiments, I wonder what would happen if during test time, we permute the $t$ teaching sequence samples, or permute all $m$ samples.\n    - Appendix F: why would this not work as a teaching sequence for the entire set of parity?\n        - Note that $k$ samples suffice only if the value of $k$ is known, and this would imply that the shortest teaching sequence for the full set of parity is of length 0.\n    - Relatedly, the point that \"FFN cannot learn from only the teaching sequences\" seems to be naturally true: the number of samples required in the teaching sequence is defined _given that the function class is known_. For example for sparse parity, $k$ samples suffice only if we know that the task is $k$-sparse parity and we know the value of $k$. However, the function class is not specified to the FFN, hence it's expected that $k$ samples alone are insufficient to learn the task.\n    - I'm not sure it's fair to say that Transformers learn \"two distinct algorithms\" for learning with and without teaching sequences, since this seems to me as simply a matter of distribution shift: if the Transformer has only seen sequences where the first $t$ samples are from a teaching sequence, then there is a drastic distribution shift in the test time when there's no such samples. What am I missing here?\n\nMisc comments\n- Section 5: the paper says real-value functions are not straightforward to evaluate \"since LLMs receive and produce discrete values\": I'm not sure how much this distinction is true or relevant, since LLMs do have embeddings which are vectors of real values.\n- Table 1: for better readability, perhaps consider highlighting the numbers with colors (e.g. set the text background according to some colormap) would make it easier to read.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The boolean evaluation setup is clean and controllable.\n- The paper presents a large set of experiments.", "weaknesses": "- The takeaway messages are a bit unclear to me. [_Update_: The authors have clarified in the rebuttal. I hope the changes could be reflected in the revised paper.]\n- Some results could be better presented and explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nWOt1XGCFc", "reviewer": "Reviewer_9RLW", "summary": "This paper investigated the in-context learnability of Transformers on discrete Boolean functions. They showed that when trained in an in-context way, the Transformers can in-context learn some Boolean functions like conjunctions, disjunctions, DNFs and CNFs, while they can struggle on more difficult tasks such as parities. They showed that when presented the teaching sequences, the Transformers show better in-context learnability and they can learn tasks like parities in this case. \n\nThey also showed that besides TFs, many other architectures show in-context learnability competitive to TFs on learning Boolean functions. They hypothesized that TFs learn two distinct algorithms on some tasks, which I feel not that convincing (I will explain it later). They also did some experiments on LLM and showed that the GPT2 architecture with fixed parameter, and many other LLMs can in-context learn Boolean functions and are competitive to Nearest Neighbour.\n\nIn general, this paper showed in experiments that the trained TFs can in-context learn some Boolean functions. The experiments with teaching sequence is particularly interesting. It's possible for me to update the score.\n\nThanks for the response from the authors. I raised my score to eight.", "questions": "Below are my suggestions, which I think can help make your paper stronger.\n\n1. Your definition and narratives of in-context learning and the algorithm learning perspective (the last two paragraphs in 'in-context learning' paragraph in section 2) seems to follow closely with the formulation in [1] and the formal definition in [2]. Does your definition of in-context learning similar to their definitions? Or do you have any differences? IMO maybe you can discuss more about your definition of ICL and how it relates to algorithm learning process.\n\n2. I am not sure how you sampled the random conjunction function for each task. I think it is more important to say how you sample the random functions than how you sample the random inputs. Do you sample the random conjunction functions by sampling k variables for a fixed k and then form the conjunction function as the intersection of these k variables (f = 1 iff all these k variables are 1)?\n\n3. Is it possible for you to show what algorithm the TFs actually implement on some simple tasks like conjunction or disjunction? For this, you can either look into the attention weight of attention matrix (maybe train a single-layer TF?) or maybe you can try to provide some constructions that can provably learn these tasks? These can be hard even an open problem, which is definitely not a requirement.\n\n4. For some tasks in your paper, there should be existing algorithms to learn it, such as conjunction or disjunction. I am also wondering how does trained TFs compare to them? Also, some existing paper shows that the TFs can approximate or possibly learn (in-context) the Bayesian optimal estimator over some function class [1,2,3]. I suppose under the task distribution in your paper, it is very likely that the Bayesian optimal estimator is analytically intractible, but I think it should be numerically computable under some simple tasks. So I am wondering how does trained TFs compare to the Bayesian optimal estimators (or some strong, computationally efficient baseline on specific task, if any).\n\n[1]. Transformers as Algorithms: Generalization and Stability in In-context Learning\n\n[2]. Trained Transformers Learn Linear Models In-Context\n\n[3]. Pretraining task diversity and the emergence of non-Bayesian in-context learning for regression.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The  experiments are sufficient and interesting, showing the in-context learnability of trained TFs on discrete Boolean functions. Previous papers mostly focused on the IC learnability of linear functions, sparse linear functions or NNs. The consideration of Boolean functions is particularly creative.\n\n2. The experiments about teaching sequence is particularly interesting, and also for the experiments on LLMs. The fact that LLMs can implement the kNN algorithm in-context is amazing, and I also like the narratives of the algorithm learning perspective of in-context learning.\n\n3. The writing is great and easy to follow.", "weaknesses": "1. The author claimed that TFs can learn two distinct algorithms on tasks such as conjunctions, which is not that convincing to me. \n\nLet's take figure 3 as an example and let's call the four sub-figure a to d from the left to the right. The way that authors compared these four figures and draw conclusions is that: they compare a and b, and the compare c with d, then they drew conclusion that the trained TFs can learn two distinct algorithms. This is not a good way for comparison. This is because one can easily give a counter-example to show that a single algorithm can simultaneously achieve a and b. For example, suppose the algorithm that TFs learn is: randomly pick one decision rule (or Boolean function) which is in the conjunction function class and agrees with all examples in the test context (the x_i, y_i pairs at test time). Then, when tested on teach conjunction (fig a), since there is only one conjunction function matching all test context, it will achieve a perfect accuracy. When tested with random sequence of examples from a conjunction task, there can be many functions in the conjunction function class that satisfying all test examples, so it can achieve a imperfect performance. Similar logic applies on the comparison between c and d.\n\nAt a high level, if you want to show the trained TFs can learn two distinct algorithms, it is not a good idea to show that they achieve different performance on different test examples but trained on same data distribution, It is better to show that they achieve different performance when trained on different data distribution, but tested on the same examples. In this case, you should compare figure b and c to draw your conclusion, instead of comparing a and b. The reason behind this is that the in-context learning is specific to the pre-training distribution, and it s very natural that they learn different algorithms on different pre-training distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)