ABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignment

Yijun Lu, Rui Ye, Jiajun Wang, Yuwen Du, Tian Jin, Songhua Liu, Siheng Chen

ABSeeker uses answer-backtracked clues to assign fine-grained rewards to individual search steps, outperforming larger agents.

How can we improve credit assignment for long-horizon search agents by using the final answer to retroactively identify which intermediate search steps were actually useful?

Long-horizon search agents often fail because they are trained on entire trajectories, treating every step as equally correct or incorrect regardless of its actual contribution to the final answer. The authors introduce Answer-Backtracked Credit Assignment (ABC): a framework that traces back from a verified answer to identify intermediate evidence clues, then scores each search step based on its progress toward those specific anchors. This dense, step-level supervision allows the model to learn from useful actions even in failed trajectories, enabling a 4B-parameter model to outperform significantly larger search agents on complex benchmarks.

Paper Primer

The core mechanism, Clue-Anchored Step Scoring, acts like a rubric-based grader: it compares each step's reasoning and tool output against a set of required evidence clues, assigning a scalar reward that reinforces productive exploration and penalizes redundant or erroneous moves.

ABSeeker achieves state-of-the-art performance for 4B-parameter search agents.

Performance on BrowseComp and BrowseComp-ZH benchmarks. 55.3% and 52.9% accuracy respectively, outperforming larger ~30B models in several categories.

The training pipeline applies this scoring in two stages: ABC-SFT reweights the loss of each turn based on its step score, and ABC-GRPO uses these scores as direct rewards for reinforcement learning, ensuring the policy is optimized for process quality rather than just final outcomes.

Why is trajectory-level supervision insufficient for long-horizon search?

It fails to distinguish between heterogeneous actions; a successful trajectory may contain flawed steps, while a failed one may contain decisive evidence-gathering steps that are incorrectly penalized by a binary outcome.

How does the model handle trajectories that ultimately fail?

By using answer-backtracked clues as fixed reference points, the system can identify and reward individual steps that successfully discovered or verified evidence, even if the final answer submitted by the agent was incorrect.

Researchers can now move beyond binary outcome-based training for agents by using verified answers to generate dense, process-level supervision, effectively turning any task with a verifiable result into a source of fine-grained training data.

Motivation and Performance Overview

Uniform step weighting hampers long‑horizon search agents, motivating fine‑grained credit assignment.

Long‑horizon search agents must orchestrate many sequential actions—searching, retrieving, verifying, and integrating evidence—to arrive at a final answer. Existing training pipelines, whether supervised fine‑tuning (SFT) or reinforcement learning (RL), treat every step in a trajectory identically, ignoring that some actions are decisive while others are redundant or erroneous. This uniform step weighting wastes supervision and impedes learning of the most critical search behaviors.

**Figure 1.** ABSeeker achieves the best performance among 4B models and remains competitive with several larger search agents. Striped regions indicate results with context management enabled.

Training long‑horizon search agents is inefficient because uniform step weighting fails to distinguish useful actions from noisy or redundant ones.

The core inefficiency stems from treating every step equally; fine‑grained, answer‑backtracked credit is needed to train effective long‑horizon search agents.

The ABC Training Framework

Uniform answer-level rewards leave intermediate steps untrained, so we introduce dense step credit.

Uniform answer‑level rewards give no guidance to intermediate decisions, so learning ignores useful steps.

Instead of rewarding only the final answer, ABC assigns a dense credit to each step by checking how it aligns with evidence clues traced back from the verified answer.

Step $s_{1}$ discovers clue $c_{1}$ → +0.8 (Table 1).

Step $s_{2}$ discovers clue $c_{2}$ → +0.8.

Step $s_{3}$ submits the verified answer → +1.0.

Base score 1.0 + 0.8 + 0.8 + 1.0 = 3.6 → clipped to 2.0.

Even if the final answer were wrong, steps that uncovered correct clues would still earn positive credit, guiding the policy toward useful sub‑behaviors.

How does ABC differ from the standard answer‑level reward?

Standard reward $r_{\text{ans}}$ is a binary signal attached only to the final answer, so every intermediate decision receives the same gradient signal. ABC replaces this with a per‑step reward $r_{t}$ that reflects whether each action contributed to the verified evidence chain, providing dense, direction‑specific feedback.

Each step is evaluated against the recovered clue set; productive actions add positive deltas, mistakes subtract, and the total is clipped to keep rewards bounded.

Base score 1.0.

+0.8 for discovering the correct clue (Table 1).

