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

Summary (Overview)

• Core Contribution: The paper proposes Answer-Backtracked Credit Assignment (ABC), a fine-grained credit assignment framework that converts sparse trajectory-level outcomes into dense step-level supervision for training long-horizon search agents. This addresses the fundamental limitation of existing methods that treat all steps within a trajectory uniformly.

• Key Innovation: ABC leverages the backtrackable nature of search tasks—given a verified answer, one can recover intermediate evidence clues (entities, facts, relations) that should have been discovered during the search process. These clues serve as fixed anchors for evaluating individual steps.

• Two-Stage Framework: ABC consists of (1) Answer-Backtracked Clue Recovery, which traces back from the verified answer to recover intermediate evidence clues, and (2) Clue-Anchored Step Scoring, which evaluates each search step against these clues to produce dense turn-level rewards.

• Training Methods: The framework enables two training approaches: ABC-SFT (reward-weighted supervised fine-tuning that reweights per-turn loss) and ABC-GRPO (step-level reinforcement learning using clue-anchored scores as rewards in GRPO).

• Key Results: The resulting model ABSeeker (trained on Qwen3.5-4B with only 8.5K examples) achieves 37.3% on BrowseComp and 39.1% on BrowseComp-ZH (improving to 55.3% and 52.9% with context management), outperforming all same-scale 4B agents and remaining competitive with larger ~30B search agents.

Introduction and Theoretical Foundation

Background and Motivation

Long-horizon search agents must execute multiple sequential actions (search, retrieve, verify, integrate) to reach a final answer. Systems like OpenAI Deep Research, Tongyi DeepResearch, and MiroThinker conduct multi-step investigations, iteratively formulating queries and revising hypotheses based on newly acquired information.

The fundamental challenge is credit assignment over long interaction horizons:

• Existing methods (SFT and RL) treat all steps within a trajectory uniformly, failing to distinguish useful actions from erroneous or redundant ones.
• Problem with uniform treatment: Even successful trajectories may contain erroneous or redundant steps, while failed trajectories may contain useful actions that retrieve decisive evidence.
• Key insight: Search tasks are naturally backtrackable—once the ground-truth answer is available, one can recover the key entities, facts, relations, and constraints that should have been discovered during the search process.

Theoretical Foundation

The paper formalizes the search trajectory and credit assignment problem. A search trajectory is defined as:

$$\tau = (s_{1}, s_{2}, \dots, s_{T}, a) \tag{1}$$

where $a$ is the final answer and each step $s_t$ contains the agent's reasoning, tool call, and tool response.

The standard trajectory-level reward is sparse and binary:

$$r_{\text{ans}}(\tau) = \begin{cases} 1, & \text{if } a = a^{*}, \\ 0, & \text{otherwise}. \end{cases} \tag{2}$$

Two fundamental credit-assignment failures arise from this sparse signal:

1. Failed trajectories: Useful intermediate steps (correct evidence discovery, verification, candidate filtering) receive zero reward despite contributing to progress.
2. Successful trajectories: Erroneous intermediate conclusions or steps that discard useful evidence are not distinguished from genuinely informative actions.

Methodology

3.1 Answer-Backtracked Clue Recovery

Given a training question $(q, a^{*})$, the recovery process maps it to a set of clues:

$$\mathcal{C} = \{c_{1}, c_{2}, \dots, c_{K}\} \tag{3}$$

where each $c_k$ is a verifiable piece of intermediate evidence (entity, fact, attribute, or relationship) connecting the query to the verified answer.

Key properties:

• The recovery uses an active ReAct loop: the recovery model conducts web searches and visits pages, tracing evidence from the answer back toward the query.
• Each clue is anchored in actual web content through verification.
• This leverages the fact that benchmarks like BrowseComp provide unique and verifiable answers, which offer a clear endpoint for evidence backtracking.

3.2 Clue-Anchored Step Scoring

Each step $s_t$ is evaluated against the recovered clue set $\mathcal{C}$. The scorer receives:

1. The current step (reasoning, tool call, tool response)
2. The original query $q$
3. The complete clue set $\mathcal{C}$

The step reward is computed as:

$$r_{t} = \operatorname{clip}\left(1.0 + \sum_{j \in \mathcal{A}_{t}} \Delta_{j}, 0, 2.0\right) \tag{4}$$

where $\mathcal{A}_{t}$ is the set of scored behavior instances at step $t$.

Scoring Rubric:

Each step starts with a base score of 1.0, ensuring reasonable exploration without obvious error is not penalized.

3.3 Training Methods

ABC-SFT (Reward-Weighted Supervised Fine-Tuning)

The SFT objective reweights each step's loss based on its reward:

$$\mathcal{L}_{\mathrm{SFT}}(\theta) = -\sum_{t=1}^{T} w(r_{t}) \sum_{j} \log p_{\theta}\left(x_{t,j} \mid x_{t,<j}\right) \tag{5}$$

where the step-level weight uses a sigmoid function: $w(r_t) = \sigma(\alpha \cdot (r_t - \beta))$, with $\alpha$ controlling sharpness and $\beta$ the neutral baseline. In practice, $w(r_t) = 2\sigma(2(r_t - 1))$, mapping neutral reward $r_t = 1.0$ to weight 1.0.

