STAMP: Provenance-Guided Credit Assignment for Deep Search Agents

Deep-search agents often struggle with a reward-credit mismatch: while reinforcement learning (RL) models are trained using trajectory-level rewards (e.g., final answer correctness), the actual search actions that discover supporting evidence remain unrewarded. This paper investigates how to better attribute credit to the specific intermediate search steps that expose useful information, thereby improving the efficiency and accuracy of long-horizon search agents.

The authors propose STAMP (Step-level Trace-guided Advantage Modulation with Provenance). Instead of relying solely on outcome-based rewards, STAMP uses a reference-based verifier to check if cited documents support entities or relations defined in a training-time evidence graph. It then performs first-exposure attribution, tracing each piece of verified evidence back to the specific action that first surfaced it. This step-level credit is injected into the training process using sign-preserving advantage modulation, which redistributes optimization pressure within a trajectory without altering the overall trajectory-level reward or the relative ranking of rollouts.

STAMP significantly improves performance on benchmarks including BrowseComp, BrowseComp-ZH, and xbench-DS. When applied to a GRPO baseline, STAMP yielded accuracy gains of +2.0, +5.5, and +3.0 points, respectively. The authors demonstrate that the gains are most pronounced when the trajectory-level reward is sparse (e.g., outcome-only or citation-rubric rewards), as the provenance-based signal provides the necessary granular supervision that outcome-level scoring lacks. Ablation studies confirm that both the verification quality and the sign-preserving modulation are essential to the performance improvements.

This work addresses a fundamental limitation in current RL-based search agents: the tendency to treat long, complex search trajectories as monolithic units. By decoupling the verification of evidence from the actions that produce it, STAMP allows models to learn more effectively from the process of discovery. This approach is particularly valuable for open-web search tasks where the agent must navigate large, evolving action spaces to find specific, verifiable facts.