PaperlayerView exact revision on arXiv

Source-linked AI summary

SRPO: Setwise Relative Policy Optimization for Multi-Agent LLMs

Shengtian Yang, Ziyu Xiong, Yu Li, Yewen Li, Qingpeng Cai, Lei Feng

arXiv:2609.08452v1cs.AI

TL;DR

Existing multi-agent RL methods often optimize responses or trajectories separately even when several outputs jointly produce one transition, creating a mismatch between the update unit and executed action. SRPO treats the transition’s minimal consumed output set as one action, using a cardinality-normalized set ratio and one clip; it provides a common interface across workflows and reports the highest displayed macro Avg@16 and Pass@16 on both Math and Search scales, with important comparison and cost limitations.

  • Problem

    Existing MAS-RL methods tie updates to workflow-specific roles, turns, or rollout layouts, so jointly transition-causing outputs lack a common action representation.

  • Method

    SRPO defines the active set as the minimal set of outputs consumed by one transition, combines member log-ratios with cardinality normalization, assigns one relative advantage, and clips once.

  • Results

    SRPO provides one action representation for fixed, mixed, and learned variable-cardinality workflows and obtains the highest displayed macro Avg@16 and Pass@16 on both Math and Search scales.

  • Takeaways & Limitations

    Division of labor and joint co-evolution become different active-set cardinalities within one policy-optimization interface across the four reported model scales.

  • Takeaways & Limitations

    Baseline rows are cross-paper references rather than paired reruns, sequence-level member log-ratios can depend on response length, and cost analysis uses an output-side proxy rather than end-to-end GPU time and tool latency.

Abstract

from arXiv · show

Multi-agent large language models solve complex tasks by coordinating several policies in a shared environment. However, existing reinforcement learning methods usually optimize each response or trajectory separately, even when several outputs jointly cause one state transition. Consequently, the update unit differs from the action executed by the system. To address this problem, we propose SRPO (Setwise Relative Policy Optimization), which treats the active set the minimal set of outputs consumed by one transition, as one multi-agent action. Specifically, SRPO combines member log-ratios into one cardinality-normalized set ratio, assigns one relative advantage, and clips the set once. This formulation unifies division of labor and joint co-evolution as actions with different set sizes. Experiments on mathematical reasoning and multi-turn search demonstrate one training interface for fixed, mixed, and dynamically routed workflows across four model scales, with the strongest macro-average results among the reported comparisons. Optimization diagnostics further characterize its stability under different event reductions and set sizes.

1 Introduction

Existing MAS-RL methods tie optimization units to workflow-specific roles, turns, or rollout layouts, so the same environmental decision can receive different updates. SRPO instead treats the transition-producing active set as one action across collaboration patterns.

  • Problem: Workflow-specific update units make agent identity, execution order, or rollout layout determine the optimizer’s action representation.This can produce different updates for the same environmental decision when contributing agents or their order changes.
  • SRPO: SRPO defines the active set as the minimal set of newly sampled outputs consumed by one state transition.This creates a workflow-independent action representation for multi-agent LLM systems.
  • SRPO: SRPO combines member likelihood changes into one cardinality-normalized set ratio, assigns one relative advantage, and clips the complete set once.The objective treats the complete transition-producing set as the optimization unit.
  • Unified interface: Singleton, multi-member, and changing-size active sets represent division of labor, joint co-evolution, and mixed or dynamically routed workflows.The same interface therefore covers collaboration regimes that existing methods typically organize separately.
  • Evaluation: The framework preserves rollout generation, reward design, and advantage estimation as interchangeable components while evaluating fixed, mixed, and routed workflows across four model scales.Experiments cover mathematical reasoning and multi-turn search, with diagnostics for gradient scale, response length, set cardinality, and event completeness.

2 Related Work

