PaperlayerView exact revision on arXiv

Source-linked AI summary

ADaPT: As-Needed Decomposition and Planning with Language Models

Archiki Prasad, Alexander Koller, Mareike Hartmann, Peter Clark, Ashish Sabharwal, Mohit Bansal, Tushar Khot

arXiv:2311.05772v2cs.AIcs.CLcs.LG

TL;DR

Complex interactive decision-making tasks expose weaknesses in iterative executors and fixed plan-and-execute systems when sub-tasks are difficult or unachievable. ADAPT addresses this with recursive, as-needed decomposition triggered by executor failure, and it outperforms strong baselines across ALFWorld, WebShop, and TextCraft. The approach also adapts to executor capability and task complexity, but relies on self-evaluation whose limitations motivate external verification.

  • Problem

    Iterative executors and non-adaptive plans struggle with complex tasks because long trajectories, limited composition, distractors, or one unachievable sub-task can cause failure.

  • Method

    ADAPT recursively decomposes a task with an LLM planner only when its executor fails, using a controller to execute and combine sub-tasks.

  • Results

    ADAPT surpasses existing baselines by up to 28.3% on ALFWorld, 27% on WebShop, and 33% on TextCraft, while adapting to executor capabilities and task complexity.

  • Takeaways & Limitations

    The findings establish the importance of recursive, as-needed decomposition for interactive decision-making across diverse environments.

  • Takeaways & Limitations

    ADAPT relies on an executor-generated success heuristic, whose self-evaluation may be limited and could require external verifiers or calibration techniques.

Abstract

from arXiv · show

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.

1 Introduction

LLM agents for interactive decision-making struggle with complex tasks when iterative execution cannot manage long trajectories or when fixed plans contain unachievable sub-tasks. ADAPT addresses this by recursively decomposing sub-tasks only when execution fails, outperforming strong baselines across three environments.

  • Iterative executors struggle with complex tasks because limited composition ability and distractors make long action-observation trajectories difficult to manage.
  • Fixed plan-and-execute approaches reduce executor complexity but can fail entirely when one planned sub-task is too complex or unachievable.Their non-adaptive plans cannot anticipate sub-task difficulty or manage execution failures.
  • ADAPT recursively decomposes complex sub-tasks only when the executor detects failure, dynamically accommodating task complexity.The approach uses separate planner and executor LLM modules.
  • 33% higher success rate on TextCraft is achieved by ADAPT over strong baselines, alongside gains of up to 28.3% on ALFWorld and 27% on WebShop.These are absolute-point improvements reported using GPT-3.5.
  • ADAPT outperforms Reflexion by 14.1%, 9%, and 20% on ALFWorld, WebShop, and TextCraft, respectively.

2 Related Work

Prior decision-making agents either execute actions iteratively or use decomposition without adapting to failures. ADAPT combines modular planning and execution with recursive, as-needed decomposition and autonomous hierarchical planning.

  • ReAct generates each next action from prior actions and observations, handling failures while implicitly tracking the full plan during local decisions.
  • Feedback- and search-based follow-up methods do not decompose tasks, so they may explore multiple whole-task trajectories when difficulty is localized to one sub-task.
  • ADAPT extends recursive hierarchical decomposition with planner-executor communication and automatic further decomposition after executor failures.
  • Unlike hierarchical methods that use predefined plan libraries, ADAPT explores autonomous task decomposition using LLM world knowledge and recursive planning.

3 Methodology

ADAPT is a modular controller that first attempts direct execution, then invokes an LLM planner to recursively decompose failed tasks. Its executor supplies success judgments, while the planner produces short sub-task plans and composition logic.

  • ADAPT combines an LLM executor and planner within a recursive controller that decomposes failed tasks and recursively executes their sub-tasks.The controller continues until a maximum depth dmax is reached.
  • LLM as an Executor: The executor iteratively interacts with the environment using LLM-generated actions until task completion or a preset iteration limit.It receives a concise task specification and demonstrations of environment-specific atomic skills.
  • LLM as an Executor: The executor emits “task completed” or “task failed” to determine whether further decomposition is needed, and this heuristic closely matches gold reward.
  • LLM as a Planner: The planner generates concise plans of typically 3–5 steps, allowing later recursive decomposition instead of requiring a detailed plan upfront.Shorter plans reduce errors from incorrect assumptions in unexplored environments.
  • LLM as a Planner: Planner-generated AND operators encode sequential sub-task requirements, while OR operators support conditional exploration where any successful branch suffices.
  • Controller: The pipeline first assigns the task to the executor, invokes the planner after failure, and recursively combines sub-task outcomes according to the selected logical operator.

4 Experimental Setup

