PaperlayerView exact revision on arXiv

Source-linked AI summary

MASPRM: Multi-Agent System Process Reward Model

Milad Yazdani, Mahdi Mostajabdaveh, Zirui Zhou, Ying Xiong

arXiv:2510.24803v3cs.MAcs.AI

TL;DR

Multi-agent search needs progress signals over routed messages, where agents act under different schedules and local views. MASPRM scores transcript prefixes and guides SBS and MCTS using terminal-reward rollouts; under stepwise search, it improves over size-matched ORM across four benchmarks.

  • Problem

    Multi-agent process supervision must account for routed messages, agent schedules, heterogeneous roles, and agents’ different local views.

    Source: §1 · p. 2

  • Method

    MASPRM scores routed-transcript prefixes and agent actions to guide SBS and MCTS, training its value model from rollout-derived preferences backed up from terminal rewards.

    Source: §1 · p. 2, §3 · p. 4, §4.1 · p. 5

  • Results

    Across four benchmarks, stepwise MASPRM beats size-matched ORM by +2.0 to +3.0 points at 1.5B and +4.1 to +14.5 at 7B.

    Source: §7 · p. 8

  • Takeaways & Limitations

    MASPRM transfers across related datasets and agent LLMs without retraining.

    Source: §7 · p. 8

    The study covers predefined, role-pipelined MAS configurations on verifiable terminal-answer tasks; open-ended generation and dynamically structured MAS remain future work.

    Source: §8 · p. 9

Abstract

from arXiv · show

Inference-time search over multi-agent systems (MAS) wastes compute when it cannot identify which agent's intermediate message advanced progress. We present the Multi-Agent System Process Reward Model (MASPRM), which scores routed transcripts (ordered sequences of messages between agents) and acts as an inference controller for step-level beam search (SBS) and Monte Carlo Tree Search (MCTS). MASPRM is trained from multi-agent MCTS rollouts labeled only with terminal outcome rewards, without human step-level annotations. We evaluate on GSM8K, MATH, MMLU, and LogiQA. Under matched scorer size and comparable MCTS budget, MASPRM exceeds a size-matched ORM by $+2.0$ to $+3.0$ points at 1.5B and $+4.1$ to $+14.5$ at 7B across all four benchmarks, with additional scorer-scaling gains over policy likelihood at 7B (avg $+13.4$ under MCTS). MASPRM also improves ranking quality, reducing Hit@1 to Hit@5 gaps by up to $10.3$ points, with the largest gains under stepwise search that uses intermediate decisions. Code: https://github.com/milad1378yz/MASPRM

1 Introduction

Inference-time search in multi-agent systems needs to identify which intermediate messages advance progress, but routed transcripts combine agent schedules, routing, heterogeneous agents, and partial observability. MASPRM scores transcript prefixes and proposed actions, is trained from terminal-reward rollouts, and guides search; on GSM8K, it outperforms a matched-size ORM under comparable MCTS budgets.

1 Introduction

  • +3.0 Hit@1 at 1.5B and +14.5 at 7B: MCTS(10, 3)+MASPRM beats matched-size ORM on GSM8K, reaching 82.9 with the 7B scorer.Figure 1 shows Hit@1 versus inference tokens.Source: Figure 1 · p. 1, §1 · p. 2
  • Answer-level voting and reranking do not identify which intermediate agent message advanced progress, while extending likely-but-misaligned prefixes can waste compute.Reliable guidance is needed over long routed transcripts.Source: §1 · p. 1
  • MASPRM scores routed-transcript prefixes and proposed agent actions, conditioning on the full transcript, acting-agent identity, and transcript ordering.Agents propose actions from local views, while the scorer provides a consistent global representation for inference-time search.Source: §1 · p. 2
  • Multi-agent process reward modeling must account for agent actions as steps, message routing and schedule, heterogeneous roles, and each agent’s partial view.These four challenges distinguish MASPRM development from single-agent reasoning.Source: §1 · p. 2
  • MAS-MCTS backs up terminal rewards to agent-action values, enabling MASPRM training without human step-level annotations.The method forms sibling preferences from these values.Source: §1 · p. 2, Figure 2 · p. 2
  • MASPRM-guided step-level beam search and MCTS allocate inference compute over agent rollouts, expanding promising branches and pruning unproductive ones.The contribution applies to predefined multi-agent systems.Source: §1 · p. 2

