Compositional Hardness of Code in Large Language Models - A Probabilistic Perspective

## Abstract

Abstract A common practice in large language model (LLM) usage for complex analytical tasks such as code generation, is to sample a solution for the entire task within the model’s context window. Previous works have shown that subtask decomposition within the model’s context (chain of thought), is beneficial for solving such tasks. In this work, we point a limitation of LLMs’ ability to perform several sub-tasks within the same context window – an in-context hardness of composition, pointing to an advantage for distributing a decomposed problem in a multi-agent system of LLMs. The hardness of composition is quantified by a generation complexity metric, i.e. , the number of LLM generations required to sample at least one correct solution. We find a gap between the generation complexity of solving a compositional problem within the same context relative to distributing it among multiple agents, that increases exponentially with the solution’s length. We prove our results theoretically and demonstrate them empirically.

## 1 Introduction

Large language models (LLMs), based on the transformer archietecture (Vaswani et al., ), have become very efficient problem solvers in many domains, such as broad-scoped question answering,
writing assistance, teaching, and more (Brown, ; Radford et al., ; OpenAI, ; Bubeck et al., ; Nori et al., ; West, ).
Yet their analytical skills, such as coding capabilities, are slow to develop - Chen et al. (); Li et al. (); Alp (); Ridnik et al. () show that even with millions of generations, LLMs may not produce a single correct solution to competitive coding problems. Zhuo et al. (), provide a benchmark for complex coding tasks, and show that SOTA LLMs are not yet capable of following complex instructions to use function calls precisely, with a performance significantly lower than human performance. Dziri et al. () show that LLMs solve compositional tasks such as long multiplication and dynamic programming without developing systematic problem-solving skills.

One way to empower LLMs in analytical tasks, is to use subtask decomposition, otherwise known as chain of thought (COT) - a method in which an LLM breaks down a problem to smaller, more manageable tasks, solves them, and integrates it into a solution. The method has been empirically demonstrated by Wei et al. (), that show reasoning capabilities of language models improve when they are prompted to break down a task. Its efficiency has also been studied theoretically - Wies et al. (); Malach () prove that through the autoregressive nature of language models, problems that cannot be solved directly, can be solved by subtask decomposition, Merrill & Sabharwal () prove that while transformers are limited in the computational problems they can solve directly, using a polynomial number of intermediate steps, they can represent any polynomial time Turing Machine, and Sanford et al. () provide a similar result on expressing more complex arithmetic circuits using more steps of COT.

Yet even with task decomposition, there is a limitation to transformer based models on analytical tasks with COT, due to their limited ability to compose functions - Sanford et al. () show single layer attention can only learn pairwise relations between tokens, limiting the ability to integrate intermediate steps for a fixed model size, and the work of Peng et al. () shows that iterative composition over a domain is limited by the size of the model, even when COT is used. Xu et al. (), show limitations of compositionality on simple linguistic tasks. Thus while theoretically possible, some tasks require an arbitrarily long COT for an LLM to solve.
However, in practice, LLMs are limited in their context length - beyond the constraint of context length during training, Hsieh et al. () introduce the RULER benchmark, for measuring the utility of LLMs on long context tasks. They show that in practice many models can perform tasks only on a much shorter context length than they were trained on. Similarly, Ebrahimi et al. () show empirically that LLMs are limited in random access to tokens within the context, in the bit parity problem. Consequently, even though COT can in theory allow an LLM to solve arbitrarily complex analytical problems, in practice, they will be limited by the effective context length.

A rising approach to remedy this limitation is to solve problems through the use of multi-agent systems, that tackle complex problems through the use of agents, where each agent is an LLM instance that solves a different aspect of the problem. While it has been used for simulating social interactions, (Park et al., ; Li et al., ; Pang et al., ), it has also been shown as an effective tool for analytical problem solving. This can be done by decomposing a large task and distributing the sub-tasks between agents. Ishibashi & Nishimura () use this method for building large code bases and Liu et al. (), use a dynamic LLM-agent network for solving code problems and analytical tasks.

In this work, we theoretically study a compositional hardness of coding problems originating from context processing limitations of LLMs, and the resultant effectiveness of a multi-agent system over a single model instance in composite coding problems. We model a composite coding problem using a pair of simpler coding problems, where the output to the composite problem can be a basic manipulation on the outputs to the pair of problems (*e.g.* composition, product of outputs, concatenation, logical function of the outputs, etc.), such that the solution to the problem can be obtained from concatenating the solutions to the problem pair. The model’s usefulness on a coding task, is quantified by a generation complexity metric (definition 2) - the number of LLM generations required to sample at least one correct solution. The appeal of this metric, is that due to the existence of code testing units, it suffices to turn an LLM into a good program candidate generator and simply output a candidate that is correct (; Thakur et al., ; Luo et al., ). The single LLM instance solves the entire problem, while the multi-agent system is comprised of two agents, each is an LLM instance tasked with solving one of the problems in the pair.
Thus the LLM’s helpfulness in the single instance case is the generation complexity for the composite problem, while in the multi-agent case, it is the product of generation complexities of the pairs of problems, as a correct solution is attained when independently sampling a correct solution to each problem.

We theoretically model an LLM as an autoregressive model, where a solution is sampled token by token, based on the hidden representations. When combining two problems whose solutions are grammatically similar but semantically different (such as different coding problems), we assume this combination injects noise into the model’s representations during solution generation for each sub-problem (assumption 1), which we denote as screening. We show that a compositional problem may have an exponential gap in generation complexity relative to the product of sub problems’ generation complexities (theorem 1), meaning an exponential hardness of composition in-context. Essentially, the model is less capable of solving two problems if they are presented within the same context, than if presented in separate contexts. This points to an advantage of decomposing a problem not only within the same LLM context, but to distribute the problems among multiple agents (*i.e.* solve each sub-task within a different context).
Additionally, this result provides a view of the model’s effective context length through the lens of screening, which is the model’s ability to isolate the relevant context at each decoding step – additional irrelevant context may reduce model’s performance on other tasks within the context window exponentially with length.
We validate our assumptions and results experimentally on Llama 3 by constructing composite code problems.

## 2 Framework

### 2.1 Generation Complexity

We focus on coding problems, meaning each problem is written in natural language and is solved by a function, and the goal is for the model to generate a code that implements it.

###### Definition 1 .

Let $L$ be a programming language. Let $x$ be a natural language description of a problem, that is solved by function $f$, then a computer program $y$ is a correct solution to $x$, if it implements $f$.

We formally define the generation complexity of a of a problem as the inverse success rate of a model to generate a correct solution to the problem:

###### Definition 2 .

For a problem $x$ and a natural language distribution $P$ over $\Sigma^{*}$, the generation complexity of $x$ *w.r.t.* $P$, is:

$$ $N(P,x)=\frac{1}{\sum_{y\in\textit{correct solutions}}P(y|x)}$ (1) $$

Intuitively, the generation complexity is the number of program candidates needed to be sampled from the distribution to get a program that solves the problem.

