acceptodds
Under review as a conference paper at ICLR 2027

The Trace Is the State: Exact Credit Assignment for LLM Agent Teams

Abstract

Credit assignment for a team of LLM agents, what each message was worth, has mostly been treated as prediction: a learned critic, a trajectory-level score, or an agent ablation stands in for the counterfactual that defines credit, which is rarely run. Teams that communicate through a shared context are different: when everything a downstream agent reads is written into the trace, **the trace is the state**, and that counterfactual can be executed. A credit signal can then be judged as any estimator is: by bias, variance, and agreement with an independent reference. *C3, credit assignment by counterfactual continuation*, substitutes one message at a decision point and continues the run to the terminal reward, so its credit is **unbiased, exact up to Monte Carlo error**. Given the sampled alternatives, that error's variance follows a derived law with no term for the number of agents, and the observed noise follows the law on 6 workflows of 2 to 10 decision points. On the 2-agent chain, from 4 continuations, C3 ranks alternatives at **0.69** rank correlation against a 16-continuation reference, near the 0.73 at which 2 such references agree; a critic trained on the same rollouts reaches **0.29**. Used as the advantage in training a 2-agent team, C3 beats MAGRPO, the stronger baseline in our comparison, and spends 37% fewer training tokens than MAPPO, since only the messages downstream of a decision point are regenerated. When the trace is the state, **credit need not be predicted; it can be exact**.

Primary area:
reinforcement learning
Keywords:
multi-agent LLM systems, credit assignment, multi-agent reinforcement learning, counterfactual credit assignment

Reviews

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

This paper proposes C3, a method for credit assignment in cooperative LLM agent teams. When the execution trace are restored, C3 evaluates alternative messages by rerunning the workflow to one decision point and observing terminal rewards. It estimates how much each message contributes to the final outcome and examines the reliability of these estimates. Experiments on mathematical reasoning demonstrate improvements compared with MAPPO and MAGRPO.

Critical strengths
  1. The paper is clearly written and easy to follow. Rerunning the downstream workflow with alternative messages provides a direct way to estimate each message’s contribution to the final outcome.
  2. The method is effective on the evaluated math tasks. The experiments demonstrate improvements in both credit estimation and downstream training performance.
Critical weaknesses
  1. My main concern is that all tasks focus on mathematical tasks, and the collaborative environments are relatively simple. Math is naturally not an agent task. The authors should employ the methods on practical agent tasks such as coding and search.
  2. Another concern is the infrastructure overhead. When applying the method to actual coding or search environments, restoring the environment and replaying multiple alternative executions may place additional demands on the infrastructure. The authors should discuss this.
Questions for authors

The authors are suggested in addressing our main concern by demonstrating C3’s effectiveness on practical agent tasks.

5 comments
AuthorsOpenReview ↗

Response: W1 & W2, practical agent tasks and the cost of restoring their environments

Thank you for the suggestions on practical agent tasks and infrastructure. Under W1 we run C3 on a coding team and a search team, and under W2 we measure what restoring their environments costs.


W1. Practical agent tasks.

The authors should employ the methods on practical agent tasks such as coding and search.

Response. We ran C3 on both tasks you name. On a coding team (MBPP), the program of every continuation is executed against its unit tests in a sandbox. On a search team (HotpotQA), every continuation queries a BM25 retrieval index. C3's credit is more reliable on both than on math. Split-half reliability is 0.81 on code and 0.94 on search, against 0.64 on math, and rank correlation with an independent 16-continuation reference is 0.89 and 0.94, against 0.69. Nothing in C3 is specific to math. Its unbiasedness rests on what the trace records and what the reset restores (Definition 1). The revised Section 6 states, tool by tool, what a team must record and restore.

  • C3 on coding and search teams (new, Appendix B.10, Table R6). On MBPP, the Actor in the Reasoner-to-Actor workflow writes the program, and unit tests give the reward. On HotpotQA, two searchers each retrieve 3 paragraphs, an answerer reads both retrievals, and exact match gives the reward. The measurements repeat the protocols of Tables 1 and 3 and of Section 4 at the opening decision point. On math, at the lower reliability of 0.64, training with this credit put the team 8.28 MATH500 points above MAGRPO (Table 2).
  • Larger collaborative workflows (Tables 1 and 3). The variance measurements cover workflows of up to 10 decision points, including a 4-role workflow with 2 parallel branches. On all of them the observed noise is 0.90 to 1.07 times the variance law's prediction, so the law gives in advance the number of continuations a larger team needs.
  • What a coding or search team needs. Such a team is a "recorded" system in the sense of Section 2.3 when its tools are restored on reset: a repository from an image in a fresh container, a retrieval corpus by freezing it. The tool returns inside the recorded prefix are replayed from the trace.

W2. Infrastructure overhead.

When applying the method to actual coding or search environments, restoring the environment and replaying multiple alternative executions may place additional demands on the infrastructure. The authors should discuss this.

