Source-linked AI summary
TaReD: Tool-Aware Recursive Decomposition for Long-Horizon Tasks
Wei-Xiang Mao, Zhi-Kai Chen, De-Chuan Zhan, Han-Jia Ye
TL;DR
Long-horizon tool tasks strain single execution chains, and large tool libraries make it difficult to provide useful capability information without overwhelming the planner. TaReD organizes tools into an on-demand capability hierarchy and uses it to guide recursive task decomposition. In the reported evaluation, it improves end-to-end task success rate by up to 40 percentage points over the compared baselines.
Problem
Long-horizon tool use requires maintaining dependencies, while full tool-library context is costly and smaller flat subsets can omit necessary tools or provide little guidance for decomposition.
Source: §1 · pp. 1–2Method
Results
TaReD improves end-to-end task success rate by up to 40 percentage points over the compared baselines.
Source: §1 · p. 2Takeaways & Limitations
The hierarchy provides structural guidance for decomposing tasks around available operations while avoiding full-library context injection and retaining on-demand access to tools.
Source: §1 · p. 2, §2 · p. 3The formulation is scoped to tasks specified by an instruction and initial environment state, with interaction through executable tools.
Source: §3.1 · p. 3
Abstract
from arXiv · showhide
Agents combine reasoning with tools to interact with external systems and complete real-world tasks. Early agents typically interleave reasoning and actions along a single execution chain. On complex tasks, this chain becomes unreliable because growing histories obscure intermediate dependencies and allow early planning errors to propagate. Recursively decomposing a complex task into smaller subtasks offers a natural solution, yet effective decomposition must account for the system's capabilities so that each subtask can be executed by the available tools. In realistic systems, however, tool libraries can be too large to expose in full. Injecting every tool description consumes substantial context while making relevant tools harder to retrieve and useful task boundaries harder to identify. We propose tool-aware recursive decomposition, which organizes tools by functional relationships into a hierarchy of capabilities. During execution, the agent discovers tools on demand and uses the hierarchy to recursively decompose a complex task into a subtask tree whose levels are aligned with the capabilities required at each stage. Experiments on complex real-world tasks show that the proposed method improves end-to-end task success rate by up to 40 percentage points over the compared baselines. The implementation of TaReD is available on GitHub: https://github.com/WeiXiang-Mao/TaReD.
1 INTRODUCTION
Long-horizon tool use makes dependencies harder to maintain, while semantic decomposition alone may produce stages the environment cannot execute. TaReD organizes tools into a capability hierarchy for on-demand discovery and capability-aligned recursive decomposition.
1 INTRODUCTION
- Long action chains accumulate intermediate states and dependencies, while semantic decomposition may create subtasks without executable capabilities or omit necessary stages.Tool use also requires selecting relevant tools, constructing valid arguments, and ordering calls whose results and state changes may affect one another.Source: §1 · p. 1
- TaReD improves end-to-end task success rate by up to 40 percentage points over the compared baselines.The evaluation compares TaReD with representative recursive, linear, and plan-then-execute strategies under matched models, budgets, verifiers, and service conditions.Source: §1 · p. 2
- TaReD organizes tools by functional relationships into a capability hierarchy, discovers relevant information on demand, and recursively divides tasks into capability-aligned stages.It binds an exact tool contract when a stage is ready to execute, avoiding full-library context injection and the omissions possible with a fixed subset.Source: §1 · p. 2, Figure 1 · p. 2
2 RELATED WORK
Prior work addresses long-horizon tasks through decomposition and tool selection, but semantic task boundaries and flat tool subsets do not ensure capability-aligned, executable stages. TaReD contributes an on-demand hierarchy that guides decomposition around available operations.
Task decomposition and hierarchical planning
- Chain-based agents interleave reasoning and actions, while task-decomposition methods break complex tasks into ordered, interdependent subproblems.Semantic-driven approaches use goals, entities, or procedural structure, but may not specify an executable sequence.Source: §2 · p. 3
Tool use and large tool libraries
- Predicting or retrieving a smaller tool subset reduces irrelevant choices but can omit necessary tools and offers little guidance about capability relations or subtask boundaries.Tool descriptions were typically provided in context, but including full tool information becomes impractical as tool libraries grow.Source: §2 · p. 3
Contributions of this work
- TaReD organizes tools by functional relationships into a hierarchy, queries it on demand, and uses capability relations to guide decomposition into executable subtasks.This avoids placing the full library in context while retaining on-demand access to every tool in the library.Source: §2 · p. 3
3 PRELIMINARY
The preliminary formulation models a long-horizon task as interaction with an environment through executable tools, and defines a capability hierarchy and recursive task tree. Its objective is to maximize goal attainment while keeping stages aligned with available tools and their execution preconditions.
3 PRELIMINARY
- The formulation treats successful long-horizon execution as achieving the task objective while moving the environment from its initial state to a desired final state.The task is represented by an instruction and initial environment state, with completion checked by a goal predicate.Source: §3 · p. 3, §3.1 · p. 3
3.1 TASK AND ENVIRONMENT
- A long-horizon task is specified by an instruction and initial environment state, and completion means the final state satisfies the task goal.The agent interacts with the environment through a library of executable tools; a tool contract specifies input and output schemas, preconditions, and state-changing effects.Source: §3.1 · p. 3
3.2 TOOL LIBRARY AND CAPABILITY HIERARCHY
- The complete tool library is organized by functional category into a tree whose internal nodes summarize capability regions and whose leaves correspond to tools with execution contracts.A root-to-leaf path represents progressively more specific information about an executable capability.Source: §3.2 · p. 3
3.3 RECURSIVE TASK DECOMPOSITION
- The recursive task tree contains ordered functional stages; each stage has a goal, relevant context, and an expected capability region.Internal stages decompose into ordered child stages, while leaf stages are ready to bind one or more tool contracts and execute.Source: §3.3 · p. 4
3.4 PROBLEM OBJECTIVE
- The alignment condition requires every task-tree leaf to have a corresponding available tool whose preconditions hold when it executes.The planning objective maximizes the probability that the final environment state satisfies the task goal, subject to that alignment condition.Source: §3.4 · p. 4
4 TARED: TOOL-AWARE RECURSIVE DECOMPOSITION
TaReD organizes tools by capability and discovers them on demand, guiding recursive task decomposition while keeping irrelevant tool information out of context. It refines subtasks into executable stages, binds tool contracts at execution time, and carries results forward through dependencies.
4 TARED: TOOL-AWARE RECURSIVE DECOMPOSITION
- TaReD organizes tools into a capability hierarchy and discovers them on demand, keeping context focused while preserving access to the full library and guiding decomposition around capability relations.This addresses the trade-off between exposing the full tool library and retrieving a smaller subset that may omit necessary tools.Source: §4 · p. 4
4.1 OVERALL WORKFLOW
- Starting from the original task, TaReD repeatedly discovers capabilities and decomposes the task until each subtask is directly executable or the available capabilities are insufficient.Executable stages plan calls, retrieve contracts, bind arguments, invoke tools, and store resulting values and state for dependent subtasks.Source: §4.1 · p. 4
4.2 HIERARCHICAL CAPABILITY REPRESENTATION
- The hierarchy groups tools into functional regions: internal nodes guide navigation, while leaves represent executable operations with the exact contract needed to run them.Capability cards summarize supported operations, their inputs and outputs, and the region’s boundary.Source: §4.2 · pp. 4–5, Figure 2 · p. 5
4.3 ON-DEMAND CAPABILITY NAVIGATION
- The controller queries the capability hierarchy from the expected region until it has enough information to plan, searching other regions when needed to fill gaps.Only information from visited nodes enters context.Source: §4.3 · p. 5
4.4 CAPABILITY-ALIGNED RECURSIVE DECOMPOSITION
- When a goal needs further decomposition, TaReD forms ordered, capability-grounded child tasks with explicit dependencies and bindings, then processes them depth first with parent review when needed.A child is dispatched only after its predecessors are closed and its bindings can be resolved.Source: §4.4 · pp. 5–6
4.5 DELAYED CONTRACT BINDING AND EXECUTION
- TaReD binds exact tool contracts only after a task is judged directly executable, then uses stored values and provenance to support later calls and dependent subtasks.Reference-based handoffs avoid copying full earlier responses into context while preserving values for reuse.Source: §4.5 · p. 6
4.6 ALGORITHMIC SUMMARY
- Algorithm 1 presents TaReD as recursive handling of task nodes, with sufficiency and direct-execution checks based on observed capability information.Subtask results return to the current task for review and further planning.Source: §4.6 · pp. 6–7
5 EXPERIMENTS
On AppWorld Challenge Test-C, TaReD leads the compared methods on task completion, scenario consistency, and partial-credit verification. Ablations favor hierarchical, on-demand tool awareness over flat alternatives.
5.1 EXPERIMENTAL SETUP
- Evaluation uses AppWorld Test-C, with 457 tools across nine applications, GPT-5.6 Luna, and a 600-second episode limit.The study also uses a 100-step cap, fixed random seed 42, and temperature 0; TGC, SGC, and ATVS measure task completion, scenario consistency, and partial-credit verification.Source: §5.1 · p. 8
5.2 MAIN RESULTS AND ANALYSIS
- TaReD achieves the highest values among four methods on TGC, SGC, and ATVS in the adopted AppWorld Challenge Test-C run set.TGC measures individual-task completion, SGC scenario-level consistency, and ATVS partial-credit verifier progress.Source: Table 1 · p. 8, §5.2 · p. 8
5.3 ABLATION STUDIES
- Full tool injection yields only slight task-completion improvement over the Predictor subset; expandable discovery improves more, and hierarchical awareness improves further.Figure 3 shows hierarchical awareness improves task execution with only a modest increase in tool context.Source: Table 2 · p. 9, §5.3 · p. 9, Figure 3 · p. 9
- 12% of tasks showed strong evidence of blocking tool omission, accounting for 24.3% of failed cases; capability information exposed averaged 7.41% and detailed contracts inspected 2.48%.These exposure measurements cover all audited TaReD runs.Source: §5.3 · p. 9
6 CONCLUSION
TaReD uses on-demand hierarchical tool discovery to guide recursive task decomposition without requiring the full library in context. Its discovery overhead and context-usage trade-off remains open.
6 CONCLUSION
- TaReD combines on-demand hierarchical tool discovery with capability-guided recursive decomposition for long-horizon tasks and large tool libraries.The design aligns subtask boundaries with available capabilities without requiring full-library context.Source: §6 · p. 9
- Navigating multiple capability levels can require extra model calls and increase execution time relative to one-shot tool selection.A cache reuses queried capability cards and tool information, reducing redundant queries while retaining more information in working context.Source: §6 · p. 9
- The trade-off between discovery overhead and context usage remains unresolved.Source: §6 · p. 9
A CAPABILITY-TREE CONSTRUCTION
The capability tree is a static, pre-execution organization of capabilities, with progressively finer internal categories and original executable contracts at the leaves.
A CAPABILITY-TREE CONSTRUCTION
- The capability representation is constructed before task execution, rather than inferred separately for each task.Source: A CAPABILITY-TREE CONSTRUCTION · p. 13
- Internal nodes summarize capability categories at progressively finer levels of granularity.Source: A CAPABILITY-TREE CONSTRUCTION · p. 13
- Leaves preserve the original executable tool contracts.Source: A CAPABILITY-TREE CONSTRUCTION · p. 13
A.1 FROM A FLAT CATALOGUE TO A HIERARCHY
The construction turns a public tool catalogue into a versioned capability hierarchy, retaining tool contracts at the leaves and using cross-branch links for related capabilities.
A.1 FROM A FLAT CATALOGUE TO A HIERARCHY
- The input catalogue supplies tool identifiers, descriptions, schemas, response information, and documented preconditions or side effects; records are validated while parameters and response schemas are preserved.Source: §A.1 · p. 13
- Each tool receives one primary path through increasingly specific functional distinctions, from broad domain to concrete operation.Intermediate levels are added only when they distinguish meaningful capabilities or execution boundaries, so branches can have different depths.Source: §A.1 · p. 13
- The tree attaches each normalized tool as a leaf under its deepest applicable category, preserving one primary parent and distinct execution identities.The explicit, versioned taxonomy yields the same primary hierarchy when rebuilt from the same catalogue and taxonomy.Source: §A.1 · p. 13
- Non-tree navigation links connect related capabilities across branches, allowing discovery beyond the current branch without copying tools or encoding execution order.Source: §A.1 · p. 13
A.2 NODE TYPES AND STORED INFORMATION
The catalogue separates navigation from execution: categories summarize capability regions, while native-tool leaves retain executable contracts. Runtime values are excluded from the static tree and retrieved only when the relevant stage runs.
A.2 NODE TYPES AND STORED INFORMATION
- The catalogue has a non-executable root, non-executable category nodes, and executable native-tool leaves.Categories are not callable; composite operations require a separately implemented node type and contract.Source: §A.2 · p. 13
- Category summaries support planning and navigation but are not unioned executable schemas or sources of live account and object values.They record scope, input and output hints, preconditions, limitations, capability facets, links, source references, and descendant-contract statistics.Source: §A.2 · p. 13
- Each native-tool leaf preserves its source identity and exact executable contract, including parameters, constraints, and success or failure responses.Runtime values such as access tokens, product identifiers, and current records are obtained from the environment when the corresponding stage executes.Source: §A.2 · p. 13
A.3 CONSTRUCTION CHECKS AND RUNTIME EXPOSURE
The catalogue is curated as a task-independent taxonomy and built deterministically from public API documentation, with checks for structural and source-contract consistency. At runtime, bounded discovery exposes categories first and exact tool contracts only when needed.
A.3 CONSTRUCTION CHECKS AND RUNTIME EXPOSURE
- Runtime discovery starts at the root and reveals bounded category summaries before exposing an exact native-tool contract at its leaf.Pagination and response budgets limit observations, and the session records only discovered nodes.Source: §A.3 · p. 14
A.4 AI-ASSISTED CURATION AND DETERMINISTIC CONSTRUCTION
- The deterministic builder produces a catalogue with 137 category nodes and 457 native-tool leaves from a reviewed, task-independent taxonomy and public API documentation.The taxonomy is curated by Codex; the builder retains documented contracts, derives summaries and counts, and records source and taxonomy hashes.Source: §A.4 · p. 14
A.3 CONSTRUCTION CHECKS AND RUNTIME EXPOSURE
- Construction checks verify unique API assignment, reachable nonempty categories, consistent node references, and leaf contracts that match their source records.The checks also validate catalogue integrity; changes to the public documentation or taxonomy require a regenerated catalogue or reviewed taxonomy.Source: §A.3 · pp. 13–14, §A.4 · p. 14
B ILLUSTRATIVE EXECUTION TRACE
A hypothetical email-to-Todoist task illustrates how capability discovery guides recursive decomposition and depth-first execution. The example separates planning summaries from executable contracts and preserves dependencies between stages through stored references.
B ILLUSTRATIVE EXECUTION TRACE
- The illustrative task is split into finding a deadline in email and creating a Todoist task, with the second child depending on the first child’s result.The parent stores the message content under a stable reference, extracts the deadline, and makes it available to the second stage.Source: B ILLUSTRATIVE EXECUTION TRACE · p. 15
- Capability summaries guide stage choice and granularity, while exact tool contracts are inspected and bound only when a stage is ready to execute.The example selects an email operation and then todoist.create after navigating to their capability regions.Source: B ILLUSTRATIVE EXECUTION TRACE · p. 15
- The example is schematic rather than an evaluated episode, and its task and returned values are hypothetical.If discovery in the expected region is insufficient, the controller may inspect another relevant region before refining or executing.Source: B ILLUSTRATIVE EXECUTION TRACE · p. 15