acceptodds
Under review as a conference paper at ICLR 2027

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Abstract

When training large language models with reinforcement learning, terminal rewards provide little guidance about which steps matter. Common methods for assigning step credit overlook that work built on uncorrected mistakes is wasted while independent work remains valid. With only a final success/failure reward, every step in a failed episode has zero total future reward, even when it made progress. We propose Dependency-Aware Reward Shaping (DARS), which represents task progress as predicates linked by prerequisite relations and assigns step-level credit over the dependency graph. An annotator marks which predicates each step verifies, invalidates, or repairs. Verified predicates are discounted according to graph distance from the nearest broken prerequisite, while independent predicates are unaffected. Repairs update these weights based on any errors that remain; invalidated predicates need re-verification to regain credit. A fixed potential converts these annotations into signed per-step rewards. A common reward and annotation interface allows DARS to integrate with a range of reasoning and agentic training methods, such as GiGPO and ARPO/AEPO, without changing their rollout strategies or optimizers. Across five task families and models from 1.5B to 8B, DARS improves success by up to points over GiGPO trained with the same budget and harness (ALFWorld), raises the WebShop task score and Search-R1 QA accuracy, complements AEPO's entropy-based training on AIME24/25 with a Python interpreter, and exceeds OmniOPD in controlled tool-free reasoning comparisons at 1.7B and 4B. Ablations show that step-level credit, dependency attenuation, and graph topology each contribute. On ALFWorld, a distilled 8B annotator matches the API annotator, enabling DARS to run efficiently without a frontier judge.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent, Reinforcement Learning, Credit Assignment

Reviews

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

The paper proposes DARS, a credit assignment paradigm for training LLMs on agentic tasks through RL. A prerequisite graph represents task dependency, and then an annotator labels verification, invalidation, and repair events. Constant local monitoring on the graph defines potential, of which the calibrated changes provide step credit alongside the original outcome signal. Experiments cover ALFWorld, WebShop, Search-R1, agentic mathematics, and tool-free reasoning, where the strongest evidence is a matched ALFWorld 1.5B improvement and ablations for attenuation, topology, and credit assignment. Other benefits depend on recipe, scale and training budget.

Critical strengths
  1. The graph representation is first-principled with how an agentic task should be evaluated.
  2. The method separates local evidence, broken prerequisites, repair, and re-verification in a structured way. The same-annotation scalar control, attenuation twins, and event-preserving topology comparison test substantive choices in using structured feedback. In particular, serializing WebShop's requirements costs 14.2 points (Table 4 and appendix K). This provides useful knowledge beyond a performance ranking.
  3. On ALFWorld 1.5B, DARS reaches 96.9% vs. 86.9% for GiGPO under the same 500-step policy budget and harness. The paper also supplies equally extended WebShop ablations, baseline catch-up, and Search component failures (Table 8, 9, 13, 14 and 18). These support a credible and narrower practical contribution.
Critical weaknesses
  1. Tool-free evaluations combine checkpoints, hosts, and repeats, with unequal mixtures across arms and a different 4B primary-host collection from the pooled summary. Exact schedules, raw scores, decoding seeds, and permutation blocking/exchangeability are not specified (Table 21 and 23). Thus the significance claims are not fully assessable. Most central comparisons also use one training run per arm - decoding repetitions measure those policies, not variation in the training-method effect. The paper acknowledges this, but small cross-domain gains remain uncertain.
  2. The selected ALFWorld hard-case audit, same-annotator repeatability, and outcome-conditioned consistency checks do not establish population correctness of intermediate V/B/P events. Outside ALFWorld, timing and semantics receive limited independent validation; 29% of usable 4B reasoning annotations omit an answer verdict (Appendix B and J). Since the potential depends on these annotations, this limits the interpretation of its rewards as valid local progress.
