mlsanityData to 7 Oct 2026

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

arXiv 2605.29697 ↗First posted 28 May 2026cs.AIcited by 2

On the map: LLM agents and tool use → Reinforcement learning for LLM agents

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.

Key facts. Cited by 2 papers in the map (data through 7 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.

Builds on

13 of 27 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Reinforcing Multi-Turn Reasoning in LLM Agents via Fine-Grained Reward Structure and Credit Assignment17 May

Other references · 12

  1. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  2. 2025Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learningcited by 1,371
  3. 2023GAIA: a benchmark for General AI Assistantscited by 1,084
  4. 2025BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agentscited by 616
  5. 2025Beyond Ten Turns: Unlocking Long-Horizon Agentic Search with Large-Scale Asynchronous RLcited by 144
  6. 2025xbench: Tracking Agents Productivity Scaling with Profession-Aligned Real-World Evaluationscited by 118
  7. 2025TreeRL: LLM Reinforcement Learning with On-Policy Tree Searchcited by 75
  8. 2025MiroThinker: Pushing the Performance Boundaries of Open-Source Research Agents via Model, Context, and Interactive Scalingcited by 72
  9. 2025Stabilizing MoE Reinforcement Learning by Aligning Training and Inference Routerscited by 67
  10. 2025Process-Supervised Reinforcement Learning for Code Generationcited by 21
  11. 2025DynaSearcher: Dynamic Knowledge Graph Augmented Search Agent via Multi-Reward Reinforcement Learningcited by 14
  12. 2026Chaining the Evidence: Robust Reinforcement Learning for Deep Search Agents with Citation-Aware Rubric Rewardscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026ABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignmentcited by 1
  2. 2026Beyond Outcome Rewards: Constructing and Assigning Retrieval Credit for Search Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026PathRouter: Aligning Rewards with Retrieval Quality in Agentic Graph Retrieval-Augmented Generation
  2. 2026PiCA: Pivot-Based Credit Assignment for Search Agentic Reinforcement Learning
  3. 2026TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
  4. 2026BiCAA: Bidirectional Credit Assignment for Search-Augmented Agent
  5. 2026Beyond Outcome Rewards: Step-Level Self-Distilled Policy Optimization for Deep Search Agents
  6. 2025PRInTS: Reward Modeling for Long-Horizon Information Seeking
  7. 2026Self-Induced Outcome Potential: Turn-Level Credit Assignment for Agents without Verifiers
  8. 2025AgentPRM: Process Reward Models for LLM Agents via Step-Wise Promise and Progress