acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
optimization
Keywords:
Multi-Agent Systems, Reinforcement Learning, Adaptive Query Selection, Substructure-Level Credit Assignment

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_mte7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors address the problem of automated multi-agent system (MAS) construction. Specifically, they identify two key bottlenecks in prior work (e.g., MaAS): (1) training queries carry unequal informational value, yet existing methods sample them uniformly; and (2) rewards are assigned only at the whole-workflow level, providing overly coarse credit assignment for individual graph-expansion actions. To overcome these limitations, the authors propose ASPO, which integrates an Adaptive Query Selection Mechanism (AQSM) that prioritizes "competence-boundary" queries, together with a substructure-aware reward for finer-grained policy optimization. Experiments across diverse benchmarks and scenarios demonstrate the effectiveness of ASPO.

Critical strengths
  1. Well-motivated problem with empirical support: The introduction clearly illustrates the research problem and provides a detailed comparison with related work. Furthermore, Figure 1 and Table 2 demonstrate that both adaptive query selection and the fine-grained reward improve the performance of MAS on downstream tasks.
  2. Comprehensive ablation studies: Section 4.3 presents transferability experiments of the automated construction method across different tasks and LLMs, which further validate the effectiveness of ASPO. Moreover, Section 4.4 provides a cost analysis showing that ASPO achieves strong performance at a lower cost.
Critical weaknesses
  1. The necessity of automated MAS construction on the provided benchmarks: My main concern is the necessity of automated MAS construction for the benchmarks used in this paper. As shown in Table 1, most MAS-Search methods achieve only comparable performance to the CoT baseline, and even underperform it on MMLU-Pro, MBPP+, and HumanEval+. Although the proposed ASPO achieves the best performance, it requires an additional training phase with extra training samples, which are not available to the CoT baseline. This raises the question: is automated MAS construction truly necessary for these tasks? I suggest that the authors include stronger yet simpler baselines for comparison, such as few-shot CoT (with in-context examples) or CoT with SFT training.
  2. The motivation curve is measured on the training set: In the Figure 1, the 59.0% → 74.3% AQSM gain is evaluated on the full training set, where concentrating budget on medium/hard training queries trivially raises training accuracy. Please provide the same grouped curves on the held-out test set, or state explicitly that the figure is only a mechanism illustration with generalization evidenced by Table 1.
  3. Heuristic design of the adaptive query selection: In AQSM, the authors estimate each query's success probability using a Beta posterior. I suggest that the authors include additional comparative baselines, such as query selection based on entropy or similarity, to provide stronger empirical support for the AQSM design.
Questions for authors

See my questions in weakness.

1 comment
AuthorsOpenReview ↗

Response to Reviewer mte7

W1: The value of automated MAS construction and comparison with stronger CoT baselines

We thank the reviewer for highlighting this concern. The failures of existing MAS-search methods directly motivate our work. Below we first analyze these failures, then compare against few-shot CoT.

Existing MAS-search methods can fail to learn effective collaboration. As detailed in our response to Reviewer k8Ff’s Q2, (i) Most MaAS and RAAS test workflows on MMLU-Pro and HumanEval+ effectively rely on a single Generate operation, consistent with repeated training on easy queries reinforcing basic generation. (ii) Puppeteer receives only about 54 policy updates on HumanEval+ and exhibits premature termination, modification without an initial solution, and repeated reflection without execution feedback. ASPO improves policy learning through adaptive query selection and substructure-level feedback. With the same backbone and operator pool, it exceeds both the strongest agent-selection baseline and CoT on all benchmarks.

ASPO also outperforms few-shot CoT with access to the same training data. We also add a retrieval-augmented few-shot CoT baseline. For each test query, it retrieves the three most similar examples from the training split and incorporates their questions and reference solutions into the prompt.

BenchmarkCoTfew-shot CoTASPO
GSM8K71.5872.9279.08
MATH48.4449.8057.89
HotpotQA76.3277.6481.00
MMLU-Pro73.1773.1777.70
MBPP+76.3277.2583.47
HumanEval+83.9483.6490.00
Average71.6372.4078.19

