Hindsight Evidence Rewards for Multi-Hop Retrieval Agents

Language models that answer multi-hop questions by searching step by step, such as "In what city was the director of Inception born?", are now commonly trained with reinforcement learning. They receive a reward only when the final answer is right. That signal is sparse. A search trajectory that correctly found the Inception article but then issued a bad second query gets the same zero as one that never got started. Recent attempts to give credit for each search step either depend on expensive external judges or on hand-labeled "gold" documents. We propose a third option that is cheap and needs no labels. Within each batch of attempts at the same question, the evidence gathered by the attempts that succeeded becomes a reference. Every other attempt is then rewarded, one step at a time, for how much closer its own evidence has moved toward that reference. Closeness is measured in the embedding space the retriever already uses, so a different passage that states the same fact still earns credit.

This carries the central lesson of semantic reward optimization in text generation over to evidence sets. That lesson is that exact-match rewards are unforgivingly sparse, and that similarity in a continuous embedding space gives dense, lenient partial credit. Rewarding exact gold document IDs is the evidence-level analogue of BLEU. Embedding coverage of hindsight evidence is the analogue of BERTScore. Because passage vectors are computed by the dense retriever anyway, the reward costs a few matrix multiplications per step, not a forward pass through a language model.

Core Claim

Multi-hop retrieval fails at the second and later hops because the bridge entity is not in the question (Ma et al. (2025); IRCoT). This rules out the obvious cheap semantic reward, which is similarity between retrieved passages and the question or the answer string. The passage saying "Nolan was born in London" looks nothing like "Inception". The only thing that reliably resembles a good hop-2 passage is another good hop-2 passage.

Our claim is that successful sibling rollouts supply exactly that at training time. A step-level reward built on embedding coverage of their evidence, which we call hindsight evidence coverage, should do three things. It should improve accuracy on 3–4 hop questions over outcome-only reinforcement learning at essentially no added compute. It should match gold-document bonuses without using document labels. And it should beat an otherwise identical reward that uses exact passage-ID matching.

Mechanism

Consider one question. The policy samples a group of rollouts, as in Group Relative Policy Optimization (GRPO, a reinforcement learning method that scores each sample against the others drawn for the same prompt). Some rollouts reach a correct answer. For each successful rollout $j$, let $R_j$ be the set of embedding vectors of the passages it retrieved. To limit lucky guesses, we keep a rollout only if the answer string appears in its evidence. Successful sets from earlier epochs are kept in a small per-question buffer. This means questions the current group fails on can still be shaped.

For any rollout whose accumulated evidence after step $t$ has embeddings $E_t$, define its coverage potential as the best match to any reference path:

$$\Phi(E_t) = \max_j \frac{1}{|R_j|}\sum_{r \in R_j} \max_{e \in E_t} \cos(e, r)$$

The inner term is passage-level BERTScore recall. Each reference passage is matched to its nearest retrieved passage. Taking the maximum over $j$ allows several valid reasoning paths.

The per-step reward is the gain in coverage minus a fixed search cost $c$. On top of this, the usual terminal correctness reward $A$ is added at the end:

$$r_t = \Phi(E_t) - \Phi(E_{t-1}) - c.$$

The shaping terms telescope to $\Phi(E_T)-\Phi(E_0)$, where $E_T$ is the final evidence set and $E_0$ is empty. This bounds how far shaping can pull the policy away from the correctness objective. It also means a redundant search that re-finds hop-1 content earns exactly $-c$. That directly targets the repeated-sub-query failure catalogued by EVO-RAG.

A full optimal transport variant, following the token-level transport rewards of OTRL, is a secondary arm. It tests whether enforcing one-to-one matching between hops adds anything beyond greedy recall.

Relation to Prior Work

Our closest competitors are the step-level semantic rewards for search agents.

InfoReasoner rewards each retrieval for reducing uncertainty over answer clusters. It samples 12 answers and groups them with an entailment model, which makes training 1.9× slower than standard reinforcement learning. Its authors name embedding-space geometry as a future replacement. We do not estimate answer uncertainty at all. We measure evidence progress against hindsight references, which removes both the answer sampling and the entailment model.

CRAFT rewards reasoning faithfulness through an LLM judge inside the rollout loop. It reports +17.50% EM on MuSiQue, but judge cost confined it to 20k samples and ≤7B students. Our reward needs no judge.

EVO-RAG gives a retrieval bonus for gold-labeled documents and penalizes lexical overlap between sub-queries. It supplies the failure taxonomy we target, but its intermediate signal is exact-ID and label-dependent. That is precisely the design we replace.

FrugalRAG rewards stopping at a target length. It motivates our search cost but ties efficiency to trajectory length rather than evidence content.

The search-and-self-training line supplies the idea of mining successful trajectories. GRAT and CoRAG both mine successful search trajectories, through tree search and rejection sampling respectively. Both then use them only as supervised fine-tuning targets. We instead use them as a within-group reference that yields dense credit for failed rollouts, which is where most of the learning signal is lost.

DPRM derives step rewards without labels but requires a knowledge graph. Our reward works over unstructured passages.

