Multi-Agent System Search via Active Substructure-aware Policy Optimization

Beicheng Xu; Bowen Fan; Weitong Qian; Lingching Tung; Bin Cui

cs.AISep 26, 2026

Multi-Agent System Search via Active Substructure-aware Policy Optimization

Authors: Beicheng Xu, Bowen Fan, Weitong Qian, Lingching Tung, Bin Cui

Organizations: School of CS, Peking University, Beijing, China

Abstract

LLMs enable multi-agent systems (MAS) to tackle complex tasks, but manually designing agent roles, prompts, and communication structures requires substantial expertise and effort. This motivates learning policies that construct query-specific MAS from execution reward. Existing approaches typically train these policies by repeatedly traversing a fixed set of training queries and assigning rewards at the workflow level. However, this overlooks differences in queries' evolving learning potential and obscures which substructures improve solution quality. In this paper, we propose Active Substructure-aware Policy Optimization (ASPO), a RL framework for query-level MAS search. ASPO introduces an Adaptive Query-Selection Mechanism (AQSM) that focuses training on queries at the policy's competence boundary: those it can solve but not yet reliably. A complementary discovery mechanism widens architectural exploration for hard queries, helping distinguish insufficient exploration from operator capability limits. Beyond query selection, ASPO introduces substructure-level rewards that measure output-quality gains within each action's descendant subgraph. These rewards guide proximal policy optimization to reinforce useful architectural refinements and discourage redundant or harmful computation. Together, these mechanisms prioritize learnable queries and provide fine-grained feedback for learning effective MASs. Across six benchmarks spanning mathematical reasoning, general question answering, and code generation, ASPO ranks first on every benchmark against twelve baselines.

Figures & tables

Figure 1: Query-level outcomes and group-wise accuracy on MATH, evaluated on the full training set after each training epoch, with and without AQSM. Queries are grouped by their outcomes without AQSM during warm-up (epochs 1–3): easy (3/3 correct), medium (1–2/3), and hard (0/3).

Figure 2: Overview of ASPO. (A) AQSM uses execution feedback to select queries and allocate rollouts. (B) The policy constructs query-specific MASs and learns from substructure-level rewards.

Single-agent methods
Method	GSM8K	MATH	HotpotQA	MMLU-Pro	MBPP+	HumanEval+	Avg.	AVG-R
Vanilla	48.58 $\pm$ 1.70	47.48 $\pm$ 2.51	76.53 $\pm$ 2.69	61.83 $\pm$ 1.87	75.40 $\pm$ 2.34	81.21 $\pm$ 2.27	65.17	10.67
CoT	71.58 $\pm$ 1.76	48.44 $\pm$ 1.27	76.32 $\pm$ 1.68	73.17 $\pm$ 1.81	76.32 $\pm$ 2.11	83.94 $\pm$ 1.13	71.63	8.17
Multi-agent collaboration
AgentVerse	73.08 $\pm$ 1.03	51.77 $\pm$ 1.00	77.36 $\pm$ 0.77	71.98 $\pm$ 1.76	74.60 $\pm$ 2.02	82.12 $\pm$ 1.13	71.82	8.00
DyLAN	75.83 $\pm$ 1.96	52.93 $\pm$ 1.67	76.84 $\pm$ 2.14	75.48 $\pm$ 1.85	77.51 $\pm$ 1.78	85.76 $\pm$ 0.86	74.06	3.50

Table 1: Main results with gpt-4o-mini , reported as mean

\pm

std over three runs. Bold marks the best and underline the runner-up. AVG-R is the average rank (lower is better).

Panel of Figure 3 — Figure 3: Transferability of the learned policy, for the top-5 methods on representative benchmarks.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Task family	Train	Test	Total	Metric
GSM8K	Math	$200$	$400$	$600$	Accuracy
MATH	Math	$210$	$490$	$700$	Accuracy
HotpotQA	General QA	$210$	$420$	$630$	F1
MMLU-Pro	General QA	$210$	$420$	$630$	Accuracy
MBPP+	Coding	$126$	$252$	$378$	pass@1
HumanEval+	Coding	$54$	$110$	$164$	pass@1

Appendix

Table 3: Curated train/test sample counts and evaluation metrics across benchmarks.

