# Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling

arXiv: https://arxiv.org/abs/2605.29697 · HTML: https://mlsanity.com/paper/2605.29697/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 28 May 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 13 of 13)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents](https://mlsanity.com/paper/2504.12516/) (2025)
- [Beyond Ten Turns: Unlocking Long-Horizon Agentic Search with Large-Scale Asynchronous RL](https://mlsanity.com/paper/2508.07976/) (2025)
- [xbench: Tracking Agents Productivity Scaling with Profession-Aligned Real-World Evaluations](https://mlsanity.com/paper/2506.13651/) (2025)
- [MiroThinker: Pushing the Performance Boundaries of Open-Source Research Agents via Model, Context, and Interactive Scaling](https://mlsanity.com/paper/2511.11793/) (2025)
- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [Reinforcing Multi-Turn Reasoning in LLM Agents via Fine-Grained Reward Structure and Credit Assignment](https://mlsanity.com/paper/2505.11821/) (2025)
- [Stabilizing MoE Reinforcement Learning by Aligning Training and Inference Routers](https://mlsanity.com/paper/2510.11370/) (2025)
- [Process-Supervised Reinforcement Learning for Code Generation](https://mlsanity.com/paper/2502.01715/) (2025)
- [DynaSearcher: Dynamic Knowledge Graph Augmented Search Agent via Multi-Reward Reinforcement Learning](https://mlsanity.com/paper/2507.17365/) (2025)
- [Chaining the Evidence: Robust Reinforcement Learning for Deep Search Agents with Citation-Aware Rubric Rewards](https://mlsanity.com/paper/2601.06021/) (2026)

## Built on by (most cited first, 2 of 2)

- [ABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignment](https://mlsanity.com/paper/2608.05102/) (2026)
- [Beyond Outcome Rewards: Constructing and Assigning Retrieval Credit for Search Agents](https://mlsanity.com/paper/2610.10179/) (2026)

## Abstract (arXiv)

In Agentic Search, trajectory-level outcome rewards fail to quantify the behavioral contributions of individual steps, while existing step-level reward methods typically rely on costly tree sampling. We view world knowledge as a latent world graph and each IS task as search within a latent task graph, where effective steps should make graph progress toward the answer node. Based on this prior, we propose Graph-Distance Contribution Reward (GDCR), a step-level process reward that scores newly-retrieved and newly-cited entities by their distance to the answer node in a training-time Entity-Relation (ER) graph. We further propose Step Advantage Policy Optimization (SAPO), which converts GDCR into step-level advantages and combines them with trajectory-level outcome advantages. Experiments on four challenging benchmarks validate the effectiveness of our method.