acceptodds
Under review as a conference paper at ICLR 2027

Counterfactual Credit Assignment over Execution Graphs of LLM-based Multi-agent Systems

Abstract

Training LLM-based multi-agent systems (MAS) requires assigning credit to agents for how their actions influence subsequent interactions and outcomes. We present RollCredits, a method for assigning decision-level credit through counterfactual advantage estimation. At a shared history, the expected reward difference between an action and policy-sampled alternatives equals the acting agent’s advantage. We formalize these comparisons using execution graphs to represent agent interactions, including sequential, parallel, and multi-round structures, with potentially distinct rewards for different agents. Each candidate action completes the downstream execution it induces and is scored by the acting agent’s reward, and we establish sampling and replay conditions under which the resulting group-relative estimator is unbiased after a fixed group-size correction. To keep collection affordable, candidates branch from decision states saved during seed executions and their continuations run concurrently. Across mathematical reasoning, code generation, and competitive games, RollCredits leads in four code metrics, three math metrics, and three games, including a held-out game. Diagnostics against an independently sampled reference show nearly unbiased credit, while local feedback retains bias despite additional sampling. In controlled math and game experiments, saved-state reuse reduces prompt recomputation by 24–25% compared with ancestor replay.

Primary area:
reinforcement learning
Keywords:
LLM-based multi-agent systems, Multi-agent reinforcement learning, Counterfactual credit assignment, Execution graphs, Advantage estimation

Reviews

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

The authors propose ROLLCREDITS, a method for credit assignment through counterfactual advantage estimation. They use execution graphs to provide a unified representation of multi agents interaction pipelines. At the same interaction history, an LLM agent generates multiple candidate responses, and each branch is executed to completion. The resulting outcomes are then compared using the acting agent’s final reward. Experiments demonstrate performance improvements in math, coding, and games.

Critical strengths

The DAG formulation is clearly presented, the overall pipeline is well motivated, and the experimental results are strong. The generalisation to a game not seen during training is particularly interesting.

Critical weaknesses

The proposed idea and method appear quite similar to this prior work [1], which already introduces a counterfactual rollout estimator with an unbiasedness guarantee and branching from saved states to reduce computation. This case would diminish the paper’s contributions and novelty. The unified execution-graph formulation appears to be a new contribution, but its significance is not clearly demonstrated in the method design or experiments. All above raises concerns about the paper’s novelty and overall contributions.

[1] Exact Is Easier: Credit Assignment for Cooperative LLM Agents

Questions for authors
  1. The authors need to explain the difference between Exact Is Easier and their paper. If possible, the authors need to add the Exact Is Easier as one baseline in the exprionments.

  2. Could you include at least one parallel fan-out/fan-in topology?

  3. Is the token budget kept consistent across all the other baselines?

5 comments
AuthorsOpenReview ↗

Response to Reviewer NwT8 (1/2)

We thank the reviewer for recognizing the DAG formulation, the strength of the results, and the held-out game generalization.

R3.W1 / R3.Q1: Distinctions from C3 and baseline comparison

Relation to C3. The table in the General Response compares RollCredits with C3 in sampling, replay, saved state and reward target.

Effect of the execution-graph formulation. The reviewer recognizes this formulation as new and asks for evidence of its significance, which competitive games and the parallel workflow provide. In games, each player is credited with its own reward, which a shared team reward cannot express; RollCredits leads in three of four games and wins 85.16 ± 0.52% on held-out Breakthrough, against 70.18 ± 0.60% for the strongest baseline. In the parallel workflow (Q2), the graph shows that a solver's siblings do not depend on it, so replay keeps their outputs and regenerates only the aggregator, which reduces generated tokens per comparison group by 46.2% and 31.0% at the first two solver positions with similar credit MSE.

C3 as a baseline. Over three training seeds, C3 reaches MAS pass@8 of 84.67 ± 0.17 in math and 71.53 ± 0.77 in code, versus 87.09 ± 0.68 and 72.95 ± 0.62 for RollCredits. C3's game entries are n/a because our games assign opposing rewards to the two players.

R3.Q2: Parallel fan-out/fan-in workflow

We added a fan-out/fan-in math workflow: three solvers answer in parallel and an aggregator produces the final answer from their outputs. A solver's history contains only the task, so its siblings are not downstream of it; the aggregator is.

The parallel-workflow comparison uses one training run per method and the overlap-filtered math test set.

MethodMAS pass@1MAS pass@8
Base54.1464.42
GRPO71.2183.05
traj-GRPO73.3585.19
Dr. MAS73.8085.24
AT-GRPO69.6384.94
C3 (parallel adaptation)70.9685.29
VinePPO70.2285.19
RollCredits, serialized-trace replay73.2086.53
RollCredits, dependency-preserving replay72.9386.53

Both RollCredits replay rules reach 86.53% MAS pass@8, the highest among these methods. Serialized-trace replay regenerates calls recorded after the decision, including later sibling solvers. Dependency-preserving replay retains unaffected sibling outputs and regenerates the aggregator. Both rules preserve the same solver inputs; a solver never sees its siblings' answers.

