PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.32430v1cs.AI

TL;DR

Query-level MAS policies need useful execution feedback, but fixed query schedules and workflow-level rewards do not target evolving query learnability or local substructure contributions. ASPO combines adaptive query selection and localized rewards for policy optimization. It ranks first against twelve baselines on all six benchmarks.

  • Problem

    Existing query-level MAS policies typically revisit fixed training queries and use workflow-level rewards, overlooking queries’ evolving learning potential and which substructures improve solution quality.

    Source: §1 · pp. 2–3

  • Method

    ASPO uses AQSM to prioritize queries at the policy’s competence boundary, explores additional rollouts for unsolved queries, and optimizes the MAS policy with substructure-level rewards.

    Source: §1 · p. 3

  • Results

    ASPO ranks first on every benchmark against twelve baselines across six benchmarks spanning mathematical reasoning, general question answering, and code generation.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    ASPO retains its advantage across task domains and LLM backbones, while its ablations validate both components and cost analyses show favorable performance–cost trade-offs.

    Source: §5 · p. 10

    ASPO relies on reference solutions and task evaluators for training feedback, limiting direct application where reliable references or success criteria are unavailable.

    Source: B LIMITATIONS AND FUTURE WORK · p. 15

Abstract

from arXiv · show

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.

1 INTRODUCTION

Existing query-level MAS policies learn from execution feedback, but fixed query schedules and workflow-level rewards may provide poorly targeted learning signals. ASPO addresses these gaps with adaptive query selection and substructure-level rewards.

1 INTRODUCTION

  • Prior MAS automation includes task-level search for a reusable domain workflow and query-level methods that select agents, adapt communication graphs, or generate MASs.The cited approaches include prompted construction, supervised fine-tuning, preference optimization, and reinforcement learning.Source: §1 · pp. 1–2
  • The paper frames its central question as whether execution feedback identifies informative queries and the substructures that contribute to successful execution.Existing reward-driven approaches commonly revisit fixed training queries and optimize policies with workflow-level feedback.Source: §1 · pp. 2–3
  • Uniformly revisiting 90 of 210 MATH queries that were always solved and 54 that were never solved can consume budget while providing little correctness-based feedback.The study reports 66 queries with both correct and incorrect outcomes across six epochs.Source: §1 · p. 2
  • Workflow-level rewards may reinforce unnecessary steps in successful workflows or overlook useful steps in failed ones, motivating finer-grained credit assignment.Across L1-to-L5 transitions, ASPO's answer-quality gains were +0.033, +0.030, +0.024, and +0.018; MaAS's gains over its first three transitions were +0.026, +0.005, and +0.012, followed by a 0.011 drop from L4 to L5.Source: §1 · p. 3
  • 74.3% overall accuracy with AQSM versus 59.5% without it; medium-query accuracy was 82.6% versus 60.9%, and hard-query accuracy was 34.8% versus 8.7%.Without AQSM, overall accuracy rose from 59.0% to 59.5% after warm-up; AQSM maintained high accuracy on easy queries.Source: §1 · p. 3
  • ASPO combines AQSM, which prioritizes queries at the policy’s competence boundary and explores additional rollouts for unsolved queries, with localized substructure rewards for PPO.The discovery mechanism retains useful trajectories to avoid mistaking insufficient exploration for inability.Source: §1 · p. 3

2 PROBLEM FORMULATION

The formulation represents a MAS as a graph of operators and learns a policy that constructs query-conditioned graphs to maximize task utility. The stated focus is extracting informative feedback under a limited budget.

2 PROBLEM FORMULATION

  • A MAS is represented as a directed acyclic graph whose nodes instantiate operators and whose edges specify output flow.The search space is defined through a pool of agentic operators, each specifying an LLM-based operation for generating or refining a response.Source: §2 · p. 3
  • Executing a graph on a training query produces intermediate responses and a final answer, paired with a reference answer in the training set.Source: §2 · p. 3
  • The architectural policy selects operators and connections conditioned on the query and current partial graph, aiming to maximize expected task utility over valid graphs.The formulation highlights extracting more informative training feedback under a limited budget.Source: §2 · p. 3

3 METHOD

ASPO trains a query-level MAS-construction policy using adaptive query selection and action-specific substructure returns. The policy builds a MAS through graph-expansion actions, and the resulting execution feedback guides both query selection and PPO updates.

3.1 POLICY-GUIDED MAS CONSTRUCTION

  • A GCN-based state encoder represents the query and partial graph, while the policy expands parent nodes by selecting child counts and compatible operators.Construction proceeds layer by layer until no operator node remains available or the construction budget is exhausted; leaf outputs are aggregated into the final answer.Source: §3.1 · pp. 4–5

3.2 SUBSTRUCTURE-AWARE POLICY OPTIMIZATION

  • Each action receives a return from quality improvements in its descendant subgraph, which guides PPO updates.The method accounts for downstream refinements and execution cost; more distant returns are discounted, and incremental cost is weighted.Source: §3.2 · p. 5

3.3 ADAPTIVE QUERY-SELECTION MECHANISM

  • AQSM estimates each query’s success probability with a discounted Beta posterior and prioritizes queries whose sampled success probability is near 0.5.After warm-up, queries are sampled in proportion to their scores; discovery mode collects additional rollouts for queries never previously answered correctly and retains trajectories with a correct answer or a positive substructure advantage.Source: §3.3 · p. 6

3.4 OVERALL ALGORITHM

  • After warm-up, AQSM selects queries and activates discovery for sampled queries never solved; the policy constructs and executes MASs using substructure rewards for PPO updates.At inference, the trained policy constructs a MAS tailored to each query.Source: §3.4 · p. 6

4 EXPERIMENTS

ASPO is evaluated on six benchmarks across three domains against twelve baselines, with transfer, cost, ablation, and sensitivity analyses. It ranks first on every benchmark, and the analyses examine its transferability, efficiency, components, and hyperparameters.

4.1 EXPERIMENTAL SETUP

  • The evaluation covers six benchmarks in mathematical reasoning, general question answering, and code generation, using twelve baselines across four categories.Reported metrics are accuracy, F1, and pass@1; implementation details specify the shared LLM backbone and ASPO settings.Source: §4.1 · pp. 6–7

4.2 MAIN RESULTS

  • ASPO ranks first on all six benchmarks, averaging 78.19 versus 74.06 for the strongest baseline, DyLAN.Its domain-level leads are 4.1 points in mathematical reasoning, 3.5 in code generation, and 3.0 in general question answering.Source: Table 1 · p. 7, §4.2 · p. 7

4.3 TRANSFERABILITY

  • ASPO ranks first in all nine benchmark–backbone combinations and retains the highest score on all three target benchmarks when transferred from MATH.On cross-domain transfer, EvoMAS loses 8.5 points on average; transfer tests use GSM8K, HotpotQA, and HumanEval+ without further adaptation.Source: §4.3 · p. 8, Figure 3 · p. 8

4.4 COST ANALYSIS

  • ASPO achieves average performance of 83.36 at normalized cost 0.69; versus DyLAN, it improves performance by 3.88 points while reducing cost by 67.4%.MaAS costs less at 0.40 but scores 4.66 points lower; RADAR costs 0.70 and scores 4.78 points lower.Source: §4.4 · pp. 8–9, Figure 4 · p. 8

4.5 ABLATION STUDY

  • Every ablated variant loses accuracy on every benchmark; removing substructure rewards costs 3.13 points on average, while disabling AQSM costs 2.69.Removing discovery costs 1.65 points, using the raw empirical success rate costs 2.67, and removing semantic similarity costs 2.44 points.Source: Table 2 · p. 8, §4.5 · p. 9

4.6 SENSITIVITY ANALYSIS

  • Performance is relatively stable for δ ∈ [0.85, 0.95] and K ∈ [3, 5], while training performance largely plateaus beyond T = 6 epochs.A warm-up of Tw = 3 generally performs better than shorter or longer periods; exceptions to preserving the baseline margin occur at K = 2 on GSM8K and K = 6 on HotpotQA.Source: §4.6 · p. 9, Figure 5 · p. 9

5 CONCLUSION

The conclusion presents ASPO as a query-specific MAS policy-learning framework and reports advantages across benchmarks, domains, and LLM backbones, while noting current scope constraints.

