Source-linked AI summary
Dense Process Supervision for Search Agents via Fact Utility Estimation
Rongzhi Zhu, Xiangyu Liu, Yi Liu, Shuo Zhang, Ruirui Zhang, Rui Wu, Tao Jiang, Zequn Sun, Wenhao Xu, Wei Hu
TL;DR
Outcome-only rewards obscure the value of intermediate search steps, making credit assignment difficult. FactAgent extracts and clusters structured facts, estimates cluster utilities from group rollouts, and turns them into dense rewards; it consistently outperforms baselines across seven QA benchmarks, with especially significant gains on multi-hop tasks.
Problem
Outcome-based supervision is sparse and delayed, making the contributions of individual intermediate search actions difficult to identify.
Method
FactAgent stores structured evidence facts, clusters semantically equivalent facts, estimates their posterior utilities Bayesianly from group rollouts, and converts them into dense step-level rewards.
Results
FactAgent consistently outperforms baselines on seven QA benchmarks, with significant gains on multi-hop reasoning tasks.
Takeaways & Limitations
Dense process supervision particularly improves evidence precision and retrieval quality while guiding credit assignment for complex reasoning chains.
Takeaways & Limitations
The method increases GPU memory use, depends on clustering quality and sufficient GRPO rollouts, and has been evaluated only on static QA datasets.
Abstract
from arXiv · showhide
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.
1 Introduction
Outcome-only rewards make it difficult to assign credit to intermediate search actions. FactAgent addresses this by representing evidence as structured facts, estimating their utility, and converting those utilities into dense rewards.
- Motivation: Outcome-based RL rewards only final-answer correctness, leaving intermediate tool-call contributions implicit and difficult to identify.Correct answers may contain unnecessary evidence, while failed trajectories may include useful earlier reasoning.
- Approach: FactAgent extracts retrieved evidence into structured facts and maintains them in an explicit fact store.The fact-centric representation replaces raw interaction history with compact evidence units.
- Approach: Bayesian estimation clusters semantically equivalent facts and infers their posterior utility from group-level rollout statistics.The estimated utilities support more precise credit assignment for intermediate steps.
- Results: 51.2 average EM with the 7B backbone surpasses the strongest baseline by +3.2 EM across seven QA benchmarks.Ablations and analyses also report improved evidence precision and retrieval quality.
2 Related Work
Related work develops retrieval-augmented and tool-using search agents, while multi-step retrieval and reasoning remain challenging. RL methods commonly optimize reasoning and search with sparse outcome rewards, alongside work on long-horizon memory management.
- Retrieval and search: Retrieval-augmented systems ground generation in external corpora, with later work improving retrieval through graphs, entity matching, and on-demand tool use.Benchmarks evaluate multi-step retrieval and reasoning, including deep-research-style systems.
- Retrieval and search: Planning and optimizing multi-step search remains challenging even as benchmarks increasingly assess multi-step retrieval and reasoning.Prior work also evaluates whether retrieved evidence sufficiently supports generated answers through fine-grained citation measures.
- RL search agents: Search-R1 and ReSearch jointly optimize reasoning and search with GRPO using sparse outcome rewards.Other RL methods address long-horizon information seeking through memory management.
3 Preliminaries
The paper formulates search-agent reasoning as an MDP with an explicit fact-based knowledge state. Agents search, assert structured evidence into a fact store, and answer, while dense supervision addresses the limitations of global outcome signals.
- Problem formulation: The agent state is st = (Q, ot, Ft), combining the question, current observation, and explicit knowledge state.Ft compactly represents accumulated evidence updated throughout the trajectory.
- Fact store representation: Fact-store entries are structured semantic evidence units derived from observations, each paired with a brief source and reliability description.Newly asserted facts at step t are denoted Kt.
- Actions and transition: The action space contains search, assert, and answer actions, with assert updating the store as Ft+1 = Ft ∪ Kt.Search produces a new observation, while answer terminates the episode.
- Training: Outcome supervision provides a global signal but obscures individual contributions, motivating dense step-level signals for GRPO credit assignment.The objective otherwise relies on sparse rewards observed only at trajectory end.
4 Methodology
FactAgent replaces raw interaction-history supervision with a compact fact-store state and dense rewards derived from semantic fact utilities. It clusters equivalent facts, estimates cluster success probabilities from GRPO rollouts, and shapes step-level rewards for credit assignment.
- FactAgent state and actions: FactAgent maintains a persistent fact store containing structured evidence, exposing the question, current store, and latest observation instead of the full interaction history.This keeps prompt length approximately constant while supporting reasoning over accumulated evidence.
- FactAgent state and actions: The agent alternates among search, assert, and answer actions, with assert extracting structured triples and updating the fact store.The answer action terminates the episode using the question and stored facts.
- Fact abstraction and utility estimation: Natural-language facts are clustered by embedding similarity followed by logical verification, allowing utility estimation to share statistical strength across semantically equivalent facts.Verification enforces constraints including negation consistency, exact numeric matching, and relation-level similarity.
- Fact abstraction and utility estimation: Cluster utility is modeled as a latent success probability and estimated from GRPO rollout statistics with a symmetric Beta prior and posterior mean.The Bayesian formulation addresses small-group, high-variance estimates when individual facts are rarely observed.
- Fact abstraction and utility estimation: Relative cluster utility subtracts the sampled group baseline, producing a cluster-level proxy for the advantage used by GRPO.Positive values indicate above-average associated success, while negative values indicate correlation with failure.
- Dense process rewards: Potential-based reward shaping converts utilities into dense feedback when new semantic information is acquired, while unique-cluster accounting prevents redundant assertions from earning repeated gains.The potential is bounded with tanh to improve training stability, and reward attribution redistributes assert-step gains toward the preceding search step.
- Dense process rewards: Auxiliary penalties discourage format violations, repetitive searches, and premature answers with empty fact stores, with the last case receiving terminal reward zero.The action-level policy update weights every reasoning step by its specific hybrid advantage.
5 Experiment
Experiments across seven single-hop and multi-hop QA benchmarks show that FactAgent improves performance, especially on multi-hop tasks, while its dense supervision and fact-centric design support credit assignment and efficiency. Ablations and analyses indicate that RL, semantic clustering, reward redistribution, and dense process rewards are important components.
- Main Results: FactAgent achieves the best weighted-average EM across seven QA benchmarks with both Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct backbones.With the 7B backbone, it surpasses the strongest baseline by +3.2 EM on average.
- Main Results: Performance gains are more significant on multi-hop datasets than on single-hop tasks, with similar improvements across the 3B and 7B backbones.The results suggest effectiveness across model sizes without requiring a strong backbone.
- Main Results: FactAgent outperforms strong Google Search-based baselines despite retrieving exclusively from the more restricted local Wiki-18 index.The authors attribute this to more effective identification and use of relevant information from limited retrieval results.
- Main Results: RL is essential: before RL, FactAgent performs poorly and can underperform one-shot RAG, whereas after RL training it becomes state-of-the-art.The authors link this change to adaptation to the specialized Search–Assert–Answer workflow.
- Ablation Study: Removing exact-match limitations from fact clustering matters: average EM drops from 51.2 to 48.9 when semantic clustering is replaced by exact-match clustering.Surface variation among model-generated facts makes exact-match grouping insufficient for complete aggregation and utility estimation.
- Ablation Study: Removing reward redistribution lowers average EM from 51.2 to 45.4, with a larger reduction on multi-hop than single-hop datasets.Propagating fact-level utility to earlier retrieval steps is especially important when multiple pieces of evidence must be combined.
- Ablation Study: Removing dense process rewards causes the largest ablation degradation, particularly for challenging multi-hop queries under restricted input and retrieval budgets.Outcome-only GRPO does not provide sufficient signals for learning effective intermediate behaviors.
- Analysis: FactAgent maintains a compact fact-store input, while ReAct accumulates nearly four times more input tokens by the eighth turn.The compact representation reduces later-step inference cost and delays context-window limits during multi-turn search.
6 Conclusion and Future Work
The paper concludes that dense process supervision addresses credit assignment in search agents by organizing evidence as facts, estimating their utility, and using it for step-level rewards. FactAgent consistently outperforms baselines, particularly on multi-hop reasoning, while future work targets richer facts and continuous utilities.
- Conclusion: FactAgent addresses search-agent credit assignment by replacing unstructured history with a fact store, Bayesian fact clustering, and step-level utility rewards.The method organizes retrieved evidence into explicit structured facts before estimating and applying their utilities.
- Conclusion: Experiments show consistent improvements over baselines, with significant gains on multi-hop reasoning tasks.The conclusion identifies multi-hop performance as the clearest reported benefit.
- Future Work: Future work includes extending dense process supervision to richer fact representations and continuous utility signals.
Ethical Considerations
The paper states that its datasets and language models are public and use permissive licenses.
- Ethical Considerations: The datasets and LLMs used in this work are public with permissive licenses.
Limitations
The paper justifies the fact store as a state abstraction under semantic sufficiency, but the method has computational, estimation, and evaluation-scope constraints. Its theoretical guarantee depends on preserving the Markov property under that assumption.
- Scope and Assumptions: The fact store is a valid state abstraction only under the assumption of semantic sufficiency, which preserves the Markov property and policy optimality.
- State Representation: The state transition retains the fact store when the action is not Assert, while search actions generate raw environment feedback.
- State Representation: The proposed state discards raw interaction history and instead tracks accumulated facts updated through the Assert action.
A.3 Equivalence Analysis
Under the semantic sufficiency assumption, the fact store is a valid state abstraction of interaction history, preserving the Markov property and optimal policy values. The section formalizes the induced MDP and states the evaluation setting.
- Equivalence Analysis: The semantic sufficiency assumption treats the fact store as sufficient for predicting future environment feedback and final rewards.
- Equivalence Analysis: Under this assumption, fact-centric states form an MDP because feedback depends on history only through the fact state.
- Equivalence Analysis: Theorem 2 states that mapping histories to fact states preserves the optimal value under the semantic sufficiency assumption.
- Equivalence Analysis: The resulting transition and reward model is well-defined over compressed fact states, so policies depending only on the fact store lose no optimality.
- Equivalence Analysis: Experiments evaluate the method on seven QA benchmarks spanning single-hop and multi-hop settings, using weighted-average exact match.
C.2 Calibration of Similarity Thresholds and Filtering Rules
The calibration study finds that embedding similarity is high for equivalent triples but also produces false positives for negation, numeric differences, and relation ambiguity. The method therefore combines a lenient threshold with deterministic consistency filters.
- Calibration of Similarity Thresholds and Filtering Rules: Semantically equivalent triples consistently exceed cosine similarity 0.95 in the calibration study.
- Calibration of Similarity Thresholds and Filtering Rules: Embedding similarity above 0.95 can falsely group triples differing in negation, numeric values, or relation meaning.
- Calibration of Similarity Thresholds and Filtering Rules: The clustering strategy uses a high-recall threshold σsim = 0.95 followed by negation, numeric, and relation-specific consistency checks.
- Calibration of Similarity Thresholds and Filtering Rules: A bidirectional test handles subject-object inversion by checking both the original and swapped triple configurations before merging.
- Calibration of Similarity Thresholds and Filtering Rules: The ablation analysis reports per-dataset EM scores for Qwen2.5-7B-Instruct across seven QA benchmarks.
- Calibration of Similarity Thresholds and Filtering Rules: SFT cold start does not consistently improve initial or post-RL performance, but it improves training stability and reduces early-stage degeneration.
F Hyperparameter Sensitivity Analysis
Performance depends on the aggregation weight for process rewards and on rollout group size, while the method adds limited measured computational overhead. Process rewards improve over outcome-only supervision at moderate weight.
- Hyperparameter Sensitivity Analysis: 7.3 points: setting Ω = 0.3 improves average EM over pure outcome-based training.
- Hyperparameter Sensitivity Analysis: Final performance is sensitive to Ω, with excessive process-reward weight reducing the benefit of the combined objective.
- Hyperparameter Sensitivity Analysis: Increasing rollout count from 4 to 6 substantially improves performance, whereas increasing it to 8 yields only marginal gains.
- Hyperparameter Sensitivity Analysis: Clustering adds 2.75 seconds per training step, while rollout_n = 6 gives a training-step time of 231.1s versus 225.2s for standard GRPO.
H Utility Distribution Analysis
Utility mass is concentrated in a small number of fact clusters across evaluated datasets, including harder questions that require slightly more evidence aggregation. The section also situates FactAgent among process-supervision approaches.
- Utility Distribution Analysis: Utility distributions remain highly concentrated rather than uniformly sparse after facts are clustered and normalized into probability masses.
- Utility Distribution Analysis: The first three fact clusters capture more than 93% of total utility mass across NQ, HotpotQA, and TriviaQA.
- Utility Distribution Analysis: Hard questions require slightly more evidence aggregation, but their utility distributions remain strongly concentrated.
- Utility Distribution Analysis: The clustering analysis supports a design centered on a small number of informative evidence facts rather than exponentially growing intermediate states.
- Utility Distribution Analysis: FactAgent estimates step-level utilities without additional annotation and avoids expensive per-step branching and Monte Carlo rollout expansion.