Providing retrieved demonstrations improves CoT’s average score from 71.63 to 72.40. ASPO nevertheless outperforms this stronger baseline on all six benchmarks, by 5.79 points on average. These results support the benefit of learning MAS architectures beyond supplying training examples through in-context prompting.

Revision. We add the few-shot CoT results to Table 1 and its implementation details to Appendix D.3. We also add an analysis of why existing MAS-search methods fail or underperform to Appendix D.5.

 

W2: Grouped learning curves on the held-out test set

Thank you for this suggestion. We now add the same grouped learning curves for 490 held-out MATH test queries in Figure 1(b). The table below reports test accuracy (%); entries for epochs 4–6 show without / with AQSM.

GroupEpoch 1Epoch 2Epoch 3Epoch 4Epoch 5Epoch 6
Easy (192)100.00100.00100.0098.44 / 99.4899.48 / 98.9698.96 / 98.96
Medium (126)46.8351.5954.7654.76 / 61.9052.38 / 65.0853.97 / 65.87
Hard (172)0.000.000.005.23 / 4.655.23 / 6.404.65 / 10.47

At epoch 6, AQSM improves medium- and hard-query accuracy by 11.9 and 5.8 percentage points, respectively, while easy-query accuracy remains 99.0% in both conditions. Overall test accuracy reaches 59.4% versus 54.3% without AQSM, showing that the gains extend to held-out queries.

Revision. We add test-set query outcomes and grouped accuracy curves to Figure 1(b), and update the Introduction to discuss both training and test results.

 

W3: Rationale for AQSM and comparison with entropy-based query selection

Thank you for suggesting additional query-selection baselines. AQSM combines a theoretically motivated selection score with uncertainty-aware success-rate estimation. We clarify these design choices below and add an outcome-entropy baseline to strengthen the empirical evidence.

Appendix C.3 derives, under the stated assumptions, an upper bound proportional to pq(1−pq)p_q(1-p_q) on the improvement in query success probability under a gradient step. This motivates prioritizing queries that are solvable but not yet reliably solved. Since these probabilities must be estimated from limited rollout outcomes, we use a Beta posterior to represent estimation uncertainty and sample from it to preserve exploration.

Following the reviewer's suggestion, we add the w/ outcome entropy variant, which samples queries in proportion to the binary entropy of their empirical success rates. It achieves an average score of 80.59 versus ASPO’s 83.36, a 2.77-point gap. The existing w/o posterior variant similarly loses 2.67 points. These results suggest that changing the weighting function alone does not address unreliable success-rate estimates under sparse observations, supporting posterior-based estimation and exploration.

MethodGSM8KHotpotQA (F1)HumanEval+Avg.
ASPO79.0881.0090.0083.36
w/ outcome entropy76.0878.4187.2780.59

Revision. We have added the w/ outcome entropy comparison to Table 3 in Section 4.5.

Reviewer_gJEAOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Active Substructure-aware Policy Optimization (ASPO), a reinforcement learning framework for query-level multi-agent system (MAS) search. The method addresses two problems in existing approaches: treating all training queries equally and using only workflow-level rewards to optimize the MAS structure. ASPO introduces an adaptive query selection mechanism that focuses on queries with more learning potential and a substructure-level reward that measures how different parts of the MAS improve answer quality. The authors evaluate ASPO on six benchmarks covering math reasoning, question answering, and code generation. The results show that ASPO consistently outperforms 12 baselines. Additional ablation studies, transfer experiments, and cost analysis further support the effectiveness of the proposed method.

Critical strengths
  1. The paper identifies two important problems in query-level MAS search: how to select useful training queries and how to assign rewards to different parts of a MAS. The proposed AQSM and substructure-level rewards address these problems in a simple and reasonable way. I think combining these two ideas into a unified framework is a useful contribution.
  2. ASPO consistently outperforms 12 baselines across six benchmarks covering mathematical reasoning, question answering, and code generation. The authors also provide ablation studies to show the contribution of each component, along with transferability and cost analyses. These results provide good evidence for the effectiveness of the proposed method and are a major reason for my positive assessment.
