Training LLMs for Multi-Step Tool Orchestration with Constrained Data Synthesis and Graduated Rewards

Cheng Jiayang; Xin Liu; Zhihan Zhang; Haoyang Wen; Zixuan Zhang; Qingyu Yin; Shiyang Li; Priyanka Nigam

cs.LGMar 25, 2026

Training LLMs for Multi-Step Tool Orchestration with Constrained Data Synthesis and Graduated Rewards

Authors: Cheng Jiayang, Xin Liu, Zhihan Zhang, Haoyang Wen, Zixuan Zhang, Qingyu Yin, Shiyang Li, Priyanka Nigam,

Organizations: Amazon Services Inc., Palo Alto, CA, USA. · Department of Computer Science and Engineering, HKUST, Hong Kong SAR, China. · School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA, USA.

Abstract

Multi-step tool orchestration remains challenging for LLMs, as state-of-the-art models frequently fail on full sequence execution due to parameter errors. Training for these workflows faces two obstacles: the lack of environments supporting complex real-world API dependencies, and sparse binary rewards that provide no signal for partial correctness. We propose a reinforcement learning framework addressing both challenges. First, we construct a deterministic environment backed by a large-scale cache of real API responses, enabling constrained synthesis of valid multi-step traces with controllable complexity. Second, we introduce a graduated reward that decomposes correctness into atomic validity (call-level correctness at increasing granularity) and orchestration consistency (correct sequencing with dependency respect). On ComplexFuncBench, our approach substantially improves turn accuracy, with ablations confirming both reward components are essential. Cross-benchmark evaluation on BFCL v4 shows that the learned orchestration skills transfer to entirely different API ecosystems (e.g., agentic web search and memory management), yielding consistent gains while maintaining stable single-step performance. Code is available at https://github.com/horizon-rl/ToolOrchestrationReward

Figures & tables

Figure 1: Framework overview using hotel booking as a running example. Phase 1 : Collect real API responses and curate workflow templates with dependency structures. Phase 2 : Sample cache entries following dependencies, then generate queries matching sampled parameters. Phase 3 : LLM interacts with the deterministic environment through multi-turn rollouts, receiving graduated rewards ( $R_{\text{atomic}}$ + $R_{\text{orch}}$ ) for GRPO updates.

Table 2

Model-LR	Zero-shot	SFT-3	SFT-10	GRPO-3	GRPO-10	SFT+GRPO-3	SFT+GRPO-10
Qwen3-8B-1e-6	34.4	32.6	31.7	36.4	30.2	31.1	29.9
Qwen3-8B-5e-6	–	–	–	28.7	29.6	22.9	28.4
Qwen2.5-7B-1e-6	13.4	11.5	13.5	25.8	23.9	27.1	16.0
Qwen2.5-7B-5e-6	–	–	–	24.1	21.3	16.5	12.1

Table 3: Training with Constrained Synthetic Data (Turn Acc %). Numbers in column headers indicate samples per workflow template (e.g., SFT-3 = SFT with 3 samples/template, GRPO-10 = GRPO with 10 samples/template). Evaluated on full 1000-sample test set.

			Web Search			Memory
Mode	Model	Overall	Agg.	Base	No Snip.	Agg.	KV	Vector	Rec. Sum.
FC	Qwen3-8B	10.5	3.5	5.0	2.0	17.4	8.4	13.6	30.3
FC	Qwen3-8B+Ours	16.1	10.5	13.0	8.0	21.7	13.6	15.5	36.1
Prompt	Qwen3-8B	10.1	7.0	5.0	9.0	13.1	4.5	7.1	27.7
Prompt	Qwen3-8B+Ours	15.4	10.0	11.0	9.0	20.9	6.5	16.1	40.0

Table 4: BFCL v4 Agentic category breakdown (%). Web Search and Memory are entirely different API ecosystems from the Booking.com training domain. +Ours denotes GRPO-3.

Model-LR	1	3	5	7
Qwen3-8B-1e-6	31.0	32.4	32.5	31.1
Qwen3-8B-5e-6	29.4	26.4	30.3	27.3
Qwen2.5-7B-1e-6	19.0	19.0	22.2	22.3
Qwen2.5-7B-5e-6	22.4	27.4	22.8	19.3

