ParaAgent: Reinforcing Parallel Acting in Open-World Tool Environments

Shengbin Yue; Hongru Wang; Siyuan Wang; Xiaoxin Chen; Wei Chen; Zhongyu Wei

cs.AISep 27, 2026

ParaAgent: Reinforcing Parallel Acting in Open-World Tool Environments

Authors: Shengbin Yue, Hongru Wang, Siyuan Wang, Xiaoxin Chen, Wei Chen, Zhongyu Wei

Organizations: Fudan University · University of Edinburgh · Chinese University of Hong Kong · Vivo AI · Huazhong University of Science and Technology · Shanghai Innovation Institute

Abstract

Language model agents are increasingly deployed in open-world tool environments, which require balancing exploring unknown capabilities and exploiting known ones. Existing methods face a performance-efficiency tradeoff: they either rigidly decouple exploration and execution or interleave them without coordination. We argue that the key lies not in whether to decouple or interleave them, but in how to coordinate them across granularities. We introduce ParaAct, a structured parallel-action loop that combines phase-level Exploration $\rightleftharpoons$ Execution with action-level parallelism. To learn this loop, ParaAgent combines multi-agent cold-start demonstrations with reinforcement learning under multi-level advantage decoupling, making planning structure explicit and supervising it with step-, phase-, and trajectory-level rewards. Learning is supported by our ToolEnv, a scalable simulator grounded in 50,011 realistic tool interfaces. On two open-world tool benchmarks, ParaAgent-4B achieves the best average success among all baselines, including GPT-4.1 systems, with the largest gains on multi-tool tasks. Behavioral analyses show that these gains stem from this action organization, highlighting its importance for capable and efficient open-world agents.

Figures & tables

Figure 1: Agent paradigms and their performance–efficiency tradeoff. (A) Exploration-then-Execution (P1) rigidly decouples exploration and execution, while native Exploration-and-Execution (P2) interleaves them without coordination. Ours separate phase-level adaptation from action-level coordination. (B) Task success (Pass@1) versus average interaction rounds per task for different agents on ToolBench and API-Bank.

Figure 2: Overview of ParaAgent . Middle : The agent generates rollouts in ToolEnv through a structured parallel-action loop. Top : A hierarchical reward provides supervision at step, phase, and trajectory levels, optimizing policy $\pi$ via decoupled three advantages. Bottom : ToolEnv is an open-world environment comprising a real-world tool library, retriever, and three-layer simulator.

Figure 3: (a) Statistics of

\mathcal{G}_{\text{dep}}

, with required hard dependencies and non-mandatory soft orderings. (b) Top 10 of 52 categories by tool count in a long-tailed library.

Exploration-then-Execution
		ToolBench								API-Bank
		I1		I2		I3		Avg
Action	Backbone	Suc.	Path	Suc.	Path	Suc.	Path	Suc.	Path	Suc.	Acc.
ReAct	GPT-4.1	43.2	28.9 $\pm$ 0.4	29.6	17.3 $\pm$ 1.2	29.5	10.2 $\pm$ 2.4	34.1	18.8 $\pm$ 0.3	20.0	44.3 $\pm$ 1.1
[2pt/2pt] DFS	GPT-4.1	45.1	29.2 $\pm$ 0.3	28.7	17.4 $\pm$ 1.3	27.9	9.6 $\pm$ 2.1	33.9	18.7 $\pm$ 0.2	20.0	45.4 $\pm$ 0.5
[2pt/2pt] DFS	T-LLaMA 7B	15.6	32.7 $\pm$ 0.4	6.5	21.0 $\pm$ 0.1	11.5	12.5 $\pm$ 0.6	11.2	22.1 $\pm$ 0.3	2.0	21.4 $\pm$ 0.0

Table 1: Main results across paradigm

\times

action strategy. Suc.: Pass@2 (%). Path: mean

\pm

sample SD (%). Cell shading marks the best , second , and third per column.

Figure 5: Action behavior per task. Above zero: calls (%: hits/calls; API-Bank uses exact match). Below zero: searches (%: gold-API coverage). Two-run means.

Method	Suc.	Path	Suc.	Acc.
	ToolBench		API-Bank
Backbone	22.13	23.49	16.00	35.88
+ SFT	31.90	37.54	20.00	43.51
[2pt/2pt] + SFT & RL(GRPO)	47.02	46.51	14.00	52.67
+ SFT & RL (Ours)	49.66	42.54	24.00	58.02

Table 2: Ablation analysis of learning strategies and hierarchical reward . Suc.: Pass@1 (%); Acc.: API accuracy (%); Turns and Tok. (output, k): averaged over both benchmarks.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Table 7

Figure 6: Category distribution of the ToolEnv tool library (50,011 tools across all 52 categories), sorted by tool count. The four largest categories (Sports, Data, Finance, Social) cover

\sim

41% of the library. Our tool library reflects the breadth of the open-world tool space.

Name	API lib.	Raw pairs	Cleaned pairs	# API	Category	Source
API calling
ToolBench ( Qin et al., 2024 )	37,366	149,693	105,877	9,483	50	RapidAPI
APIGen ( Liu et al., 2024 )	25	20,728	9,962	25	10	RapidAPI, OpenAPI Hub
ToolACE ( Liu et al., 2025 )	2,562	1,353	445	1,260	49	Public API hubs
Simia ( Li et al., 2025d )	26	310,870	10,000	26	2	Public API hubs
MCP server

Appendix

Table 5: Details of ToolEnv SFT data. API lib. is the number of distinct tool/API entries contributed by the source; Raw pairs is the number of raw request–response pairs before deduplication and cleaning; Cleaned pairs is the count retained after the cleaning, alignment, and LLM-completion pipeline; # API is the distinct API count retained; Category is the number of vertical categories covered.

