OrchDAG: Complex Tool Orchestration in Multi-Turn Interactions with Plan DAGs

Agentic tool use has gained traction with the rise of agentic tool calling, yetmost existing work overlooks the complexity of multi-turn tool interactions. Weintroduce OrchDAG, a synthetic data generation pipeline that models tool executionas directed acyclic graphs (DAGs) with controllable complexity. Using this dataset,we benchmark model performance and propose a graph-based reward to enhanceRLVR training. Experiments show that the dataset presents a challenging butsolvable benchmark, and the proposed reward is effective when combined withGRPO-style algorithms, highlighting the importance of leveraging topologicalstructure and data complexity in multi-turn tool use.