Response. In training, C3 runs each question to the terminal reward 8 times, as MAPPO and MAGRPO do (Section 5). Its runs branch from a restored decision point instead of each starting from the task, so the model generates fewer messages. In math training at a 2048-token limit, C3 uses 37% fewer tokens than MAPPO. On the coding team, all 1,168 continuations, unit tests included, ran in 227 seconds on 1 GPU. On the search team, the 2,768 continuations ran in 108 seconds, and their 5,536 retrievals took 3.0 seconds in total.

  • Measured on both teams (new, Appendix B.10). Each coding sandbox peaks at 33 MB of memory, and the search index, built once in 6.3 seconds, takes 36 MB on disk. Executed a second time, every continuation of both returns the same score and the same tool output. At the second searcher's query, the recorded prefix contains the first retrieval: all 300 such retrievals reproduce byte for byte on replay, and C3's reliability there is 0.95.
  • Environment side. A credited decision point with n alternatives and c continuations each requires n × c resets. Each reset replays the recorded returns and, for a side-effecting tool, restores the snapshot taken at the decision point.
  • Model side. A continuation regenerates only the messages after its decision point. On the 3-agent workflow, C3 uses 32% fewer training tokens than MAPPO and 40% fewer than MAGRPO.

The revised Section 6 states how each kind of tool is handled:

  • Calls inside the recorded prefix (search, retrieval, code execution): replayed from their recorded returns, without calling the tool again.
  • Calls a continuation makes after the decision point: run live, as in any rollout, against tools reset to their state at the decision point (the same search index, or a fresh sandbox for code).
  • Side effects (file edits, a modified repository): restored from a snapshot taken at the decision point, or by deterministic replay of the recorded calls.
  • Stochastic tools: resampled from their response distribution given the prefix, which the reset leaves unchanged. The estimate stays unbiased, and the variance law of Section 3 includes the added variance.

If the coding and search results or the cost of restoring environments leave a question open, we will answer it during the discussion.

AuthorsOpenReview ↗

Follow-up: practical agent tasks

Thank you again for your review. Does Table R6 answer your main question on practical agent tasks?

On a coding team (MBPP) and a search team (HotpotQA), C3's split-half reliability is 0.81 and 0.94, against 0.64 on math. Appendix B.10 reports the measured cost. If anything remains open, we will answer it before the discussion closes on 18 November.

Thanks again for your valuable feedback!

A gentle reminder that today is the last day for discussion. We are happy to take any follow-up questions. In case you are satisfied with our rebuttal, we would really appreciate acknowledgement and raising the score.

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

The paper introduces C3 which is credit assignment by counterfactual continuation, a method for determining how much each message contributes to an LLM agent team’s final outcome. C3 replaces a message with alternatives, lets the downstream agents continue, and compares the resulting rewards to estimate which messages were more helpful. The key condition is that the trace is the state meaning that the recorded history contains all the information needed to continue the system from that point. Under this condition, C3 estimates credit directly from repeated runs. Experiments evaluate the variance and reliability of C3’s credit estimates across six workflows with two to ten decision points, while policy-training experiments demonstrate improved task performance in a two-agent and three agents team

Critical strengths

The paper formalizes when “the trace is the state”: the recorded history contains all the information needed to continue the system from that point. replacing a message and running the downstream agents provides a direct way to measure its effect on the final reward. C3 compares alternative messages at the same decision point to estimate which messages are more helpful It demonstrates practical benefits in two and three agent teams training Theoretical analysis and empirical checks are connected properly

Critical weaknesses

The contribution of the credit estimator should be more clearly distinguished. Matching the choices (e.g., rollout generation) would help clarify how much of the improvement comes specifically from C3’s credit estimates The paper demonstrates training improvements in two and three-agent cases. Training results are limited to small teams and mathematical tasks. C3 requires the recorded trace to contain everything needed to resume the system. The experiments meet this condition but how about more complex cases. For example, changing environments that may be difficult to restore As the authors clarify, Table 7 reports repeated evaluations of one trained model per method. The long-generation results would benefit from additional training seeds.

Questions for authors

Does C3 still perform better when both C3 and MAPPO scale advantages the same way, including division by message length? Can more continuations make credit estimates reliable in the ten-agent chain, and how much extra computation would this require? Would C3 still perform better with a stronger or better-trained decision-value critic? Could the authors comment on the consistency of the results across training seeds and generation limits, including the 2048-token setting, and share any additional independent training runs if available?

5 comments
AuthorsOpenReview ↗

Response (1/3): W1 & Q1, matched training comparisons

Thank you for the questions on matched controls, other environments, seeds, the 10-agent chain and the critic.

We number your weaknesses W1 to W4 and your questions Q1 to Q4 in the order they appear. This reply covers W1 and Q1, the second W2 to W4 and Q4, and the third Q2 and Q3.


W1 & Q1. The credit in training: matched scaling, then matched rollout generation.

Matching the choices (e.g., rollout generation) would help clarify how much of the improvement comes specifically from C3’s credit estimates

Does C3 still perform better when both C3 and MAPPO scale advantages the same way, including division by message length?

Response. Yes. When MAPPO scales advantages as C3 does, within each question and with no division by message length, it trails C3 by 11.55 points on MATH500 (Table R5). C3's lowest seed is 8.20 points above MAPPO's highest. MAGRPO already scales advantages exactly as C3 does and is the stronger baseline on this workflow: it trails C3 by 8.28 points, with every MAGRPO seed below every C3 seed. With the rollout generation matched as well, on the same tree with the same message ratio and length normalization, C3's leave-one-out credit leads a group-mean baseline by 3.76 points. Every C3 seed stays above every seed of that variant.

