Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability

Authors: zhuoyan  xu
zhenmei  shi
yingyu  liang
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-22 05:17:06

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

Main paper: 
 introduction: 
 In recent years, large language models (LLMs) have revolutionized the natural language processing (NLP) and general AI 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 a 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 a model trained and in-context learned on individual tasks can effectively integrate these skills to tackle combined challenges, which are intuitive and simple for humans. For instance, in Figure 1 , if a 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.Figure 1 : Inconsistent performance in GPT-4. Consider two simple tasks: If a word is followed by an asterisk (*), capitalize the letter. If 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.Compositional ability is an active problem in the AI community and is crucial for advancing Artificial General Intelligence (AGI). Recent studies have made significant contributions to the understanding of this area. Dziri et al. (2023) formulate compositional tasks as computation graphs to quantify each task's complexity level. Power et al. (2022) show that models may develop generalization capabilities when trained extensively, beyond the point of overfitting, highlighting a phenomenon known as "grokking". An et al. (2023b) examines how LLMs acquire abstract reasoning and achieve compositional generalization in a linguistic context through ICL by testing LLMs on tasks that involve translating a formal language with a custom grammar. 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 underlying mechanisms of such behaviors.Inspired by these seminal works, we further evaluate LLMs on a 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 or 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 it "a separable composite task"). The performance of the model depends on how it 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 of LLMs through ICL. Theoretically, we provide analysis on a simple yet insightful model: a 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 us to demonstrate a 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.We briefly summarize related work and provide a detailed discussion in Appendix A.LLMs are often Transformer-based (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 a 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 AI 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., 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 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. 
