🤖 AI

STAMP: Provenance-Guided Credit Assignment for Deep Search Agents

STAMP addresses the reward-credit mismatch in deep-search agents by introducing a provenance-guided credit assignment mechanism that traces supporting documents back to their exposing actions and redistributes advantage via sign-preserving modulation, thereby significantly improving performance over GRPO baselines across multiple benchmarks.

Original authors: Ke Xu, Han Xu, Xinran Chen, Yuqian Wang, Zhixuan Li, Xiaojian Liu, Changwo Wu, Jianqiang Xia, Yuchen Li

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ke Xu, Han Xu, Xinran Chen, Yuqian Wang, Zhixuan Li, Xiaojian Liu, Changwo Wu, Jianqiang Xia, Yuchen Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are training a super-smart digital detective to solve tricky mysteries on the internet. This detective, called a "deep-search agent," doesn't just guess; it hunts for clues, reads webpages, and pieces together evidence to answer a question. For a long time, the way we taught these detectives was a bit like grading a whole movie based only on the final scene. If the detective got the right answer at the end, the entire movie got a gold star. If it got the wrong answer, the whole thing got a red "F."

But here's the problem: sometimes the detective finds a brilliant clue in the middle of the movie but still gets the final answer wrong because it got confused later. Other times, it stumbles onto the right answer by luck without ever finding the real evidence. The old method couldn't tell the difference. It gave the same credit (or blame) to every single move the detective made, even the boring ones that did nothing. The authors of this paper call this the "reward-credit mismatch." It's like a teacher giving a student a failing grade for a whole essay just because the conclusion was wrong, even if the student wrote three perfect paragraphs of research in the middle.

The Big Idea: STAMP
The researchers propose a new training method called STAMP (Step-level Trace-guided Advantage Modulation with Provenance). Think of STAMP as a super-observant film critic who watches the detective's movie frame-by-frame.

Instead of just looking at the final answer, STAMP asks two specific questions:

Did the detective actually find the right evidence? (Did they find the specific person or fact they were looking for?)
Which specific move first revealed that evidence? (Did they find it when they typed a search query, or when they clicked a link?)

STAMP uses a "reference-based verifier"—basically a smart checker that looks at the documents the detective found and asks, "Does this document actually prove the fact we need?" If it does, STAMP traces that document back to the exact moment the detective first saw it. That specific moment gets a "credit boost."

How It Works Without Breaking the Movie
Here is the clever part: STAMP doesn't change the final grade of the movie. If the detective still got the final answer wrong, the movie is still a failure. But, STAMP uses a special "sign-preserving advantage modulation" to tweak the training.

Imagine the detective is on a rollercoaster. If the ride was a success (positive advantage), STAMP gives a little extra boost to the specific moments where they found good clues, making those moves feel even more rewarding. If the ride was a crash (negative advantage), STAMP doesn't punish the good moves as harshly. It says, "Okay, you failed the mission, but that one search query you made was actually brilliant—let's not erase that lesson." This ensures the detective learns exactly which search moves work, without confusing the lesson with the final outcome.

What the Paper Says It's NOT
The authors are very clear about what this method is not. They argue against the idea that we need to invent complex new reward systems for every single step of the search. They also rule out the idea that we need to guess which moves were good without proof. STAMP relies on proven evidence: if the document isn't there, or if the verifier says it doesn't support the fact, no credit is given. They explicitly state that simply adding random bonuses to steps doesn't work because the old systems just average them out anyway.

The Results: Does It Work?
The team tested STAMP on three different challenge sets: BrowseComp, BrowseComp-ZH (a Chinese version), and xbench-DS. They compared it against a standard training method called GRPO using the exact same starting model, the same training data, and the same search tools.

The results showed that STAMP consistently improved the detective's performance:

On BrowseComp, accuracy went up by +2.0 points.
On BrowseComp-ZH, it jumped by +5.5 points.
On xbench-DS, it improved by +3.0 points.

The paper suggests that these gains happen because STAMP catches "hidden gems"—steps that found useful evidence even in failed attempts—which the old method ignored. In fact, they found that in correct attempts, 83.5% of the steps actually produced no useful evidence at all, while in wrong attempts, 7.0% of the steps did find useful clues. STAMP fixes this by rewarding the useful steps regardless of the final outcome.

How Sure Are They?
The authors are confident in these numbers because they ran controlled experiments where everything was identical except for the training method. They also ran "ablation studies" (which are like taking the machine apart to see which piece does what) and found that every part of STAMP—the verifier, the tracing of the first exposure, and the special modulation—contributed to the success.

However, they do note a limitation: they only tested this on one specific model size (Qwen3-30B). They suggest that while it works well there, it's not yet proven whether this method works just as well on much larger models (like 70B+). So, while the results are solid for the tests they ran, the full potential for bigger brains is still an open question.

In short, STAMP teaches AI detectives to appreciate the journey, not just the destination, by giving credit to the specific moves that actually uncovered the truth.

Technical Summary: STAMP – Provenance-Guided Credit Assignment for Deep Search Agents

1. Problem Statement: The Reward-Credit Mismatch