Prior work provides role-aware, turn-wise, group-relative, and orchestration-specific methods, but its policy actions remain tied to predefined workflow structures. SRPO connects multi-agent execution to a common optimization unit without requiring a new prompting or search procedure.

  • Policy actions: Existing language-agent RL methods commonly use responses or single-agent trajectories as policy actions, leaving jointly transition-causing outputs unspecified.This limits how several outputs can be represented as one multi-agent decision.
  • Workflow-specific methods: Recent MAS-RL methods organize updates by agent, turn, group, rollout layout, or heterogeneous role structure.Examples include multi-turn group-relative updates, agent- and turn-wise grouping, heterogeneous rollout groups, and agent-wise normalization.
  • Orchestration: Orchestration systems model spawning, delegation, communication, aggregation, and stopping, but do not define the policy action when several agents jointly change the environment.Execution design and optimization-unit design therefore remain distinct.
  • SRPO: SRPO defines outputs consumed by one transition as an active set, placing division of labor, joint co-evolution, and mixed orchestration in one optimization framework.The formulation remains compatible with existing execution systems, reward functions, and credit estimators.
  • Scope: The contribution is the policy-optimization unit for collaborating outputs rather than a new prompting or search procedure.The Search and Math environments build on established interaction patterns such as reasoning, retrieval, branching, and verification.

3 Preliminaries: Multi-Agent Decisions as Set-Valued Actions

The framework defines a multi-agent decision by the minimal set of outputs jointly consumed by one environment transition. Active-set cardinality unifies singleton division of labor and multi-output joint co-evolution, while setwise normalization aligns clipping with the transition.

  • Decision events: At decision event e, the shared pre-action state and execution schedule determine which policy outputs are sampled and consumed by the next transition.Each active-set member is produced by an event-specific policy, such as a router, worker, or aggregator.
  • Active set: The active set S_e is the minimal set of newly sampled outputs that the environment consumes together to produce the next state.The corresponding environment-facing action is the set of member outputs.
  • Transition boundary: Committed shared-memory proposals induce transitions even when external tool state is unchanged, whereas private uncommitted drafts do not.If only an aggregator output is committed, the active set is the aggregator’s singleton output.
  • Decision events: Outputs revealed sequentially belong to successive events because all outputs within one event derive from the same logical pre-action state.The environment-facing event action factorizes over member policies sampled from that shared state.
  • Collaboration regimes: Active-set cardinality K_e distinguishes collaboration regimes: singleton events represent division of labor, while K_e > 1 represents joint co-evolution.Mixed workflows vary K_e over time, making division of labor the singleton boundary of the same set-valued policy.
  • Setwise objective: SRPO normalizes summed member log-ratios by √K_e and makes one clipping decision for the event.This avoids independently constraining members or letting unnormalized event scale grow proportionally with active-set size.

4 Setwise Relative Policy Optimization

SRPO treats the complete multi-agent decision causing one environment transition as the policy action, while preserving standard rollout, reward, advantage, and optimizer machinery. It computes member-level policy changes, reduces them to one cardinality-normalized event ratio and one advantage, then clips and averages at the event level.

  • SRPO optimizes the complete multi-agent decision that causes an environment transition without changing rollout generation, rewards, advantage estimation, or the optimizer.
  • For each action record, SRPO computes a masked sequence log-ratio over generated response tokens using behavior and updated policies.Prompt, padding, and environment tokens are excluded from the member-level calculation.
  • SRPO combines member log-ratios into one normalized event log-ratio and event ratio for the complete active set.When the active set has one member, the score is the ordinary sequence-level likelihood ratio; larger sets receive cardinality normalization.
  • Each decision event receives one relative advantage derived from its downstream team return and its group of comparable events.The same scalar advantage is assigned to every member, while alternative action-independent estimators can replace the group-relative estimator.
  • SRPO clips each complete active set once and averages over complete events rather than member rows or tokens.Its event-atomic implementation keeps all rows from one event together, invalidates events with missing members, and retains selected outputs even when unquoted by the aggregator.
  • The same interface supports dynamically routed workflows in mathematical reasoning and multi-turn search, where selected policies interact with the environment and an aggregator produces the team-scored action.

5 Experiments