Critical weaknesses
  1. The two main components of ASPO are closely related to existing ideas in curriculum learning and fine-grained reward assignment. Although their combination for query-level MAS search is well motivated, the technical novelty seems somewhat limited.
  2. Although the paper evaluates ASPO on six benchmarks, the experiments mainly focus on math reasoning, question answering, and code generation with a predefined set of agents. It remains unclear how well the proposed method would work on more complex agent tasks that require longer interactions and more flexible agent structures.
Questions for authors
  1. In Section 3.3, the authors use (p_q(1-p_q)) to prioritize queries near the competence boundary. However, queries with similar success probabilities may have different learning potential. For example, a query may have a 50% success rate because the policy sometimes selects a good MAS structure, while another query may have the same success rate mainly due to randomness in the underlying LLM. How does AQSM distinguish between these two cases, given that further training may help the first query but not necessarily the second?
  2. In Section 3.2, the authors define the immediate reward based on the quality difference between the parent output and the aggregated child outputs, and further include descendant returns in Eq. (5). For example, an intermediate agent may identify an error or provide useful information without immediately producing an answer closer to the reference solution. Could the proposed reward still underestimate the contribution of such agents, even when descendant returns are considered?
  3. In Section 3.2, the authors introduce a cost penalty to discourage unnecessary computation, and Section 4.4 shows that ASPO achieves a good cost-performance trade-off. However, it is unclear how this penalty affects the actual MAS structures. Does it encourage the policy to build shallower graphs with fewer agents, or does it mainly affect the selection of different operators? It would be helpful to understand how the cost penalty changes the structures learned by ASPO.
4 comments
AuthorsOpenReview ↗

Response to Reviewer gJEA [Part 1]

W1: Relation to prior work

Thank you for raising this point. Prior work in other domains offers related ideas on adaptive data selection and fine-grained reward assignment (Appendix A), but MAS architecture search introduces specific exploration and credit assignment challenges that require tailored designs. Our technical novelty is therefore twofold: (i) to our knowledge, we are the first to identify uneven query informativeness and coarse substructure feedback as bottlenecks in query-level MAS search and demonstrate their impact on policy learning; (ii) our analysis and adaptation experiments show that directly transferring existing methods from other domains to MAS search can yield lower performance and higher training costs. These findings motivate two new training strategies specifically designed to address these bottlenecks in MAS search. Below, we summarize both components and their supporting evidence. Detailed mechanisms and comparisons are provided in our response to Reviewer k8Ff's W1 and Q1.

1. Adaptive query selection.

  • Problem and impact. Figure 1 shows learning stagnation under uniform query selection. Our workflow analysis further suggests that repeated training on easy queries reinforces basic generation behavior, limiting effective collaboration in MaAS and RAAS (Appendix D.5).

  • Design and evidence. AQSM (i) supports PPO without requiring GRPO-style group reward variation, (ii) uses a theoretically motivated score for proportional sampling, and (iii) introduces discovery to allocate extra rollouts to selected, previously unsolved queries. Removing discovery lowers average performance by 1.65 points. The joint DAPO replacement scores 1.97 points below ASPO and uses 6.69 times as many training tokens at group size 8.

2. Substructure-level reward assignment.

  • Problem and impact. Our layerwise analysis in the Introduction shows that additional computation can reduce answer quality. Workflow-level feedback can overlook intermediate progress and reinforce unnecessary or harmful expansions.

  • Design and evidence. ASPO addresses both feedback sparsity and attribution granularity by assigning local quality gains and descendant returns to individual graph expansions. SHARP refines worker attribution but still depends on sparse final-correctness changes. Moreover, ASPO reuses the observed execution subgraph, while SHARP requires downstream counterfactual re-execution. The SHARP replacement scores 2.02 points below ASPO and uses 3.87 times as many training tokens.

Revision. We expand the comparisons in Appendix A, analyze why existing MAS-search methods fail or underperform in Appendix D.5, and report the DAPO and SHARP variants in Section 4.5 and Table 3.

 

W2: Evaluation on more complex agent tasks

Thank you for highlighting this concern. We add experiments on GAIA to extend our evaluation to complex, real-world tool-use tasks beyond the original evaluation domains. GAIA requires multi-step reasoning, multimodal understanding, and tool use, making it a challenging test of agent capabilities. It has also been adopted by MaAS, RAAS, and EvoMAS to evaluate MAS methods in this setting. Specifically, we use GAIA 2023’s official split, training on 165 validation questions and evaluating on 301 test questions. The table below reports per-level and overall accuracy for the top five MAS methods in Table 1 and Vanilla.

