Fine-grained credit assignment is a central challenge in reinforcement learning for long horizon LLM agents. Standard objectives often train from programmatically verifiable terminal rewards by broadcasting each sparse outcome to every action in a trajectory. Existing methods typically seek finer credit from the rollout side, constructing auxiliary trajectory signals or additional comparisons to estimate action importance. Although useful, these approaches still treat the verifier that judged success as a scalar reward, discarding its internal task structure. Our key insight is that many verifiable tasks already encode the relevant checks inside their terminal verifier. We propose VICT (VerifierInstrumented Credit Tracing), a training-time interface that exposes executable or evidence backed atoms and traces them back to actions through dependency-valid proof edges. VICT redistributes group-relative advantage only along those edges, shifting credit assignment from rollout-side inference to verifierside tracing. It preserves the original terminal reward, abstains when evidence is incomplete or ambiguous, and changes only the training-time advantage tensor, requiring no learned critic, process labels, branch rollouts, or inference-time verifier access. On ALFWorld and WebShop, VICT improves substantially over outcome-only training and achieves strong performance alongside recent fine-grained credit methods; ablations rule out dense atom rewards, final-commit credit, temporal proximity, and sparsity as sufficient explanations.
Figures & tables
Figure 1: Overview of verifier-instrumented credit tracing. A long-horizon flight-booking trajectory is checked by verifier atoms such as booking completion, budget satisfaction, and route correctness; VICT traces evidence from concrete actions to these atoms and assigns sparse verifier-backed credit only to supported steps.
Figure 2: VICT pipeline. The verifier is first exposed as atoms, dependencies, evidence extractors, and commit predicates; trajectories are then converted into proof graphs that link actions to verifier atoms. Dependency cores estimate which atoms matter to success or failure, and the final step redistributes normalized credit only to proof-supported actions.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Closed-Source LLMs
GPT-4o
75.3
60.8
31.2
56.7
21.6
49.8
48.0
31.8
23.7
Gemini-2.5-Pro
92.8
63.3
62.1
69.0
26.6
58.7
60.3
42.5
35.9
Qwen2.5-1.5B-Instruct
Base
5.9
5.5
3.3
9.7
4.2
0.0
4.1
23.1
5.2
Table 1: Main performance on ALFWorld and WebShop. ALFWorld reports task-wise and average success rate (%), while WebShop reports normalized score and strict success rate (%). Subscripts denote standard deviations where available.
Setting
ALFWorld All
WebShop strict
VICT alone
93.7 ±0.8
83.6 ±0.9
GiGPO alone / + VICT
90.8 ±1.3 / 94.6 ±0.7
72.8 ±3.2 / 84.7 ±1.1
HCAPO alone / + VICT
91.4 ±2.3 / 94.3 ±0.9
–
SALT alone / + VICT
–
76.2 ±3.4 / 85.2 ±0.8
Table 2: Compatibility with rollout-side credit methods using Qwen2.5-7B. Each cell reports the method alone / with VICT ; comparisons are descriptive.
Method
Retail
Airline
Base
35.7
23.2
GRPO
39.1
36.0
DAPO
45.2
20.0
Dr.GRPO
47.0
28.0
AWPO
43.5
30.0
Fission-GRPO
51.3
40.0
Table 3: Supplemental service-agent evidence on τ -bench. Pass@1 (%) is measured with Qwen3-8B under simulated-user interaction; the VICT row reports mean and standard deviation over three seeds.
Figure 3: Core evidence with Qwen2.5-7B. (a) Final score versus normalized validation AUC over the same 300 updates; arrows connect outcome-only GRPO to VICT , and upper right is better. “Best non- VICT ” is HCAPO for ALFWorld and SALT for WebShop. (b) Point decrease from full VICT for each ablation or negative control. Exact mean and standard deviation values are in Table 4 and Appendix Table 8 .
Variant
ALFWorld
WebShop
Outcome-only GRPO
77.6 ±5.2
66.1 ±3.7
Dense atom reward
88.6 ±1.7
78.2 ±1.5
Commit-only verifier credit
86.1 ±2.2
75.4 ±1.8
Temporal-nearest atom credit
88.0 ±2.0
77.1 ±1.7
Randomized proof-edge placebo
79.4 ±3.9
67.3 ±3.4
w/o dependency core
90.4 ±1.5
80.1 ±1.2
Table 4: Ablation and negative-control results with Qwen2.5-7B. Values are mean with standard deviation over three seeds.
Domain
Atoms
Recon.
Mutation
Elig. pass
Proof cov.
Abstain
ALFWorld
5.8
100.0
99.6
100.0
92.4
8.1
WebShop
6.3
99.8
98.9
100.0
88.7
11.6
τ Retail
9.7
100.0
99.2
100.0
86.5
14.3
τ Airline
11.2
99.7
98.6
100.0
84.9
15.8
Table 5: Verifier-interface diagnostics before policy updates. Reconstruction and mutation conformance test agreement with the original verifier; eligibility-invariant pass rate, coverage, and abstention audit whether verifier facts can be safely attached to actions.
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
ALFWorld
WebShop
Backbones
Qwen2.5-1.5B/7B
Qwen2.5-1.5B/7B
Group size
8
8
Max episode steps
50
15
Max prompt length
2048
4096
Max response length
512
512
Actor learning rate
1×10−6
1×10−6
Appendix
Table 6: VICT training configuration for ALFWorld and WebShop.
Benchmark
Task groups/update
Eval tasks
Updates
Rollouts/update
Train rollouts/seed
Checkpoint rule
ALFWorld
16
134
300
128
38.4k
last-five average
WebShop
16
500
300
128
38.4k
last-five average
Appendix
Table 7: Training scale used for VICT on ALFWorld and WebShop. Each task group contains 8 rollouts.
Method
ALF final
ALF AUC
Web final
Web AUC
GRPO
77.6 ±5.2
58.4 ±3.8
66.1 ±3.7
52.7 ±2.9
Best non- VICT
91.4 ±2.3
71.8 ±2.1
76.2 ±3.4
61.4 ±2.6
Dense atom reward
88.6 ±1.7
72.6 ±1.9
78.2 ±1.5
64.9 ±1.8
VICT
93.7 ±0.8
78.9 ±1.4
83.6 ±0.9
70.8 ±1.2
Appendix
Table 8: Sample-efficiency summary over 300 training updates. AUC is computed from validation success curves and normalized to the same percentage scale as final performance. The best non- VICT row uses HCAPO for ALFWorld and SALT for WebShop.
Earliest point at which the atom can be safely evaluated.
Online state, evidence revealed, commit action, or terminal only.
dependencies
Parent atoms or clauses required for valid counterfactual edits.
“field update allowed” depends on “confirmation obtained”.
state_vars
Variables used by Mx and Φx to attach witnesses.
Product id, selected option, object location, database record field.
score_role / audit_source
Effect on Fx and evidence saved for audit.
Hard conjunction, penalty, prerequisite; state diff, observation span, API log.
Appendix
Table 9: Verifier atom schema used by VICT .
Figure 4: Adapter engineering cost and training-time overhead across domains. Marker size encodes adapter lines of code, and labels report atom coverage.
Domain
Atom families
Witness sources
Mutation tests
ALFWorld
Target object identity; object held; transformation; receptacle found; final placement; second-object requirement; wrong-object or premature-placement violation.
Simulator state diffs; inventory changes; temperature or cleanliness transitions; receptacle transitions; final placement actions.
Move final object to wrong receptacle; remove transformation flag; swap target object; drop second object.
WebShop
Product identity; category match; hard attribute match; option selected; price under budget; purchase committed; wrong-purchase violation.
Target record identified; required information collected; confirmation obtained; policy precondition; target field updated; forbidden field unchanged; final response consistent.
API call logs; database diffs; user turns; policy-rule checks; final assistant response.
Delete confirmation; alter target field; add extra database write; change policy precondition.
Appendix
Table 10: Example VICT instantiations.
Hyperparameter
Default
Core budget B
8 atom additions
Core threshold ρi
0.5sR∣Aibase∣
Tie margin ϵq for qi
10−6 base-advantage units
Conformance tolerance ηx
0 for exact verifiers
Direct-write / commit / violation weight
1.0
Evidence-path total weight
1.0 split over support path
Appendix
Table 11: Default values for the verifier correction.
Domain
Trigger
Sparsity
NZ acts/traj
Core size
Budget hit
Abstain
Top abstention reason
ALFWorld
61.8 ±2.1 %
18.6 ±1.0 %
4.7 ±0.4
2.9 ±0.2
1.4 ±0.3 %
8.1 ±0.6 %
terminal-only fact
WebShop
57.2 ±1.8 %
15.3 ±0.9 %
2.2 ±0.2
3.4 ±0.3
2.1 ±0.4 %
11.6 ±0.8 %
ambiguous product evidence
τ Retail
52.9 ±2.4 %
12.8 ±1.1 %
3.1 ±0.3
4.6 ±0.4
4.8 ±0.6 %
14.3 ±1.0 %
missing confirmation witness
τ Airline
49.5 ±2.6 %
11.7 ±1.0 %
3.4 ±0.4
5.1 ±0.5
5.6 ±0.7 %
15.8 ±1.1 %
unresolved policy precondition
Appendix
Table 12: Credit behavior diagnostics computed on final training rollouts before policy update. ALFWorld/WebShop values are averaged over three training seeds; τ -bench values are averaged over final service-validation rollout batches because that setting is treated as supplemental validation. Trigger is the fraction of rollouts with at least one non-zero verifier correction; sparsity is the fraction of actions with non-zero verifier correction.
Fridge contains bowl, pan, plate, and potato, but no egg.
No target-object atom is satisfied; the negative observation is logged but not a success core atom.
reveal, no core
0
3–4
go to countertop 2 ; observation lists egg 3 , egg 2 , and egg 1 .
The target object is now grounded to visible egg instances.
target_object_visible=sat .
evidence reveal
+
5
take egg 1 from countertop 2 .
Inventory changes from no target object to holding egg 1 .
target_object_held=sat .
direct write
+
6–7
go to microwave 1 ; open microwave 1 .
The heating device is reachable and usable.
Dependency for heated_egg is prepared, but no transformation has happened yet.
support path
0/+
8
heat egg 1 with microwave 1 .
Simulator state marks egg 1 as heated.
transformation_heated=sat .
direct write
+
Appendix
Table 13: ALFWorld proof trace for an illustrative Heat task. VICT credits the actions that write target identity, heating, and placement atoms, while search actions only receive credit when they lie on a proof-supported evidence path.
Near miss
Verifier diagnosis
Action receiving correction
Why this is different from outcome-only RL
Takes potato 1 from the fridge after failing to find an egg.
The wrong move or put action receives negative placement credit.
The heating action remains supported even though the terminal reward is zero.
Loops through look and repeated container openings after the egg is held.
No additional atom changes; no reveal edge adds new verifier evidence.
Repeated no-op actions receive no verifier correction.
VICT does not create dense progress rewards for merely longer successful-looking histories.
Appendix
Table 14: ALFWorld failure contrasts. The dependency core allows useful predecessor actions and harmful commit actions to receive different signs inside the same failed rollout.
Step
Action
Observation / evidence
Verifier atom status
Proof edge
Sign
1
Search with color b-blue , size xx-large , budget 0-40 , product type, fit, and sleeve slots.
Query covers several hard constraints, but no product atom is yet evaluable.
reveal path
+
2
click[b09q67h373]
Result title: “JSPOYOU 2022 Newly T-Shirt… Short Sleeve Tees…”; price 1.99–8.99 .
price_under_budget=sat ; product_type_tuxedo=unsat/unk ; material and elastic-waist evidence absent.
evidence reveal
+/−
3
click[b-blue]
Product page exposes color options including b-blue .
color_option_selected=sat .
direct write
+
4
click[xx-large]
Product page exposes size options including xx-large .
size_option_selected=sat .
direct write
+
5
click[buy now]
Final purchase commits the current product, whose page lacks the tuxedo-shirt, polyester-cotton, elastic-waist, and requested-fit evidence.
purchase_committed=sat ; hard product atoms missing.
commit violation
−
Appendix
Table 15: WebShop proof trace for an illustrative failed purchase. Option-selection actions can receive positive correction, but the final purchase receives negative commit credit because dependency-core atoms for product type and hard attributes remain unsatisfied.
Continuation
Satisfied atoms
Missing or violated atoms
VICT effect
Select b-blue and xx-large , then buy B09Q67H373 .
Price, color option, and size option are supported by page evidence.
Product category, material, elastic waist, and requested fit are not supported.
Positive option writes are preserved, but the buy now action is penalized as a wrong purchase.
Click a cheap, semantically clothing-related result without checking product details.
Search result may reveal a low price and some lexical overlap.
Hard attributes are unknown, so the core cannot certify purchase correctness.
Evidence is insufficient; VICT either abstains or credits only the evidence-reveal edge, not a commit.
Return to search after detecting missing product-type evidence.
The failed candidate contributes negative evidence for the current product.
No terminal purchase is committed.
The click can be treated as useful evidence gathering rather than as a failed purchase.
Buy after all hard product atoms and required options are observed.
Product type, hard attributes, options, budget, and commit are all satisfied.
No missing hard atom remains in the dependency core.
Evidence-revealing clicks, option writes, and the final commit all receive positive correction.
Appendix
Table 16: WebShop continuation contrasts. The decisive distinction is whether the final buy action commits a product whose hard verifier atoms are all supported.
Step
Action / turn
Evidence source
Verifier atom status
Proof edge
Sign
1
Name+zip authentication via find_user_id_by_name_zip .
Tool returns the matching benchmark user record.
identity_authenticated=sat .
evidence reveal
+
2
Retrieve order #W2378156 with get_order_details .
Order status is delivered ; target item ids and original payment method are visible.
delivered_order=sat ; target items identified.
evidence reveal
+
3
Check keyboard product 1656367028 .
Keyboard variants show 9025753381 is exact but unavailable; 7706410293 is clicky, no-backlight, full-size, and available.
Thermostat variant 7747408585 is Google Assistant compatible, black, and available.
Thermostat replacement valid.
evidence reveal
+
5
Assistant lists both exchanges and obtains explicit user “yes”.
Retail policy requires confirmation before any database-changing exchange.
confirmation_obtained=sat .
user-turn reveal
+
6
Call the exchange API with order #W2378156 , old ids 1151293680/4983901480 , new ids 7706410293/7747408585 , and credit_card_9513926 .
Database changes status to exchange requested and records exact old/new item lists.
exchange_status=sat ; no_extra_write=sat ; all item atoms satisfied.
direct write + commit
+
Appendix
Table 17: τ -bench Retail proof trace for an illustrative multi-item exchange task. The product-detail calls reveal the unavailable exact keyboard variant, the valid fallback, and the valid thermostat replacement.
Failure continuation
Failed atom
Credited or penalized action
Training signal
Calls the exchange tool before obtaining explicit user confirmation.
The mutating API call receives negative violation credit.
Learn to ask for confirmation before database writes.
Chooses exact keyboard item 9025753381 .
replacement_available=viol ; tool would reject unavailable item.
The product-detail evidence is useful, but the exchange call is penalized.
Learn that an unavailable exact variant triggers the fallback branch.
Chooses thermostat item 4953074738 .
thermostat_compatibility=viol because it is Amazon Alexa, not Google Assistant.
The wrong new-item id in the exchange call receives negative commit credit.
Learn to bind replacement ids to checked option atoms.
Exchanges only the thermostat and omits the keyboard in this task variant.
keyboard_exchange_included=unsat .
The final exchange call receives omission credit for the missing item id.
Learn to batch all requested delivered-order exchanges into one mutating call.
Appendix
Table 18: τ -bench Retail failure contrasts. The verifier core localizes whether the error is a policy violation, an unavailable item, a wrong replacement option, or an incomplete database update.
Step
Action / evidence
Database or search fact
Verifier atom status
Proof edge
Sign
1
Retrieve user and reservation details.
OBUT9V : IAH–DEN round trip, economy; outbound is HAT078 / HAT118 on May 27 and return is HAT084 / HAT266 on May 28.
Target reservation identified; economy booking is modifiable.
evidence reveal
+
2
Search return flights from DEN to IAH on May 27.
The task record specifies HAT290 DEN–LAS 14:00–16:00 and HAT175 LAS–IAH 17:00–20:00.
same_day_return=sat ; return_route_selected=sat .
evidence reveal
+
3
Compare payment methods.
gift_card_7480005 has 6;giftcard6276644has113 and is the smallest sufficient gift card.
smallest_usable_gift_card=sat .
evidence reveal
+
4
Obtain explicit user confirmation for flight and baggage changes.
Airline policy requires confirmation before updating flights or baggage.
confirmation_obtained=sat .
user-turn reveal
+
5
Flight-update API call for OBUT9V : economy itinerary HAT078/HAT118/HAT290/HAT175 , paid with gift_card_6276644 .
The whole new reservation is written, retaining outbound segments and replacing the return with same-day flights.
flight_update=sat ; outbound preserved.
direct write + commit
+
6
Baggage-update API call for OBUT9V : total=2 , nonfree=0 , payment gift_card_6276644 .
Total checked bags becomes 2; silver economy allowance keeps nonfree bags at 0.
baggage_update=sat ; free allowance respected.
direct write + commit
+
Appendix
Table 19: τ -bench Airline proof trace for an illustrative reservation-modification task. The proof core combines itinerary search, payment sufficiency, user confirmation, and two database writes.
Fine-Grained Credit Assignment studies how to attribute outcomes to the steps, agents, or components that caused them, enabling more targeted learning.
Reinforcement learning with verifiable rewards (RLVR) offers a verifier-bounded performance ceiling for training multi-turn tool-use agents, yet its trajectory-level credit assignment conflates heterogeneous per-turn outcomes into a single reward signal. On-policy distillation provides dense per-token supervision but is either teacher-bounded or prone to gradient concentration collapse. We introduce CrEST, a hierarchical credit assignment framework that retains RL's verifier-bounded ceiling while incorporating dense token-level signals from a privileged self-teacher. CrEST resolves credit at two levels: turn-segmented verified advantages address inter-turn dilution, while entropy-gated self-teacher modulation refines intra-turn token contributions. Experiments on BFCL V3 and WildToolBench show that CrEST consistently outperforms both RL and distillation baselines across two model scales, with the largest gains on long-trajectory and strict session-level metrics. Our work demonstrates that the teacher's role in policy optimization can be reduced from determining update directions to modulating update magnitudes, unlocking dense credit assignment without sacrificing the verifier-bounded ceiling.
Zechuan Wang, Siyuan Lu, Hongxuan Zhang +3
Zhejiang University · AWorld Team, Inclusion AI · Shanghai Innovation Institute +2
Multi-turn agents solve complex tasks through extended sequences of tool interactions before producing a final answer, making credit assignment a fundamental challenge during post-training. Outcome rewards provide reliable supervision for short-horizon reasoning, but become sparse and high-variance as trajectories grow to tens or hundreds of tool calls. They can also be misleading: a failed rollout may contain many useful actions that move the agent closer to the goal, yet outcome-only training assigns them the same negative advantage as the eventual mistake. We propose TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for agentic reinforcement learning. TRACE represents rollouts as state transitions at tool-call boundaries, obtains gold-answer log-probabilities from a frozen reference model, transforms them into log-ratio state values, and derives per-action rewards as Temporal-Difference changes in those values. This requires no additional critic or process-label training, and its one-step log-ratio TD component telescopes across redundant tool calls. On long-horizon complex search, TRACE substantially improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, or training on live-web data. On the closed-web BrowseComp-Plus benchmark, it raises Qwen3-4B from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6. The learned search behavior also transfers to open-web benchmarks, and the learning curves show earlier improvement and faster convergence during RL training.
Leitian Tao, Baolin Peng, Wenlin Yao +5
University of Wisconsin–Madison · Microsoft Research
Reinforcement learning from verifiable rewards (RLVR) has improved the reasoning capabilities of large language models (LLMs), yet existing approaches predominantly rely on sparse outcome-level feedback, posing a substantial credit-assignment challenge in long-horizon agentic tasks. In this work, we study structured agentic reasoning problems that admit symbolic or algorithmic task-solving oracles. We propose Verifiable Process Rewards (VPR), a training framework that repurposes such task oracles as action-level process verifiers, providing dense rewards for intermediate actions and enabling fine-grained credit assignment. We instantiate VPR in three distinct settings: a search-based oracle for Sokoban, a constraint-based oracle for Sudoku, and a posterior-based oracle for Minesweeper. To optimize policies with these rewards, we introduce oracle-guided state-group rollout and locally normalized optimization. Empirically, VPR-trained Qwen3-4B outperforms outcome-reward GRPO and VinePPO across all three training environments. When jointly trained on math data and all three game environments, VPR achieves the highest average general-reasoning performance and strongest agentic results among the compared training configurations. To further assess its applicability to more general agentic tool-use settings, we apply VPR-style action-level supervision to τ2-bench using an expert LLM as a reference policy and observe improved performance over outcome-reward GRPO on held-out tasks. Together, these results position VPR as a promising approach for leveraging reliable task oracles to improve agentic reasoning, while highlighting its dependence on the availability and reliability of task oracles and the challenge of extending intermediate verification to less structured, open-ended environments.