Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915130439106560 |
|---|---|
| author | Wolf, Yotam Rothberg, Binyamin Shteyman, Dorin Shashua, Amnon |
| author_facet | Wolf, Yotam Rothberg, Binyamin Shteyman, Dorin Shashua, Amnon |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18028 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective Wolf, Yotam Rothberg, Binyamin Shteyman, Dorin Shashua, Amnon Artificial Intelligence Computation and Language 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. |
| title | Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective |
| topic | Artificial Intelligence Computation and Language |
| url | https://arxiv.org/abs/2409.18028 |