At a fixed checkpoint, we compare both replay rules against an independent high-budget advantage reference with matched visible histories and candidate actions. Repeated trials resample sibling outputs from their conditional distribution; dependency-preserving replay shares those outputs across candidates within each trial. Each cell below reports dependency-preserving / serialized-trace replay. Generated tokens include seed cost, allocated over the groups it serves.

Solver positionMean absolute biasVarianceMSEGenerated tokens per group
solver 10.077 / 0.0740.171 / 0.1720.181 / 0.18130.4k / 56.5k
solver 20.077 / 0.0710.174 / 0.1750.183 / 0.18330.0k / 43.5k
solver 30.071 / 0.0700.172 / 0.1740.180 / 0.18230.8k / 30.8k

Dependency-preserving replay reduces generation by 46.2% at solver 1 and 31.0% at solver 2, with similar MSE. At solver 3, both rules regenerate only the candidate and aggregator, so their generation counts coincide. The empirical bias estimates use eight trials per candidate and include finite-trial and reference sampling noise. The independent reference uses 32 continuations per candidate, as in Figure 3. We run the diagnostic on the final RollCredits checkpoint of the parallel workflow, using 96 decision states (32 problems × 3 solver positions).

AuthorsOpenReview ↗

Response to Reviewer NwT8 (2/2)

R3.Q3: Token budgets

The optimization schedule and sequence budget are the same across methods: 220 updates for math/games and 162 for code, with 64 groups of 8 sequences per update. Training-token totals vary with sequence length, and generation budgets vary with rollout collection. RollCredits, C3 and VinePPO all estimate credit from sampled continuations, so generation is the cost each pays for its credit signal, and a matched generation budget compares how efficiently each estimator uses it. For each pair, the budget is the smaller of the two methods' total generation, and the method that generated more is evaluated at its checkpoint reaching that budget.

DomainBaselineGeneration budget (B)Baseline MAS pass@1 / pass@8RollCredits MAS pass@1 / pass@8
MathC30.8970.54 / 84.6070.62 / 85.29
MathVinePPO1.3369.11 / 84.4271.87 / 86.41
CodeC30.4258.65 / 71.2160.36 / 73.14
CodeVinePPO0.4257.67 / 72.0160.36 / 73.14

RollCredits achieves higher MAS pass@1 and pass@8 than both C3 and VinePPO at matched generation budgets in math and code. Our response to Reviewer mdEg (Q4) also reports generated and input tokens, approximate model calls and training tokens for every method.

Dear Reviewer NwT8,

Thanks for your time and effort in reviewing this paper. Your comments are valuable to improve the quality of this paper. As the author-reviewer discussion period ends in 48 hours, we kindly request that you review the rebuttal and confirm whether your concerns have been addressed. Thanks a lot.

Regards from the authors.

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

Training LLM-based multi-agent systems (MAS) requires assigning credit to agents for how their actions influence subsequent interactions and outcomes. The paper presents RollCredits, a method for decision-level credit assignment through counterfactual advantage estimation over execution graphs. At a shared history, candidate actions complete their induced downstream executions and are scored using the acting agent’s outcome reward, yielding a group-relative advantage estimator that is unbiased under stated sampling and replay conditions after a fixed group-size correction. To reduce collection cost, RollCredits branches candidates from decision states saved during seed executions and runs their continuations concurrently.

Critical strengths
  • Clear illustration. The paper clearly elaborates on three types of credit assignment methods for MAS, reflecting the advantages of RollCredits in decision history and reliable estimation of action value.
  • Competitive results. The evaluation covers mathematical reasoning, code generation, and games. Table 1 reports results under both single-agent and MAS inference, demonstrating the benefits of MAS inference. RollCredits achieves the best performance in 10 of the 12 evaluation settings, supporting its effectiveness.
Critical weaknesses
  • Insufficient comparison with related works. The experiments lack comparisons with closely related methods such as VinePPO and C3. Both are discussed in the paper and have publicly available code. Why were they not included as direct experimental baselines?
  • Unclear sources of performance gains. Table 1 shows improvements in single-agent performance in most settings. It is therefore unclear whether the gains under MAS inference stem from stronger individual model capabilities or improved coordination within the MAS. The paper would benefit from ablation experiments and interpretable analyses that disentangle these two sources of improvement.
Questions for authors
  • Why is credit assigned only to solver/coder actions, without directly training the verifier, planner, and tester? What motivates this design choice?
  • Why does MAS training yield greater improvements under single-agent inference than GRPO? I am confused by this result. Could the authors provide a well-supported analysis and explanation?
5 comments
AuthorsOpenReview ↗

Response to Reviewer j68p

We thank the reviewer for the positive assessment of our presentation and results.

R2.W1: VinePPO and C3 baselines

We now include VinePPO and C3 as direct baselines, each with three training seeds under the same model, data, update count, batch and evaluation protocol; the General Response reports the full comparison. RollCredits has the highest mean MAS pass@8 in math and code, and higher means than C3 and VinePPO on all eight math/code metrics. For VinePPO, decision nodes serve as steps, and in games the values at sampled decision points use each player's own reward. C3 is evaluated in math and code, because its shared-reward formulation does not cover the opposing player rewards of our games.