Questions for authors
  1. Can you provide the schedules, raw scores, decoding seeds, and exact permutation design behind Table 21 and 23? Do the principal DARS-scalar and DARS-OmniOPD effects remain when matching existing cells by checkpoint and host?
  2. What validation supports intermediate event correctness and timing in WebShop, Search-R1, and mathematics? Can inspection/replay of existing annotations quantify errors and omissions and assess sensitivity to correcting or excluding them?
  3. A frozen-model graph-in-context comparison is interesting additional verification: Just give the untrained model the same graph in context and ask it to solve the task by executing the graph. Can you provide your insights to this idea, and provide some numbers if it makes sense to do so?
6 comments
AuthorsOpenReview ↗

Author Rebuttal Part 1

Dear Reviewer cvNT,

Thank you for your careful reading of our paper and for your constructive feedback. We respond to your comments point by point below.

W1&Q1: How were the tool-free comparisons in Tables 21 and 23 evaluated, how much uncertainty do decoding repeats capture, and do the DARS–scalar and DARS–OmniOPD results hold when checkpoints and hosts are matched?

We release the full evaluation ledger (542 cells, 37 columns), per-arm schedules, per-sample records (Table 23: 82/82 upper, 53/53 lower; Table 21: 62/78), and the exact permutation code. Design: the unit is one evaluation cell, over all relabelings of the two arms' cells, unblocked, with no multiplicity correction — Table 21 by exact enumeration, Table 23 by 200,000 Random(0) draws, which exact enumeration confirms (.0051).

Decoding is uniform and documented for every cell: T=1.0, top_p=1.0, top_k=−1, n=8, max_new_tokens=32768, chat template, thinking on, sglang 0.5.10.post1. The sampler seed was not set, so each repeat is an independent draw rather than a replayable run — which is precisely why we report arm means over cells with permutation tests rather than single cells or maxima.

On matching: the two arms' checkpoint grids coincide at 1.7B step 30; at 4B they do not overlap, so the matched comparison there is by host.

  ┌───────────────────────────────┬───────┬─────────┬────────────────┐
  │             Match             │ DARS  │ OmniOPD │       Δ        │
  ├───────────────────────────────┼───────┼─────────┼────────────────┤
  │ 1.7B, m30, step 30            │ 59.79 │ 56.98   │ +2.81          │
  ├───────────────────────────────┼───────┼─────────┼────────────────┤
  │ 1.7B, m40, step 30            │ 57.95 │ 57.23   │ +0.72          │
  ├───────────────────────────────┼───────┼─────────┼────────────────┤
  │ 1.7B, all cells (10 v 9)      │ 58.23 │ 57.24   │ +0.99 (p=.031) │
  ├───────────────────────────────┼───────┼─────────┼────────────────┤
  │ 4B, m35 host-matched (16 v 9) │ 79.49 │ 78.29   │ +1.20 (p=.005) │
  └───────────────────────────────┴───────┴─────────┴────────────────┘

Host-stratifying the 1.7B cells gives +0.95 (p=.040). Every checkpoint-matched pair and every host-matched contrast favours DARS.

AuthorsOpenReview ↗

Author Rebuttal Part 2

W2&Q2: What independent evidence supports the correctness and timing of intermediate events in WebShop, Search-R1, and mathematics, and how sensitive is reward allocation to errors and omissions in those annotations?

Thank you. We distinguish two questions: whether an event is correct, and whether the resulting supervision is useful for training. We have studied annotation quality through environment checks, answer checks, timing interventions and reward replay. These provide evidence about specific aspects of quality; they do not certify every intermediate event.

(1) What can serve as ground truth for V/B/P?

V records that a result has been established, B that an error has been introduced or a condition invalidated, and P that a previous error has been repaired. Validating an event therefore requires both a defined node meaning and evidence at the annotated turn. The original LLM annotation is not ground truth. Environment states and benchmark answers provide external references for some events; open-ended reasoning requires additional semantic judgment. Different valid decompositions and discovery-versus-confirmation timings can also produce different annotations of the same trajectory. Consequently, a disagreement is not automatically an error, but agreement alone does not establish correctness either.

For WebShop, we reconstructed predicate events from goal metadata and page states on 1,280 trajectories per run, covering successes and failures. V precision was 97.8–98.2% when timing was ignored. Exact-turn precision was 22.7–28.6% at one-turn alignment and 29.8–51.4% at zero-turn alignment; within-one-turn precision/recall at one-turn alignment was 57.3–75.9%/29.8–41.7%. These checks support recognition of the covered predicates while identifying timing and recall limitations; they do not validate every B/P event.