5 CONCLUSION

  • ASPO combines adaptive query selection and discovery with substructure-level rewards to learn query-specific MAS policies.The approach is described as Active Substructure-aware Policy Optimization.Source: §5 · p. 10
  • ASPO outperforms twelve baselines across six benchmarks and retains its advantage across task domains and LLM backbones.Ablations validate both components, and cost analyses show favorable performance–cost trade-offs.Source: §5 · p. 10
  • ASPO currently searches within a predefined operator pool and uses reference solutions to compute training rewards.The conclusion identifies dynamically changing operator pools and tasks without reliable reference solutions as directions for future work.Source: §5 · p. 10

AI USE STATEMENT

The authors report using generative AI to polish manuscript wording and assist with experimental-analysis scripts, with author review of revisions and script outputs.

AI USE STATEMENT

  • Generative AI tools were used to polish manuscript wording and assist with writing scripts for experimental analysis.The authors state that three authors reviewed language revisions for intended meaning and technical accuracy.Source: AI USE STATEMENT · p. 10
  • Three authors inspected and tested AI-assisted scripts and checked their outputs against experimental records.Source: AI USE STATEMENT · p. 10
  • The authors take responsibility for the final content, including AI-assisted text and code.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

The ethics statement notes possible financial access barriers from expensive LLMs. The related-work discussion connects ASPO to adaptive training-data selection and localized credit assignment while distinguishing its target and mechanism.

ETHICS STATEMENT

  • Reliance on expensive LLMs may create financial barriers to access.The statement reports no anticipated fairness, privacy, security, or other harmful societal or ethical issues beyond broader field considerations.Source: ETHICS STATEMENT · p. 10

A RELATED WORK

  • ASPO applies adaptive training-data selection to query-specific MAS architecture learning and gives never-solved sampled queries extra discovery rollouts.Unlike criteria that downweight both success-rate extremes, ASPO treats consistently solved queries and never-solved queries asymmetrically.Source: A RELATED WORK · p. 15
  • ASPO assigns credit to graph expansions for child-output quality improvement over parent output, discounted descendant returns, and execution costs.Its target is MAS architecture decisions such as operator selection, branching, and termination, rather than reasoning steps or agents’ marginal contributions.Source: A RELATED WORK · p. 15

B LIMITATIONS AND FUTURE WORK

ASPO is bounded by its predefined operator pool and depends on reference-based feedback. Its implementation uses graph-based state encoding, task-specific similarity scoring, and a posterior-sampled competence-boundary score.

B LIMITATIONS AND FUTURE WORK

  • ASPO’s capabilities are bounded by its predefined operator pool and underlying LLMs; discovery explores compositions but cannot add missing capabilities.Future work could extend the pool dynamically and jointly learn operator design and composition.Source: B LIMITATIONS AND FUTURE WORK · p. 15
  • Reference-based training feedback limits direct application to tasks without reliable references or success criteria, while semantic similarity can miss valid alternatives or reward incorrect lookalikes.The authors suggest executable verification, human preferences, or learned evaluators as alternatives.Source: B LIMITATIONS AND FUTURE WORK · p. 15

C.1 STATE ENCODER IMPLEMENTATION

  • The state encoder combines operator embeddings, graph-convolution node representations, attention-pooled graph context, the current parent representation, and query encoding.Its two GCN layers carry information from nodes and upstream nodes within two message-passing steps.Source: §C.1 · p. 16

C.2 SEMANTIC SIMILARITY

  • Mathematical reasoning and question-answering outputs use bidirectional segment matching with ROSCOE embeddings, while code outputs use clipped cosine similarity over AST node-type counts.The text score combines average best-match precision and recall with their harmonic mean; code identifiers and literal values are excluded, and parsing failures score zero.Source: §C.2 · pp. 16–17

C.3 WHY THE COMPETENCE-BOUNDARY SCORE

  • The competence-boundary score estimates query-level improvement potential using p_q(1 − p_q), which bounds how much one policy update can raise success probability.Posterior sampling retains score dispersion as evidence accumulates; at δ = 0.9, effective evidence is capped at 10, preserving exploration.Source: §C.3 · pp. 17–18

C.4 ASPO TRAINING ALGORITHM