Table 5: Effect of Data Scale (Turn Acc %). Scale denotes target samples per workflow; actual totals are 67, 179, 283, 383.

Figure 2: Training dynamics under different reward configurations. Left :

R_{\text{atomic}}

only achieves high atomic validity but orchestration collapses. Middle :

R_{\text{orch}}

only achieves perfect orchestration but atomic validity drops. Right : Combined reward achieves balanced improvement.

Figure 3: Turn Accuracy (%) stratified by (a) dependency depth and (b) dependency pattern. Performance degrades with depth and for fan-out patterns. RL training provides consistent improvements across all stratifications.

Call-Level (among produced calls)
Error Type (%)	Zero	SFT	GRPO
Func. Selection Err	15.0	15.3	14.8
Parameter Err	18.7	18.2	16.5
Parameter-Level (given correct func.)
Query Param Err	14.7	15.8	12.7
Dep. Param Err	7.9	4.9	5.6

Table 6: Error analysis on ComplexFuncBench (Qwen3-8B). Call-level : among produced calls; param-level : given correct function; seq-level : why incomplete samples stopped.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Breakdown of

R_{\text{atomic}}

into AST validation (static) and semantic validation (execution).

R_{\text{orch}}

only training maintains

R_{\text{AST}}

but

R_{\text{sem}}

collapses, indicating syntactically valid but semantically broken calls.

Figure 5: Tool calling success metrics during training. Left : Tool calling success rate measures whether predicted calls match ground truth. Right : Tool executable rate measures whether calls execute without errors.

R_{\text{atomic}}

only achieves highest success rates, while

R_{\text{orch}}

only shows lower execution success despite high orchestration scores.

Figure 6: Training vs validation metrics for the Combined model. All three metrics (

R_{\text{atomic}}

R_{\text{orch}}

, Mean Reward) show consistent improvement on both training and validation sets, with a moderate generalization gap indicating some overfitting to the training distribution.

Type	Dist.	Zero-shot	GRPO-3	RL-Oracle
fallback_logic	5%	43.2	54.7	51.6
explicit_conj.	86%	34.9	35.8	43.6
alternative_opt.	4%	24.4	43.7	48.1
parallel_conj.	5%	21.5	18.1	23.6
Overall	–	34.4	36.4	43.4

Appendix

Table 7: Turn Accuracy (%) stratified by logical composition type. The dataset is dominated by explicit_conjunction (86%), with other patterns representing edge cases.

Domain	Zero-shot	SFT-3	GRPO-3
Attraction	49.8	57.9	60.7
Car-Rental	52.6	57.7	58.6
Hotels	25.4	22.6	29.0
Flights	33.4	29.4	33.6
Cross-domain	27.6	21.9	25.9
Overall	34.4	32.6	36.4

Appendix

Table 8: Turn Accuracy (%) by API domain. Single-domain tasks (Attraction, Car-Rental) are generally easier than cross-domain tasks. SFT degrades cross-domain performance while GRPO maintains or improves across all domains.

Mode	Model	Overall	Agentic	Multi-Turn	Live	Non-Live	Halluc.
FC	Qwen3-8B	41.6	10.5	41.6	80.4	88.8	80.5
FC	Qwen3-8B+Ours	43.4	16.1	40.2	80.8	86.4	81.8
Prompt	Qwen3-8B	38.7	10.1	31.6	80.1	89.3	82.4
Prompt	Qwen3-8B+Ours	39.5	15.4	27.8	78.8	89.8	81.6

Appendix

Table 9: BFCL v4 overall summary (%). FC = Function Calling; Prompt = Prompt mode.

Mode	Model	Overall	Base	Miss Func	Miss Param	Long Ctx
FC	Qwen3-8B	41.6	49.5	50.0	32.5	34.5
FC	Qwen3-8B+Ours	40.2	48.5	44.0	36.5	32.0
Prompt	Qwen3-8B	31.6	37.0	34.0	28.5	27.0
Prompt	Qwen3-8B+Ours	27.8	32.5	33.0	25.0	20.5