For Search-R1, the reference combines the dataset's gold answers, the environment's exact-match scorer and the turn containing the submitted answer. Among 480 stored failed trajectories, 406 contained an incorrect answer submission. New annotations emitted 337 B(answer) events, of which 263 matched: precision = 263/337 = 78.0%, recall = 263/406 = 64.8%. All 263 matches were at the submission turn. These are incorrect-answer-event metrics, not accuracy over all V/B/P events. The annotator was told the trajectory failed; original training annotations were unavailable. The audit annotator version also differs from the corpus annotator. These metrics therefore do not validate historical training labels or intermediate-hop correctness.

For mathematics, our exploratory timing study compared 30 natural distance-two placements from 15 trajectories and two annotator arms with 32 artificially shifted annotations from one arm. GLM flagged 0.0% versus 65.6%, and Astra 6.7% versus 50.0%, as unsupported or incorrectly timed. This is consistent with defensible timing variation and detection of deliberate perturbations. The groups were unpaired, natural placements inherited segment-level judgments, and node IDs lacked fixed semantic definitions. These LLM judgments therefore provide supporting evidence rather than ground truth for intermediate reasoning.

The dependency graph itself is also an inferred representation, not a certified or necessarily unique proof graph. To examine concrete failure modes, we added an Astra-assisted qualitative inspection of eight cached task graphs (four each from WebShop and ALFWorld) and ten stored mathematics re-annotations under the production rubric, deliberately including V-only, B, P and empty-event cases. The cases were selected before the new judgments, and the inputs and reviews are retained. These are separate audit inputs, not identified errors in the exact labels or graph instances of the training comparisons below; the audit describes failure modes rather than estimating population error rates.

AuthorsOpenReview ↗

Author Rebuttal Part 3

ComponentWhat the inspection found
GraphSome shopping graphs preserve the requested attributes but serialize independent properties, such as color and capacity, into prerequisites. One inspected graph leaves independent requirements unordered. Requirement coverage and edge correctness need separate checks.
VCorrect final answers can be recognized only at a later repetition; a verified answer can also agree with a faulty reference. Intermediate IDs such as step:2 lack exported meanings, preventing definitive node-level validation.
BOne truncated geometry solution was assigned B(answer) although it never stated a final answer. An unfinished solution should not automatically receive an incorrect-answer event.
PTwo inspected B-to-P sequences coincide with explicit algebra errors and their subsequent corrections. Another repair placement remains ambiguous. Missing node meanings prevent certifying the precise node attribution even when the local error and repair are evident.
OmissionsThe inspected empty-event cases contain no final answer, so absence of an answer verdict is appropriate; whether useful intermediate work was omitted depends on the unspecified node meanings.

(2) Can training still be effective, and how much does correcting annotations change credit?

Imperfect supervision can retain useful learning signal. In Li et al., Findings of EMNLP 2025, SFT of Qwen2.5-32B-Instruct on approximately 4,600 reasoning traces with wrong final answers increased average accuracy from 56.7% to 63.1%, compared with 66.3% using correct traces. This supports learning useful reasoning behavior from imperfect examples. In Shao et al., ICML 2026, Qwen2.5-Math-7B gained 21.4 percentage points on MATH-500 with random rewards, versus 29.1 with correct rewards. These results establish that noise and effective training can coexist in specific settings; they do not establish that our annotation errors are random or harmless.

Our evidence for DARS's utility is its held-out evaluation with the annotations actually used. For example, the matched ALFWorld 1.5B evaluation improves success by 4.85 percentage points over GiGPO (game-clustered 95% CI [+1.21, +8.77], one training run per arm). Useful credit also survives changes of representation: four automatically generated WebShop specifications produced credit–environment-progress correlations of 0.357–0.509, versus 0.264 for our specification, on the same 49 failed trajectories within a 120-trajectory pool. Only one difference interval excludes zero. In a separate step-200 comparison, automatically generated graphs achieved 69.21% success versus 69.35% with our rule (paired difference, ours minus generated: 0.14 percentage points, 95% CI [−1.6, +1.8]; one training run per arm). Graded task score still favored our rule by 2.27 points. These results support the utility of the implemented training pipeline and tolerance to the tested specification changes; they do not certify each inferred event or edge.

