Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
Authors: Zhuoyan Xu
Zhenmei Shi
Yingyu Liang
Venue: COLM (2024)
Keywords: Large Language Model; in-context learning; compositional ability
TL;DR: We investigate how Large Language Model behaves in composite tasks empirically and theoretically.

Abstract: Large language models (LLMs) have emerged as powerful tools for many AI problems and exhibit remarkable in-context learning (ICL) capabilities. Compositional ability, solving unseen complex tasks that combine two or more simple tasks, is an essential reasoning ability for Artificial General Intelligence. 
Despite the tremendous success of LLMs, how they approach composite tasks, especially those not encountered during the pretraining phase, remains an open and largely underexplored question.
In this study, we delve into the ICL capabilities of LLMs on composite tasks, with only simple tasks as in-context examples. We develop a test suite of composite tasks including linguistic and logical challenges and perform empirical studies across different LLM families. We observe that models exhibit divergent behaviors: (1) For simpler composite tasks that apply distinct mapping mechanisms to different input segments, the models demonstrate decent compositional ability, while scaling up the model enhances this ability; (2) for more complex composite tasks involving reasoning multiple steps, where each step represents one task, models typically underperform, and scaling up generally provides no improvements. 
We offer theoretical analysis in a simplified setting, explaining that models exhibit compositional capability when the task handles different input parts separately.
We believe our work sheds new light on the capabilities of LLMs in solving composite tasks regarding the nature of the tasks and model scale. Our dataset and code are available at {\url{https://github.com/OliverXUZY/LLM_Compose}}.

Published as a conference paper at COLM 2024
Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
Zhuoyan Xu, Zhenmei Shi, Yingyu Liang
University of Ausconsin-Madise {zxu444, zhmeishi, yliang] www..wiscc......... edu
Abstract
Large language models (LLMs) have emerged as powerful tools for many AI problems and exhibit remarkable in-context learning (ICL) capabilities. Compositional ability, solving unseen complex tasks that combine two or more simple tasks, is an essential reasoning ability for Artificial General Intelligence. Despite the tremendous success of LLMs, how they approach composite tasks, especially those not encountered during the prefraining phase, remains an open and largely underexplored question. In this study, we delve into the ICL capabilities of LLMs on composite tasks, with only simple tasks as in-context examples. We develop test suite of composite tasks including linguistic and logical challenges and perform empirical studies across different LLM families. We observe that models exhibit divergent behaviors: (1) For simpler composite tasks that apply distinct mapping mechanisms to different input segments, the models demonstrate decent compositional ability, while scaling up the model enhances this ability; (2) for more complex composite tasks involving reasoning multiple steps, where each step represents one task, models typically underperform, and scaling up generally provides no improvements. We offer theoretical analysis in simplified setting, explaining that models exhibit composi- tional capability when the task handles different input parts separately. We believe our work sheds new light on the capabilities of LLMs in solving com- posite tasks regarding the nature of the tasks and model scale. Our dataset and code are available at https: //gi thub. cwm/ i vervverxUu XUZY/LLL Compose.
1 Introduction
In recent years, large language models (LLMs) have revolutionized the natural language processing (NLP) and general Al community, Recent advances, including ChatGPT (OpenAI, 2022), GPT4 (OpenAI, 2023), and Claude 3 (Anthropic, 2024) have shown success in various fields. As model scale increases, larger models exhibit new behavior known as emergence ability. One remarkable emergence is the in-context learning ability (ICL) (Brown et al., 2020), where a model can solve new tasks given only few examples as input, without any parameter updates. However, despite recent success, how LLMs solve complex reasoning tasks, particularly not seen in pre-training, remains an open question and largely lacks understanding.
In this paper, we focus on the problem of how LLMs tackle composite tasks that incorporate multiple simple tasks. Specifically, we investigate whether model trained and in-context learned on individual tasks can effectively integrate these skills to tackle combined chal- lenges, which are intuitive and simple for humans. For instance, in Figure 1, if human is given examples where words following an asterisk (*) will be capitalized and words surrounded by parenthesis will be permuted, one can also understand words following an asterisk (*) surrounded by parenthesis will be capitalized and permuted simultaneously. This basic generalization seems trivial, yet we observe that LLMs fail to generalize in this way.
"Fqual contribution

---

Published as a conference paper at COLM 2024
Compositional ability is an active problem in the AI community and is crucial for advancing Artificial General Intelligence (AGI). Recent studies have made signif- icant contributions to the understanding of this area. Dziri et al. (2023) formu- computation late compositional tasks graphs to quantify each task's complexity level. Power et al. (2022) show that mod- els may develop generalization capabilities when trained extensively, beyond the point of overfitting, highlighting phenomenon known as " "grokking" An et al. (2023b) ex- amines how LLMs acquire abstract reason- ing and achieve compositional generaliza- tion in linguistic context through ICL by testing LLMs on tasks that involve translat- ing formal language with custom gram- mar. Although these studies offer insight, how LLMs compose tasks together is still not fully understood, especially in the ICL setting. Moreover, the absence of a solid theoretical framework in these discussions needs to be investigated concerning the un- derlying mechanisms of such behaviors.
Simple tasks
Composite task
Just give me output. Input: apple
give output.
output: APPLE
input: toe
input: bird
output: TOE
oulput BIRD
Input: (farm frog)
output: frog farm
Just give me output. imput: bulll book ) output: book ball
imput:: (* pie sports)
input: hhouse hat)
output: sports pie
output: house
Figure 1: Inconsistent performance in GPT-4. Consider two simple tasks: Tf a word is fol- lowed by an asterisk (*), capitalize the letter. two words are surrounded by parentheses, swap the positions. GPT-4 correctly solves two simple tasks based on demonstrations (left). The composite tasks have test inputs with both asterisk (*) and parenthesis. The correct answer should be output: SPORTS PIE. However, GPT-4 fails to solve the composite tasks (right). The same failure was observed in Claude 3.
Inspired by these seminal works, we further evaluate LLMs on series of compositional tasks through ICL. The models were presented with examples of simple tasks and then asked to tackle composite tasks that they had not
encountered during pretraining in-context learning. We observe various behaviors: (1) for some composite tasks, the models showed a reasonable level of compositional skill, a capability that improved with larger model sizes; (2) for more complex composite tasks requiring sequential reasoning, the model struggle, and increasing the model size typically did not lead to better performance.
Our key intuition is that if the simple tasks that form a composite task can be easily separated into subtasks based on the inputs (e.g., performed separately on different parts of the input sentence), the model is more likely to complete such a composite task successfully (we call "a separable composite task"). The performance of the model depends on how connects and uses the information given for each part of the task. To clarify this insight, we present theoretical analyses in a simplified setting and provide key insights into conditions needed for success in such separable composite tasks.
Our contributions are twofold. Empirically, we introduce a variety of composite tasks from both the linguistic and logical domains to explore how the nature of these tasks influences the compositional performance LLMs through ICL. Theoretically, we provide analysis on a simple yet insightful model: one-layer single-head linear self-attention network (Von Oswald et al., 2023; Akyürek et al., 2023; Mahankali et al., 2023; Zhang et al., 2023b). This framework allows to demonstrate clear separation in input embedding, effectively breaking down composite tasks into simpler components. We delve into the scaling of language models by examining the structure of the key and query matrices in the attention mechanism, arguing that larger models with a more complex internal structure exhibit enhanced performance on individual tasks, thereby improving their overall compositional capabilities on such separable tasks.
1.1 Related Work
We briefly summarize related work and provide detailed discussion in Appendix A.
2

---

