PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yotam Wolf, Binyamin Rothberg, Dorin Shteyman, Amnon Shashua

arXiv:2409.18028v3cs.AIcs.CL

TL;DR

LLMs can struggle to use long contexts fully, limiting how far within-context task decomposition can address complex coding problems. The paper models compositional coding and compares solving subtasks in one context with distributing them across agents. It reports an exponential gap in generation complexity that increases with solution length, under its screening model and experiments.

  • Problem

    Effective context-length limits constrain chain-of-thought decomposition for complex coding problems, including codebases too large for one context.

    Source: §1 · pp. 1–2

  • Method

    The paper models coding tasks as compositions and compares generation complexity in a single context with the product of subtask complexities when agents solve them separately.

    Source: §1 · p. 2

  • Results

    The authors report an exponential gap in generation complexity between solving a composition in one context and distributing its subtasks across agents, increasing with solution length.

    Source: §1 · p. 2, §6 · p. 12

  • Takeaways & Limitations

    The findings point to an advantage for distributing decomposed coding problems among multiple agents rather than solving all subtasks within one context.

    Source: §1 · p. 2, §6 · p. 11

    The theoretical result assumes weighted logit noise is continuous, symmetric, and bounded at each decoding step.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

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

Although chain-of-thought decomposition can help with analytical tasks, effective context-length limits constrain how much complexity an LLM can handle in one context. This work studies whether distributing subtasks across agents changes the generation complexity of composite coding problems.

1 INTRODUCTION

  • LLMs can decompose analytical tasks through chain of thought, solving smaller tasks and integrating them into a solution.Prior work reports empirical benefits and theoretical results on what decomposition can represent.Source: §1 · p. 1
  • Effective context length limits practical use of chain of thought for problems, such as large codebases, that exceed what one context can contain.Models may be unable to use all information in their context, even when trained on longer contexts.Source: §1 · pp. 1–2
  • Multi-agent systems distribute a large task’s subtasks across agents, each an LLM instance working on a different aspect.Prior work has applied this approach to building large codebases and solving code and analytical tasks.Source: §1 · p. 2
  • The paper measures usefulness by generation complexity: the number of LLM generations needed to sample at least one correct solution.For a single model, it measures the composite problem; for multiple agents, it is the product of the subtasks’ generation complexities.Source: §1 · p. 2
  • Under a screening assumption, composition in one context may require exponentially more generations than solving subtasks in separate contexts.The authors report theoretical results and experiments on Llama 3 8B and 70B Instruct and Mistral 7B Instruct V0.3.Source: §1 · p. 2

2 RELATED WORKS

Prior work motivates sampling many candidate programs and studies decomposition, probabilistic code generation, and performance on long contexts. This paper focuses on compositional coding and the effect of mixed subtasks within a context.

LLMs as solution candidate generators in programming

  • Sampling many program candidates can yield correct solutions detectable by tests, motivating generation complexity as an expected sampling-cost measure.Prior work reports that thousands of samples may yield a handful of correct programs, and that increasing test-time sampling can improve performance.Source: §2 · pp. 2–3

Theoretical results on composition

  • Earlier theoretical work studies deterministic function composition and decomposition, whereas this paper treats probabilistic autoregressive code generation and multiple correct solutions.The paper argues this framing accommodates sampling and scaling test-time compute in coding tasks.Source: §2 · p. 3

Effectiveness of LLMs in utilizing long context

  • Prior long-context studies report retrieval degradation and limited random access; this paper examines generated code, where semantically different subtasks may interfere even in shorter contexts.The paper frames this as noise from different subtasks’ context during generation.Source: §2 · p. 3

3 FRAMEWORK

The framework treats coding tasks as probabilistic composition and separates decomposition from implementing the resulting subtasks. It models screening as bounded symmetric noise in autoregressive decoding and derives how that noise affects correct-token probabilities.

