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

Thank you for your helpful feedback.

Reply to weaknesses:

• Thank you for your suggestion, we moved technical details from lemma 1 and theorem 1 to the appendix to make them more accessible in the revised version.

Reply to questions:

• The related works were discussed in the introduction, but to crystalize our contributions on top of existing works, we added a related works section.
• We refer to works that show utilization of long context is limited (e.g. [1]), we will also cite the work you suggest. However, there is a big difference between our work and the works mentioned, because the contexts in our work are not necessarily very long, (can be less than 1000 tokens and not multiple documents). This is not considered a long context for most models. This exemplifies that the LLM does not just suffer from utilizing information in long contexts but also has trouble when dealing with multiple tasks within one context, getting noise from one task while trying to solve another. We will emphasize this difference to the existing works mentioned in the related works.

[1] https://arxiv.org/abs/2404.06654

[2] https://arxiv.org/abs/2307.03172

Thank you for your insightful comments.

Reply to weaknesses:

• We agree that if a model is finetuned on composing specific types of problems, then it may improve its performance on composing similar problems. Though we can then redefine the composite problem to be the basic problem (as that can essentially be treated as one problem that the model trained on) and try to compose them. Thus our interest is in composition in the sense of out of distribution performance, i.e. – If a model knows how to solve two problems, what can we say about its ability to solve their composition if it was not explicitly trained to do so. The significance of this is that since LLMs can solve such a wide range of problems, it would be beneficial to leverage it to solve problems which require combining different pieces of knowledge. Our work shows a limitation of this ability to combine its capabilities in a single context, pointing out that to utilize the model's capabilities better, splitting to contexts or finding a way to mask irrelevant information is important.
• That is a good point – We performed the composition experiment for the llama-3-70B-instruct model on code contest problems to see the dependence on size. The results are presented in appendix F, where indeed we see it is significantly more efficient at composition, though the effect is not diminished, and is similar to llama-3-8B-instruct’s results on humaneval composition. However, while in the experiments the compositions were explicitly concatenations of the subproblems, which are the simplest compositions, the theoretical results apply also to cases where the composition may be less direct, where there will be a mixing of tokens from different tasks that can be more challenging to separate, leading to a higher generation complexity.
• It is a good point that potentially if the model generates $y_1$, then it can serve as an in-context learning example that would increase the chance of producing $y_2$. We discuss this in the revised version:
  1. In reality, compositions may not necessarily be similar enough logically to induce in context learning - for example, if a compositional problem has a dynamics programming part and a randomized algorithm part, then there is no reason for one to improve the success rate of the other.
  2. Our theoretical results do not guarantee that for any dataset composition becomes harder, it requires the noise to be large enough and the solutions to be long enough. Indeed, in the simpler experimental dataset of combined human eval problems (figure 1a), there are problems where composition is easier (indicating in-context learning), while for the more complex problems such as in the dataset of combined code contest problems (figure 1b), this happens less. Thus, there may be a competing mechanism of in context learning, that is overcome by the noise when complexity rises. We also note that, there is a significance to the order in which $x_1,x_2,y_1,y_2$ appear. In the case of in-context learning, the model is given $x_1,y_1,x_2$ and the model only needs to generate $y_2$, while in our compositional case, $y_1$ and $y_2$ need to be written in one program, and are not completely separated blocks of code, which may make it harder for the model to infer that $x_1,y_1$ are an in-context example to $x_2$ (after the generation of $y_1$).
• Generally, it is experimentally observed even on the largest of models that longer contexts reduce their accuracy on tasks such as retrieval [1,2]. Specifically, performance depends on relevant information being positioned at “convenient” places within the context. Thus in compositional problems, even the larger models may not attend to the correct parts of the context, leading to the noise described in our framework. As exemplified in our experiments on the 70B model, while the decrease in performance is not as great as the 8B model, there is a consistent drop in accuracy on most compositional problems.

[1] https://arxiv.org/abs/2404.06654

[2] https://arxiv.org/abs/2307.03172

Reply to questions:

