OrchDAG: Complex Tool Orchestration in Multi-Turn Interactions with Plan DAGs
Yifu Lu, Shengjie Liu, Li Dong · 2025
Read OrchDAG: Complex Tool Orchestration in Multi-Turn Interactions with Plan DAGs by Yifu Lu, Shengjie Liu, Li Dong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24663.txt.
Introduction
Yifu Lu, Shengjie Liu, and Li Dong build a test set for agents that call tools over many turns. Most past work looks at one call or a short chain, not a web of steps. Their pipe, OrchDAG, lays tool steps out as a graph with no loops, where each step can feed later ones.
They can set how hard each graph is, then score how well a model runs it. A new graph based prize helps train models with trial based learning. Tests show the set is hard but can be solved. Their point is that graph shape and task depth should guide training.
Catalog record
| CREATOR | Yifu Lu, Shengjie Liu, Li Dong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24663
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
OrchDAG: Complex Tool Orchestration in Multi-Turn Interactions with Plan DAGs Yifu Lu, Shengjie Liu, Li Dong Abstract Agentic tool use has gained traction with the rise of agentic tool calling, yet most existing work overlooks the complexity of multi-turn tool interactions. We introduce OrchDAG, a synthetic data generation pipeline that models tool execution as directed acyclic graphs (DAGs) with controllable complexity. Using this dataset, we benchmark model performance and propose a graph-based reward to enhance RLVR training. Experiments show that the dataset presents a challenging but solvable benchmark, and the proposed reward is effective when combined with GRPO-style algorithms, highlighting the importance of leveraging topological structure and data complexity in multi-turn tool use. 1 INTRODUCTION Large Language Models (LLMs) ( brown2020languagemodelsfewshotlearners ; JMLR:v24:22-1144 ; deepseekai2025deepseekr1incentivizingreasoningcapability ; touvron2023llama2openfoundation ; zeng2023glm130bopenbilingualpretrained ) have been at the forefront of advancing artificial intelligence, marking significant breakthroughs in diverse fields. The planning capabilities of LLMs, particularly their ability to use tools ( yao2023treethoughtsdeliberateproblem ; yao2023reactsynergizingreasoningacting ), enable them not only to execute commands and perform web searches but also to enhance their advanced mathematical reasoning abilities. LLM Compiler kim2024llmcompilerparallelfunction and its subsequent work ( erdogan2024tinyagentfunctioncallingedge ; erdogan2025planandactimprovingplanningagents ) propose constructing tooling usage as a directed acyclic graph (DAG) to enable the parallel execution of independent tools, thereby improving tool-calling efficiency. CodeAct wang2024executablecodeactionselicit and CodePlan wen2024unlockingreasoningpotentiallarge propose leveraging the generation of pseudo-Python code to outline high-level reasoning processes for complex multi-step reasoning tasks, where each tool usage is represented as a function call within the code. ReWOO xu2023rewoodecouplingreasoningobservations proposes a modular framework that decouples the reasoning process from the external observations of each tool usage, thereby reducing token consumption and improving efficiency. liu2025toolplannertaskplanningclusters clusters the provided tools into groups of toolkits, plans at the toolkit level, and replans by selecting tools within the same toolkit if error comes out. ma2024nonmyopicgenerationlanguagemodels proposes a method called Predictive-Decoding, which leverages Model Predictive Control from the optimal control field to mitigate early errors in planning and promote non-myopic planning, thereby enhancing overall accuracy. ReasonFlux yang2025reasonfluxhierarchicalllmreasoning proposes a framework in which the LLM reasons over template fields, executes tools based on the templates, and employs reinforcement learning to improve planning accuracy using an action completion reward. In the agentic setting, LLMs are evolving beyond purely textual reasoning toward dynamic agents capable of planning, tool use, and multi-step (also multi-turn) execution. The introduction of Group Relative Policy Optimization (GRPO) shao2024deepseekmathpushinglimitsmathematical further inspired the development of Reinforcement Learning with Verifiable Reward (RLVR) for agentic tool use, driven by its efficiency. The xLAM zhang2024xlamfamilylargeaction suite introduces purpose-built “large action models” optimized for function calling, offering strong baselines and open resources for multi-turn tool execution. Llama-Nemotron bercovich2025llamanemotronefficientreasoningmodels extends this trajectory with efficient reasoning modes and scalable inference, enabling models to dynamically switch behaviors across long conversations. ToolRL qian2025toolrlrewardtoollearning systematically studies reinforcement learning reward designs—covering granularity, temporal structure, and signal types—to improve generalization in multi-turn tool-integrated reasoning, while OTC wang2025actingreasoningmoreteaching complements this by explicitly balancing accuracy and tool-call efficiency to maintain productivity over prolonged interactions. Kimi K2 kimiteam2025kimik2openagentic shows that stabilizing long-context training and using multi-stage RL leads to robust performance across multi-round software engineering, math, and agentic tasks. These works highlight that advancing agentic LLMs in multi-turn settings requires not only larger or more efficient models, but also principled reward design, cost-aware tool-use strategies, and scalable system pipelines. Recent advances in evaluating agentic models have led to new benchmarks and environments for assessing performance in realistic, interactive scenarios. ACEBench chen2025acebenchwinsmatchpoint overcomes limits of prior evaluations by introducing a structured benchmark with Normal, Special, and Agent categories to test atomic-level tool use across simple, complex, multi-agent, and ambiguous instruction settings. Complementing this, BFCL (v3) patil2025bfcl standardizes function-calling benchmarks across real-world contexts, supporting serial and parallel invocations in multiple languages through an AST-based evaluation. \tau -Bench, \tau^{2} -Bench, and UserBench yao2024taubenchbenchmarktoolagentuserinteraction ; barres2025tau2benchevaluatingconversationalagents ; qian2025userbenchinteractivegymenvironment together extend evaluation from structured tool–user interactions to controlled bidirectional agent cooperation and finally to fully user-centric, dynamic environments, progressively enriching the realism and robustness of agent assessment. Prior work on tool use has mainly studied general real-world APIs qin2023toolllmfacilitatinglargelanguage , such as send email or make calendar , along with related functions in web search systems like Manus. Meanwhile, current multi-turn settings mainly focus on computer-use tasks patil2025bfcl , such as manipulating files in the operating system. In industrial settings, however, an agent may need to work with hundreds of domain tools, including APIs and pipeline endpoints, and may also interact with other domain agents to produce a complete answer to a user query. The complexity usually arises from three aspects: (1) the dependencies among tools can be intricate, (2) the output of a tool is often represented as a JSON file with many fields, and (3) a key output field from one tool may serve as an input to another, but with different field names. Moreover, in multi-turn settings, the environment may execute the required tools but encounter time-outs or runtime errors in their responses. Therefore, it is important to construct a dataset that not only evaluates current models but also pushes their capabilities in complex multi-turn tool interaction, which is essential for building robust and reliable agents. In summary, this work makes several pivotal contributions: • We design a synthetic multi-turn data generation pipeline OrchDAG for agentic tool use, where each round of tool execution for a user query is represented as a DAG. The complexity of the generated data is controlled by a pipeline hyperparameter. • Using the constructed dataset, we first evaluate the current model’s performance and then introduce a graph-based reward derived from the DAG for RLVR training. • Extensive experiments show the effectiveness of our approach, emphasizing the value of incorporating the topological structure of tool execution graphs and the importance of controlling data complexity in multi-turn tool use. 2 PRELIMINARY 2.1 LLM Reasoning with Tools for Multi-turn Settings For the first turn, given a user query x and a pretrained LLM \rho_{\theta}(\cdot) , the LLM generates an tool execution plan represented as a graph with p=\{\mathcal{P}_{1},\dots,\mathcal{P}_{n}\}\sim\rho_{\theta}(p\mid\mathcal{T},\mathcal{D},x) , where p is the plan list after topological sorting, \mathcal{T} is the set of available tools, and \mathcal{D} is the collection of descriptions for all available tools. At each step t , the LLM generates an intermediate reasoning output r_{t}\sim\rho_{\theta}(r_{t}\mid\mathcal{T},\mathcal{D},x,p,\mathcal{O}_{1},\dots,\mathcal{O}_{t-1}) and executes the plan step \mathcal{P}_{t} to obtain the observation \mathcal{O}_{t} . The final response is then generated as \mathcal{R}\sim\rho_{\theta}(\mathcal{R}\mid\mathcal{T},\mathcal{D},x,p,\mathcal{O}_{1},\dots,\mathcal{O}_{n}) . In later turns, a user may issue an irrelevant query requiring a completely new tool execution graph, or a dependent query that builds on partial outputs from earlier tool executions or responses. Additionally, some tools may return errors (e.g., timeouts), requiring unfinished execution paths from prior queries to be rescheduled. 2.2 Tool Execution as DAG Given a plan p generated by the LLM, we represent it as a directed graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , where \mathcal{V}=(v_{1},\dots,v_{n}) is the set of nodes and \mathcal{E}=(e_{1},\dots,e_{m}) is the set of edges. The node v_{1} corresponds to the user query, and v_{n} represents the final node that aggregates observations and returns the response. The intermediate nodes v_{2},\dots,v_{n-1} correspond to tool calls, each associated with an attribute that stores its tool payload in JSON format. An edge e_{i}\in\mathcal{E} denotes a dependency between two