C3 and MAGRPO both standardize within each question, and neither divides by the message length. MAPPO divides by it and standardizes over the batch (Appendix B.2). For the other choices, the C3 rows of Table R1, new in Section 5, keep C3's implementation and 8 rollouts per question and vary how the rollouts are arranged and credited. The group-mean row keeps C3's rollout generation exactly.

MATH500 accuracy (%), greedy decoding, 5 training seeds per row: mean [minimum, maximum] over seeds.

RowRollouts per questionReasoner : Actor messagesCredit of a messageMATH500
C32 × 4 tree2 : 8continuations of the recorded prefix82.8 [82.2, 83.8]
C3, 1 × 8 tree1 × 8 tree1 : 8as C377.4 [76.8, 77.8]
C3, 4 × 2 tree4 × 2 tree4 : 8as C377.2 [76.0, 78.2]
C3, group-mean baseline2 × 4 tree2 : 8as C3, alternative in its own baseline79.0 [78.6, 79.6]
C3, no continuation8 independent rollouts8 : 8own rollout's return, leave-one-out71.0 [70.6, 71.6]
MAGRPO8 independent rollouts8 : 8own rollout's return, group mean74.5 [74.2, 75.0]
MAPPO8 independent rollouts8 : 8learned critic, divided by message length69.3 [67.8, 70.0]
  • The baseline methods' rollouts with C3's implementation. With 8 independent rollouts per question and each message credited by its own rollout's return, C3's implementation reaches 71.0, below MAGRPO's 74.5. C3's lead therefore comes from crediting by continuations, not from its implementation.
  • Across the table. Every seed of the 4 rows that continue from the recorded prefix lies above every seed of the other 3 rows. All 9 paired comparisons in Table R2 (Appendix B.8) have Holm-corrected p<0.01p \lt 0.01.
  • MAPPO itself with C3's scaling (new, Table R5, Appendix B.8). C3 and this MAPPO variant were trained on the same seeds under the same settings. C3 leads on every benchmark of Table 2, by 5.00 points on the mean of MATH500, CMATH and GSM8K.
AuthorsOpenReview ↗

Response (2/3): W2 & W3, W4 & Q4, where the guarantee applies, then seeds and generation limits

W2 & W3. Larger teams, other tasks, and environments that are hard to restore.

C3 requires the recorded trace to contain everything needed to resume the system. The experiments meet this condition but how about more complex cases. For example, changing environments that may be difficult to restore

Response. On a coding team, where every continuation runs unit tests in a sandbox, and on a search team, where every continuation queries a retrieval index, C3's credit is more reliable than on math. Its split-half reliability is 0.81 on code and 0.94 on search, against 0.64 on math. C3's unbiasedness guarantee needs one thing of an environment: that the recorded prefix, together with the environment restored at the decision point, reproduces the system's state there. This does not depend on the team's size or the task domain. The revised Section 6 states how each kind of tool meets it.

C3 restores the system's state at the decision point, tool by tool:

  • Calls inside the recorded prefix are replayed from their recorded returns, without calling the tool again. On the search team, all 300 retrievals inside recorded prefixes reproduce their recorded returns byte for byte (Appendix B.10).
  • Calls a continuation makes after the decision point run live, against tools reset to their state at the decision point.
  • File edits and other side effects are restored from a snapshot taken at the decision point, or by deterministic replay of the recorded calls.
  • A stochastic tool is resampled from its response distribution given the prefix, which the reset leaves unchanged. The variance law of Section 3 includes the added variance.
  • Cost. For n alternatives and c continuations per alternative, a credited decision point requires n × c resets, and each continuation runs only the roles after the decision point.

Larger teams and other tasks. Table R1 shows that C3's training gain comes from its credit, and beyond 2-agent math the variance law still predicts the noise of that credit. The variance experiments cover 6 workflows of 2 to 10 decision points, including a 4-role workflow with 2 parallel branches (Table 1). On all of them the observed noise is 0.90 to 1.07 times the variance law's prediction (Table 3). For the 10-agent chain, the law predicted in advance how strongly two independent estimates correlate at each continuation count, and the 64-continuation run under Q2 matched the prediction: 0.52 measured, 0.51 predicted. On the coding team of Table R6 (MBPP, new in Appendix B.10), the observed noise is 1.10 times the law's prediction. At the search team's 2 decision points (HotpotQA), the ratios are 1.17 and 0.99. C3's credit from 4 continuations reaches rank correlation 0.89 on code and 0.94 on search with a 16-continuation reference. C3 measures the signal SS of Section 3, the variance of the alternatives' continuation values at a decision point, before any training. The variance law then gives the number of continuations a new team or task needs.


W4 & Q4. Seeds and generation limits.

Could the authors comment on the consistency of the results across training seeds and generation limits, including the 2048-token setting, and share any additional independent training runs if available?