• Line 0: As written in the introduction – some previous works studied the advantages and limitations of multi-step tasks in language models, while primarily focusing on expressibility or learnability of deterministic functions that perform well defined mathematical tasks, such as the bit parity problem [3], Turing machines [4,5], or iterative composition of a single function [6], which cannot necessarily be translated in an interesting manner to code generation. In such results, for a given problem, the model provides a deterministic answer to the problem which is either correct or incorrect. This deviates from the practical use of language models for code generation that is based on probabilistic sampling of multiple solutions and filtering the correct ones (which can be 1 in 1000 or even worse). Thus previous works cannot capture the usefulness of LLMs on code, as most SOTA LLMs do not deterministically provide correct solutions to complex coding problems, but rather what makes them useful is sampling many solutions so that one is good. For this reason, we introduce the generation complexity metric that allows to quantify this usefulness by not just providing a binary answer to whether a model will succeed in a composition or not, but quantify how hard it is relative to the subproblems with a softer definition, which cannot be done in the previous settings. To improve accessibility and make this point clear, we summarized this in a new “related works” section.
• Line 147: It may be possible to achieve better results on composition with training. Though as mentioned above in reply to weaknesses, the main motivation for composition is an out of distribution result – so that the model can piece together different problems it was not trained to solve together. An interesting future direction to alleviate this problem is a more “focused” attention mechanism that removes irrelevant context more aggressively and improves the signal to noise ratio, such as in [8].
• Line 161: As mentioned above in reply to weaknesses, a few-shot effect is expected to rise when the problems are semantically similar, while in reality interesting compositions can have quite different subtasks. But we agree that studying the tradeoff between in-context learning to compositional hardness is a very interesting subject that we leave for future work.
• Line 304: As mentioned above, we performed the experiment on the larger 70B model, and show that the effect is weaker on the same dataset relative to the 8B model, but existent.

[3] https://arxiv.org/abs/2204.02892

[4] https://arxiv.org/abs/2309.06979

[5] https://arxiv.org/abs/2310.07923

[6] https://arxiv.org/abs/2402.08164

[7] https://arxiv.org/abs/2410.05258

[8] https://arxiv.org/abs/2410.05258

Dear reviewer ka9k,

We greatly value your constructive feedback on our paper. We would greatly value your review of our responses to ensure we have properly addressed your concerns.

Thank you for your feedback.

Reply to weaknesses:

• We explain below the significance of the theoretical results.
• Below we explain how the experimental setup arises from the theoretical results, why it is not arbitrary, and the significance of the results.

Reply to questions:

• Significance explained informally –
  • Why generation complexity is important - As presented in the introduction, when it comes to LLMs generating code to solve problems, a common practice is to sample multiple programs (could be 100, could be 1000, or even more), and to filter out those that pass correctness tests. There are instances where out of thousands of generations only one solution is correct. Due to the use of testing units, an LLM can still be useful even if only 1 in 1,000 sampled programs is correct, because you can filter out the correct one. Of course, if 1 in 100 is correct, then the LLM is much more useful, as you would only need a tenth of the sampling budget/test time compute (which translates to a tenth of the actual price in standard LLM APIs). Understanding how many programs one needs to sample from an LLM to assure a correct solution is sampled, quantifies the LLM's usefulness on such a task. The generation complexity metric quantifies exactly this.
  • The gist of our results - We then show that in tasks that involve several steps, one would need to sample exponentially more programs if it is done sequentially within one context, compared to sampling the solutions separately, in different contexts. This quantifies a difficulty of problem composition. It is significant for the real purpose of code generation, because if one can sample a correct solution with a budget of 100 generations compared to 1,000 generations, the cost is significantly lower.
  • Where this comes into play in real life - When dealing with compositional coding problems, one typically uses a chain of thought to solve a series of subproblems whose concatenated solutions solve the problem y_1⊕…⊕y_n (e.g. break the task into multiple helper functions). It is not intuitive that after decomposing the problem, an LLM that can solve one subproblem with probability 0.5 (1 in 2 generations on average) and another with probability 0.2 (1 in 5 generations on average), will have success probability 0.01 (1 in 100 attempts) to solve them in the same context and not the product of individual probabilities 0.2*0.5=0.1 (1 in 10 generations). This phenomena of in-context hardness of composition is what we tackle in this paper.
  • We added a related works section that highlights the motivations for our theoretical approach given existing works.
• We do not claim that this covers the entire aspect of composing problems, but that the aspect we present can be a very significant contributor to LLM failure in composition, which has not been covered by previous works, and that a multi-agent system can have a big advantage in this regard.
• Experimental justification – as the aspect of compositional hardness we want to tackle is the in-context hardness explained above, the experimental setup is natural, as you take two problems, and observe that solving them together requires more generations than independently solving them in separate contexts. Thus concatenating problems can be thought of as a lower bound for the hardness of composition (as they are an easy form of composition) - meaning harder compositions will have higher complexity. We added this point to the revised paper.
• Hypothesis to explain experimental results – as mentioned in the paper, when combining two problems, the self-attention mechanism mixes attention in tokens from different problems. This is quantified by the noise we defined – if the hidden representations in the non-compositional case are more "accurate" in the sense that they lead to sampling more correct programs, then in the compositional case, the representations are noised, which leads to the generation of less accurate programs.

Dear reviewer xEcp,

We appreciate your feedback on our paper. To ensure our responses are helpful to resolve your concerns, we would greatly appreciate it if you could review them.

Reply to questions:

