Dense Process Supervision for Search Agents via Fact Utility Estimation

• URL: http://arxiv.org/abs/2609.00833v1
• Date: Tue, 01 Sep 2026 07:34:33 GMT
• Title: Dense Process Supervision for Search Agents via Fact Utility Estimation
• Abstract summary: We propose a dense process supervision method based on fact utility estimation.<n> Experiments on seven single-hop and multi-hop QA benchmarks show that our method consistently outperforms existing baselines.
• Score: 39.89624659103789
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning (RL) for search agents typically relies on outcome rewards. However, it often fails to achieve effective credit assignment, due to the unclear value of intermediate steps. It is hard to separate their contributions from the final result. In this paper, we propose a dense process supervision method based on fact utility estimation, which models the reasoning process as the accumulation of discrete evidence facts. We first extract structured facts from raw observations and organize them into an explicit fact store. To support credit assignment, we then cluster semantically equivalent facts and infer the posterior utility of each fact cluster using Bayesian estimation over group rollouts. Finally, we convert the estimated fact utilities into dense step-level rewards to guide RL training. Experiments on seven single-hop and multi-hop QA benchmarks show that our method consistently outperforms existing baselines. Ablation studies validate clear relative improvements on multi-hop QA compared to outcome reward-only training.

Related papers

• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• PiCA: Pivot-Based Credit Assignment for Search Agentic Reinforcement Learning [11.926589875842359]
  Large Language Model (LLM)-based search agents have significantly improved the performance of knowledge-intensive tasks.<n>Existing methods encounter critical challenges in long-horizon credit assignment.<n>We propose Pivot-Based Credit Assignment (PiCA) to reformulate the search trajectory as a sequential process of cumulative search progress.
  arXiv  Detail & Related papers  (2026-05-10T03:21:47Z)
• Evaluate-as-Action: Self-Evaluated Process Rewards for Retrieval-Augmented Agents [24.080021799509847]
  textscEvalAct (Evaluate-as-Action) converts implicit retrieval quality assessment into an explicit action.<n>textscEvalAct achieves the best average accuracy, with the largest gains on multi-hop tasks.
  arXiv  Detail & Related papers  (2026-03-10T05:22:40Z)
• Truncated Step-Level Sampling with Process Rewards for Retrieval-Augmented Reasoning [32.295907409325615]
  Training large language models to reason with search engines via reinforcement learning is hindered by a credit assignment problem.<n>We propose SLATE, a framework built on two complementary ideas.<n> Experiments on seven QA benchmarks confirm that SLATE consistently outperforms both sparse-reward and process-reward baselines.
  arXiv  Detail & Related papers  (2026-02-26T19:05:40Z)
• Local Coherence or Global Validity? Investigating RLVR Traces in Math Domains [13.626335241662977]
  Reinforcement Learning with Verifiable Rewards (RLVR)-based post-training of Large Language Models (LLMs) has been shown to improve accuracy on reasoning tasks.<n>We investigate the effect of RL post-training on intermediate tokens which are not directly incentivized.
  arXiv  Detail & Related papers  (2025-10-20T23:58:31Z)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal [70.28430200655919]
  We show that finetuning LLMs with verifier-based (VB) methods based on RL or search is far superior to verifier-free (VF) approaches based on distilling or cloning search traces, given a fixed amount of compute/data budget.<n>We corroborate our theory empirically on both didactic and math reasoning problems with 3/8B-sized pre-trained LLMs, where we find verification is crucial for scaling test-time compute.
  arXiv  Detail & Related papers  (2025-02-17T18:43:24Z)
• Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning [90.23629291067763]
  A promising approach for improving reasoning in large language models is to use process reward models (PRMs) PRMs provide feedback at each step of a multi-step reasoning trace, potentially improving credit assignment over outcome reward models (ORMs) To improve a base policy by running search against a PRM or using it as dense rewards for reinforcement learning (RL), we ask: "How should we design process rewards?" We theoretically characterize the set of good provers and our results show that optimizing process rewards from such provers improves exploration during test-time search and online RL.
  arXiv  Detail & Related papers  (2024-10-10T17:31:23Z)
• VinePPO: Refining Credit Assignment in RL Training of LLMs [66.80143024475635]
  We propose VinePPO, a straightforward approach that leverages the flexibility of language environments to compute unbiased Monte Carlo-based estimates.<n>Our method consistently outperforms PPO and other baselines across MATH and GSM8K datasets in less wall-clock time.
  arXiv  Detail & Related papers  (2024-10-02T15:49:30Z)
• AMU-Tuning: Effective Logit Bias for CLIP-based Few-shot Learning [50.78033979438031]
  We first introduce a unified formulation to analyze CLIP-based few-shot learning methods from a perspective of logit bias. Based on analysis of key components, this paper proposes a novel AMU-Tuning method to learn effective logit bias for CLIP-based few-shot classification.
  arXiv  Detail & Related papers  (2024-04-13T10:46:11Z)

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.