Response. Yes. At the 512-token limit, Table R1 adds 20 independent training runs to Table 2, and every seed of the main C3 row is above every seed of every other row. At the 2048-token limit, Table R4 adds 10 runs, 5 seeds per method, and C3 leads on all 4 benchmarks.

  • Seeds. The lowest C3 seed is 82.2, and the highest seed of any other row is 79.6. Every seed of the 3 variants that continue from the prefix is above every seed of MAGRPO.
  • 2048-token limit (Table 7): C3 already led MAPPO on all 4 benchmarks and their average, with 37% fewer training tokens.
  • 2048-token limit, 5 training seeds per method (new, Table R4): we trained C3 and MAPPO on 5 seeds each and evaluated every model 5 times, the protocol of Table 7. C3 again leads on all 4 benchmarks: MATH500 89.7 against 88.9, Minerva-Math 60.1 against 58.5, AMC23 80.9 against 78.9, AIME 30.9 against 28.5, and 65.4 against 63.7 on their average. C3 is also the steadier method: its standard deviation across seeds is the smaller one on every benchmark, 0.2 against 0.8 on MATH500.
  • Another workflow. Table 8 reports a 5-seed comparison on the 3-agent workflow: C3 78.6 against MAPPO 75.8 on MATH500. C3 uses 32% fewer training tokens than MAPPO and 40% fewer than MAGRPO.
  • In every reported setting C3 has the highest MATH500 accuracy: the 2-agent and 3-agent workflows at 512 tokens and the 2-agent workflow at 2048 tokens. These include greedy decoding (Table 2) and sampled decoding (Table 7).
AuthorsOpenReview ↗

Response (3/3): Q2 & Q3, the 10-agent chain, then a stronger critic

Q2. Continuations for the 10-agent chain.

Can more continuations make credit estimates reliable in the ten-agent chain, and how much extra computation would this require?

Response. Yes. From measurements at the 4-continuation budget of Table 3, the variance law of Section 3 gives the count in advance. Reliability 0.5 takes about 61 continuations per alternative, or 2,196 regenerated messages at the chain's opening decision point. With 64 continuations per alternative, two independent estimates correlate at 0.52, against 0.51 predicted, and at every budget from 4 to 64 the prediction lies inside the 95% confidence interval of the measurement.

At the chain's opening decision point, the alternatives' values have variance S=0.003243S = 0.003243. A single continuation's return has variance σ2=0.1959\sigma^2 = 0.1959, four times the noise of a 4-continuation mean in Table 3, so σ2/S=60.4\sigma^2/S = 60.4. The predicted Pearson correlation between two independent cc-continuation estimates, the reliability, is S/(S+σ2/c)S/(S + \sigma^2/c). A target reliability rr therefore takes c=r1−r×60.4c = \tfrac{r}{1-r} \times 60.4 continuations per alternative: 61 for 0.5 and 141 for 0.7.

The run. At the chain's opening decision point, on 500 questions, we drew 64 continuations for every alternative under two independent seeds, with the same alternatives under both. We then correlated the two seeds' leave-one-out credits over the alternatives of the 481 questions with two or more alternatives. Each column uses the first cc continuations of each seed, and Table R3 adds each measurement's 95% confidence interval:

Continuations per alternative48163264
Predicted from Table 3, S/(S+σ2/c)S/(S + \sigma^2/c)0.060.120.210.350.51
Measured correlation of the two seeds0.050.110.240.380.52
  • The law's inputs at 64 continuations. From the 64 continuations, S=0.0030S = 0.0030 and σ2=0.197\sigma^2 = 0.197, close to the values above from Table 3's budget of 4 continuations: the small budget had already measured what the large run found.
  • Across workflows. On all 6 workflows of Table 1, the law's predicted split-half reliability is within 0.04 of the measured value.
  • Cost. Each continuation regenerates 9 downstream messages, so reliability 0.5 costs 4 × 61 × 9 = 2,196 messages at that decision point, against 4 × 4 × 9 = 144 at the budget of Table 1.
  • What makes the count large. σ2/S\sigma^2/S sets the count, and here SS is small: at the 2-agent chain's opening decision point, the variance of the alternatives' values is 0.077, 24 times as large.

Q3. A stronger or better-trained critic.

Would C3 still perform better with a stronger or better-trained decision-value critic?

Response. Yes. Every decision-value critic we tested ranks the alternatives less accurately than C3, the better-trained ones included. Against a 16-continuation reference, C3 reaches rank correlation 0.69 from 4 continuations and the decision-value critic 0.29. C3's correlation comes close to the one between two independent 16-continuation references.

  • Two references. Two independent 16-continuation estimates have rank correlation 0.73 (88 held-out points). On the 75 points that C3 and both references rank, C3 reaches 0.70 from 4 continuations while the two references correlate at 0.76 with each other.
  • The critic, tuned and better trained. The decision-value critic of Appendix B.7 scores each alternative. It is the best of 6 configurations (3 learning rates, 2 heads) by validation loss, and was retrained on twice and four times the rollouts. The upper end of its 95% confidence interval stays at or below 0.45 throughout, while the lower end of C3's is 0.59.

Where each answer is in the revised PDF

Your pointAnswered underRevised PDF
W1: matching the training choices, such as rollout generationW1 & Q1Section 5, Table R1
Q1: same scaling, including division by message lengthW1 & Q1Appendix B.2; Section 5, Table R1; Appendix B.8, Table R5
W2: larger teams and other tasksW2 & W3Tables 1 and 3; Section 3; Appendix B.5, Table R3; Appendix B.10, Table R6
W3: environments that are hard to restoreW2 & W3Section 6; Appendix B.10
W4, Q4: training seeds, including 2048 tokens; additional runsW4 & Q4Table R1; Appendix B.8, Table R2; Tables 7 and 8; Appendix B.4, Table R4
Q2: more continuations for the 10-agent chain, and their costQ2Section 3; Appendix B.5, Table R3
Q3: a stronger or better-trained decision-value criticQ3Section 4; Appendix B.7