The experiments evaluate LLM agents on three interactive environments using task success rate, with TextCraft introducing compositional crafting tasks. ADAPT is compared against iterative, planning, retry, and reflection-based baselines under shared implementation settings.

  • Datasets: The evaluation uses task success rate across ALFWorld, WebShop, and TextCraft, with separate test and development splits described for the environments.ALFWorld uses 134 unseen evaluation games; WebShop reports 100 test instructions and a separate 40-query development set.
  • Datasets: TextCraft is a new text-only Minecraft crafting environment whose tasks have compositional recipe structures with varying complexity.Tasks can require recursively crafting ingredients, and recipe depth provides a complexity measure.
  • Evaluation: Table 1 reports overall success rates on the ALFWorld test split, comparing ADAPT with prior-work baselines.The table marks the highest rates in bold and the second-highest rates with underlining.
  • Baseline Approaches: The baselines include ReAct executor-only interaction, fixed-plan Plan-and-Execute, repeated Try Again with ReAct, and Reflexion with feedback memory.Plan-and-Execute plans once, whereas Reflexion reruns the entire task after failure, including previously successful sub-tasks.
  • Baseline Approaches: All methods share a standardized executor for relative comparison, while ADAPT decomposes only when the executor fails and generates shorter adaptive plans.ADAPT with dmax = 2 therefore differs from fixed Plan-and-Execute despite both using planner and executor modules.
  • Implementation Details: The default setup uses GPT-3.5 for planning and execution, with dmax = 3 for ALFWorld and WebShop and dmax = 4 for TextCraft.ReAct receives proportionally more iterations so baselines use a comparable number of LLM calls.

5 Main Results

ADAPT achieves the highest success rates across ALFWorld, WebShop, and TextCraft, outperforming prior baselines through adaptive decomposition and planning. Its gains include improvements over both fixed-plan and adaptive full-trajectory approaches.

  • Cross-dataset results: ADAPT achieves the highest success rate across ALFWorld, WebShop, and TextCraft when using GPT-3.5.The comparison includes strong baselines from prior work.
  • ALFWorld: 28.3% points higher than ReAct on ALFWorld, ADAPT also exceeds Plan-and-Execute by 28.3% and Try Again by 23.8% points.ADAPT is additionally 14.1% points higher than Reflexion overall.
  • ALFWorld: Over a factor of 4× improvement occurs on ALFWorld ‘pick2’ tasks, where baselines achieve below 12% success rates.These tasks require composing two pick-style tasks over a longer action history.
  • WebShop: 27% points over ReAct, Plan-and-Execute, and Try-Again is the maximum WebShop improvement, while ADAPT exceeds Reflexion by 9% and LATS by 6% points.The results indicate gains over both planning and search-based baselines.
  • TextCraft: 33% over ReAct, 25% points over Plan-and-Execute, and 20% points over Reflexion are ADAPT’s reported TextCraft improvements.TextCraft results highlight adaptive, as-needed planning for complex crafting tasks.

6 Analysis and Discussion

Analysis shows that ADAPT benefits from deeper recursive decomposition, supports executors with varied capabilities, and adjusts decomposition to task complexity. It also transfers useful plans across different planner and executor models without relying on substantially more LLM calls.

  • Recursive decomposition: Increasing maximum decomposition depth dmax from 1 to 2 and from 2 to 3 consistently improves success rates across all datasets.The dmax = 1 setting corresponds to the executor-only ReAct baseline.
  • Executor capabilities: 41.7% success versus 3.3% is achieved by ADAPT for the weakest executor setting, while ADAPT improves all three executor-capability settings.Task-specific trajectories perform best, and atomic-skills-only prompting performs worst.
  • Different LLMs: 37% is the largest reported TextCraft improvement for GPT-4, while ADAPT improves LLaMA by up to 15% and benefits all evaluated models across datasets.The evaluated models are GPT-3.5, GPT-4, LLaMA-2 70B, and Lemur 70B.
  • Task complexity: 78.2% versus 26.9% for recipe depth 2 and 38.7% versus 1.8% for depth 3 show ADAPT’s gains over ReAct as recipes become more complex.With dmax = 4, average utilized decomposition depth kmax rises from 1.9 to 2.8 as recipe depth increases from 2 to 3.
  • Computational budget: Comparable LLM-call counts to Try-Again and Reflexion indicate ADAPT’s gains do not simply stem from substantially more calls.Other methods may use fewer calls because they fail to handle intermediate execution failures.

7 Conclusion

ADAPT dynamically decomposes complex tasks when executor LLMs encounter challenges, using recursive as-needed planning. Across ALFWorld, WebShop, and TextCraft, it surpasses existing baselines and adapts to executor capabilities and task complexity.

  • ADAPT recursively decomposes complex tasks when the executor LLM encounters challenges.The approach uses as-needed decomposition rather than always expanding tasks into detailed plans.
  • 28.3%, 27%, and 33% points are the reported maximum margins over existing baselines on ALFWorld, WebShop, and TextCraft, respectively.
  • ADAPT adapts to both the capabilities of the underlying executor LLM and the complexity of individual task instances.

Limitations

ADAPT relies on an executor-generated success heuristic to determine whether a complex task can be performed. The authors identify self-evaluation limits as a boundary for extending the framework beyond the studied decision-making tasks.

  • ADAPT uses the executor LLM’s success heuristic to assess whether the model can perform a complex task.
  • For the decision-making tasks studied, LLMs reliably determine task success from past action trajectories and textual environment feedback.
  • Limits in LLM self-evaluation and self-refinement may require external verifiers or improved calibration techniques for broader tasks such as question answering.

A ADAPT Implementation Details

ADAPT combines ReAct-style executors, dataset-specific planners, and a recursive controller. Its implementation specifies atomic skills, termination logic, information propagation, model configurations, and evaluation budgets.

  • Executor: The executor uses ReAct with in-context example trajectories for environment-specific atomic skills.Examples include taking, placing, cleaning, and heating objects in ALFWorld; atomic skills are task dependent.
  • Planner: The planner receives atomic-skill descriptions and demonstrations of dataset-specific task decompositions.In ALFWorld, “find” is handled by the planner because it is not an executor atomic skill; WebShop and TextCraft use corresponding decomposition demonstrations.
  • Controller: The controller bridges planner and executor information and determines termination using planner logic, executor success, or a maximum depth dmax ≥ 1.
  • Evaluation: The evaluation compares ADAPT with prior baselines on ALFWorld and evaluates methods on WebShop, using the reported task-specific model and iteration configurations.The executor models are text-davinci-003 for ALFWorld, gpt-3.5-turbo for WebShop, and gpt-3.5-turbo-instruct for TextCraft; budgets are 20, 15, and 20 iterations respectively.
  • Overall pipeline: ADAPT first executes the task directly, then invokes the planner and recursively executes sub-tasks when direct execution does not succeed.
  • Evaluation: Success rates in Sections 5 and 6 are reported from a single run of each LLM because of cost constraints.

B Handling Complex Logic in Plans

ADAPT’s controller parses planner-produced logical expressions containing AND and OR operators and decomposes them into multiple levels. This also lets plan-and-execute baselines simulate multilevel planning through detailed plans.

  • The controller supports complex logical expressions containing both AND and OR operators.The planner is instructed to append the execution order with a fixed prefix, which a deterministic parser processes.
  • The parser splits complex logical expressions into homogeneous expressions that are passed to ADAPT.
  • Expressions such as Step 6 = Step 1 OR Step 2 OR Step 3, followed by Step 6 AND Step 4 AND Step 5, produce multiple planning levels.
  • Detailed plans allow the plan-and-execute baseline to simulate a multilevel planning structure, while the same logical expressions can be used within ADAPT.

C Task-specific Executors in ALFWorld

ADAPT improves performance when layered onto task-specific ALFWorld executors, surpassing baselines on nearly all task types. It also outperforms Reflexion despite lacking dedicated memory and natural-language feedback.

  • 23.1% points is the maximum overall success-rate improvement ADAPT achieves over the compared baselines.
  • ADAPT surpasses baselines on all but one task type when used with task-specific executors.
  • 12.6% points is ADAPT’s improvement over Reflexion despite lacking dedicated memory and natural-language feedback.
  • A stronger task-specific executor improves plan-and-execute performance on complex sub-tasks, while ADAPT remains superior overall.

D Additional WebShop Experiments

Additional WebShop experiments show that ADAPT improves success rates across search-page complexities and produces shorter trajectories when decomposition is needed. The experiments also describe how environment state is propagated during execution.

  • Increasing search-page products makes WebShop harder because the executor must choose among more products and track more information.
  • 22.5% and 20.0% are ADAPT’s success-rate improvements over ReAct with 10 and 3 products per search page, respectively.
  • ADAPT decomposes complex tasks after executor failure, producing shorter action trajectories for easier execution than ReAct’s long-history approach.
  • ADAPT yields higher improvement in the more complex 10-product search setting than in the 3-product setting.
  • In WebShop rollouts, the current search page and matched products are propagated to future executor runs.
  • In TextCraft, the executor can compose skills to craft an unavailable item such as diorite without further decomposition.

F Evaluation of Success Heuristic

The success heuristic lets ADAPT repeatedly assess whether a sub-task requires further decomposition. Its reliability varies by environment, with substantially inflated assessments in WebShop affecting downstream performance.

  • ADAPT repeatedly uses the executor’s binary success heuristic to decide whether a sub-task needs further decomposition.
  • On ALFWorld and TextCraft, the LLM slightly overestimates overall task success relative to gold environment rewards.
  • On WebShop, the LLM’s success assessment is inflated by more than 30 points compared with the environment reward.
  • The WebShop feedback error can terminate ADAPT before further decomposition is performed.
  • ALFWorld executor examples use inventory and environment observations to verify assumptions before completing tasks.
  • ALFWorld examples illustrate searching multiple locations for objects before taking or using them.
Loading 2311.05772v2…