In this work, we consider simple compositional problems, which are decomposable to two smaller problems, and their concatenated solutions solve the compositional problem. This captures cases such as a composition of two code functions, or simple manipulations on outputs of code functions (*e.g.* concatenation, product, etc.).
For a compositional problem $x$, decomposable to $x_{1},x_{2}$, we quantify the in-context hardness of composition as the ratio of generation complexity to the full problem $N(P,x)$ with the product of generation complexities for the sub-problems $N(P,x_{1})\cdot N(P,x_{2})$. If the latter is much smaller, this points to an advantage for distributing the sub-problems between different instances of an LLM (multiple agents), as it would require fewer generations to sample a correct solution. This defines a compositional hardness of coding problems that originates from context processing limitations, as the compositional problem can be mathematically equivalent to solving both problems, yet seeing them both in the same context reduces the model’s performance on them.

###### Definition 1 .

###### Definition 2 .

### 2.2 Screening in Autoregressive Models

Here we introduce a source of hardness in code composition based on the autoregressive nature of LLMs. Typically, latent representations of the model contain information about the context beyond the next token prediction, *e.g.* the structure of the solution to problems (Ye et al., ). Thus when composing two code problems, we expect the representations during the generation of the second program to contain information about the first program and vice versa, which is grammatically similar (same programming language) but semantically very different. As a result, this additional information creates noise that can harm the generation process.

Formally, we denote by $r^{(L)}(x)$ the model’s last hidden layer representation of the prompt $x$, by $U$, the model’s unembedding matrix (hidden dimension to vocabulary). The logit of the $i$’th token is thus defined as the token’s score before the softmax operation: $\langle r^{(L)}(x),U^{T}e_{i}\rangle$, where $e_{i}$ is the one-hot vector of the token. The probability distribution at each decoding step is the softmax applied to the logits, $P_{LLM}(i|x)=softmax(\langle r^{(L)}(x),U^{T}e_{i}\rangle)$.

In the process of generating a solution to a compositional code problem, $x$, that is implicitly or explicitly decomposable to $x_{1}$ and $x_{2}$, the model will implement a solution to the first part $y_{1}$ and then to the second part $y_{2}$. The sequence is generated based on the hidden representations. Informally, we expect the representation of the solution to the first problem, $y_{1}$, within the compositional problem, $x$, to be a noisy version of the solution’s representation in the non-compositional problem, $x_{1}$:

$$ $r^{(L)}(x\oplus y_{1})=r^{(L)}(x_{1}\oplus y_{1})+noise$ (2) $$

Similarly, the representation of the second problem’s solution, $y_{2}$, in the compositional problem, $x$, is expected to be a noisy version of the solution’s representation in the non-compositional problem, $x_{2}$:

$$ $r^{(L)}(x\oplus y_{1}\oplus y_{2})=r^{(L)}(x_{2}\oplus y_{2})+noise$ (3) $$

Essentially, this means the model attempts to generate the same solutions as in the non-compositional case, but noise may interfere in the process. The projection of this noise onto the dictionary creates noise in the logits during decoding, which can lead the model to make mistakes.

As the two problems $x_{1},x_{2}$ and their solutions $y_{1},y_{2}$ may be different semantically, we do not expect the noise to “push" the model towards the correct solutions more than to incorrect solutions, thus when projected onto the vocabulary, $V$, the noise on the logit of the correct token minus the noise on an incorrect token, $\langle noise,U^{T}e_{i_{\textit{correct next token}}}\rangle-\langle noise,U^
{T}e_{i_{\textit{an incorrect next token}}}\rangle$, should be symmetric on average. Additionally it should be bounded within some range $[-M,+M]$, as it changes the hidden representation to a finite extent. In practice, we only expect this to be true for the high probability tokens, as the vocabulary $V$ is very large, and some low probability tokens may be systematically enhanced. To avoid this issue, we make our assumptions only on the weighted average of the noise, where the weights are given by the probability mass that the model assigns them. This way, low probability tokens with asymmetric noise or large norms receive low weight and are averaged with the noise of other tokens. Denote by $P(i|context)$ the probability assigned to the $i$’th token given the context. We will make our assumptions on the weighted average of the noise on the incorrect token logits minus correct token logits:

$$ $X=\frac{\sum_{i\in V/\{\textit{correct next token}\}}P(i|context)\langle noise ,U^{T}e_{i}-U^{T}e_{i_{\textit{correct next token}}}\rangle}{\sum_{i\in V/\{ \textit{correct next token}\}}P(i|context)}$ (4) $$

###### Assumption 1 .

Denote by $X$ the weighted noise on the logits as defined in equation 4. We assume that at every given decoding step it is a continuous, symmetric random variable and bounded within $[-M,+M]$ for some $M>0$.

In experiment subsection 4.3 we show the noise satisfies these assumptions, with $M\approx 3-4$.

###### Assumption 1 .

### 2.3 Effect of noise on decoding

While the noise onto the logits, $X$, averages to zero, its effect on the decoding process does not. The probability of each token in a decoding step is changed to:

$$ $P(i|context)\rightarrow P^{\prime}(i|context)\leq\frac{P(i|context)}{P(i| context)+(1-P(i|context))e^{X}}$ (5) $$

The denominator, $P(i|context)+(1-P(i|context))e^{X}$ can be thought of as a renormalizing term, which redistributes the probability of the tokens. For $X=0$, the token’s probability does not change, for $X<0$ it increases and for $X>0$ it decreases. Note that if $P(i|context)\in(\epsilon,1-\epsilon)$ for $\epsilon>0$ (the model has finite confidence), then on average, the noise decreases the probability of a correct continuation $P(i|context)$, by a factor of $exp(-\Delta(\epsilon,X))$, where $\Delta$ is the renormalizing term’s mean:

$$ $\Delta(\epsilon,X):=\mathbb{E}_{X}[\log(\epsilon+(1-\epsilon)e^{X})]$ (6) $$

Intuitively $\Delta$ is the average renormalization of the correct token’s probability. In experiment subsection 4.3, we calculate $\Delta(\epsilon,X)$ empirically as a function of $\epsilon$, and find that for $\epsilon=0.1$ for example, $\Delta\approx 0.2$.
The consequence of this, is that on average, most long sequences have their probability reduced by the noise, while few random long sequences have their probability greatly enlarged. Since for long coding problems most sequences are incorrect, the probability of a correct solution getting enlarged is small. We formally show this in the next section. To do so, we will use concentration inequalities, for which we note that:

$$ $|\log(\epsilon+(1-\epsilon)e^{X})|<M$ (7) $$

Thus the renormalizing term’s variance is also bounded:

$$ $\sigma^{2}(\epsilon,X):=Var_{X}[\log(\epsilon+(1-\epsilon)e^{X})]\leq M^{2}$ (8) $$

## 3 Results

Here we show that composing two coding problems can be significantly harder than solving each on its own. A natural quantification of compositional hardness is the gap between generation complexity of the problem’s components and the complete problem. For example, we say that composition is hard if:

$$ $N(P,x)\gg N(P,x_{1})\cdot N(P,x_{2})$ (9) $$

While it is easy if:

$$ $N(P,x)\approx N(P,x_{1})\cdot N(P,x_{2})$ (10) $$

The rational behind this, is that $N(P,x_{1})\cdot N(P,x_{2})$ is the number of attempts required to independently sample a correct solution to $x_{1}$ and to $x_{2}$, while $N(P,x)$ is the number of attempts required to sample a solution to problem that integrates both problems. In an easy composition scenario, the model solves the sub-problems to the best of its abilities as it would if each was solved independently. In a hard composition scenario, seeing both problems combined reduces its performance on each sub-problem, and it is better to use a multi-agent system, by feeding the model the subproblems in different contexts and sampling solutions independently.

