TL;DR
TDAG is a new multi-agent framework that tackles complex, multi-step tasks by dynamically decomposing them into subtasks and generating specialized subagents on the fly. Alongside the framework, the authors introduced ItineraryBench, a travel-planning benchmark that moves away from "pass/fail" metrics toward a fine-grained evaluation of an agent's incremental progress.
What Problem Does This Paper Address?
Large Language Model (LLM) agents are great at simple tasks but often crumble when faced with complex, real-world scenarios. The authors identify two primary bottlenecks:
- Methodological Brittleness: Most current frameworks use "static" planning. An agent breaks a task into steps (A, B, and C) at the start. If step A fails or returns unexpected data, the agent continues to step B regardless, leading to cascading task failure. Furthermore, many systems use "hard-coded" subagents that lack the flexibility to handle diverse, unpredictable requests.
- Coarse Evaluation: Most benchmarks use binary scoring—you either finish the whole task or you fail. This "all-or-nothing" approach masks an agent's true capabilities. An agent might successfully book three flights but fail to find a specific hotel; a binary score would label this a total failure, ignoring the successful sub-steps.
Methods
The TDAG (Dynamic Task Decomposition and Agent Generation) framework introduces a more fluid way for agents to work:
- Dynamic Decomposition: Instead of a fixed checklist, the "Main Agent" treats the plan as a living document. After each subtask is completed, the framework updates the remaining subtasks based on the actual results (or failures) of the previous step.
- On-the-Fly Agent Generation: Rather than using a library of pre-defined agents, TDAG generates a specific subagent tailored to the current subtask. This includes generating a "cleaned-up" version of tool documentation to reduce context noise and improve the subagent's focus.
- Incremental Skill Library: Inspired by projects like Voyager, TDAG maintains a library of successful "skills" (solutions to subtasks). When a new subtask arises, the system uses SentenceBERT to retrieve the most relevant past solutions, allowing the agent to learn from experience without manual hard-coding.
Datasets
The authors introduced ItineraryBench, a benchmark focused on travel planning. It consists of 364 samples across 15 cities and 83 attractions. Tasks are categorized into three levels of complexity:
- Type 1: Inter-city planning (transportation between cities).
- Type 2: Intra-city planning (navigating attractions within one city).
- Type 3: Combined (the full "personal assistant" experience).
To prove generalizability, they also evaluated TDAG on WebShop (e-commerce navigation) and TextCraft (a Minecraft-inspired crafting environment).
Key Insights and Ideas
- The "Plan B" is Mandatory: The most significant "aha moment" is the data on Cascading Task Failure (CTF). Static methods like P&E (Plan & Execute) had CTF rates as high as 34.78%. TDAG reduced this to just 4.35% by allowing the agent to re-evaluate the plan after every step.
- Context is Noise: By generating subagents with task-specific tool documentation, the authors found that agents perform better when they don't see the full complexity of the entire system, only what is relevant to their immediate subtask.
- Fine-Grained Scoring Matters: The paper argues that binary scoring leads to the "mirage" of emergent abilities. By using a three-level scoring system (Executability, Constraint Satisfaction, and Efficiency), they show that agents are often "mostly right," and we need metrics that reflect that nuance to guide research effectively.
Key Results
On the ItineraryBench, TDAG consistently outperformed established baselines like ReAct and ADAPT:
- Overall Performance: TDAG achieved an average score of 49.08, compared to ReAct’s 43.02 and ADAPT’s 44.74.
- Generalizability: In the TextCraft environment, TDAG reached a success rate of 73.5%, a massive jump over the previous state-of-the-art (ADAPT at 52.0%).
- Ablation Study: Removing "Dynamic Decomposition" caused a significant performance drop, confirming that the ability to pivot mid-task is the framework's "secret sauce."
Limitations and Future Work
While TDAG is powerful, it has a few hurdles:
- Skill Verification: Unlike coding environments where a compiler can verify a "skill," travel planning relies on LLM self-summarization. If an agent summarizes a "skill" incorrectly, that error could persist in the library.
- Cost and Latency: Multi-agent frameworks that involve constant re-planning and agent generation naturally consume more tokens and take longer to execute than single-agent linear chains.
- Model Dependency: The framework was tested primarily with GPT-3.5 and GPT-4. Its performance on smaller, open-source models remains an open question for future research.
Summary updated