Direction 1 supplies the method and a caution. Yasui et al. and Nakatani et al. show that embedding-based rewards give credit to valid paraphrases that string metrics zero out. Yasui et al. also documents reward gaming: policies appended words to inflate similarity. The evidence-level analogue is padding the context with many near-reference passages. This is why the per-search cost and the recall form of $\Phi$ matter. A passage adds reward only if it covers a reference passage that nothing else yet covers.

Research Program

We will train an 8B instruction model, Llama-3.1-8B-Instruct as used by CoRAG, as a search agent with a dense Wikipedia retriever and a maximum of 6 searches. Training uses GRPO on the combined HotpotQA, 2WikiMultiHopQA, and MuSiQue training sets, with document labels removed from all reward computation. Labels are used only for evaluation.

The analysis has three parts. First, we measure where the reward helps, broken down by hop count using MuSiQue's 2–4 hop structure. Second, we measure how often credit goes to non-gold but equivalent passages. To check whether this credit is deserved, we hand-inspect a 300-passage sample of passages that received high coverage but are not gold. Third, we examine how reward quality degrades on questions where no rollout ever succeeds.

Baselines

The naive reference points are prompting-only agents with the same retriever. We run ReAct and IRCoT with the same 8B model and search limit. FrugalRAG reports ReAct at 64.20% MBE with 2.76 searches on HotpotQA. The "do nothing" reinforcement learning baseline is outcome-only GRPO: identical in model, data, group size, and steps, with the terminal correctness reward and search cost but no shaping. The proposal must beat this baseline to justify itself.

The strongest existing method on this exact question is InfoReasoner's semantic information-gain reward. Its paper reports 39.1% average accuracy across 7 QA benchmarks against 33.7% for Search-R1 and 36.9% for AutoRefine. We reimplement it with $M=12$ and the same entailment clustering, on our model and data. We compare at two budgets: equal optimizer steps and equal wall-clock training time. Beating it means matching its accuracy at equal steps while using clearly less wall-clock time, or exceeding it at equal wall-clock time.

For reference points we will not reproduce, we cite reported numbers only. FrugalRAG reports 68.47% MBE with 2.05 searches on HotpotQA. GRAT reports 66.8% accuracy on 2WikiMultiHopQA for self-trained Llama3-8B. CoRAG reports MuSiQue retriever recall of 47.1%. We found no reported result on Lacuna for Bamboogle for any of these systems.

We also run a gold-document bonus in the style of EVO-RAG. It gives +1 per newly retrieved labeled supporting passage, uses the same scale and search cost, and is tuned with the same small sweep over reward weight. This is a privileged-information upper reference.

Two ablations isolate the key ingredient. Exact-ID hindsight uses the same successful-sibling references but credits only identical passage IDs, which removes the semantic leniency. Answer-similarity shaping rewards cosine similarity between evidence and the gold answer string, which removes the hindsight reference. All reward variants get the same three-value sweep over $c$ and the shaping weight, selected on a held-out dev split.

Why not just…?

Why not just use outcome-only GRPO, which already works? It is the default, and on 2-hop HotpotQA it may be enough. The case for shaping rests on longer chains, where a correct first hop followed by a wrong second hop receives no credit. MuSiQue shows single-hop shortcuts cost about 30 F1 relative to HotpotQA, per MuSiQue. The per-hop-count breakdown settles this. If shaping does not improve 3–4 hop EM over outcome-only GRPO, the proposal fails.

Why not just use gold-document labels, as EVO-RAG does? On these three training sets the labels exist, and a gold bonus is a real threat in-domain. We expect to roughly match it, not beat it. The value of our reward is that it needs no labels. We test this directly by comparing both methods on Bamboogle, which is designed to resist shortcuts, and on held-out MuSiQue 4-hop questions. If the gold bonus wins clearly everywhere, we would state that our contribution is limited to settings without labels.

Why not just fine-tune on the successful trajectories, as GRAT and CoRAG do? This uses the same hindsight data with less machinery. However, it discards the signal in failed rollouts. CRAFT also reports that supervised fine-tuning on multi-hop chains degrades faithfulness. We include rejection-sampling fine-tuning on the identical successful set as an extra arm, matched in the number of trajectories.

Why not just reward similarity to the question or answer? A good second-hop passage need not resemble either one; that is the core of the multi-hop gap. The answer-similarity ablation measures this. We predict it helps hop-1 recall but not hop-2+ recall.

Proposed Experiments and Decisive Checks

We evaluate EM and F1 on HotpotQA, 2WikiMultiHopQA, MuSiQue, and Bamboogle. Alongside accuracy we report supporting-passage recall per hop, searches per question, and the fraction of repeated sub-queries. We also report the added wall-clock cost of the reward relative to outcome-only GRPO, which we expect to be under 10% but will measure rather than assume.

Four results decide the question. First, hindsight coverage must beat outcome-only GRPO on MuSiQue 3–4 hop EM across three seeds. Second, it must beat exact-ID hindsight; if the two tie, the semantic ingredient contributes nothing and the idea reduces to sibling-ID matching. Third, it must match InfoReasoner's accuracy at much lower training cost. Fourth, the hand audit must show that high-coverage non-gold passages usually contain the needed fact. If instead they are topical near-misses, the reward is being gamed in the way Yasui et al. warns about.