Hyperparameter	Value
Max rounds per task ( $T_{\max}$ )	12
Retrieval top- $k$ per capability slot	3
Simulator error-injection rate	5%
LLM decoding temperature (all agents)	0.7
Max tokens per agent call	2,048

Appendix

Table 6: Multi-agent trajectory generation hyperparameters.

Symbol	Scope	Value	Role
$\lambda_{\tau}$	Eq. 7	$1.0$	trajectory-advantage weight
$\lambda_{p}$	Eq. 7	$0.5$	phase-advantage weight
$\lambda_{s}$	Eq. 7	$0.25$	step-advantage weight
$w_{1}$	$R_{\text{phase}}$	$0.1$	L1 retrieval grounding
$w_{2}$	$R_{\text{phase}}$	$0.2$	L2 dependency declaration
$w_{3}$	$R_{\text{phase}}$	$0.2$	L3 layered plan

Appendix

Table 7: Reward coefficients used in all experiments. The phase weights

w_{1},\ldots,w_{4}

sum to

1

;

R_{\text{step}}

weights its two scores equally (Eq. 4 ) and has no further coefficient.

State	Condition	Credited behavior	$r_{\text{plan}}$
Need	no controller, or DAG exhausted	emit a valid plan	$1$ , else $0$
May	new observation or recoverable failure	no plan, or a valid new plan	$1$ , else $0$
No	no new information	no plan	$1$ ; repeated plan: $0$
Answer	final answer step	no <plan>	$0$

Appendix

Table 8: Plan score

r_{\text{plan}}^{(s)}

by controller state.

r_{\text{base}}^{(s)}

is checked in every state.

Q/F/U pattern	$000$ , $010$ , $100$	$001$ , $101$	$011$ , $110$	$111$
$R_{\text{ans}}$	$-0.5$	$0$	$0.5$	$1.5$
Meaning	insufficient evidence; not both complete and faithful	sufficient evidence, but unfaithful claims	faithful, but incomplete or under-evidenced	complete, faithful, and well-evidenced

Appendix

Table 9: Answer reward

R_{\text{ans}}

by Q/F/U pattern (Quality, Faithfulness, Utility). A bit is

1

if the judge verdict is YES and

0

otherwise ( PARTIAL or NO ). For example,

010

is a faithful answer that is incomplete and lacks sufficient tool evidence, such as an honest report that the tools failed.

Judge model	Quality	Faithfulness	Utility
Qwen3.6-27B	89.0%	76.0%	78.0%
Qwen3-235B-A22B-Instruct-2507 (deployed)	89.0%	83.0%	81.0%

Appendix

Table 10: Answer-judge accuracy across judge models on a shared set of 100 human-annotated gold trajectories (temperature

0

, single-call prompt). Each verdict is binarized as YES versus PARTIAL / NO , matching the strict projection used by

R_{\text{ans}}

during training.

Explore similar work

Small Model as Master Orchestrator: Learning Unified Agent-Tool Orchestration with Parallel Subtask Decomposition
Apr 18, 2026Wenzhen Yuan, Wutao Xiong, Fanchen Yu +7Multi-Agent Orchestration Orchestration
Shanghai Jiao Tong University · Sichuan University · Shanghai AI Lab +2
AnyAct: Universal Action for Self-Evolving Agents
Sep 29, 2026Lingrui Xu, Yangqin Jiang, Jiachang Zhang +2Self-Evolving Agents Action Space
The University of Hong Kong
Can Agents Generalize to the Open World? Unveiling the Fragility of Static Training in Tool Use
Jul 1, 2026Song-Lin Lv, Weiming Wu, Rui Zhu +2Open-World Supervised Finetuning
School of Intelligence Science and Technology, Nanjing University, Nanjing, China · National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

Apr 18, 2026, cs.AIJ/K move · Enter open · S save

Small Model as Master Orchestrator: Learning Unified Agent-Tool Orchestration with Parallel Subtask Decomposition

Wenzhen Yuan, Wutao Xiong, Fanchen Yu, Shengji Tang+6

Shanghai Jiao Tong University · Sichuan University · Shanghai AI Lab+2

Multi-Agent Orchestration Orchestration Multi-Stage Training Small Models

Open paper AskPDF arXiv

Multi-agent systems (MAS) demonstrate clear advantages in tackling complex problems by coordinating diverse agents and external tools. However, most existing orchestration methods rely on static workflows or serial agent scheduling, and are further constrained by heterogeneous interface protocols between tools and agents. This leads to high system complexity and poor extensibility. To mitigate these issues, we propose Agent-as-Tool, a unified parallel orchestration paradigm that abstracts both agents and tools into a standardized, learnable action space with protocol normalization and explicit state feedback. Building on this paradigm, we train a lightweight orchestrator, ParaManager, which decouples planning decisions from subtask solving, enabling state-aware parallel subtask decomposition, delegation, and asynchronous execution. For training, we adopt a two-stage ParaManager training pipeline. It improves robustness by incorporating supervised fine-tuning (SFT) trajectories equipped with recovery mechanisms, and further applies reinforcement learning (RL) to achieve an optimal balance among task success, protocol compliance, diversity, and reasoning efficiency. Experiments show that ParaManager achieves strong performance across multiple benchmarks and exhibits robust generalization under unseen model pools.

Abstract

Explore similar work

Small Model as Master Orchestrator: Learning Unified Agent-Tool Orchestration with Parallel Subtask Decomposition

AnyAct: Universal Action for Self-Evolving Agents

Can Agents Generalize to the Open World? Unveiling the Fragility of Static Training in Tool Use