PaperlayerView exact revision on arXiv

Source-linked AI summary

TDAG: A Multi-Agent Framework based on Dynamic Task Decomposition and Agent Generation

Yaoxiang Wang, Zhiyong Wu, Junfeng Yao, Jinsong Su

arXiv:2402.10178v2cs.CL

TL;DR

LLM-based agents face error propagation and limited adaptability, while existing benchmarks may lack the granularity to measure incremental progress on multi-step tasks. The paper introduces TDAG's dynamic decomposition and generated subagents, alongside ItineraryBench's fine-grained travel-planning evaluation; it reports that TDAG significantly outperforms existing baselines across several benchmarks.

  • Problem

    Existing benchmarks often lack the granularity to capture incremental progress, and fixed task decompositions and manually constructed subagents face error-propagation and adaptability constraints.

    Source: §1 · p. 1

  • Method

    TDAG dynamically decomposes complex tasks into subtasks handled by specifically generated subagents, while ItineraryBench provides fine-grained evaluation of progressively complex travel-planning tasks.

    Source: §1 · p. 2

  • Results

    TDAG significantly outperforms existing baselines across several benchmarks.

    Source: §6 · p. 9

  • Takeaways & Limitations

    ItineraryBench's nuanced evaluation captures agents' capabilities in partial task completions beyond binary scoring.

    Source: §6 · p. 9

Abstract

from arXiv · show

The emergence of Large Language Models (LLMs) like ChatGPT has inspired the development of LLM-based agents capable of addressing complex, real-world tasks. However, these agents often struggle during task execution due to methodological constraints, such as error propagation and limited adaptability. To address this issue, we propose a multi-agent framework based on dynamic Task Decomposition and Agent Generation (TDAG). This framework dynamically decomposes complex tasks into smaller subtasks and assigns each to a specifically generated subagent, thereby enhancing adaptability in diverse and unpredictable real-world tasks. Simultaneously, existing benchmarks often lack the granularity needed to evaluate incremental progress in complex, multi-step tasks. In response, we introduce ItineraryBench in the context of travel planning, featuring interconnected, progressively complex tasks with a fine-grained evaluation system. ItineraryBench is designed to assess agents' abilities in memory, planning, and tool usage across tasks of varying complexity. Our experimental results reveal that TDAG significantly outperforms established baselines, showcasing its superior adaptability and context awareness in complex task scenarios.

1 Introduction

LLM-based agents face methodological challenges in complex real-world tasks, while existing benchmarks can miss incremental progress on multi-step tasks. The paper introduces ItineraryBench for fine-grained travel-planning evaluation and TDAG, which dynamically decomposes tasks and generates subagents.

1 Introduction

  • Existing multi-step benchmarks can miss partial successes, while fixed decompositions risk error propagation and manually built subagents limit adaptability.The paper identifies binary scoring as insufficiently granular and notes that static subagents are labor- and time-intensive.Source: §1 · pp. 1–2
  • ItineraryBench evaluates interconnected, progressively complex travel-planning tasks with a fine-grained system that reflects partial task completion.The benchmark uses a simulator for dynamic scenarios spanning travel planning; the introduction also notes the use of databases and a code interpreter.Source: §1 · p. 2
  • TDAG dynamically decomposes complex tasks into smaller subtasks and assigns each to a specifically generated subagent.Subsequent subtasks can adjust based on earlier completion status, and the subagents have an evolving skill library.Source: §1 · p. 2
  • Experiments on ItineraryBench are reported to validate TDAG and highlight the benefits of fine-grained evaluation.The introduction presents these experiments as evidence for both the framework and the benchmark's evaluation approach.Source: §1 · p. 2

2 Related Work

Prior work uses LLM-based agents for complex tasks and develops methods for reasoning, planning, and agent evaluation. The paper extends planning approaches with dynamic decomposition and introduces a travel-planning benchmark that assesses partial completion.

2.1 Large Language Model-based Agents.

  • LLM-based agents use language models as their core processing units to tackle complex tasks across varied domains.The related work describes applications ranging from software development to scientific research.Source: §2.1 · p. 2

2.2 Enhancing Agent Planning with Large Language Models

  • Planning methods include ReAct's iterative thought-action process, Reflexion's self-reflection, and ADAPT's recursive task decomposition; TDAG adds dynamic decomposition with generated subagents.The paper presents this extension as flexible task management for complex and unpredictable scenarios.Source: §2.2 · p. 2

2.3 Evaluating LLM-based Agents.

  • ItineraryBench distinguishes itself by assessing partial task completion in travel planning, where tasks vary in complexity and require memory, planning, and tool use.The related work characterizes travel planning as a realistic, dynamic environment for examining incremental progress on multi-step tasks.Source: §2.3 · p. 3

3 ItineraryBench

ItineraryBench is a travel-planning benchmark built around interconnected tasks of increasing complexity. Its simulator evaluates itineraries at multiple levels rather than relying on binary success or a single ground truth.

3.1 Overview

  • ItineraryBench asks agents to plan trips across multiple cities and attractions under time and budget constraints, using tools to retrieve information and support planning.Itineraries specify activities for each trip segment.Source: §3.1 · p. 3

3.2 Dataset Construction

  • The test set contains 364 travel scenarios built from 83 attractions across 15 cities, 846 intra-city routes, and 3,903 inter-city routes.Samples combine cities, attractions, transportation modes, and scheduling constraints.Source: §3.2 · p. 3

Type 1: Inter-city Travel Planning

  • Type 1 plans a multi-city journey by choosing city order, stay durations, and inter-city transportation, using go_to_city and stay_in actions.Scenarios vary the cities, stay lengths, and available activity hours.Source: Type 1: Inter-city Travel Planning · p. 4

Type 2: Intra-city Travel Planning

  • Type 2 plans visits within one city from a fixed starting location, accounting for opening hours and time allocations for meals and activities.Its itinerary uses go_to_place and visit actions.Source: Type 2: Intra-city Travel Planning · p. 4

Type 3: Combined Intra- and Inter-city Travel Planning

  • Type 3 combines the first two task types, planning attraction visits across multiple cities with go_to_city, go_to_place, and visit actions.Agents can use a database of transport and attraction information and a Python interpreter for calculations and numerical optimization.Source: Type 3: Combined Intra- and Inter-city… · p. 4

3.3 Evaluation Metrics

  • The simulator scores itineraries for executability, constraint satisfaction, and time/cost efficiency, advancing to each higher level only after the preceding level is fully attained.The staged metrics reflect partial task completion; efficiency bounds are set using the mean and standard deviation of 50 valid simulated itineraries.Source: §3.3 · pp. 4–5

3.4 Feature Highlights

  • ItineraryBench links travel tasks that increase in complexity through evolving objectives and constraints, while its multi-level scoring recognizes degrees of completion.The benchmark also uses a Python interpreter for planning optimization and a database for external transportation and attraction information.Source: §3.4 · p. 5

4 A Multi-agent Framework based on Dynamic Task Decomposition and Agent Generation

TDAG combines dynamic task decomposition with subtask-specific agent generation, adapting later subtasks to earlier outcomes. Its agent-generation process customizes tool documents and maintains a skill library that is refined as tasks are completed.

4.1 Dynamic Task Decomposition

  • Subtasks are dynamically adjusted using earlier results, allowing the task-solving strategy to recalibrate when execution yields failures or new information.Each subtask is assigned to a subtask-focused agent, reducing irrelevant information and potential noise.Source: §4.1 · pp. 5–6, Figure 2 · p. 6

4.2 Agent Generation

  • LLM prompting customizes subagents for specific subtasks through tool-document generation and an incremental skill library, reducing human effort for agent setup and adaptation.This differs from assigning tasks to predefined, fixed subagents.Source: §4.2 · p. 6

4.2.1 Tool Document Generation

  • Tool-document generation restructures, clarifies, and enriches the original content to address redundancy and unclear descriptions that may mislead agents.The aim is to make the information relevant and optimally formatted for comprehension and application.Source: §4.2.1 · p. 6

4.2.2 Incremental Skill Library

  • Subagents summarize completed subtasks into skills stored for future similar objectives, with retrieval by subtask content and continuous refinement for variable tasks and environments.Because benchmark feedback cannot guarantee skill correctness, skills are refined rather than treated as verified.Source: §4.2.2 · pp. 6–7

5 Experiments

The experiments evaluate TDAG on ItineraryBench, examine its error patterns and the value of fine-grained scoring, and test its performance on WebShop and TextCraft. TDAG outperforms the established baselines on ItineraryBench and the baselines on both additional datasets.

5.1 Settings

  • Experiments cover three Itinerary Bench task types with fine-grained evaluation for partial task completions; ablations remove dynamic decomposition using a static planner as in P&E, or subagent customization using predefined subagents.Baselines include ReAct, P&S, P&E, and ADAPT.Source: §5.1 · p. 7

5.2 Main Results

  • TDAG outperforms established baselines on ItineraryBench, and ablations support the contribution of dynamic decomposition and agent generation.P&E does not outperform ReAct; the authors attribute this to fixed assignments that cannot adapt when earlier subtasks fail.Source: §5.2 · p. 7, Table 2 · p. 8