2 Related Work

Prior work studies multi-agent coordination, inference-time search, and process supervision, but MASPRM focuses on learning process values over routed transcripts in a fixed multi-agent system. Multi-agent routing and agents’ differing local views make a partial state different from a single-agent linear prefix.

2 Related Work

3 Preliminaries

The paper models a multi-agent execution as a finite routed transcript over a directed communication graph, with actions proposed from each acting agent’s local view. States track the question, transcript prefix, and acting agent; terminal correctness supplies the reward used to define state and action values.

3 Preliminaries

  • A multi-agent execution is a finite ordered list of routed messages on a directed graph, ending when a message reaches the terminal node.The graph’s edges indicate which agents can route messages to which recipients.Source: §3 · p. 3
  • A fixed schedule determines the acting agent at each turn, with rollouts ending at the sink or after the final scheduled action.The main experiments terminate after the final scheduled turn, though earlier stopping is allowed.Source: §3 · pp. 3–4
  • Agents propose actions from their local transcript views, while the default MASPRM scorer uses the full routed transcript prefix and acting-agent identity.Valid actions pair a message with an outgoing recipient; routing changes who observes messages, not the fixed turn schedule.Source: §3 · p. 4
  • Terminal answers receive reward +1 when correct and −1 otherwise; V(s) and Q(s, a) are expected terminal rewards under future rollout actions.Non-terminal states receive reward 0, and deterministic transitions imply Q(s, a) equals the value of the successor state.Source: §3 · p. 4
  • Search samples candidate actions from the acting agent’s policy and uses a learned process-value estimate to score states; MCTS also tracks edge visits and backed-up values.Rollouts respect the communication graph and schedule, with a bounded candidate set and maximum depth.Source: §3 · p. 4

4 MASPRM

MASPRM learns values for intermediate multi-agent states from terminal outcomes and uses those values to guide inference-time search. Its training creates preferences among sibling successor states, while MCTS and step-level beam search use the scorer to select promising continuations.

4 MASPRM

  • MASPRM assigns intermediate MAS states values through a shared head, with candidate actions generated under the communication graph.The pipeline uses MAS-MCTS rollouts to train the scorer and shares policy expansion and value scoring across MCTS and SBS.Source: §4 · p. 4

4.1 MASPRM training

  • MAS-MCTS terminal rewards are backed up into action-value targets for visited successors, producing process labels without manual step-level annotations.Sibling successors from the same parent are compared to form preference pairs, and the value head is trained with a Bradley-Terry ranking loss.Source: §4.1 · pp. 4–5

4.2 Inference guidance

  • At inference, MCTS uses scorer values to initialize and evaluate search edges, then backs up values and decodes along the child with the highest backed-up value.UCT selects actions during tree search.Source: §4.2 · p. 5
  • For SBS, each beam state is expanded with sampled actions, successors are scored, and the top-B1 states are retained at each depth.The final answer is the highest-scoring terminal state in the final beam.Source: §4.2 · p. 5

5 Experiments & Results

The experiments compare inference methods and scorers on four verifiable-answer datasets, using fixed MAS configurations and matched budgets within each search-method block. MASPRM outperforms matched-size ORM under MCTS and shows transfer across datasets and agents, with ablations examining scorer inputs, ranking, graph sensitivity, and dynamic scheduling.

5.1 Overall experimental setup

  • Experiments use GSM8K, MATH, MMLU, and LOGIQA with fixed dataset configurations, comparing policy likelihood and learned scorers under matched agent-call and token budgets within each search method.ORM scores only completed transcripts, so it is excluded from SBS, which ranks intermediate successors.Source: §5.1 · pp. 5–6, §5 · p. 5

5.2 MASPRM improves MAS within budget

  • Under MCTS(10, 3), MASPRM exceeds size-matched ORM by +2.0 to +3.0 points at 1.5B and +4.1 to +14.5 at 7B across all four datasets.With 1.5B agents, 7B MASPRM improves over policy likelihood by an average of +13.4 under MCTS(10, 3).Source: §5.2 · p. 6, Table 1 · p. 7