We quantify credit sensitivity by holding trajectories and the reward computation fixed and changing only annotations. Correcting Search-R1 answer events changed 212/480 = 44.2% of reward vectors. The summed absolute reward change was 42.8% of the original summed absolute reward, and 7.37% of originally nonzero-reward turns changed sign. Replacing WebShop annotations with reconstructed events changed 93.9–95.9% of vectors; randomly deleting 19.7–22.3% of events changed 52.3–55.1%. Random deletion measures omission sensitivity, not targeted removal of adjudicated errors. These are measurable changes in credit allocation, not estimates of lost task accuracy. The causal performance cost of annotation errors remains unmeasured without matched training on original and corrected labels.

Finally, the quoted 29% mathematics omission figure came from a separate audit tape. Answer-verdict absence on the actual training tapes was 59/2,919 = 2.0% at 4B and 317/775 = 40.9% at 1.7B. These are absence rates, not independently established error rates: the rubric requires no answer event when no final answer is stated.

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

The paper proposes Dependency-Aware Reward Shaping (DARS). This method represents task progress as predicates connected by prerequisite dependencies and assigns step-level credit based on the dependency graph. Across five categories of tasks and on models with parameter scales ranging from 1.5B to 8B, DARS achieves SOAT results.

Critical strengths

S1: DARS proposes a dependency-aware reward shaping method that provides fine-grained step-level credit assignment. It can distinguish valid task progress, dependency errors, and independent subgoals, which helps the model to better learn from intermediate steps.

S2: The paper conducts extensive experiments on several agentic and reasoning benchmarks, including ALFWorld, WebShop, Search-R1, and math reasoning tasks.

Critical weaknesses
  1. Identifying predicates, abstracting actions, and obtaining these dependencies will be major limits for this method. An incorrect dependency graph directly leads to incorrect credit assignment.

  2. Although DARS is presented as a reward-shaping framework, its implementation relies on manually specified predicate vocabularies, dependency topologies, and domain-specific annotation rules. It can not be used in different benchmarks without human annotations.

Questions for authors

Q1. How sensitive is DARS to errors in predicate identification and dependency graph construction? The method will become invalid when dependency graph is wrong

Q2. How much human annotations are required to apply DARS to a new benchmark? if there is no human annotations, Could the authors demonstrate whether predicates and dependency graphs can be constructed automatically with the help of LLM? How bad the predicates and dependency graphs will be in this case?

3 comments
AuthorsOpenReview ↗

Author Rebuttal Part 1

Dear Reviewer PvCx, Thank you for your careful reading of our paper and for your constructive feedback. We respond to your comments point by point below.

W1 & Q1: Sensitivity to errors in predicates and dependency graphs

The dependency graph determines step-level credit, so a different graph produces different step credit. Two factors limit the impact of different step credit. First, step credit supplements the trajectory-level reward rather than replacing it, so the outcome signal is unchanged when step credit is imperfect. Second, DARS does not depend on a single correct graph. Different reasonable predicate sets and topologies yield credit of similar or better quality, while clearly wrong graphs are detectably worse.

To measure this, we held the annotator, trajectory pool, and shaping rule fixed and changed only the specification. On a pool of 120 WebShop trajectories, we computed the pooled per-turn Pearson correlation r between assigned credit and the environment's recorded progress on the 49 unsuccessful trajectories. The four LLM-written specifications are those described in Q2.

Table 1: Credit–progress correlation under different specifications (WebShop, fixed pool)

Specificationr95% CI of (arm − ours)
Ours, as submitted0.264—
LLM-written, ParallelAnd (2 roots)0.509[+0.098, +0.368]
LLM-written, annotator-supplied edges0.376[−0.050, +0.244]
LLM-written, chain0.370[−0.047, +0.227]
LLM-written, ParallelAnd (3 roots)0.357[−0.103, +0.263]
Null: turn-count proxy0.179[−0.229, +0.025]
Null: another task's graph0.150[−0.278, +0.047]
Null: shuffled credit0.085[−0.358, −0.010]
Null: everything satisfied−0.143[−0.575, −0.265]

