Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.32430 · 0 citations · 68 references
Computer Science

TL;DR

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, and introduces substructure-level rewards that measure output-quality gains within each action's descendant subgraph.

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.

View source

Similar papers

#machine learning Preprint Oct 2026

Dynamic Harness Search: Building Multi-Agent Systems Per-Query via Prediction

This work introduces SHIFT, which moves execution out of the per-query search loop and shows that choosing structure, instructions, and tools jointly beats choosing only instructions or only tools by up to 9.1 percentage points, and that learned value selection identifies more accurate harnesses with lower execution co...

Som Sagar, Sha-Sha Li, He-Jie Cui et al. · 0 citations

Beyond Scripted Search: Sample-Efficient Reward Discovery via Agentic Black-box Optimization

An Agentic Reward Black-box Optimization (ARBO) framework is proposed, in which an LLM agent builds the search strategy at run time from an evaluation history maintained as its persistent workspace, which comprises two components: observations maintained by the evaluation oracle and an agent-maintained belief that reco...

Ming-Hao Li, Rui Tan, Rui-Hang Wang · 1 citation
#natural language process... Preprint Oct 2026

Harness-Search: Guiding Long-Horizon Search through Multi-Agent Coordination

Harness-Search is introduced, a multi-agent search harness to reduce the local errors propagating across subsequent exploration, evidence curation, and termination decisions, and improves both retrieval and answer generation under the same policy backbone.

Shanyong Wang, Zhen-Wen Ji, Lei Jin et al. · 0 citations
#natural language process... Preprint Oct 2026

Programmatic Search Agents: Extending Agentic Search Beyond Query Reformulation

The introduced Programmatic Search Agent (PSA), which makes a local executable computation over candidates the unit of a search action, unifies a persistent candidate workspace, flexible primitive composition, and selective evidence presentation.

Jia-Ming Qian, Hui-Yan Yang, Man-Di Liu et al. · 0 citations
Preprint Aug 2026

PlanPO: Group Planning-Aware Policy Optimization for Multi-Turn Agentic LLMs

Group Planning-aware Policy Optimization (PlanPO) is proposed, a simple yet effective RL method for learning generalizable planning abilities beyond task-specific high-quality behavior patterns that enables agents to actively learn generalizable and deliberate behaviors spanning interaction planning and textual generat...

D. Liang, Liyuan He, Xuan Feng et al. · 0 citations

MAS-OPD: On-Policy Distillation for Multi-agent Systems

MAS-OPD is presented, where Role-Advantage Specialization defines the role advantage as the difference between the teacher signals under target and non-target role conditions, and Privileged Attribution for Coordination attributes an interaction conflict to its source and supplies it to the teacher alone as privileged...

Qi-Yong Zhong, Mao Zheng, Ming-Yang Song et al. · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.