5.3.1 Cross-dataset transfer

  • Within-domain cross-dataset transfer averages 5.8 points below in-domain MASPRM but +7.6 points above policy likelihood.The transfer evaluation trains on one dataset and tests on a related dataset without retraining the reward model.Source: §5.3.1 · pp. 6–7, Table 2 · p. 7

5.3.2 Cross-agent transfer

  • MASPRM-7B trained on Qwen2.5-1.5B-Instruct rollouts transfers to Llama3.2 3B-Instruct without retraining, exceeding policy likelihood by +8.7 to +13.0 points and ORM-7B by +4.0 to +8.0.Source: §5.3.2 · p. 7

5.4 Ablations

  • Bradley-Terry is the best MASPRM reward head on all four datasets at both scorer sizes, while BCE is the best or tied ORM head.With optimal heads and size-matched 1.5B models, MASPRM is 2.0 to 3.0 points above ORM under MCTS(10,3).Source: §5.4 · p. 7
  • Using the full routed transcript beats the local-view scorer by 2.2 to 5.5 points on every dataset under MCTS(10,3).Source: §5.4 · p. 7
  • The GSM8K dynamic scheduler has higher mean Hit@1 than scheduled MAS1 in Single-Pass and MCTS(10,3), but MCTS cost rises substantially.The authors treat this as preliminary evidence of applicability beyond predefined MAS configurations, not a broad scheduling claim.Source: §5.4 · pp. 7–8
  • MASPRM-7B narrows the average Hit@1-to-Hit@5 gap under MCTS and SC@5, while guided-search ranges across three GSM8K graphs are smaller than the Single-Pass range.The reported gaps are 16.1 to 5.8 under MCTS and 19.0 to 10.5 under SC@5; graph ranges are 1.8 to 2.2 points versus 9.0 points for Single-Pass.Source: §5.4 · p. 8

6 Discussion

MASPRM improves inference-time search in the predefined multi-agent configurations studied, with the strongest evidence under stepwise search, especially MCTS. Its advantages vary by inference procedure and task, while transfer and graph-sensitivity results broaden the tested scope.

6 Discussion

  • MASPRM improves search in the studied predefined configurations, especially MCTS, narrows Hit@1-to-Hit@5 gaps, and benefits from full multi-agent state representation.The evidence is strongest when the scorer guides intermediate branch expansion or pruning.Source: §6 · p. 8
  • +2.0 to +3.0 points at 1.5B and +4.1 to +14.5 at 7B over size-matched ORM across four datasets under MCTS.At 1.5B, SC@5 improves over policy likelihood but does not beat ORM; the 7B-versus-policy-likelihood gains also reflect scorer scaling with fixed 1.5B agents.Source: §6 · p. 8
  • MASPRM does not universally replace ORM for final-answer selection; preference-ranking heads fit search particularly well because they mirror its pairwise selection comparisons.Process guidance is most useful when the algorithm repeatedly makes intermediate search decisions.Source: §6 · p. 8
  • MASPRM transfers without retraining across related datasets and one different generator, while in-domain training remains better; guided search reduces, but does not eliminate, sensitivity across three tested GSM8K graphs.Source: §6 · p. 8
  • Guided small-agent MAS is strong on GSM8K and MMLU, roughly competitive on MATH, while the strongest single-agent baselines remain ahead on LOGIQA.The results suggest inference-time multi-agent search complements, but does not yet substitute for, large-model scaling on harder reasoning tasks.Source: §6 · p. 8

7 Conclusion

MASPRM scores routed transcript prefixes to guide step-level beam search and MCTS in predefined multi-agent systems on verifiable terminal-answer tasks. Across four benchmarks, its advantage over size-matched ORM is strongest in MCTS, and it also transfers across related datasets and agent LLMs without retraining.

7 Conclusion

  • MASPRM is a process reward model for multi-agent systems on verifiable terminal-answer tasks that scores routed transcript prefixes and guides SBS and MCTS.Source: §7 · p. 8
  • +2.0 to +3.0 points at 1.5B and +4.1 to +14.5 at 7B over size-matched ORM across four benchmarks under MCTS.The comparison depends on inference method: SC@5 at 1.5B is mixed, while stepwise search benefits more from MASPRM.Source: §7 · p. 8
  • Transfer across related datasets and agent LLMs without retraining suggests learned process-level value signals can be a useful component for MAS search.Source: §7 · pp. 8–9