Domain	Benchmark	Spearman	Kendall $\tau_{b}$
Mathematical reasoning	GSM8K	$\mathbf{0.692}$	$\mathbf{0.545}$
	MATH	$0.609$	$0.494$
General question answering	HotpotQA	$\mathbf{0.656}$	$0.520$
	MMLU-Pro	$0.647$	$0.520$
Code generation	HumanEval+	$\mathbf{0.727}$	$\mathbf{0.562}$
	MBPP+	$0.617$	$0.468$

Appendix

Table 4: Rank correlation between each benchmark’s method ordering and the overall ordering across all six benchmarks. Bold marks the benchmark selected for each domain.

Hyperparameter	Value	Sensitivity Analysis
Adaptive Query-Selection Mechanism (AQSM)
Posterior discount $\delta$	$0.9$	Section 4.6 , Figure 5(a)
Discovery samples $K$	$3$	Section 4.6 , Figure 5(a)
Substructure-aware Optimization
Maximum number of layers	$5$	Appendix D.6 , Figure 8
Maximum number of children per node	$2$	Appendix D.6 , Figure 8

Appendix

Table 5: ASPO hyperparameter settings grouped by component, with references to the corresponding sensitivity analyses.

Figure 6: Cost–performance trade-offs on GSM8K, HotpotQA, and HumanEval+. The top and bottom rows show training and inference costs, respectively, against the same final test performance: accuracy, F1, and pass@1 for the three columns. Costs are in USD, with separate axis ranges and bubble-size scales for each panel. Dashed lines indicate the observed Pareto frontiers. Vanilla, CoT, and AgentVerse incur no training cost and are omitted from the top row.

Multi-Agent LLM Systems

Multi-agent large language model systems coordinate multiple AI agents to solve tasks through communication, specialization, shared tools, and memory.

See all 1,050 papers

MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks
Mar 3, 2026Zhi Hong, Qian Zhang, Jiahang Sun +5Multi-Agent LLM Systems Multi-Agent System Optimization
The Chinese University of Hong Kong, Shenzhen · South China University of Technology · Ritsumeikan University +1
MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems
May 7, 2026Zhexuan Wang, Xuebo Liu, Li Wang +4Multi-Agent LLM Systems Multi-Agent System Optimization
Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China.
Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization
May 28, 2026Wenwu Li, Yuran Song, Mingze Zhao +2Multi-Agent LLM Systems Multi-Agent System Optimization
Tongji University, Shanghai, China · The University of Hong Kong, Hong Kong, China

Mar 3, 2026J/K move · Enter open · S save

MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks

Zhi Hong, Qian Zhang, Jiahang Sun, Zhiwei Shang+4

The Chinese University of Hong Kong, Shenzhen · South China University of Technology · Ritsumeikan University+1

Multi-Agent LLM Systems Multi-Agent System Optimization

Open paper AskPDF arXiv

Large Language Models (LLMs) have achieved great success in many real-world applications, especially the one serving as the cognitive backbone of Multi-Agent Systems (MAS) to orchestrate complex workflows in practice. Since many deployment scenarios preclude MAS workflow modifications and its performance is highly sensitive to the input prompts, prompt optimization emerges as a more natural approach to improve its performance. However, real-world prompt optimization for MAS is impeded by three key challenges: (1) the need of sample efficiency due to prohibitive evaluation costs, (2) topology-induced coupling among prompts, and (3) the combinatorial explosion of the search space. To address these challenges, we introduce MASPOB (Multi-Agent System Prompt Optimization via Bandits), a novel sample-efficient framework based on bandits. By leveraging Upper Confidence Bound (UCB) to quantify uncertainty, the bandit framework balances exploration and exploitation, maximizing gains within a strictly limited budget. To handle topology-induced coupling, MASPOB integrates Graph Neural Networks (GNNs) to capture structural priors, learning topology-aware representations of prompt semantics. Furthermore, it employs coordinate ascent to decompose the optimization into univariate sub-problems, reducing search complexity from exponential to linear. Extensive experiments across diverse benchmarks demonstrate that MASPOB achieves state-of-the-art performance, consistently outperforming existing baselines.

Abstract

Multi-Agent LLM Systems

Explore similar work

MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks

MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems

Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization