Skip to content

STAMP: Provenance-Guided Credit Assignment for Deep Search Agents

🕒 Published (v1): 2026-07-13 07:12 UTC · Source: Arxiv · link

Why this paper was selected

Provenance-guided credit assignment for deep-search agents; novel RL signal beyond trajectory-level scoring

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Deep-search RL agents trained with trajectory-level rewards suffer a reward-credit mismatch: 83.5% of steps in correct rollouts produce no evidence, while 7.0% of steps in incorrect rollouts still expose useful evidence. STAMP resolves this by tracing citation provenance to identify which search action first exposed each verified document, then injecting that step-level credit via sign-preserving advantage modulation on top of GRPO—without altering the trajectory-level reward. On BrowseComp, BrowseComp-ZH, and xbench-DS, STAMP yields +2.0/+5.5/+3.0 points over the GRPO baseline.

Problem

Outcome-supervised RL (e.g., GRPO) broadcasts a single scalar reward uniformly to every action token in a trajectory. For long-horizon web search agents, this ignores which intermediate search or read action first surfaced the supporting document. Richer trajectory-level rewards (citation-aware, entity-hit, rubric-based) still share the same uniform-broadcast flaw: they refine what to reward but not which step deserves it. The result is that evidence-producing actions receive no targeted credit, slowing policy improvement and suppressing relation-verification capability.

Method

STAMP operates in four post-rollout steps after standard GRPO sampling:

  1. Evidence graph construction (training time only): Each query \(q\) is paired with a graph \(G=(V,E)\) where nodes are task-relevant entities (\(V_{\text{tar}}\) = hidden targets) and edges are single-hop, single-document-verifiable natural-language constraints \(c_{ij}\).

  2. Evidence verification: An LLM-based verifier \(J\) checks whether each cited document supports a specific entity or constraint from \(G\), producing supporting document sets \(D(e)\) and \(D(u_k)\). Verification indicators are: $\(\text{verified}(u_k) = \text{cov}(e_i)\cdot\text{cov}(e_j)\cdot\text{cov}(c_{ij})\)$

  3. First-exposure attribution: Each supporting document \(d\) is assigned to \(\text{step}(d) = \min\{t : d \in A_t\}\), the earliest action that made it available. Per-step credit accumulates entity and relation contributions, capped at \(C \in [0,1)\): $\(\text{credit}_t = \min\!\left(C,\; E_t + U_t\right)\)$

  4. Sign-preserving advantage modulation: The GRPO advantage \(A_i\) is modulated at the step level using the multiplicative operator: $\(M_c(A) = A\!\left(1 + \text{sign}(A)\cdot c\right), \quad c \in [0,C]\)$ For positive-advantage trajectories, credited steps are amplified; for negative-advantage trajectories, credited steps are attenuated (not sign-flipped), preserving the trajectory ranking. The clipped GRPO objective replaces the broadcast \(A_i\) with the per-token modulated advantage \(A^*_{i,m}\).

Key Contributions

  • Empirical characterization of the reward-credit mismatch: 83.5% of steps in correct rollouts produce no evidence; 7.0% of steps in incorrect rollouts still expose entity- or relation-level evidence.
  • STAMP: a provenance-guided credit assignment mechanism that converts citation provenance into verifiable step-level credit via a reference-based LLM verifier and first-exposure attribution.
  • Sign-preserving advantage modulation (Eq. 9) that redistributes optimization pressure within a trajectory without altering trajectory-level rewards or group rankings, with bounded per-step credit (Eq. 8) scaling with evidence-graph size rather than trajectory length.
  • Demonstrated orthogonality to reward design: STAMP composes additively with outcome-only (GRPO), entity-aware (E-GRPO), and rubric-based (C-GRPO) base rewards.

Results

  • GRPO + STAMP vs. GRPO: +2.0 BrowseComp / +5.5 BrowseComp-ZH / +3.0 xbench-DS (+2.6 overall).
  • E-GRPO + STAMP vs. E-GRPO: +1.1 / +1.7 / +0.0 (+1.2 overall).
  • C-GRPO + STAMP vs. C-GRPO: +2.2 / +3.5 / +2.0 (+2.4 overall).
  • Gains are largest when the base reward least supervises entity recovery (outcome-only > citation-rubric > entity-aware).
  • Ablation — verification method: LLM URL+Judge (20.9/36.3/73.0) vs. string matching (15.6/26.6/65.0) on BC/BC-ZH/xbench.
  • Ablation — modulation variants: Full design (20.9/36.3/73.0) outperforms all-step attribution (19.2/31.1/71.0), unbounded cap (16.3/28.7/67.0), and positive-only modulation (20.1/34.0/71.0).
  • Training dynamics: STAMP achieves higher outcome reward and faster convergence; largest separation on relation verification rate; attribution is sparse (~10–12% of steps receive non-zero credit).

Limitations

  • Evidence graph is synthesized from Wikipedia; generalization to non-Wikipedia domains or queries with sparse structured evidence is unverified.
  • Verification and attribution rely on GPT-5.1 as an LLM judge, introducing cost and potential judge-model bias; errors in verification propagate directly into step credit.
  • First-exposure attribution is a deliberate inductive bias (favors query-formulation over page-reading); learned or information-gain-based alternatives are left to future work.
  • The evidence graph is a training-time scaffold, not an exhaustive enumeration of valid evidence paths, so some useful evidence may go uncredited.
  • Gains on E-GRPO (entity-aware reward) are smaller and zero on xbench-DS, suggesting diminishing returns when the base reward already densely supervises entity recovery.
  • Tested on a single base model family (Qwen3-30B-A3B-Thinking-2507); broader model generalization is not reported.

Relevance to Agentic AI / LLM Agents

STAMP directly addresses a core training challenge for tool-using LLM agents operating over long horizons: the mismatch between trajectory-level outcome signals and the individual actions that actually produce useful intermediate results. The sign-preserving advantage modulation technique is a general RL credit-assignment mechanism applicable to any multi-step agent trained with GRPO-style group-relative policy optimization, not just web search. The finding that ~83.5% of steps in successful trajectories contribute no evidence—yet receive equal reinforcement—has direct implications for the efficiency of RL training in coding, research, and planning agents that face similar credit-assignment sparsity. The provenance-tracing approach (map document support → earliest-exposure step) is a practical instantiation of process-level supervision that avoids the need for a learned process reward model by grounding credit in verifiable citation artifacts.