Source-linked AI summary
VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning
Pengcheng Li, Zhengyang Zhang, Dongxu Zhang, Sui Huang, Shaohua Ma
TL;DR
Long-horizon LLM-agent RL struggles because sparse terminal outcomes are broadcast across actions while verifier structure is discarded. VICT instruments verifier atoms and traces advantage only through dependency-valid proof edges, preserving the outcome anchor. Across ALFWorld and WebShop, it improves substantially over outcome-only training and remains competitive with recent fine-grained methods, while abstaining when reliable proof is unavailable.
Problem
Sparse terminal rewards are often broadcast to every action, obscuring why a long-horizon trajectory succeeded or failed despite structure inside the terminal verifier.
Method
VICT instruments terminal verifiers into executable or evidence-backed atoms and redistributes group-relative advantage only through verified, dependency-valid action-to-atom proof edges.
Results
On ALFWorld and WebShop, VICT improves substantially over GRPO and remains competitive with recent fine-grained methods.
Takeaways & Limitations
Verifier-backed tracing shifts fine-grained credit assignment from rollout-side inference toward auditable structure already present in terminal verifiers.
Takeaways & Limitations
VICT is limited to tasks with instrumentable verifiers and observable relevant state changes, evidence, commits, or violations; it is less direct for holistic learned judges or hidden verifier state.
Abstract
from arXiv · showhide
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.
1 Introduction
Long-horizon agent RL often broadcasts sparse terminal outcomes across all actions, obscuring which decisions determined success. VICT instead instruments verifier structure and traces sparse credit to supported actions through auditable evidence and proof edges.
- Motivation: Long-horizon agents may receive the same sparse terminal advantage for every action, although only a few decisions determine success or failure.Terminal outcomes can erase why a trajectory succeeded or failed.
- Motivation: Many verifiable tasks already encode concrete checks inside programmatic terminal verifiers, but standard RL interfaces expose only the final number.These checks can include required state changes, forbidden operations, observed evidence, and final commitments.
- Method: VICT turns instrumentable terminal verifiers into sparse, auditable action-level credit by linking executable or evidence-backed atoms to observable trajectory evidence.The approach shifts credit construction toward exposing existing verifier structure rather than inventing intermediate rewards.
- Evaluation: On ALFWorld and WebShop, VICT improves substantially over GRPO and remains competitive with recent fine-grained methods.The paper also reports suggestive τ-bench validation and audits reconstruction, mutation conformance, eligibility, coverage, sparsity, abstention, core-size, and cost.
- Method: VICT introduces dependency-core attribution and proof-edge-constrained advantage correction with an explicit eligibility invariant.Credit is assigned only to actions supported by dependency-valid verifier evidence.
2 Related Work
Prior work refines long-horizon credit through critic-free normalization, alternative comparison units, rollout branching, reward decomposition, process supervision, and criteria-based evaluation. VICT complements these approaches by constraining verifier decomposition to executable or evidence-grounded atoms connected to actions through proof edges.
- Policy-gradient RL: RLOO and GRPO avoid learned critics by normalizing rewards within rollout groups, but still leave terminal-outcome assignment across individual actions unresolved.This critic-free design is attractive for long-context agent trajectories.
- Fine-grained credit: GiGPO, SALT, ProxMO, and HCAPO refine credit by comparing actions through repeated states, trajectory graphs, semantic proximity, or hindsight reasoning.These methods change the comparison unit used to estimate action utility.
- Rollout-based methods: Tree- and branch-based methods change rollout distributions by sampling continuations from shared prefixes or uncertain decision points.They expose local preferences when useful comparisons can be created from states, prefixes, branches, or prompted hindsight.
- Structured rewards: Return redistribution, potential-based shaping, reward machines, and reward decomposition expose delayed or composite rewards in more informative forms.Process supervision and PRMs provide step-level feedback but typically require labels, learned reward models, or search-generated supervision.
- Verifier-based credit: VICT treats verifier decomposition as constrained instrumentation: atoms must be executable or evidence-backed, reconstruct the terminal verifier, and attach to actions through proof edges.This addresses reliability concerns for natural-language criteria that are not executable or evidence-grounded.
3 Method
VICT instruments terminal verifiers into executable or evidence-backed atoms, dependency-valid cores, and action-to-atom proof graphs, then adds verifier-derived credit only to proof-supported actions while retaining the outcome signal. It abstains when conformance, core search, or proof support fails and changes only the training-time advantage tensor.
- Verifier-Instrumented Interface: VICT represents terminal verifiers with executable atoms, score aggregation, dependency rules, evidence bindings, extractors, and commit predicates.Atom statuses include sat, unsat, unk, and viol; deterministic dependency closure is required for credit use.
- Verifier-Instrumented Interface: Conforming verifier interfaces expose checked facts and dependencies without introducing policy-visible subgoals or new preferences.Exact verifiers use zero tolerance, while graded-verifier tolerance is fixed before training; nonconforming atoms are excluded.
- Credit Trace and Core Attribution: VICT constructs action-to-atom proof graphs only when logged history and extracted evidence certify that an action wrote, revealed, committed, or violated an atom.Terminal-only atoms without a reliable writer or commit action create no edge, so unsupported attribution is treated as missing information.
- Credit Trace and Core Attribution: Dependency-closed cores identify atoms whose verifier-assignment removal or repair changes the score, with leave-one-out marginals assigned only inside valid cores.Positive-sign rollouts search success cores, negative-sign rollouts search correction cores, and VICT abstains when no core meets the threshold or uncertainty is too high.
- Proof-Edge-Constrained Advantage Optimization: Eligible core signals are redistributed through proof edges using witness weights, while atoms without witness links receive no verifier correction.The default gives direct verifier witnesses weight 1 and splits evidence-path credit uniformly over the support path.
- Proof-Edge-Constrained Advantage Optimization: The final advantage preserves the outcome signal and adds a clipped verifier-derived correction, falling back to the base advantage when eligibility conditions fail.VICT keeps group-based optimization, trains no critic, requires no process labels or branch rollouts, and exposes no verifier atoms at inference time.
4 Experiments
Experiments evaluate VICT across verifiable agent benchmarks, compare it with outcome-only and fine-grained credit methods, and test whether its gains depend on verifier-grounded proof structure. Results show strong improvements, compatibility with rollout-side credit, and intentional abstention when action-level evidence is unsupported.
- 4.1 Setup: VICT is evaluated on ALFWorld, WebShop, and τ-bench against outcome-level, fine-grained, and protocol-specific baselines.ALFWorld reports task-wise and average success, WebShop reports normalized score and strict success, and τ-bench reports Retail/Airline pass@1.
- 4.2 Main Results on ALFWorld and WebShop: With Qwen2.5-1.5B, VICT improves over GRPO by 18.2 points on ALFWorld average success and 24.9 points on WebShop strict success.
- 4.2 Main Results on ALFWorld and WebShop: 93.7 average success and 83.6 WebShop strict success are achieved with Qwen2.5-7B, gains of 16.1 and 17.5 points over GRPO.
- 4.2 Main Results on ALFWorld and WebShop: VICT’s gains concentrate on verifier-sensitive tasks and coincide with higher validation AUC under the same 300-update budget.Improvements are reported for ALFWorld Look, Cool, and Pick2, and for WebShop final purchase correctness.
- 4.3 τ-bench: Under the Fission-GRPO τ-bench protocol, VICT reaches 56.6/45.1 Retail/Airline pass@1 versus 51.3/40.0 for Fission-GRPO.The paper treats this comparison as supplemental because it uses a different backbone and protocol.
- 4.4 Ablations and Diagnostics: Verifier diagnostics use reconstruction, mutation conformance, eligibility, coverage, abstention, sparsity, core-size, and runtime measures to gate safe credit assignment.Eligibility-invariant pass rate is 100%, while lower proof coverage reflects intentional abstention on unsupported terminal-only facts.
- 4.5 Qualitative Behavior: Across benchmarks, learned behavior shifts toward delaying commitments, preserving intermediate achievements, and avoiding unsupported or irrelevant state changes.
5 Conclusion
The paper concludes that VICT provides auditable, sparse action-level credit for long-horizon agents using instrumentable programmatic verifiers. Across embodied, web, and tool-use settings, its improvements coexist with verifier-interface safety checks and abstention on unsupported evidence.
- VICT assigns sparse action-level advantage corrections through dependency-valid proof edges while preserving the original outcome reward.
- The method requires no critic or process labels, and its non-zero corrections remain auditable.
- Across embodied, web, and tool-use settings, experiments and diagnostics show improved fine-grained training alongside reconstruction, mutation, eligibility-invariant, sparsity, and abstention checks.
Limitations
VICT applies only when verifiers expose auditable atoms and relevant evidence in trajectory logs. Its engineering, dependency, and credit-interpretation constraints can reduce coverage and recall.
- VICT requires executable or evidence-backed verifier atoms and observable relevant state changes, evidence, commits, or violations.
- Holistic learned judges, hidden verifier state, and tasks dominated by exploration failure are less direct settings for VICT.
- Verifier instrumentation can require domain knowledge and maintenance, especially for branch instrumentation and deterministic adapters.
- Large atom sets or ambiguous dependencies can produce larger local cores or abstention, reducing credit recall while preserving proof-edge validity.
- Proof edges establish verifier-defined eligibility rather than causal necessity, so redundant or correlated support may receive credit.
- VICT changes only the training-time advantage tensor and therefore still requires strong exploration, stable optimization, careful verifier design, and matched-budget diagnostics.
A Training Algorithm Details
VICT inserts verifier tracing into the base group-optimization loop before policy updates, using auditable atoms, proof graphs, and dependency-valid cores to modify advantages.
- VICT follows the base rollout and policy-update loop but inserts verifier tracing before the clipped policy-gradient objective.
- Verifier atoms and proof logs remain outside the policy prompt and are not exposed at inference time.
- The procedure samples rollout groups, evaluates terminal rewards, computes base advantages, and builds or retrieves a verifier interface.
- It evaluates temporal atom traces, runs reconstruction and mutation conformance, masks failed atom families, and constructs proof graphs from trajectory witnesses.
- When no core reaches the threshold, corrections are zero; otherwise, leave-one-out marginals are group-normalized and redistributed to proof-bearing actions.
- The updated advantage is passed to the base clipped policy-gradient update with KL regularization, while non-zero corrections are logged with audit fields.
- Evidence extraction uses deterministic adapters over logs, state differences, observations, and verifier metadata, with results reported over three random seeds.
B Additional Experimental Results
The reported variants use Qwen2.5-7B-Instruct and three random seeds.
- All variants use Qwen2.5-7B-Instruct and three seeds.
- The experimental comparisons therefore share the stated model family and three-seed reporting setup.
- Results in this section are based on the stated Qwen2.5-7B-Instruct configuration.
B.2 Sample-Efficiency Summary
The sample-efficiency analysis summarizes final scores and normalized validation AUC over 300 updates, while reporting training scale and supplemental τ-bench context separately.
- B.2 Sample-Efficiency Summary: Final scores and normalized validation AUC are summarized over the same 300 training updates.
- B.2 Sample-Efficiency Summary: Each ALFWorld and WebShop task group contains 8 rollouts, and training scale is reported by task groups and rollouts per update.
- B.2 Sample-Efficiency Summary: AUC is computed from validation success curves and normalized to the same percentage scale as final performance.
- B.2 Sample-Efficiency Summary: The best non-VICT comparison uses HCAPO for ALFWorld and SALT for WebShop.
- B.2 Sample-Efficiency Summary: Supplemental τ-bench evidence uses Qwen3-8B under simulated-user interaction and a separate protocol from the primary experiments.
- B.2 Sample-Efficiency Summary: Atom decomposition uses executable predicates as the source of truth, with representative families relying on simulator diffs, product evidence, purchase commits, API logs, database diffs, user turns, and policy checks.
D Attribution, Core Search, and Normalization
VICT instruments terminal verifiers into auditable atoms and proof edges, then restricts advantage corrections to dependency-valid evidence. Its core search and normalization safeguards prioritize eligibility, abstention, and calibrated corrections over unsupported attribution.
- Verifier instrumentation: VICT accepts verifier interfaces only when they reconstruct the original terminal verifier within a fixed tolerance.Mutation conformance is also evaluated on verifier-relevant mutations.
- Proof edges: Verifier atoms connect to actions through fixed witness predicates for writes, evidence reveals, commits, and violations.Terminal-only atoms require a reliable last writer or final commit action.
- Eligibility: Every non-zero correction requires a verifier-backed proof gate with an observed witness edge, non-zero marginal, and dependency-valid proof record.Proof records log action and atom identities, witness information, core identity, marginal, weight, and correction.
- Core search: Greedy core search prioritizes validity and auditability over global optimality, preserving the proof-edge eligibility invariant without claiming a global approximation ratio.On small atom sets, greedy search returned minimum-cardinality valid cores in 91.8–97.6% of cases and matched exhaustive-minimal eligible action sets in 96.2–98.8% of rollouts.
- Normalization and abstention: VICT abstains when conformance, evidence, core search, robust scale, or uncertainty conditions fail, leaving the base advantage unchanged.Near-tied cores are abstained unless exact conformance is available; correction overhead is O(Tim|Rx|cW + BmcF).
- Scope: VICT changes the stochastic gradient through a clipped verifier-derived correction and does not claim potential-based policy invariance.Corrections can introduce bias through scaling, clipping, greedy search, dependency design, and proof coverage, while missing or ambiguous evidence falls back to the base advantage.
E Diagnostics and Ablation Interpretation
VICT diagnostics measure whether verifier-derived credit is reconstructable, eligible, covered, sparse, and appropriately abstained. Audits and controls distinguish dependency-aware proof credit from causal claims and simpler credit heuristics.
- Diagnostics: VICT reports reconstruction, mutation conformance, eligibility-invariant pass rate, proof coverage, abstention, sparsity, and reward-hacking diagnostics.Eligibility pass rate is an implementation invariant: violations indicate errors rather than an empirical trade-off.
- Eligibility audit: Eligibility is explicitly not treated as causal necessity or sufficiency; a fixed-continuation intervention reduced terminal verifier scores for 55/60 ALFWorld and 52/60 WebShop credited actions.Two annotators labeling 150 credited proof edges per domain achieved Cohen’s κ = 0.81.
- Core diagnostics: Core-size distributions and budget sensitivity should be reported for larger atom sets because the default B = 8 targets small per-instance atom sets.The correction scale should also be swept when verifier score ranges change substantially.
- Ablation interpretation: Ablations test whether dependency cores, proof edges, and abstention add value beyond dense atom rewards, treating all satisfied facts as relevant, or relying on temporal proximity.The dense atom reward ablation does not establish that VICT is not return redistribution.
- Negative controls: Targeted controls compare VICT with commit-only credit, temporal-nearest assignment, and randomized proof-edge placebos while preserving or varying credited-action sparsity.These controls are designed to rule out simpler explanations for the gains.
F Illustrative Proof Traces and Real-Task Case Studies
Case studies show VICT tracing useful predecessor actions and harmful commits through verifier-supported proof edges across household, shopping, retail, and airline tasks. The traces expose why scalar terminal outcomes conflate distinct errors and successes.
- ALFWorld: In ALFWorld Heat, VICT credits taking, heating, and placing the egg because those actions write verifier-relevant identity, transformation, and placement atoms.Opening the fridge receives no progress credit when it does not enter the dependency core.
- ALFWorld: Within failed ALFWorld trajectories, useful object-acquisition actions can receive positive correction while premature or wrong final placement receives negative commit credit.The dependency core therefore separates helpful predecessors from harmful final actions in one rollout.
- WebShop: The WebShop failed purchase satisfies some options and budget checks but violates hard product-type, material, and fit requirements.The product page describes a T-shirt rather than the requested tuxedo shirt with required material and fit constraints.
- WebShop: VICT encourages delaying purchase until evidence supports all hard atoms, unlike dense atom reward that could reward cheap options and price while the final product remains invalid.The decisive issue is whether the final buy commits a product whose hard verifier atoms are all supported.
- τ-bench Retail: The τ-bench Retail trace uses verifier atoms to resolve unavailable exact variants, fallback preferences, and valid multi-item exchange replacements.The exact clicky/RGB/full-size keyboard variant is unavailable, so the available no-backlight/full-size fallback is selected.
- τ-bench Retail: Retail verification distinguishes missing confirmation, unavailable replacements, wrong preference resolution, and incomplete exchange lists that scalar zero reward would collapse together.The case shows why policy and database atoms belong in the verifier core.
- τ-bench Airline: In the Airline case, VICT assigns negative credit to API calls writing inconsistent fields while crediting earlier evidence-gathering calls that identified correct reservation, route, or payment candidates.The proof core combines itinerary search, payment sufficiency, confirmation, and database writes.