Published as a conference paper at COLM 2024
LLMs are often Transformer-basse (Vaswani et al., 2017) equipped with the enormous size of parameters and pretrained on vast training data. One key property that makes such LLM successful is called scaling law: Increasing the scale of language models (pretraining data scale, model parameters) can lead to better performance in downstream tasks. One ability that emerges as the model scale increases is in-context learning (ICL) (Brown et al., 2020). Given sequence of labeled examples and a testing example (combined as a prompt), the model can construct new predictors for testing examples without further parameter updates Dong et al. (2022). Scaling law was first proposed by Kaplan et al. (2020) and then followed up by Hoffmann et al. (2022), emphasizing both the scale of models and training data. Recent works show LLMs with larger scales have distinct behaviors compared to smaller language models (Wei et al., 2023b; Shi et al., 2023b). This work investigates experiments and analyses how LLM can exhibit compositional ability in ICL.
Solving complex tasks and reasoning is an active problem in the AT community Huang & Chang (2022). There is line of empirical works investigating the compositional ability in linguistic fashion (Kim & Linzen, 2020; Levy et al., 2022; An et al., 2023a;b). LLMs are capable of learning abstract reasoning (e.g., grammar) to perform new tasks when finetuned or given suitable in-context examples. In our work, we include linguistic experiments as part of our testing suite, illustrating LLMs' compositional ability: Ye et al. (2023); Berglund et al. (2023); Dziri et al. (2023) show LLMs will struggle to solve tasks requiring reasoning. Berglund et al. (2023) studies that LLMs trained on "A is B" fail learn "B is A". In our work, we conduct similar experiments showing LLMs will fail on composite if different steps of logical rules are mixed.
2 Warm-up: A Failure Case for Composition
Our goal is to understand the behavior of LLMs on compositional reasoning tasks. As warm-up, we evaluate the Capitalization & Swap tasks (Figure 1) on different models. Recall the tasks: given words of common objects, represents the operation of capitalizing the letters, () represents swapping the positions of the two words. We consider the standard in-context learning setting, which concatenates input-output examples K = 10 and one test imput as the prompt for LLM. We perform experiments across various LLM families, e.g. Llama families (Touvron et al., 2023) and GPTss (Radford et al., 2019; Black et al., 2021), see model details in Appendix B.
Evaluation settings. To make thorough evaluations, we con- sider four settings: (1) capi- tal: only on the capitalization task; (2) swap: only on swap; (3) composite: in-context ex- amples are from simple tasks while the test input is about the composite task; (4) com- posite in-context: in-context examples and the test input are all drawn from the com- posite task. The composite in-context setting reduces the evaluation to another simple task, not requiring the model to composite the simple task ability but directly learning from the in-context examples. It serves as the gold standard performance for the composite task. See Table 1 for illustration.
Composite
Composite in-context
Prompt
imput: " apple
imput: (* good * zebra )
output: APPLE
output: ZEBRA GOOD imput: (" bicycle add )
imput: ( farm frog oufpul: frog form
imput: (* bell ford)
Truth
output: FORD BELL
output: ADD BICYCLE
Examples of two settings on composite tasks. Composite: in-context examples are about simple tasks, while the test input is about the composite task. Composite in-context: both in-context examples and the test input are about the composite task.
Table 1:
Results. In Figure 2, somewhat surprisingly, we observe that LLMs cannot solve the composite task, although they perform well on simple tasks. There is a significant gap between the performance in these settings. Models in Llama families can solve capital and swap with nearly 900 accuracy but only achieve around 20% or below on the composite
3

---

Published as a conference paper at COLM 2024
task. We also observe that composite in-context examples will significantly improve the performance: The accuracy of Llama families can go up to match the simple task accuracy. These observations show that the models fail to compose the knowledge from the simple tasks, although they do have the representation power to solve the composite lask (which can only be exploited when provided composite in-context examples) and scaling up may not help.
Llamal
Llama2
GPT
100
100-
80
80
80-
capital
Acc
60
swap
60-
40
composite
composite compose Incontext
20
20
20
0
7b
136
30b
65b
3b
13b
70b
0.74b 1.36
2.7b
Figure 2: The exact match accuracy (y-axis) vs the model scale (x-axis, "b" stands for billion) for Capitalization & Swap tasks (example in Figure 1). Line capital: performance on the simple task of capitalization; swap: on the simple task of swap; composite: in-context examples from simple tasks while test input from the composite task. composite incontext: in-context examples and test input are all from the composite task (example in Table 1).
3 Variability of Compositional Performance
The experiment on Capitalization Swap shows failure cases while existing studies reported some successful composite abilities (Levy et al., 2022; An et al., 2023b). This observation suggests a more refined perspective: LLMs exhibit variable compositional abilities, excelling in certain composite tasks while struggling in others. This section expands our exploration to additional composite tasks to further examine and understand this variability.
We introduce more composite tasks, including linguistic and logical challenges, wrapped as a testing suite. Similar to the Capitalization & Swap experiment, we design composite tasks that compose two simple tasks and evaluate the model in four settings: the two simple tasks, the composite setting, and the composite in-context setting (Table show examples for the latter two). We consider two kinds of task: logical rules and linguistic translation. We first choose two simple tasks and compose them to construct a composite task.
To address concerns about data leakage and the possibility that models encounter similar tasks during pretraining, we opt for synthetic data in this work. While it is challenging to guarantee that test data has never been seen during pretraining, we take significant steps to mitigate this risk. Specifically, we construct our compositional test data using unique syntax and mapping mechanism. This approach substantially shifts the data distribution away from existing web-scale data, making it highly improbable that our test data has been encountered during pretraining. By doing so, we aim to create novel composite tasks that comprehensively evaluate the models' compositional abilities.
Section 3.1 investigates logical tasks and Section 3.2 investigates translation tasks.
We perform experiments to answer the following questions: (Q1) How do LLMs perform in various tasks, where models might perform well some scenarios while failing in others?
(Q2) Does scaling up the model help in general? (Q3) Is the variability in performance
relevant to the nature of tasks? Our experiments provide the following answers: (A1)
A pattern of variable performance is observable across a range of composite tasks. (A2)
Scaling-up helps when the model exhibits compositional ability for certain tasks but may not help when the model initially struggles. (A3) In tasks that involve processing inputs from varied segments or perspectives, especially simpler ones, the model tends to demonstrate compositional capabilities.
4

---

Published as a conference paper at COLM 2024
3.1 Composite Logical Rules
We enhance our suite of logical tasks by introducing a series of straightforward tasks that process either simple words or numerical values, with the output being specific functional transformation of the input. These tasks are detailed in Table 2.
Tasks
Task
Input
Output
Words
(A) Capitalization
apple
APPLE
(B) Swap
bell ford
ford bell
(C) Two Sum
twenty @ eleven
thirty-one
(D) Past Tense
pay
paid
(E) Opposite
Above
Below
Numerical
(F) Plus One
435
(G) Modular
15 @ 6
3
(H) Two Sum Plus One 12
18
Table
This table contains collection of simple logical tasks. The Words category encompasses tasks that modify words at the character or structural level. The Numerical category devoted tasks that involve arithmetic computations performed on numbers.
Composite tasks are created by merging two simple tasks. We conceptualize simple tasks as functions, f(.) and g()) that map inputs to their respective outputs. We identify two dis- tinct approaches to creating composite tasks: (1) Compose by parts: For inputs x, the result is g(y) One exam- ple is (A) + (F) in Table 3. If numerical number is given, will increment by one; the word is given, the letters will be capitalized; if both are given, perform both operations. (2) Compose by steps: Given input x, the result is fg(()). One example (A) + (B) in Table 3. We use customized symbols as function mapping for composing two simple tasks. Examples are in Figure 1 and Table 3. Following existing work, we use exact match accuracy to evaluate the performance since the output for these tasks is usually simple and short.
Tasks
Simple Task
Simple Task
Composite
(A) (B)
input: apple output: APPLE
input farm frog)
input: ( ('bell ford) output: FORD BELL
output: frog farm
(A) (F)
input: 435
input: cow
input: 681 cat
output: 436
output: COW
output: 685 CAT
Table 3: Examples of the two logical composite tasks. Full examples can be found in Appendix
Results. We provide our main results on composite tasks in Table 4. For the composed by parts tasks (A) + (F) and (D) + (F), the models show strong compositional ability: the composite accuracy is high, improves with increasing scale, and eventually reaches similar performance the "gold standard" composite in-context setting, as highlighted in red numbers. We refer to these tasks as "separable composite tasks", which are relatively easy for the model to solve. On the compose-by-step tasks, we observe the models have various performances. For composite tasks with sequential reasoning steps, the models exhibit various performances. For tasks involving capitalization (A) or swap (B), the model has poor performance on small scale (7b or lower) but has increased performance in increased model scale, such as 44% accuracy in (A) (C) and 66% accuracy in (B) (D). One exception is Llamal 165b, which has lower accuracy than smaller-scale model. We conjecture it is due to some unknown inductive bias during the pretraining. On composite steps tasks in- volving the arithmetic calculation of numerical numbers (G) (H), the model has the worst performance, and increasing the model scale does not provide benefits. A key observation is that compose-by-parr tasks are separable compositions where the input can be broken down into two distinct segments. Such tasks are typically straightforward for a model to address. In all experiments, providing composed examples as in-context demonstrations
5

---

Published as a conference paper at COLM 2024
will help the model understand and solve the composite tasks well, such Com. in-context rows all task combinations. We conclude that models fail to compose mechanisms of two simple tasks together; however, given composite examples, models can learn the composed mechanism efficiently. We also experimented with prompt demonstrations and found in- structions provide no direct results; see more experimental details in Appendix B.2. See more experimental results (including Llama3 (Meta, 2024)) and visualizations in Appendix B.3.
Mistral
Llama2
Llamal
Tasks
7B
8x7B
7B
13B
70B
7B
13B
30B
65B
(A) (B)
Capitalization
99
98
99
100
100
98
98
100
100
swap
100
100
100
100
100
100
100
100
100
Compose
16
42
7
37
0
30
16
13
Com. in-context
95
96
96
98
100
66
97
96
98
(A) (C)
twoSum
71
100
72
93
99
62
56
98
99
Capitalization
98
99
100
95
99
97
98
99
99
Compose
8
19
3
23
44
3
3
31
2
Com. in-context
31
65
52
77
100
22
93
69
(A) (F)
Capitalization
97
99
98
77
99
84
96
99
98
PlusOne
100
99
100
100
100
100
100
100
100
Compose
92
96
74
97
57
60
69
99
Com. in-context
99
98
99
100
100
99
99
100
100
(B) + (D)
Swap
100
100
100
100
100
100
100
100
100
Past Tense
97
99
97
100
99
97
98
100
100
Compose
6
12
0
62
57
34
46
5
Com. in-context
92
98
86
95
98
86
95
89
94
(B) + (E)
Swap
100
100
100
100
100
100
100
100
100
Opposite
61
62
58
68
65
51
58
64
63
Compose
0
0
0
Com. in-context
35
32
12
37
37
0
7
9
(D) (F)
Past Tense
100
100
98
100
100
100
100
100
100
Plus One
100
100
100
100
100
99
100
100
100
Compose
71
46
32
80
80
40
44
14
74
Com. in-context
98
100
98
99
100
95
96
98
100
(G) + (H)
Modular
25
22
5
23
43
9
16
29
29
twoSumPlus
38
42
77
90
14
10
40
87
Compose
4
5
0
1
0
0
0
5
Com. in-context
8
13
13
12
11
13
12
Table 4: Results are evaluated composite tasks on various models. The accuracy is in %.
3.2
Composite Linguistic Translation
Inspired by previous work in compositional generalization (An et al., 2023b; Levy et al., 2022; An et al., 2023a; Kim & Linzen, 2020), here we design our composite tasks by formal language translation tasks.
Our translation tasks are mainly derived from semantic parsing task COGS (Kim & Linzen, 2020) and compositional generalization task COFE An al. (2023b). These two datasets contain input as natural English sentences and output a customized grammar (see details Appendix C). We construct two composite tasks centered on compositional generalization utilizing the training datasets to create in-context examples. See details in Appendix C.
chain-ruled sentence following
We the word error rate (WER) the metric. It measures the minimum number of editing operations (deletion, insertion, and substitution) required to transform one sentence into another and is common for speech recognition machine translation evaluations.

---

Published as a conference paper at COLM 2024
(T1) Phrase Recombination with Longer Chain. COFE proposed two compositional gener- alization tasks (Figure 2 in An et al. (2023b)). Phrase Recombination: integrate a prepositional phrase (e.g., "A in B²) into specific grammatical role (e.g., "subject", "object"); Longer Chain: Extend the tail of the logical form in sentences. We see them as simple tasks, and merge them to form composite task: substitute the sentence subject in the Longer Chain task with a prepositional phrase from the Phrase Recombination task. Details and examples are in Table of Appendix C.
(T2) Passive to Active and Object to Subject Transformation. We consider two tasks from Kim & Linzen (2020). Passive to Active: Transitioning sentences from passive active voice. Object to Subject: Changing the same object (a common noun) from objective to subjective. They are merged to form our composite task, where both transformations are applied simultaneously to the input sentence. Details and examples are in Table 8 of Appendix C.
Results. Figure 3 shows that LLMs can handle these composite tasks. The WER on the composite task is decent and improves with increasing model scale, particularly in Llamma2 models. These confirm the composite abilities of the models in these tasks.
Here, we notice that both composite tasks are separable composite tasks. If we break down these sentences into sub-sentences and phrases, the simple task operations occur in different parts or perspectives of the input sentences. So, the results here provide further support for composite abilities on separable composite tasks, where simple tasks that form the composite task are related to inputs from different parts or perspectives.
We also observed the LLM ex- hibits better compositional abil- ity on linguistic tasks than on logical tasks. We conclude nat- ural language inputs can indeed help language models understand concepts better than special sym- bols or code. Natural language provides a richer context, which aligns better with how these mod- els are trained on large text cor- pora. In contrast, logical and nu- merical tasks often rely on more rigid structures, which makes harder for models to generalize without explicit training on such patterns.
Llamal
Llama2
60
60
PhraReco
LongChan
composite
WER
40
40
Incontex
20
76
13b
30b
650
3b
7b
13b
706
Llamal
Llama2
PassisveActive
ObjoctSubject
compposite incontex
WER
4
13b
130
706
Discussion. We observe the ca- pability of models to handle com- posite tasks is significantly influ- enced by the task characteristics. If composite tasks contain sim- ple tasks related to different parts or perspectives of the input, the model will tackle the composite tasks well.
Figure 3: The word error rate (WER) vs the model scale on composite linguistic translation tasks. Dashed lines: simple tasks. Solid lines: composite tasks. Rows: (T1) Phrase Recombination with Longer Chain; (T2) Passive Active and Object Subject Transformation. Columns: different models. Lines: performance in different evaluation settings, e.g,, the two simple tasks, the composit setting, and the composite in-context setting (examples are shown in Appendix C).
One natural explanation is that the model processes the input in some hidden embedding space and de- composes the embedding of the input into different "regions". Here, each region is dedicated to specific types of information and thus related to different tasks, such as word-level modifications, arithmetic calcula- tions, mapping mechanisms, semantic categorization, linguistic acceptability, or sentiment analysis. Then, suppose the two simple tasks correspond to two different task types that relate to separate regions of the embedding. In that case, the model can effectively manage
7

---

Published as a conference paper at COLM 2024
the composite task by addressing each simple task operation within its corresponding region. As the model scales, its ability to handle individual tasks improves, leading to enhanced performance on composite tasks in such scenarios. For separable composite tasks, the inputs are divided into distinct regions and also reflected in embeddings, resulting in the model's high performance. However, when the simple tasks are not separable (e-g., requiring sequential steps in reasoning), their information mixes together, complicating the model's s ability discern and process them distinctly. Such overlap often leads to the model's 's inability to solve the composite task. This intuition is formalized in the following sections in a stylized theoretical setting.
4 Theoretical Analysis
4.1 Problem Setup
Despite the complex nature of non-linearity in transformers in LLMs, we note it is useful to appeal to the simple case of linear models see if there are parallel insights that can help us better understand the phenomenon. In this section, we analyze a linear attention module and aim provide rigorous proof about why LLMs can achieve compositional ability in some simple cases that could shed light on the more intricate behaviors observed in LLMs.
In-context learning. We follow existing work (Akyürek et al., 2023; Garg al., 2022; Mahankali et al., 2023) with slight generalization to K simple tasks. A labeled example is denoted as yx where x E R y RK In simple task k E [K], y has only one non-zero entry (*) In composite task, y can have non-zero entries in dimensions corresponding to the combined simple tasks. The model takes prompt (x.,, XN, XN,NN, X,) as input, which contains N in-context examples ys's and query Xg, and aims predict J, close to the true label Yg for Xq. The prompt is usually stacked into an embedding matrix:
E
X1 X2 ... XN
Xq
E Rd+((N+1) where de d K. In in-context learning, we
y1 1/2
yN
first pretrain the model using training prompts and then evaluate the model with evaluation prompts; see details below.
Pretraining procedure. We have B training data indexed by T, each containing an input prompt (x..1. XT,N, Vr, XT,q) and a corresponding true label yrą.- Consider the following empirical loss: [()) 1 (0) 2 - Ilyr yrgll2 and the population (ŪTA yr&)) )?]
loss (i.e., + oo): L(0)= = E = ATN.NE,NN-..
Evaluation procedure. We now detail how to evaluate the model on downstream composite tasks. We consider the downstream classification task to be a multi-class classification problem, where the output label is K-dimensional vector, and each entry corresponds to a simple binary classification task. For any given simple task k, the binary classification
label is given by sgn(y)))) (+), where sgn is the sign function. Similarly, our prediction is
Fq
(x)
sgn
Fq
The accuracy of composite task is defined as Acco( xg) =
G sgn V/ sgn(y, We denote it as Acca (cc Here we denote the model performance on each task as separate dimension, (e.g.letter capitalization, num- bers increment), and the performance of composite tasks as the aggregation of multiple dimensions.
R
Data. Assume iid. (O,,,),, where A E I is the covariance matrix. Assume y Wx, where W E Rkdd For any simple task [K], its label is the k-th entry of y, which is y
(wo(k), x), where (kk) is the k-th row of W. We assume each task weight (k) iid, N (0,
Linear self-attention networks. These networks are widely studied (Von Oswald et al., 2023; Akyürek et al., 2023; Garg et al., 2022; Zhang et al., 2023b; Shi et al., 2023b). Fol- lowing them, consider the following linear self-attention network with parameters
8

---

Published as a conference paper at COLM 2024
0 (WPV, wKQ): fiS + WPVE. ET The prediction of the model for xg is N
91
the bottom rightmost sub-vector of fisA,(EE) with length K. LLM on composite tasks.
Compositional ability. We now provide a formal definition about compositional ability of an
Definition (Composite cositioilnal Ability), Consider a composite task T that combines tao simple tasks k and 8. Let Sy denote N labeled examples from lask k, and similarly for Sg. Given an xq from composite task T, we say that the model has compositional ability on T if the model has higher accuracy using in-context examples from Sy U than from either single one, i.e. I Accy(Se USg).
max
4.2 Theoretical Results
In this section, we present our theoretical results. We explain the observation in empirical results through the lens of confined supports in input embeddings corresponding to separate subspaces (modeling separable composition). We provide theoretical justification showing that separable composite task composite tasks whose inputs are composed by components adhere to certain conditions where models exhibit satisfactory performance. Models will fail when such conditions are violated. We first introduce the basic setup and definitions.
Disjoint subspaces of simple tasks. Recall that x lies in d-dimensional space where each dimension represents a different characteristic. A simple task may depend only on a subset of these dimensions since its label only depends on few features. Let S [d] represent the dimensions of x. For task k, the output y(8 (W;,x) depends on a subset of dimensions in x. Denote this subset by KK C S and call it the active index set for task k.
In the following, we always assume that the K tasks have disjoint subspaces: for any two tasks k + g, their active index sets K, and G are disjoint, i.e., KK G = Ø. In practice, the dimensions within K could be associated with numerical arithmetic operations, while those in G might pertain to semantic analysis. This illustrates the model's 's approach to address these tasks in their respective subspaces.
We now introduce a mild assumption regarding the distribution of input embeddings.
Assumption 1. Given two disjoint subspaces and G, the covariance matrix A of the input distribution can be segmented into block matrices AKK, AKG, AçK, and AgG, then we assume Umax (AKG) = Umax (AnK) I E for constant e, where o--) denote the singular value of matrix.
Assumption 1 implies that for two separate simple tasks, each associated with its respective feature subspace K and G, the covariance between these two sets of features is bounded by constant value. This is natural assumption when inputs of composite tasks can be decomposed into parts. Suppose we have input embeddings from two tasks: arithmetic computations and semantic analysis. This assumption suggests that the feature subspaces of the input embeddings for two tasks are almost independent.
We now define confined support, which means that each task's input embedding only has support within its feature subspace.
Definition 2 (Confined Support). We say task has confined support if the input only has larger singular values within its active index set. The norm of entries outside the active index set is bounded by a small constant 8.
This definition shows that each simple task only has large values within its corresponding subsets of dimensions of input embeddings. For example, let IK represent the first dj dimensions of an input vector x, and G account for the remaining d2 dimensions, with the total dimension being d d1 + d2. The examples from task k will have input as x xx) where X1 E R Xs, E Rdh ||x < 6. Similarly, the examples from task will have inputs as x = (x6y, X2)
We now present results of the compositional ability under confined support of x. Theorem 1. Consider distinct tasks and g with corresponding examples Sx, Sg. If two tasks have confined support, and Assumption 1 is true, then with high probability, the model has the
9

---

Published as a conference paper at COLM 2024
compositional ability defined in Definition 1. Moreover,
(S))(S)) + Accg(Sg) I Acca (Skug)
Theorem shows the compositional ability of LLMs to handle composite tasks that integrate two simple tasks, which have confined support in their own feature subspace.
An illustrative case involves the tasks Capitalization (A) & Plus One (F) and Past Tense (D) & Plus One (F), as depicted in Table 4. These two simple tasks involve word-level modification and arithmetic operation on separate parts of the input. Due to this separation, each task correlates with specific segment of the input embedding. Therefore, it is observed that these tasks possess confined supports.
We further provide theory illustrating the necessity of the confined supports, we demon- strate that when the confined support is violated, simple tasks begin to show variations (indicated by large singular values) across the entire feature subspace of the input embed- ding. For instance, the composite task of Capitalization (A) & Swap (B), which involves mixed steps in reasoning as shown in Figure 2, shows poor performance of LLMs given both simple tasks' examples as in-context demonstrations. Another example is Modular (G) & Two Sum Plus (H) as shown in the last row of Table 4, where both simple tasks involve multisteps arithmetic operation. These two tasks share the same embedding space support, mixing their variations and causing the model to unable to effectively address the com- posite tasks that integrate them. We further substantiate this observation with Corollary 1, which establishes that when two tasks share overlapping support in the embedding space, scenario can arise where the model fails to demonstrate compositional ability.
Corollary 1. If two tasks do not have confined support, there exists one setting in which we have
Ac))(Sa) ACc)(Sg) Acco(Sk.u)
Corollary demonstrates that a model's s failure to solve tasks with mixed steps reasoning, which contains overlapping input embedding spaces, thereby diminishing the model's ability to solve them when presented together.
We also show the scaling effect: if simple tasks have confined support, the compositional ability of language models will increase as the model scale increases in Theorem in Appendix D.1. We demonstrate this by showing that the model's accuracy on each simple task improves with a larger model scale. We finally provide a case study on confined support for illustration in Appendix D.2. We defer the full proof in Appendix E.
Conclusion
In this work, we presented a distinct pattern in LLMs' behaviors when tackling composite tasks. We observed that if the composite task can be separated into two simple tasks whose inputs are from distinct perspectives, the models exhibit decent compositional ability. Otherwise, LLMs will struggle, and scaling up the model size may not offer improvement. We illustrated this behavior across variety of logical and linguistic challenges. We extended our discussion to the role of input embeddings in affecting model performance, providing a theoretical backup that connects the nature of tasks to how inputs are processed. We anticipate that our research will shed light on the compositional capabilities and reasoning of LLMs, and stimulate further exploration in this direction.
Impact Statements
Our work aims to improve the understanding of in-context learning capabilities of Large Language Models (LLMs) in the handling of composite tasks. Our paper is mostly theoreti- cal in nature, and thus, we foresee no immediate negative ethical impact. We illustrate the empirical behavior of LLMs complex reasoning tasks and provide theoretical explana- tion for it. In the long term, we hope our work may inspire effective algorithm design and better understanding and employment of LLMss.
10