As there are typically more incorrect solutions to coding problems than correct ones, the random noise inserted into the logits generally harms the model’s performance. The following lemma quantifies an exponential decrease in the model’s probability of a correct solution to a compositional problem, $P(y_{1}\oplus y_{2}|x)$, relative to the probabilties of the sub-problem solutions $P(y_{1}|x_{1})\cdot P(y_{2}|x_{2})$:

###### Lemma 1 .

Let $\epsilon,\delta\in(0,1)$, and $M>0$. Let $x$ be a compositional problem and $y_{1}\oplus y_{2}$ a solution, with $x_{1}$, $x_{2}$ being the corresponding sub-problems. Suppose that the noise injected to the logits as defined in equation 4, satisfies assumption 1 - for all decoding steps, it is continuous, symmetric and bounded within $[-M,+M]$. Suppose further that the probability assigned to the correct token at each decoding step is bounded within $[\epsilon,1-\epsilon]$. Denote by $\Delta:=\mathbb{E}_{X}[\log(\epsilon+(1-\epsilon)e^{X})]$ and $\sigma^{2}:=Var_{X}[\log(\epsilon+(1-\epsilon)e^{X})]$ the renormalizing term’s mean and variance (as defined in equations 6 and 8 respectively). Under the assumption, $\Delta,\sigma$ are strictly positive, and
if $|y_{1}|+|y_{2}|>\frac{M^{2}}{\sigma^{2}\cdot h(\frac{3\Delta\cdot M}{4\sigma^{
2}})}\ln\frac{1}{\delta}$, where $h(x)=(x+1)\ln(1+x)-x>0$, we have with
probability of at least $1-\delta$ that:

$$ $P(y_{1}\oplus y_{2}|x)\leq P(y_{1}|x_{1})\cdot P(y_{2}|x_{2})e^{-\frac{\Delta \cdot(|y_{1}|+|y_{2}|)}{4}}$ (11) $$

Where $P(y|x)$ is the probability assigned to $y$ by the model, given context $x$.

The proof is presented in appendix A. The intuition behind this result is that as there are typically more incorrect choices to make when generating code, random noise usually reduces the probability for sequences with finite confidence. Thus most sequences get their probability reduced, while very few random sequences get a large increase, and these are usually not correct solutions.

The assumption on bounded probability for the correct token $[\epsilon,1-\epsilon]$ implies we are considering solutions where the model has high but limited confidence in each decoding step. While LLMs are often very confident in “obvious" next steps (line break, etc.), in practice, during generation, nucleus sampling is commonly used, where sampling only occurs if the model is not overly confident. *e.g.* with $p=0.95$, if a token’s probability $P$, is larger than $0.95$, then the probability is rounded $1$. Thus when considering probabilities of sequences, it suffices to look only at decoding steps where the model is not too confident, hence we can consider $\epsilon\approx 0.05$.

In subsection 4.3, we see empirically that for $\epsilon=0.1$, $\Delta\approx 0.2,\sigma\approx 1.5,M\approx 4$, making $\frac{M^{2}}{\sigma^{2}\cdot h(\frac{3\Delta\cdot M}{4\sigma^{2}})}\approx 200$, thus for solutions with length $>200$ tokens, the results apply.

In practice, there may be multiple solutions to the same problem, *e.g.* multiple implementations of the same function. So it is necessary to take all of them into account when considering the generation complexity.
With this taken into account using a union bound, we obtain the following result of an exponential gap in generation complexity between a composition of problems and the sub-problems, indicating a compositional hardness that is exponential in the solution’s length:

###### Theorem 1 .

Let $\epsilon,\delta\in(0,1)$, and $N,M>0$. Let $x$ be a compositional problem, with $x_{1}$, $x_{2}$ being the corresponding sub-problems. Denote by $L_{1},L_{2}$ the minimal solution length to $x_{1},x_{2}$ respectively, and the total number of solutions to $x$ by $N$. Define $\Delta,\sigma$, the renormalizing term’s mean and variance (as defined in equations 6 and 8 respectively) and by $M$ the bound on the logit noise (assumption 1). Under the assumptions of lemma 1, they are strictly positive, $\Delta,\sigma,M>0$, and if the minimal solution length $L_{1}+L_{2}$, satisfies $L_{1}+L_{2}>\frac{M^{2}}{\sigma^{2}\cdot h(\frac{3\Delta\cdot M}{4\sigma^{2}})
}\ln\frac{N}{\delta}$, where $h(x)=(x+1)\ln(1+x)-x>0$, we have with probability of at least $1-\delta$ that the generation complexity (definition 2) satisfies:

$$ $N(P,x)\geq N(P,x_{1})N(P,x_{2})\cdot e^{\frac{\Delta\cdot(L_{1}+L_{2})}{4}}$ (12) $$

The proof is presented in appendix B. We see that longer problems become harder to solve due to the noise injected into the decoding steps by previously generated tokens.
This shows that a model that fully utilizes its context in decoding (*i.e.* the next token probability distribution is explicitly a function of all the previous tokens), can have a hard time mixing different concepts due to the screening effect. This result implies that for long coding problems, it is more beneficial to distribute sub-tasks between different instances of the LLM, and not expose it to the full context. Additionally, this result provides a view of the model’s effective context length through the lens of screening – additional irrelevant context may reduce model’s performance on other tasks within the context window exponentially with length.
The intuition to the result is that there are more incorrect solutions than correct ones, so the random noise usually reduces their total probability mass.

We note that for the union bound of theorem 1 to hold, we need the number of solutions to be bounded by an exponential in the length of the solution, $L_{1}+L_{2}$:

$$ $N<\delta\cdot exp\left((L_{1}+L_{2})\cdot\frac{\sigma^{2}}{M^{2}}h\left(\frac{ 3\Delta\cdot M}{4\sigma^{2}}\right)\right)$ (13) $$

Typically, we expect the number of solutions to a problem to grow exponentially with the length of the shortest solution, $y$:

$$ $N\sim exp(c\cdot|y|)$ (14) $$

As each line of code can be implemented slightly differently, lines may be interchanged, different variable names, etc. Still, the exponential’s coefficient is expected to be small as most sequences are not correct solutions to the problem due to the constraints between the tokens (*e.g.*, once a variable name is chosen, it is fixed throughout the solution).
With the empirical values calculated in subsection 4.3, we see empirically that the coefficient of the exponential number of solutions is $\approx 0.005$, thus for a solution of length $L_{1}+L_{2}=1,600$ tokens, we have $N<\delta\cdot exp(8)=3,000\cdot\delta$ solutions.

###### Lemma 1 .

###### Theorem 1 .

## 4 Experiments

In this subsection we test the assumptions and results of our theoretical part. We create simple compositional coding problems with pairs of problems from the humaneval benchmark (Chen et al., ) and code contests dataset (Li et al., ). First, we show the results of theorem 1, stating that composition is typically harder than independently solving the subproblems. Then, we show explicit indications for the exponential length dependence of compositional hardness, by comparing probabilities of solutions with/without composition, as theoretically suggested in lemma 1. Finally, we look at our assumption 1 on the noise inserted into the logits of the second problem, and observe that it is indeed large enough to interfere with the decoding process (assumption 1). The experiments were performed on Llama-3-8B-Instruct (Dubey et al., ). For additional experimental details, see appendix C.

