VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning

Pengcheng Li; Zhengyang Zhang; Dongxu Zhang; Sui Huang; Shaohua Ma

cs.LGAug 28, 2026

VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning

Authors: Pengcheng Li, Zhengyang Zhang, Dongxu Zhang, Sui Huang, Shaohua Ma

Organizations: Tsinghua University · Xi’an Jiaotong University · Jiaxing Nanhu University

Abstract

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.

Closed-Source LLMs
Method	ALFWorld							WebShop
	Pick	Look	Clean	Heat	Cool	Pick2	All	Score	Succ.
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

\tau

-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
$\tau$ Retail	9.7	100.0	99.2	100.0	86.5	14.3
$\tau$ 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\times 10^{-6}$	$1\times 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.

Field	Meaning	Examples
atom_id	Stable identifier for the checked fact.	webshop.price_under_budget , tau.confirmation_obtained .
predicate	Executable function mapping trajectory state/evidence to $\{\mathrm{sat},\mathrm{unsat},\mathrm{unk},\mathrm{viol}\}$ .	Product price comparison; database-field equality; ALFWorld object-state predicate.
evaluable_when	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 $M_{x}$ and $\Phi_{x}$ to attach witnesses.	Product id, selected option, object location, database record field.
score_role / audit_source	Effect on $F_{x}$ 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.	Search results; product page metadata; option-click logs; selected product state; final buy action.	Change price; remove required attribute; change selected option; replace purchased product id.
$\tau$ -bench	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 $\rho_{i}$	$0.5\,s_{R}\|A_{i}^{\mathrm{base}}\|$
Tie margin $\epsilon_{q}$ for $q_{i}$	$10^{-6}$ base-advantage units
Conformance tolerance $\eta_{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
$\tau$ 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
$\tau$ 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;

\tau

-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.

Step	Observation / action	Evidence used by adapter	Verifier atom status after action	Proof edge	Sign
0	Initial kitchen contains countertop 1 , countertop 2 , fridge 1 , and microwave 1 .	Receptacle and heating-device candidates are visible.	receptacle_candidate=seen ; heat_tool=seen ; target object unknown.	evidence reveal	$0$
1–2	go to fridge 1 ; open fridge 1 .	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.	wrong_object_held=viol ; target egg atoms remain unsatisfied.	The wrong take action receives negative violation credit if it enters the failure core.	The model is not told that all early navigation was wrong; the blame is attached to the first wrong-object write.
Moves egg 1 to the countertop before heating.	target_object_held=sat , but transformation_heated=unsat at final placement.	move egg 1 to countertop 1 receives negative premature-commit credit; take egg 1 may still receive positive object credit.	A partially useful failed trajectory is decomposed into a correct object choice and an incorrect final commitment.
Heats the egg, then places it in the sinkbasin.	transformation_heated=sat ; final_receptacle=viol .	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.	Search query contains color, size, budget, product type, fit, and sleeve constraints.	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.	Keyboard replacement valid; fallback condition satisfied.	evidence reveal	$+$
4	Check thermostat product 4896585277 .	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:

\tau

-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.	confirmation_obtained=unsat ; policy_precondition=viol .	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:

\tau

-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; gift_card_6276644 has$ 113 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:

\tau

-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

Fine-Grained Credit Assignment studies how to attribute outcomes to the steps, agents, or components that caused them, enabling more targeted learning.

See all 41 papers

Teach the Magnitude, Not the Direction: Verifier-Bounded Credit Assignment for Multi-Turn Multi-step LLM Agents
Aug 13, 2026Zechuan Wang, Siyuan Lu, Hongxuan Zhang +3Token-Level Credit Assignment Step-Level Credit Assignment in RL
Zhejiang University · AWorld Team, Inclusion AI · Shanghai Innovation Institute +2
TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
Jul 15, 2026Leitian Tao, Baolin Peng, Wenlin Yao +5Credit Assignment in RL Step-Level Credit Assignment in RL
University of Wisconsin–Madison · Microsoft Research
Verifiable Process Rewards for Agentic Reasoning
May 11, 2026Huining Yuan, Zelai Xu, Huaijie Wang +6Process Reward Models Credit Assignment in RL
Tsinghua University

Aug 13, 2026J/K move · Enter open · S save

Teach the Magnitude, Not the Direction: Verifier-Bounded Credit Assignment for Multi-Turn Multi-step LLM Agents

Zechuan Wang, Siyuan Lu, Hongxuan Zhang, Linjian Mo+2

Zhejiang University · AWorld Team, Inclusion AI · Shanghai Innovation Institute+2

Token-Level Credit Assignment Step-Level Credit Assignment in RL Reinforcement Learning with Verifiable Rewards Step-Level Credit Assignment On-Policy Distillation RL for Tool Use

Open paper AskPDF arXiv

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

\textbf{CrEST}

, a hierarchical credit assignment framework that retains RL's verifier-bounded ceiling while incorporating dense token-level signals from a privileged self-teacher.

\textbf{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

\textbf{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.

Abstract

Fine-Grained Credit Assignment

Explore similar work

Teach the Magnitude, Not the Direction: Verifier-Bounded Credit Assignment for Multi-Turn Multi-step LLM Agents

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents

Verifiable Process Rewards for Agentic Reasoning