Dense Process Supervision for Search Agents via Fact Utility Estimation¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: Medical LLM
Keywords: Search Agent, Process Supervision, Fact Utility Estimation, Bayesian Inference, Reinforcement Learning
TL;DR¶
Addressing the credit assignment challenge in RL-trained search agents caused by sparse outcome rewards and implicit intermediate contributions, FactAgent represents accumulated evidence within an explicit fact store, infers the posterior utility of semantic fact clusters from group rollouts via Bayesian estimation, and applies potential-based reward shaping to deliver dense step-level process supervision.
Background & Motivation¶
Autonomous search agents powered by large language models (LLMs) alternate between external retrieval tool use and multi-step reasoning, showing strong potential in navigating open-world environments and answering knowledge-intensive questions. Reinforcement learning (RL), particularly group relative policy optimization (GRPO), has emerged as the standard paradigm to optimize these planning and information seeking policies. However, prevailing RL algorithms rely almost entirely on outcome-based rewards, evaluating trajectories strictly by the correctness of the final answer. This terminal scalar signal is sparse, delayed, and inherently incapable of distinguishing which intermediate steps actively contributed to the outcome.
In multi-hop information-seeking tasks, the causal link between intermediate observations and final answers is subtle and context-dependent. A trajectory that eventually arrives at the correct answer may contain redundant queries, irrelevant retrieved passages, or coincidental facts that contributed nothing to the reasoning chain. Conversely, a failed trajectory often contains valuable, high-precision retrieval steps that are unfairly penalized by a zero terminal reward. Furthermore, standard ReAct architectures append raw interaction histories directly into the prompt, leading to linear context window explosion across turns and rendering implicit state representations mathematically and statistically intractable for fine-grained credit assignment.
To overcome these structural limitations, this paper proposes discretizing continuous, unstructured interaction histories into interpretable semantic evidence units whose utilities can be statistically tracked across sampled rollouts. Core idea: decompose intermediate retrieved evidence into a structured fact store, infer the posterior utility of semantic fact clusters using Bayesian estimation across group rollouts, and transform these utilities into dense step-level process rewards via potential-based reward shaping, achieving fine-grained credit assignment without requiring an external reward model.
Method¶
Overall Architecture¶
FactAgent formulates the multi-turn search and reasoning problem as an explicit fact-centric Markov Decision Process (MDP) defined over state tuples \(s_t = (Q, o_t, F_t)\), where \(Q\) is the initial question, \(o_t\) is the most recent observation (overwriting prior observations to keep prompt length approximately constant), and \(F_t\) is a persistent structured fact store. At each step, the policy selects one of three discrete actions: issuing an information-seeking query via search, distilling the retrieved observation into structured triples and updating the fact store \(F_{t+1} = F_t \cup K_t\) via assert, or terminating the episode with a concise response via answer. During training, group rollouts are generated under GRPO; newly asserted facts are grouped through a two-stage semantic clustering strategy, their cluster-level posterior utilities are computed through Bayesian estimation, and dense process rewards are shaped via potential differences and causally redistributed back to earlier retrieval actions.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Query Q & Environment Interaction"] --> B["Explicit Fact Store Construction<br/>Extract structured triples to update Ft while keeping prompt constant"]
B --> C["Two-Stage Fact Semantic Clustering<br/>E5 embedding filtering combined with conservative logical constraints"]
C --> D["Bayesian Utility Estimation & Relative Gain<br/>Conjugate Beta posterior inference over cluster-level success rates"]
D --> E["Potential-Based Reward Shaping & Credit Redistribution<br/>PBRS preserves policy optimality with backward assignment to search"]
E --> F["Hybrid Advantage Optimization<br/>Combine global outcome advantage with dense process advantage"]
Key Designs¶
1. Explicit Fact Store Construction: Eliminating context explosion and enabling transparent intermediate attribution
Standard ReAct agents suffer from linear token accumulation because the entire interaction history is preserved in the prompt, quickly consuming the context window and clouding step-level attribution. FactAgent replaces raw conversational history with a structured fact store \(F_t\), maintaining state as \(s_t = (Q, o_t, F_t)\). Upon receiving an observation \(o_t\), an assert action distills raw snippets into structured triples paired with short verbalized summaries, updating \(F_{t+1} = F_t \cup K_t\). The authors theoretically prove under the semantic sufficiency assumption that \(F_t\) is a sufficient statistic of the full history \(h_t\) for predicting future observations and terminal rewards, ensuring the Markov property of state transitions and preserving optimal policy value equivalence (\(V^{\text{hist}}(h)^* = V^{\text{fact}}(\Phi(h))^*\)). This reduces input length by nearly 75% at later turns while converting continuous text into discrete, auditable semantic units.
2. Two-Stage Fact Semantic Clustering: Bridging natural language variability and statistical sample sparsity
Directly calculating utility for individual natural language facts within small group rollouts (\(G \in [4, 16]\)) is statistically infeasible because most verbalized facts appear only once or vary in surface wording. FactAgent resolves this by aggregating semantically equivalent facts into equivalence clusters \(C_k = \{f \in \mathcal{F}(\tau) \mid f \sim f_{\text{rep}}\}\). The aggregation pipeline uses a two-stage test: first, a coarse filter checks whether cosine similarity under E5 embeddings exceeds a high-recall threshold (\(\sigma_{\text{sim}} = 0.95\)); second, strict deterministic rules verify negation consistency (rejecting merges between affirmative and negated relations), exact numeric consistency (preventing embeddings from conflating distinct dates or quantities), and relation-level compatibility, along with bidirectional subject-object inversion checks (e.g., "A founded B" versus "B was founded by A"). This ensures reliable statistical strength sharing without spurious semantic collapses.
3. Bayesian Utility Estimation & Relative Gain: Overcoming small-sample empirical variance in advantage estimation
In small rollout groups, calculating empirical success rates directly yields high variance where a single coincidental success skews probability estimates. FactAgent models the latent success probability \(\theta_k = \Pr(R = 1 \mid \mathcal{F}(\tau) \cap C_k \neq \emptyset)\) under a Bayesian conjugate framework, placing a symmetric Beta prior \(\theta_k \sim \text{Beta}(\epsilon, \epsilon)\) (with \(\epsilon = 0.5\)). Given \(N(C_k)\) trajectories in the group containing cluster \(C_k\) and \(S(C_k)\) of them reaching success \(R=1\), the posterior mean is: $\(P(C_k) = \mathbb{E}[\theta_k \mid S(C_k), N(C_k)] = \frac{S(C_k) + \epsilon}{N(C_k) + 2\epsilon}\)$ To align with GRPO's group-relative optimization, the relative cluster utility is centered against the empirical group baseline: \(V(C_k) = P(C_k) - \bar{P}_{\text{group}}\), where \(\bar{P}_{\text{group}} = \frac{1}{G}\sum_{i=1}^G R(\tau_i)\). Positive values indicate evidence statistically associated with above-average success, while negative values penalize misleading paths.
4. Potential-Based Reward Shaping & Credit Redistribution: Preserving policy optimality while solving temporal lag
Arbitrary step-level heuristic rewards often induce policy degeneration through reward hacking. FactAgent utilizes Potential-Based Reward Shaping (PBRS) by defining the potential over unique fact clusters \(\mathcal{U}_t\) present in the fact store at step \(t\):
$\(\Phi(s_t) = \tanh\left(\sum_{C \in \mathcal{U}_t} V(C)\right)\)$
The bounded step shaping reward \(r^{\text{shape}}_t = \Phi(s_t) - \Phi(s_{t-1})\) is non-zero strictly when novel informative knowledge is acquired, guaranteeing policy invariance. Because an assert step causally depends on the preceding search action that retrieved the evidence, FactAgent redistributes the reward using attribution coefficient \(\alpha = 0.2\): the assertion receives \(r^{\text{proc}}_t = (1-\alpha) r^{\text{shape}}_t\) while the preceding search step \(t'\) receives \(r^{\text{proc}}_{t'} = \alpha r^{\text{shape}}_t\), directly reinforcing queries that uncover high-utility knowledge.
Loss & Training¶
FactAgent is implemented on the verl RL framework using Qwen2.5-3B/7B-Instruct backbones and trained on merged splits of NQ and HotpotQA with local Wiki-18 retrieval via E5. The overall action advantage combines global normalized outcome advantage with local process advantage: \(A^{\text{total}}_{i,j} = A^{\text{outcome}}_i + \Omega \cdot r^{\text{proc}}_{i,j}\) (with \(\Omega = 0.5\)). The surrogate clipped objective aggregates gradients over all steps across group trajectories: $\(\mathcal{J}(\theta) = \mathbb{E}\left[ \frac{1}{\sum n_i} \sum_{i=1}^G \sum_{j=1}^{n_i} \min\left(\rho_{i,j} A^{\text{total}}_{i,j}, \text{clip}(\rho_{i,j}, 1-\epsilon_{\text{clip}}, 1+\epsilon_{\text{clip}}) A^{\text{total}}_{i,j}\right) - \beta D_{\text{KL}}(\pi_\theta \parallel \pi_{\text{ref}}) \right]\)$ with \(\rho_{i,j}\) denoting importance sampling ratio, \(\epsilon_{\text{clip}} = 0.2\), and \(\beta = 0.001\). Additional auxiliary penalties penalize JSON parse errors (\(-0.1\)) and duplicate search queries (\(-0.01\)), with a hard constraint setting terminal reward to 0 if an answer is issued from an empty fact store.
Key Experimental Results¶
Main Results¶
Evaluation across three single-hop QA benchmarks (NQ, TriviaQA, PopQA) and four multi-hop QA benchmarks (HotpotQA, 2WikiMultiHopQA, MuSiQue, Bamboogle) measuring Exact Match (EM, %):
| Backbone | Method | NQ | TriviaQA | PopQA | HotpotQA | 2Wiki | MuSiQue | Bamboogle | Weighted Avg. EM |
|---|---|---|---|---|---|---|---|---|---|
| Qwen2.5-3B | Naive RAG | 34.8 | 54.4 | 38.7 | 25.5 | 22.6 | 4.7 | 8.0 | 34.4 |
| Qwen2.5-3B | Search-R1 | 34.1 | 54.5 | 37.8 | 32.4 | 31.9 | 10.3 | 26.4 | 37.7 |
| Qwen2.5-3B | Zerosearch (Google) | 41.4 | 57.4 | 44.8 | 27.4 | 30.0 | 9.8 | 11.1 | 39.5 |
| Qwen2.5-3B | GiGPO | 42.0 | 59.5 | 42.4 | 36.9 | 37.0 | 12.6 | 64.1 | 42.7 |
| Qwen2.5-3B | ReSearch (Google) | 20.4 | 33.5 | 17.3 | 35.6 | 39.3 | 17.3 | 37.6 | 29.1 |
| Qwen2.5-3B | AutoRefine | 43.6 | 59.7 | 44.7 | 40.4 | 38.0 | 16.9 | 33.6 | 44.3 |
| Qwen2.5-3B | FactAgent (w/o RL) | 22.1 | 41.1 | 20.1 | 26.1 | 23.3 | 4.3 | 18.4 | 25.7 |
| Qwen2.5-3B | FactAgent (w/ RL) | 43.9 | 60.3 | 42.3 | 42.6 | 43.1 | 16.9 | 32.8 | 45.4 |
| Qwen2.5-7B | Naive RAG | 34.9 | 58.5 | 39.2 | 29.9 | 23.5 | 5.8 | 20.8 | 36.4 |
| Qwen2.5-7B | Search-R1 | 39.3 | 61.0 | 39.7 | 37.0 | 41.4 | 14.6 | 36.8 | 43.2 |
| Qwen2.5-7B | Zerosearch (Google) | 43.6 | 65.2 | 48.8 | 34.6 | 35.2 | 18.4 | 27.8 | 45.2 |
| Qwen2.5-7B | GiGPO | 46.4 | 64.7 | 46.1 | 41.6 | 43.6 | 18.9 | 68.9 | 47.7 |
| Qwen2.5-7B | ReSearch (Google) | 40.9 | 63.7 | 44.6 | 43.5 | 47.6 | 22.3 | 42.4 | 48.0 |
| Qwen2.5-7B | FactAgent (w/o RL) | 33.0 | 55.1 | 36.7 | 29.2 | 23.8 | 9.1 | 20.8 | 34.9 |
| Qwen2.5-7B | FactAgent (w/ RL) | 46.3 | 69.4 | 46.7 | 44.6 | 51.5 | 19.4 | 44.0 | 51.2 |
Ablation Study¶
Ablation analysis on Qwen2.5-7B-Instruct across single-hop and multi-hop subsets (EM, %):
| Configuration Variant | Single-Hop Avg. | Multi-Hop Avg. | Overall Avg. EM | Note / Observations |
|---|---|---|---|---|
| FactAgent (Full RL) | 55.5 | 45.8 | 51.2 | Full proposed model |
| w/ EM-only clustering | 52.4 | 44.4 | 48.9 | -2.3% overall; surface variations fail to aggregate |
| w/o reward redistribution | 50.6 | 38.7 | 45.4 | -7.1% on multi-hop; search queries uncredited |
| w/o dense process reward | 47.5 | 31.4 | 40.5 | -14.4% on multi-hop; degenerates into sparse GRPO |
Key Findings¶
- Dense process supervision rescues multi-hop reasoning: Disabling dense process rewards causes multi-hop performance to collapse from 45.8% to 31.4% (a 14.4 point drop). Tracking ground-truth reference triple recall on HotpotQA reveals that FactAgent improves evidence recall by nearly 40% during training, whereas outcome-only GRPO shows no upward trend.
- Reward redistribution directly incentivizes effective search queries: Removing the \(\alpha\)-redistribution back to preceding search actions reduces multi-hop EM by 7.1 points, proving that rewarding assertion alone leaves earlier retrieval actions in a credit assignment blind spot.
- SFT cold start stabilizes execution format without lifting performance ceiling: While SFT prevents policy collapse into invalid JSON outputs during early training, the model fine-tuned with SFT achieves 49.5% average EM after RL, slightly lower than the 51.2% achieved by direct RL.
- Scalable token efficiency with minimal computational overhead: By maintaining state strictly through \(F_t\) and the latest observation, FactAgent uses roughly 1/4 the input tokens of ReAct at turn 8. Furthermore, online semantic clustering adds merely 2.75 seconds per step, resulting in per-step training times comparable to vanilla GRPO (231.1s vs. 225.2s).
Highlights & Insights¶
- Turning unstructured history into countable discrete semantic evidence: By mapping continuous textual reasoning into an explicit fact store backed by a formal sufficient statistic proof, the authors enable principled statistical credit assignment for intermediate decisions.
- Intrinsic process supervision without external reward models: Rather than training an error-prone learned reward model or gathering expensive step-level human annotations, FactAgent extracts reliable step rewards purely from group rollout statistics via Bayesian smoothing.
- Broad transferability across agent architectures: The architectural paradigm of "explicit belief state + semantic clustering + Bayesian utility estimation + potential-based reward shaping" can be directly adapted to other sequential decision-making domains such as code generation agents, tool-calling multi-agent frameworks, and autonomous deep research.
Limitations & Future Work¶
- Increased GPU memory footprint for intermediate state reconstruction: Reconstructing step-specific state contexts to perform action-level policy gradient backpropagation demands higher peak memory than terminal-only outcome baselines.
- Sensitivity to clustering fidelity and rollout group size: Utility estimation accuracy depends on the semantic clustering rules and sufficient sample diversity within the GRPO group; extremely small group sizes may still suffer estimation noise.
- Evaluation restricted to static QA corpora: Currently tested primarily on Wikipedia-based static QA benchmarks; extending FactAgent to open-ended, non-stationary agentic environments (such as GAIA or live web browsing) remains an important frontier.
Related Work & Insights¶
- vs Search-R1 / ReSearch: Standard agent RL optimizes policies purely using outcome rewards over full textual trajectories; FactAgent maintains a compact structured fact store and derives dense process rewards that provide essential step-level guidance.
- vs GiGPO / AutoRefine: GiGPO clusters raw implicit agent states which are sensitive to minor surface paraphrasing, while AutoRefine relies on heuristic retrieval-specific metrics; FactAgent clusters explicit semantic fact units and provides theoretically grounded potential-based shaping.
- vs VinePPO: VinePPO requires expensive per-step branching and Monte Carlo tree rollouts to estimate intermediate value; FactAgent avoids online branching overhead by sharing statistical strength across concurrent group rollouts.
Rating¶
- Novelty: โญโญโญโญโญ [Decoupling history into an explicit fact store and inferring step utilities via Bayesian group rollouts is an elegant breakthrough]
- Experimental Thoroughness: โญโญโญโญโญ [Extensive evaluation across 7 benchmarks, complete ablations, theoretical proofs, and cost-efficiency profiles]
- Writing Quality: โญโญโญโญโญ [Rigorous mathematical formulation, clear narrative structure, and comprehensive empirical analyses]
- Value: โญโญโญโญโญ [Provides a practical, external-model-free blueprint for training process-supervised search and reasoning agents]