---

Published as a conference paper at COLM 2024
Acknowledgements
The work is partially supported by Air Force Grant FA9550-18-1-0166, the National Science Foundation (NSF) Grants 2008559-IIS, CCF-2046710, and 2023239-DMS.
References
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 Represenlations, 2023.
Ahmed Alajrami, Katerina Margatina, and Nikolaos Aletras. Understanding the role of input token characters in language models: How does information loss affect performance? In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023, URL https://openreviee hee//ForummiddRRR@FF3XX
Shengnan An, Zeqi Lin, Bei Chen, Qiang Fu, Nanning Zheng, and Jian-Guang Lou. Does deep learning learn to abstract? systematic probing framework. In The Eleventh Interna- tional Conference on Learning Representations, 2023a.
Shengnan An, Zeqi Lin, Qiang Fu, Bei Chen, Nanning Zheng, Jian-Guang Lou, and Dongmei Zhang. How do in-context examples affect compositional generalization? Xrv preprint ar arXiv:2305.04885, 2023b.
Anthropic. The claude 3 model family: Opus, sonnet, haiku. //wwww//wwwwcdn.... com/de8ba9bel htt.eeeaabbbbecccccaaaabaaaaaaea c 8857627 (05766677Modelcaaa Saaeee_Carrd_laae Caadddllade_,,. 3.ppf, 2024.
Sanjeev Arora and Anirudh Goyal. A theory for emergence of complex skills in language models. ar Xiv preprint Xiv:23007.15936, 2023.
Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. The reversal curse: Lims trained on" a is b" fail to learn" is a". Xiv preprint ar Xrx::2230.12288, 2023.
Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tenso Technical report, Zenodo, March 2021. If you use this software, please cite using these metadata.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 2020.
Yanda Chen, Ruiqi Zhong, Sheng Zha, George Karypis, and He He. Meta-learning via language model in-context tuning, In Smaranda Muresan, Preslav Nakov, and Aline Villav- icencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 719-730, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653 /t1//11/2100 w112022.acl-oong...
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gauray Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint ar 2rXi::2204.02311, 2022.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction-finetuned language models. ar Xiv preprint arXin:2210. 11416, 2022.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics,2011 2019.
11

---

Published as a conference paper at COLM 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, ar preprint Xiv:2301.002344 2022.
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Lim- its of transformers on compositionality. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. SimCSE: Simple contrastive learning of sentence embeddings. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 2021. Association for Computational Linguistics. doi: 10.18653 /000//112222/1// m222...emnppmmii.55222
Online and Punta Cana, Dominican Republic, November
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? case study of simple function classes. Advances Neural Information Processing Systems, 15:30583-30598, 2022.
Xinyang Geng and Hao Liu. Openllama: An open reproduction of Ilama, May 2023. URL https:/ /tgi:://githut com/openlme wwwmmm-eeerrchppppeeeeeee 1lama.
Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Tianyi Zhou. Fourier circuits in neural networks: Unlocking the potential of large language models in mathematical reasoning and modular arithmetic. Xiv preprint ar 4xXii::402..94469 2024a.
Jiuxiang Gu, Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, and Junze Yin. Conv- basis: new paradigm for efficient attention inference and gradient computation in transformers. Xiv preprint ar XxXi::2405.05219 2024b.
Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Chiwun Yang. Toward infinite- long prefix in transformer. arviv preprint ar Xiv:2406.14036 2024c.
Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Tensor atten- tion training: Provably efficient learning of higher-order transformers. arXiv preprint arXi::240.16611, 2024d.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXio preprint ar arXio:2203.15556, 2022.
Ari Holtzman, Peter West, Vered Shwartz, Yejin Choi, and Luke Zettlemoyer. Surface form competition: Why the highest probability answer isn't always right. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 7038-7051, 2021.
SU Hongjin, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang, Jiayi Xin, Rui Zhang, Mari Ostendorf, Luke Zettlemoyer, Noah A Smith, et al. Selective annotation makes language models better few-shot learners. In The Eleventh International Conference Learning Represenlations, 2023.
Edward Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computa- tional limits of low-rank adaptation (lora) for transformer-based models. Xiv preprint ar arXio:2406.03116, 2024.
12