MethodLevel 1Level 2Level 3Overall
Vanilla7.534.400.004.65
DyLAN30.1121.382.0420.93
EvoMAS29.0322.648.1622.26
MaAS25.8122.016.1220.60
RADAR26.8820.754.0819.93
ASPO (Ours)31.1825.1616.3325.58

ASPO leads across all three GAIA difficulty levels. It achieves an overall accuracy of 25.6%, exceeding the strongest baseline, EvoMAS, by 3.3 percentage points. Its margin over the strongest baseline at each level increases from 1.1 points at Level 1 to 2.5 at Level 2 and 8.2 at Level 3. This pattern is consistent with Figure 1, where AQSM yields larger gains on medium and hard queries.

Revision. We add the GAIA results and analysis to Section 4.2 and Table 2, with dataset and split details in Appendix D.1.

AuthorsOpenReview ↗

Response to Reviewer gJEA [Part 2]

Q1: Learning potential under LLM execution randomness

Thank you for raising this distinction. AQSM uses overall success probability as a proxy for learning potential without explicitly separating architecture-selection variability from LLM execution randomness. We clarify the rationale and a complementary way to improve feedback reliability below.

1. Architecture learning can improve robustness to LLM randomness. MAS architecture and LLM execution randomness jointly shape outcomes, and their effects interact. We focus on architecture quality because verification and aggregation can mitigate random errors, while unsuitable dependencies can amplify them. Learning better architecture policies can therefore also improve robustness to LLM randomness.

2. Repeated evaluation offers a complementary extension. RAAS (Yang et al., 2026) reduces evaluation noise by repeatedly executing each architecture on the same query and aggregating the results. This mechanism is orthogonal to AQSM and could be incorporated to trade additional rollout cost for more reliable feedback.

Revision. We discuss repeated evaluation in Appendix B.

 

Q2: Credit for intermediate contributions and delayed benefits

Thank you for highlighting this concern. Our method already incorporates three complementary mechanisms to mitigate this issue. (i) Node outputs integrate the available information into a candidate solution, allowing supporting computations to affect the evaluated answer. (ii) Local quality feedback combines similarity with task utility to capture partial improvements before correctness changes. (iii) Descendant returns propagate downstream gains to earlier expansions through Eq. (5), allowing useful actions to receive credit even when their benefits are delayed. These design choices are supported by Table 3: replacing substructure rewards with workflow-level feedback lowers average performance by 3.13 points, and removing the similarity term causes a 2.44-point drop. Together with the end-to-end gains in Table 1, these results support the practical benefits of our design.

Precisely quantifying how much each intermediate action contributes remains highly challenging, particularly when benefits are delayed or depend on interactions among agents. Compared with methods relying solely on workflow-level rewards, our design already substantially mitigates this issue through local quality feedback and descendant returns, yielding end-to-end gains. Further reducing the underestimation of delayed or interacting contributions is a direction for future work.

Revision. We discuss more precise credit assignment as future work in Appendix B.

 

Q3: How the cost penalty affects learned MAS structures

Thank you for this suggestion. We add an analysis on HumanEval+, showing that the cost penalty affects both graph structure and operator selection. The table below summarizes three representative cost coefficients, reporting mean depth, mean width, and selected operator usage shares (%).

Metricλ=0.001\lambda=0.001λ=0.01\lambda=0.01 (default)λ=0.1\lambda=0.1
Mean depth2.111.391.15
Mean width2.091.751.44
Generate25.0%25.5%29.9%
GenerateCoT26.5%24.9%24.7%
MultiGenerateCoT23.8%19.6%17.5%
Debate4.7%6.0%6.6%

Stronger penalties produce shallower, narrower workflows and shift operator usage toward simpler generation: Generate’s share increases, while GenerateCoT and MultiGenerateCoT decline. These trends suggest that larger cost penalties discourage costly generation and favor simpler operators. The modest increase in Debate may reflect a cost–performance trade-off: the policy reduces repeated candidate generation while retaining collaborative refinement whose benefits may justify its additional cost.

Revision. In the revised manuscript, we add this analysis and the complete results for all five cost coefficients, including mean depth, mean width, and the full operator usage distributions, to Appendix D.7 and Figure 9.

Reviewer_gJEAOpenReview ↗

Reply to authors

Thanks to the authors for the detailed response and additional experiments. The new GAIA results help address my concern about generalization to more complex agent tasks. I also appreciate the additional comparisons with DAPO and SHARP, as well as the analysis of how the cost penalty affects the learned MAS structures.

I still have some concerns about AQSM using success probability as a proxy for learning potential, since it does not distinguish architecture-related failures from LLM randomness. The substructure-level reward may also underestimate some intermediate contributions, as the authors acknowledged.

Overall, I think the rebuttal addresses most of my concerns and makes the paper more convincing. I will keep my rating at 3.

We thank the reviewer for the thoughtful follow-up. We are glad that our clarifications and additional experiments helped address the reviewer’s concerns about technical novelty and the scope of our evaluation. We would like to briefly revisit the two remaining points.

  1. AQSM and LLM randomness. We focus on MAS architecture because it can amplify or mitigate the effects of LLM randomness on the final answer. As discussed in Appendix B, repeatedly running the same architecture on the same query, as in RAAS, could complement AQSM by reducing evaluation noise at the cost of additional rollouts.
  2. Credit for intermediate contributions. Ensuring that no intermediate contribution is underestimated, even slightly, is exceptionally difficult. Existing MAS search methods leave this problem entirely unaddressed. In response, our design has substantially mitigated it by capturing intermediate progress and propagating downstream gains. We discuss more precise attribution as future work in Appendix B.

We thank the reviewer again for taking the time to discuss our work and help us improve the paper.

Reviewer_k8FfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper targets two issues in query-level MAS search problems: (1) Uneven query informativeness (i.e., training on whole data-set, not filtering over-simplified or over-difficult ones). (2) Coarse-grained substructure attribution (i.e., credit assignment in RL).

The authors propose ASPO, which uses a shared GNN controller for progressive DAG rollout and introduces: (1) Adaptive Query-Selection Mechanism (AQSM): Uses a discounted Beta posterior to sample the queries the near policy’s competence boundary, while a discovery mode runs extra rollouts on unsolved queries. (2) Substructure-aware Policy Optimization: Replaces global rewards with substructure-level rewards  for PPO updates.

Across six benchmarks (Table 1), ASPO ranks first overall (~78.19%), generalizes across tasks and LLM backbones (Figure 3).

Critical strengths
  1. Strong accuracy: Ranks first on all 6 benchmarks in Table 1 (e.g., 79.08% on GSM8K, 57.89% on MATH, 90.00% on HumanEval+).
  2. Good ablations and transfer results: Table 2 shows every part helps, and policies trained on MATH transfer to GSM8K, HotpotQA, and HumanEval+ with very small drops, as shown in Figure 3.
Critical weaknesses
  1. The core ideas are mostly borrowed from LLM math RL: 
  • (1) AQSM is very close to MoPPS (Qu et al., 2026) on discounted Beta posterior, and DAPO (Yu et al., 2025) on dynamic sampling. AQSM is a straightforward combination of these techniques.;
  • (2) Substructure reward is just step-by-step ORM difference. Because every node outputs a final answer, taking the score difference between parent and child is just standard ORM reward shaping, not really solving a multi-agent credit assignment problem (like leave-one-out credit assignment, or TD-Error) .
  1. Critic bias and reward hacking in Discovery Mode (Algorithm 1): It saves a failed trajectory to the PPO buffer if any step has a positive substructure advantage. However, throwing away trajectories with negative advantages and only keeping positive ones creates a strong selection bias, which might cause the PPO critic to overestimate state values. (looking for more solid ablations on this)

  2. Missing the strong baselines in Table 1: (1) meta-agent methods, such as FlowReasoner, ScoreFlow, MAS-GPT; (2) RL baselines that focus on sampling and credit-assignment methods, such as DAPO.