### 4.1 Generation Complexity Results

Here we test the actual generation complexity of an LLM to different problems corresponding to scenarios from our theoretical results.
As proposed in the theoretical section, an LLM may be able to solve two problems with low generation complexity, but their composition might take a significantly larger generation complexity if the model was not explicitly trained on such a task. To test this, we built a set of composite problems based on the Human Eval benchmark (Chen et al., ) and code contests dataset (Li et al., ).

To create composite problems, we took pairs of problems from Human Eval and code contests, and created from each a problem whose solution requires to explicitly solve both problems. Additionally, for harder problems, we created compositions of problems from code contests dataset.
The three templates used were:

- •
(Human Eval) Problem 1 has a True/False output, Problem 2 has an arbitrary output. Composition is to solve problem 1, then if its output is true, print the second problems’ output, otherwise, print “-1":
- •
(Human Eval) Problem 1 and Problem 2 have an integer output. Composition is to solve both and print the product of their outputs.
- •
(Code Contests) Problem 1 and problem 2 are problems from the dataset. Composition is to read the inputs sequentially and print the outputs sequentially.

We denote the composite problem of $x_{1}$ and $x_{2}$ as $x_{1}\oplus x_{2}$. While these compositions may appear artificial, their purpose is to demonstrate the “mental load" on the model during composition, which leads to the result of theorem 1. For each problem we sampled 200 solutions and evaluated the generation complexity as the inverse of percentage of correct solutions.

Figure 1 shows the cumulative distribution function (CDF) of the compositional hardness - the value along the $y$ axis is the CDF of $\frac{N(P,x)}{N(P,x_{1})N(P,x_{2})}$, *i.e.*  percentage of compositional problems, in which $\frac{N(P,x)}{N(P,x_{1})N(P,x_{2})}$ is smaller than a given value. For example, with $a=5$, the corresponding value on the $y$ axis, is the percentage of problems in which composition requires up to $\times 5$ more generations relative to solving independently. As can be seen, for most of the problems, composition generation complexity is larger than the product of generation complexities of the components (up to factors of $10-20$).

Figure: Figure 1: Cumulative distribution function for the ratio of generation complexity using composition, $N(P,x)$, to product of generation complexities for the standalone problems, $N(P,x_{1})\cdot N(P,x_{2})$ (corresponding to the multi-agent generation complexity). The x axis denotes values for the ratio of generation numbers required to solve the problem in the two cases (composition vs multi-agent), the y axis is the percentage of problems in which the ratio is no larger than this value (*e.g.* for $a=5$, the y axis value is the percentage of problems where composition requires up to $\times 5$ more samples than the multi-agent case). (a) For the human eval composition. As can be seen in most of the cases, composition requires twice more samples, and for some problems 10 times more samples. (b) For the code contests composition. As can be seen the majority of problems have a factor of at least 5, and some up to 20.
Refer to caption: x4.png

As seen in theorem 1, we have:

$$ $N(P,x_{1}\oplus x_{2})\gg N(P,x_{1})N(P,x_{2})$ (15) $$

Furthermore, we see that in code contests, where the problems typically have longer solutions (few hundreds of tokens), and the problems are harder thus the model is less certain, the compositional hardness is much larger.

Assuming one only has access to end-to-end verifier of the composite problem, it is more advantageous to generate independently for each problem then to generate for the composite problem, giving the advantage to a multi-agent system over a single LLM instance.

### 4.2 Exponential Length Dependence of Compositional Hardness

Here, we used the same compositions as in the previous subsection, and measured the difference in probabilities of correct solutions with vs without composition as a function of the number of tokens in the solution.
The “correct" solutions were taken as the canonical solutions of the dataset, as they are “neutral" in the sense that solutions generated by the model with/without composition may have different styles, and measuring the probability of these generated sequences may create an artificial bias in favor of one of the two.

As suggested by lemma 1, we expect to see on average:

$$ $\log\frac{P(y_{1}|x_{1})P(y_{2}|x_{2})}{P(y_{1}\oplus y_{2}|x)}\geq\frac{ \Delta}{4}\cdot(|y_{1}|+|y_{2}|)$ (16) $$

Meaning that the log ratio of correct solutions without/with composition increases linearly with length.
As can be seen in figure 2, an exponential increase in probability of the correct solution is observed without composition relative to with composition, as a function of length of the code.
As the y axis is plotted in the log domain, the linear curve approximates $\Delta/4$, which takes a value of $\approx 0.05$. This means a decrease of $e^{-1}$ in success rate for every 20 tokens. This matches the typical increase in generation complexity seen in figure 1. In practice, $\Delta$ is likely larger for some compositions, as the average is over many sequences, yet still has high fluctuations.

While measuring probability of sequences not generated by the model is less reliable than the above experiment in 4.1, which shows the gap of compositional hardness in a real sampling scenario, this approach is useful to qualitatively show how in certain compositional scenarios, the probability of sequences are exponentially lower than non-compositional scenarios, as a function of code length, which is expected to hold during generation.

Figure: Figure 2: Ratio of correct solution probability with vs without composition. An exponential trend is observed as a function of length.
Refer to caption: x6.png

### 4.3 Assumptions

Here we look at our assumption of noise inserted into the logits (assumption 1).

#### Noise distribution:

Using the same compositions as before, we measure the change to the logits of correct tokens with vs without composition. As in the theoretical assumption, we subtract this with the mean change in the logits of the incorrect tokens:

$$ $X=\frac{\sum_{i\in incorrect}P_{i}\langle noise,U^{T}e_{i}-U^{T}e_{correct} \rangle}{\sum_{i\in incorrect}P_{i}}$ (17) $$

We calculate this over different sequences. As can be seen in figure 3, the change in logits creates a noise that is symmetric, bounded, $X<M\approx 4$, and has finite absolute deviation $E[|X|]>0$, in accordance with assumption 1.

Figure: Figure 3: Change in logits of correct tokens minus incorrect tokens due to composition.
Refer to caption: x7.png

#### Estimation of Δ ⁢ ( ϵ , X ) Δ italic-ϵ 𝑋 \Delta(\epsilon,X) roman_Δ ( italic_ϵ , italic_X ) :

To estimate $\Delta(\epsilon,X)$ we approximate the noise as a Gaussian with mean 0 and try two values standard deviation $\sigma=1$ and $\sigma=2$, then calculate $\Delta(\epsilon,X)\approx mean_{\{X_{i}\}}[\epsilon+(1-\epsilon)e^{X}]$. The values are plotted in figure 4, match the estimation of $\Delta\approx 0.05-0.2$ from the above subsection.

Figure: Figure 4: Numerical Estimation of $\Delta(\epsilon,X)$.
Refer to caption: x8.png

#### Estimation of σ ⁢ ( ϵ , X ) 𝜎 italic-ϵ 𝑋 \sigma(\epsilon,X) italic_σ ( italic_ϵ , italic_X ) :

Similarly, we estimate $\sigma(\epsilon,X)$. The values are plotted in figure 5, showing typical values of $\sigma\approx 1-2$.

Figure: Figure 5: Numerical Estimation of $\sigma(\epsilon,X)$.
Refer to caption: x9.png