8 Limitations

The study covers predefined, role-pipelined multi-agent configurations on verifiable terminal-answer tasks. Open-ended generation and dynamically structured systems remain future directions, and the default full-transcript scorer fits centralized inference.

8 Limitations

  • The study is scoped to predefined, role-pipelined MAS configurations on verifiable terminal-answer tasks, where process-value supervision is well-defined.Source: §8 · p. 9
  • Open-ended generation, where terminal correctness is undefined, is left to future work; mixed-initiative or dynamically structured MAS are a natural next step.The paper reports one preliminary instance of dynamically structured MAS.Source: §8 · p. 9
  • The default scorer uses the full routed transcript and fits centralized inference; the full-transcript variant exceeds the local-view variant by 2.2 to 5.5 Hit@1 points.The authors identify decentralized scorers that close this gap as future work.Source: §8 · p. 9
  • Inference-time scoring cost scales with transcript length but remains substantially below per-agent generation cost.On GSM8K, a scorer call takes 0.16s versus 18.94s for an agent call.Source: §8 · p. 9

9 Ethical Considerations

The ethical discussion limits MASPRM to research on predefined multi-agent systems and verifiable terminal-answer benchmarks, while warning that it does not guarantee correctness or safety. The appendix illustrates fixed agent scheduling, routed message paths, divergent transcript trajectories, and how terminal rewards are backed up to train the scorer.

9 Ethical Considerations

  • MASPRM is studied for predefined MAS on verifiable terminal-answer benchmarks, not as a guarantee of correctness or safety.High-stakes use calls for task-specific validation, uncertainty reporting, and human oversight; the method also adds inference-time computation and may introduce privacy, security, or misuse risks in open-ended settings.Source: §9 · p. 9

A.1 Example MAS and schedule

  • A fixed schedule orders one turn per agent, while directed edges specify allowed message routes from the question to the final answer.Source: Figure 3 · p. 11, §A.1 · p. 11

A.2 Stylized transcript for an arithmetic word problem

  • The ticket example contrasts a trajectory preserving the requested VIP-minus-standard revenue quantity, which returns 410, with one answering a different quantity and returning 550.Source: §A.2 · p. 11, Figure 4 · p. 12

A.3 MCTS backpropagation example

  • Terminal correct and incorrect answers receive rewards of +1 and −1, which are backed up along visited paths to form sibling-comparison values for MASPRM training.Source: §A.3 · pp. 11–12, Figure 5 · p. 12

B.1 Benchmarks and Dataset Splits

The appendix specifies data splits, answer scoring, MASPRM and ORM training, search procedures, and compute accounting, then reports contextual and ranking comparisons. Its results include large guided-MAS gains over direct small-model baselines and narrower Hit@1-to-Hit@5 gaps under MASPRM scoring.

B.1 Benchmarks and Dataset Splits

  • A development set is held out from the shuffled training pool, with 5% reserved for hyperparameter selection; dataset-specific training and evaluation partitions are specified for MATH, GSM8K, LogiQA, and MMLU.The evaluation set is held out for reporting, and the appendix points to Table 3 for exact split sizes.Source: §B.1 · p. 12

B.2 Answer extraction and normalization

  • Final answers are extracted from terminal-agent outputs using answer tags when present, with dataset-specific fallbacks and normalization; non-parsable outputs or timeouts score incorrect.Free-form numeric answers are accepted within tolerance δ = 10^-3, while multiple-choice outputs are mapped to canonical labels.Source: §B.2 · pp. 12–13

B.3 MASPRM training data generation

  • MASPRM process targets use backed-up Monte Carlo values, and mined preference pairs compare high- and low-valued sibling actions; each tree contributes at most eight pairs.The scorer uses a Qwen2.5-1.5B or 7B backbone and a scalar head; the BT variant ranks pairs, while the MSE variant regresses to process targets.Source: §B.3 · p. 13, §B.4 · p. 13