Questions for authors
  1. Solid comparison with DAPO and SHARP (Shapley credit) : Using the same GNN controller and operator pool, how does AQSM compare against DAPO, and how does substructure-level reward compare against SHARP?

  2. Baseline degradation: Why do MaAS, RAAS, and Puppeteer underperform a single CoT call on MMLU-Pro and HumanEval+ (Table 1)? Are their hyper-parameters well-tuned for your 10-operator pool and small training sets?

6 comments
AuthorsOpenReview ↗

Response to Reviewer k8Ff [Part 1]

W1 and Q1: Relation to prior work and comparisons with DAPO and SHARP

We thank the reviewer for the comments on novelty and the suggested comparisons. Prior work in other domains offers related ideas on adaptive data selection and fine-grained reward assignment (Appendix A), but MAS architecture search introduces specific exploration and credit assignment challenges that require tailored designs. Our technical novelty is twofold: (i) to our knowledge, we are the first to identify uneven query informativeness and sparse, coarse-grained feedback as bottlenecks in query-level MAS search and demonstrate their impact on policy learning; (ii) Directly transferring existing methods from other domains to MAS search can yield lower performance and higher training costs. These findings motivate two new training strategies specifically designed to address these bottlenecks in MAS search.

W1.1: Adaptive query selection and comparison with DAPO

Below, we present evidence of uneven query informativeness as a bottleneck in MAS search, clarify AQSM's differences from prior methods, and report a comparison with DAPO.

1. A different learning problem, supported by empirical observations. DAPO (Yu et al., 2025), GRESO (Zheng et al., 2025), and MoPPS (Qu et al., 2026) primarily study RL fine-tuning of LLM reasoning policies. We instead examine how uneven query informativeness affects MAS architecture learning. Figure 1 shows that, under uniform query selection, accuracy barely improves after warm-up. Our additional analysis in Appendix D.5 of the revision further shows that most test workflows generated by MaAS and RAAS effectively rely on a simple vanilla agent. These observations highlight the impact of lacking adaptive query selection in MAS search and motivate our design.

2. A design tailored to PPO training of MAS architecture policies. AQSM differs from prior methods in three respects: (i) Query selection tailored to PPO. DAPO and GRESO tailor query filtering to GRPO’s need for within-group reward variation. AQSM instead selects queries using posterior success-rate estimates, without requiring within-group reward variation. (ii) Theoretically motivated sampling. MoPPS shares our use of discounted Beta posteriors but chooses the top BB queries closest to a target success rate. AQSM instead samples queries in proportion to p~q(1−p~q)\tilde p_q(1-\tilde p_q), which is theoretically motivated by our bound on improvement under a gradient step (Appendix C.3). (iii) A distinctive discovery mechanism. Existing selection criteria can downweight both success-rate extremes, but low success rates may reflect insufficient architecture exploration. ASPO therefore allocates extra rollouts to selected queries that have never been solved. Failed discovery trajectories containing positive-advantage expansions can still support policy updates, linking query-level exploration to substructure feedback.

3. Direct comparison with DAPO. Following Q1, we jointly replace ASPO's query sampling and policy optimization with DAPO.

MethodGSM8KHotpotQA (F1)HumanEval+Avg.
ASPO (ours)79.0881.0090.0083.36
w/ DAPO76.6779.3188.1881.39

The DAPO variant scores 1.97 points below ASPO on average (Table 3). Its workflow-level GRPO feedback and filtering of already-generated rollouts may partly explain this gap: the former provides limited credit to individual expansions, while the latter wastes rollout effort. Moreover, due to grouped rollouts and resampling, the DAPO variant uses 6.69 times as many training tokens as ASPO at group size 8.

Revision. In the revision, we provide a more detailed comparison with existing adaptive training data selection methods in Appendix A. We also add the w/ DAPO variant to Section 4.5 and Table 3.

AuthorsOpenReview ↗

Response to Reviewer k8Ff [Part 2]

W1.2: Substructure-level credit assignment and comparison with SHARP

Below, we explain how our learning signal extends beyond immediate reward shaping, clarify the design differences from existing credit methods, and report a controlled comparison with SHARP.