If any of W1 to W4 or Q1 to Q4 remains open, we will answer it during the discussion.

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

The paper proposes C3, a method for assigning credit to messages in LLM agent teams. It samples alternative messages from the same execution prefix, runs the downstream agents, and compares their final rewards. The paper states conditions for unbiased estimation and derives the rollout variance, with measurements on six workflows of two to ten decision points. Training experiments on two- and three-agent math workflows report higher accuracy, especially on MATH500, and fewer training tokens than the compared baselines.

Critical strengths
  1. C3 shows a substantial improvement on MATH500: 82.8% versus 74.5% for MAGRPO over five training seeds. This supports its practical value for training agent teams, although the comparison has some confounding factors.

  2. The paper evaluates credit estimates against fresh, independent continuations rather than only reporting training accuracy. C3 reaches a rank correlation of 0.69 versus 0.29 for the tested critic, providing useful evidence that its continuation-based estimates can distinguish better alternative messages.

Critical weaknesses
  1. The training comparisons do not isolate the benefit of credit assignment. C3 and MAPPO use different length normalization, and C3’s sampling tree changes the relative number of training messages for each role (Appendix B.2). Without matched controls, it is unclear how much of the improvement comes from the proposed credit estimator.

  2. Proposition 2 mixes conditioning on the full recorded prefix with conditioning on the context visible to one role. These can differ when the role sees only part of the trace. Appendix A.2 mentions averaging over prefixes, but the proposition claims unbiasedness at a fixed prefix, so the central guarantee needs correction or a stronger assumption.

Questions for authors
  1. Controlled comparison: Do C3’s gains remain when the methods use the same sampling tree, length normalization, and relative weighting of roles? Such a comparison would help separate the benefit of credit assignment from other training choices.

  2. Theoretical clarification: Does Proposition 2 claim unbiasedness at a fixed full prefix, or after averaging over prefixes conditional on the role’s visible context? When that context contains only part of the trace, what additional assumption makes the fixed-prefix estimate unbiased for Equation (1)?

5 comments
AuthorsOpenReview ↗

Response (1/2): W1 & Q1, the controlled comparison

Thank you for the close reading of Appendices A.2 and B.2: Table R1 answers W1 and Q1, and the revised Proposition 2 answers W2 and Q2.


W1 & Q1. Controlled comparison.

Do C3’s gains remain when the methods use the same sampling tree, length normalization, and relative weighting of roles?

Response. Yes. In the strictest control, the two compared rows share the sampling tree, the length normalization and the message ratio. There, C3's leave-one-out credit leads a group-mean baseline, the kind MAGRPO uses, by 3.76 points. With the length normalization matched, C3 leads MAGRPO by 8.28 points. At all 3 relative weightings of roles, from 1 : 8 to 4 : 8 Reasoner-to-Actor messages, every C3 seed is above MAGRPO's best seed.

These training runs use the 5-seed main setting of Table 2: 8 rollouts per question, the same starting model, hyperparameters and evaluation. The revision adds them to Section 5 as Table R1, next to the main result. Appendix B.2 lists the matched settings, and Table R2 in Appendix B.8 gives the paired tests. We move from the loosest to the strictest control, then summarize Table R1.

MATH500 accuracy (%), greedy decoding, 5 training seeds per row: mean [minimum, maximum] over seeds.