---

Published as a conference paper at COLM 2024
Zhiqiang Hu, Lei Wang, Yihuai Lan, Wanyu Xu, Ee-Peng Lim, Lidong Bing, Xing Xu, Soujanya Poria, and Roy Lee. LLM-adapters An adapter family for parameter-efficient fine-tuning of large language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, Pp. 5254-527666 Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/ 222033vv12222// eenll-
Jie Huang and Kevin Chen-Chuan Chang- Towards reasoning in large language models: A survey. arviv preprint urXiv:2212.104033, 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. Xiv preprint ar Stt:2001.008611, 2020.
Najoung Kim and Tal Linzen. COGS: A compositional generalization challenge based on semantic interpretation. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Process- ing (EMNLP), pp. 9087-9105, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/vv 1t12220.emmllmmminn.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2021.
Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. arviv preprint ar arXiv:2212.06800) 2022.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing. Association for Computational Linguistics, 2021.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for GPT-3? In Eneko Agirre, Marianna Apidianaki, and Ivan Vulié (eds.), Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, pp. 100- 114, Dublin, Ireland and Online, May 2022. Association for Computational Linguistics. doi: 10.18653 http://1222222eeeeooo1
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXio:1907.11692 2019.
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 Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 8086-8098, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/ / 222022.acl-long.555
Haozheng Luo, Jiahao Yu, Wenxin Zhang, Jialong Li, Jerry Yao-Chieh Hu, Xinyu Xing, and Han Liu. Decoupled alignment for robust plug-and-play adaptation. ar preprint arXiv:2406.01514, 2024.
Avinash Madasu and Shashank Srivastava. What do large language models learn beyond language? In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Findings of the Asso- ciation for Computational Linguistics: EMNLP 2022, pp. 6940-6953, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653 /vl/ URL https::/acclantholoo.. org/2022. findings-emnlp... 516.
2022.findings-eman
Arvind Mahankali, Tatsunori B Hashimoto, and Tengyu Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arv preprint ar Xiv: 00377600366600 2023.
13

---

Published as a conference paper at COLM 2024
Meta. Introducing meta llama 3: The most capable openly available Ilm to date. https: 3/, 2024.
//ai. waa.mmtt...mm mweea.cco/bllleeee http:/looommttttleeeee
Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi. MetalCL: Learning to learn in context. In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2791-2809, Seattle, United States, July 2022a. Association for Computational Linguistics. doi: 10. 18653 /155/v1l// wwt//22.aacllmmiinn222.
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? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2022b.
Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi. Cross-task generalization via natural language crowdsourcing instructions. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics, 2022.
OpenAl. Introducing ChatGPT, https://opemai. www/blogg/caattpp//oooo////oo//a httpss///ooeaa..ccoo///////oooo 2022. Accessed: 2023- 09-10.
OpenAL. GPT-4 technical report. ar Xrv preprint arxivv:3033088774 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 2022.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02117, 2022.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language understanding by generative pre-training OpenAl blog, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2022.
Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, et al. Multitask prompted training enables zero-shot task generalization. In International Conference on Learning Representations, 2022.
Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha. The trade-off between universality and label efficiency of representations from contrastive learning. In International Conference on Learning Representations, 2023a.
Zhenmei Shi, Junyi Wei, Zhuoyan Xu, and Yingyu Liang. Why larger language models do in-context learning differently? In Ro-FoMo:RRousttnes of Few-shot and Zero-shot Learning in Large Foundation Models, 2023b.
Zhenmei Shi, Yifei Ming, Ying Fan, Frederic Sala, and Yingyu Liang. Domain generalization via nuclear norm regularization. In Conference on Parsimony and Learning, pp. 179-201. PMLR, 2024a.
Zhenmei Shi, Junyi Wei, Zhuoyan Xu, and Yingyu Liang. Why larger language models do in-context learning differently? Forty-first International Conference on Machine Learning, 2024b. URL
14

---

Published as a conference paper at COLM 2024
Yiyou Sun, Zhenmei Shi, Yingyu Liang, and Yixuan Li. When and how does known class help discover unknown ones? provable understanding through spectral analysis. In International Conference on Machine Learning, pp. 33014-33043. PMLR, 2023.
Yiyou Sun, Zhenmei Shi, and Yixuan Li. A graph-theoretic framework for understanding open-world semi-supervised learning. Advances in Neural Information Processing Systems, 36, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances neural informa- fion processing systems, 30, 2017.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Joao Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 35151-35174. PMLR, 23-29 Jul 2023,
Jiayu Wang, Yifei Ming, Zhenmei Shi, Vibhav Vineet, Xin Wang, and Neel Joshi. Is a picture worth a thousand words? delving into spatial reasoning for vision language models. arxiv preprint ar arXio:2406.1 14852, 2024.
Xinyi Wang, Wanrong Zhu, Michael Saxon, Mark Steyvers, and William Yang Wang. Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning. In Thirty-seventh Conference Neural Information Processing Systems, 2023a.
Zhen Wang, Rameswar Panda, Leonid Karlinsky, Rogerio Feris, Huan Sun, and Yoon Kim. Multitask prompt tuning enables parameter-efficient transfer learning. In The Eleventh International Conference on Learning Representations, 2023b.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Transactions on Machine Learning Research, 2022.
Jerry Wei, Le Hou, Andrew Kyle Lampinen, Xiangning Chen, Da Huang, Yi Tay, Xinyun Chen, Yifeng Lu, Denny Zhou, Tengyu Ma, and Quoc V Le. Symbol tuning improves in-context learning in language models. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023a.
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, et al. Larger language models do in-context learning differently. arXiv preprint ar Xiv:2303.003446 2023b.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022.
Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Yin Li, and Yingyu Liang. Improving foundation mod- els for few-shot learning via multitask finetuning. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023.
Zhuoyan Xu, Khoi Duc Nguyen, Preeti Mukherjee, Somali Chaterji, Yingyu Liang, and Yin Li. Adainf: Adaptive inference for resource-constraaeed foundation models. In Workshop on Efficient Systems for Foundation Models II @ ICML2024, 2024a. URL https: httpee/wwwweeeeeeoorrrr///////ae
15

---

Published as a conference paper at COLM 2024
Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang. Do large language models have compositional ability? an investigation into limitations and scalability. ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024b. openreview. peet/forrmiid=4XPeFOO0
URL https://
Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Fangzhou Mu, Yin Li, and Yingyu Liang, Towards few- shot adaptation of foundation models via multitask finetuning. In The Twelfth International Conference on Learning Representations, 2024c.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree thoughts: Deliberate problem solving with large language models. In Seirth- Conference Neural Information Processing Systems, 2023.
Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. Compositional exemplars for in-context learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 39818-39833 PMLR, 23-29 Jul 2023.
Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. In The Tweifth International Conference on Learning Represenlations, 2024.
Renrui Zhang, Jiaming Han, Aojun Zhou, Xiangfei Hu, Shilin Yan, Pan Lu, Hongsheng Li, Peng Gao, and Yu Qiao. Llama-adapter: Efficient fine-tuning of language models with zero-init attention. arviv preprint ar drXft:2303.16199, 2023a.
Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. Xiv preprint arXiv:2306.09992, 2023b.
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance language models. In International Conference on Machine Learning, pp. 12697-12706. PMLR, 2021.
16

---

Published as a conference paper at COLM 2024
Appendix
Contents
1 Introduction
1
1.1 Related Work
2 Warm-up: A Failure Case for Composition
3 Variability of Compositional Performance
3.1 Composite Logical Rules
3.2 Composite Linguistic Translation
Theoretical Analysis
4.1
Problem Setup
8
4.2
Theoretical Results
5 Conclusion
10
A Related Work
18
Logical Tasks
19
B.1 Task Setup
19
B.2 Experimental Setup
19
B.3 Results
20
Formal Language Translation Tasks
21
D Theory for Confined Support
23
D.1 Compositional Ability with Model Scale
23
D.2 Case Study of Confined Support
23
E
Deferred Proof
24
E.1
Linear self-attention networks.
24
E.2 Proof of Compositional Ability under Confined Support ................................
24
E.3
Proof of Compositional Ability with Model Scale
28
E.3.1
Accuracy under =
28
E.3.2
Model scale composite tasks
29
17

---

Published as a conference paper at COLM 2024
In this appendix, we provide more related work in Appendix A. We provide more empirical settings and results for logical tasks in Appendix and linguistic translation tasks in Appendix C. We provide theory for confined support and model scalability, along with case study of toy model in Appendix D. We provide full proof in Appendix E.
A Related Work
Large language model. LLMs are often Transformer-based (Vaswani al., 2017) equipped with the enormous size of parameters and pretrained on vast training data. Typical LLMs includes BERT Devlin et al. (2019), PaLM Chowdhery et al. (2022), LLaMATouvron et al. (2023), ChatGPT (OpenAI, 2022), GPT4 (OpenAI, 2023). Pretraining methods include masked language modeling (Devlin et al., 2019; Liu et al., 2019), contrastive learning (Gao et al., 2021; Shi et al., 2023a; Sun et al., 2023; 2024) and auto-regressive pretraining (Radford et al., 2018; 2019). Several works (Madasu & Srivastava, 2022; Alajrami et al., 2023) investi- gate the effects of pretraining on language models. Adapting LLMSs to various downstream tasks has received significant attention, e.g., adaptor (Hu et al., 2022; 2023; Zhang et al., 2023a; Luo et al., 2024), prompt tuning (Lester al., 2021; Li & Liang, 2021; Wei et al., 2023a; Gu et al., 2024c), multitask finetuning (Sanh et al., 2022; Wang et al., 2023b; Xu et al., 2023; 2024c), instruction tuning Chung et al. (2022); Mishra et al. (2022), in-context learning (Min et al., 2022b; Dong et al., 2022; Yao et al., 2023), low-rank adaptation Hu et al. (2022); Zeng & Lee (2024); Hu et al. (2024), reinforcement learning from human feedback (RLHF) (Ouyang et al., 2022) and inference acceleration (Gu et al., 2024b;d; Xu et al., 2024a).
In-context learning. LLM exhibits a remarkable ability for in-context learning (ICL) (Brown et al., 2020), particularly for generative models. Given a sequence of labeled examples and testing example (combined as prompt), the model can construct new predictors for testing examples without further parameter updates. Several empirical studies investigate the behavior of ICLs. Zhao et al. (2021); Holtzman et al. (2021); Lu et al. (2022) formulate the problems and report the sensitivity. Rubin et al. (2022); Liu et al. (2022); Hongjin et al. (2023); Wang et al. (2023a) provide methods to better choose in-context learning examples. Chen et al. (2022); Min et al. (2022a) use meta training with an explicit in-context learning object to boost performance. Theoretically, Xie et al. (2022); Garg et al. (2022) provide a framework to explain the working mechanism of in-context learning. Von Oswald al. (2023); Akyürek et al. (2023); Mahankali et al. (2023); Zhang et al. (2023b), investigating with linear models, show how transformers can represent gradient descent and conduct linear regression. Based on these works, we provide an analysis showing how LLM can exhibit compositional ability in ICL.
Emergence of compositional ability. Scaling law was first proposed by Kaplan et al. (2020) and then followed up by Hoffmann et al. (2022), emphasizing both the scale of models and training data. Sometimes, increasing scale can lead to new behaviors of LLMs, termed emergent abilities (Wei et al., 2022; Arora & Goyal, 2023), such as domain generalization Shi et al. (2024a), math reasoning Gu et al. (2024a), spatial reasoning Wang et al. (2024) and so on. Recent works show LLMs with larger scales have distinct behavior compared to smaller language models (Wei et al., 2023b; Shi et al., 2023b; 2024b). These behaviors can have positive or negative effects on performance. Solving complex tasks and reasoning is an active problem in the Al community Huang & Chang (2022). There is a line of empirical works investigating the compositional ability in linguistic fashion (Kim & Linzen, 2020; Levy et al., 2022; An et al., b023a;b; Xu et al., 2024b). L.MSs are capable of learning abstract reasoning (e.g,, grammar) to perform new tasks when finetuned or given suitable in-context examples. In our work, we include linguistic experiments as part of our testing suite, illustrating LLMs' compositional ability. Ye et al. (2023); Berglund et al. (2023); Dziri et al. (2023) show LLMs will have difficulties solving tasks that require reasoning. Berglund et al. (2023) studies that LLMs trained on "A "A is B" fail to learn "B is A". In our work, we conduct similar experiments showing LLMs will fail on composite if different steps of logical rules are mixed.
18