3.1 GENERATION COMPLEXITY

  • Generation complexity is the inverse success rate of sampling a correct program, and ordinary coding tasks can be decomposed into code blocks that form one solution.The model’s success depends on finding a correct decomposition and implementing a program matching its subtasks.Source: §3.1 · pp. 3–4
  • The generation complexity of a general problem is expressed as a weighted sum over compositional problems, separating decomposition probability from the cost of implementing a solution.The framework also lower-bounds the full problem’s complexity by the best model-suggested decomposition’s compositional complexity.Source: §3.1 · p. 4
  • When solutions to subtasks are sampled in one context, their joint correctness probability is exponentially lower in total code length than when sampled in parallel contexts.The passage states that parallel sampling is more beneficial when intermediate solutions cannot be tested and only the final output can be checked.Source: §3.1 · p. 4
  • Unlike an exponentially decreasing success rate alone, an exponentially growing ratio of composite to parallel generation complexity indicates an advantage to parallel sampling.An exponential decrease in composite success rate alone does not establish an advantage over parallelizing subtasks.Source: §3.1 · p. 4

3.2 SCREENING IN AUTOREGRESSIVE MODELS

  • The screening model assumes that composing semantically different tasks injects noise into their representations during token-by-token autoregressive generation.The noise is modeled as a weighted logit difference between incorrect and correct next tokens, with weights given by token probability mass.Source: §3.2 · p. 5
  • At each decoding step, the weighted noise is assumed to be a continuous, symmetric random variable bounded within [−M, +M].The authors report that experiments support these assumptions, with M approximately 3–4.Source: §3.2 · pp. 5–6

3.3 EFFECT OF NOISE ON DECODING

  • Although logit noise averages to zero, its renormalizing effect does not; the resulting probability shifts can lower correct-sequence probabilities.The paper notes that most long sequences are incorrect, making a large probability increase for a correct solution unlikely.Source: §3.3 · p. 6
  • For a model with finite confidence, noise decreases the average probability of a correct continuation by a factor exp(−∆(ϵ, X)).∆ is the mean of the renormalizing term; the paper gives ∆≈0.2 for ϵ = 0.1.Source: §3.3 · p. 6

4 RESULTS

Composing coding subtasks can require exponentially greater generation complexity than solving them in parallel contexts, and the analysis extends a lower bound to general problems with multiple possible decompositions.

4 RESULTS

  • The paper quantifies compositional hardness as the generation-complexity ratio between solving the combined problem and the product for its subproblems.A ratio significantly above 1 indicates hard composition; a ratio near 1 indicates easy composition.Source: §4 · p. 6
  • Noise from combining subtasks with semantically different but grammatically similar solutions can exponentially reduce the correct-solution probability relative to solving each separately.The proposed intuition is that random noise usually reduces sequence probabilities because code generation has many more incorrect choices than correct ones.Source: §4 · pp. 6–7
  • At ϵ=0.1, ∆≈0.2, σ≈1.5, and M≈4, c≈200, so the stated length condition applies to solutions longer than 200 tokens.The analysis assumes correct-token probabilities in [ϵ, 1 − ϵ]; the paper argues ϵ≈0.05 is plausible for nucleus sampling.Source: §4 · p. 7
  • Under the theorem’s assumptions, sufficiently long compositions have an exponential generation-complexity gap relative to solving their subproblems in parallel.The result holds with probability at least 1 − δ under the stated length and solution-count conditions.Source: §4 · p. 7
  • The theorem’s union bound requires the number of solutions to remain bounded exponentially in solution length; the estimated coefficient is ≈0.005.For a 1,600-token solution, the paper estimates N < 3,000·δ solutions.Source: §4 · p. 7

4.1 GENERATION COMPLEXITY FOR GENERAL PROBLEMS

  • For general coding problems, the paper derives a lower bound on generation complexity using the lowest-complexity valid decomposition the model can generate.The bound relates success on a general problem to simpler tasks and applies across decompositions meeting the stated length condition.Source: §4.1 · p. 8

5 EXPERIMENTS

The experiments test compositional hardness on synthetic Human Eval and code-contest problems, then examine its length dependence and the assumptions behind the theory. Compositions generally require more generations than solving subproblems independently, and the experiments report an exponential length trend and noise properties consistent with the model.

5 EXPERIMENTS

  • The experiments use Llama-3-8B-Instruct on pairwise Human Eval and code-contest compositions, sampling 200 solutions per problem; additional appendices test Mistral-7B and Llama-3-70B.The pairwise composition pass rate was about 1/200, motivating the choice not to test larger compositions in the main experiments.Source: §5 · p. 8, §5.1 · pp. 8–9