1. Our learning signal moves beyond step-by-step ORM score differences. We agree that local quality differences have a reward-shaping interpretation. Each node integrates available information into a candidate solution, making intermediate progress evaluable. Beyond immediate score changes, each expansion’s return includes discounted descendant gains (Eq. 5), allowing delayed contributions to receive credit. The resulting advantage differs from a standard TD error but likewise incorporates information beyond the immediate reward.

2. Credit assignment tailored to MAS architecture decisions. ASPO assigns credit using quality gains from child outputs and descendant returns, matching the controller’s graph-expansion decisions. Directly adopting existing counterfactual credit introduces two concerns in this setting: (i) Dependence on sparse global feedback. We identify two limitations in the Introduction: feedback sparsity and coarse-grained attribution. SHARP (Li et al., 2026) refines attribution across workers, but still relies on changes in final-answer correctness. ASPO addresses both limitations by providing denser feedback to individual graph expansions. (ii) Execution cost. Applying SHARP/LOO-style credit in our setting requires masking agents’ contributions and re-executing affected downstream agents, increasing training cost. ASPO instead reuses the observed execution subgraph without additional rollouts.

3. Direct comparison with SHARP. Following Q1, we replace our substructure-level reward with the counterfactual credit mechanism from SHARP.

MethodGSM8KHotpotQA (F1)HumanEval+Avg.
ASPO (ours)79.0881.0090.0083.36
w/ SHARP credit76.9279.8487.2781.34

The SHARP variant improves average performance by 1.11 points over w/o sub-reward but remains 2.02 points below ASPO (Table 3). This gap may partly reflect the limitations of final-correctness-based credit in capturing intermediate improvements. Moreover, counterfactual re-execution of affected downstream agents raises its average training token consumption to 3.87 times that of ASPO.

Revision. In the revision, we provide a more detailed comparison with existing credit assignment methods in Appendix A. We also add the w/ SHARP credit variant to Section 4.5 and Table 3.

AuthorsOpenReview ↗

Response to Reviewer k8Ff [Part 3]

W2: Justification of discovery filtering

Thank you for raising this concern about selection bias in discovery mode. Below, we clarify the filtering rule, explain its motivation, and report an ablation that removes the filter.

1. The motivation is to avoid excessive training effort on persistently unsolved extreme queries. Because discovery allocates additional rollouts to previously unsolved queries, retaining every unsuccessful attempt may concentrate excessive training effort on these extreme cases. Our filtering rule aims to limit this additional investment. (i) Abundant learning signals. On GSM8K, HotpotQA, and HumanEval+, respectively, 93.1%, 80.7%, and 100% of discovery rollouts already contain positive-advantage actions. These already provide a substantial pool of trajectories. (ii) Persistent failure cases. Some queries yielded only negative-advantage actions across all K discovery rollouts. Inspection identified cases beyond the capabilities of our model and operator pool, as well as problematic reference labels. Further updates on these queries offer no benefit.

2. Discovery improves performance, while filtering has a small, dataset-dependent effect. We add the w/o discovery filt. variant, which allows all discovery rollouts to contribute to policy updates.

MethodGSM8KHotpotQA (F1)HumanEval+Avg.
ASPO (ours)79.0881.0090.0083.36
w/o discovery filt.79.0080.4090.0083.13

Removing only the filter has negligible effects on GSM8K and HumanEval+, where most discovery rollouts already contain positive-advantage actions. HotpotQA has a lower proportion of such rollouts and loses 0.60 points. The ablation shows that filtering provides modest, dataset-dependent gains.

Revision. In the revised manuscript, we add the w/o discovery filt. variant and its analysis, including the proportions of discovery rollouts containing positive-advantage actions, to Section 4.5 (Ablation Study) and Table 3.

W3: Comparison with MAS-GPT

Thank you for suggesting additional baselines. To cover trained meta-agents, we add MAS-GPT to Table 1. Following MAS-Orchestra (Ke et al., 2026) and EvoMAS (Hu et al., 2026), we use the official MAS-GPT-32B checkpoint to reproduce MAS-GPT.