All four LLM-written specifications produce credit at least as well aligned with progress as ours, and one is significantly better. The useful signal therefore does not depend on reproducing our exact predicates and topology. Clearly wrong specifications have lower correlations, for example a graph from another task (0.150) or shuffled credit (0.085). DARS is therefore robust to reasonable variation in the specification but not to grossly wrong graphs. We note that this offline metric does not separate our specification from the turn-count proxy (CI includes 0), because it only measures linear alignment with recorded progress. End-to-end training (Table 3 below) is the primary evidence: replacing our graphs with automatically generated graphs leaves task success unchanged.

AuthorsOpenReview ↗

Author Rebuttal Part 2

W2 & Q2: Human effort and automatic construction

Human effort. DARS does not require per-instance or per-trajectory human annotation. We design one set of benchmark-specific decomposition rules in the annotation prompt, and the dependency graphs for all task instances are generated automatically from it. Standard agent RL training already requires a task-specific prompt. We drafted ours with Opus 4.8 from the method description, authored it once, and did not tune it.

Can an LLM construct the specification? We asked four frontier models to generate a complete specification: a predicate vocabulary, a dependency topology, and an annotator prompt. Each model received the same two example episodes, the public action list, and the specification contract. Outputs were validated mechanically and used without human editing or model-specific coaching. An invalid output received one generic retry.

Table 2: Automatic specification construction on WebShop

ModelUsable specAttemptsTopology chosen
DeepSeek-V4.1-flashyes1Chain
Doubao-Seed-2.1-proyes1ParallelAnd, 2 roots
GLM-5.2yes1Annotator-supplied edges
Kimi-K3.1-proyes2ParallelAnd, 3 roots

All four models produced usable specifications, three of them on the first attempt, and they chose different representations. The fourth model fixed its initial topology error using only the validator's feedback.

How good are the automatic specifications? As Table 1 shows, the credit they produce is comparable to or better than that of our submitted specification.

End-to-end training. We then replaced our per-instance graphs with graphs generated by an LLM from the task description and action list alone, using a fixed generic constructor prompt with no examples and one validation retry. The annotator, training configuration, and 200-step budget were unchanged, so the two arms differ only in the graph source.

Table 3: WebShop, step 200

Graph sourceSuccessTask score
Ours0.6935 ± 0.03030.8495 ± 0.0252
LLM-generated0.6921 ± 0.01510.8268 ± 0.0139
Paired difference (ours − generated), 95% CI+0.14 pp [−1.6, +1.8]+2.27 pp [+1.0, +3.5]

Values are mean ± s.d. over 11 paired evaluation runs, with identical task sets for the two arms within each pair. Each run draws a different task subset, so the s.d. mainly reflects task-subset variation, and the paired difference is the appropriate comparison. Task success is statistically indistinguishable. Our graphs retain a small but significant advantage in graded task score, which leaves room for improving automatic construction, for example through prompt optimization.

These results show that DARS can be set up for a benchmark with one prompt and no per-instance annotation, and that automatically constructed graphs preserve task completion on WebShop. We will add these experiments and a discussion of this limitation to the revision.

We hope that our clarifications address your concerns. Thank you again for your thoughtful feedback, which helped us improve the paper.

Sincerely,

The Authors

AuthorsOpenReview ↗

Author Response

Dear Reviewer PvCx,

Thank you for your time and feedback. As the discussion period is drawing to a close, we would appreciate your thoughts on our response. If your concerns have been resolved, we would be grateful if you could consider updating your assessment and score accordingly.

Best regards,
The Authors

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