R2.W2: Individual capabilities and collaboration

Removing multi-agent training. Single-agent GRPO uses the same training data and recipe, with rewards on standalone answers. It reaches similar single-agent pass@1 to RollCredits. Under MAS inference, GRPO gains 0.37 points in math and 1.54 in code, whereas RollCredits gains 5.73 and 4.86 (three-seed means).

Gains are computed from unrounded means.

DomainMethodSingle pass@1MAS pass@1Gain from MAS inference
MathGRPO66.0366.39+0.37
MathRollCredits66.9972.73+5.73
CodeGRPO56.0557.59+1.54
CodeRollCredits55.6960.55+4.86

Swapping roles. Using the all-role RollCredits checkpoint, we evaluate all four combinations of trained and initial models in the solver/coder role and the partner roles (verifier in math; planner and tester in code).

Solver / coderPartnersMath MAS pass@1Math MAS pass@8Code MAS pass@1Code MAS pass@8
InitialInitial51.0667.8650.1262.30
TrainedInitial69.9383.8458.9871.13
InitialTrained52.4569.6250.8663.62
TrainedTrained71.8786.4160.3673.14

Holding the trained solver/coder fixed, trained partners add 1.94/2.57 MAS pass@1/pass@8 points in math and 1.38/2.01 in code. They also improve the initial solver/coder, by 1.39/1.76 points in math and 0.74/1.32 in code. RollCredits therefore gains from a stronger solver/coder and from stronger partners, which standalone pass@1 does not capture.

R2.Q1: Solver/coder-only training

The submission used solver/coder-only training as a task-specific configuration. We now credit all roles under the same recipe to separate credit estimation from role selection. All-role RollCredits reaches MAS pass@8 of 86.41 in math and 73.14 in code, compared with 85.55 and 73.01 for the submitted checkpoints. The revised main comparison reports three-seed results for all-role RollCredits (General Response). In games, both players’ decisions receive credit.

R2.Q2: Single-agent inference

Across three seeds, RollCredits has similar single-agent pass@1 to GRPO (66.99 vs. 66.03 in math; 55.69 vs. 56.05 in code) and higher single-agent pass@8 (82.32 vs. 78.92; 70.70 vs. 68.65). Its single-agent advantage over GRPO is therefore most apparent in pass@8. It also exceeds C3 and VinePPO on all four single-agent mean scores.

RollCredits compares alternative initial answers at the same history by their expected outcomes after verification and revision. This trains answer generation using feedback from complete multi-agent interactions, while single-agent GRPO scores standalone answers. The shared model learns from this downstream feedback during training and can generate answers without partner calls at inference.

Dear Reviewer j68p,

Thanks for your time and effort in reviewing this paper. Your comments are valuable to improve the quality of this paper. As the author-reviewer discussion period ends in 48 hours, we kindly request that you review the rebuttal and confirm whether your concerns have been addressed. Thanks a lot.

Regards from the authors.

AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer j68p,

With the discussion period closing in approximately 24 hours, we would appreciate your feedback on our response and the additional experiments addressing your concerns, including VinePPO and C3 as baselines with three training seeds and ablations separating individual capability from collaboration. Please let us know if any concerns remain so that we can address them before the discussion closes. Thank you for your time and consideration.

Regards from the authors.

Reviewer_mdEgOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

RollCredits trains LLM-based multi-agent systems by assigning credit to a decision through its downstream outcomes. At a saved decision state, it samples alternative actions, completes each action's continuation, and computes group-relative advantages using the acting agent's terminal reward. The method uses a shared policy across roles and saved-state reuse for rollout collection. Experiments cover solver-verifier math workflows, planner-coder-tester code workflows, and competitive games, all using Qwen3-4B. The paper reports task performance, credit bias/variance diagnostics, and prompt-recomputation measurements. Its reported math/code configurations directly train solver/coder actions while the other roles continue to participate in the workflow.

Critical strengths
  1. The method addresses a meaningful MAS training problem: an action's immediate correctness can differ from its contribution through later interactions. Completing candidate continuations provides a concrete way to evaluate these downstream consequences, and the paper supplements task scores with direct credit-estimation diagnostics.

  2. The evaluation covers math, code, and cooperative/competitive reward settings, including a held-out game. The saved-state collection implementation and cache measurements also address a practical obstacle to using complete continuations.