B.5 Search configurations

  • MCTS uses UCT and MASPRM leaf values, while SBS retains globally top-ranked candidates at each depth; policy likelihood ranks successors or initializes/evaluates MCTS states.Full-rollout scoring averages per-action MASPRM values or policy scores, whereas ORMs score completed transcripts only.Source: §B.5 · pp. 13–14, §B.9 · p. 15

B.6 Compute budgets and accounting

  • Within each search-method block, agent-call and token budgets are matched or made comparable, with reward-model calls accounted for according to whether scoring occurs per successor or only at terminal evaluations.MCTS budgets are reported as empirical mean ± standard deviation because calls are stochastic; experiments used eight V100 GPUs.Source: §B.6 · p. 14, §B.7 · p. 14

B.10 ORM Γ

  • For ORM training, intermediate states are discarded and only terminal outcomes supervise the scorer; the appendix also reports artifact licensing and intended-use boundaries.ORMs are trained with BCE or MSE heads, while datasets and model artifacts are used under their stated licenses or provider terms and are not redistributed.Source: §B.10 · p. 15, §B.11 · p. 15

C.1 Contextual single-agent comparison

  • +41.0, +34.3, +40.9, and +19.7 points are the MCTS(10,3)+MASPRM gains over direct Qwen2.5-1.5B-Instruct on GSM8K, MATH, MMLU, and LOGIQA, respectively.On LOGIQA, MCTS(10,3)+MASPRM reaches 45.5, below GPT-4o-mini at 50.1 and Mistral 24B-Instruct at 56.4; the comparison is not matched by AC/TOK.Source: Table 4 · p. 15, §C.1 · p. 15

C.2 Hit@k sensitivity under limited candidates

  • +10.3 points for MCTS and +8.5 points for SC@5 are the reductions in average Hit@1-to-Hit@5 gaps with MASPRM versus policy likelihood.The comparison uses Qwen2.5-1.5B-Instruct agents; SBS(5,3) returns only three terminal candidates, so Hit@5 is not applicable there.Source: §C.2 · p. 16

C.3 Cross-LLM transfer results

The transfer experiment tests whether reward models trained on Qwen2.5-1.5B-Instruct rollouts can guide Llama3.2 3B-Instruct agents without retraining. MASPRM-7B achieves the highest Hit@1 across datasets and search methods reported, with positive MCTS gains over both policy likelihood and ORM-7B.

C.3 Cross-LLM transfer results

  • +11.2, +8.7, +13.0, and +8.7 points are MASPRM-7B’s MCTS(10,3) gains over policy likelihood on GSM8K, MATH, MMLU, and LOGIQA, respectively.MASPRM-7B gives the highest Hit@1 across SC@5, SBS, and MCTS in every dataset when guiding Llama3.2 3B-Instruct agents with fixed reward models.Source: §C.3 · p. 16

C.4 Head-type ablation for MASPRM and ORM

The ablations compare reward-model heads and scorer observability, and describe a separate dynamic-scheduler experiment on GSM8K. BT is the best tested MASPRM head, while full-transcript scoring has the highest Hit@1 across the four datasets in the observability comparison.

C.6 DYLAN-style dynamic scheduler on GSM8K

  • The GSM8K dynamic setup uses three solver agents, an agreement-checking judge, and conditional refinement when the judge disagrees, with a final judge producing the terminal answer.Training data generation and testing are run from scratch for each setup, including a newly trained MASPRM-7B for MCTS evaluation.Source: §C.6 · pp. 16–17

C.4 Head-type ablation for MASPRM and ORM

  • +0.3 to +4.3 points for 1.5B and +0.3 to +9.6 points for 7B are the BT-head gains over MSE across four datasets; BT is best for MASPRM at both sizes.For ORMs, BCE is best or tied, supporting BT for MASPRM and BCE for ORM in the main comparison.Source: §C.4 · p. 16, Table 7 · p. 17

C.5 Local observability ablation for MASPRM

  • Full routed-transcript scoring gives the highest Hit@1 on all four datasets; the local-view variant lowers Hit@1 by 5.5 points on GSM8K, 2.4 on MATH, 3.5 on MMLU, and 2.2 on LOGIQA.Both variants use the same rollouts, agent model, search budget, MCTS(10,3) setting, and MASPRM-7B backbone.Source: §C.5 · p. 16, Table 8 · p. 17