The paper addresses credit assignment in RL for LLM agents trained with outcome-only rewards, where every step of a failed episode receives zero return. DARS describes each task as a dependency graph of predicates (sub-goals). An LLM annotator labels, for each step, which predicates it verifies, invalidates, or repairs. A deterministic potential sums the verified predicates and down-weights those below a broken prerequisite by exp(-λd). The clipped change in this potential is used as a step reward and plugged into GiGPO, ARPO/AEPO, or a token-level objective. Experiments cover ALFWorld, WebShop, Search-R1, and math with and without tools (1.5B to 8B). The main reported result is +10.0 points over a budget-matched GiGPO on ALFWorld 1.5B (96.9 vs 86.9), with smaller gains elsewhere.

Critical strengths
  1. Outcome-only rewards cannot separate progress from mistakes inside a failed episode, and the dependency view (an error affects dependent work but not independent work) is intuitive. The LLM only outputs structural events, and the reward is computed deterministically, so the same annotations can be re-credited offline for clean ablations.
  2. DARS only changes the reward and works on top of GiGPO, ARPO/AEPO, and a token-level objective without changing their rollouts or optimizers.
  3. The paper uses budget-matched local baselines, paired tests, and an equally extended GiGPO control, and it reports negative findings openly. On ALFWorld 1.5B, DARS leads GiGPO at every checkpoint and learns faster.
Critical weaknesses
  1. Gains are smaller and less consistent than claimed. Under the paper's own strictest controls: on WebShop 1.5B, DARS does not beat an equally extended GiGPO (Table 13). On WebShop 7B, success improves by 1.5 points but task score does not (-0.2). The Search-R1 held-out gain (+2.1) shrinks to +0.2 with σ = 0.5. Math with Python trains for only 15 steps, with about ±5 points of decoding noise. Tool-free math improves over the untrained model by only 0.33 to 0.75 points.
  2. The ablations do not isolate the benefit of the graph. Ablated variants are often worse than plain GiGPO. For example, λ = 0 scores 95.2 vs. 98.1 for GiGPO on ALFWorld 7B, and both WebShop topology arms are below GiGPO. The ablations therefore show that a mis-specified shaped reward hurts, not that DARS beats no shaping. In addition, three of the five domains use plain chains, and negative credit is rare (0.4 to 3.5% of turns), so the core idea of independent branches and repair is exercised in few settings.
  3. Limited generality and annotation concerns. Each domain needs its own prompt rules and sometimes extra terms (for example, Search-R1 collapses without an answer-commitment term). The headline results also come from different annotators and recipes. The annotator has a 15% major-error rate in a manual audit and sees the outcome and reference answers. A matched baseline in which the same LLM directly scores per-step progress, without a graph, is missing on the agentic tasks.
Questions for authors
  1. Why is κ = 0.3 the default when κ = 1 works better on WebShop 1.5B (67.7 vs. 63.0 success)? Does the graph-vs-chain topology result still hold at κ = 1?
  2. On ALFWorld and WebShop, how does DARS compare with the same annotator directly scoring per-step progress (no graph), under the same budget?
  3. Why does DARS with λ = 0 perform worse than plain GiGPO on ALFWorld 7B (95.2 vs. 98.1)?
  4. How much does performance depend on the annotator seeing the outcome and reference answer, and what must be hand-designed to apply DARS to a new domain?
5 comments
AuthorsOpenReview ↗

Author Rebuttal Part 1

Dear Reviewer D5ip,

Thank you for your careful reading of our paper and for your constructive feedback. We respond to your comments point by point below.

W1. Size and consistency of the gains

We agree that the gains are not large in every setting. Below we report updated matched evaluations and measured noise levels, and we say plainly where a difference is within noise.

ALFWorld and WebShop, 1.5B. In an updated matched evaluation, DARS outperforms GiGPO by 4.85 points on ALFWorld at 500 steps and by 5.0 points on WebShop at 150 steps. Each comparison uses the same policy-training budget for both methods. The differences are significant across repeated decoding runs of the evaluated checkpoints (p = 0.0078 and p = 0.001). These p-values capture decoding variance for a single training seed, not variance across training seeds.

WebShop 7B and Search-R1. We agree that the WebShop 7B task score (−0.2) and the held-out Search-R1 gain (+0.2, σ = 0.5) are within noise. The revision will state this instead of counting them as gains. Across the main tables, a DARS configuration has the highest aggregate score in each of the five domains, and DARS wins 8 of 9 task/model/backbone comparisons. The size of the gain varies by setting.

