Credit Assignment for Search Agents: Why Final-Answer Rewards Alone Fall Short

The Dilemma of a Search Agent

Imagine researching a complex question in a library: "Which university did the undergraduate alma mater of the 2024 Nobel Physics laureates belong to?"

You wouldn't find the answer in one shot. You'd first search "2024 Nobel Physics laureates," find Hopfield and Hinton; then search "Hopfield's undergraduate institution," finding Swarthmore College; then "Hinton's undergraduate institution," finding Cambridge.

Every search step is an intermediate achievement. But if you only score the agent at the end—1 point for a correct answer, 0 for wrong—the agent gets no feedback on whether intermediate searches were good.

This is the core difficulty in training search agents: final rewards are too sparse, and intermediate effort goes unrewarded.

The Blind Spot of RLVR

The most popular method for training search agents today is RLVR (Reinforcement Learning with Verifiable Rewards): let the agent try repeatedly, reward correct answers, penalize wrong ones. Crude but effective.

The problem: when an entire group of attempts all fails, RLVR goes blind.

Suppose the agent tries the same question 8 times and gets all 8 wrong. But 3 of the attempts retrieved half of the key evidence, while the other 5 retrieved nothing. Judged by final answers, all 8 score 0—no difference. Yet the intermediate processes clearly differ: those 3 attempts are far better than the other 5.

RLVR's group-relative training mechanism completely fails here: when all rollouts share the same final score, the policy gradient is zero. The agent never learns that "retrieved half the evidence" beats "retrieved nothing."

It's like a student who got 8 problems all wrong, but 3 had the right approach and only the final step was miscalculated. If the teacher grades only final answers, the 8 problems are indistinguishable, and the student never learns which approach was more correct.

Intermediate Supervision: Scoring the Search Process

The paper's core idea: add intermediate retrieval rewards on top of the final reward.

But scoring intermediate searches is more complicated than it seems. The authors identify two key choices:

Choice 1: What should be rewarded?

The paper compares three intermediate signals:

1. Coverage (Cov): the fraction of annotated evidence retrieved. If 3 of 5 supporting passages are found, the score is 0.6. 2. Dependency-aware coverage (Cov-Dep): evidence must also satisfy prerequisites. Finding "Hinton's alma mater" doesn't count if "Hinton is a 2024 laureate" hasn't been retrieved yet—because you wouldn't know why to search for Hinton. 3. Answer Match (AM): whether retrieved text contains the reference answer.

Choice 2: How does the reward enter the policy update?

1. Scalar: add the intermediate reward to the final reward, changing the whole trajectory's total score—like adding a "process grade" to the student's overall score. 2. Local credit: assign the intermediate reward only to the search action that produced it, changing that action's advantage—like a teacher giving feedback on a specific step.

Combining the two choices yields 3×2 = 6 schemes.

Experimental Findings: Local Credit Wins

Testing with Qwen3-4B on 7 QA benchmarks, results were clear:

• All intermediate supervision beats pure outcome rewards: regardless of signal or assignment, adding intermediate rewards outperforms final-answer-only training.
• Local credit > scalar rewards: Cov-local (coverage + local credit) works best, with average F1 up 3.09 and multi-hop QA up 4.81.
• Signals must be aligned with their source action: moving the intermediate reward away from the search action that produced it eliminates the gains—credit must stay with the action that "did the right thing."
• Gains are largest when final answers tie: in exactly the scenario where RLVR fails entirely (all rollouts share the same final score), intermediate supervision helps most.

A Key Finding: Gains in "Retrieval," Not "Reasoning"

Agents trained with Cov-local retrieve more supporting evidence, but "answer accuracy conditioned on the same retrieved evidence" is about the same as outcome-only training. This suggests intermediate supervision mainly teaches the agent to search better, not to reason better.

The bottleneck of search agents is search, not reasoning—consistent with intuition: large models already reason well enough, provided they retrieve the right information.

Data Construction: Preserving Intermediate Annotations

A technical highlight of the paper is data construction. To know what each search step "should" retrieve, the authors built a pipeline:

1. Start from Wikidata entity relations, finding entity pairs co-occurring in the same sentence. 2. Keep each relation's source passage as supporting evidence. 3. Compose multiple relations into multi-hop questions, while preserving each sub-question, its supporting passages, and the dependencies between sub-questions.

Every question thus has complete "intermediate answer annotations"—what each step should retrieve, and which step is a prerequisite for which. These annotations compute intermediate rewards during training and enable analysis of what the agent actually retrieved during evaluation.

Why This Matters

"Credit Assignment" Is a Core Problem in Agent RL

Search agents are just one instance of agents. More generally, any multi-step decision-making agent faces credit assignment:

• Tool-calling agents: 5 tool calls, task failed—which call is to blame?
• Code generation agents: 10 functions written, program crashed—which one is broken?
• Multi-agent collaboration: 3 agents complete a task together, it fails—who contributed least?

The paper's framework—"what to reward" and "how to assign reward" as two dimensions—transfers directly to these settings.

"Sparse Rewards" Aren't Solved by Just "Adding Intermediate Rewards"

The paper reveals something deeper: the design of intermediate rewards is itself a dimension requiring careful study. Arbitrarily adding an intermediate reward may not help. You need to:

1. Choose the right intermediate signal (coverage vs. answer match vs. dependency-aware coverage). 2. Choose the right assignment scheme (scalar vs. local). 3. Ensure the signal is aligned with its source action.

This gives Agent RL practitioners a clear design checklist.

An Honest Assessment

1. Depends on annotated intermediate answers: Cov and Cov-Dep require knowing what each step "should" retrieve—hard to obtain in real scenarios, where real user questions have no standard intermediate answers. 2. Only tested on QA: search agents mainly do question answering; intermediate reward design for other tasks (navigation, manipulation) may differ entirely. 3. Coverage depends on corpus annotation: coverage requires pre-annotated supporting passages, limiting generality. 4. Implementation complexity of local credit: requires modifying RL training frameworks to support per-action advantages—not plug-and-play.

Still, the core insight—signal selection and credit assignment for intermediate supervision are two independent design dimensions—is valuable enough on its own.

Closing Thoughts

The post ends with an analogy: training a search agent is like training a detective. Outcome-only training means repeatedly solving cases—bounty for solved, nothing otherwise. Good police academies don't train this way—they decompose the process: were clues collected correctly, is the reasoning chain sound, is the evidence chain complete?

Intermediate supervision gives search agents "process evaluation." Not all effort shows up in final results, but good process deserves good feedback.

As Agent RL grows more complex, credit assignment will become ever more critical. This paper offers a clear starting point.

---

Paper: Beyond Outcome Rewards: Constructing and Assigning Retrieval Credit for Search Agents