C.7 Graph sensitivity ablation on GSM8K

This section examines MASPRM-guided search’s sensitivity to agent communication graphs on GSM8K and documents task-specific workflows, communication schedules, and related transfer, runtime, and MAS configuration details. It also describes training process targets from terminal outcomes and using the learned scorer to guide MCTS or step-level beam search.

C.7 Graph sensitivity ablation on GSM8K

  • The scorer is trained on MAS1 rollouts and transferred unchanged to MAS2 and MAS3; at each prefix, candidate next-step messages are scored as successor states for relative selection.All three use Qwen2.5-1.5B-Instruct agents and a Qwen2.5-7B-based MASPRM-7B scorer, with role prompts and directed communication graphs as the only differences.Source: §C.7 · pp. 17–18
  • 9.0 points separate MAS1–MAS3 single-pass Hit@1 (47.2 to 56.2), while MASPRM-guided SBS/MCTS narrows configuration ranges to 1.8–2.2 points, reductions of 6.8–7.2 points.The SBS/MCTS ranges are 73.4 to 75.2, 77.5 to 79.7, and 80.9 to 82.9 across the three configurations.Source: Table 10 · p. 18, §C.7 · p. 18

C.8 OOD transfer protocol

  • +5.3 to +11.1 points is the cross-dataset transfer advantage over policy likelihood on each target, although transfer remains below in-domain results.The protocol evaluates GSM8K→MATH, MATH→GSM8K, MMLU→LOGIQA, and LOGIQA→MMLU using MCTS(10,3) and Qwen2.5-1.5B-Instruct agents.Source: §C.8 · p. 18

C.9 Wall-clock Comparison

  • 11 min for MCTS(10,3) and 16 min for SBS(5,3) are the estimated per-instance GSM8K runtimes; one MASPRM scorer pass is about 118 times faster than one agent generation.Mean agent-generation and reward-scorer times are 18.94 s and 0.16 s, respectively.Source: §C.9 · p. 18

D MAS Graph, Prompts, and Configuration

  • The paper varies MAS depth, agent roles, and directed communication graphs across settings, drawing on decomposition, self-refinement, and multi-agent debate designs.The appendix includes the GSM8K MAS3 consensus configuration and a GSM8K dynamic scheduler configuration.Source: D MAS Graph, Prompts, and Configuration · p. 18

D.1 Agent roles, system prompts, and decoding

  • MASRPSV uses Reader→Planner→Solver→Verifier (Wang et al., 2023a), MASRefine uses Solver→Evaluator→Reflector→Reviser (Madaan et al., 2023), and MASConsensus uses dual solvers with a judge (Wang et al., 2023b).These configurations implement plan-then-solve with verification, an explicit feedback-and-refine loop, and consensus-style answer selection, respectively.Source: §D.1 · pp. 19–20
  • The appendix specifies task-specific MAS workflows, including Angel/Devil debate with Judge aggregation and a constraint-extraction, world-building, and option-checking pipeline.The configurations are presented for MMLU and LogiQA, respectively.Source: §D.1 · p. 21

D.2 Communication edges and schedule

  • Communication graphs are directed, with schedules fixed by listed agent order except DYLAN-style conditional refinement, which runs only after Judge disagreement.The Judge's agreement makes its output terminal and skips the refinement layer.Source: §D.2 · pp. 21–22

E Algorithms (Brief Overview)

  • At inference, MCTS bootstraps leaf evaluations with Vϕ and initializes new children with virtual visits, unlike training, which backs up ground-truth terminal rewards.Decoding greedily follows the child with maximal bQ at each depth.Source: E Algorithms (Brief Overview) · pp. 22, 24
  • Training assigns expanded edges process targets from backed-up terminal outcomes and fits the process head with within-parent sibling preference pairs using a Bradley–Terry ranking loss.The target for each child is the edge's backed-up value, bQ(s, a).Source: E Algorithms (Brief Overview) · p. 23
  • Step-level beam search expands candidates at each scheduled agent depth, scores successor states with a selected scorer, and keeps the global top-B1 states.It returns the highest-scoring terminal state in the final beam.Source: E Algorithms (Brief Overview) · p. 24
Loading 2510.24803v3…