---

Published as a conference paper at COLM 2024
B Logical Tasks
B.1 Task Setup
We provide a comprehensive explanation of logical composite tasks below. Examples can be seen in Table 5.
(A) (B) Capitalization & Swap, as in Section 2.
(A) + (C) Capitalization & Two Sum. Given words of numerical numbers, represents the operation of capitalizing, represents summing the two numbers.
(G) + (H) Modular & Two Sum Plus. Given numerical numbers, @ represents the operation of taking modular, # represents to sum the two numbers and then plus one.
(A) (F) Capitalization & Plus One. If numerical numbers are given, plus one; if words are given, capitalize the word; both are given, perform both operations.
Among these, (A) + (F) performs the two operations on separable parts of the test inputs (i.e., separable composite task).
Tasks
Simple Task
Simple Task
Composite
(A) (B)
input: apple output APPLE
input: farm frog
imput:
beblll ford
output: frog farm
output: FORD BELL
(A) (C)
input: * (fee) J
input: twenty eleven
input: *( thirty-seven seven @ sixteen
output: FIVE
output: thirty-one
output: FIFTY-THREF
(G) (H)
input: 15 @
input: 12 #
input: 8 @
output:
output:
Ouput: 4
(A) + (F)
input: 435
input: cow
imput: 684 cat output: 685 CAT
output: 436
output: COW
Table 5: Examples of the four logical composite tasks. Note that in (G) (H), the output of the composite task can be either 4 or 11 depending on the order of operations, and we denote both as correct.
We design our logical tasks following the idea of math reasoning and logical rules. The details are shown in Table 5. Our numerical numbers in Table 2 are uniformly randomly chosen from to 1000. The words of numbers task (C) are uniformly randomly chosen from one to one hundred. The words representing objects in Table 2 are uniformly randomly chosen from class names of ImageNet after dividing the phrase (if any) into words. We randomly chose 100 examples in composite testing data in our experiments and replicated the experiments in each setting three times. We fixed the number of in-context examples as K 10 demonstrations.
B.2
Experimental Setup
We use exact match accuracy to evaluate the performance between sequence outputs. The calculation of exact match accuracy divided the number matched words by the length of ground truth.
For Llama models, we use official Llamal and Llama2 models from Meta (Touvron al., 2023), we .lama_33m333 from open OpenLlama (Geng & Liu, 2023). For GPT models, we use GPI2-large from OpenAl (Radford et al., 2019), and we use GPT-neo models for GPT models in other scales from EleutherAT (Black et al., 2021).
We've 'e' experimented with prompt demonstrations. Instructional prompts do help ChatGPT and Claude3 (although we haven't we quantified the accuracy in large-scale experiments), but they offer limited benefits for current open-source models. On the other hand, we did not have prompt tuning any other parameter updates during our evaluation.
19

---

Published as a conference paper at COLM 2024
In our experiments, provided the model with instructions. Here are instructions of Fig- ure I, which were prepended to ICL examples. We refer to our codebase for full instructions and results.
* is a function before words for swapping the position of words, is another function after words for capitalizing letters of words.
B.3 Results
We show a visualization of some logical task accuracy along the increasing to model scale, complement Table 4.
Llamal
Llama2
100
capital
80
twoSum
composite
Acc
60
60
composite incontext
40
40
20
20
0
76
13b
Llamal
Llama2
100
100
mod
80
twoSumPlus
composite
Acc
composite incontext
40
40
20
20
76
13b
30b
65b
3b
7b
13b
70b
Llamal
Llama2
100
100
80
80
ACC
60
60
capital
plusOne
camposite
20
composite incontext
0
0
7b
13b 30b
65b
3b
7b
13b
70b
Figure 4: The accuracy v.s. model scale composite logical rule tasks. Dashed lines: simple tasks. Solid lines: composite tasks. Rows: (A) + (C) Capitalization & Two Sum; (G) + (H) Modular & Two Sum Plus; (A) + (F) Capitalization & Plus One. Columns: different models. Lines: performance in different evaluation settings, i.e., the two simple tasks, the composite setting, and the composite in-context setting (examples for the last two are shown in Table 1).
We also include results for the more recent model Llama3 (Meta, 2024) on the part of our logical tasks to demonstrate the idea. We show results in Table 6.
As shown in the Table 6, for the separable composite tasks which are relatively easy for model to solve (A) (F), the models show strong compositional ability: the composite accuracy is high, improves with increasing scale, and eventually reaches similar performance as the gold standard composite in-context setting. For composite tasks with sequential reasoning steps
20

---

Published as a conference paper at COLM 2024
Llama3
Tasks
8B
70B
(A) (B)
Capitalization
100
100
swap
100
100
Compose
52
72
Com. in-context
97
100
(A) + (F)
Capitalization
100
100
PlusOne
100
100
Compose
88
100
Com. in-context
100
100
Table 6: Results evaluating composite tasks on Llama3. The accuracy is shown in %.
(A) + (B), the model has poor performance on a small scale but has increased performance increased model scale. Providing composed examples in-context demonstrations will help the model understand and solve the composite tasks well.
C Formal Language Translation Tasks
Our translation tasks mainly follow the compositional generalization tasks in COFE (An et al., 2023b). The details can be found in Section 4 in An et al. (2023a). We directly take the source grammar Gs COGS, which mimics the English natural language grammar, and reconstruct the target grammar G: in COGS to be chainn-truuctrre.
We follow the Primitive coverage principle proposed by An et al. (2023b) that primitives contained in each test sample should be fully covered by in-context examples. Here, primi- tives refer to the basic, indivisible elements of expressions, including subjects, objects, and verbs. Note that multiple sets of in-context examples can meet these criteria for each test case. Across all experimental conditions, we maintain consistent number of test instances at 800.
We use the word error rate (WER) as the metric. It measures the differences between sentences. It measures the minimum number of editing operations (deletion, insertion, and substitution) required to transform one sentence into another and is common for speech recognition or machine translation evaluations. The computation of WER is divided by the number of operations by the length of ground truth.
Original Target Grammar
Shrin-Structured Target Grammar
rose (x. (x_1) AND help. theme (x_3,x_1 AND AND agent (x.3,
AND dog (x.6)
HELP (DOG, ROSE, NONE) (CAPTION, NONE, NONE)
"appain (x_1 jaat. agent x_1)
deg ( (x.4) hope agent x.1, Liam AND hope
ccomp 5.5) AND prefer. agent xx_),x4)
HOPE (LIAM, NONE, NONE CCOMP PREFER (DOG, NONE, NONE)
Table 7: Demonstration in An et al. (2023a) showing examples with the original grammar and the new chain-structured grammar.
In formal language tasks, as mentioned in Section 3.2, we change the original target grammar of COGS to be chain-structured. In Table we list some examples with the original target grammar and the new chain-structured grammar.
First, to distinguish the input and output tokens, we capitalize all output tokens (e.g., from "rose" to "ROSE").
Second, we replace the variables (e-g., "x 1") the original grammar with their corresponding terminals (e.g., "ROSE").
Then, we group the terminals of AGENT (e.g, "DOG"), THEME (e.g., "ROSE"), and RECIPIENT with their corresponding terminal of PREDICATE, (e.g., "HELP") and
21

---

Published as a conference paper at COLM 2024
combine this group of terminals in function format, ie., "PREDICATE (AGENT, THEME, RECIPIENT y". If the predicate is not equipped with an agent, theme, recipient in the original grammar, the corresponding new non-terminals (i.e,, AGENT, THEME, and RECIPIENT, respectively) in the function format above will be filled with the terminal NONE (e.g., "HELP (DOG, ROSE, NONE )"). Such function format is the minimum unit of CLAUSE.
Finally, each CLAUSE is concatenated with another CLAUSE by the terminal CCOMP (e.g. "HOPE (LIAM, NONE, NONE ) CCOMP PREFER (DOG, NONE, NONE )*)
Task
In-conlext Example
Testing Example
The book squeezed. SQUEEZE ( NONE, BOOK, NONE
Sophia squeezed the donut.
Passive to Active
SQUELZE ( (SOPHIA, DONUT, NNONE)
Henry liked a cockroach in a box
A cockroach inflated a boy.
Object to Subject
LIKE (HENRY, IN (COCKROACH, BOX)
INFLATE ( COCKROACH,
The book was squeezed.
cockroach squeezed the hedgehog.
Composite Task
SQUEEZE ( (NONE, BOOK, NONE)
Henry liked a cockroach in box
SQUEFZE (
COCKROACH, hedgehog, NONE)
LIKE (HENRY, IN (COCKROACH, BOX)
Table 8: Testing examples of Passive to Active and Object to Subject, red text shows the verbs changing from passive to active voice in simple tasks, and blue text shows the nouns from objective to subjective.
Task
Example
Phrase
Input Output
The baby tray the house screamed.
Recombination
SCREAM ( ON BABY, IN ( (TRAY, HOUSE) )), NONE, NONE
Input
girl valued that Samuel admired that monkey liked that Luna liked that Oliver respected that Savannah hoped that a penguin noticed that Emma noticed that the lawyer noticed that
Longer Chain
cake grew
Output
VALÚE ( GIRL, NONE, NONE) |
CCOMP ADMIRE (SAMUEL. NONE, NONE) )
CCOMP LIKE ( MONKEY, NONE, NONE )
CCOMP
LUNA, NONE,, NONE) !
CCOMP RESPECT (OLIVER, NONE, NONE !
CCOMP HOPE SAVANNAH. NONE, NONE) )
CCOMP NOTICE PENGUIN, NONE, NONE
CCOMP NOTICE EMMA, NONE, NONE,,NOE) NONNE)
CCOMP NOTICE LAWYERR, NONE, NONE)
CCOMP GROW NONE, CAKE, CAKE,NONE)
Input
The baby on a tray in the house valued that Samuel admired that a monkey liked that Luna liked that Oliver respected that Savannah huped that a penguin nuticed that Emuma noticed that the lawyer noticed that cake grew
Composite Task
Output
VALUE (ON( BABY. (TRAY, HOUSE) ), NONE, , NONE))
CCOMP ADMIRE (SAMUEL, NONE, NONE )
CCOMP LIKE MONKEY, NONE, NONE )
CCOMP LIKE LUNA, NONE, NONE )
CCOMP RESPECT (OLIVER, NONE, NONE )
CCOMP HOPE SAVANNAH, NONE, .NONE)
CCOMP NOTICE ( (PENGUIN, NONE, NONE NONE
CCOMP NOTICE EEMM,, NONE, NONE)). !
CCOMP NOTICE (LAWYER, NONE, NONE,NONE) )
CCOMP GROW (NONE, CAKE,NONE,
Table 9: Testing examples of Phrase Recombination and Longer Chain, red text shows the phrase serving as primitives in sentences in simple tasks, and blue text shows the logical structures as sub-sentences in long sentences.
In the following, we we provide detailed explanation of our two composite tasks in translation tasks.
Passive to Active and Object to Subject Transformation. Based on the generalization tasks identified in Kim & Linzen (2020)), we select two distinct challenges for our study as two simple tasks. Passive to Active: Transitioning sentences from Passive to Active voice. Object to Subject: Changing the focus from Object to Subject using common nouns. These
22