warm-up: a failure case for composition: 
 Our goal is to understand the behavior of LLMs on compositional reasoning tasks. As a 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 input as the prompt for LLM. We perform experiments across various LLM families, e.g., Llama families (Touvron et al., 2023) and GPTs (Radford et al., 2019; Black et al., 2021) 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 ∼90% accuracy but only achieve around 20% or below on the composite 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 task (which can only be exploited when provided composite in-context examples) and scaling up may not help.  
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 1 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 a 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 in 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.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 a specific functional transformation of the input. These tasks are detailed in Table 2 . 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 distinct approaches to creating composite tasks: (1) Compose by parts: For inputs x, y, the result is f (x), g(y). One example is (A) + (F) in Table 3 . If a numerical number is given, it will increment by one; if 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 f (g(x)). One example is (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.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 as 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 a 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 Llama1-65b, which has lower accuracy than a smaller-scale model. We conjecture it is due to some unknown inductive bias during the pretraining. On composite steps tasks involving 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-part tasks are separable compositions where the input can be broken down into two distinct segments. 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 et al. (2023b) . These two datasets contain input as natural English sentences and output as a chain-ruled sentence following a customized grammar (see details in 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.We use the word error rate (WER) as 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 or machine translation evaluations.(T1) Phrase Recombination with Longer Chain. COFE proposed two compositional generalization tasks (Figure 2 in An et al. ( 2023b)). Phrase Recombination: integrate a prepositional phrase (e.g., "A in B") into a 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 a 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 9 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 to 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.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 exhibits better compositional ability on linguistic tasks than on logical tasks. We conclude 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 how these models are trained on large text corpora. In contrast, logical and numerical tasks often rely on more rigid structures, which makes it harder for models to generalize without explicit training on such patterns.Discussion. We observe the capability of models to handle composite tasks is significantly influenced by the task characteristics. If composite tasks contain simple tasks related to different parts or perspectives of the input, the model will tackle the composite tasks well. One natural explanation is that the model processes the input in some hidden embedding space and decomposes 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 calculations, 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 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 ability to discern and process them distinctly. Such overlap often leads to the model's inability to solve the composite task. This intuition is formalized in the following sections in a stylized theoretical setting. 
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 to 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 to 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 et al., 2022; Mahankali et al., 2023) with slight generalization to K simple tasks. A labeled example is denoted as (x, y) where x ∈ R d , y ∈ R K . In a simple task k ∈ [K], y has only one non-zero entry y (k) . In a composite task, y can have non-zero entries in dimensions corresponding to the combined simple tasks. The model takes a prompt x 1 , y 1 , . . . , x N , y N , x q as input, which contains N in-context examples (x i , y i )'s and a query x q , and aims to predict ŷq close to the true label y q for x q . The prompt is usually stacked into an embedding matrix: N+1) where d e = d + K. In in-context learning, we first pretrain the model using training prompts and then evaluate the model with evaluation prompts; see details below.E := x 1 x 2 . . . x N x q y 1 y 2 . . . y N 0 ∈ R d e ×(Pretraining procedure. We have B training data indexed by τ, each containing an input prompt x τ,1 , y τ,1 , . . . , x τ,N , y τ,N , x τ,q and a corresponding true label y τ,q . Consider the following empirical loss:L(θ) = ∑ K k=1 L k (θ) = 1 2B ∑ B τ=1 ∥ y τ,q -y τ,q ∥ 2 and the population loss (i.e., B → ∞): L(θ) = 1 2 E x τ,1 ,y τ,1 ,••• ,x τ,N ,y τ,N ,x τ,q y τ,q -y τ,q 2 .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 a 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(k) q ), where sgn is the sign function. Similarly, our prediction is y(k) q = sgn y (k) q. The accuracy of a composite task is defined as Accθ (x 1 , . . . , y N , x q ) = 1 K ∑ K k=1 1 sgn y (k) q = sgn(y (k) q ) . We denote it as Acc θ ({x i , y i } N i=1 ).Here we denote the model performance on each task as separate dimension, (e.g.letter capitalization, numbers increment), and the performance of composite tasks as the aggregation of multiple dimensions.i.i.d.∼ N (0, Λ), where Λ ∈ R d×d is the covariance matrix. Assume y = Wx, where W ∈ R K×d . For any simple task k ∈ [K], its label is the k-th entry of y, which is y (k) = ⟨w (k) , x⟩, where w (k) is the k-th row of W. We assume each task weight w (k) i.i.d.∼ N (0, I d ).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) . Following them, we consider the following linear self-attention network with parametersθ = (W PV , W KQ ): f LSA,θ (E) = E + W PV E • E ⊤ W KQ E N .The prediction of the model for x q is ŷq = [ f LSA,θ (E)] (d+1):(d+K),N+1 , the bottom rightmost sub-vector of f LSA,θ (E) with length K.Compositional ability. We now provide a formal definition about compositional ability of an LLM on composite tasks. Definition 1 (Compositional Ability). Consider a composite task T that combines two simple tasks k and g. Let S k denote N labeled examples from task k, and similarly for S g . Given an x q 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 S k ∪ S g than from either single one, i.e. max{Acc θ (S k ), Acc θ (S g )} ≤ Acc θ (S k ∪ S g ).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 a 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 a few features. Let S = [d] represent the dimensions of x. For a task k, the output y (k) = ⟨w k , x⟩ depends on a subset of dimensions in x. Denote this subset by K ⊆ 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., K ∩ 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 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 K and G, the covariance matrix Λ of the input distribution can be segmented into block matrices Λ KK , Λ KG , Λ GK , and Λ GG , then we assume σ max (Λ KG ) = σ max (Λ GK ) ≤ ϵ for constant ϵ, where σ(•) 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 a constant value. This is a 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 a task has confined support if the input x 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 δ.This definition shows that each simple task only has large values within its corresponding subsets of dimensions of input embeddings. For example, let K represent the first d 1 dimensions of an input vector x, and G account for the remaining d 2 dimensions, with the total dimension being d = d 1 + d 2 . The examples from task k will have input as x = (x 1 , x δ 1 ) wherex 1 ∈ R d 1 , x δ 1 ∈ R d 2 , ∥x δ 1 ∥ ≤ δ.Similarly, the examples from task g will have inputs as x = (x δ 2 , x 2 ).We now present our results of the compositional ability under a confined support of x. Theorem 1. Consider distinct tasks k and g with corresponding examples S k , S g . 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, Acc θ (S k ) + Acc θ (S g ) ≤ Acc θ (S k∪g ).Theorem 1 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 of 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 a 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 demonstrate 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 embedding. 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 be unable to effectively address the composite 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, a 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 haveAcc θ (S k ) = Acc θ (S g ) = Acc θ (S k∪g ).Corollary 1 demonstrates that a model'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 2 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 a 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. 
 
 Appendix: 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 theoretical in nature, and thus, we foresee no immediate negative ethical impact. We illustrate the empirical behavior of LLMs on complex reasoning tasks and provide a theoretical explanation for it. In the long term, we hope our work may inspire effective algorithm design and better understanding and employment of LLMs. In this appendix, we provide more related work in Appendix A. We provide more empirical settings and results for logical tasks in Appendix B and linguistic translation tasks in Appendix C. We provide a theory for confined support and model scalability, along with a case study of a toy model in Appendix D. We provide full proof in Appendix E.Large language model. LLMs are often Transformer-based (Vaswani et al., 2017) (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) investigate the effects of pretraining on language models. Adapting LLMs 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 et 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. 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 AI 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., 2023a; b; Xu et al., 2024b) . 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 have difficulties solving tasks that require reasoning. Berglund et al. (2023) studies that LLMs trained on "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.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.• 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 1 to 1000. The words of numbers in 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 as demonstrations.We use exact match accuracy to evaluate the performance between sequence outputs. The calculation of exact match accuracy divided the number of matched words by the length of ground truth.For Llama models, we use official Llama1 and Llama2 models from Meta (Touvron et al., 2023) , we use open llama 3b v2 from open OpenLlama (Geng & Liu, 2023) . For GPT models, we use GPT2-large from OpenAI (Radford et al., 2019) , and we use GPT-neo models for GPT models in other scales from EleutherAI (Black et al., 2021) .We'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.In our experiments, we provided the model with instructions. Here are instructions of Figure 1 , 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 2 words, # is another function after words for capitalizing letters of words.We show a visualization of some logical task accuracy along the increasing to model scale, complement to Table 4 . 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 combine this group of terminals in a function format, i.e., "PREDICATE ( AGENT, THEME, RECIPIENT )". If the predicate is not equipped with an agent, theme, or 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 a function format is the minimum unit of a CLAUSE. In the following, we provide a 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 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 generalization tasks (Figure 2 in An et al. ( 2023b)): Phrase Recombination (PhraReco): integrate a prepositional phrase (e.g., "A in B") into a specific grammatical role (e.g., "subject", "object"); 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 a 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 .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 * PV and W * KQ can be seen as a measure of the model'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 a composite task satisfies confined support. Suppose that we have x 1 , y 1 , . . . , x N , y N , x q as a testing input prompt and the corresponding W where y i = Wx i .As rank r decreases, E W,x 1 ,••• ,x N [Acc θ ] will have a smaller upper bound.Theorem 2 shows the expected accuracy of a model on composite tasks is subjected to a 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 as presented in Table 4 and Figure 3 , where inputs are composed of parts.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. In 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 δ = ϵ = 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), wherea ∈ R 2 , b ∈ R 2 , d = 4. Consider W = 1 -1 0 0 0 0 1 -1 and y = Wx.Consider the inputs from simple and composite tasks as:• Task 1: Red: x 1 = (1, 0, 0, 0), y 1 = (1, 0) and blue: x 2 = (0, 1, 0, 0), y 2 = (-1, 0).• Task 2: Circle x 3 = (0, 0, 1, 0) y 3 = (0, 1) and square x 4 = (0, 0, 0, 1) y 4 = (0, -1).• Composed task: red circle x 5 = (1, 0, 1, 0), y 5 = (1, 1), red square x 6 = (1, 0, 0, 1), y 6 = (1, -1), blue circle x 7 = (0, 1, 1, 0) y 7 = (-1, 1) and blue square x 8 = (0, 1, 0, 1) y 8 = (-1, -1).Suppose that we have the optimal solution ŷq as in Equation (1). Given x q = (1, 0, 1, 0) as a 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 1 (red and blue): [(x 1 , y 1 ), (x 2 , y 2 )], we have y q = (1, 0) can only classify the color as red. 2. Given only examples from Task 2 (square and circle): [(x 4 , y 4 ), (x 3 , y 3 )], we have y q = (0, 1) only classify the shape as a circle.3. Given a mixture of examples from Task 1 and 2 (red and circle): [(x 1 , y 1 ), (x 3 , y 3 )],we have y q = (1, 1) can classify as red and circle.We can see that in the final setting, the model shows compositional ability. This gives a concrete example for the analysis in Theorem 1.In this section, we provide a formal setting and proof. We first formalize our model setup.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 θ = (W PV , W KQ ):f LSA,θ (E) = E + W PV E • E ⊤ W KQ E N .The prediction of the model for x q is ŷq = [ f LSA,θ (E)] (d+1):(d+K),N+1 , the bottom rightmost sub-vector of f LSA,θ (E) with length K. LetW PV = W PV 11 W PV 12 (W PV 21 ) ⊤ W PV 22 ∈ R (d+K)×(d+K) , W KQ = W KQ 11 W KQ 12 (W KQ 21 ) ⊤ W KQ 22 ∈ R (d+K)×(d+K) ,where W PV 11 ∈ R d×d , W PV 12 , W PV 21 ∈ R d×K , and W PV 22 ∈ R K×K ; similar for W KQ . Then the prediction isy q = (W PV 21 ) ⊤ W PV 22 EE ⊤ N W KQ 11 (W KQ 21 ) ⊤ x q .(1)We observe only part of the parameters affect our prediction, so we treat the rest of them as zero in our analysis.Here, we provide the proof of our main conclusion regarding Theorem 1 and Corollary 1.Without abuse of notation, we denote U = W KQ 11 , u = W PV 22 . We also add some mild assumptions.1. The covariance matrix Λ of simple tasks will have the same trace to prevent the scale effect of different simple tasks.2. The spectral norm of Λ is bounded on both sides m ≤ ∥Λ∥ ≤ M.We first introduce the lemma where the language model only pretrained on one simple task (K = 1). The pretraining loss L(θ) can be refactored, and the solution will have a closed form. We further discuss the following.Lemma E.1 (Lemma 5.3 in Zhang et al. (2023b) ).Let Γ := 1 + 1 N Λ + 1 N tr(Λ)I d×d ∈ R d×d . Let l(U, u) = tr 1 2 u 2 ΓΛUΛU ⊤ -uΛ 2 U ⊤ Then min θ L(θ) = min U,u l(U, u) + C = - 1 2 tr[Λ 2 Γ -1 ] + Cwhere C is a constant independent with θ. For any global minimum of l, we have uU = Γ -1 .As the above lemma construction, we denote the optimal solution as W * PV and W * KQ . Taking one solution as U = Γ -1 , u = 1, we observe the minimizer of global training loss is of the form:EQUATIONWe then prove our main theory Theorem 1 in Section 4. ∈ R d 1 , b ∈ R d 2 , d 1 + d 2 = d.Since x 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 w (1) = (w a , w δb ), for simple task 2, we have w (2) = (w δa , w b ).We have x ∼ Λ, where:Λ = Λ KK Λ KG Λ GK Λ GG • Task 1: x = (a, 0 d 2 ) ⊤ + (0, b δ ) ⊤ , y = (w ⊤ a a, 0) + (0, w ⊤ δb b δ ). • Task 2: x = (0 d 1 , b) ⊤ + (a δ , 0 d 2 ) ⊤ , y = (0, w ⊤ b b) + (w ⊤ δa a δ ), 0). • Composed task: x = (a, b) ⊤ + (a δ , b δ ) ⊤ , y = (w ⊤ a a, w ⊤ b b) + (w ⊤ δa a δ , w ⊤ δb b δ ).The form of E is, N+1) .E :=   a 1 a 2 . . . a N a q b 1 b 2 . . . b N b q y 1 y 2 . . . y N 0   + E r ∈ R (d+2)×(where E r represents the values caused by residual dimensions whose entries are bounded by δ.Following Equation (4.3) in Zhang et al. (2023b) , we haveEE ⊤ = 1 N    ∑ N i=1 a i a ⊤ i + a q a ⊤ q ∑ N i=1 a i b ⊤ i + a q b ⊤ q ∑ N i=1 a i y ⊤ i ∑ N i=1 b i a ⊤ i + b q a ⊤ q ∑ N i=1 b i b ⊤ i + b q b ⊤ q ∑ N i=1 b i y ⊤ i ∑ N i=1 y i a ⊤ i ∑ N i=1 y i b ⊤ i ∑ N i=1 y i y ⊤ i    + δ • o(EE ⊤ ).The W PV can be presented in block matrixW PV =   W PV 11 W PV 12 W PV 13 (W PV 21 ) ⊤ W PV 22 W PV 23 (W PV 31 ) ⊤ (W PV 32 ) ⊤ W PV 33   ∈ R (d 1 +d 2 +2)×(d 1 +d 2 +2)We can apply Lemma E.1 into optimization and recallW * KQ = Γ -1 all 0 d 0 ⊤ d 0 .where Γ -1 all ∈ R (d 1 +d 2 )×(d 1 +d 2 ) . Consider two tasks only related to disjoint dimension of x, we also have σ(Λ KG ) = σ(Λ GK ) ≤ ϵ. Denote Λ = Λ + Λ r where Λ = Λ KK Λ GG , Λ r = Λ KG Λ GK We apply Lemma E.1 Recall Γ := 1 + 1 N Λ + 1 N tr(Λ)I d×d ∈ R d×d , we have: Γ = 1 + 1 N Λ + 1 N tr( Λ)I d×d + 1 + 1 N Λ r = Γ + Γ rwhere denote Γ r = 1 + 1 N Λ r . We have:Γ -1 = Γ-1 -Γ-1 Γ r Γ-1 + O(Γ r ) We denote Γ = Γ 1 0 0 Γ 2 ,whereΓ 1 = 1 + 1 N Λ KK + 1 N tr(Λ)I d 1 ∈ R d 1 ×d 1 and Γ 2 = 1 + 1 N Λ GG + 1 N tr(Λ)I d 2 ∈ R d 2 ×d 2 . Then we have; Γ -1 = Γ -1 1 0 0 Γ -1 2 + Awhere σ(A) ≤ 2m 2 ϵ.Then, It's similar to applying Lemma E.1 for pretraining separately into dimensions corresponding to different tasks. We solve similarly to W KQ .We have:EQUATION)where Ã representing residual matrix whose norm can be bounded by O(m 2 ϵδ) Recall x ∼ N(0, Λ), then with high probability each entry in v will be bounded by Cm 2 δϵ for some constant C.WLOG, we write residual vectors as 0 vector for simplicity of notation, and only consider residuals for estimations ŷ. Note that we composed example x = (a, b) ⊤ , y = (w ⊤ a a, w ⊤ b b). For simplicity, we write ŵa = 1 N Γ -1 1 ∑ N i=1 y(1) i a i , similarly, ŵb = 1 N Γ -1 2 ∑ N i=1 y(2) i b i . Given in-context examples from one simple task only, consider that we have N examples from simple task 1, S 1 = {(a i , 0), y i } N i=1 . We have ŵ(1) = ( ŵa , 0 d 2 ), ŵ(2) = (0 d ), and we also have ŷq = ( ŷ(1) q , 0) ⊤ , where ŷ(1)EQUATIONi a i + Cm 2 δϵ. We have Acc θ (S 1 ) = 1 y (1) q =y(1) q 2 .Similarly, for N in-context examples only from task 2, we have ŵ(1) = (0 d ), ŵ(2) = (0 d 1 , ŵb ), ŷq = (0, ŷ(2) q ) ⊤ , where ŷ(2)EQUATIONi b i + Cm 2 δϵ. We have Acc θ (S 2 ) = 1 y (2) q =y(2) q 2 . Then we have S 1∪2 contains 2N in-context examples from both tasks, specifically, we have N from task 1 and rest from task 2. We have ŵ(1) = ( ŵa /2, 0 d 2 ), ŵ(2) = (0 d 1 , ŵb /2), ŷq = ( ŷ(1) q , ŷ(2) q ) ⊤ .Since y (k)τ,q = sgn(⟨w τ , x τ,q ⟩), yτ,q = sgn y (k) τ,q , following the proof of Lemma E.2, where Acc θ only concerns the direction of ŵ and w, we have Acc θ (S 1∪2 ) = 1 y (1) q =y(1) q +1 y(2) q =y(2) q 2 .Extending the above analysis into any of two simple tasks, when the composite task integrates them, we have Acc θ (S k ) + Acc θ (S g ) ≤ Acc θ (S k∪g ).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 θ (S k ) = Acc θ (S g ) = Acc θ (S k∪g ).Proof of Corollary 1. WLOG, consider two simple tasks, K = 2. We have x = (a, b), wherea ∈ R d 1 , b ∈ R d 2 , d 1 + d 2 = d.Consider the setting where w also have the same active dimensions, i.e., for simple task 1, we have w (1) = (w a , 0), for simple task 2, we have w (2) = (0, w b ).We have x ∼ Λ. Consider tasks are overlapping on all dimensions, where:• Task 1: x = (a (1) , b (1) ) ⊤ , y = (w ⊤ a a (1) , w ⊤ b b (1) ).• Task 2: x = (a (2) , b (2) ) ⊤ , y = (w ⊤ a a (2) , w ⊤ b b (2) ).• Composed task: x = (a, b) ⊤ , y = (w ⊤ a a, w ⊤ b b).Denote hyperplane orthogonal to w as P w and similar to P ŵ. Recall that x q is independent of other samples. We have the expectation conditioned on w τ , x 1 , • • • , x N is the probability that x q falls out of the angle between P w and P ŵ. Denote the angle between w and ŵ as θ. As x q is uniform along each direction (uniform distribution or isotropic Gaussian), then theprobability is 1 -| θ| π given w τ , x 1 , • • • , x N . Then E w τ ,x 1 ,••• ,x N [Acc θ ] = E w τ ,x 1 ,••• ,x N 1 -| θ| π . Note that E w τ ,x 1 ,••• ,x N cos( θ) = w τ ∥w τ ∥ 2 , ŵ ∥ ŵ∥ 2 .As, we can choose α, w.l.o.g, we take ∥w τ ∥ = ∥ ŵ∥ = 1, then we haveE w τ ,x 1 ,••• ,x N cos( θ) = E w τ [E x 1 ,••• ,x N [⟨w τ , ŵ⟩ |w τ ]] .Given w τ , we haveE[ ŵ|w τ ] = 1 N Γ -1 N ∑ i=1 E [⟨w τ , x i ⟩ x i |w τ ] = 1 N Γ -1 N ∑ i=1 Λw τ = Γ -1 Λw τ .Then, we haveE w τ [⟨ ŵ, w τ ⟩] = Γ -1 Λw ⊤ τ , w τ = tr(Γ -1 Λ).Thus, we have E cos( θ) = tr(Γ -1 Λ) (12)EQUATION)Note that when θ ≤ π 6 , we have 1 -| θ| π ≤ cos(θ). Thus, as N > C where C is constant, we have ŵ and w τ are closed and satisfy θ ≤ π 6 . Then we get the statement.Here, we present proof for model scale and performance on composite tasks. Recall we consider the rank of W * PV and W * KQ as a measure of the model's scale.We first introduce a lemma about U as an optimal full-rank solution. where U = cΓ -1 , u = 1 c for any non-zero constant c are minimum solution. We also have l(U, u)minEQUATION)As the scale of the model decreases, the rank of U also reduces, leading to an optimal reduced rank solution U. Our findings reveal that this reduced rank U can be viewed as a truncated form of the full-rank solution U. This implies that smaller-scale models are 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

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

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

They 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.
strength_weakness: strength_weakness: 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: questions: 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?

2) 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? 

3) 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?
paper_summary: paper_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. 

This 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.
strength_weakness: strength_weakness: 1. Need more evidence on more complex tasks for example mathematical reasonings.
paper_summary: paper_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.
strength_weakness: strength_weakness: None
questions: questions: 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?
2.  Do the authors think these results follow similar trend for all smaller LMs eg: BERT?
3. The authors claim that the tasks are not present in the training data. How do they validate it?
4. The authors missed a couple of related studies in their papers. How does these studies vary from the current proposed one?

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

b. 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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
2.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
3.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.

Comments: comment: Thank you for your comments. I will keep my score.