Appendix

Table 10: BFCL v4 Multi-Turn category breakdown (%).

Mode	Model	Overall	Simple	Multiple	Parallel	Par. Multi.
FC	Qwen3-8B	88.8	75.2	96.0	94.0	90.0
FC	Qwen3-8B+Ours	86.4	75.5	96.0	90.0	84.0
Prompt	Qwen3-8B	89.3	77.8	96.5	93.5	89.5
Prompt	Qwen3-8B+Ours	89.8	79.2	95.0	94.0	91.0

Appendix

Table 11: BFCL v4 Non-Live AST category breakdown (%).

Mode	Model	Overall	Simple	Multiple	Parallel	Par. Multi.
FC	Qwen3-8B	80.4	83.3	79.5	87.5	83.3
FC	Qwen3-8B+Ours	80.8	82.6	80.4	81.2	75.0
Prompt	Qwen3-8B	80.1	84.9	79.2	81.2	66.7
Prompt	Qwen3-8B+Ours	78.8	83.0	78.2	75.0	66.7

Appendix

Table 12: BFCL v4 Live AST category breakdown (%).

LLM Agent Orchestration

Large language model agent orchestration coordinates models, tools, and workflows to complete complex tasks reliably and efficiently.

See all 458 papers

Synthesize and Reward -- Reinforcement Learning for Multi-Step Tool Use in Live Environments
Jun 2, 2026Ibrahim Abdelaziz, Asim Munawar, Kinjal Basu +4Synthetic Data Generation Reinforcement Learning with Verifiable Rewards
IBM Research
Utility-Guided Agent Orchestration for Efficient LLM Tool Use
Mar 20, 2026Boyan Liu, Gongming Zhao, Hongli XuLLM Agent Orchestration LLM Tool Use
University of Science and Technology of China, Hefei, Anhui, China · Suzhou Institute for Advanced Research, University of Science and Technology of China
TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition
May 16, 2026Anay Kulkarni, ChiaEn Lu, Dheeraj Mekala +3Reward Modeling Reinforcement Learning with Verifiable Rewards
UC San Diego · Cisco Research

Jun 2, 2026J/K move · Enter open · S save

Synthesize and Reward -- Reinforcement Learning for Multi-Step Tool Use in Live Environments

Ibrahim Abdelaziz, Asim Munawar, Kinjal Basu, Maxwell Crouse+3

IBM Research

Synthetic Data Generation Reinforcement Learning with Verifiable Rewards LLM Agent Training Tool Use RL for Tool Use

Open paper AskPDF arXiv

Training LLMs to orchestrate multi-step tool calls is held back by three coupled obstacles: realistic stateful execution environments are costly to build, synthetic training queries are often detached from the server's actual state (so the generated tool calls fail to execute), and recall-based RL rewards incentivize verbose tool-calling patterns. We present PROVE (Programmatic Rewards On Verified Environments), a framework with three contributions: (1) a library of 20 stateful MCP (Model Context Protocol) servers exposing 343 tools, enabling live-execution RL training with session-scoped state isolation; (2) a state-machine data synthesis pipeline that generates multi-turn tool-call trajectories grounded in live-sampled server state, so generated queries reference entities that actually exist; and (3) a multi-component programmatic reward with an adaptive efficiency penalty that counters the verbosity incentive of recall-based rewards. We train four models (Qwen3-4B, Qwen3-8B, Qwen2.5-7B, Granite-4.1-8B) with GRPO on the resulting ~13K training examples. On BFCL Multi-Turn, tau2-bench, and T-Eval, PROVE yields improvements of up to +10.2, +6.8, and +6.5 points respectively, demonstrating that this framework yields consistent gains on multi-step tool orchestration across two model families.

Abstract

LLM Agent Orchestration

Explore similar work

Synthesize and Reward -- Reinforcement Learning for Multi-Step Tool Use in Live Environments

Utility-Guided Agent Orchestration for Efficient LLM Tool Use

TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition