Source-linked AI summary
HTN-Orchestrate: A Hierarchical Task Network Framework for Multi-Agent Orchestration
Yanchen Deng, Jianguo Huang, Yao Long Teng, Yixuan Li, Handuo Zhang, Ning Wang, Liangcai Su, Xinyu Wang, Bo An
TL;DR
HTN-Orchestrate addresses the tension between adaptive local execution and structured global planning with a two-layer hierarchical task network. Across five benchmarks, it consistently outperforms ReAct, Agent Team, and DeepSeek Harness.
Problem
Existing orchestration approaches either fix decomposition before execution or provide limited explicit modeling of task hierarchies and dependencies, leaving adaptive execution and structured global planning difficult to reconcile.
Source: §1 · p. 1Method
HTN-Orchestrate incrementally expands a hierarchical task network using prerequisite results, delegates executable leaves to local Orchestrators, synthesizes upward under AND semantics, and rebuilds using accumulated evidence when needed.
Source: §1 · pp. 1–2Results
HTN-Orchestrate consistently outperforms ReAct, Agent Team, and DeepSeek Harness across five benchmarks spanning web research, scientific reasoning, and research workflows.
Source: §5 · p. 10Takeaways & Limitations
The findings show that separating control across two layers while feeding results through a shared, revisable task structure allows each layer to inform the other.
Source: §5 · p. 10Future work includes scaling task-network depth for problems requiring deeper decomposition hierarchies.
Source: §5 · p. 10
Abstract
from arXiv · showhide
Orchestrating multiple agents on a complex task requires reconciling local subtask execution with global task planning. Dynamic dispatch approaches provide execution flexibility but do not explicitly model subtask hierarchies or dependencies, while predefined workflows impose this structure but fix the decomposition before execution begins. Therefore, we introduce HTN-Orchestrate, a two-layer framework that separates these responsibilities through a hierarchical task network (HTN). The Planner maintains subtask hierarchies and dependencies, deferring decomposition until prerequisite results become available, while local Orchestrators schedule workers to execute each leaf subtask. Results propagate upward under \textbf{AND} semantics, and accumulated findings inform a rebuilt task network when the current decomposition cannot resolve the task. On five benchmarks spanning web research, scientific reasoning, and research workflows, HTN-Orchestrate outperforms ReAct, Agent Team, and DeepSeek Harness using the same base model, achieving 89.73% accuracy on BrowseComp and 73.44% on SUPERChem, exceeding Agent Team by 2.45 and 4.69 percentage points, respectively.
1. Introduction
HTN-Orchestrate addresses the tension between adaptive local execution and structured global planning by separating planning from worker orchestration in a hierarchical task network. Its evaluations report consistent gains over competing systems across five benchmarks.
1. Introduction
- Local subtask execution must respond to emerging findings while global planning maintains task structure and tracks dependencies.The paper frames this reconciliation as the orchestration challenge.Source: §1 · p. 1
- Existing workflows fix decomposition before execution, while runtime delegation lacks explicit modeling of subtask hierarchies or precedence dependencies.Dynamic decomposition methods also offer limited support for complex dependencies.Source: §1 · p. 1
- The framework uses a Planner to maintain task hierarchies and dependencies, while an Orchestrator coordinates workers on each executable leaf.The Planner incrementally expands the network as prerequisite results arrive.Source: §1 · p. 2
- HTN-Orchestrate combines result-informed decomposition, upward synthesis under AND semantics, and evidence-retaining network rebuilding when the current decomposition cannot resolve a task.Planning decisions for dependent subtasks are deferred until prerequisite findings are available.Source: §1 · p. 2
- 89.73% accuracy on BrowseComp and 73.44% on SUPERChem exceed Agent Team by 2.45 and 4.69 percentage points, respectively.The evaluation spans five benchmarks in web research, scientific reasoning, and research workflows.Source: §1 · pp. 2–3
2. Related Work
Related work spans fixed or learned coordination structures, runtime delegation, and adaptive task decomposition. HTN-Orchestrate combines explicit hierarchy and dependencies with result-informed planning and separate local execution control.
2.1. Multi-Agent Orchestration
- Fixed workflows and architectures provide coordination structure but are determined before or independently of task execution.Runtime delegation adapts during execution but commonly couples decomposition, dispatch, and synthesis without explicitly separating global planning from local management.Source: §2.1 · p. 3
- HTN-Orchestrate separates global planning from local execution and assigns a dedicated Orchestrator to each executable leaf, unlike Workforce’s central coordinator.Its Planner incrementally expands the task network while local coordination proceeds within each subtask.Source: §2.1 · p. 3
2.2. Task Decomposition
- Static decomposition methods finalize task breakdowns before execution, even when they improve decomposition quality or account for agent capabilities.Examples include least-to-most prompting, Agent-Oriented Planning, D-CORE, and Select-Then-Decompose.Source: §2.2 · p. 3
- Adaptive decomposition methods revise plans during execution, but provide limited support for explicitly modeling precedence dependencies among subtasks.HTN-Orchestrate uses prerequisite results to defer decomposition of dependent subtasks until relevant evidence is available.Source: §2.2 · p. 3
2.3. Hierarchical Task Networks and Dependency-Aware Planning
- HTN-Orchestrate distinguishes parent-child decomposition, which governs upward synthesis, from sibling precedence dependencies, which govern access to prerequisite results.Each executable task invokes a local Orchestrator, joining hierarchical decomposition, result-informed planning, and multi-worker coordination.Source: §2.3 · p. 3
- Table 1 compares systems across structured plans, result-informed work, decoupled control, replanning, and evidence carryover.These dimensions distinguish explicit task structure and control separation from adaptation and retention of prior findings.Source: Table 1 · p. 4
3. Method
The method uses a hierarchical task network for global planning and delegates executable leaves to local Orchestrators. Results inform later decomposition, upward synthesis, and rebuilding when the current network is insufficient.
3.1. Task Network Representation
- The task network represents parent-child decomposition with hierarchy edges and acyclic precedence constraints among siblings, where each dependency requires a prior result.An LLM generates decompositions during execution rather than selecting them from a predefined rule library.Source: §3.1 · p. 4
- A leaf is a node with no children, and planning or execution requires it to be pending with all prerequisites completed.Completed prerequisites may provide partial findings even when their subtasks remain unresolved; those findings inform synthesis and replanning.Source: §3.1 · p. 4
3.2. Result-Informed Planning
- Dependent subtasks are decomposed using summaries of relevant prerequisite results, and proposed decompositions are checked for parent-task coverage and acyclic dependencies.Depth and branching limits control network growth.Source: §3.2 · pp. 4–5
- Ready executable leaves run in parallel as a wave, and internal nodes synthesize results only after all children return.Returned results support later decomposition along dependency edges and upward synthesis along hierarchy edges.Source: §3.2 · p. 5
- When a network fails or yields no plausible solution, the Planner carries supported completed and partial findings into a bounded rebuild rooted at the original task.If budgets expire before resolution, the framework synthesizes available evidence and reports unresolved requirements rather than treating stopping as success.Source: §3.2 · p. 5
3.3. Multi-Agent Orchestration
- Each leaf Orchestrator dispatches, waits, or finishes based on its context, worker reports, and active assignments, collecting reports as they arrive.Concurrency, dispatch rounds, and time are bounded; the leaf result includes supported findings, outcome, and evidence references, including gaps when execution limits intervene.Source: §3.3 · pp. 5–6
4. Empirical Evaluations
The evaluation compares HTN-Orchestrate with three controlled baselines across five benchmarks, then examines execution patterns and component ablations on a 200-question BrowseComp subset. HTN-Orchestrate leads the controlled baselines on every benchmark, while the analysis shows how planning, orchestration, and rebuilding relate to execution and accuracy.
4.1. Experimental Setup
- Evaluation covers five benchmarks and compares HTN-Orchestrate with ReAct, Agent Team, and DeepSeek Harness using DeepSeek-V4.1-Flash as the shared backbone.The benchmarks span web research, scientific reasoning, and research workflows; rubric-based FSR and PRL-Bench use different reporting measures from accuracy-based BC, FSO, and SUPERChem.Source: §4.1 · p. 6
4.2. Main Results
- 89.73% BrowseComp accuracy and 73.44% SUPERChem accuracy exceed Agent Team by 2.45 and 4.69 percentage points, respectively; HTN-Orchestrate leads all three controlled baselines on every benchmark.It also achieves the highest scores among all models on FSR and PRL-Bench, and remains competitive with larger proprietary systems on FSO and SUPERChem.Source: §4.2 · p. 6, Table 2 · p. 7
4.3. Analysis
- Among shared correct answers, HTN-Orchestrate finishes faster than Agent Team on 112 of 165 questions, with a median completion-time ratio of 0.699.Against ReAct, HTN-Orchestrate generally takes longer on shared correct answers, but answers 38 questions ReAct misses and misses 12 ReAct answers.Source: Figure 2 · p. 7, §4.3 · p. 8
- Correct and incorrect questions have similar final task-tree depths and leaf counts, but incorrect questions involve more execution activity and more frequent rebuilding.Rebuilding occurs in 50.0% of incorrect questions versus 14.7% of correct questions; Table 3 distinguishes final-tree metrics from execution counts accumulated before and after rebuilding.Source: Table 3 · p. 7, §4.3 · p. 8
- Average worker concurrency is 2.47 for HTN-Orchestrate versus 1.70 for Agent Team across all questions, and 2.42 versus 1.82 on shared successes.On shared successes, HTN-Orchestrate spends 24.6% of run time with at least four active workers versus 11.8% for Agent Team; worker activity includes model and tool waits, but excludes control agents.Source: Figure 3 · p. 8, §4.3 · p. 8
- Across 200 questions, prerequisite-dependent subtasks are generated 79 times across 57 questions, and rebuilding occurs on 35 questions, 27 of which are ultimately correct.The case studies illustrate result-informed narrowing of a downstream search and rebuilding that retains findings to add a targeted search branch.Source: §4.3 · pp. 8–9, Figure 5 · p. 9, Figure 6 · p. 9
- Removing result-informed planning, local multi-agent orchestration, or rebuilding each reduces accuracy, but changes coordination and execution activity differently.Without result-informed planning, accuracy falls from 92.0% to 90.5%, with more worker invocations and longer median completion time; single-agent leaves and no rebuilding each reach 89.5%.Source: §4.3 · pp. 9–10
- In Q193, result-informed planning narrows a downstream search and uses four leaves rather than five; both compared runs answer correctly.In Q501, rebuilding retains findings and adds a feature-based search branch that finds the target post; the no-rebuilding variant returns a different song.Source: §4.3 · p. 10
5. Conclusion
HTN-Orchestrate separates global planning from local multi-agent execution through a revisable hierarchical task network. Across five benchmarks, it consistently outperforms ReAct, Agent Team, and DeepSeek Harness.
5. Conclusion
- The Planner incrementally decomposes a hierarchical task network as prerequisite findings become available and can rebuild it when the initial plan proves insufficient.The lower layer coordinates multiple workers within each executable subtask.Source: §5 · p. 10
- Across five benchmarks, HTN-Orchestrate consistently outperforms ReAct, Agent Team, and DeepSeek Harness.The benchmarks span web research, scientific problem solving, and research-level reasoning.Source: §5 · p. 10
- BrowseComp ablations suggest result-informed planning, local multi-agent orchestration, and task-network rebuilding each contribute to the advantage, with traces revealing interdependence between the two layers.Future work includes deeper task-network hierarchies and evaluation across additional backbone models.Source: §5 · p. 10
A.1. Benchmarks and Tool Access
The evaluation covers five settings across research and scientific tasks, with offline tasks retaining Python computation. Baselines in the within-backbone comparison use the same solver backbone as HTN-Orchestrate.
A.1. Benchmarks and Tool Access
- The five evaluation settings cover web research, scientific problem solving, and research-level reasoning; BrowseComp main results use 1,266 questions, while ablations use a fixed 200-question subset.All ablation variants use the same subset.Source: §A.1 · p. 14
- Offline evaluation disables search, page retrieval, and external network access while retaining Python computation; offline workers derive results from the problem statement and verify calculations with Python.The verifier independently checks the derivation and answer using the same available tools.Source: Table 5 · p. 14, §A.1 · p. 14
A.2. Model and Execution Settings
- The solver backbone is DeepSeek-V4.1-Flash, and the ReAct, Agent Team, and DeepSeek Harness within-backbone baselines use the same solver backbone.Planner and Orchestrator calls use high reasoning effort, while worker and instruction-generation calls use low reasoning effort.Source: §A.2 · p. 14
A.3. Evaluation Judges
Evaluation uses task-specific judging, while execution measurements define question duration, execution counts, and worker concurrency. Dataset averages weight questions equally, and paired latency ratios include only jointly correct answers.
A.3. Evaluation Judges
- GPT-5.5 judges semantic answer matching and rubric evaluation on four benchmarks, while SUPERChem uses exact matching against the selected option.The four GPT-5.5-judged benchmarks are BrowseComp, FrontierScience-Research, FrontierScience-Olympiad, and PRL-Bench.Source: §A.3 · p. 14
A.4. Execution Measurements
- Question duration covers planning, worker execution, coordination, and finalization; execution counts include all epochs, and a worker invocation is one ReAct worker launch.An executed leaf is identified by its question, epoch, and node ID; Orchestrator decisions include dispatch, wait, and terminate actions.Source: §A.4 · pp. 14–15
- Time-averaged worker concurrency uses the main execution trace duration and includes intervals with no active workers; dataset averages weight questions equally.Paired latency ratios compare a question only when both methods answer it correctly.Source: §A.4 · p. 15
B.1. Task-Node Representation
Task nodes retain objectives, prerequisites, execution state, and evidence summaries. Planner and Orchestrator prompts structure decomposition, worker dispatch, synthesis, and recovery around task context and completed findings.
B.1. Task-Node Representation
- Each task node stores its objective, hierarchical position, sibling prerequisites, execution state, and evidence summary; a pending leaf becomes ready after all declared prerequisites complete.When more planning is needed, the Planner receives the node objective and completed precursor summaries before choosing direct execution or decomposition.Source: §B.1 · p. 15
B.2. Prompt Templates and Tool Schemas
- The Planner chooses direct execution for one coherent investigation, verification, or synthesis, and decomposes only when distinct workstreams benefit from separation or parallelism.It receives completed precursor evidence and retained evidence when rebuilding.Source: §B.2 · pp. 15–16
- For decomposition, the Planner emits one call per subtask; the runtime collects calls into an atomic plan, validates coverage and acyclicity, and installs the children.Subtask calls specify dependencies and whether planning should resume after prerequisites.Source: §B.2 · p. 16
- The Orchestrator dispatches workers when reports do not yet answer the leaf task, waits when work is in flight without a distinct gap, and terminates after verification or when no evidence-producing route remains.Multiple dispatches in one response start independent assignments concurrently.Source: §B.2 · p. 17
- Separate synthesis templates combine worker reports at leaves, child results at internal nodes, and requested output fields at the root, distinguishing resolved from exhausted_unresolved outcomes.The latter preserves partial evidence when a decisive relation remains missing after available routes are exhausted.Source: §B.2 · p. 17
- When the current network cannot resolve the root objective, recovery extracts supported facts with verbatim quotes and source references, then uses them with unresolved relations to form the next epoch’s restart context.Rebuild instructions also ask the Planner to identify the most discriminative unresolved relation and preserve a route to an alternative candidate.Source: §B.2 · p. 17
C.1. Ablation Definitions
The ablations isolate orchestration changes on 200 BrowseComp questions, then compare execution costs and paired correctness against the full system.
C.1. Ablation Definitions
- Single-agent assignment is per executed leaf within an epoch, while upfront planning fixes a downstream worker’s position and objective before prerequisite results arrive.Each ablation changes one part of the orchestration procedure while preserving the other mechanisms.Source: §C.1 · p. 17
C.2. Accuracy, Execution Volume, and Latency
- Upfront decomposition uses more executed leaves and workers and longer mean and median duration; the single-agent variant lowers worker use and latency but increases executed leaves.It rebuilds on 64 questions versus 35 for the full system; removing rebuilding reduces mean duration but slightly raises median duration.Source: §C.2 · p. 18
C.3. Paired Correctness
- Table 11 partitions the same 200 questions by paired correctness, distinguishing cases only the full system answers correctly from those only an ablated variant answers correctly.The supplied passages describe the partition but do not provide its outcome counts.Source: Table 11 · p. 18, §C.3 · p. 18
D.1. Using an Intermediate Result to Specialize Later Work
The examples show intermediate results specializing later work, local orchestration verifying candidate evidence, and rebuilding carrying findings through a timeout.
D.1. Using an Intermediate Result to Specialize Later Work
- The specialized chain reaches 1980 with four leaves and 15 workers versus five leaves and 20 for upfront decomposition, which also answers correctly.The Planner uses the returned author list to specialize the downstream investigation.Source: §D.1 · pp. 18–19
D.2. Targeted Verification within a Leaf
- Within BrowseComp Q1025, venue-first evidence was verified to identify Linus Lerner; the single-agent-per-leaf variant submitted Gregory Wait without establishing the requested review.The full attempt used three leaves and ten workers.Source: Figure 8 · p. 19, §D.2 · p. 19
D.3. Evidence Carried across a Rebuild
- 5 leaves and 72 workers across two epochs yielded “Serial Killer” after evidence-preserving recovery, versus 2 leaves and 18 workers and “Silent Night” without rebuilding.After the first epoch timed out before recovering the required list, recovery retained findings and unresolved work; later finalization used accumulated evidence at the execution limit.Source: §D.3 · p. 20, Table 12 · p. 20