5.2 EXPONENTIAL LENGTH DEPENDENCE OF COMPOSITIONAL HARDNESS

  • Without composition relative to with composition, the log ratio of correct-solution probabilities rises linearly with code length (≈0.05, approximating Δ/4), corresponding to an e^-1 success-rate decrease every 20 tokens.The authors describe this length dependence as qualitative because measuring probabilities of sequences not generated by the model is less reliable than a real sampling scenario; fluctuations are high.Source: §5.2 · pp. 9–10

5.1 GENERATION COMPLEXITY RESULTS

  • For most problems, composition requires more generations than solving components independently; Human Eval compositions usually require about 2× more, while most code-contest compositions require at least 5× and some reach 20×.Figure 1 plots the cumulative distribution of the ratio of compositional generation complexity to the product of standalone complexities.Source: §5.1 · p. 9, Figure 1 · p. 10

5.3 EXPERIMENTS ON ASSUMPTIONS

  • The measured change in correct-token logits relative to incorrect-token logits is symmetric, bounded near 4, and has finite nonzero absolute deviation.The estimated theoretical constants are Δ≈0.05–0.2 and σ≈1–2.Source: §5.3 · p. 11, Figure 3 · p. 11

6 DISCUSSION

The discussion characterizes composition as an in-context limitation: generation complexity can grow exponentially relative to distributing subproblems across agents. The authors attribute the gap to screening-related noise in decoding and note that multi-agent systems may bring coherence challenges.

6 DISCUSSION

  • The paper defines generation complexity as the generations needed to sample at least one correct solution and reports an exponential gap between solving a composition in one context and distributing it across agents.The authors attribute the gap to noise caused by mixing subtasks’ latent representations during decoding, termed screening.Source: §6 · pp. 11–12
  • Screening frames effective context length as the model’s ability to isolate relevant context at each decoding step; irrelevant context may reduce performance on other tasks in the same window.The authors connect this account to transformer decoding using all context tokens simultaneously.Source: §6 · p. 12
  • Multi-agent systems may introduce coherence between agents as a new challenge, which the authors leave for future work.Source: §6 · p. 12

A PROOF OF LEMMA 1

The proof establishes that symmetric noise yields a positive expected renormalizing term, then uses bounded-noise assumptions and concentration to bound the probability change across solution tokens.

A PROOF OF LEMMA 1

  • Under continuous symmetric noise bounded within [−M, +M] and correct-token probabilities bounded within [ε, 1−ε], the proof states that Δ and σ are strictly positive.Δ and σ² are defined as the mean and variance of log(ε + (1−ε)e^X).Source: A PROOF OF LEMMA 1 · p. 15
  • For continuous symmetric noise, the expected renormalizing term Δ(p, X) is positive; when p lies in (ε, 1−ε), it exceeds its boundary values at ε and 1−ε.The proof argues positivity by symmetry and the positivity of the integrand except at zero, and states monotonicity with p(1−p).Source: A PROOF OF LEMMA 1 · pp. 15–16
  • The proof applies Bennett’s inequality to a sum of token-level terms, using the positive mean and bounded summands to obtain a high-probability bound.It defines the sequence probability through P(y|x) and combines bounds for both subproblem solutions.Source: A PROOF OF LEMMA 1 · pp. 15, 17

B PROOF OF THEOREM 1

The proof states a high-probability generation-complexity bound under positive parameter assumptions, then uses a union bound to extend the result across solutions. A separate variance-bound proof establishes that the noise variance is maximal at p = ϵ.

B PROOF OF THEOREM 1

  • With probability at least 1 − δ, the theorem gives a generation-complexity bound under its stated assumptions, including positive ∆, σ, and M.The supplied theorem passage omits the complete bound and its full length condition.Source: B PROOF OF THEOREM 1 · p. 18
  • A union bound extends the lemma’s result across all N solutions; the proof states a condition on the minimal combined solution length.The supplied condition is L1 + L2 > M 2.Source: B PROOF OF THEOREM 1 · p. 18

C PROOF OF VARIANCE BOUND

  • The variance-bound proof establishes that the noise variance is maximal at p = ϵ, using a comparison of transformed variances.It states Var[Tp(X)] ≤ Var[Tϵ(X)].Source: C PROOF OF VARIANCE BOUND · pp. 18–19

