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

• URL: http://arxiv.org/abs/2409.18028v2
• Date: Thu, 3 Oct 2024 14:11:23 GMT
• Title: Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective
• Authors: Yotam Wolf, Binyamin Rothberg, Dorin Shteyman, Amnon Shashua,
• Abstract summary: A common practice in large language model (LLM) usage 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 is beneficial for solving such tasks.
• Score: 6.911107705494142
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability [12.349247962800813]
  Large language models (LLMs) have emerged as powerful tools for many AI problems. They exhibit remarkable in-context learning (ICL) capabilities. How they approach composite tasks remains an open and largely underexplored question.
  arXiv  Detail & Related papers  (2024-07-22T15:22:34Z)
• Smurfs: Leveraging Multiple Proficiency Agents with Context-Efficiency for Tool Planning [14.635361844362794]
  Smurfs' is a cutting-edge multi-agent framework designed to revolutionize the application of large language models. Smurfs can enhance the model's ability to solve complex tasks at no additional cost.
  arXiv  Detail & Related papers  (2024-05-09T17:49:04Z)
• Ensemble Learning for Heterogeneous Large Language Models with Deep Parallel Collaboration [39.35476224845088]
  Large language models (LLMs) exhibit complementary strengths in various tasks, motivating the research of LLM ensembling. We propose a training-free ensemble framework DeePEn, fusing the informative probability distributions yielded by different LLMs at each decoding step.
  arXiv  Detail & Related papers  (2024-04-19T08:52:22Z)
• Evaluating LLMs' Mathematical Reasoning in Financial Document Question Answering [53.56653281752486]
  This study explores Large Language Models' mathematical reasoning on four financial question-answering datasets. We focus on sensitivity to table complexity and performance variations with an increasing number of arithmetic reasoning steps. We introduce a novel prompting technique tailored to semi-structured documents, matching or outperforming other baselines in performance.
  arXiv  Detail & Related papers  (2024-02-17T05:10:18Z)
• Limits of Transformer Language Models on Learning to Compose Algorithms [77.2443883991608]
  We evaluate training LLaMA models and prompting GPT-4 and Gemini on four tasks demanding to learn a composition of several discrete sub-tasks. Our results indicate that compositional learning in state-of-the-art Transformer language models is highly sample inefficient.
  arXiv  Detail & Related papers  (2024-02-08T16:23:29Z)
• In-context Learning Generalizes, But Not Always Robustly: The Case of Syntax [36.98247762224868]
  In-context learning (ICL) is now a common method for teaching large language models (LLMs) new tasks. Do models infer the underlying structure of the task defined by the context, or do they rely on superficial generalizations that only generalize to identically distributed examples? In experiments with models from the GPT, PaLM, and Llama 2 families, we find large variance across LMs. The variance is explained more by the composition of the pre-training corpus and supervision methods than by model size.
  arXiv  Detail & Related papers  (2023-11-13T23:52:43Z)
• Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processes [56.714690083118406]
  In multi-task reinforcement learning (RL) under Markov decision processes (MDPs), the presence of shared latent structures has been shown to yield significant benefits to the sample efficiency compared to single-task RL. We investigate whether such a benefit can extend to more general sequential decision making problems, such as partially observable MDPs (POMDPs) and more general predictive state representations (PSRs) We propose a provably efficient algorithm UMT-PSR for finding near-optimal policies for all PSRs, and demonstrate that the advantage of multi-task learning manifests if the joint model class of PSR
  arXiv  Detail & Related papers  (2023-10-20T14:50:28Z)
• Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models [58.41943058963672]
  We propose a new inference framework called Recursion of Thought (RoT) RoT introduces several special tokens that the models can output to trigger context-related operations. Experiments with multiple architectures including GPT-3 show that RoT dramatically improves LMs' inference capability to solve problems.
  arXiv  Detail & Related papers  (2023-06-12T06:34:16Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.