Critical weaknesses
  1. The shared-policy and selective-role training design is insufficiently justified and controlled. Although the paper studies MAS, every role uses the same Qwen3-4B parameters, while the reported math/code configurations directly train only solver/coder actions. The paper gives a consolidation rationale for sharing parameters, but does not report comparisons with independently trained role-specific policies. It also lacks controlled ablations comparing the selected roles with each role separately, alternative role combinations, or all-role training. Appendix B.2 states that roles and scheduling were selected after inspecting evaluations, but does not fully specify the search space, per-configuration results, or separation between selection and final testing. Consequently, the contribution of counterfactual credit estimation is not sufficiently separated from role selection and scheduling. These missing controls are central to my assessment.

  2. Training-data disclosure and resource accounting are insufficient for interpreting the performance gains. The exact selected training subsets, unique-task counts, and model-based filtering procedure are unclear; the supplied generic preparation explicitly does not reconstruct the paper's selected subsets. The paper measures cache reuse and prompt recomputation, but does not provide a complete end-to-end training-cost account or establish gains under matched total resources. The reported 24-25% prompt-recomputation reduction is not a measurement of total training savings, and continuation-only generation may be absent from the plotted accounting. Hardware/GPU-hours and all seed, continuation, rejected-group, and tool-execution costs are needed. Finally, all results use one model and one training seed per configuration, limiting robustness. Math/code gains are often modest, although some game gains are larger; the current controls do not establish how much improvement is attributable to the method at comparable cost.

Questions for authors
  1. Why use one shared policy rather than independently parameterized role-specific models? Please justify this choice and provide relevant shared-versus-independent-policy evidence if available. In rebuttal, please prioritize controlled selected-role versus all-role training, and report each-role/alternative-role ablations where available, with the workflow, estimator, scheduling, and resource budget held fixed. Do the uncredited planner/tester/verifier roles improve or degrade when the shared parameters are updated?

  2. How exactly were training roles and scheduling selected? Please enumerate the configurations tried, their results, the datasets and metrics inspected, and each baseline's selection budget. Were final test benchmarks used for configuration selection? Please clarify whether Breakthrough remained isolated throughout selection as well as absent from RL training. This is a request to resolve possible test-set adaptation, not an assertion of confirmed leakage.

  3. What are the exact training-set sizes by domain, including unique tasks, subset identifiers, repetitions, and the counts before/after model-based filtering? Please disclose the filtering model, criterion, and procedure, together with train/validation/test separation and overlap checks. Update counts and training-sequence counts alone do not specify the training set.

  4. Please disclose total training cost for each method/domain: GPU type and count, wall-clock duration, GPU-hours, all generated input/output tokens and model calls (including seed discovery, downstream continuations, and rejected groups), optimization cost, and sandbox/tool execution. How much does saved-state reuse reduce the complete cost, and do the performance advantages remain under equal total generation or compute budgets? Please also clarify the choice of K=8 and the branch-node selection/state cap.

  5. Which findings are supported beyond the single Qwen3-4B/shared-weight setting? Please discuss model-family dependence and the uncertainty not covered by single-training-seed results. For Breakthrough, what evidence separates improved strategic play from interface/legal-action handling against the fixed opponent?

  6. Please clarify the substantive method/theory increment over prior fixed-history counterfactual rollout methods, particularly C3 (Exact Is Easier, pre-submission May 2026 version). Which capability or result depends specifically on your execution-graph or replay formulation rather than the existing rollout-and-relative-baseline construction?

6 comments
AuthorsOpenReview ↗

Response to Reviewer mdEg (1/4)

We thank the reviewer for the precise questions. Each is answered below with new results; a summary appears in the General Response.

R1.W1 / R1.Q1: Shared policy and role selection

Shared policy by design. As stated in Section 2, our goal is to improve a single foundation model through learning across agent roles. We believe that training one model to learn from and perform multiple roles is a practical direction for MAS. Independently trained role-specific models require maintaining, updating and deploying a separate set of weights for each role. A shared policy brings these learning signals into one model that can serve different roles through their instructions and observations. Prior comparisons show that the preferred architecture depends on the task and model: Dr. MAS reports higher aggregate math scores with independent policies at 4B but shared policies at 8B [1], while AT-GRPO finds benefits from sharing across overlapping roles and specialization across distinct roles [2]. Our study focuses on decision-level credit assignment for a shared model learning through multi-agent interactions. We therefore fix parameter sharing across MAS methods and compare their credit rules; a comparison of shared and independent policy architectures is outside this scope.

Unified role protocol. To separate credit estimation from role selection, we train RollCredits with all roles credited in math and code using the same training recipe. We repeat every applicable method/domain configuration with three training seeds and report means and sample standard deviations in the revised main comparison. Each method trains every role its credit rule can score: RollCredits, C3, VinePPO, traj-GRPO and Dr. MAS train all roles; AT-GRPO trains roles with immediate rewards (solver, verifier and refiner in math; coder in code).

MethodRoles trainedMath MAS pass@8Code MAS pass@8
traj-GRPOall85.13 ± 0.4565.73 ± 0.26
Dr. MASall84.01 ± 0.6966.54 ± 0.75
AT-GRPOroles with immediate reward83.45 ± 1.9371.63 ± 0.33
C3all84.67 ± 0.1771.53 ± 0.77
VinePPOall84.83 ± 0.2572.34 ± 0.57
RollCreditsall87.09 ± 0.6872.95 ± 0.62

Math scores exclude the 23 test problems that overlap with the training data (R1.Q3). All-role RollCredits achieves the highest mean MAS pass@8 in both domains among the methods above. Games already credit both seats.

Each role and role combinations. We train RollCredits with each role credited alone, with two role combinations in code, and with all roles, keeping the training data, update count, batch size and group size fixed (single seed).