D PROOF OF THEOREM 2

The proof of Theorem 2 expresses success through valid decompositions and their implementations, then bounds generation complexity using the easiest decomposition. A separate noisy-decoding argument bounds token-probability changes through average noise.

D PROOF OF THEOREM 2

  • The probability of a correct final answer combines generating a valid CoT decomposition with correctly implementing each subtask’s solution.The proof then applies the probability chain rule and identifies the inner sum as the compositional problem’s generation complexity.Source: D PROOF OF THEOREM 2 · p. 19
  • The proof bounds success by a weighted sum over valid decompositions, yielding a generation-complexity bound from the easiest decomposition with finite probability.It extends the argument to k subproblems and uses a union bound over valid decompositions.Source: D PROOF OF THEOREM 2 · pp. 19–20

E PROBABILITY BOUND FOR NOISY DECODING

  • The noisy-decoding bound limits each token’s changed probability in terms of its original probability and logit noise X.The proof uses a softmax representation and Jensen’s inequality; the resulting bound depends on average noise rather than each token’s exact noise projection, enabling sequence-probability bounds.Source: E PROBABILITY BOUND FOR NOISY DECODING · p. 20

F EXPERIMENTAL DETAILS

The experiments used paired composite problems, controlled sampling and correctness checks, and matched solution templates to compare composition with standalone generation. Probability measurements account for template adjustment, with additional logit-noise and Human Eval procedures.

F EXPERIMENTAL DETAILS

  • Each experiment used 50 composite problem pairs, while standalone problems were restricted to pass rates of at least 0.1 to limit excessive composite sampling.Composite problems paired tasks in the formats described in subsection 5.1.Source: F EXPERIMENTAL DETAILS · p. 20
  • Code was sampled at T = 1 with nucleus sampling p = 0.95, then evaluated against the datasets’ provided test cases.The code-generation and evaluation procedures are described separately.Source: F EXPERIMENTAL DETAILS · p. 20
  • Synthetic composite solutions combined standalone dataset solutions in functional or sequential templates intended to be neutral to composition.Both templates modeled the model’s observed ways of solving paired problems.Source: F EXPERIMENTAL DETAILS · pp. 20–21
  • Sequence probabilities were measured after initial tokens in both templates to allow format adjustment; the templates showed similar trends.The procedure measured both solutions in the composite problem for a fair composition-versus-standalone comparison.Source: F EXPERIMENTAL DETAILS · p. 21
  • The logit-noise experiment extracted solution logits under composition and standalone generation and calculated noise as defined in subsection 5.3..Source: F EXPERIMENTAL DETAILS · p. 21
  • An additional Human Eval template made the second problem’s output conditional on the first problem’s True/False result.If the first output was false, the composite output was “-1”.Source: F EXPERIMENTAL DETAILS · p. 21

G EXPERIMENT ON MISTRAL-7B-INSTRUCT-V0.3

For the Mistral experiment, composition typically required ten times more generations than solving both problems in separate contexts. Figure 4 reports the distribution of composition-to-multi-agent generation-complexity ratios.

G EXPERIMENT ON MISTRAL-7B-INSTRUCT-V0.3

  • Typically 10 times more generations were required for composition than for generating solutions to both problems in separate contexts.The passage reports a similar effect for this model.Source: G EXPERIMENT ON MISTRAL-7B-INSTRUCT-V0.3 · p. 21
  • Figure 4 shows that composition required twice more samples in most cases and 10 times more for some problems than the multi-agent case.Its x-axis is the ratio of generation complexities, and its y-axis is the percentage of problems at or below each ratio.Source: Figure 4 · p. 22

H EXPERIMENT ON LLAMA-3-70B-INSTRUCT

On Llama-3-70B-Instruct, composition still generally needs more generations than the non-compositional comparison, though its ratio is typically smaller than before. With irrelevant problems added, the composition penalty remains large; numerical estimates place ∆ in 0.05–0.2 and typical σ around 1–2.

H EXPERIMENT ON LLAMA-3-70B-INSTRUCT

I NUMERICAL ESTIMATION OF ∆AND σ

Related papers

Loading 2409.18028v3…