Experiments evaluate SRPO across mathematical reasoning and multi-turn search, using fixed, joint, and routed workflows. SRPO achieves the best reported macro averages while diagnostics examine cardinality, normalization, training stability, and output-side cost.

  • 5.1 Mathematical Reasoning: The experiments cover mathematical reasoning and multi-turn search with routed solver, verifier, worker, and aggregator workflows across multiple model scales.Math uses a solver–verifier loop with parallel candidates and singleton verification or revision events; search routes worker queries and aggregates retrieved evidence.
  • 5.1 Mathematical Reasoning: SRPO obtains the best macro averages in both reported Math settings, with gains over the strongest displayed Dr. MAS rows at both model scales.With Qwen3-4B, SRPO reaches 61.3 ± 0.5 macro Avg@16 and 77.9 ± 0.8 macro Pass@16; with Qwen3-8B, it reaches 62.5 ± 0.5 and 77.8 ± 0.7.
  • 5.2 Multi-Turn Search: SRPO also obtains the best macro averages in both reported Search settings, improving over the strongest displayed Dr. MAS rows at 3B and 7B.The reported macro Avg@16/Pass@16 values are 40.1±0.5/56.1±0.8 for Qwen2.5-3B and 45.6 ± 0.4/61.6 ± 0.7 for Qwen2.5-7B.
  • 5.3 Ablation Studies on Search: In the active-set ablation, the five-member SRPO variant exceeds the singleton boundary by 2.9 Avg@16 points and 3.7 Pass@16 points under square-root normalization.The comparison does not establish an advantage under an equal computation budget.
  • 5.3 Ablation Studies on Search: At K = 5, SRPO exceeds unnormalized-sum reduction by 1.5 Avg@16 and 1.8 Pass@16 points, and mean reduction by 5.4 and 7.5 points.The displayed ordering favors square-root scaling over both alternatives on Search task performance.
  • 5.4 Training Dynamics: Training diagnostics show finite gradient traces, changing active-set sizes, and no monotonic growth in generated team-token proxies across several runs.The event-reduced run’s gradient norm stays in [56.97, 108.10], while the learned router’s output-side proxy decreases from 1,144 to 788 tokens.

6 Discussion and Limitations

SRPO reports the highest displayed macro Avg@16 and Pass@16 across both Math and Search scales, with the largest gains on Search. The authors qualify these comparisons by noting cross-paper baselines, response-length dependence, output-side cost proxies, and deployment trade-offs.

  • Results: SRPO obtains the highest displayed macro Avg@16 and Pass@16 on both Math scales and both Search scales.The largest gains are reported on Search.
  • Limitations: Cross-paper baseline rows make the comparison descriptive rather than a result from paired reruns.
  • Limitations: The sequence-level member log-ratio can still depend on response length.
  • Limitations: The cost analysis uses an output-side proxy rather than end-to-end GPU time and tool latency.Establishing end-to-end cost efficiency requires further measurements.
  • Deployment considerations: Activating more models concurrently can increase agentic-system scale and cost, while parallel agents can amplify correlated retrieval errors.Future deployments should jointly optimize utility with token, latency, and tool-use cost.

7 Conclusion

The conclusion defines the active set as the multi-agent action and instantiates it with SRPO, which clips one cardinality-normalized surrogate per environment-changing event. Completed math and search runs demonstrate the interface across model scales.

  • Conclusion: SRPO defines the active set as the action for multi-agent reinforcement learning and clips one cardinality-normalized surrogate per environment-changing event.
  • Conclusion: Division of labor and joint co-evolution become different cardinalities of the same policy representation.
  • Conclusion: The surrounding reinforcement-learning pipeline remains unchanged under this action representation.
  • Conclusion: Completed math and search runs demonstrate the interface across model scales.

Supplementary Material Contents

The supplementary material lists appendices covering task descriptions for Math and multi-turn Search. It also includes sections on random-seed reporting and optimization-stability diagnostics.

  • Appendix A: Random-seed reporting is included in supplementary section A.1.
  • Appendix B: The supplementary material describes the Math task in section B.1 and the multi-turn Search task in section B.2.

C Pseudocode 15

