acceptodds
Under review as a conference paper at ICLR 2027

GRAR: Graph-Rubric-guided Agentic Reward for Reinforcement Learning of LLM Agents

Abstract

Reinforcement learning for large language model (LLM) agents is naturally super-vised by the environment’s terminal signal: whether the task was completed. Under group-relative policy optimization (GRPO), terminal supervision is uninformative in two distinct regimes. In an all-failed group, every sampled trajectory receives the same reward, so the group produces no policy-gradient signal. In a mixed group containing both successful and failed trajectories, the terminal reward distinguishes their outcomes but does not identify which decisions contributed to success or failure. We introduce GRAR (Graph-Rubric-guided Agentic Reward), a post-hoc credit-assignment framework that preserves the terminal reward while providing process-level feedback in both regimes. For groups containing at least one success, graph settlement assigns step credit from verified outcomes represented in a group-local semantic state graph. For all-failed groups, rubric settlement scores a small set of graph-selected steps with a single guarded LLM-judge call. Trajectory advantages remain determined solely by terminal rewards, while process credit enters as a bounded step-aligned bonus; under the deployed configuration, this preserves the ordering between successful and failed trajectories. A single environment-agnostic adapter spans τ 2-bench, WebShop, and ALFWorld. Across the evaluated bench-mark settings, the best GRAR variant improves on the terminal-only baseline on both metrics.

Primary area:
reinforcement learning
Keywords:
Agentic RL, Credit Assignment, Graph & Rubric Settlement

Reviews

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

The paper starts from the observation that under group-relative policy optimization with a binary terminal reward, there are two regimes in which terminal supervision carries no usable information: an all-failed group, where every trajectory receives reward zero so all advantages are zero and the group contributes no gradient, and a mixed group, where the terminal signal establishes that the goal was reached but not which intermediate decisions were decisive. The paper reports that the silent regime is not an edge case, averaging between 0.44 and 0.51 of groups across the five trained WebShop runs, and Figure 6 shows the fraction declining but never approaching zero during training.

GRAR is a post-hoc credit-assignment pass that runs inside the GRPO trainer after all group rewards have been received. Environments are integrated through a three-field adapter that records a normalized action signature (action type, tool or command, and environment outcome class, including terminal signatures), a compact state payload with entity identifiers normalized away, and hindsight consisting of the terminal reward and episode flags. For each group, the trainer rebuilds a temporary group-local semantic state graph from all G trajectories and dispatches to one of two settlement procedures by a deterministic ownership rule: if at least one trajectory succeeded, graph settlement; if all failed, rubric settlement.

Graph settlement computes a per-node potential from the node's empirical success rate among visiting terminals multiplied by a normalized discounted remaining-horizon term, fuses this with a second component that averages the environment's own deterministic progress scalar over anchor-bearing visits, applies a detour penalty that is active only at sources with at least two successful outgoing edges and that measures relative verbosity among verified successful alternatives, and clamps steps whose signature indicates a tool error or a repeat to non-positive reward. Rubric settlement selects up to L candidates per trajectory by a priority order (errors first, then repeats, then branch points), pre-scores errors at minus one and repeats at minus half deterministically without calling the judge, sends the remaining candidates in a single batched call to a frozen instruction-tuned judge conditioned on the task objective and a domain rubric, snaps returned scores to a five-level set, zeros any score whose self-reported confidence falls below a gate, and applies a verified-progress lower bound for candidates with a positive anchor delta. The resulting step rewards enter the policy update as a bounded step-aligned bonus added to the unchanged terminal-reward advantage, with token-level alignment advanced by a cursor over the completion mask.

The contributions claimed are the unified framework covering both regimes, graph settlement for mixed groups, guarded rubric settlement for all-failed groups, and a reproducible protocol spanning tau-squared-bench, WebShop and ALFWorld under a shared trainer. Lemma 1 states that with step rewards bounded in magnitude below two and process weight w_s, every token of a successful trajectory receives a strictly larger fused advantage than every token of a failed trajectory whenever four times w_s times the group's terminal-reward standard deviation is less than one, which the default configuration satisfies. Experiments train Qwen3.5-9B with G equal to 8, compare three GRAR variants against a terminal-only GRPO baseline and a GiGPO baseline under the same trainer, and report pass@1 and pass@5 over five samples per task.