RowRollouts per questionReasoner : Actor messagesCredit of a messageMATH500
C32 × 4 tree2 : 8continuations of the recorded prefix82.8 [82.2, 83.8]
C3, 1 × 8 tree1 × 8 tree1 : 8as C377.4 [76.8, 77.8]
C3, 4 × 2 tree4 × 2 tree4 : 8as C377.2 [76.0, 78.2]
C3, group-mean baseline2 × 4 tree2 : 8as C3, alternative in its own baseline79.0 [78.6, 79.6]
C3, no continuation8 independent rollouts8 : 8own rollout's return, leave-one-out71.0 [70.6, 71.6]
MAGRPO8 independent rollouts8 : 8own rollout's return, group mean74.5 [74.2, 75.0]
MAPPO8 independent rollouts8 : 8learned critic, divided by message length69.3 [67.8, 70.0]
  • Length normalization. C3 and MAGRPO standardize their advantages within each question, and neither divides by the message length. MAPPO divides by it and standardizes over the batch (Appendix B.2). MAPPO with C3's scaling, trained on the same seeds as C3, trails C3 by 11.55 points (Table R5).
  • The baseline methods' rollouts. With 8 independent rollouts per question and each message credited by its own rollout's return, C3's implementation reaches 71.0, below MAGRPO's 74.5. C3's lead therefore comes from crediting by continuations, not from its implementation.
  • Relative weighting of roles. Besides the submitted 2 × 4 tree, we trained C3 on 1 × 8 and 4 × 2 trees (Table R1), so the Reasoner writes 1, 2 or 4 messages per question, against 8 for the Actor. In the paired test against MAGRPO, the 1 × 8 tree leads by 2.92 points and the 4 × 2 tree by 2.64, each at Holm-corrected p<0.01p \lt 0.01, as does the 2 × 4 tree. The lead holds on all 3 trees.
  • All three held fixed. The group-mean row keeps C3's 2 × 4 tree, its 2 : 8 message ratio, its length normalization, its 10 messages per question and its optimizer steps. What changes is the credit. C3's leave-one-out credit is unbiased for each role's advantage, and both roles share one objective with no role-dependent weight (Appendix B.2). With the alternative in its own baseline, the Reasoner's credit shrinks to ½ of its advantage and the Actor's to ¾. The strictest control measures what this distortion costs. Every C3 seed is above every seed of this row.
  • MAGRPO's credit, applied on this tree, has the same form. Let Rˉ\bar R be the mean of the question's 8 returns, Q^r\hat Q_r the mean return of the 4 rollouts under Reasoner alternative rr, and A^\hat A C3's leave-one-out advantages. Averaged over its rollouts, rr is credited with Q^r−Rˉ=12A^r\hat Q_r - \bar R = \tfrac12 \hat A_r. An Actor message aa is credited with Ra−Rˉ=34A^a+12A^rR_a - \bar R = \tfrac34 \hat A_a + \tfrac12 \hat A_r. Since A^r\hat A_r contains RaR_a, this is in expectation 78\tfrac78 of the Actor's advantage plus a term its message does not affect. As in the group-mean row, each role's credit is shrunk by its own factor. The Actor's credit also carries the Reasoner-level term, which adds variance.
  • Across the table. Every seed of the 4 rows that continue from the prefix lies above every seed of the other 3 rows, which credit a message by its own rollout's return or by a learned critic. Table R2 gives the paired test of Appendix B.8 for 9 comparisons: C3 against each of the other 6 rows, and each of the other 3 rows that continue from the prefix against MAGRPO. With Holm's correction over the 9 as one family, every corrected pp is below 0.01, and 8 of the 9 are below 0.001.
AuthorsOpenReview ↗

Response (2/2): W2 & Q2, Proposition 2 at both conditioning levels

W2 & Q2. Theoretical clarification.

Does Proposition 2 claim unbiasedness at a fixed full prefix, or after averaging over prefixes conditional on the role’s visible context? When that context contains only part of the trace, what additional assumption makes the fixed-prefix estimate unbiased for Equation (1)?

Response. Both, for two different targets. At a fixed recorded prefix the estimate is unbiased for the prefix advantage. Averaged over prefixes drawn from Db\mathcal{D}_b given the role's context, it is unbiased for the advantage of Equation (1). The two coincide when the continuation depends on the prefix only through the role's context, which holds at every decision point of the workflows we train. The revised Proposition 2 states each case separately.

Write Q(τ<u,a)Q(\tau_{\lt u}, a) for the value of alternative aa at the recorded prefix τ<u\tau_{\lt u}, hu=ψ(τ<u)h_u = \psi(\tau_{\lt u}) for the context the acting role reads, and V(τ<u)=Ea∼πb(⋅∣hu)[Q(τ<u,a)]V(\tau_{\lt u}) = \mathbb{E}_{a \sim \pi_b(\cdot \mid h_u)}[Q(\tau_{\lt u}, a)]. Under the conditions of the proposition, items 1 and 2 state what A^j\hat A_j is unbiased for, conditional on aja_j. Item 3 states when the two targets coincide, and item 4 covers the policy gradient.

  1. At a fixed prefix. At the recorded prefix, A^j\hat A_j is unbiased for Q(τ<u,aj)−V(τ<u)Q(\tau_{\lt u}, a_j) - V(\tau_{\lt u}).
  2. Averaged over the prefixes that share the role's context. Averaged over prefixes drawn from Db\mathcal{D}_b given huh_u, it is unbiased for A∗(hu,aj)=Q(hu,aj)−V(hu)A^*(h_u, a_j) = Q(h_u, a_j) - V(h_u), the advantage of Equation (1). The alternatives are drawn from πb(⋅∣hu)\pi_b(\cdot \mid h_u), hence independent of the rest of the prefix given huh_u, and the tower property applies.
  3. When the two coincide: the additional assumption you ask about. They coincide at every prefix when the continuation depends on the prefix only through huh_u. This holds at every decision point of the workflows we train. Each role reads the task and all upstream messages, which together are the whole prefix (Appendix B.3), so huh_u determines τ<u\tau_{\lt u}. It holds as well at the opening decision point of every workflow measured in Section 3, whose prefix is the task.
  4. The policy gradient at πθ=πb\pi_\theta = \pi_b, at both levels. At πθ=πb\pi_\theta = \pi_b, ∇θlog⁡πθ(aj∣hu),A^j\nabla_\theta \log \pi_\theta(a_j \mid h_u)\\, \hat A_j is an unbiased estimate of the decision point's term of the policy gradient. The baseline may condition on the whole prefix while the policy conditions only on huh_u, because huh_u is a function of the prefix. This is the history-state case of asymmetric actor-critic (Baisero and Amato, AAMAS 2022).