The supplementary material includes optimization diagnostics and case studies for Math and multi-turn Search. Its diagnostics cover gradient-norm stability, cross-run stability, and reduction-variant training curves.

  • Optimization diagnostics: Gradient-norm stability on Math is covered in supplementary section D.1.
  • Optimization diagnostics: Cross-run stability and training curves of reduction variants are covered in sections D.2 and D.3.
  • Case studies: Supplementary case studies cover multi-turn Search in section E.1 and Math in section E.2.

A Experimental Reporting Details

The experiments use fixed, adaptive, and search-oriented multi-agent workflows with explicit prompt roles, parser constraints, and event-level training diagnostics. The completed 8B comparison reports lower gradient variation for event-level reduction while active-set size changes during training.

  • Reporting protocol: Three-seed means and sample standard deviations are reported for the headline Math and Search results.The headline tables use shared benchmark definitions, decoding, and checkpoint-selection rules.
  • Prompt and validation design: Prompt templates expose environment state, teammate outputs, and role-specific instructions while enforcing parser-visible solver, verifier, router, and aggregator outputs.Malformed responses receive an invalid-action penalty and downstream orchestration follows the recorded parser state.
  • Math orchestration: Math workflows route solver outputs through verification and aggregation, with parallel candidates forming one active set and singleton verification or revision events.Fixed-K workflows activate the configured solver set directly, whereas adaptive routing selects a subset or stops.
  • Search orchestration: Search workflows use routers, parallel workers, evidence verification, and answer aggregation to iteratively resolve missing factual relations.Dynamic routing selects the smallest sufficient worker subset, while verification checks whether required relations are directly supported.
  • Reduction diagnostics: 90.7 versus 72.1 mean gradient norm distinguishes token-reduced from event-reduced 8B runs, while event reduction has coefficient of variation 0.107.The event-reduced run’s mean active-set size changes from 2.233 to 2.421 as training proceeds.

D.3 Training Curves of Reduction Variants

The reduction-variant diagnostics separate optimization conditioning from downstream accuracy and illustrate how SRPO groups outputs consumed by shared-state transitions. Event-level reduction shows lower gradient variation while the traces distinguish set-valued proposal actions from singleton verification and revision.

  • Training curves: 58.5 versus 53.2 validation Avg@16 compares token-reduced and event-reduced 8B runs, while event reduction has lower gradient variation.The comparison separates downstream accuracy from optimization conditioning.
  • Search event structure: The search traces use parallel queries to resolve multiple relations, then singleton queries when only one unresolved relation remains.One example records K1 = 2 and K2 = 1; another uses sets of three and two queries for successive relation groups.
  • Search event structure: Retrieved documents are verifier observations rather than policy members, so event cardinality counts queries consumed by the transition.The first search transition therefore remains K1 = 2 despite producing several documents.

E.2 Math Task: Iterative Coordination

The math traces show iterative coordination in which competing solver outputs are verified before revision or answer selection. The examples demonstrate that SRPO treats parallel proposals as set-valued actions and later verification or revision as singleton actions.

  • Combinatorial verification: 30 versus 15 exposes a combinatorial double count in the hexagon problem: unordered intersecting diagonal pairs correspond one-to-one with four-vertex subsets.The no-three-diagonals condition makes this correspondence one-to-one.
  • Combinatorial verification: The verifier rejects the first hexagon solution because it counts each unordered diagonal pair twice, while the four-vertex bijection supports the second solution.The verification explicitly checks both the unordered-pair convention and the four-vertex correspondence.
  • Modular-arithmetic verification: 401 is the verified last-three-digit residue for 7^2024, supported by Chinese-remainder and direct-squaring checks after one solver’s multiplication error.The verifier rejects Solver 1 and approves Solvers 2 and 3.
  • Iterative event structure: The modular trace uses three competing derivations, a singleton verification event, answer selection, and a final singleton revision.The event audit records cardinalities 3, 1, 1, and 1 for the successive math actions.
  • Event bookkeeping: Event identity keeps outputs sharing a pre-action state together through ratio construction, advantage assignment, clipping, and batch reduction.This provides an implementation check for preserving set membership during optimization.
Loading 2609.08452v1…