5.3 Error Analysis

  • P&E is particularly prone to cascading task failures, while TDAG generally has low CKE, EIM, and CNC error rates.ReAct outperforms more complex approaches in minimizing EIM errors; the authors suggest excessive context may increase hallucinations.Source: §5.3 · pp. 8–9, Table 3 · p. 8

5.4 Binary Scoring v.s. Fine-grained Evaluation

  • For challenging tasks with low completion probability, binary scoring poorly distinguishes methods, while fine-grained scoring reflects partial completion.Figure 3 compares performance under binary and fine-grained evaluation.Source: Figure 3 · p. 8, §5.4 · p. 9

5.5 Generalizability

  • TDAG outperforms baselines on WebShop and TextCraft in the reported reward-score and success-rate metrics.The authors describe these datasets as covering both multifaceted and more straightforward tasks.Source: Table 4 · p. 8, §5.5 · p. 9

6 Conclusion

The conclusion presents ItineraryBench for evaluating agents on complex real-world tasks, particularly travel planning, and introduces TDAG's dynamic decomposition and custom-generated subagents. The reported experiments show TDAG significantly outperforms existing baselines across several benchmarks.

6 Conclusion

  • ItineraryBench evaluates LLM-based agents on complex real-world tasks, particularly travel planning, using interconnected, progressively challenging tasks and nuanced evaluation.The evaluation captures partial task completions beyond binary scoring.Source: §6 · p. 9
  • TDAG dynamically decomposes complex tasks into manageable subtasks handled by custom-generated subagents.Source: §6 · p. 9
  • Experiments show TDAG significantly outperforms existing baselines across several benchmarks.Source: §6 · p. 9

A Benchmark Details

The appendix describes the benchmark's composition in terms of task types, city and attraction counts, and travel-planning constraints.

A Benchmark Details

A.1 Task Type Distribution

ItineraryBench divides travel-planning scenarios into three task types, spanning inter-city travel, intra-city navigation, and a combination of both.

A.1 Task Type Distribution

  • Type 1 tasks involve inter-city travel planning, including city visits and transportation.Source: §A.1 · p. 11
  • Type 2 tasks focus on intra-city navigation among attractions within one city.Source: §A.1 · p. 11
  • Type 3 tasks combine inter-city travel and intra-city attraction navigation for a more complex scenario.The task-type distribution is designed to cover different planning complexities.Source: §A.1 · p. 11, Table 5 · p. 11

A.2 City and Attraction Distribution

The benchmark describes the geographic and attraction distribution represented in its travel tasks and incorporates constraints intended to simulate real-world travel planning.

A.2 City and Attraction Distribution

  • Figures 4 and 5 show how often each city and attraction appears across the dataset, respectively.The accompanying text describes these distributions as reflecting geographic spread and the variety and frequency of tourist spots in the plans.Source: §A.2 · p. 11, Figure 4 · p. 11, Figure 5 · p. 11

A.3 Constraints in Travel Planning

  • Travel-planning tasks include time, budget, transport, duration, hotel, activity-time, and rest-period constraints.The text says these constraints are intended to simulate real-world conditions and make plans adhere to specific requirements.Source: §A.3 · p. 11, Table 6 · p. 12
  • Attraction and transportation information was obtained from public websites or self-edited.The passage states this was done to avoid privacy, copyright, or ethics issues.Source: §A.3 · p. 11

B Experimental Details

The experimental setup sets the temperature to 0.

B.1 Implementation of the Incremental Skill Library

The Incremental Skill Library summarizes subagent solutions into skills, filters redundant entries, and retrieves relevant skills for new subtasks. Experiments use specified GPT-3.5 models across ItineraryBench, WebShop, and TextCraft.

B.1 Implementation of the Incremental Skill Library

  • The Incremental Skill Library stores skills as Name, Detail, and Solution fields, using prompted subagent summaries and SentenceBERT embeddings to manage them.A proposed skill is excluded as redundant when at least two existing skills have detail similarity greater than θ = 0.7; retrieval supplies the top two skills by subtask-name embedding similarity.Source: §B.1 · p. 12

B.2 Models and Hyperparameters

  • Experiments use gpt-3.5-turbo-16k for ItineraryBench, gpt-3.5-turbo for WebShop, and gpt-3.5-turbo-instruct for TextCraft.The passage says the latter two configurations follow Prasad et al. (2023).Source: §B.2 · p. 12

Related papers

Loading 2402.10178v2…