Critical strengths
  1. The paper is exceptionally disciplined about the central risk of dense process rewards, and it designs against it rather than around it. Reward hacking and terminal dilution are the standard failure modes when a learned or judged process score is mixed into a group-relative objective, and GRAR's construction addresses both in a way that is verifiable from logged traces: the terminal reward remains the sole source of trajectory advantage, process credit enters only as a bounded step-aligned bonus whose weight is chosen to satisfy an explicit ordering-preservation condition (Lemma 1, with the worst case at standard deviation of one half giving the condition that w_s be below one half), the deviation from potential-based shaping is stated openly with the detour penalty identified as a deliberate exception, the judge is restricted to all-failed groups so that it can never overturn a terminal verdict, and a confidence gate plus a five-level snapped score set bound any single judgment to half a point. Appendix I then audits every run against six structural criteria, including terminal invariance (terminal rewards bit-identical to the baseline pipeline), clamp effectiveness, and the requirement that no rubric credit appears in groups with a success. This is consequential for my assessment because in a literature where dense rewards are usually added and then monitored informally, here the non-interference claim is both provable in the deployed configuration and checkable after the fact. It is the most convincing part of the paper.

  2. Identifying and then directly targeting the all-failed group is a genuinely useful problem selection, and the reported recovery in that regime is large. Most step-level credit methods implicitly assume that at least one trajectory in the group contains positive signal to propagate, which is exactly the assumption that fails when a task lies outside the policy's reach. The paper shows this regime is common (44 to 51 percent of WebShop groups) and then reports that the rubric-only variant, which by construction only touches groups whose trajectory advantage is identically zero, raises WebShop pass@1 from 15.4 to 32.7 and pass@5 from 55.8 to 67.3, and that the combined variant reaches 69.2 pass@5. The ALFWorld breakdown in Table 9 is consistent with this reading: the combined variant is the best on two-object placement at 96.2 pass@5 and on clean at 60.7 pass@5, which are the task types with the longest horizons, and the paper attributes the largest gains to the guarded rubric channel. Since the mechanism is restricted to groups that would otherwise contribute no gradient at all, the improvement cannot be explained by reshuffling credit among successful trajectories, which makes this the cleanest evidence in the paper.