DomainCredited rolesSingle pass@1Single pass@8MAS pass@1MAS pass@8
Mathnone (initial model)50.3766.8351.0667.86
Mathsolver68.0781.2372.1585.55
Mathverifier59.5975.3664.2780.47
Mathall66.3781.8171.8786.41
Codenone (initial model)46.8356.2450.1262.30
Codeplanner51.3662.9354.9667.25
Codecoder56.0569.1960.1073.01
Codetester50.2761.4955.6468.75
Codeplanner + coder56.0069.8860.4072.76
Codecoder + tester55.8970.1360.4472.64
Codeall55.9870.8260.3673.14

Crediting any single role improves both inference modes over the initial model, and the solver or coder contributes most. Crediting all roles gives the highest MAS pass@8 in both domains.

To evaluate the uncredited roles, we fix the selected-role solver/coder and replace its partners. Base denotes the initial model; Selected denotes the same selected-role checkpoint used for the solver/coder.

DomainPartner configurationMAS pass@1MAS pass@8
Mathverifier = Base70.9284.03
Mathverifier = Selected72.1585.55
Codeplanner = Base, tester = Base58.6371.25
Codeplanner = Selected, tester = Base58.7971.40
Codeplanner = Base, tester = Selected59.8272.35
Codeplanner = Selected, tester = Selected60.1073.01

The updated partners improve MAS pass@1/pass@8 by 1.23/1.52 percentage points in math and 1.47/1.76 in code. Roles without direct credit thus improve through shared-parameter updates.

[1] Feng et al. Dr. MAS: Stable Reinforcement Learning for Multi-Agent LLM Systems. arXiv:2602.08847, 2026.

[2] Zhao et al. Stronger-MAS: Multi-Agent Reinforcement Learning for Collaborative LLMs. arXiv:2510.11062, 2025.

AuthorsOpenReview ↗

Response to Reviewer mdEg (2/4)

R1.W1 / R1.Q2: Configuration selection and test benchmarks

Shared recipe. Within each domain, all methods share the training data, update count, batch size, clipping, learning rate and absence of a KL penalty, adopted from DeepCoder [3] and DAPO [4] without per-method tuning. Each baseline applies its published credit rule, including the local reward for AT-GRPO, so the comparison isolates the credit rule. The three training seeds repeat this fixed recipe.

Configuration selection. The revised comparison removes the role choice this question concerns. Each method now trains every role its credit rule can score, so the credited roles follow from the method itself, and the all-role results in R1.W1 replace the earlier selected-role comparison. In code, RollCredits allocates candidate groups equally across the credited roles. In games, collection balances games and seats with at most two decision states per seed execution. We set the collection protocol using mean return on the three training games; Breakthrough is excluded from RL training and the selection metric.

[3] Luo et al. DeepCoder: A Fully Open-Source 14B Coder at O3-mini Level. Notion Blog, 2025.

[4] Yu et al. DAPO: An Open-Source LLM Reinforcement Learning System at Scale. NeurIPS, 2025. arXiv:2503.14476.

R1.W2 / R1.Q3: Training data

DomainSourceTasks before filteringRetained tasks
Mathaaabiao/dapo_filter, train split13,0447,089 unique tasks
CodeDeepCoder-Preview-Dataset: TACO + PrimeIntellect21,3855,206 (1,774 + 3,432)
GamesColonel Blotto, Connect Four and Liar’s Dice (TextArena)—768 starting states (256 per game)

For math and code, we sampled eight responses per task from the initial Qwen3-4B and retained tasks with both correct and incorrect responses, then removed duplicates. All methods in each domain use the same training set. We will release the retained task IDs and filtering script.

Within each domain, all methods receive the same number of updates and 512 training sequences per update, so they train on the same number of sequences. Data passes differ because methods draw different numbers of training sequences from each task and dynamic sampling replaces groups with identical rewards. Passes describe sample collection; the optimization schedule and sequence budget are fixed. The table reports passes from each run’s final data cursor:

MethodMathCodeGames
GRPO5.243.982.30
traj-GRPO1.570.501.42
Dr. MAS1.630.711.73
AT-GRPO3.346.6945.1
RollCredits (all roles)4.533.5131.7
C32.281.65n/a
VinePPO3.182.4239.9

Test overlap. Our checks found no duplicate code problems in HumanEval+, MBPP+ or LiveCodeBench. For math, we identified 7 overlaps in MATH500 and 16 in AMC23, with none in AIME24 or AIME25. All revised math comparisons, including the General Response, exclude these 23 test problems. We split the data into training and test sets only, with no validation split; every method reports its final checkpoint.

AuthorsOpenReview ↗

Response to Reviewer mdEg (3/4)

R1.W2 / R1.Q4: Training cost, matched budgets and sampling settings

Generation budget. Our runs used different GPU allocations on NVIDIA H100 cluster, so wall-clock time and GPU-hours are not comparable across methods. We report hardware-independent rollout costs: total generated and input tokens and approximate model calls from the inference-engine logs. These totals include seed executions, candidates, continuations and discarded groups. Sandbox execution time was not recorded separately.

DomainMethodGenerated tokens (B)Input tokens (B)Model calls (M, approx.)Training tokens (M)
MathGRPO1.070.100.35503
Mathtraj-GRPO0.580.710.30673
MathDr. MAS0.460.580.29567
MathAT-GRPO0.830.830.46528
MathC30.891.470.60639
MathVinePPO1.633.020.83617
MathRollCredits (all roles)1.331.760.61673
CodeGRPO0.190.110.17135
Codetraj-GRPO0.030.130.09160
CodeDr. MAS0.050.220.15179
CodeAT-GRPO0.502.141.03230
CodeC30.501.830.88214
CodeVinePPO0.642.971.03207
CodeRollCredits (all roles)0.422.141.08232
GamesGRPO0.040.160.2688
Gamestraj-GRPO0.040.120.21104
GamesDr. MAS0.100.120.38148
GamesAT-GRPO1.124.102.95127
GamesVinePPO3.2316.2110.28118
GamesRollCredits0.891.502.11108

Optimization cost. All methods use the same optimization schedule and sequence budget: 220 updates for math/games and 162 for code, with 512 training sequences per update (64 groups × 8). The final column reports the prompt and response tokens processed during optimization.

Equal generation budget. RollCredits, C3 and VinePPO all estimate credit from sampled continuations, so generation is the cost each pays for its credit signal, and a matched generation budget compares how efficiently each estimator uses it. We compare the three with the same software stack and recipe. For each pair, the budget is the smaller of the two methods' total generation, and the method that generated more is evaluated at its checkpoint reaching that budget.

DomainBaselineGeneration budget (B)Baseline MAS pass@1 / pass@8RollCredits MAS pass@1 / pass@8
MathC30.8970.54 / 84.6070.62 / 85.29
MathVinePPO1.3369.11 / 84.4271.87 / 86.41
CodeC30.4258.65 / 71.2160.36 / 73.14
CodeVinePPO0.4257.67 / 72.0160.36 / 73.14

RollCredits achieves higher MAS pass@1 and pass@8 than both C3 and VinePPO at matched generation budgets in math and code.

Saved-state reuse and replay. RollCredits branches candidates directly from decision states saved during seed executions, rather than replaying each execution from the start to reach them; at fixed decision states, this reduces prompt recomputation by 24–25% with prefix caching enabled in both settings (Section 4.5). When a candidate changes one solver's answer in the parallel workflow, dependency-preserving replay keeps the other solvers' outputs and regenerates only the aggregator, whereas serialized-trace replay also regenerates the later solvers. This reduces total generated tokens per group, including seed cost, from 56.5k to 30.4k at solver 1 and from 43.5k to 30.0k at solver 2, savings of 46.2% and 31.0%. The two rules generate the same 30.8k tokens at solver 3, which has no later solvers, and both achieve 86.53% MAS pass@8 on the overlap-filtered test set.

K and state selection. K=8 matches the group size of the GRPO-family baselines, so every method trains on 64 groups × 8 = 512 sequences per update. In math, two seed executions per problem supply decision states, taken in discovery order until 64 groups with non-identical candidate values fill the update. In code, balanced scheduling allocates the 64 groups equally across the credited roles. In games, collection takes at most two decision states from each seed execution, so each batch covers more seed executions. Section 4.4 reports estimation error as a function of M at K=8.

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response — Part 1/2

We thank all reviewers for their thoughtful feedback and recognition of our execution-graph formulation of downstream credit assignment [Reviewers mdEg, NwT8], action-value estimation and direct diagnostics [Reviewers mdEg, j68p], and saved-state collection [Reviewer mdEg]. The reviewers also highlighted the strong results across math, code and games [Reviewer j68p], including generalization to held-out Breakthrough, which Reviewer NwT8 found “particularly interesting.”

In response to the reviewers' feedback, we further clarify our unique contributions and distinctions from prior work, and add C3 and VinePPO as direct experimental baselines. RollCredits introduces a unified framework for decision-level credit assignment over dynamic execution graphs in cooperative and competitive MAS, combining direct branching from saved decision states, agent-specific reward evaluation and dependency-preserving replay, with theoretical guarantees for credit estimation under stated sampling and replay conditions. The table below summarizes the specific distinctions from prior work.

VinePPO [1]C3 [2]RollCreditsBenefit and evidence
SamplingMC continuations from trajectory statesNested branching across role turnsDirect branching at selected decision statesAllocates candidate comparisons to selected decisions without expanding upstream alternatives.
Execution and replaySequence replay from a saved reasoning prefixSequence replay from a saved interaction historyExecution-graph replay preserving unaffected outputs and regenerating affected calls46.2%/31.0% fewer generated tokens at solver positions 1/2, similar credit MSE; both replay rules reach 86.53% MAS pass@8.
Saved stateReasoning prefixComplete text historyHistory, environment state and unaffected outputs, reused under Proposition 2Preserves the raw estimator's conditional mean under the stated conditions. Collector: 24%/25% less prompt recomputation in math/games versus ancestor replay, both with prefix caching (§4.5).
Reward targetTask rewardShared team rewardActing agent's rewardSupports cooperation and competition. Across three seeds, leads in 3/4 games; held-out Breakthrough 85.16 ± 0.52% vs. 70.18 ± 0.60% for Dr. MAS.

New experiments.

  • Stability and generalization. We train two additional seeds for every applicable method/domain configuration, giving three seeds per configuration (main comparison below). We also train on Llama-3.2-3B-Instruct in math to test whether the results hold on another model family. RollCredits achieves the highest overlap-filtered MAS pass@8 on this model, 46.65%. In the Breakthrough behavior analysis, it wins 84.88% after excluding illegal-action terminations and 83.20% against a random legal opponent.
  • Parallel fan-out/fan-in workflow. As Reviewer NwT8 suggested, three solvers answer independently and an aggregator combines their outputs. Dependency-preserving replay reuses unaffected sibling outputs, yielding the generation savings in the table above. Both replay rules achieve the highest MAS pass@8, 86.53%.
  • Role ablation. As Reviewer mdEg requested, every method now trains all roles its credit rule can score. Among the tested role configurations, crediting all roles gives the highest MAS pass@8, 86.41 in math and 73.14 in code. With the trained solver/coder fixed, the trained partners add 1.94/2.57 MAS pass@1/pass@8 points in math and 1.38/2.01 in code, so both the solver/coder and its partners contribute to the gains.
  • Generation and training costs. We additionally report generated and input tokens, approximate model calls and optimizer training tokens. At matched generation budgets, RollCredits achieves higher MAS pass@1 and pass@8 than both C3 and VinePPO in math and code. In a controlled measurement, saved-state reuse reduces prompt recomputation by 24–25%.

[1] Kazemnejad et al. VinePPO: Refining Credit Assignment in RL Training of LLMs. ICML 2025.

[2] Chen et al. Exact Is Easier: Credit Assignment for Cooperative LLM Agents. arXiv:2603.06859v2, 2026.

AuthorsOpenReview ↗

General Response — Part 2/2

Main comparison. Every applicable method/domain configuration is repeated with three training seeds; the tables report means and sample standard deviations. Math uses the overlap-filtered test set; RollCredits trains all roles in math and code; C3's game entries are n/a because its formulation uses a shared team reward.

DomainMethodSingle pass@1Single pass@8MAS pass@1MAS pass@8
MathGRPO66.03 ± 1.0778.92 ± 0.7766.39 ± 1.0877.60 ± 1.18
Mathtraj-GRPO60.52 ± 0.4372.37 ± 0.3472.31 ± 0.2385.13 ± 0.45
MathDr. MAS65.46 ± 1.1878.69 ± 0.9073.57 ± 1.0884.01 ± 0.69
MathAT-GRPO66.56 ± 1.2980.99 ± 1.2568.61 ± 0.9883.45 ± 1.93
MathC365.82 ± 0.8979.33 ± 0.4970.05 ± 0.6484.67 ± 0.17
MathVinePPO65.99 ± 0.1779.35 ± 0.2769.36 ± 0.1684.83 ± 0.25
MathRollCredits66.99 ± 0.5582.32 ± 0.5072.73 ± 0.9387.09 ± 0.68
CodeGRPO56.05 ± 0.3968.65 ± 0.1357.59 ± 0.1870.76 ± 0.17
Codetraj-GRPO49.01 ± 0.0261.20 ± 0.7553.42 ± 0.2465.73 ± 0.26
CodeDr. MAS49.48 ± 0.9362.62 ± 0.8653.60 ± 0.6066.54 ± 0.75
CodeAT-GRPO55.31 ± 0.4468.71 ± 0.4859.62 ± 0.7771.63 ± 0.33
CodeC351.74 ± 0.6865.12 ± 0.5458.75 ± 0.5971.53 ± 0.77
CodeVinePPO53.34 ± 0.7367.10 ± 0.6058.78 ± 0.6272.34 ± 0.57
CodeRollCredits55.69 ± 0.3270.70 ± 0.8260.55 ± 0.3672.95 ± 0.62
MethodBlottoConnect FourLiar’s DiceBreakthroughID mean
GRPO17.38 ± 1.8857.49 ± 1.3054.95 ± 0.8825.39 ± 0.7043.27 ± 1.05
traj-GRPO25.91 ± 0.8853.06 ± 0.5623.24 ± 0.3458.07 ± 0.4534.07 ± 0.25
Dr. MAS94.08 ± 0.3063.74 ± 1.0860.87 ± 1.1970.18 ± 0.6072.89 ± 0.54
AT-GRPO67.45 ± 1.0866.15 ± 0.5660.16 ± 1.1955.08 ± 0.9064.58 ± 0.85
VinePPO75.33 ± 0.1165.17 ± 0.6062.11 ± 0.5255.86 ± 0.9067.53 ± 0.20
RollCredits98.96 ± 0.1159.44 ± 1.5875.59 ± 1.8685.16 ± 0.5277.99 ± 0.39

RollCredits achieves the highest mean single-agent pass@1/pass@8 and MAS pass@8 on math, and the highest mean single-agent pass@8 and MAS pass@1/pass@8 on code. Compared with C3 and VinePPO, it has higher mean scores on all eight math/code metrics. It also leads in three of four games, with an ID mean of 77.99 ± 0.39% and a held-out Breakthrough win rate of 85.16 ± 0.52%.

Revisions. We have uploaded a revised PDF, with changes highlighted in blue.

  • Table 1 and Section 4.2 report three-seed means and standard deviations with all-role RollCredits, C3 and VinePPO, and summarize the ablations, matched-budget comparisons and Llama-3.2-3B-Instruct results.
  • New Section 4.3 presents the parallel fan-out/fan-in workflow and the replay comparison, with diagnostic details in Appendix D.1.
  • Section 2 clarifies how execution dependencies determine decision histories, and Section 5 adds the comparison with C3 and VinePPO.
  • The appendix is regrouped into experimental setup (B), additional results (C) and diagnostics (D); the former Appendices C and D are now E and F.
  • Appendix B.2 adds training-data statistics and overlap checks, and Appendix B.3 states the shared training recipe, the role protocol and the baseline adaptations.
  • Appendix C reports three-seed benchmark-level results (C.1), the Breakthrough behavior analysis (C.3), role ablations (C.4), generation accounting with matched budgets (C.5) and Llama-3.2-3B-Instruct results (C.6).

Dear Reviewers,

Thanks for your time and effort in reviewing this paper. Your comments are valuable to improve the quality of this paper. As the author-reviewer discussion period will end in about 3 days, we gently request that you read the rebuttal and check whether your concerns are addressed. Thanks again for your time and help in improving the quality of this paper.

Regards from the authors.

AuthorsOpenReview ↗

Final summary

We thank the Area Chair and reviewers for the discussion. The reviews recognized the motivation for evaluating an action through later interactions [mdEg], the execution-graph formulation [NwT8], and the empirical results across math, code and games [j68p, NwT8]. Direct credit-estimation diagnostics and saved-state measurements [mdEg] provide evidence about how the method works, alongside its task performance.

Reviewer concerns and our responses

  • Execution-graph replay reduces collection cost without biasing credit. In response to mdEg and NwT8, we clarified the estimator differences from C3 and VinePPO and revised the contribution statement to specify the acting-agent reward target and the replay guarantee. NwT8’s requested parallel workflow shows what the dependencies permit: replay keeps independent workers’ outputs while regenerating the affected aggregation. This reduces generated tokens per group by 46.2% and 31.0% at the first two solver positions, with similar credit MSE. The theory states conditions under which this reuse preserves the corrected estimator’s expected value.
  • The gains involve both answer-producing roles and their partners. To address mdEg’s role-selection concern, we replaced the selected-role main comparison with all-role RollCredits and added individual-role and role-combination ablations. To answer j68p’s question about stronger individual models versus collaboration, we held the trained solver/coder fixed and swapped its partners. Trained partners improve MAS pass@8 by 2.57 points in math and 2.01 in code. RollCredits also matches GRPO on single-agent pass@1 and exceeds it on pass@8, because it trains answers on feedback from complete verification and revision.
  • The comparison now includes the closest baselines and broader controls. Following the reviewers’ requests, we added C3 and VinePPO, three seeds for every applicable main comparison, a second model family, generation accounting and matched-generation comparisons. RollCredits keeps the highest mean MAS pass@8 in math and code and exceeds both rollout baselines at matched generation budgets. The Breakthrough advantage also holds after excluding illegal-action terminations and against a random legal opponent, addressing mdEg’s concern about interface handling.
  • Training data are documented, and the math overlap leaves the conclusions unchanged. We reported each domain's source, filtering procedure and counts. With the math setup of Dr. MAS, our audit found 7 MATH500 and 16 AMC23 problems in the training corpus and none in AIME, code or games. Rescoring the submitted checkpoints without them leaves the leading method unchanged on all four math metrics (details in our reply to mdEg), and all revised results exclude them.

Revisions to the paper. The revised PDF marks all changes in blue. Table 1 and Section 4.2 now report three-seed means and standard deviations with all-role RollCredits, C3 and VinePPO, and the new Section 4.3 presents the parallel workflow. The introduction states the revised contribution, and Sections 2 and 5 clarify execution-graph histories and the relation to C3 and VinePPO. The appendix adds the training data and overlap audit (B.2), benchmark-level three-seed results, role ablations, cost accounting, Llama-3.2-3B-Instruct and Breakthrough analyses (C), and the replay diagnostic (D.1).

Our findings on credit assignment over execution graphs

  1. Immediate correctness is a biased credit signal. An action that looks wrong in isolation can still lead a partner to a better final answer, so credit should be measured through the outcomes an action leads to.
  2. The execution graph sets where candidates are compared and what replay can reuse. Candidates are compared at the history the graph gives the acting call, and replay regenerates only the calls a candidate affects. Reusing the remaining outputs keeps the credit unbiased while cutting collection cost.
  3. Counterfactual credit extends to competitive settings. Scoring each decision with the acting agent's own reward makes the same estimator valid for cooperative and opposing objectives.
  4. A shared model transfers learning across roles. Credit given to one role also improves the others, and multi-agent training builds collaboration that single-agent training does not.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.