MethodGSM8KMATHHotpotQA (F1)MMLU-ProMBPP+HumanEval+Avg.
MAS-GPT71.25 ± 2.0745.37 ± 2.5170.74 ± 2.6272.62 ± 2.6368.78 ± 2.7675.15 ± 1.1467.32
ASPO (ours)79.08 ± 1.2557.89 ± 1.1181.00 ± 1.1777.70 ± 0.8883.47 ± 0.8290.00 ± 1.4878.19

ASPO outperforms MAS-GPT on all six benchmarks by 10.87 points on average (78.19 vs. 67.32). MAS-GPT even underperforms CoT and Vanilla on some benchmarks. MAS-Orchestra and EvoMAS also report cases where MAS-GPT underperforms single-agent baselines. Consistent with prior analyses in MAS-Orchestra and EvoMAS, our inspection suggests two issues: (i) execution failures, where generated code crashes; and (ii) limited task adaptation, such as applying math-solving workflows to coding.

Revision. In the revision, we add MAS-GPT to the baselines in Section 4.1 and Table 1, document its setup in Appendix D.3, and analyze why it underperforms in Appendix D.5.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We thank all reviewers for their constructive feedback. We have responded to each review in detail and revised the manuscript accordingly. Key manuscript changes are highlighted in blue. Below we first summarize the reviewers’ concerns and our responses across three themes: method clarifications, additional experiments, and additional analyses.

1. Method clarifications.

  • Query selection: Expanded comparisons with DAPO, GRESO, and MoPPS in Appendix A (k8Ff W1.1; gJEA W1).
  • Credit assignment: Clarified differences from ORM shaping in our response and from counterfactual credit assignment in Appendix A (k8Ff W1.2; gJEA W1).
  • Mechanisms and limitations: Clarified discovery filtering (k8Ff W2) and expanded the discussion of feedback reliability and credit assignment in Appendix B (gJEA Q1, Q2).

2. Additional experiments.

  • Stronger baselines: Added MAS-GPT and few-shot CoT to Table 1, with setups in Appendix D.3 (k8Ff W3; mte7 W1).
  • Complex agent tasks: Added GAIA evaluation to Section 4.2 and Table 2, with dataset details in Appendix D.1 (gJEA W2).
  • More rigorous ablations: Added DAPO and SHARP comparisons, outcome-entropy selection, and a discovery-filtering ablation to Section 4.5 and Table 3 (k8Ff Q1, W2; mte7 W3).

3. Additional analyses.

  • Generalization: Added grouped MATH test curves to Figure 1(b) and updated the Introduction (mte7 W2).
  • Baseline failures: Examined learned workflows and execution failures in Appendix D.5 (k8Ff Q2).
  • Cost penalty: Examined its effects on graph depth, width, and operator selection in Appendix D.7 and Figure 9 (gJEA Q3).

In addition, the table below organizes our manuscript revisions by reviewer concern and lists their locations.

Reviewer concernsRevision / clarificationLocation
k8Ff W1, Q1Expanded method comparisons; added DAPO and SHARP variantsAppendix A; Section 4.5; Table 3
k8Ff W2Clarified discovery filtering; added its ablationSection 4.5; Table 3
k8Ff W3Added MAS-GPT, its setup, and failure analysisTable 1; Appendix D.3; Appendix D.5
k8Ff Q2Clarified baseline setups; added workflow failure analysisResponse to Q2; Appendix D.5
gJEA W1Expanded novelty discussion and comparisons with existing methodsAppendix A; Section 4.5; Table 3
gJEA W2Added GAIA evaluation and dataset detailsSection 4.2; Table 2; Appendix D.1
gJEA Q1Discussed repeated evaluation for more reliable feedbackAppendix B
gJEA Q2Clarified delayed credit and discussed more precise attributionAppendix B
gJEA Q3Added analysis of cost effects on graph structure and operator selectionAppendix D.7; Figure 9
mte7 W1Added few-shot CoT and baseline failure analysisTable 1; Appendix D.3; Appendix D.5
mte7 W2Added held-out MATH learning curvesIntroduction; Figure 1(b)
mte7 W3Added outcome-entropy selection baselineSection 4.5; Table 3

Detailed responses to each concern are provided under the corresponding review. Your time and effort in helping us improve the paper are sincerely appreciated. We hope these revisions address all concerns and further strengthen the paper. Thank you again for your time and helpful feedback.

Best regards,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.