TLDR: OrchDAG is a synthetic data generation pipeline that models complex multi-turn LLM tool execution as Directed Acyclic Graphs (DAGs). It provides a challenging benchmark and introduces a graph-based reward (using Graph Edit Distance) for reinforcement learning, which significantly improves LLM performance in orchestrating tools by accounting for structural dependencies and providing denser feedback.
Large Language Models (LLMs) are becoming increasingly capable, moving beyond simple text generation to act as dynamic agents that can plan and use tools. While tool use is a significant advancement, most current approaches struggle with the complexities of multi-turn interactions, where an agent might need to perform a series of interconnected actions over time.
To address this challenge, researchers Yifu Lu, Shengjie Liu, and Li Dong have introduced OrchDAG, a novel synthetic data generation pipeline. This pipeline is designed to model complex tool execution as Directed Acyclic Graphs (DAGs), allowing for controllable complexity. The goal is to create a challenging yet solvable benchmark for evaluating and improving LLM performance in multi-turn tool use scenarios. You can read the full research paper here.
Understanding the Challenge of Multi-Turn Tool Use
In real-world applications, LLM agents often face intricate tool interactions. These complexities arise from several factors: tools can have elaborate dependencies, their outputs are often detailed JSON files, and a key output from one tool might be an input for another, but with different field names (schema misalignment). Furthermore, in multi-turn settings, tools might encounter errors or timeouts, requiring the agent to adapt and reschedule tasks.
Existing work has explored various aspects of LLM planning and tool use, from parallel execution with LLM Compiler to leveraging pseudo-Python code for reasoning. However, OrchDAG specifically focuses on generating data that captures the nuanced dependencies and potential failures inherent in complex, multi-turn tool orchestration.
How OrchDAG Works
The OrchDAG pipeline generates synthetic multi-turn data where each round of tool execution for a user query is represented as a DAG. The complexity of these DAGs can be precisely controlled through hyperparameters. The pipeline incorporates several key principles to reflect real-world scenarios:
- Controllable complexity of the tool execution DAG.
- Inclusion of irrelevant tools in the system prompt to train models to select only relevant ones.
- Tools with multiple output fields, often four or five.
- Schema misalignment, where an output field from one tool serves as an input to another with a different name.
Crucially, OrchDAG extends to multi-turn settings by simulating scenarios like completely irrelevant follow-up queries, dependent queries that build on previous outputs, or tool execution errors (e.g., timeouts). This allows for a comprehensive evaluation of an agent’s ability to adapt and replan.
A New Reward System for Better Training
One of OrchDAG’s significant contributions is a graph-based reward system designed to enhance Reinforcement Learning with Verifiable Reward (RLVR) training. Traditional reward signals can be sparse in complex tool interactions, meaning the model doesn’t get much feedback for partially correct actions. OrchDAG addresses this by using a weighted Graph Edit Distance (GED) as a reward signal.
This GED-based reward measures the “distance” between the predicted tool execution DAG and the ground-truth DAG. By doing so, it provides denser rewards, giving credit to LLMs for correctly predicting partial dependencies and improving the overall structure of the plan, even if the entire plan isn’t perfect initially. This approach is particularly effective when combined with GRPO-style algorithms.
Experimental Insights
Experiments with the OrchDAG dataset revealed that it presents a challenging but solvable benchmark. Advanced models like GPT-4o and Claude 4 showed some ability to predict the correct DAG, while other models struggled, highlighting the dataset’s difficulty. The research also demonstrated that the proposed graph-based reward significantly improves model performance, especially when increasing the number of training steps and rollouts in reinforcement learning.
The multi-turn experiments further underscored the challenges, with performance decreasing in scenarios requiring cross-turn dependencies or handling tool errors. This emphasizes the need for robust planning and adaptation capabilities in LLM agents for real-world, dynamic environments.
Also Read:
- AI Agents Get Smarter: A Graph-Based Approach to Understanding Complex Tools
- PIPS: Enhancing LLM Reasoning Through Dynamic Program Synthesis
Looking Ahead
OrchDAG highlights the critical importance of leveraging the topological structure of tool execution graphs and managing data complexity in multi-turn tool use. While the current framework effectively models explicit dependencies, future work aims to extend it to scenarios involving implicit dependencies, such as file operations in computer-use tasks, further pushing the boundaries of agentic LLM capabilities.
