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

• URL: http://arxiv.org/abs/2605.29697v1
• Date: Thu, 28 May 2026 09:57:12 GMT
• Title: Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling
• Abstract summary: In Agentic Search, trajectory-level outcome rewards fail to quantify the behavioral contributions of individual steps.<n>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.
• Score: 26.540951598344787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning [30.228760269449072]
  Group-based reinforcement learning (RL) methods have achieved remarkable success in improving the performance of large language models (LLMs)<n>We propose Graph-based Group Policy Optimization (GraphGPO), which aggregates all rollout trajectories into a unified state-transition graph.<n>It estimates the distance from each state to the task goal using the global information encoded in the graph.<n>Finally, GraphGPO assigns credit to each edge by estimating a graph-based advantage, based on how much the transition reduces the distance to the task goal.
  arXiv  Detail & Related papers  (2026-05-26T08:23:34Z)
• UniER: A Unified Benchmark for Item-level and Path-level Exercise Recommendation [53.62147575168325]
  We present a Unified Benchmark for Exercise Recommendation (UniER)<n>UniER is a comprehensive evaluation framework that unifies ILER and PLER.<n>Our results reveal the systematic dominance of PLER and expose the pedagogical failure of ILER's fragmented recommendations.
  arXiv  Detail & Related papers  (2026-05-16T02:07:58Z)
• STAR: Semantic-Tuned and Tail-Adaptive Retriever for Graph-Augmented Generation [69.66045538889777]
  We propose STAR, a semantic-tuned and tail-adaptive retriever for GraphRAG.<n> STAR consistently outperforms baselines, achieving average retrieval performance gains of 1.8%.
  arXiv  Detail & Related papers  (2026-04-11T10:16:51Z)
• STEP: Success-Rate-Aware Trajectory-Efficient Policy Optimization [23.48518286261969]
  Trajectory-level optimization treats each trajectory as a single training sample.<n>This approach can be inefficient and yield misleading learning signals.<n>We propose STEP (Success-rate-aware Trajectory-Efficient Policy optimization), a framework that dynamically allocates sampling based on per-task success rates.
  arXiv  Detail & Related papers  (2025-11-17T07:43:15Z)
• Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations [37.10671332775445]
  The integration of graphs with Goal-conditioned Reinforcement Learning (GCHRL) has recently gained attention.<n>Existing approaches typically rely on domain-specific knowledge to construct these graphs.<n>This paper proposes a solution by developing a graph encoder-decoder to evaluate unseen states.
  arXiv  Detail & Related papers  (2025-11-14T00:58:39Z)
• Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs [39.425801384830415]
  Reasoning over structured graphs remains a fundamental challenge for Large Language Models.<n>We propose Reasoning by Exploration (RoE), a novel approach that unifies retrieval and generation by framing reasoning over graphs as a process of graph exploration.<n>RoE achieves substantial overall improvements over baselines, while also generalizing effectively to unseen graphs.
  arXiv  Detail & Related papers  (2025-10-08T19:29:19Z)
• Agentic Reinforcement Learning with Implicit Step Rewards [92.26560379363492]
  Large language models (LLMs) are increasingly developed as autonomous agents using reinforcement learning (agentic RL)<n>We introduce implicit step rewards for agentic RL (iStar), a general credit-assignment strategy that integrates seamlessly with standard RL algorithms.<n>We evaluate our method on three challenging agent benchmarks, including WebShop and VisualSokoban, as well as open-ended social interactions with unverifiable rewards in SOTOPIA.
  arXiv  Detail & Related papers  (2025-09-23T16:15:42Z)
• GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning [13.481673780508215]
  GRAIL is a framework designed to interact with large-scale graphs for retrieval-augmented reasoning.<n>GRAIL achieves an average accuracy improvement of 21.01% and F1 improvement of 22.43% on knowledge graph question-answering datasets.
  arXiv  Detail & Related papers  (2025-08-07T15:34:41Z)
• RRO: LLM Agent Optimization Through Rising Reward Trajectories [52.579992804584464]
  Large language models (LLMs) have exhibited extraordinary performance in a variety of tasks.<n>In practice, agents sensitive to the outcome of certain key steps which makes them likely to fail the task.<n>We propose Reward Rising Optimization (RRO) to mitigate this issue.
  arXiv  Detail & Related papers  (2025-05-27T05:27:54Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  Goal-conditioned reinforcement learning can solve tasks in a wide range of domains, including navigation and manipulation. We propose the distant goal-reaching task by using search at training time to automatically generate intermediate states. E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints.
  arXiv  Detail & Related papers  (2021-10-22T22:05:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.