1. The functional shape of equation 5 comes from the reweighting of the logits due to the noise and applying Jensen's/AMGM inequality, as seen in the proof of lemma 1 up to equation 35. We added a derivation in appendix D to explain this more clearly. This represents a useful upper bound on the probability of producing a correct token in a compositional problem relative to the non compositional case. There can be other forms of bounds, but this is a relatively succinct bound as it removes the dependence on the exact projection of noise on each token in the vocabulary, and instead takes into account the average noise on the different tokens.
2. We hope the explanations above and clarifications in the revised version answer the questions on the proof of lemma 1.
3. In figure 1 and 2 we used the second form (multiplication). Both forms yielded similar results.
4. Relative complexity of different compositions - in the theoretical results, a solution to a compositional problem is the concatenation of solutions to the subproblems, which is consistent with the use of a chain of thought, in which a problem x is solved in steps $y_1⊕…⊕y_n$ (such as helper functions in programming). In our framework, the relative complexity of compositions is quantified by the length of the solution and the magnitude and shape of the logit noise introduced by the context (both in the prompt and partial generations of the model). This quantifies a specific type of compositional hardness introduced by context noise. Indeed, there may be other types of composition difficulties not captured by tuning the noise from our framework, but the aspect of hardness in this work serves as a lower bound on compositional hardness due to its presence in problems that require sufficiently long solutions. The experiments section shows this effect in concatenations, which are the simplest compositions, in order to cleanly show that the effect of the context noise is significant, hence they can be seen as a lower bound. We note that the results of our paper do not claim to capture all aspects of compositional complexity, but rather an unexpected mechanism introduced by the noise, which can be a significant factor of composition, due to the necessity to break down complex problems to smaller problems with chain of thought.

Thank you for your detailed feedback.

Reply to weaknesses:

• Regarding the technical proof of the lemma. We are sorry for the confusion, we elaborated more on these steps in the proof in the revised version to improve clarity. For completeness we explain here briefly on the points that you raised:
  1. Equation 40 (now numbered 46): Bennet's inequality bounds the deviation from the expected value, we use the lower tail bound $P(\sum_i (X_i-E[X_i ])≤-t)≤exp⁡()$ (symmetric to the upper tail bound case with ≥t). Move the expectation value to the r.h.s. and take $t=3/4 \sum_i E[X_i]$, which gives $P(\sum_i X_i≤1/4 \sum_i E[X_i])≤exp⁡()$. Lastly, take the complementary event, which gives the desired result $P(\sum_i X_i>1/4 \sum_i E[X_i])≥1-exp⁡()$.
  2. The choice of t which includes the 3/4, explains the factor of 3/4 on the right hand side of equation 40. The factor L is a typo, meant to be $|y_2 |$, the length of the solution. The origin of this is that in Bennet's inequality, you place there the variance of the sum, which in our case is bounded by $|y_2 | σ^2$. To make the exponent small and obtain a large probability 1-δ, we go to equation 41 (now 47), where we find how large $|y_2 |$ needs to be for this to hold.
  3. Thus before equation 42 (now numbered 48), indeed as you thought, 1-δ is the probability that the noise sampled is large enough so that equation 42 holds.
  4. The transition from 35 to 42 (now 36 to 48): in 35, we have $P_{composition} < P_{no composition}⋅e^{-S}$, and in the series of equations 36-41 (now 37-47), we introduce a concentration inequality on S, showing that with high probability $S>Δ/4|y_2 |$. So, with high probability, $P_{composition}<P_{*no composition*}⋅e^{-S}<P_{*no composition*}⋅e^{-Δ/4|y_2 |}$.
  5. See revised version for full details.
• The subsection 4.3 serves two parts – first to plot the noise in a compositional coding problem and see that it qualitatively looks as we expect in the assumption (symmetric, continuous) and to estimate its magnitude. The second part, is to take noise with this typical size and shape, to get a ballpark estimation to Δ and σ.
• Def 1: f is an abstract function that solves x (e.g. if x is the problem of finding shortest paths between two vertices in a graph, then f is a mathematical function that receives a graph and two vertices, and outputs the shortest path in the graph between them). The solution y, is the implementation of the abstract function f in the language L, i.e. the program.
• Def 2: We are sorry for not clarifying, Σ is the vocabulary of the LLM, thus Σ* are sequences of tokens. "Sampled from the distribution" indeed refers to the conditional distribution P(⋅|x), as in definition 2 we sum over conditional probabilities of correct solutions P(y|x). For consistency we changed the notation of vocabulary from Σ to V in the revised version.
• Set difference vs quotient difference – you are correct, we mean the set difference, we fixed it.
• We changed the exp font.
• The line "Δ≈0.05-0.2" means Δ is in the range 0.05 to 0.2, not a subtraction. We corrected this in the text. Hence it does not contradict the earlier point of Δ≈0.2, but agrees with it.
• Eq 30: We referred earlier to V as the vocabulary, we clarified in the revised version.
• Eq 31: Yes, you are correct, we fixed this.
• Eq 33: Noted, we will use Jensen's inequality
• Eq 34: Thank you, it is true, we corrected. We note that in the following we did use the correct sign.