ABC-GRPO (Step-Level Reinforcement Learning)

For each rollout $i$, the reward at step $t$ is $R_{i,t} = r_{i,t}$. Rewards are normalized within each rollout group, and the discounted step-level advantage is:

$$A_{i,t} = \sum_{k=t}^{T_{i}} \gamma^{k-t} \widehat{R}_{i,k} \tag{7}$$

where $\gamma = 0.25$ controls how future step rewards propagate to earlier decisions. The standard clipped GRPO objective is used with step-specific advantages instead of trajectory-level ones.

Empirical Validation / Results

Experimental Setup

• Training data: 8.5K trajectories from OpenSeeker (5.5K correct, 3.0K incorrect), with maximum 200 steps per trajectory
• Backbone: Qwen3.5-4B
• SFT: 3 epochs, batch size 64, learning rate $5 \times 10^{-5}$
• RL: 1,000 questions, 8 rollouts each, learning rate $1 \times 10^{-6}$, KL coefficient 0.001
• Scoring/Recovery model: DeepSeek-V4-Flash

Main Results

Table 2: Performance comparison across five benchmarks (BrowseComp and BrowseComp-ZH results with * denote no context management):

Key findings:

• ABSeeker achieves the best performance among all 4B search agents on every benchmark
• Outperforms all reported 30B agents on xbench-2505 and GAIA-text
• Surpasses several 30B systems on BrowseComp and BrowseComp-ZH
• Despite training exclusively on BrowseComp-style questions, the model generalizes effectively to xbench and GAIA

Reward Distribution Analysis

Analysis of step-reward distributions over the 8.5K SFT trajectories reveals:

• Successful trajectories contain approximately 4% low-quality steps (reward < 1.0)
• Failed trajectories contain nearly 10% high-quality steps (reward > 1.0) that discover or verify useful clues despite ultimately producing incorrect answers
• Trajectory-level supervision would incorrectly reinforce erroneous actions in successful trajectories and penalize useful actions in failed ones

RL Training Dynamics

ABC-GRPO achieves consistently stronger BrowseComp performance after training begins while producing longer search trajectories, demonstrating that step-level credit assignment improves both search accuracy and exploratory behavior.

Ablation Study

Table 3: Ablation of ABC-SFT and ABC-GRPO (evaluated without context management):

ABC-SFT improves over standard SFT on four of five benchmarks, and ABC-GRPO consistently outperforms standard trajectory-level GRPO across all benchmarks.

Theoretical and Practical Implications

Theoretical Implications

1. Fine-grained credit assignment matters: The results demonstrate that distinguishing useful actions from erroneous ones—even within trajectories of the same outcome class—provides significantly better training signal than trajectory-level supervision.

2. Backtrackability as a general principle: The paper establishes that tasks with verifiable final answers can be backtracked to recover intermediate evidence, providing a principled basis for process supervision. This principle could extend beyond web search to any long-horizon agent task with verifiable outcomes.

3. Fixed anchors for evaluation: The recovered clues serve as fixed, answer-backtracked evaluation criteria that remain stable during training, unlike model-dependent signals (e.g., IGPO's likelihood-based credit) that fluctuate with policy updates.

Practical Implications

1. Data efficiency: ABSeeker achieves competitive performance with only 8.5K training examples, demonstrating that high-quality process supervision can compensate for limited data.

2. Scalability: The approach works with a compact 4B model, suggesting that fine-grained credit assignment is a promising direction for democratizing capable search agents.

3. Context management synergy: The combination of ABC with context management (256K token budget, discard-all strategy) yields substantial improvements (37.3% → 55.3% on BrowseComp), indicating complementary benefits.

4. Cross-benchmark generalization: Training on BrowseComp-style questions generalizes to xbench and GAIA benchmarks, showing that the learned search behaviors are transferable.

Conclusion

The paper presents Answer-Backtracked Credit Assignment (ABC), a framework that addresses the credit assignment challenge in long-horizon search agent training by:

1. Recovering intermediate evidence clues from verified answers
2. Evaluating each search step against these clues to produce dense step-level rewards
3. Using these rewards to reweight SFT losses (ABC-SFT) and provide step-level GRPO advantages (ABC-GRPO)

Key takeaways:

• ABC rewards useful actions in failed trajectories while suppressing erroneous actions in successful ones
• The trained ABSeeker (4B parameters) outperforms all same-scale baselines and remains competitive with ~30B agents
• Step-level supervision improves reward quality, training dynamics, and long-horizon exploration

Future directions:

1. Scaling to larger models: Examine whether answer-backtracked credit assignment brings stronger gains under higher model capacity
2. Extending to other domains: Apply the framework to other long-horizon agent tasks where final outcomes can be backtracked into intermediate evidence, subgoals, or decision points

Availability: Code is available at https://github.com/PolarSeeker/ABSeeker and the model at https://huggingface.co/PolarSeeker/ABSeeker-4B-RL.