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.
Method
GSM8K
MATH
HotpotQA
MMLU-Pro
MBPP+
HumanEval+
Avg.
AVG-R
Single-agent methods
Vanilla
48.58 ± 1.70
47.48 ± 2.51
76.53 ± 2.69
61.83 ± 1.87
75.40 ± 2.34
81.21 ± 2.27
65.17
10.67
CoT
71.58 ± 1.76
48.44 ± 1.27
76.32 ± 1.68
73.17 ± 1.81
76.32 ± 2.11
83.94 ± 1.13
71.63
8.17
Multi-agent collaboration
AgentVerse
73.08 ± 1.03
51.77 ± 1.00
77.36 ± 0.77
71.98 ± 1.76
74.60 ± 2.02
82.12 ± 1.13
71.82
8.00
DyLAN
75.83 ± 1.96
52.93 ± 1.67
76.84 ± 2.14
75.48 ± 1.85
77.51 ± 1.78
85.76 ± 0.86
74.06
3.50
Table 1: Main results with gpt-4o-mini , reported as mean ± std over three runs. Bold marks the best and underline the runner-up. AVG-R is the average rank (lower is better).
Figure 3: Transferability of the learned policy, for the top-5 methods on representative benchmarks.
Figure 5
Figure 5: Sensitivity analysis of ASPO hyperparameters over three 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 τb
Mathematical reasoning
GSM8K
0.692
0.545
MATH
0.609
0.494
General question answering
HotpotQA
0.656
0.520
MMLU-Pro
0.647
0.520
Code generation
HumanEval+
0.727
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 δ
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.
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.
Zhi Hong, Qian Zhang, Jiahang Sun +5
The Chinese University of Hong Kong, Shenzhen · South China University of Technology · Ritsumeikan University +1
Large language model (LLM)-based Multi-agent systems (MAS) have shown promise in tackling complex collaborative tasks, where agents are typically orchestrated via role-specific prompts. While the quality of these prompts is pivotal, jointly optimizing them across interacting agents remains a non-trivial challenge, primarily due to the misalignment between local agent objectives and holistic system goals. To address this, we introduce MASPO, a novel framework designed to automatically and iteratively refine prompts across the entire system. A core innovation of MASPO is its joint evaluation mechanism, which assesses prompts not merely by their local validity, but by their capacity to facilitate downstream success for successor agents. This effectively bridges the gap between local interactions and global outcomes without relying on ground-truth labels. Furthermore, MASPO employs a data-driven evolutionary beam search to efficiently navigate the high-dimensional prompt space. Extensive empirical evaluations across 6 diverse tasks demonstrate that MASPO consistently outperforms state-of-the-art prompt optimization methods, achieving an average accuracy improvement of 2.9. We release our code at https://github.com/wangzx1219/MASPO.
Zhexuan Wang, Xuebo Liu, Li Wang +4
Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China.
While Multi-Agent Systems (MAS) empower Large Language Models to tackle complex reasoning tasks through collaborative interaction, optimizing their dynamics remains a formidable challenge due to the discrete, non-differentiable nature of the computation graph and the sparsity of global supervisory signals. Existing black-box optimizers struggle to attribute trajectory-level failure to specific local components, resulting in inefficient, high-variance exploration. We argue that tractable MAS optimization needs structural inductive biases to disentangle error signals. We propose temporal and structural credit assignment, which decomposes the objective along two axes: (i) temporal credit, using state-space bottlenecks to identify critical rounds, and (ii) structural credit, using stationary role policies to isolate agent contributions. Leveraging these decomposed signals, we introduce a discrete, verbalized block coordinate descent algorithm for iterative refinement. Rather than indiscriminate global updates, it alternates between optimizing role prompts and aggregation protocols, using LLM-generated "proxy gradients" to target only the identified weak links. Across diverse reasoning benchmarks, our approach substantially reduces query complexity while improving performance, providing a principled and interpretable path toward self-improving MAS.
Wenwu Li, Yuran Song, Mingze Zhao +2
Tongji University, Shanghai, China · The University of Hong Kong, Hong Kong, China