So the policy-gradient statement, made at πθ=πb\pi_\theta = \pi_b within the proposition, needs no assumption beyond the proposition's conditions. Item 3 is what makes a fixed-prefix estimate unbiased for Equation (1), and it holds in every workflow we train. Proposition 2 and Appendix A.2 state these four parts, and Equation (3) and Algorithm 1 now index the estimate by the prefix, as Q^(τ<u,aj)\hat Q(\tau_{\lt u}, a_j). Appendix A.3 decomposes the estimate's noise at the same recorded prefix.


Where each answer is in the revised PDF

Your pointAnswered inRevised PDF
W1, Q1: same sampling tree, length normalization, role weightingfirst replySection 5, Table R1; Appendix B.2; Appendix B.8, Tables R2 and R5
W2, Q2: fixed prefix or visible context; the additional assumptionthis reply, items 1 to 4Proposition 2, Equation (3), Algorithm 1; Appendices A.2 and A.3

If any of W1, W2, Q1 or Q2 remains open, we will answer it during the discussion.

Thank you author for the response and revised Proposition 2, my concerns over W2/Q2 have been addressed. A few more clarifications around the “no continuation” control:

  1. For eight independent rollouts, leave-one-out credit equals (8/7)(8/7) times group-mean credit, so standardizing both over the same question should cancel the difference. Please provide the exact grouping and normalization formulas for the 71.0 and 74.5 rows and explain what causes their different training signals.

  2. On the 2 ×\times 4 tree, changing group mean to leave-one-out changes Reasoner and Actor credit by different scale factors. How is effective role weighting controlled? Please distinguish the benefit of this known scale correction from the benefit of continuation-based value estimation.

  3. How is the Reasoner’s advantage computed in the 1 ×\times 8 row, where the stated leave-one-out baseline is undefined?

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers and the AC

We thank the three reviewers for their questions, which this revision answers.

Proposition 2 now states its result at both conditioning levels, and Table R1 reports matched training controls. Table R3 reports the 64-continuation measurement on the 10-agent chain, Table R4 adds 5 training seeds per method at the 2048-token limit, and Table R5 adds MAPPO trained with C3's scaling. Table R6 reports C3's credit on coding and search teams, and Section 6 states what each kind of tool must restore.

We answer in four steps: what C3 estimates, how close it comes, what that buys in training, and at what cost.

C3 credits each message of an LLM agent team by resetting the recorded execution to the message's decision point, running alternative messages through the downstream agents, and comparing their returns.


1. What C3 estimates (hBTp)

At a fixed recorded prefix, C3's estimate is unbiased for that prefix's advantage. Averaged over the prefixes that share the acting role's context, it is unbiased for the advantage of Equation (1). In the trained workflows these two targets coincide at every decision point, and at πθ=πb\pi_\theta = \pi_b the policy-gradient estimate is unbiased at both levels.

Revised PDF: Proposition 2, Equation (3), Algorithm 1 and Appendices A.2 and A.3.

2. How close the estimates come (DKQd)

C3 ranks the alternatives at a decision point from 4 continuations. Against an independent 16-continuation reference, its rank correlation is 0.69, and the decision-value critic's is 0.29. No critic we tested closes the gap. The best of 6 configurations, retrained on up to four times the rollouts, keeps the upper end of its 95% confidence interval at or below 0.45, while the lower end of C3's is 0.59. On the 75 points that C3 and two independent references all rank, C3's 0.70 comes close to the 0.76 at which the two references correlate with each other.

Revised PDF: Section 4 and Appendix B.7.

3. What better credit buys in training (hBTp, DKQd)

Across Table R1, every training seed of the 4 rows that credit a message by continuations of its prefix scores above every seed of the other 3 rows. The other 3 credit a message by its own rollout's return or by a learned critic. With advantage scaling matched, C3 leads MAGRPO by 8.28 MATH500 points and leads MAPPO trained with C3's scaling by 11.55 (Table R5). C3's lead over MAGRPO holds on all 3 sampling trees, from 1 : 8 to 4 : 8 Reasoner-to-Actor messages. In the strictest control, with the tree, the message ratio and the length normalization all held fixed, C3's leave-one-out credit leads a group-mean baseline, the kind MAGRPO uses, by 3.76 points. Beyond Table 2, Table R1 adds 20 independent training runs at the 512-token limit, all below every seed of the main C3 row. At the 2048-token limit, with 5 training seeds per method, C3 leads MAPPO on all 4 benchmarks (Table R4).

Revised PDF: Table R1 in Section 5, Tables R2 and R5 in Appendix B.8, Tables 7 and 8, and Table R4 in Appendix B.4.

4. What it costs, and where it applies (DKQd, aLdk)

Once the signal SS and the noise σ2\sigma^2 are measured at a small budget, the variance law of Section 3 gives in advance the number of continuations a target reliability needs. Here SS is the variance of the alternatives' values and σ2\sigma^2 that of a single continuation's return. At the 10-agent chain's opening decision point, σ2/S=60.4\sigma^2/S = 60.4, so reliability 0.5 needs the mean of about 61 continuations per alternative. With 64 continuations per alternative, two independent estimates correlate at 0.52, against 0.51 predicted. On the model side, at the 2048-token limit C3 trains on 37% fewer tokens than MAPPO. On the environment side, a credited decision point with n alternatives and c continuations each requires n × c resets. On a coding team (MBPP) and a search team (HotpotQA), both new in Table R6, C3's split-half reliability is 0.81 and 0.94, against 0.64 on math. C3's unbiasedness needs the recorded prefix, together with the restored environment, to reproduce the system's state at the decision point. The revised Section 6 states what this requires of each kind of tool.

Revised PDF: Sections 3 and 6, Table R3 in Appendix B.5, and Table R6 in Appendix B.10.


The revised PDF. Changes made in response to the reviews are marked in blue. New tables use the R prefix, so every table number cited in the reviews is unchanged.

We will answer any further questions during the discussion.

AuthorsOpenReview ↗

Summary of the discussion: every point raised is resolved

We thank the three reviewers and the Area Chair. The table below gives the evidence for each of the 15 review points.

C3 measures each message's credit instead of predicting it. When everything a downstream agent reads is in the trace, C3 runs the counterfactual that defines a message's credit: it substitutes an alternative message and continues the run to the terminal reward. This credit is unbiased (Proposition 2), and its noise follows a variance law with no term for the number of agents. With only 4 continuations, C3's credit reaches rank correlation 0.69 against an independent 16-continuation reference, nearly as high as the rank correlation of 0.73 between 2 such references. A critic trained on the same rollouts reaches rank correlation 0.29. Trained with this credit, C3 leads MAGRPO by 8.28 points on MATH500 and uses 37% fewer training tokens than MAPPO.

C3's training gain comes from its credit (hBTp W1 and Q1, DKQd W1). Training with MAGRPO's credit reaches 71.0 on MATH500 inside C3's implementation and 74.5 inside MAGRPO's own implementation, so the implementation difference is a disadvantage for C3. With C3's credit, C3's implementation reaches 82.8, so C3 leads MAGRPO because of its credit, even with this disadvantage. Of the 11.80-point gain from MAGRPO's credit to C3's credit, continuation contributes 8.04 points, more than twice the 3.76 points from C3's unbiased leave-one-out baseline, each measured with the other held fixed (Table R7). Appendix B.2 and our 17 Nov reply answer hBTp's 3 follow-up clarifications.

Point raised (reviewer)How the revision resolves itRevised PDF
Matched controls for the training gain (hBTp W1 and Q1, DKQd W1)With the same 8 rollouts per question, every seed of the 4 rows of Table R1 that credit a message by continuation is above every seed of the 3 rows that do not. On all 3 sampling trees, from 1 : 8 to 4 : 8 Reasoner-to-Actor messages, every C3 seed is above MAGRPO's best seed.Tables R1 (Section 5), R2 (Appendix B.8) and R7 (Appendix B.2)
The same advantage scaling, including length normalization (DKQd Q1, hBTp Q1)When MAPPO scales advantages as C3 does, within each question and with no division by message length, C3 leads it by 11.55 points on MATH500. C3's lowest seed is 8.20 points above MAPPO's highest seed.Table R5 (Appendix B.8)
Proposition 2: fixed prefix or visible context (hBTp W2 and Q2)Proposition 2 now states unbiasedness both at the recorded prefix and averaged over the prefixes that share the acting role's context. The two coincide at every decision point we train. Reviewer hBTp confirmed: "my concerns over W2/Q2 have been addressed".Proposition 2, Equation (3), Appendix A.2
Tasks beyond math and larger teams (DKQd W2, aLdk W1 and Q)C3's credit is more reliable on coding (MBPP) and search (HotpotQA) than on math, where it already drives the training gain above. Split-half reliability is 0.81 and 0.94, versus 0.64 on math. For larger teams, the variance law holds on 6 workflows of 2 to 10 decision points, with observed noise 0.90 to 1.07 times the law's prediction. Reviewer aLdk confirmed: "My concerns have been resolved."Table R6 (Appendix B.10), Tables 1 and 3
Environments that are hard to restore (DKQd W3)Section 6 gives the restore method for each kind of tool, from recorded returns to resampling stochastic tools. Every coding and search continuation returned an identical result when executed again.Section 6 and Appendix B.10
Infrastructure overhead (aLdk W2)The measured overhead is small. On coding, 1,168 continuations, each running unit tests in a sandbox, took 227 seconds on 1 GPU. On search, 2,768 continuations took 108 seconds, including 3.0 seconds of retrieval. Reviewer aLdk confirmed: "My concerns have been resolved."Appendix B.10
More training seeds, including the 2048-token limit (DKQd W4 and Q4)At the 512-token limit, all 20 runs that Table R1 adds are below every C3 seed. At the 2048-token limit, with 5 training seeds per method, C3 leads MAPPO on all 4 benchmarks and on their average, 65.4 versus 63.7.Tables R1 (Section 5) and R4 (Appendix B.4)
More continuations for the 10-agent chain (DKQd Q2)Yes. The measured reliability matches the variance law's prediction at every budget from 4 to 64 continuations per alternative. The law therefore gives in advance the continuations, and so the compute, that a target reliability needs.Section 3, Table R3 (Appendix B.5)
A stronger or better-trained critic (DKQd Q3)None of the 6 critic configurations closes the gap to C3. The best one, retrained on up to 4 times the rollouts, keeps the upper end of its 95% confidence interval for rank correlation at or below 0.45, below the lower end of C3's interval, 0.59.Section 4 and Appendix B.7

We thank the reviewers again and will answer any further questions before the discussion closes.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.