## 5 Discussion

In this work, we point a limitation of LLMs’ ability to perform several sub-tasks within the same context window – an in-context hardness of composition, pointing to an advantage for distributing a decomposed problem in a multi-agent system of LLMs over using a single LLM instance. The hardness of composition is quantified by the generation complexity metric, *i.e.*, the number of LLM generations required to sample at least one correct solution. We found an exponential gap between generation complexity of solving a composition problem within the same context relative to distributing it among multiple agents. This is attributed to the transformer’s nature of using all tokens in the context simultaneously for decoding, which inserts noise into generated sequences, caused from mixing in sub-tasks’ latent representations (screening). Consequently, even if a model has the ability to perform two tasks, it may not be able to perform them both within the same context, in agreement with empirical work of Zhuo et al. (), showing SOTA LLMs still perform poorly on complex coding tasks.
This provides a view of the model’s effective context length through the lens of screening, which is the model’s ability to isolate the relevant context at each decoding step – additional irrelevant context may reduce model’s performance on other tasks within the context window exponentially with length.
Lastly, we point that while advantegous, the use of multi-agent systems may introduce new challenges, such as coherence between agents, which we leave for future work.

## Acknowledgments

We thank Yoav Levine and Noam Wies for fruitful discussions. This research was supported by the ERC (European Research Council) and the ISF (Israel Science Foundation).

## Appendix A Proof of Lemma 1

We start by proving the following lemma:

###### Lemma 2 .

Let $p\in(0,1)$ and $X$ a random variable over real numbers. Denote by:
$\Delta\left(p,X\right)=E\left[\log{\left(p+\left(1-p\right)e^{X}\right)}\right]$.
Claim: For a continuous symmetric random variable, X, we have $\Delta\left(p,X\right)>0$. Furthermore, if $p\in(\epsilon,1-\epsilon)$, then $\Delta(p,X)>\Delta(\epsilon,X)=\Delta(1-\epsilon,X)$

Proof:

Denote by $\rho(X)$ the density function of $X$, then:

$$ $E\left[\log{\left(p+\left(1-p\right)e^{X}\right)}\right]=\int_{-\infty}^{0}{ \log{\left(p+\left(1-p\right)e^{x}\right)}\rho(x)}+\int_{0}^{\infty}{\log{ \left(p+\left(1-p\right)e^{x}\right)}\rho(x)}=$ (18) $$

Switching sign of the integration variable in the second term:

$$ $=\int_{0}^{\infty}{\log{\left(p+\left(1-p\right)e^{-x}\right)}\rho(-x)}+\int_{ 0}^{\infty}{\log{\left(p+\left(1-p\right)e^{x}\right)}\rho(x)}=$ (19) $$

Using the symmetry condition on $X$:

$$ $=\int_{0}^{\infty}{\log{\left(p+\left(1-p\right)e^{-x}\right)}\rho(x)}+\int_{0 }^{\infty}{\log{\left(p+\left(1-p\right)e^{x}\right)}\rho(x)}=$ (20) $$

$$ $=\int_{0}^{\infty}{\left(\log{\left(p+\left(1-p\right)e^{-x}\right)}+\log{ \left(p+\left(1-p\right)e^{x}\right)}\right)\rho(x)}=$ (21) $$

Again, applying the symmetry of $X$:

$$ $=\frac{1}{2}\int_{-\infty}^{\infty}\left(\log{\left(p+\left(1-p\right)e^{-x} \right)}+\log{\left(p+\left(1-p\right)e^{x}\right)}\right)\rho\left(x\right)$ (22) $$

The integrand is positive:

$$ $\mathrm{log}(p+(1-p)e^{x})+\mathrm{log}(p+(1-p)e^{-x})\mathrm{=}$ (23) $$