Critical weaknesses
  1. The empirical base cannot support the paper's claims at the reported granularity: every training configuration uses a single seed, the reported gains are within the paper's own stated variance, and the headline result comes from a baseline that is close to floor. Section 4 states that each training configuration uses a single seed, and Table 1 reports standard deviations that are enormous relative to the effects: terminal-only GRPO on WebShop is 15.4 plus or minus 11.6 on pass@1 and 55.8 plus or minus 19.3 on pass@5, GiGPO on ALFWorld is 42.2 plus or minus 11.9, and GRAR combined on ALFWorld is 49.5 plus or minus 19.2. The combined variant's average margins over the baseline are 6.5 points on pass@1 and 6.3 on pass@5 across five columns, which is inside one standard deviation of the baseline in several individual columns. Section 5.4 additionally reports the sensitivity study as the per-metric best over checkpoints 10 through 68 (approximately 100), so the hyperparameter result is a maximum over roughly 59 checkpoints per cell with no seed replication, and the main-table numbers appear to be selected the same way. There is no significance testing, no confidence interval, and no second seed anywhere in the paper. This matters because the paper's central claim is comparative: GRAR is reported to exceed GiGPO and terminal-only GRPO on both metrics in aggregate, and with this variance structure I cannot distinguish that from seed variation. The concern is amplified by the evaluation scope: all results use one model (Qwen3.5-9B), the ALFWorld evaluation uses 93 valid-seen tasks from four retained families rather than the standard benchmark, and WebShop is run on a 52-task validation split with a 100-product catalog with no argument given for why the full environment is unnecessary. On telecom, the highest-baseline domain, the baseline retains the best pass@1 (71.2 against the combined variant's 71.0) while GRAR with rubric reaches the domain best at 72.7, so the paper's own table contains a domain where the combined method does not lead.

  2. The components that drive the measured improvement are the environment's own progress signal and an unvalidated judge, while the mixed-group branch is ordering-invariant by construction, so the framework's distinctive claim is the least well supported part. Table 2 reports that disabling the deterministic anchor fusion costs 9.6 pass@1 and 7.7 pass@5 on WebShop, which the paper itself calls the largest isolated channel in that ablation, and the anchor is the environment's own per-step task score or subgoal ladder rather than anything the method derives. The judge is the second channel: across the runs, deterministic overrides resolve 34.6 percent of candidate settlements, the batched judge resolves 56.6 percent with mean self-reported confidence 0.91, and the confidence gate never altered a reward. Since all-failed groups have identically zero trajectory advantage, the judge's scores are the entire learning signal in the regime the paper emphasizes, and the paper states plainly that it does not claim to measure the judge's accuracy; Appendix I's six audit criteria are structural constraints on influence (who may be scored, how many steps, what the clamps do) rather than evidence about correctness, and the worked trace itself notes that the judge's verdicts are plausible and well supported but not independently verified. The confidence gate compounds this, because self-reported model confidence is known to be poorly calibrated, so gating on it preferentially admits confident judgments and discards hedged ones. Meanwhile the mixed-group branch cannot alter which trajectory is preferred: Section 3.4 states that the guarantee has two parts and that trajectory advantages are computed from the terminal reward alone by construction, and Lemma 1's purpose is to show that the step bonus is too small to reverse success-versus-failure ordering, which is satisfied at the default weight. So in mixed groups the branch only perturbs within-trajectory token credit while leaving cross-trajectory ordering untouched, and the paper never isolates whether that perturbation helps, because the rubric-only and graph-only variants differ in more than the ordering channel. A further gap is that the judged branch can be actively harmful in a way the design does not bound: in an all-failed group, if the judge gives a positive score to early plausible steps of a trajectory that ultimately fails, the fusion optimizes those steps with no terminal counterweight, and the page-visit candidates scored zero in the Appendix C trace illustrate exactly the class of judgment this depends on.

Questions for authors

Multi-seed evidence. Please report at least three seeds for the WebShop and tau-squared columns with means and standard deviations, and a paired comparison against terminal-only GRPO. Given that the baseline's own pass@1 standard deviation is 11.6 and the reported average margin is 6.5, what is the basis for concluding that GRAR exceeds the baseline rather than that the seeds differ?

Checkpoint selection. Are the main-table entries the best checkpoint over the run, or the final checkpoint? If they are selected, please report the final-checkpoint and last-five-average numbers as well, since the sensitivity study is explicitly a per-checkpoint maximum.

The anchor ablation compared with the baseline. Table 2 reports that GRAR with rubric and anchors disabled still reaches 23.1 pass@1, which is 7.7 points above the terminal-only baseline. That means the graph component alone, without the environment's progress signal, already carries most of the effect. Can you report the corresponding anchor-on and anchor-off numbers for a variant that also disables the graph, so that the environment's dense signal can be evaluated as a standalone baseline? If WebShop exposes a per-step task score, a natural control is terminal-only GRPO augmented only with that score.

Judge accuracy. The paper deliberately bounds the judge's influence rather than measuring its accuracy, and the gate never triggered in the diagnostics. Can you report the judge's agreement with an independent assessment (human or a different model family) on a sample of all-failed-group candidates, and the effect of removing the confidence gate entirely? If the judge is systematically overconfident, the gate is not providing the protection it appears to provide.

Judge model overlap. The judge is Qwen3.6-35B-A3B and the policy is Qwen3.5-9B, from the same family. Since scoring its own family's outputs is a documented source of self-preference bias, did you test a judge from a different family, or a non-LLM rubric checker where the environment permits one?

Does the mixed-group branch help? Because Lemma 1 guarantees that the step bonus cannot reverse success-versus-failure ordering, the mixed-group branch can only redistribute credit within trajectories. Please report a variant with graph settlement disabled (rubric only) and one with the step bonus applied only in all-failed groups, so the two effects are separated, and report whether the mixed-group branch changes anything beyond noise.

Evaluation scope. Why is WebShop run on a 52-task validation split with a 100-product catalog rather than the standard environment, and why does the ALFWorld evaluation retain only four families (93 valid-seen tasks)? Would the conclusions hold on the standard configurations, and do the results extend to a second model scale?

Telecom. On telecom pass@1 the baseline attains 71.2 and the combined variant 71.0, with the rubric-only variant at 72.7. Since the abstract reports that the best variant improves on both metrics in the evaluated settings, please state the per-domain exceptions explicitly in the main text and explain what differs about telecom.

Group-local graph cold start. The graph is rebuilt per group and discarded, and node potentials are calibrated only from the current group's trajectories. For a group with one success and seven failures, most nodes have very few terminal observations, and the Laplace smoothing mentioned in Appendix G is applied only in the ALFWorld rubric variant. How stable are the node potentials at group sizes of eight, and does potential variance across groups contribute to the variance observed in the training curves?

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

This paper introduces GRAR, a complementary reward estimation framework for agentic RL. Specifically, this method separately processes two conditions of sampling trajectories in agentic RL. For all-failed trajectories, this method applies a rubric-based reward estimation to avoid missing supervision. For trajectories that contain at least one successful trajectory, GRAR applies a graph-based reward estimation method to assign fine-grained process-level rewards. Experiments show that GRAR has advantages over previous agentic RL methods in three different agentic benchmarks.

Critical strengths
  1. This paper aims to address an important problem: the sparsity of reward in agentic RL, and proposes a simple but effective method to address the problem.
  2. The experiments in this paper are comprehensive, including three benchmarks with various baselines.
Critical weaknesses
  1. The novelty and contribution of this paper are limited. I find various papers contribute to graph-based reward estimation [1-3] and rubric-based reward estimation [4,5]. A simple combination of the two directions cannot be seen as a huge novelty and significant contribution. It could be beneficial to further compare with the existing methods.

  2. The generality of graph-based reward estimation is a big concern. The basis of this direction is a reliable state determination to group similar states. However, for some agentic tasks with stochastic states (e.g., math and coding tasks, where the state is the return of code, which is dependent on the writing code), this may limit the generality of GRAR.

  3. The reliability of rubric-based reward estimation is important, but using an LLM solely as a judge could raise this concern. Further discussion or experiments could be helpful.

  4. The experiments only use Qwen3.5-9B as the base model, which is limited in demonstrating applicability to different models or model families. It would be better to apply more base models in the experiments.

Reference:

[1] Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning.

[2] RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models.

[3] Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling.

[4] DR Tulu: Reinforcement Learning with Evolving Rubrics for Deep Research.

[5] Step-DeepResearch Technical Report

Questions for authors

See critical weaknesses

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

This paper proposes GRAR, a post-hoc credit-assignment framework for GRPO-based training of LLM agents. For rollout groups containing successful trajectories, graph settlement derives step-level credit from a group-local graph and verified outcomes. For all-failed groups, rubric settlement combines deterministic rules with a frozen LLM judge to score selected steps. These process rewards enter as bounded token-level bonuses while terminal rewards remain unchanged. Experiments evaluate Qwen3.5-9B across τ²-bench, WebShop, and ALFWorld.

Critical strengths

1.Addresses a concrete limitation of terminal-only GRPO.

GRAR distinguishes all-failed groups from groups containing successes and provides process feedback without changing terminal rewards. The bounded advantage-fusion design makes the scope of the process signal explicit.

2.Encouraging results across distinct agent domains.

Evaluation spans tool-calling dialogue, shopping, and household tasks. GRAR improves over terminal-only GRPO on most settings, and the comparison with GiGPO uses a shared trainer and evaluation protocol. The appendix also provides useful examples, hyperparameters, and diagnostics.

Critical weaknesses
  1. The incremental value of the graph-based design is not sufficiently isolated.

The framework combines outcome-based step credit, environment progress signals, deterministic penalties, and LLM-judged process rewards. These are individually familiar ideas, making controlled comparisons important for establishing the contribution of their combination. In particular, removing anchors reduces WebShop graph-only pass@1 from 32.7 to 23.1. Comparisons against GRPO or GiGPO using the same progress signals, and a simple step-reward baseline using the same judge, would clarify what the graph and settlement design add.

  1. The validity of signature-based state merging is insufficiently examined.

Nodes are induced by normalized action signatures, which need not identify equivalent environment states. The same action under different observations or histories may have different consequences, yet merged outcome statistics determine its credit. The paper does not quantify incorrect merges or test sensitivity to retaining more state information. The rules for preserving task-determining arguments also need clarification.

  1. Deterministic penalties may conflate unsuccessful outcomes with poor decisions.

Rubric settlement assigns −1 to results classified as errors, empty, unavailable, or not found. Some such outcomes can arise from reasonable exploration and provide useful information. The trace audits establish that these rules are enforced, but do not validate their correctness. An error analysis and ablation of these overrides would help establish whether they introduce systematic miscredit.

  1. Experimental uncertainty and checkpoint selection need clarification.

Each training configuration uses a single seed, without uncertainty estimates. Table 2 additionally reports the per-metric best checkpoint, leaving unclear whether the main-table pass@1 and pass@5 values correspond to one consistently selected model. Repeated training runs and a checkpoint selected on a separate validation set would strengthen the reported gains.

Questions for authors

1.Can the authors add progress-matched GRPO/GiGPO baselines and a simple process-reward baseline using the same judge, to isolate the contribution of graph construction and settlement?

2.Which action arguments and state information are retained when merging nodes? How often are semantically different states merged, and how sensitive are results to the abstraction?

3.What fraction of deterministic negative rewards penalize reasonable exploration? Do the gains persist without the error and repeat overrides?

4.How are checkpoints selected for Table 1? Please report both metrics from the same selected checkpoint and provide results across multiple training seeds.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.