Tool-free math. In our updated evaluation, DARS improves the average over AMC, AIME24, and AIME25 by 0.93 points at 1.7B and by 0.88 points at 4B, relative to the instruction-tuned models before RL. These models already reason with chain of thought and start close to the ceiling (the 4B model scores 97.26 on AMC before training), so there is little room to improve.

ScaleArmPeak step3-benchmark avg ± SDDecoding drawsAMCAIME24AIME25
1.7BBefore RL—57.17 ± 0.88484.5350.3136.67
1.7BDARS3058.10 ± 1.12585.1350.5838.58
1.7BDirect-score control (no graph)1557.74 ± 1.99386.1549.0338.06
4BBefore RL—79.25 ± 0.783097.2673.8966.61
4BDARS15080.13 ± 0.95797.3775.5467.50
4BDirect-score control (no graph)15079.70 ± 0.95497.9775.0066.14

The direct-score control uses the same annotator and trajectories as DARS. It assigns a scalar progress score at each step and uses the clipped change in that score as the step reward, without a graph. Each arm is reported at its best measured checkpoint, from one training seed. The DARS gains over the pre-RL model are positive at both scales but not significant (4B: p = 0.051 against 30 baseline draws; 1.7B: p = 0.21). DARS and the direct-score control cannot be separated at this precision (p = 0.50 and p = 0.80). Picking each arm's best checkpoint from 5–7 noisy evaluations also inflates every peak, so we treat these results as showing the direction of the effect only.

Math with Python: training length and noise. The ±5-point figure in the caption was a conservative estimate that we had not measured. We have now measured it from 56 per-draw benchmark records across seven evaluation cells, all run under Table 2's exact protocol. A single draw has an SD of 3.73 points on the AIME24/AIME25 average. Each cell averages four independent draws, which gives a standard error of 1.9 points and a 95% interval of ±3.7 points. Under this measured noise, AEPO+DARS has the highest single cell (67.5) and the highest mean across the three checkpoints (63.6, versus 61.7 for AEPO and 62.0 for ARPO). However, the differences between these three-checkpoint means are within noise (p = 0.13–0.30), so we report them as directional. Appendix I will give the per-cell table.

Fifteen steps is a substantial amount of training in this setting. At batch size 128 with 16 rollouts per prompt, it covers 1,920 prompts and about 31,000 tool-augmented rollouts. The policy is the instruction-tuned Qwen3-8B, which can already use tools, so this phase refines its behavior rather than teaching the task from scratch. Held-out AIME accuracy peaks within steps 5–15 for every arm, while training-side validation keeps rising (0.16 at step 15 to 0.68 at step 40). The reported window is therefore the peak region, not a truncated run.

AuthorsOpenReview ↗

Author Rebuttal Part 2

W2 and Q3. Do the ablations isolate the benefit of the graph? Why is λ = 0 below GiGPO?

Setting λ = 0 keeps the annotation call, the graph, the persistence latch, and the signed step reward r_t = ρ · clip(Φ_G(t) − Φ_G(t−1), −κ, κ) (Eqs. 9–10). It removes only the attenuation along dependency edges (Appendix K.1). λ = 0 therefore reduces DARS to counting milestones. When an upstream predicate fails (for example, the agent picks up the wrong object in ALFWorld), downstream steps that satisfy their local predicates still receive full positive reward. This gives dense positive feedback to trajectories that are already off track, which is why λ = 0 can fall below a no-shaping baseline.

Three results isolate the graph more directly:

  1. No-graph control (Q2 below). With the same annotator assigning credit without a graph, training is unstable on ALFWorld and collapses on WebShop and Search-R1.
  2. Graph versus chain at κ = 1. The two arms differ only in topology. The graph arm leads by +4.92 success points (71.35 vs. 66.44) and +2.26 task-score points on WebShop. Its success is higher in 12 of 12 decoding draws (p = 0.0005, one training seed per arm).
  3. Direct-score control on math (table in W1). It cannot be separated from DARS on accuracy at the current precision.