$$ $=\log{(p^{2}+\left(1-p\right)^{2}+p\left(1-p\right)\left(e^{x}+e^{-x}\right)}=$ (24) $$

$$ $\log{(1+}p\left(1-p\right)\left(e^{x}+e^{-x}-2\right))\$ (25) $$

For $x=0$, the argument inside the log equals $1$, otherwise, the argument inside the log is always larger than $1$, since $e^{x}+e^{-x}-2>0$.
Hence the integrand is positive everywhere except in $x=0$, meaning the integral is positive for any continuous symmetric $X$.
Thus, for any $p$ the expectation value is positive.

$$ $E\left[\log{\left(p+\left(1-p\right)e^{X}\right)}\right]=\Delta\left(p,X\right )>0$ (26) $$

Furthermore it is symmetric around $p=1/2$, and monotonic for $p\rightarrow 0$ and $p\rightarrow 1$:

$$ $\mathrm{log}(p+(1-p)e^{x})+\mathrm{log}(p+(1-p)e^{-x})\mathrm{=}$ (27) $$

$$ $=\log{(p^{2}+\left(1-p\right)^{2}+p\left(1-p\right)\left(e^{x}+e^{-x}\right)}=$ (28) $$

$$ $\log{(1+}p\left(1-p\right)\left(e^{x}+e^{-x}-2\right))\$ (29) $$

As can be seen, it is monotonic with $p(1-p)$, and if $p\in(\epsilon,1-\epsilon)$, it is minimal for $p=\epsilon,1-\epsilon$.

###### Lemma 2 .

#### Proof of Main Lemma:

We now move to the proof of the main lemma. We show the exponential growth with the length of the solution to the second problem, $y_{2}$ (the proof for the exponential dependence on $y_{1}$ is identical). Let us look at the probability that the model assigns the $n$’th token in the sequence $y_{2}$ in the compositional problem. It is given by the softmax on the projections of the final hidden layer representation on the vocabulary given the context:

$$ $P\left(y_{2}\left[n\right]\middle|x\oplus y_{1}\oplus y_{2}\left[:n\right] \right)=\frac{e^{\left\langle r^{(L)}\left(x\oplus y_{1}\oplus y_{2}\left[:n \right]\right),U^{T}e_{y_{2}\left[n\right]}\right\rangle}}{e^{\left\langle r^{ (L)}\left(x\oplus y_{1}\oplus y_{2}\left[:n\right]\right),U^{T}e_{y_{2}\left[n \right]}\right\rangle}+\Sigma_{i\in\left[V\right]}e^{\left\langle r^{(L)}\left (x\oplus y_{1}\oplus y_{2}\left[:n\right]\right),U^{T}e_{i}\right\rangle}}$ (30) $$

According to assumption 1, $\left\langle r^{(L)}\left(x\oplus y_{1}\oplus y_{2}\left[:n\right]\right),U^{T
}e_{i}\right\rangle=\left\langle r^{(L)}\left(x_{2}\oplus y_{2}\left[:n\right]
\right),U^{T}e_{i}\right\rangle+X_{i}$, meaning the model is receiving a noisy version of the representation to the problem it is trying to solve, where $X_{i}$ is the noise onto the $i$’th token.

$$ $=\frac{P\left(y_{2}\left[n\right]\middle|x\oplus y_{1}\oplus y_{2}\left[:n \right]\right)e^{X_{y_{2}\left[n\right]}}}{P\left(y_{2}\left[n\right]\middle|x \oplus y_{1}\oplus y_{2}\left[:n\right]\right)e^{X_{y_{2}\left[n\right]}}+ \Sigma_{i\in\left[V\right]}P\left(i\middle|x\oplus y_{1}\oplus y_{2}\left[:n \right]\right)e^{X_{i}}}$ (31) $$

For brevity, denote $P_{0}=P\left(y_{2}\left[n\right]\middle|x\oplus y_{1}\oplus y_{2}\left[:n
\right]\right)$, and $P_{i}=P\left(i\middle|x\oplus y_{1}\oplus y_{2}\left[:n\right]\right)$.

$$ $=\frac{P_{0}e^{X_{0}}}{P_{0}e^{X_{0}}+\Sigma_{i\in\left[V\right]/{0}}P_{i}e^{X _{i}}}$ (32) $$

Now, using the AMGM inequality:

$$ $\leq\frac{P_{0}e^{X_{0}}}{P_{0}e^{X_{0}}+\left(1-P_{0}\right)e^{\Sigma_{i\in \left[V\right]}\frac{P_{i}X_{i}}{1-P_{0}}}}=\frac{P_{0}}{P_{0}+\left(1-P_{0} \right)e^{\Sigma_{i\in\left[V\right]}\frac{P_{i}X_{i}}{1-P_{0}}-X_{0}}}$ (33) $$

Now, denote $X=\Sigma_{i\in\left[V\right]}\frac{P_{i}(X_{i}-X_{0})}{1-P_{0}}$, according to assumption 1, it is a symmetric, continuous random variable, bounded between $[-M,+M]$. Rewriting the above as:

$$ $=P_{0}e^{\log(P_{0}+(1-P_{0})e^{X})}$ (34) $$

So the correct token probability with composition $P_{0}^{\prime}$ is decreased the factor in the exponent $\rightarrow P_{0}e^{\log(P_{0}+(1-P_{0})e^{X})}$, relative to the probability without composition, $P_{0}$. For a full sequence, we apply the probability chain rule and obtain the following:

$$ $P\left(y_{2}\middle|x\oplus y_{1}\right)=P\left(y_{2}\right|x_{2})e^{-\Sigma_{ i=1}^{\left|y_{2}\right|}\log{\left(P_{0}^{i}+\left(1-P_{0}^{i}\right)e^{X_{i} }\right)}}$ (35) $$

Where $P_{0}^{i}$ is the probability of the correct token in the $i$’th step without composition.
Now, because $E_{X_{i}}\left[\log{\left(P_{0}+\left(1-P_{0}\right)e^{X_{i}}\right)}\right]=
\Delta\left(P_{0},X_{i}\right)>0$, from the above lemma. We get a sum of random variables with mean that is larger than zero. We will use a concentration inequality to bound it.

We start with bounding the random variables:

$$ $\log{\left(P_{0}+\left(1-P_{0}\right)e^{X_{i}}\right)}<\log{\left(P_{0}+\left( 1-P_{0}\right)e^{M}\right)}\leq M$ (36) $$

$$ $\log{\left(P_{0}+\left(1-P_{0}\right)e^{X_{i}}\right)}>\log{\left(P_{0}+\left( 1-P_{0}\right)e^{-M}\right)}\geq-M$ (37) $$

Also notice that since $P_{0}\in(\epsilon,1-\epsilon)$, the above lemma implies:

$$ $\Delta\left(P_{0},X_{i}\right)>\Delta\left(\epsilon,X_{i}\right)$ (38) $$

Thus from linearity of the expectation value:

$$ $E\left[\Sigma_{i=1}^{\left|y_{2}\right|}\log{\left(P_{0}+\left(1-P_{0}\right)e ^{X_{i}}\right)}\right]>\left|y_{2}\right|\cdot\Delta(\epsilon,X)$ (39) $$

We can then apply Bennet’s inequality:

$$ $P\left(\Sigma_{i=1}^{\left|y_{2}\right|}\log{\left(P_{0}+\left(1-P_{0}\right)e ^{X_{i}}\right)}>\frac{1}{4}\left|y_{2}\right|\cdot\Delta(\epsilon,X)\right) \geq=1-\exp{\left(-\frac{L\sigma^{2}}{M^{2}}h{\left(\frac{3\Delta M}{4\sigma^{ 2}}\right)}\right)}$ (40) $$

Where $\sigma^{2}$ is the variance of each summand, $\log{\left(P_{0}+\left(1-P_{0}\right)e^{X_{i}}\right)}$ (which is positive, since the variable is continuous), $M$ is its bound, $\Delta=\Delta(\epsilon,X)$ is a lower bound for the expectation value, and $h(x)=(1+x)\log(1+x)-x$.
Thus for:

$$ $\left|y_{2}\right|>\frac{M^{2}}{\sigma^{2}h(\frac{3\Delta M}{4\sigma^{2}})} \cdot\ln{\frac{1}{\delta}}$ (41) $$

We obtain the with probability of at least $1-\delta$ that:

$$ $P\left(y_{2}\middle|x\oplus y_{1}\right)<P\left(y_{2}\right|x_{2})e^{-\frac{ \Delta}{4}|y_{2}|}$ (42) $$

Using the same idea for $y_{1}$, we obtain:

$$ $P\left(y_{1}\middle|x\right)<P\left(y_{1}\right|x_{1})e^{-\frac{\Delta}{4}|y_{ 1}|}$ (43) $$

Thus together, if $\left|y_{1}\right|+\left|y_{2}\right|>\frac{M^{2}}{\sigma^{2}h(\frac{3\Delta M
}{4\sigma^{2}})}\cdot\ln{\frac{1}{\delta}}$, we have with probability $1-\delta$ that:

$$ $P\left(y_{1}\oplus y_{2}\middle|x\right)<P\left(y_{1}\right|x_{1})P\left(y_{2} \right|x_{2})e^{-\frac{\Delta}{4}(|y_{1}|+|y_{2}|)}$ (44) $$

## Appendix B Proof of theorem 1

Now, suppose there are $N$ solutions to the problem, then we need to use a union bound. We get the result of the lemma 1 over all sequences with probability:

$$ $\left(1-\exp{\left(-\frac{L\sigma^{2}}{M^{2}}h{\left(\frac{3\Delta M}{4\sigma^ {2}}\right)}\right)}\right)^{N}\geq 1-N\exp{\left(-\frac{L\sigma^{2}}{M^{2}}h{ \left(\frac{3\Delta M}{4\sigma^{2}}\right)}\right)}$ (45) $$

Require this to equal:

$$ $=1-\delta$ (46) $$

Thus for:

$$ $\left|y_{1}\right|+\left|y_{2}\right|>\frac{M^{2}}{\sigma^{2}h(\frac{3\Delta M }{4\sigma^{2}})}\cdot\ln{\frac{N}{\delta}}$ (47) $$

We obtain with probability of at least $1-\delta$ that all solutions satisfy the result of lemma 1. If the minimal solution length is $L_{1}+L_{2}$, for all solutions to satisfy the inequality, we require:

$$ $L_{1}+L_{2}>\frac{M^{2}}{\sigma^{2}h(\frac{3\Delta M}{4\sigma^{2}})}\cdot\ln{ \frac{N}{\delta}}$ (48) $$

Thus we have with probability $1-\delta$ that:

$$ $N(P,x)=\frac{1}{\sum_{y_{1},y_{2}\in\textit{correct solutions}}P(y_{1}\oplus y _{2}|x)}\geq~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{} ~{}~{}~{}~{}~{}~{}~{}$ (49) $$

$$ $~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\geq\frac{1}{\sum_{y_{1},y_{2}\in\textit{correct solutions}}P(y_{1}|x_{1})P(y_{2}|x_{2})}e^{\frac{\Delta}{4}(L_{1}+L_{2})}=$ (50) $$

$$ $=\frac{1}{\sum_{y_{1}\in\textit{correct solutions for $x_{1}$}}P(y_{1}|x_{1}) \sum_{y_{1}\in\textit{correct solutions for $x_{2}$}}P(y_{2}|x_{2})}e^{\frac{ \Delta}{4}(L_{1}+L_{2})}$ (51) $$

$$ $=N(P,x_{1})N(P,x_{2})e^{\frac{\Delta}{4}(L_{1}+L_{2})}$ (52) $$

## Appendix C Experimental Details

#### Composite Problem Construction:

The composite problems were created by pairs of problems in the formats described in subsection 4.1. Our results were based on 50 such composite problems for each experiment. The non-composite problems from human eval and code contests were also tested independently, and we used problems with standalone pass rates $\geq 0.1$, in order to avoid sampling too many solutions in the composite problems (which would typically have accuracy smaller than the product of pass rates of the standalone problems).

#### Code Generation:

For each problem, code was generated by sampling at $T=1$, and nucleus sampling with $p=0.95$.

#### Evaluation of Generated Code:

To evaluate the correctness of code generated by the LLM in the experiment described in subsection 4.1, we tested the code on the test cases provided in the datasets.

#### Format of synthetic solutions to composite problems:

In subsections 4.2 (exponential length dependence) and 4.3 (assumptions), we performed a forward pass of the problem+solution in a scenario with and without composition in order to compare the logits in the two cases. To create correct solutions to the problems, that are “neutral" (not more likely to be generated by the LLM in a compositional problem than in the standalone case, or vice versa), we created solutions to the composite problems from the standalone problem solutions provided in the datasets. Typically, the model attempted to solve the problems sequentially, either by building functions to solve each problem in the pair, and apply the function sequentially, or by writing the explicit solutions one after the other. We used both templates to create solutions for these experiments.

#### Sequence Probability Calculation:

In subsection 4.2, we measured the probability of solutions to problems with composition vs without composition. As explained above, we used to templates for the calculation that are similar to the model’s generations (solution in a functional form, where a function is defined for each problem, and in a non-functional form, where the solutions to the problems are written sequentially). In both templates we observed similar trends. In order to avoid an artificial difference between composition and non-composition in the sequence probabilities due to the templates, we measured the probability of sequences after the first few tokens, so that the model has “time" to adjust to the format in both cases (composition and non-composition), and only measure the probabilities of the actual solution. We did this for both solutions of the compositional problem, for a more fair comparison between composition and non-composition sequence probabilities.

#### Logit Noise Experiment:

In subsection 4.3, we used the templates as mentioned in the above on the sequence probability calculation. We extracted the of the logits of the solutions both in the case of composition and non-composition, and calculated the logit noise as defined in subsection 4.3 and equation 4.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. Where does the functional shape of eq (5) come from? Why this shape and not another?
2. Can you answer all the questions above about the proof of Lemma 1?
3. In Fig 1 and Fig 2, exactly which of the two Human Eval composition is being used? What happens if you take consider the other?
4. What can you say about the relative compexity of different combination mechanisms and its impact on the noise term of Eq (2-3)?
soundness: 2
strengths: The authors tackle a problem which is of high importance from the perspective of implementation and of explainable AI. Problem decomposition can be both an efficient method (as evidenced in this paper), and one that is easier to interpret (since part of the explaining is being done by the decomposition).

The methodology is elegant, providing what feels like the right level of abstraction to be able to make meaningful and general statements about systems as complex as LLMs. The formal statements are plausible (although there are some issues in the proofs, see below). The empirical evidence, particularly Fig 1 and Fig 2 is convincing (if rather limited).
summary: This submission presents a probabilistic model of compositional problem solving by LLMs (eq (2-3)). Based on this model, the authors present a theoretical result showing that solving the composition (for various notions of "composition") of two problems can be exponentially more complex (for a probabilistic notion of complexity related to the expected number of samples to reach success) than solving the two problems separately. The authors then present some empirical evidence justiying the assumptions behind their model as well as their main theoretical result.
weaknesses: * Conceptually, a more detailed examination of the notion of composition would probably be beneficial. Some "compositions" are clearly harder than others. Concatenating a function with itself is trivial, composing a function with itself typically isn't. Therefore, the "noise" term which forms the (very elegant) technical heart of the paper cannot be expected to be as agnostic to the composition mechanism as suggested in this work. This aspect of problem composition is not addressed at all.

* Technically, I'm not 100% convinced by the proof of Lemma 1. At Eq (40), Bennet's inequality is used. It says that \\(P(\sum_{i=1}^n X_i>t)\leq \exp\left(-\frac{n\sigma^2}{M^2}h\left(\frac{Mt}{n\sigma^2}\right)\right)\\). Here, the inequality is reversed and uses a term \\(1-\exp()\\). This is incompatible with the definition, and would be the lower-bound for \\(P(\sum_{i=1}^n X_i\leq t)\\). Also, when pattern-matching this definition with Eq (40), I could not find a reason/meaning for the term \\(L\\) and for the factor \\(3\\). So Eq (40) looks suspicious. The statement before Eq (42) is also suspicious (and I'm not talking about the typo). What is the probability of \\(1-\delta\\) associated with? Is it the probability of sampling \\( |y_2| \\) noise terms such that (42) holds? Can you explain how you go from Eq (35) to Eq (42)?

* Section 4.3 does not really serve any purpose, the noise model is completely ad-hoc (centered Gaussian with standard deviation \\(\sigma=1,2\\) and so it doesn't tell us anything.

* Specific comments:

- Def 1: Is \\(f\\) written in \\(L\\)? What exactly is the meaning of \\(y\\) implementing \\(f\\)?
- Def 2: What is \\(\Sigma\\)? Just below, "sampled from the distribution" -> the conditional distribution \\(P(\cdot\mid x)\\)?
- Eq (4) and throughout the document: I think you're writing the quotient symbol / when you mean the set difference \\(\setminus \\) symbol.
- Eq (13)-(14): use \\(\exp\\) instead of \\(exp\\)
- l292: \\(\delta \exp(8)\approx 3000\delta\\)
- l485: \\(\Delta \approx 0.05 - 0.2\\) looks like a subtraction, also it seems to contradict the earlier point that \\(\Delta\approx 0.2\\).
- Eq (22): this step is not necessary
- Eq (30): What is \\(V\\)? Where does it come from?
- Eq (31): I think all instances of \\(x\oplus y_1\oplus y_2\\) here should be \\(x_2\oplus y_2\\)
- Eq (33): I would find this step much clearer if you invoked Jensen's Inequality which does the job exactly.
- Eq (34): Minus sign missing before \\(\log\\)

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 1
questions: Can you explain the significance of your theoretical results in informal terms?

Can you better justify the experimental set-up and the decisions you made there?

Do you have a clear hypothesis to explain your experimental results?
soundness: 2
strengths: Very compelling and natural problem with realworld implications.
summary: The paper addresses a natural problem: how good are LLMs at solving programming tasks when those tasks require compositions of subsolutions? Given the rise of co-pilots, this is extremely relevant. The paper presents a simple mathematical model of the problem, and some experimental results.

While I think the problem is natural, I found the realisation in the present paper to be weak. The formal model is poorly presented (Definition 1 is effectively empty, the theoretical results are laboured and their significance very unclear). The experimental results section is the most interesting, but I found it somewhat contrived and unconvincing. 

Overall, my sense is this is an interesting direction, but its a rather strange paper overall.
weaknesses: Theoretical results are poorly presented and laboured. Significance not clear.

Experimental results seem contrived and the experimental setup seems a little arbitrary. Significance of these results not clear.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: I look forward to reading other reviewers feedback and the authors responses and am open to adjust my scores based on more info.

Line 0: Have other papers done similar analysis say for multi-step tasks in general and this is a special case of that?

Line 147: If the LLM is effectively using attention to mask out the irrelevant parts in the lower layers, the higher layers could have noise=0.  So could the noise at L could be 0 in theory for a properly trained LLM for compositional problems?

Line 161: If x1 and x2 are similar – like “x1 = write a function that takes a number and returns the number + 7, x2 = write a function that takes a number and returns the number + 9” – then couldn’t their be a few shot effect that improves the prob of correct y2 given x1, y1, or even correct y1 given very similar x1,x2.  Does the semantic difference/similarities of x1,x2 impact how much worse the prob of a correct answer to both together is than the product of getting a correct answer to each question in isolation?

Line 304: Llama-3-8B Instruct for the model – do the results hold for other models?  Does this work show any interesting scaling law effects for larger Llama models?  Or on the best OpenAI or Anthropic models?  On larger models I would expect composition wouldn’t be as big of an impact, there would be less noise and sort of predictably less noise as the model size scales up. I could imagine that for problems of a certain complexity there is a number of problems that can be solved together before they interfere and start significantly degrading combined performance compared to solving each alone, and that number that can be solved together is proportional to model size in some way.
soundness: 2
strengths: I like the presentation and analysis done on the problem with COT causing each step to be less likely to succeed if not done in an agentic way, intuitively most folks know completing multi-step tasks successfully has an exponentially small chance of success if all steps must succeed. But this work emphasizes that the prob of success is even worse than that – the multiple steps compete for attention and processing capacity in the layers – reducing chance of success even more – as the chance of each step succeeding is reduced by seeing all the other steps in the context.

I thought the paper was well written, and had lots of references to interesting relevant papers

I agree with the premise of the paper overall, the agent approach does seem intuitively better to eliminate distractions of irrelevant tokens  and empirically that is shown in the experiments in the paper.  I wish there was more empirical data for larger models showing how larger models maybe handle more problems in some scaling law sort of way.
summary: The paper explains how if an LM is solving 2 coding problems (x1 and x2) at the same time, and since the generation of a solutions is probabilistic based on the temperature, then assuming the probability of finding a correct solution for solving each x1,x2 separately is P1,P2 (i.e. prob of the LLM solving x1 alone in 1 roll-out is P1). Then to solve x1 and x2 coding problems at the same time, at best you’d expect that getting both correct solutions in 1 roll-out is P1*P2. But since the LLM has finite capacity of depth, number of heads, and imperfect attention, then the authors find that the LLM does far worse than P1*P2, because when solving x1 and x2, the solution written for x1 gets noise from seeing the x2, and vice versa.

The paper advocates using an agentic approach and calling the LLM separately for each problem x1 & x2, which allows the LLM to use all its capacity and attention more optimally to solve the problems, so the success rate is P1*P2, and not lots worse.

The paper makes some assumptions and calculates some bounds on how much worse the accuracy of solving x1 & x2 together can be.

The paper shows results on Llama3-8b-Instruct
weaknesses: W1. I agree from your results that current Llama-8b-Instruct as trained today doesn't do this multiple tasks as well as doing each task in isolation, but maybe if the LLM were fine-tuned on a dataset of compositional tasks they would learn to do screening/masking of irrelevant tokens more aggressively and not see the same degradation as currently seen, which might be because they are not typically trained on compositional tasks as often so haven't learned to aggressively mask/screen irrelevant tokens as well. Kind of impossible to test if training on more compositional data helps, so maybe not a fair weakness comment.

W2. I also wonder if the degraded performance is a model depth/size thing too – where bigger deeper models with more heads can mask/screen irrelevant tokens better and don’t see the degradation overload with multiple problems. It would be a stronger paper to understand either how bigger models do with multiple combined problems compared to solving them individually, and how much better models can do if finetuned on the compositional task so they might learn to mask/screen out irrelevant tokens better.

W3. Theoretically it's not clear to me the work rigorously proves the agent approach should be better for “all” datasets given the x1,y1 might be a few-shot example for the x2,y2 and help solve x2,y2 more accurately. I think the paper shows it doesn’t always help, wasn’t sure if that is just noise or are there reasons like x1 and x2 are so similar to help contextually.

W4. The assumptions about noise in the output layer, I’m unclear if for bigger deeper models if that still holds or if it the irrelevant tokens are masked out effectively on bigger models, or even the 8b models finetuned to do compositional tasks. The bounds analysis makes lots of assumptions that I'm not sure are valid in all cases.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Why is there no related work section?

2. It is not unknown that LLMs insufficiently utilize some part of the long context (e.g., [1]). How do you think this incapability to handle information in a long context window confounds your observation or LLM's incapability in doing complex code generation in one turn?

[1] Liu, N. F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., & Liang, P. (2023). Lost in the Middle: How Language Models Use Long Contexts. CoRR abs/2307.03172 (2023). arXiv preprint arXiv:2307.03172, 10.
soundness: 3
strengths: originality: The paper provides a novel complexity metric that quantifies code generation difficulty. This is very interesting as the hardness of natural language processing tasks (code generation being one of them as part of instructions/generations can be in natural language) tends to be quite difficult to quantify.

quality: the paper provides both theoretical and empirical evidence for why multi-agent systems should be favored against single-agent generation when it comes to composed code generation problems. This is sound and clear.

clarity: The paper has a clear argument and consistent storyline.

significance: This paper is theoretically and empirically interesting in that it provides a theory to quantify the code generation hardness and also provides experiments to prove it.
summary: This paper develops a complexity metric to measure the composition hardness of complex code generation by LLMs. By this metric, the authors conclude that decomposed individual generation by multiple agents is easier than generation within one context. This claim is further supported by empirical evidence.
weaknesses: The math part is too compact and creates difficulty for readers. The authors might consider providing more straightforward intuition and re-organizing some details in the appendix.

Meta-review: This paper investigates the degradation in performance of language models when they are tasked with solving two programming problems jointly. They present a mathematical analysis of this degradation, and validate that it appears to be true for competition programming tasks.

A strength is that it tries to give a first principles analysis of the phenomena its studies. A weakness is that the papers conclusion, at least in qualitative form, is already known (see "Faith and Fate: Limits of Compositionality", among many other papers).

I argue for rejection because the basic insight is already well known, hence the lukewarm reception from the reviewers. I don't think that the theoretical analysis compensates for this, particularly because it is only applicable to a very specific kind of compositionality, namely when the function outputs are concatenated.

Decision: Reject