ASPO warms up with a traversal of the training set, then samples queries by posterior-based weights and applies discovery rollouts to unsolved queries. It uses filtered trajectories for PPO updates while tracking query outcomes.

C.4 ASPO TRAINING ALGORITHM

  • After warm-up, ASPO samples training batches using posterior-derived query weights and spends up to K rollouts on unsolved queries rather than one.All executed rollouts count against the remaining budget; discovery trajectories enter the buffer only if successful or if some substructure advantage is positive.Source: §C.4 · p. 18
  • For each trajectory, ASPO evaluates node outputs and final-answer correctness, computes action rewards, returns, and advantages, then stores eligible trajectories with fixed PPO targets and old action probabilities.PPO updates the actor, critic, and shared encoder when the buffer is nonempty.Source: §C.4 · p. 18
  • During non-discovery rollouts, ASPO updates each query’s success and failure counts and marks it solved after any successful rollout.Warm-up traverses the training set in batches; posterior-weighted sampling begins after the specified warm-up epochs.Source: §C.4 · p. 18

D.1 BENCHMARKS AND DATA CURATION

The evaluation covers six benchmarks across mathematical reasoning, general question answering, and code generation, using shared approximately 1:2 train/test splits. The math benchmarks are difficulty-filtered, so their absolute scores are not comparable to full-benchmark scores.

D.1 BENCHMARKS AND DATA CURATION

  • The six benchmarks cover mathematical reasoning, general question answering, and code generation, with approximately 1:2 training-to-test splits shared across methods.The benchmarks are GSM8K, MATH, HotpotQA, MMLU-Pro, MBPP+, and HumanEval+.Source: §D.1 · p. 19
  • GSM8K retains the 600 lowest-solve-rate problems, while MATH is restricted to Lv.5 and sampled across seven subject types.The resulting splits contain 200 train / 400 test GSM8K problems and 210 train / 490 test MATH problems; their absolute scores are below full-benchmark scores and should not be compared with them.Source: §D.1 · p. 19
  • The other four benchmarks are not difficulty-filtered: HotpotQA and MMLU-Pro are sampled uniformly across annotation categories, while MBPP+ and HumanEval+ use all problems.HotpotQA uses the distractor setting, with supporting and distractor passages supplied and no additional retrieval required.Source: §D.1 · p. 19

D.2 REPRESENTATIVE BENCHMARK SELECTION

To limit the cost of repeated analyses, the paper selects one representative benchmark per domain by how well its method ranking matches the overall six-benchmark ranking. The baseline set spans single-agent, collaboration, task-level search, and query-level search methods.

D.2 REPRESENTATIVE BENCHMARK SELECTION

  • For each domain, the selection procedure chooses the benchmark whose method-rank vector has the highest Spearman correlation with the overall six-benchmark ranking.The target ordering averages each method’s ranks across all six benchmarks; the analyses use representative benchmarks because running all six for every configuration is expensive.Source: §D.2 · pp. 19–20
  • GSM8K, HotpotQA, and HumanEval+ are selected as the representative benchmarks, and together their method ordering correlates 0.907 with the overall ordering.The greedy selection is also the best of all eight possible three-domain combinations; the other seven yield correlations from 0.778 to 0.891.Source: §D.2 · p. 20

D.3 BASELINE SETUPS

  • The twelve baselines are grouped into single-agent, multi-agent collaboration, task-level MAS search, and query-level MAS search.Examples include prompt-only Vanilla and CoT, hand-designed AgentVerse, and learned or searched systems such as DyLAN and ADAS.Source: §D.3 · pp. 20–21
  • The baseline configurations vary in search space and optimization: AFlow searches code workflows with tree search, while MaAS uses a query-conditioned operator supernet.RAAS shares MaAS’s operator-selection space but uses a group-baseline policy-gradient signal; Puppeteer learns agent activations with REINFORCE.Source: §D.3 · pp. 21–22

D.4 ASPO IMPLEMENTATION DETAILS AND HYPERPARAMETER REFERENCE

ASPO uses conventional clipped PPO settings and distinguishes localized substructure-reward aggregation from the final answer aggregation. The appendix also provides cost–performance views and links ASPO-specific hyperparameters to sensitivity analyses.

