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
EMNLP 2026)
cs.CL, cs.LG
2026-09-01
FactAgent stores evidence as triples, estimates cluster utility, and turns it into dense step rewards. Qwen2.5-7B hits 51.2 mean EM, 3.2 above the strongest baseline.
RL for search agents usually scores only the final answer. A retrieval step that supplied the key fact, added noise, or sent reasoning off track all look the same. A correct ending does not mean every step helped; a wrong ending does not mean every step failed. Multi-hop QA makes the gap worse: a sparse, delayed signal cannot assign credit to a specific tool call.
FactAgent, from Nanjing University and Ant Group, treats reasoning as accumulating discrete evidence and scores each step by that evidence's utility. The paper is accepted at EMNLP 2026.
The agent does not dump raw retrieval text into context. It keeps a fact store. Three actions: Search issues a query; Assert writes (subject, relation, object) triples from the current observation into the store; Answer reads only the question and the store. The prompt holds the question, the store, and the latest observation, so input length does not grow linearly with turns. An appendix argument treats the store as a sufficient statistic of the interaction history.
Dense rewards come from group-rollout statistics. No separate process-reward model. Isolated facts are too rare for a stable Pr(correct | fact). Facts are clustered by embedding similarity, then filtered with negation, numeric, and relation checks so paraphrases share a cluster. Each cluster's success probability gets a Beta(ε, ε) prior with ε=0.5; the posterior mean is (successes+ε)/(occurrences+2ε). Relative utility is that mean minus the group's mean success rate.
State potential is tanh of the sum of cluster utilities. The potential difference is nonzero only when new semantics arrive. The gain lands on Assert, but the evidence came from an earlier Search, so a share α=0.2 of the shaping reward is sent back to that Search and 0.8 stays on Assert. Format errors, repeated searches, and answering from an empty store are penalized; an empty-store answer zeros the terminal reward.
Total advantage is outcome advantage plus Ω times process advantage, default Ω=0.5. Optimization is still GRPO, but at the action level on the current store, not on one growing prompt.
Training merges NQ and HotpotQA. Retrieval is Wiki-18 with E5, at most 8 turns. The outcome reward is answer F1; the reported metric is weighted-average EM.
| Backbone | FactAgent (RL) | Strongest baseline | No RL |
| Qwen2.5-7B-Instruct | 51.2 | ReSearch 48.0 | 34.9 |
| Qwen2.5-3B-Instruct | 45.4 | AutoRefine 44.3 | 25.7 |
The 7B gap is larger on multi-hop: 2Wiki 51.5 (ReSearch 47.6, Search-R1 41.4) and HotpotQA 44.6. On Bamboogle, GiGPO reaches 68.9 against FactAgent's 44.0, a clear single-set loss; the weighted average still favors FactAgent. ZeroSearch and ReSearch call Google Search; FactAgent uses local Wiki-18 and still wins on average.
Ablations on 7B: drop process rewards and mean EM falls from 51.2 to 40.5, multi-hop from 45.8 to 31.4. Skip sending utility back to Search: 45.4. Cluster by exact match only: 48.9. Ω=0.3 already beats outcome-only by 7.3 points; Ω=0.7 falls to 45.2, so the process term must not dominate.
At turn 8, ReAct prompts are about four times longer than FactAgent. On HotpotQA distractors, recall of reference triples rises by nearly 40% relative to the start of training; outcome-only GRPO shows no matching climb. An SFT cold start does not raise the ceiling (SFT+RL 49.5 versus direct RL 51.2) but prevents occasional garbled JSON actions. Clustering adds about 2.75 seconds per step; at rolloutn=6 a step takes 231.1s versus 225.2s for standard GRPO.
Dense signal for search RL usually means a learned process-reward model or clustering raw agent states (GiGPO). FactAgent clusters extracted facts and grows supervision from outcome statistics, without an extra reward model. The store also keeps multi-turn context near constant length, which matters for agents that search many times.
The cost is a new Assert action. The backbone must learn Search–Assert–Answer. Without RL, the 3B model averages 25.7, below one-shot RAG at 34.4. The workflow is not a prompting trick; RL has to weld it on.
There is no standalone limitations section. Visible bounds: retrieval is still the 2018 Wikipedia dump; Assert quality is tied to the backbone; cluster utility is association between "this cluster appeared" and a correct answer, not a causal effect. Embeddings confuse negation and numbers at high similarity; the extra rules that catch those cases are themselves a new failure mode.
The Bamboogle gap versus GiGPO is real; the average does not hide it. SFT cold start lowers the final score, while direct RL can break format, so training stability is not settled by one ablation. Richer fact types and continuous utilities are left for later.