+0.4 for correctly ruling out a wrong candidate.

Total = 1.0 + 0.8 + 0.4 = 2.2 → clipped to 2.0.

Clipping ensures that even a step that performs many good actions cannot exceed the maximum reward, keeping the learning signal on a stable scale.

Is this scoring just another form of reward shaping?

No—reward shaping typically adds a heuristic term to a scalar reward. Here the reward is computed deterministically from a verified evidence set, and each delta corresponds to a concrete, interpretable behavior, making the signal transparent and grounded in the task.

**Figure 2.** Overview of the training pipeline, which consists of two core stages. **Stage 1: Answer-Backtracked Clue Recovery** recovers intermediate evidence clues from the query and its verified answer. **Stage 2: Clue-Anchored Step Scoring** evaluates each step against the recovered clues and produces dense, fine-grained rewards for each step, in contrast to the sparse answer-level reward.

**Figure 3.** An illustrative example of **Answer-Backtracked Clue Recovery** and **Clue-Anchored Step Scoring**. **Left:** Given a multi-constraint query and the verified answer, the recovery produces six intermediate evidence clues ($c_1$–$c_6$) that form a verified evidence chain connecting the query to the answer. **Right:** Selected steps from a sampled trajectory are evaluated against the recovered clue set, with rewards reflecting the quality and contribution of each step.

Table 1 enumerates the scoring rubric: discovering a correct clue adds +0.8, ruling out a wrong candidate adds +0.4, incorrectly dismissing a correct clue subtracts –0.8, and answer submission adds +1.0 or –1.0.

Empirical Evaluation

ABSeeker’s step‑level credit assignment yields consistent gains across benchmarks.

We train on OpenSeeker trajectories (≤200 steps) using Qwen3.5‑4B as the backbone. Supervised Fine‑Tuning runs for three epochs on 8.5 K trajectories, and RL samples 1 K questions with eight rollouts each. All ABC components rely on DeepSeek‑V4‑Flash.

ABSeeker reaches 55.3 % accuracy on BrowseComp, surpassing all reported 4 B search agents.

Table 2 shows ABSeeker’s 55.3 % score, the highest among 4 B agents.

OpenSeeker supplies a large corpus of search trajectories, both successful and failed, that serve as the raw supervision for credit assignment.

How does OpenSeeker differ from a standard web‑search log?

OpenSeeker records the full sequence of tool invocations and the final answer, whereas a typical log only stores the query and final result. This granularity enables step‑level credit signals.

During supervised fine‑tuning, each step receives a back‑tracked credit based on whether it contributed to the final verified answer.

Why not simply weight all steps by the final outcome?

Uniform weighting would give the same signal to useless steps in a successful run and to useful steps in a failed run, blurring the learning signal. ABC‑SFT isolates the truly helpful actions.

In reinforcement learning, ABC‑GRPO replaces trajectory‑level returns with step‑level credits, guiding the policy toward actions that demonstrably improve the answer.

How does ABC‑GRPO avoid the high variance typical of step‑wise rewards?

Credits are deterministic functions of the trajectory’s final answer, so they do not introduce stochastic noise beyond the usual policy sampling variance.

**Table 1.** Performance comparison of various models on different benchmarks, categorized by model type and parameter size.

**Figure 4.** Distribution of step rewards across the 8.5K SFT trajectories. The left half shows successful trajectories, while the right half shows failed trajectories. Each bar represents one-tenth of the steps in a trajectory, ordered from earliest to latest; for example, 0–10% represents the first 10% of steps in a trajectory. Red, gray, and green denote low-quality steps with $r_t < 1.0$, neutral steps with $r_t = 1.0$, and high-quality steps with $r_t > 1.0$, respectively.

**Figure 5.** RL training dynamics. **Left:** Performance during training. **Right:** Average number of interaction turns.

ABC consistently outperforms uniform training baselines across model sizes.

Ablations and Robustness

Key ablations and context‑budget analysis for the proposed credit‑assignment framework.

Recall that the paper’s core idea is to give credit only to those search steps that actually lead to the final verified answer, rather than treating every step equally.

**Figure 6.** Performance under different context budgets.

Table 3 compares standard fine‑tuning (SFT) and GRPO against their ABC‑augmented counterparts across five benchmarks. In every case the “+ABC‑SFT” and “+ABC‑GRPO” rows achieve higher scores than the plain “+Standard” rows, confirming that removing the ABC credit‑assignment component degrades performance.

Read the original paper

Open the simplified reader on Paperglide

Browse all simplified papers