---

Published as a conference paper at COLM 2024
tasks serve as the basis for our composite task, where both transformations are applied simultaneously to the same sentence. Examples illustrating this dual transformation can be found in Table 8.
Enhanced Phrase Subject with Longer Chain. COFE proposed two compositional gener- alization tasks (Figure 2 in An et al. (2023b)): Phrase Recombination (PhraReco): integrate prepositional phrase (e.g., "A in B") into a specific grammatical role (e.g., "subject", "ob- ject"); Longer Chain (LongChain); Extend the tail of the logical form in sentences. We consider these two generalization tasks as two simple tasks, merging them to form a composite task. In particular, we substitute the sentence subject in the Longer Chain task with prepositional phrase from the Phrase Recombination task, creating a more complex task structure. Detailed examples of this combined task can be found in Table 9.
D Theory for Confined Support
D.1
Compositional Ability with Model Scale
We then show that if simple tasks have confined support, the compositional ability of language models will increase as the model scale increases. We demonstrate this by showing that the accuracy of the model on each simple task improves with a larger model scale.
Note that the optimal solutions of the parameter matrices are W*PV and W*kQ, We naturally consider that the rank of the parameter matrices W and W*kQ can be seen as a measure of the model's 's scale. A higher rank in these matrices implies that the model can process and store more information, thereby enhancing its capability. We state the following theorem.
Theorem 2. Suppose composite task satisfies confined support. Suppose that we have (I,.,,...., NN. as testing input prompt and the corresponding W where y; = Wx;, As rank r decreases, EW,yy"" [Actg] will have a smaller upper bound.
Theorem 2 shows the expected accuracy of model on composite tasks is subjected lower upper bound as the scale of the model diminishes. This conclusion explains why scaling up helps the performance when the model exhibits compositional ability for certain tasks (those we call "separable composite tasks"). One common characteristic of these tasks is their inputs display confined supports within the embeddings. This is evidenced by the model's decent performance on tasks presented in Table 4 and Figure 3, where inputs are composed of parts.
D.2 Case Study of Confined Support
Our theoretical conclusion shows the model behavior regarding input embedding. It states that the model will have compositional ability if tasks are under confined support of input embedding. To illustrate such theoretical concepts and connect them to empirical observations, we specialize the general conclusion to settings that allow easy interpretation of disjoint. this section, we provide a toy linear case study on classification tasks, showing how confined support on embedding can be decomposed and composite tasks can be solved. We assume 8 = é = 0 in the following simple example.
Consider that there are only two simple tasks for some random objects with the color red and blue and the shape square and round: (1) binary classification based on the color red and blue. (2) binary classification based on shape: circle and square. However, during evaluation, the composite task is a four-class classification, including red circle, red square, blue circle, and blue square.
Then we have two simple tasks K = 2. Consider the input embedding x = (a, b), where
a E R2,b b E R2, d 4. Consider
-1
0
-1 and y = Wx.
0
0
0
Consider the inputs from simple and composite tasks as:
23

---

Published as a conference paper at COLM 2024
Task 1: Red: x1 (1,0,0,0), (1,0) and blue: x2 (0,1,0,0), (-1,0).
Task 2: Circle X3 = (0,0,1,0) J/3 (0,1) and square X4 = (0,0,0,1) y4 (0,
Composed task: red circle X5 = (1,0,1,0), = (1,1), red square X6 = 0,,0,0,1),10 (1, (1, blue circle X7 (0, 1, 1,0 y7 (-1,1) and blue square X8 = (0,1,0,1) ys = (-1
Suppose that we have the optimal solution Og as in Equation (1). Given X 1,, testing input for a red circle example, During the test, we have different predictions given different in-context examples:
1. Given only examples from Task (red and blue): ((x1//1), (X2, (2)1,, we have D4 =
(1, 0) can only classify the color as red.
2. Given only examples from Task 2 (square and circle): [(x4,y4); (Ix, (x)) we have
44 (0, 1) only classify the shape as circle.
3. Given mixture of examples from Task 1 and 2 (red and circle): [(x (x3, ya)l, we have F/ = (1, 1) can classify as red and circle.
We can see that in the final setting, the model shows compositional ability. This gives concrete example for the analysis in Theorem 1.
E Deferred Proof
In this section, we provide formal setting and proof. We first formalize model setup.
E.1 Linear self-attention networks.
These networks are widely studied (Von Oswald et al., 2023; Akyürek et al., 2023; Mahankali et al., 2023; Garg et al., 2022; Zhang et al., 2023b; Shi et al., 2023b). Following them, we consider the following linear self-attention network with parameters (WPV, wkQ):
E E N
fISA, (E) = E W.
The prediction of the model for xg is 8q = ViisA,(E))ee 1)s( KI the bottom rightmost sub-vector of fiSA, E) with length K. Let
WPV (W:P0)
WPV W PV
WXk kk WXO
PPV
E IR (ddK)xx(a+K) wke= = (Wotd) TT
E R ((+)))((2+K))
J
where WPY Rdxa prediction is
WPV E Rdxk and WPy e RKXK, similar for WKQ, Then the 12 21
EE N
WXQ (W TT
y== ((WP))
WPY)
Xg.
(1)
We observe only part of the parameters affect our prediction, so we treat the rest of them as zero in our analysis.
E.2 Proof of Compositional Ability under Confined Support
Here, we provide the proof of our main conclusion regarding Theorem and Corollary 1. Without abuse of notation, we denote Ll WXQ u W.P.
We also add some mild assumptions.
1. The covariance matrix simple tasks will have the same trace to prevent the scale effect of different simple tasks.
24

---

Published as a conference paper at COLM 2024
2. The spectral norm of A is bounded on both sides S ||||| S M.
We first introduce the lemma where the language model only pretrained on one simple task
(K = =1). The pretraining loss L(0) can be refactored, and the solution will have closed form. We further discuss the following.
Lemma E.1 (Lemma 5.3 in Zhang et al. (2023b)). Let == (1 + +)) A tr(A) Raxd,
Lef
2(U,u) = tr u TAAAAA -
UAPUT
Then
min (()) mmn +C= -
U
where C is constant independent with 0. For any global minimum of ?, we have ut = r-1
As the above lemma construction, we denote the optimal solution as WaPV and WakQ, Taking one solution as r-1, , we observe the minimizer of global training loss is of the form:
0Oixd Oy) WVPV = (00za 1
w
00 00
(2)
We then prove our main theory Theorem 1 in Section 4.2, we first re-state below:
Theorem 1. Consider distinct tasks and g with corresponding examples Sk, Sg. If two tasks have confined support, and Assumption 1 is true, then with high probability, the model has the compositional ability as defined in Definition 1. Moreover,
ACco(Sk) + Acco(S;)) S Acco(Skug).
Proof of Theorem 1. WLOG, consider two simple tasks, K = 2. We have (a, where Rd, b Rd= 41 + d2 d. Since only has large values on certain dimensions, it's equivalent to just consider corresponding dimensions in w, i.e., for simple task 1, we have (1) (Wa, Ws6), ) for simple task 2, have w(2) (W5ar W6).
We have x ~ A, where:
AAKK AKG
A
ACK Acc
Task (a,0,z) + (0, , (m) a, 0) + (0, (0,WTTbb))
Task 2: b) TT + (as, 02₂) T, , (0, b) + (w as)
Composed task: (T, T (as, bz) (w) a, w b) + (w (1 w bs).
The form of E is,
A1
AN
aq
E
b
b2
by
by
+ E, E E (d12)
1/1
V/2
VN
where E, represents the values caused by residual dimensions whose entries are bounded by 8.
Following Equation (4.3) in Zhang et al. (2023b), we have
1 N
a:a + agag
Σ N
Di n,b_ + ag b
Σ N
=
a:y;
EE
bia + baag
b,b + bgb
biy.
+8.0 (EET))
i= yia;
VN V:y
25

---

Published as a conference paper at COLM 2024
The WVV can be presented in block matrix
WPy II (W TT (W VV )T
WPy
WPV
WPV
12
WPv
E R (4)
(W
)
WPi
We can apply Lemma E.1 into optimization and recall
woko
(T
all
0g
where r rall E t2)x+ Consider two tasks only related to disjoint dimension of we also have o (AKG) = (Ack) I e. Denote
A ^+
where
A = (AKi ACG ) ,,,-- = (MOX AKG
We apply Lemma E.1 Recall r :=
(1+ 1
A + tr()Ta E Ruxdd we have:
N
1
tr(A)laxa+ + (1+ NN) Ar
r= 1+ N
Â + N
= =I+
where denote r, (1+ x) ^y. We have:
r 1 f TrT 1 OT,)
We denote
T1 0 12) f (
where 11 = (1+ +)+ AKK + N/ tr(()la, E Rdixd and I22 = (1+ AcE + tr(())4 e
d22 Then we have;
r-= T-l ) +A 0
where (AA) < 2mpe.
Then, It's similar to applying Lemma E.1 for pretraining separately into dimensions corre- sponding to different tasks. We solve similarly to Wxo-
We have:
Odixds
Odixd2
0d,x2 x2
I O4zxd1 0zxdi
0d T
Odpx2
ag
fo(E)
Odzxdi
Odzzxdz
02
EE
Od2x2 02x2
bg
Ā
(3)
02xdy
02xdz
1
O2xd2z
0
N
N Σ
T
ag
9g N
Σ V:a:
Σ y.b.T
V.y?
[ 2
by
+ v
(4)
1
1
Σ
y:a:
I ag +
N Σ vib,
I by +
(5)
N
N y (1)
ag r,
aj
N
b T EN y/ (2)bi
+
(6)
26

---

Published as a conference paper at COLM 2024
where Á representing residual matrix whose norm can be bounded by ( Recall N(O, A), then with high probability each entry in will be bounded by Cmêôee for some constant C.
WLOG, write residual vectors 0 vector for simplicity of notation, and only consider residuals for estimations y. Note that we composed example x (a, b)
(w, a, 2 b).
For simplicity, we write a = N Σ v/" a, similarly, tb = 2 E== Vi bj.
(2)
Given in-context examples from one simple task only, consider that we have N examples
from simple task 1, S [{ y; We have @01) = (1aa 0z₂) 202)) = (0,), and
we also have gq = (1g 00) where D = ay TT ا + Cm?de. We have
AC)) = 1(80 -y"""
Similarly, for N in-context examples only from task 2, we have 20 (0a), (0a, (0b), 9q (0, )T, where 0/2) ag T2 ( EN yj bi) Cmrôe. We have (S2) = (2) (2) 24
Then we have Siu2 contains 2N in-context examples from both tasks, specifically, we have N from task and rest from task 2. We have (1) (zta22 0,,,,, w612 (Odt, 10 (2t/22).
0q (0g²) (1) 9g )
(k) Since Yr. sgn( (gn((Wr,,a)) Xr,)),, Viq sgn (o42). following the proof of Lemma E.2, where v1
(1)
+ (1 y,
Acco only concerns the direction of zà and w, we have Acco(S1uz)
Extending the above analysis into any of two simple tasks, when the composite task inte- grates them, we have
ASc + ACc) S Acco(SRug).
We then prove Corollary 1, and we first restate it below.
Corollary 1. If two tasks do not have confined support, there exists one setting in which we have
Acc)(Sa) = Acco(Sg) = AAcc ASco(Sk
Proof of Corollary 1. WLOG, consider two simple tasks, K - 2. We have x = (a, b), where R4 Rdz,d, + d2 d. Consider the setting where also have the same active dimensions, i.e., for simple task 1, we have (1)) (wa, for simple task 2, we have mv(2) = (0, wp).
We have A. Consider tasks are overlapping on all dimensions, where:
Task 1: x (a(1), (0)), (w) (1),, wo b(1)).
Task 2: = (a(2), ((22),(21) y = (w) (2), wo. b(.)).
Composed task: (a,b)T, T, (w) w.Db). b).
27

---

Published as a conference paper at COLM 2024
Similarly, we have:
T ag
g9 =
1
Σ yia;
yib;
T E ycyi
2 bg
(8)
N
1
N
N Σ
yia!
Ii ag Ag +
yibi
12 bq
(9)
N
N
1
a4
1
y
+ T 1 E
vi bi
(10)
N
a
[ Σ N
yi + +b, 1 Σ (2)
(2)
Note that composed example x = (a, b) y y (w] a, 202 b).
When in-context examples are from simple task, we have N examples from simple task 1, S = {(a ,
N and Dg has the same form as Equation (10), similarly, for task 2.
i=1
Suppose $1.2 contains 2N examples from both tasks, where from task 1 and rest from 2a We have
1 ay T - Da bb Σ b 2) ,,,,,,,,,,,,, 2 Vi b,
94
(11)
2N
We finish the proof by checking that Equation (10) and Equation (11) share the same direction.
E.3 Proof of Compositional Ability with Model Scale
Here, we provide the proof of our conclusions in Theorem 2 in Appendix D.1 with respect to model performance and model scale. We first introduce lemma under the K = 1 setting.
E.3.1 Accuracy under K =
When K can give an upper bound of accuracy by A and r. Taking into account the optimal solution in Equation (2), we have the following accuracy lemma.
Lemma E.2. Consider and Xy (O, I4). When N > C, where a constant, we have
Bar AN [Acce] < tr(
Proof of Lemma E.2. Since K 1, the problem reduces the linear regression problem in ICL. Consider the solution form in Lemma E.1, we have
1 N
9q x
Σ
(w xx) Xi
We re-write the form as 0g x have:
xJ(0. w. Following Equation (4.3) in Zhang et al. (2023b), we
N Σ
tb
r
WTr xx) X₁.
N
Recall the definition of Acca and yTA sgn((W,, Frg) ) VTA -gnn (Tt
(k)
(k)
(1k sgn((t0, xtg)),
for any > O, we have:
Ba AN [Acce] = P ((x( wr) > 0, (x))
az0) > 0) + ((Xxr we) < 0, (Xi, ano) < <0)
28

---

Published as a conference paper at COLM 2024
Denote hyperplane orthogonal to Pw and similar to Pa. Recall that Xg is independent of other samples. We have the expectation conditioned on X1, ... XN is the probability that xq falls out of the angle between Pw and Pa. Denote the angle between w and t as f.
As xq is uniform along each direction (uniform distribution or isotropic Gaussian), then the
probability is given Wr, "1, XN- Then Em,,, AN
[Accel = B AN 1
Note that
B xN cos(()] =
20
10 2 |
As, we can choose a, w.l.ogg, we take ||w || = ||:0|| = 1, then we have
E Ewany AN
cos(0)
Ewy Ax [10 (0) |we]l.
Given Wr, we have
E El20 [r]
E [( xi) xi x/|wr]
N
r
Aw,
N
r- AWO
Then, we have
Ew: [(00, wr)] = -(r- (I-IAw wt
-r((T-1A).
Thus, we have
IE co) = =tr(T-1A) A)
(12)
E [Acce] = EE 1 0
(13)
Note that when H, we have cos( Thus, as > where C is constant, we Then we get the statement.
have di and Wr are closed and satisfy π.
E.3.2 Model scale composite tasks
Here, we present proof for model scale and performance on composite tasks. Recall we consider the rank W and W as measure of the model's scale.
We first introduce a lemma about U as an optimal full-rank solution.
Lemma E.3 (Corollary A.2 in Zhang al. (2023b)). The loss function ? in Lemma E.1 satisfies
min ?(U,u) = tr(
UIRRid MER
where U -1 -1, for any non-zero constant minimum solution. We also have
1 r ( 2
?(U,u) u) min UERAsdRER
7(U,u)
(14)
As the scale of the model decreases, the rank of U also reduces, leading to an optimal reduced rank solution Ü. Our findings reveal that this reduced rank can be viewed as truncated form of the full-rank solution U. This implies that smaller-scale models are
29

---

Published as a conference paper at COLM 2024
essentially truncated versions of larger models, maintaining the core structure but with reduced complexity.
Recall A is the covariance matrix, we have eigendecomposstion an orthonormal matrix containing eigenvectors of A and D is a sorted diagonal matrix with non-negative entries containing eigenvalues of A, denoting as D = diag , Ad)), where 1 2 Ad 2 We introduce the lemma below.
QDQ where Q is
Lemma E.4 (Optimal rank-r solution). Recall the loss function in (Lemma E.1). Let
U", U²"
arg min ?(U, u).
UERasd (ank(U)
Then u* cQV* Q", 11 1 where is any non-zero constant and V diag( is satisfying for any S 0, (N+1)A++H(D)) and for any >> r, =
N
Then, we proof the Lemma E.4
Proof of Lemma E.4. Note that, arg min Jank
Z(U,u)
arg min U Rd rank(U)) STRER
2(U,u))
min UCR ,cRR
E(U, 1))
arg min Uddd sank(U)Sracck
((U,u)
min VERRXd,EER
z(U,,)
Thus, we may consider Equation (14) in Lemma E.3 only. On the other hand, we have
1
r
A
tr tr(A)laxd
N
N
1
1 N
QDQT
+
(r(a)
N
=
((1+
1
D tr(D)laxa QT.
We denote D' (1 #) D t tr(D) We can see A Q r Q
and r-1 QT We denote V = = UQ. Since I and A are commutable and the Frobenius norm (F-norm) of a matrix does not change after multiplying it by an orthonormal matrix, have Equation (14)
1
r (uAtUnd AF- ||
Z(U,u)
min ueRdxd
E(U,u)
-
1
| (ullrr ^t |
=
1
D' (V- D
2
=
As WKQ is a matrix whose rank at most r, we have V is also at most rank r. Then, we (V-D'-1)
D''D' D3 (v - D² D F'
denote Va yeg rrnkk diagonal matrix. Denote D' diag( (1, A'1) and V diag((vi...... have
We can see that V* is Then, we
1 oz)).
2
D (V-D"-1) D
(15)
Σ 2 A/2 oz - 1x11 1))² )²
(16)
- (1+ x A + INN
tr(D)
1
17 or
(17)
(1+ 1v) A; +
tr(
N
30

---

Published as a conference paper at COLM 2024
As V* is the minimum rank solution, we have that vy 2 0 for any i [d] and if of > 0,
Denote g(x) = (11 x
we have of
(1+ A+t 00
1 D Jx+
=
x²
It is easy to see that g()) is an increasing function on 00) Now,
N x+ use contradiction to show that V only has non-zero entries in the first diagonal entries. Suppose r, such that o > O, then we must have S such that vj = 0 as V a rank
solution. We find that if we set o7 = 0, (1+ x/ ) mo) and all other values remain the
N
same, Equation (17) will strictly decrease as 8(x) ) is an increasing function on [0, 00). Thus, here is a contradiction. We finish the proof by V = uQ Q.Q.
We then ready to prove the Theorem 2 in Appendix D.1, we first re-state below. Theorem Suppose composite task satisfies confined support. Suppose that we have (x., NN as testing input prompt and the corresponding W where yi Wx;- As rank decreases, IW,,,, Ax [Accg] will have a smaller upper bound.
Proof of Theorem 2. We first prove in simple task setting (K = 1), that the accuracy will have such a conclusion. By Lemma E.2, consider Xy ~ (0, Ia). When > C, where C constant, we have
Ew. AN [Acce] I tr(r-1AA)
Recall Lemma E.4. WLOG, we take c 1. We have
tr(T-1 A) tr (QV* DQ)
N
N+1 -
where second equation comes from Lemma E.4.
Under the confined support setting, the same conclusion holds since Equation (7) in the proof of Theorem 1.
31


Reviews:
[{"review_id": "HBSkRkuTyb", "reviewer": "Reviewer_YRjW", "summary": "This paper studies the capabilities of LLMs in solving compositional reasoning tasks -- a crucial capability towards advancement of understanding capabilities of LLMs . They develop a test suite of composite tasks which differ in various linguistic and logical challenges. \n\nIn the composite logical challenge - they looked at a mix or word and numerical transformations. It was evaluated in 4 settings, the two simple tasks, the composite task with simple tasks as in-context examples and composite task with the composite tasks as in-context example. They find that separable composite tasks, where the simple tasks forming the composite task are distinct, are more straightforward to handle by LLMs, so compose-by-parts tasks seemed easier than compose-by-steps tasks. They also show that composite-in-context examples are easier to handle. \n\nIn the composite linguistic challenge - they evaluated the ability to translate english based on some customized rules. They constructed two tasks and was also evaluated in the same 4 settings. The authors find that LLMs are capable of handling these composite tasks, and their performance improves with increasing model scale. They attribute this success to the fact that these composite tasks are separable. \n\nThey support their results through theoretical analysis too where they say for separable composite tasks can occupy different subspaces for the individual simpler tasks in their input embeddings. They also discuss that larger models, with higher rank matrices, are better at compositional capabilities.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and address the questions below.\n> Composite linguistic capabilities generalized better than the logical ones, could some regressions also be attributed to the models numerical and code understanding capabilities?\n\nYes. We believe natural language inputs can indeed help language models understand concepts better than special symbols or code. Natural language provides a richer context, which aligns better with the way these models are trained on large text corpora.  In contrast, logical and numerical tasks often rely on more rigid structures, which is harder for models to generalize without explicit training on such patterns.\n>  Did the authors try some prompt tuning?\n\nWe've experimented with prompt demonstrations. Instructional prompts do help ChatGPT and Claude3 (although we haven't quantified the accuracy in large-scale experiments), but they offer limited benefits for current open-source models. On the other hand, we did not have prompt tuning or any other parameter updates during our evaluation. \n\nIn our experiments, we provided the model with instructions. Here are instructions of Figure 1, which were prepended to ICL examples.\n```\n* is a function for capitalizing letters, () is another function for swapping the position of 2 words.\n```\nWe will add full instructions to the appendix in further revisions.\n\n> What if some of the composite logical examples were made more natural language.\n\nWe believe it is an interesting direction. Rephrasing the tasks into natural language could leverage the model's strengths in understanding and processing human language, possibly improving its performance in logical reasoning. We will explore it in our future work.\n\n> More commercial and bigger LLMs.\n\nDue to time and budget limits, we added Llama3 results for part of our tasks to demonstrate the idea.\n\n|            | Tasks                | 8B | 70B |\n|------------|----------------------|----|-----|\n| (A) + (B)  | Capitalization       | 100| 100 |\n| -           | Swap                 | 100| 100 |\n| -           | Compose              |  52|  72 |\n| -           | Com. in-context      |  97| 100 |\n| (A) + (F)  | Capitalization      | 100| 100 |\n| -           | PlusOne  | 100| 100 |\n| -           | Compose              |  88|  100 |\n| -           | Com. in-context      |  100| 100 |\n\nLLMs perform better on ``separable composite tasks'' (A)+(F) but poorly on composite tasks with sequential reasoning steps (A) + (B).", "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": "This is a well written paper that attempts to understand a very challenging problem for LLMs, i.e. compositional generalization. \n\nI like how the authors tried to isolate this task and approached it in a systematic approach. They provide support with both empirical and theoretical findings. Although I still have questions around if the tasks have actually been isolated, I believe the paper's findings could stimulate further research into LLM reasoning and compositional generalization.", "reasons_to_reject": "The approach seems like something that could have been done on top of more commercial and bigger LLMs too, like GPT, LLama-3, Claude and Gemini. I would really like to know how these capabilities scale to those models. Specially they seem to be particularly better at numeric transformations and code-understanding.", "questions_to_authors": "1) I notice that the composite linguistic capabilities generalized much better than the logical ones, could some of the regressions also be attributed to some of the models numerical and code understanding cabilities?\n\n2) When the in-context examples are of the actual composite task instead of the simpler tasks the generalization seems to be much better. I wonder if this implies that the way the in-context examples or the prompt instruction given to the model was tuned. Did the authors try some prompt tuning? \n\n3) If some of the composite logical examples were made more natural language - I wonder if these would have changed things. Specially given my point (1). I'd be curious to know if you tried this?", "extra_scores": {}}, {"review_id": "D9lkUNVVaE", "reviewer": "Reviewer_Biao", "summary": "In this paper, the authors investigate the compositional ability of LLMs. They found \"(1) For simpler composite tasks that apply distinct mapping mechanisms to different input segments, the models demonstrate decent compositional ability while scaling up the model enhances this ability; (2) for more complex composite tasks that involve reasoning multiple steps, which each step represent one task, models typically underperform, and scaling up does not generally lead to improvements.\" They offer a theoretical analysis explaining the model when the task handles different input parts separately, the model exhibits compositional capability. \n\nThis paper provides an angle of how LLM does compositional on a toy task. The paper is written and it is novel. This work may benefit the understanding of LLM.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and address the questions below.\n> Need more evidence on more complex tasks for example mathematical reasonings.\n\nWe thank the reviewers for bringing up more tasks and models.\nIn this work, we chose synthetic data to avoid the risk of data leakage. Due to time constraints, we only constructed the tasks presented in the paper. In future work, we plan to expand our task set, particularly focusing on mathematical reasoning. Additionally, we have included results from Llama3 for a more comprehensive evaluation.\nDue to time and budget limits, we added Llama3 results for part of our tasks to demonstrate the idea.\n|            | Tasks                | 8B | 70B |\n|------------|----------------------|----|-----|\n| (A) + (B)  | Capitalization       | 100| 100 |\n| -           | Swap                 | 100| 100 |\n| -           | Compose              |  52|  72 |\n| -           | Com. in-context      |  97| 100 |\n| (A) + (F)  | Capitalization      | 100| 100 |\n| -           | PlusOne  | 100| 100 |\n| -           | Compose              |  88|  100 |\n| -           | Com. in-context      |  100| 100 |\n\nAs shown in the table, for the _separable composite tasks_ which are relatively easy for model to solve _(A) + (F)_, the models show strong compositional ability: the composite accuracy is high, improves with increasing scale, and eventually reaches similar performance as the _gold standard_ composite in-context setting. \n\nFor composite tasks with sequential reasoning steps _(A) + (B)_,  the model has poor performance in small scale but have increased performance in increased model scale. Providing composed examples as in-context demonstrations will help the model understand the composite tasks and solve them well.", "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": "1. Interesting explanation of how LLM do compositional tasks.\n2. Good theoretical analysis.", "reasons_to_reject": "1. Need more evidence on more complex tasks for example mathematical reasonings.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vmdwv5LY5f", "reviewer": "Reviewer_sUH4", "summary": "This paper studies the compositional abilities in language models through in-context learning. In this study, the author introduces simple tasks who are quite intuitive to humans to analyze the reasoning abilities of LMs. The authors test these tasks on several LMs like GPT, Llama and Mistral with varying sizes. The results show that (i) models show some compositionality skills which improved with model sizes. (ii) models struggle on tasks requiring sequential reasoning. In addition to empirical analysis the authors also provide theoretical analysis.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and address the questions below.\n> There is a performance improvement for increased sizes. Do these results correlate to better learning abilities of LMs?\n\nYes. Larger models indeed have better abilities. This has been shown in various related works [1,2]. Large-scale models will generally have better reasoning and learning abilities on various tasks.\n\n\n> Similar trend for all smaller LMs eg: BERT\n\nYes, we conjecture smaller LMs like BERT will also have such a trend (better abilities for larger size). In our work we didn’t verify this since BERT is an encoder model and does not have zero-shot or in-context learning ability. The adaptation of models like BERT will require additional finetuning and is not covered by our work.\n\n\n> Other related works [a,b]\n\nWe thank the reviewer for providing related studies [a,b], and we state the distinctions below. \n\n[a,b] primarily investigate the effects of pretraining on language models. Specifically, [a] examines whether pretraining enables language models to acquire reasoning skills. [b] focuses on how information loss in training token characters affects language model performance. In contrast, our work explores whether language models can learn reasoning through in-context learning without delving into pretraining aspects.\n\nRegarding the experimental models, [a, b] mainly experiment on relatively small models, including the encoder model (BERT, DeBERTa) and LSTM model (ELMO), while our work mainly explores large decoder-based language models, including Mistral, Llama, and open source GPT models (GPT-Neo, GPT-j-6b).\n\nWe thank the reviewer's suggestions and will add these works to our related work in revision. \n\n> Validate the tasks are not present in the training data.\n\nIn this work, we opt for synthetic data to avoid data leakage. While we cannot fully ensure that the test data has not been seen during pretraining, we mitigate this risk by constructing our compositional test data using a unique syntax and mapping mechanism. This approach significantly shifts the data distribution away from existing web-scale data, making it highly improbable that our test data has been encountered during pretraining.\n\nWe hope this explanation helps address your concern.\n\n\n[1] Jerry Wei . et al. Larger language models do in-context learning differently.\n\n[2] Jason Wei . et al. Emergent abilities of large language models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The compositional tasks introduced are quite intuitive and can be used to understand compositional abilities of LMs.\n2. The experiments are interesting and thorough. Authors also provided reasonable theoretical analysis for the behaviors.\n3. The paper is clearly written and easy to follow. I enjoyed reading the paper.", "reasons_to_reject": "None", "questions_to_authors": "1. Given that the tasks are not present in the pretraining data, there is a performance improvement for increased sizes. Do these results correlate to better learning abilities of LMs?\n2.  Do the authors think these results follow similar trend for all smaller LMs eg: BERT?\n3. The authors claim that the tasks are not present in the training data. How do they validate it?\n4. The authors missed a couple of related studies in their papers. How does these studies vary from the current proposed one?\n\na. Madasu, Avinash, and Shashank Srivastava. \"What do Large Language Models Learn beyond Language?.\" In Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 6940-6953. 2022.\n\nb. Alajrami, Ahmed, Katerina Margatina, and Nikolaos Aletras. \"Understanding the Role of Input Token Characters in Language Models: How Does Information Loss Affect Performance?.\" In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 9085-9108. 2023.", "extra_scores": {}}, {"review_id": "ncw1HQqsrV", "reviewer": "Reviewer_EV4J", "summary": "This paper is targeting wheter LLMs have compositional ability through in-context learning setting. The paper get intuition from the observation of whether LLMs can solve comsite task formed by simple tasks and make two important contributions to this research question (1) empirically, they introduce several composite tasks to explore how the nature of the seperate task influence compisitonal performance; (2) theoretically, they introduce a simple yet insightful model to provide analysis. Based on these effort, the authors hightlight the variable performance of LLMs on these tasks and theoretical insights into conditions under which LLMs manage to achieve or fail in compositional ability.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and address the questions below.\n\n> The theoretical section lacks an explanation on the non-linearity in transformers.\nWe acknowledge that our linear self-attention framework is a simplification of actual transformers, but it captures core theoretical insights while remaining practical. We consider each input mapped to a feature vector. For simpler composite tasks that apply mapping to different input segments, the features of the inputs can be divided into disjoint regions. Conversely, the input features become more mixed and inseparable for more complex tasks involving sequential reasoning.\n\nThis simplified framework aligns with recent works [1-4] analyzing in-context learning (ICL) on transformers. It provides a straightforward theoretical construction without compromising the fundamental nature of LLMs.\n\n> Explain ``composite tasks have not been seen by the LLMs during pretraining.”\n\nIn this work, we opt for synthetic data due to the avoidance of data leakage. While we cannot fully ensure that the test data has not been seen during pretraining, we mitigate this risk by constructing our compositional test data using a unique syntax and mapping mechanism. This approach significantly shifts the data distribution away from existing web-scale data, making it highly improbable that our test data has been encountered during pretraining.\n\nWe hope this explanation addresses your concern .\n\n\n> Experimental evidence to validate the application of the proposed theorem.\nWe appreciate the reviewer for highlighting the connection between our theoretical conclusions and the real-world experimental results.\n\nWe have provided an intuitive demonstration showing that inputs from simple tasks can be divided into distinct segments (e.g., (A) + (F)). This corresponds to the separability of the input features learned by the models. In future work, we plan to include visualizations of the learned embeddings of input, illustrating the feature space corresponding to the simple task inputs.\n\n[1] ​​Akyürek, Ekin et al. What learning algorithm is in-context learning? Investigations with linear models.\n\n[2] Oswald, Johannes Von et al. Transformers Learn In-Context by Gradient Descent.\n\n[3] Zhang, Ruiqi et al. Trained Transformers Learn Linear Models In-Context\n\n[4] Mahankali, Arvind et al. One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention.", "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": "1.This research question, compositional ability, is an important topic in the domain of LLMs and is critical for advancing towards more general AI capabilities.\n2.The authors provide clear and insightful empirical experiments of when LLMs succeed or fail on compositional ability across a variety of tasks.\n3.The authors have effectively linked the concept of compositional ability with scaling laws, demonstrating that when a model exhibits confined support for simple tasks, enhancements in model scale can yield superior performance. This finding is particularly useful for practical applications.", "reasons_to_reject": "1.The theoretical section lacks a bridge that connects it effectively with the empirical results presented earlier. For instance, the first sentence, 'Despite the complex nature of non-linearity in transformers in LLMs,' does not seem to directly follow from or reference the empirical findings discussed previously\n2.Given the extensive and diverse nature of pretraining data (most of them are closed source), there exists a possibility that certain components of the testing tasks may have been indirectly encountered by the models during pretraining phase. So I wonder how do authors ensure this in Section 3: \"We make sure composite tasks have not been seen by the LLMs during pretraining.\". This should be explained\n3.The theoretical conclusions presented in the paper are derived based on certain assumptions regarding the models and data. However, the actual scenarios involving LLMs and their pretraining processes are notably complex. So, my question is whether there is any experimental evidence to validate the application of the proposed theorem for guiding real-world LLMs in tackling combinatorial tasks.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the ability of LLMs to perform compositional reasoning through in-context learning.

Scores are positive, one very positive and three lukewarm but still above acceptance threshold.

Strengths:
- well-motivated study of important problem (YRjW, Biao, EV4J)
- the problem is isolated and studied systematiicaly (YRjW)
- theoretical analysis (Biao, EV4J)
- well-motivated tasks (sUH4)
- thorough experiments (sUH4)

Weaknesses:
- no inclusion of large/commerical LLMs, beyond partial inclusion of LLaMa3 during rebuttal (YRjW)
- despite synthetic data, some reviewers voiced concerns about data leakage (e.g. EV4J), which the authors argue is addressed by using a custom syntax
- simplistic theoretical analysis compared to real transformers (EV4J), which the authors is in line with other recent work on ICL

One reviewer asked for more tasks (Biao), though with little specific indication of which these would be.
Decision: Accept