AD a PT : As-Needed Decomposition and Planning with Language Models (2024)

Abstract: Large Language Models (LLMs) are increasingly being used for interactive decision-making tasks requiring planning and adapting to the environment. Recent works employ LLMs-as-agents in broadly two ways: iteratively determining the next action (iterative executors) or generating plans and executing sub-tasks using LLMs (plan-and-execute). However, these methods struggle with task complexity, as the inability to execute any sub-task may lead to task failure. To address these shortcomings, we introduce As-Needed Decomposition and Planning for complex Tasks (ADaPT), an approach that explicitly plans and decomposes complex sub-tasks as-needed, i.e., when the LLM is unable to execute them. ADaPT recursively decomposes sub-tasks to adapt to both task complexity and LLM capability. Our results demonstrate that ADaPT substantially outperforms established strong baselines, achieving success rates up to 28.3% higher in ALFWorld, 27% in WebShop, and 33% in TextCraft – a novel compositional dataset that we introduce. Through extensive analysis, we illustrate the importance of multilevel decomposition and establish that ADaPT dynamically adjusts to the capabilities of the executor LLM as well as to task complexity.

## introduction recent advances in large language models (llms) have expanded their application beyond conventional nlp tasks to more complex tasks involving mathematical, symbolic, and commonsense reasoning @xcite . recent models have even been applied to decision-making tasks, such as performing household chores, navigating a webpage, etc., that require interactions with external environments or tools @xcite . 1 project: https://allenai.github.io/adaptllm prior works on using llms for decision-making, such as react @xcite , iteratively generate the next action to be executed in the environment given the history of actions and observations (see fig. 1 ; top-left). however, as the tasks become more complex, llms struggle due to their limited composition ability @xcite and inability to deal with the distractors @xcite in a long action-observation trajectory. to mitigate this, modular approaches @xcite @xcite incorporate a separate planner module that utilizes an llm to create a high-level plan. 2 the planner then delegates simpler sub-tasks to an executor llm module thereby reducing the compositional complexity and length of action trajectory required by the executor. we refer to this category broadly as plan-andexecute approaches (see fig. 1 ; top-right). while the plans enable these methods to guide the execution and track progress @xcite , their non-adaptive nature poses a limitation when confronting unachievable sub-tasks. these approaches inherently lack the flexibility to adapt to task complexity and manage execution failures, as shown in fig. 1 (top-right), where just one sub-task that is too complex results in overall task failure. to address such failures, we propose as-needed decomposition and planning for complex tasks (adapt), a recursive algorithm that further decomposes sub-tasks when necessary, to dynamically accommodate to task complexity. we utilize separate planner and executor llm modules within our framework but only decompose a task using the planner, if the executor llm detects a failure. as shown in fig. 1 , the overall task of putting a clean mug on a desk in an unfamiliar household is too complex for the model, leading to failure of the iterative executor. while a plan-andexecute-style approach initially breaks down the task into three sub-tasks, it falls short in accounting for the complexity in finding a mug. moreover, it is challenging to anticipate the difficulty of such a subtask in advance, as the executor could find a mug in the first attempt or in an obscure location. therefore, adapt employs its recursive structure to dynamically adapt to execution failures (assessed by llms), by further decomposing the complex sub-task of finding a mug via the planner. empirically, we demonstrate the effectiveness of adapt on three datasets involving interactive environments: alfworld @xcite , @xcite , and a new compositional text game for crafting minecraft recipes called textcraft (sec. 4.1). using gpt-3.5 as the underlying llm, adapt outperforms strong baselines (discussed in sec. 4.2) such as react @xcite , and plan-and-solve @xcite ) by up to 28.3%, 27%, and 33% absolute points on alfworld, webshop, and textcraft respectively (sec. 5). compared to reflexion @xcite , an adaptive approach that addresses failures in the full task trajectory, adapt yields higher success rates by 14.1%, 9%, and 20% on alfworld, webshop, and textcraft respectively. through extensive analysis of adapt, we establish the importance of recursive decomposition (sec. 6.1) and showcase dynamic adaptation to the capabilities of the executor llm including open-source models such llama-2 @xcite and lemur @xcite in sec. 6.2. lastly, we demonstrate that adapt incorporates task complexity (sec. 6.3), where the extent of recursive decomposition aligns with the inherent task complexity. to summarize, our contributions are: 1. we present adapt, a recursive algorithm that dynamically decomposes complex sub-tasks on an as-needed basis, i.e., intervening only if the task is too complex for the executor. 2. on three diverse datasets, alfworld, webshop, and textcraft, adapt improves success rate of gpt-3.5 over previous approaches by up to 28.3%, 27%, and 33% points respectively. 3. analysis of adapt underscores the significance of recursive decomposition and the ability to adapt dynamically to varying llm execution capabilities and task complexities. ## methodology we introduce as-needed decomposition and planning for complex tasks (adapt), a modular approach for decision-making that integrates an llm as an executor and a planner (secs. 3.1 and 3.2) within an llm program called the controller (sec. 3.3). in fig. 1 , when adapt is given a complex task, it first attempts to accomplish the entire task by running the executor iteratively, and resorting to the llm planner for further decomposition into sub-tasks if the executor fails. subsequently, adapt is recursively called for each sub-task to ensure their successful completion, ultimately leading to overall task success. ## experimental setup we describe the datasets used in our experiments and baselines used for comparison with adapt. ## main results using gpt-3.5 as the underlying llm, in this section, we show that adapt yields the highest success rate compared to baselines from prior work on alfworld, webshop, and textcraft datasets. ## analysis and discussion we analyze adapt in detail by addressing the following research questions on dev data splits. ## conclusion we introduce adapt, a recursive algorithm designed to harness the planning capabilities of llms, dynamically decomposing complex tasks when the llm acting as an executor encounters challenges. our evaluation across three diverse decision-making tasks, alfworld, webshop, and textcraft, reveals impressive performance of adapt, surpassing existing baselines by substantial margins of up to 28.3%, 27%, and 33% points, respectively. this not only underscores the effectiveness of adapt but also highlights the significance of as-needed decomposition in enhancing task performance. moreover, our findings demonstrate that adapt not only adapts to the capabilities of the underlying executor llm but also takes into account the complexity of individual task instances, showcasing its versatility and effectiveness.