Chains and rare negative credit. Three of the five domains use chains, and negative credit appears in 0.4–3.5% of turns. A chain still uses the dependency mechanism: when a prerequisite breaks, every predicate below it is attenuated by exp(−λd). Only independent branches are limited to fewer domains, and we will state this scope in the revision.

W3. Generality and annotation

Per-domain design. Each domain needs a predicate vocabulary, dependency rules, and an annotator prompt, but no per-trajectory human annotation. These components can be generated automatically. As reported in our response to Reviewer PvCx (Q2), four LLMs from different vendors produced usable WebShop specifications without human editing or model-specific coaching, three on the first attempt. Their credit signals were at least as well aligned with environment progress as our handwritten specification. In a training comparison, automatically generated graphs reached 69.21% success versus 69.35% with ours.

Q1. Why is κ = 0.3 the default when κ = 1 is better on WebShop 1.5B?

Because Φ lies in [0, 1], κ = 1 never clips, so it is a no-clipping control rather than a tuned alternative. Table 16 comes from a single training seed. We keep κ = 0.3 because every reported number was produced with it, and because in the one measured clipping comparison (WebShop 7B), κ = 0.3 was kept. We will revise the appendix justification for this choice.

Does the graph-versus-chain result hold at κ = 1? Yes. With κ = 1, the graph and chain arms differ only in topology, and both peak at step 170. Over twelve decoding draws on one evaluation host, graph success is 71.35 versus 66.44 for the chain (+4.92, higher in 12 of 12 draws, p = 0.0005). Task score is +2.26 higher. Each rule was trained with one seed.

AuthorsOpenReview ↗

Author Rebuttal Part 3

Q2. Same annotator directly scoring per-step progress, without a graph

We ran this control in its least constrained form: the same annotator assigns credit directly, with no graph and no progress scale. In this design, the annotator is called once per trajectory, identifies the first decisive error in a failed episode, and assigns dense credit to the steps before it. Each run matches its paired GiGPO baseline in annotator, call budget, step budget, and configuration (GiGPO reference harness, Qwen2.5-1.5B-Instruct, 150 steps). These results come from an earlier version of our code base, so their absolute numbers are not directly comparable to the paper's tables.

  • ALFWorld: Free-form credit reaches a peak validation success of 0.930, versus 0.898 for GiGPO. Across seeds, however, it ranges from 0.859 to 0.938, so whether it beats GiGPO depends on the seed. On ALFWorld, the annotator scoring progress by itself is therefore competitive at its best, but unstable.
  • WebShop: Free-form credit fails to train. Task score falls from 0.253 to 0.085 and success drops to 0.000, versus 0.708 and 0.504 for GiGPO (paired difference −0.455 task score, −0.442 success, still declining when the run was stopped).
  • Search-R1: The same free-form judge collapses to 0.000 success by step 60.

The WebShop failure has an identifiable cause. WebShop grades partial attribute matches on [0, 1] but counts success only for an exact match. Most unsuccessful rollouts are therefore graded near-misses with no single decisive error. Free-form credit then rewards almost the entire plausible browsing trajectory. Committing to a purchase risks the binary success cliff, while browsing keeps earning credit. As a result, episode length rose to the step cap (12.4 to 14.5) and success went to zero. ALFWorld failures usually do have a decisive step, which is why the same rule works better there.

DARS is also an LLM assigning credit. The graph constrains where that credit can land by specifying what counts as progress, so that plausible-looking but unproductive actions cannot satisfy it. The comparison above shows that this constraint is what makes the annotator's credit usable in WebShop and Search-R1. We will add this comparison to the appendix.

Q4. Dependence on outcome and reference visibility, and what must be hand-designed

Outcome and reference visibility. The annotator sees the outcome and reference answer only while computing training rewards. The policy never sees them, and they are not used at evaluation time. This is the same information that the outcome reward already uses.

What must be hand-designed. See W3: a predicate vocabulary, dependency rules, and an annotator prompt per domain, which LLMs can generate automatically. No per-trajectory annotation is needed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.