Deep search agents, which perform multi-step web navigation to verify relations and assemble evidence, are increasingly trained using Reinforcement Learning (RL). However, current training paradigms suffer from a fundamental disconnect known as the reward-credit mismatch.

Trajectory-Level Scoring: Standard RL approaches (e.g., GRPO) assign a single scalar reward to an entire rollout based on outcome correctness, citation quality, or evidence coverage. This reward is then broadcast uniformly to every action token within that trajectory.
The Mismatch: This uniform broadcast fails to distinguish between actions that successfully exposed critical evidence and those that did not. Empirical analysis reveals that in correct rollouts, 83.5% of steps produce no target evidence, while in incorrect rollouts, 7.0% of steps still expose useful entity or relation evidence.
Consequence: The "evidence channel"—identifying which specific search or read actions first surfaced supporting documents—remains an underused supervision signal. Simply adding step-level bonuses to a scalar reward often fails because the bonuses are summed and re-broadcast uniformly, erasing the temporal localization intended.

2. Methodology: STAMP

The authors propose STAMP (Step-level Trace-guided Advantage Modulation with Provenance), a framework that decouples what evidence a trajectory verifies from which action first made that evidence available. STAMP operates without altering the trajectory-level reward or the relative ranking of trajectories within a group.

Core Components

Reference-Based Verification:
- A training-time evidence graph $G=(V, E)$ is constructed for each query, defining target hidden entities and single-hop factual relations.
- A verifier (instantiated as an LLM-based extractor-matcher) judges whether cited documents in a trajectory support specific entities or constraints defined in the graph. This is a reference-based judgment, avoiding the need to score arbitrary intermediate actions directly.
First-Exposure Attribution (Provenance):
- Instead of crediting the action that consumed a document, STAMP credits the action that first exposed it (e.g., the search query that returned the URL).
- For every supporting document $d$ , the system identifies the earliest step $t$ where $d$ became available. All credit for $d$ is assigned to this step.
- Credit is distributed uniformly across supporting documents for a verified entity or relation, bounded by a cap $C$ to prevent any single step from dominating the gradient.
Sign-Preserving Advantage Modulation:
- STAMP injects this step-level credit into the GRPO update process via a multiplicative modulation operator: $M_c(A) = A(1 + \text{sign}(A)c)$ .
- Mechanism:
  - For positive-advantage trajectories ( $A > 0$ ), steps that exposed evidence receive amplified reinforcement ( $1+c$ ).
  - For negative-advantage trajectories ( $A < 0$ ), steps that exposed evidence are attenuated ( $1-c$ ) rather than uniformly penalized. This prevents useful search actions in failed rollouts from being treated as uninformative.
  - The modulation preserves the sign of the original advantage, ensuring the trajectory-level reward and group ranking remain untouched.
- This approach avoids the pitfalls of additive shaping (which requires consensus thresholds) or power-based scaling (which can invert semantics).

3. Experimental Setup

Base Model: Qwen3-30B-A3B-Thinking-2507.
Datasets: Bilingual training data synthesized from Wikipedia (3,000 queries for SFT, 2,600 for RL).
Benchmarks: BrowseComp, BrowseComp-ZH, and xbench-DS.
Baselines: Controlled comparisons using identical SFT initialization, training data, and search tools, differing only in reward design:
- GRPO: Binary outcome reward.
- E-GRPO: Entity hit rate reward.
- C-GRPO: Citation-rubric + outcome reward.

4. Key Results

STAMP consistently improves performance across all benchmarks and reward baselines, demonstrating that provenance-based credit assignment captures complementary optimization signals.

Performance Gains:
- Over the standard GRPO baseline: +2.0 (BrowseComp), +5.5 (BrowseComp-ZH), and +3.0 (xbench-DS).
- Over E-GRPO: +1.1 to +1.7 points.
- Over C-GRPO: +2.2 to +3.5 points.
Ablation Studies:
- Verification: LLM-based verification significantly outperforms simple string matching.
- Attribution: "Earliest-exposure" attribution outperforms "all-step" attribution, confirming the value of identifying the discovery action.
- Modulation: Bounded modulation and attenuation of negative advantages are both critical; removing the cap or ignoring negative trajectories degrades performance.
Training Dynamics: STAMP converges faster and achieves higher relation verification rates than the baseline. Credit attribution remains sparse (~10–12% of steps), indicating the method successfully concentrates optimization pressure on the specific actions that matter.

5. Significance and Claims

The paper claims that STAMP addresses a critical gap in deep search RL by utilizing citation provenance as a verifiable, step-level signal without requiring additional human annotations or changing the fundamental trajectory-level reward structure.

Orthogonality: The method is orthogonal to the choice of trajectory-level reward (outcome-only, entity-aware, or rubric-based), providing additive gains in all cases.
Efficiency: It avoids the computational cost of learning process reward models or performing complex token-level reward modeling during rollout generation. Verification and attribution occur post-hoc.
Interpretability: By tracing evidence back to the specific search query or read action that exposed it, the method provides a clear mechanism for credit assignment that aligns with the agent's actual information-seeking behavior.

The authors conclude that citation provenance carries optimization signals not captured by trajectory-level rewards alone, offering a robust path to improving deep search agents through finer-grained credit assignment.