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

arXiv: https://arxiv.org/abs/2409.18028 · HTML: https://mlsanity.com/paper/2409.18028/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 42 references that are in the map.
- First posted on arXiv 26 Sep 2024.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions](https://mlsanity.com/paper/2406.15877/) (2024)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration](https://mlsanity.com/paper/2310.02170/) (2023)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [Code Generation with AlphaCodium: From Prompt Engineering to Flow Engineering](https://mlsanity.com/paper/2401.08500/) (2024)
- [MetaAgents: Large Language Model Based Agents for Decision-Making on Teaming](https://mlsanity.com/paper/2310.06500/) (2023)
- [Self-Organized Agents: A LLM Multi-Agent Framework toward Ultra Large-Scale Code Generation and Optimization](https://mlsanity.com/paper/2404.02183/) (2024)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [Self-Alignment of Large Language Models via Monopolylogue-based Social Scene Simulation](https://mlsanity.com/paper/2402.05699/) (2024)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability](https://mlsanity.com/paper/2407.15720/) (2024)
- [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024)
- [Advances in apparent conceptual physics reasoning in GPT-4](https://mlsanity.com/paper/2303.17012/) (2023)
- [Your Context Is Not an Array: Unveiling Random Access Limitations in Transformers](https://mlsanity.com/paper/2408.05506/) (2024)

## Built on by (most cited first, 3 of 3)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Inverse Scaling in Test-Time Compute](https://mlsanity.com/paper/2507.14417/) (2025)
- [Attention Illuminates LLM Reasoning: The Preplan-and-Anchor Rhythm Enables Fine-Grained Policy Optimization](https://mlsanity.com/paper/2510.13554/) (2025)

## Abstract (arXiv)

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.