The credit-assignment problem in long-horizon search
Search agents increasingly handle complex tasks through multi-turn interactions with external environments. They interleave reasoning with search and tool use, while correctness is often determined only after the full interaction through a verifiable final answer. This makes supervision naturally trajectory-level: a rollout is sampled first, then judged at the end.
With outcome-level rewards, reinforcement learning inherits a flat credit-assignment problem. The final reward gives one signal for the whole trajectory, making it difficult to attribute the result to individual turns or actions. This problem becomes sharper in long-horizon search, where early queries and observations can change later states, and different paths can still lead to the same final answer.
If one trajectory-level advantage is applied across the whole sequence, locally harmful actions in successful trajectories can be reinforced, while useful intermediate behaviors in failed trajectories can be penalized. The final label may be correct, but the policy update can still be noisy because it does not distinguish which parts of the process actually mattered. This motivates finer-grained credit assignment and process-level reward signals.
Design Candidates for Turn-Level Credit
Turn-level credit can be defined in several ways. The table below treats them as design candidates rather than a ranking: each candidate makes a different choice about where the signal comes from, what it can supervise, and what dependency it introduces.
| Candidate | Signal source | What it can supervise | Main limitation |
|---|---|---|---|
| Ground-truth documents / information gain | Whether retrieved content matches the ground-truth evidence path, plus redundancy penalties | Dense feedback for search and retrieval efficiency | Requires ground-truth documents or paths; may reward retrieval more than reasoning |
| Retrospective critic | A model judges after the rollout whether each search step helped the final answer | Step-level credit without manually writing every heuristic | Requires an additional critic and evaluation pass, and its judgments may not transfer reliably across task types or search patterns |
| Final-answer probability change | Change in the policy model's probability of the exact ground-truth final answer after a turn | A direct attempt to connect each turn to final-answer progress | Exact-match probability is not a reliable measure of semantic progress; early useful clues may not immediately increase the final-answer probability |
| Sparse answer trigger | Give positive reward to steps that produce the correct answer | Simple and directly verifiable signal when the answer is produced | Still sparse; mostly credits answer production rather than earlier search work |
| Learned reward model | Human annotators, rule-based checks, or LLMs label attributes such as tool-selection quality or query quality, and a reward model is then trained | After labeling, the reward model can approximate the original evaluation process for batch scoring, reducing the cost of subsequent large-scale per-sample evaluation | Depends on label quality, evaluator coverage, and transfer |
| Same-state grouping | Group the same turn across rollouts whose task-specific states are judged identical, then compute relative advantage within the group | Normalizes relative advantages among actions taken from a shared state | State definitions are task-specific and difficult to design reliably for most tasks |
| Monte Carlo tree search / rollout-tree grouping | Build a rollout tree by grouping trajectories with common prefixes; use leaf outcome rewards and propagate values to parent nodes | Shares outcome information across branches with the same prefix and supports step-level advantage estimation | Requires tree construction during rollout and a value-aggregation rule, adding search and rollout cost |
| Answer-Conditioned Self-Teacher | Compare the probabilities that the same model assigns to sampled actions under ordinary and answer-conditioned contexts, then use these probability signals to reweight trajectory-level advantage | Uses an answer to allocate credit across turns without changing the policy target | Requires a correct and useful answer |
Why Answer-Conditioned Self-Teacher Credit Fits Long-Horizon Search
Swipe horizontally to inspect the diagram at a readable size.
Long-horizon search creates a credit-assignment problem: a trajectory may contain many queries, tool calls, and evidence-gathering steps, while the final answer only tells us whether the whole trajectory succeeded. The training signal therefore needs to remain tied to the final answer while providing guidance for intermediate turns and preserving the ability to explore different paths.
The answer-conditioned self-teacher is used only for this credit-assignment role. During rollout, the student uses the ordinary task context. After the trajectory is collected, the same model is evaluated with the verified answer as additional context. The teacher view does not generate a target rollout for the student to imitate; it only evaluates actions that have already occurred.
This separation preserves exploration. Because the answer is not available when the rollout actions are generated, the student can still try different queries, tool calls, and evidence-gathering paths. Each trajectory can then receive guidance based on its own actions, rather than being forced toward a single answer-conditioned path.
The resulting signal is directional rather than absolute. After seeing the answer, the model may become more inclined toward a particular action that occurred in the trajectory, or that action may become less favored. The signal can therefore increase or reduce the credit assigned to that turn, without claiming that the action definitely caused the final answer.
The adjustment remains limited. The self-teacher signal only makes a small change to how the final-reward weight is distributed across turns; the final reward remains the dominant training signal. This makes it harder for an intermediate proxy to improve independently and take over the optimization direction, reducing the risk of reward hacking.
The key idea is therefore not to replace final-answer supervision or to make the student imitate a policy that has seen the answer. It is to use the answer after rollout to calibrate how the dominant final-reward signal is distributed across a long trajectory.
At a high level, the training loop is straightforward. The agent first samples on-policy multi-turn rollouts. The final answer of each trajectory is then checked, producing an outcome. The same model then evaluates each sampled trajectory from the ordinary student view and the answer-conditioned teacher view. The difference in how the two views treat each observed turn becomes a turn-level guidance signal. That signal is used to adjust how much of the original sequence-level advantage each turn inherits, after which the policy is updated with these calibrated weights. The final outcome still determines whether the trajectory is reinforced or penalized; the additional signal only refines the allocation across turns.
Why the Design Still Needs Stability Guards
Turn-level probability signals are useful only when their direction is reliable. In practice, many per-turn evidence scores sit near zero. Their sign can be dominated by estimation noise rather than genuine teacher-student disagreement. Passing these weak signals directly into training would add sign-aware perturbations with little semantic meaning.
The first guard is Low-SNR filtering. Scores close to zero are filtered out, so only evidence differences with sufficient magnitude affect the turn-level weight.
The second guard is clipping. It limits the magnitude of turn-level weight adjustments, prevents outliers from dominating the policy update, and keeps the update compatible with standard policy optimization.
In training with MoE models, routing replay can help the policy update reproduce expert routing, but the replayed logits are not suitable for computing the evidence score. If these replayed outputs are used directly to compare ordinary and answer-conditioned contexts, score differences may come from routing replay rather than answer conditioning itself. The evidence score should therefore be recomputed without routing replay, using the same evaluation path for the ordinary and answer-conditioned contexts; the policy update can still use the standard replay log-probabilities. This keeps the credit-assignment signal attributable to answer conditioning rather than extra variation introduced by routing replay.
Together, these guards make the design less like a raw auxiliary reward and more like a controlled credit-calibration layer on top of outcome-level reinforcement learning.
Extending to Tasks Without Ground-Truth Answers
The same credit-assignment idea can be extended to tasks without a single verified final answer, as long as the task provides a small, task-relevant conditioning signal. The signal does not need to prescribe the full solution or reveal the correct trajectory. It only needs to give the self-teacher a lightweight task reference.
For general tool-using agents, this signal could be a short list of key tools that are relevant to the task. The list need not cover every tool that may be useful, and it does not specify how any particular tool should be used. It serves only as a lightweight task reference, while leaving the agent free to explore different call sequences and evidence-gathering paths.
For coding agents, the signal could consist of a task-type description or an error hint rather than a ground-truth solution. An error hint might provide only a local constraint or failure clue. These signals only provide additional directional information; the agent still has to inspect files, make code changes, and run tests to determine whether the changes are correct.