D.4 ASPO IMPLEMENTATION DETAILS AND HYPERPARAMETER REFERENCE

  • PPO uses a 0.2 clipping threshold, batches of eight queries, at most four updates per batch, and stops updates when approximate KL exceeds 0.02.The subgraph discount is γ = 0.95 so distant descendants remain nearly undiscounted across construction of up to five layers.Source: §D.4 · p. 22
  • Local substructure rewards use ScEnsemble to combine child outputs, while final answers aggregate all leaf outputs using ensembling or voting by task type.Open-ended generation uses the ensemble operator; multiple-choice and fill-in-the-blank tasks use majority voting.Source: §D.4 · p. 22
  • Figure 6 compares training and inference costs in USD with final test performance for GSM8K, HotpotQA, and HumanEval+, using separate panel scales.Dashed lines mark observed Pareto frontiers; Vanilla, CoT, and AgentVerse are omitted from the training-cost row because they incur no training cost.Source: Figure 6 · p. 23
  • Table 5 groups ASPO-specific hyperparameter settings by component and points to the corresponding sensitivity analyses.The analyses cover query-selection settings, cost coefficient, and architectural layer and branching limits.Source: §D.4 · p. 23

D.5 COST–PERFORMANCE TRADE-OFFS BY BENCHMARK AND PHASE

The appendix compares performance with monetary and wall-clock costs, then examines sensitivity to architecture-related settings on HumanEval+. It also describes the ten operators available to ASPO, ranging from generation and aggregation to refinement and reference retrieval.

D.5 COST–PERFORMANCE TRADE-OFFS BY BENCHMARK AND PHASE

  • ASPO reaches the highest-performance end of all six observed Pareto frontiers across training and inference costs on GSM8K, HotpotQA, and HumanEval+.At inference, MaAS costs less on all three benchmarks, while trailing ASPO by 4.41, 2.31, and 7.27 performance points, respectively.Source: §D.5 · p. 23
  • ASPO’s training costs are $7.37, $2.64, and $0.46 on GSM8K, HotpotQA, and HumanEval+, respectively, while achieving the highest test performance on each.Against MaAS, ASPO costs more to train on GSM8K and HotpotQA but less on HumanEval+ ($0.46 versus $0.55), where pass@1 improves by 7.27 points.Source: §D.5 · p. 23
  • 90.00% pass@1 takes ASPO 82 minutes total on HumanEval+, below the median time across evaluated methods.Its total is 70 minutes of training plus 12 minutes of testing; faster MaAS and AFlow trail ASPO by 7.27 and 5.45 pass@1 points, respectively.Source: §D.5 · p. 24, Figure 7 · p. 24

D.6 SENSITIVITY TO ARCHITECTURE HYPERPARAMETERS

  • On HumanEval+, increasing the cost coefficient from 0.001 to 0.01 reduces accuracy by 2.7 points, with a further 6.4-point drop at 0.05 as cost decreases across the range.The layer budget raises accuracy from 84.6 to 90.0 between three and five layers; extending from five to seven adds 14% cost for a 0.9-point gain.Source: §D.6 · p. 24, Figure 8 · p. 24
  • Raising the maximum branching limit from two to three children yields similar HumanEval+ accuracy and cost: 90.0 at $0.51 versus 89.1 at $0.50.The tested defaults were λ = 0.01, five layers, and two children per node.Source: §D.6 · p. 24

D.7 OPERATOR SPACE

  • The ten-operator pool covers candidate generation, aggregation, refinement, and reference-knowledge retrieval.Its listed operations include chain-of-thought generation, multi-sample generation, planning, background retrieval, self-refinement, variation, debate, and code execution with synthesis.Source: §D.7 · pp. 24–25
  • MultiGenerateCoT supplies three independent chain-of-thought candidate lanes for downstream aggregation.ScEnsemble groups equivalent final answers, selects a plurality answer, breaks ties by reasoning quality, and synthesizes the selected reasoning.Source: §D.7 · p. 25
  • The Programmer operator writes and executes Python in a sandbox, then synthesizes the final answer from the code and execution result.It can retry with error feedback before synthesis.Source: §D.7 · pp. 25, 29

Related papers

Loading 2609.32430v1…