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

Source-linked AI summary

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

arXiv:2608.05102v1Aug 5, 2026cs.AI

TL;DR

Long-horizon search-agent training often assigns uniform credit across heterogeneous actions, obscuring useful, erroneous, and redundant steps. ABSeeker introduces answer-backtracked step-level credit assignment and achieves strong results across search benchmarks, reaching 55.3% on BrowseComp with context management.

Problem
Existing long-horizon search-agent training treats trajectory steps uniformly, despite successful trajectories containing erroneous or redundant actions and failed trajectories containing useful actions.
Method
ABC recovers intermediate clues from verified answers, scores each search step against them, and uses the resulting rewards in ABC-SFT and ABC-GRPO.
Results
Across BrowseComp, BrowseComp-ZH, xbench, and GAIA-text, ABSeeker outperforms same-scale baselines and remains competitive with substantially larger agents, reaching 55.3% on BrowseComp with context management.
Takeaways & Limitations
ABC demonstrates the effectiveness of answer-backtracked step-level credit assignment for training long-horizon search agents.
Takeaways & Limitations
Experiments focus on a compact 4B model, leaving performance at larger backbone scales unexamined.

Abstract

from arXiv · show

Long-horizon search agents must make multiple sequential actions (steps) to search, retrieve, verify, and integrate evidence to reach a final answer. However, existing methods for training these agents typically treat all steps within a trajectory uniformly during both supervised fine-tuning (SFT) and reinforcement learning (RL), failing to distinguish useful actions from erroneous or redundant ones. In this paper, we propose Answer-Backtracked Credit Assignment (ABC), a fine-grained credit assignment framework for training long-horizon search agents by converting sparse trajectory-level outcomes into dense step-level supervision that rewards useful actions (even in failed trajectories) while suppressing erroneous or redundant actions. Specifically, given a potentially obscure query and its corresponding ground-truth answer, ABC first performs Answer-Backtracked Clue Recovery, which traces back from the answer to recover intermediate clues required to solve the question. It then applies Clue-Anchored Step Scoring to evaluate each search step against these clues, converting sparse binary outcome supervision into dense step-level rewards. Based on these rewards, we develop ABC-SFT, which reweights the loss of each turn, and ABC-GRPO, which uses the step-level scores as rewards in GRPO. Building on this framework, we train ABSeeker based on Qwen3.5-4B with only 8.5k examples. ABSeeker achieves 37.3% on BrowseComp and 39.1% on BrowseComp-ZH. With context management, the scores further improve to 55.3% and 52.9%, respectively, significantly outperforming same-scale (4B) agents and even matching the performance of larger ones (approximately 30B). These results demonstrate the effectiveness of answer-backtracked step-level credit assignment for training long-horizon search agents.

1 Introduction

Long-horizon search agents perform multi-step investigations, but existing training methods assign uniform credit across trajectory steps. ABC addresses this by recovering answer-linked clues and scoring individual steps, enabling improved training and strong ABSeeker results.

Motivation: Search agents iteratively formulate queries, inspect evidence, revise hypotheses, and adapt subsequent actions in multi-step investigations.Representative systems include OpenAI Deep Research, Tongyi DeepResearch, and MiroThinker.
Problem: Existing SFT and RL methods typically treat all trajectory steps uniformly, without distinguishing their individual contributions to the final outcome.This creates a fundamental credit-assignment challenge for long interaction horizons.
Method: ABC recovers intermediate entities, facts, and relations from the verified answer, then evaluates every search step against the clues required to solve the question.Its two stages are Answer-Backtracked Clue Recovery and Clue-Anchored Step Scoring.
Training: ABC rewards useful actions in failed trajectories while suppressing erroneous actions in successful ones, and supports ABC-SFT loss reweighting and ABC-GRPO step-level rewards.ABC-SFT reweights each turn according to its step reward, while ABC-GRPO incorporates step-level rewards into GRPO.
Results: 37.3% on BrowseComp and 39.1% on BrowseComp-ZH are achieved by ABSeeker based on Qwen3.5-4B using ABC-SFT followed by ABC-GRPO.With context management, performance further improves to 55.3% on BrowseComp and 52.9% on BrowseComp-ZH.

2 Related Work

The related work spans ReAct-style web agents extended to long-horizon search and recent methods for fine-grained credit assignment. ABC instead uses verified answers to derive dense process supervision through clue recovery and step scoring, supporting both SFT and GRPO training of ABSeeker.

Search Agents: ReAct interleaves reasoning, tool calls, and observations, while long-horizon search agents extend this recipe to dozens of retrieve–browse–integrate cycles across multiple sources.This paradigm targets knowledge-intensive tasks through dynamic interaction with external environments.
Credit Assignment for Search Agents: IGPO assigns step-level rewards from changes in ground-truth-answer likelihood, whereas CSO identifies critical steps by testing alternative actions and verifying outcomes.IGPO’s credit depends on model belief estimation and can fluctuate with policy updates.
Our Approach: ABC recovers intermediate evidence clues from verified answers, then scores each step by its contribution or error to produce dense process supervision.Answer-Backtracked Clue Recovery precedes Clue-Anchored Step Scoring.
Our Approach: ABC-SFT uses the step scores to reweight SFT losses, while ABC-GRPO uses them as rewards to train ABSeeker.The framework provides separate integrations with supervised fine-tuning and GRPO.

3 Method

ABC converts sparse final-answer supervision into dense, clue-anchored step rewards for long-horizon search trajectories. It uses recovered evidence chains to score actions and then trains with reward-weighted SFT followed by step-level reinforcement learning.

Training pipeline: ABC recovers intermediate evidence clues from each query and verified answer, then evaluates retained successful and failed trajectories against those clues.The recovered clues define meaningful progress toward the answer and provide fixed anchors for scoring every rollout.
Problem formulation: Trajectory-level rewards fail to credit useful steps in incorrect searches or penalize erroneous steps in correct searches.Useful actions may include evidence discovery, verification, and candidate filtering, while correct trajectories can still discard evidence.
Clue-Anchored Step Scoring: Each step starts at 1.0, accumulates behavior-specific deltas, and is clipped to [0, 2.0] by the clue-anchored scoring rubric.The scorer considers the step’s reasoning, tool call, tool response, original query, and complete clue set.
Clue-Anchored Step Scoring: A correct clue discovered in a failed trajectory receives positive credit, whereas incorrectly dismissing a correct clue in a successful trajectory incurs a penalty.This makes the scoring sensitive to intermediate action quality regardless of the final outcome.
Training objectives: ABC trains agents in two stages: reward-weighted supervised fine-tuning (ABC-SFT) followed by step-level reinforcement learning (ABC-GRPO).Both successful and failed trajectories are retained so high-quality steps are reinforced while erroneous steps are down-weighted or penalized.

4 Experiments

Experiments train ABSeeker with answer-backtracked supervision on 8.5K trajectories and evaluate it across five benchmarks. The method achieves leading 4B-agent results, benefits substantially from context management, and improves both SFT and RL training behavior.

Training Setup: ABSeeker uses Qwen3.5-4B, 8.5K SFT trajectories, trajectories capped at 200 steps, and RL with 1,000 questions and 8 rollouts each.DeepSeek-V4-Flash provides the backbone LLM for clue recovery and step scoring.
Main Results: 55.3% on BrowseComp, 52.9% on BrowseComp-ZH, 77.0% on xbench-2505, 46.0% on xbench-2510, and 81.6% on GAIA-text are ABSeeker’s best results among 4B search agents.ABSeeker also outperforms all reported 30B agents on xbench-2505 and GAIA-text.
Reward Distribution Analysis: Nearly 10% of steps in failed trajectories receive rewards above 1.0, while approximately 4% of steps in successful trajectories receive rewards below 1.0.These distributions show that failed trajectories can contain useful clues and successful trajectories can contain low-quality actions.
RL Training Dynamics: ABC-GRPO achieves consistently stronger BrowseComp validation performance than trajectory-level GRPO while producing longer search trajectories.The validation set contains 200 randomly sampled BrowseComp questions.
Effect of Context Management: 55.3% on BrowseComp and 52.9% on BrowseComp-ZH follow improvements from 37.3% and 39.1%, respectively, under context management.The setup uses a 256K-token maximum context and discard-all strategy for up to five rounds.
Ablation Results: ABC-GRPO consistently outperforms standard trajectory-level GRPO across all five benchmarks, while ABC-SFT improves several benchmarks over standard SFT and remains comparable on xbench-2505.The results attribute gains to emphasizing useful actions and suppressing erroneous ones throughout SFT and RL.

5 Conclusion

ABC trains long-horizon search agents with clue-anchored, step-level credit assignment derived from verified answers, implemented through ABC-SFT and ABC-GRPO. Future work will test larger backbones and extend the framework beyond web search to other long-horizon agent tasks.

Conclusion: ABC recovers intermediate evidence clues from verified answers and uses them to evaluate individual search steps instead of treating trajectory steps uniformly.This produces fine-grained credit assignment for long-horizon search-agent training.
Conclusion: ABC-SFT reweights each turn’s loss, while ABC-GRPO uses step-level scores as GRPO rewards to reward useful actions and suppress erroneous or redundant ones.The framework can reward useful actions even in failed trajectories while suppressing errors or redundancy in successful ones.
Future Work: Future work will scale ABSeeker beyond the compact 4B model and examine whether answer-backtracked credit assignment yields stronger gains with larger backbones.The paper attributes the current focus on a 4B model to computational constraints.
Future Work: The framework will also be extended beyond web search to long-horizon agent tasks whose outcomes can be backtracked into evidence, subgoals, or decision points.These intermediate structures would provide fine-grained process supervision.

A Training Details

ABSeeker is trained with SFT from Qwen3.5-4B on 8.5K scored trajectories, followed by RL from the SFT checkpoint on 1,000 filtered questions. The training setup specifies distinct data mixtures, rollout limits, batching, and optimization schedules for the two stages.

Supervised Fine-Tuning: 8.5K trajectories—5.5K correct and 3.0K incorrect—are used for three SFT epochs with a global batch size of 64.SFT initializes from Qwen3.5-4B and is implemented with Slime.
Supervised Fine-Tuning: 5 × 10−5 learning rate, cosine decay, 0.1 warmup ratio, 1 × 10−6 minimum learning rate, and 0.1 weight decay define the SFT optimization schedule.The optimizer is Adam.
Reinforcement Learning: 1,000 questions are used for RL: 200 have fewer than 100 turns, while 800 have at least 100 turns.RL initializes from the SFT checkpoint and is implemented with veRL.
Reinforcement Learning: 8 rollouts per question, a training batch size of 16, and up to 200 interaction turns define the RL sampling setup.Rollouts use 16 asynchronous agent-loop workers, temperature 1.0, and top-p = 0.95.

B Evaluation Details

The evaluation samples 200 BrowseComp questions for RL validation and averages three runs, with all evaluations allowing up to 200 interaction turns and using DeepSeek-V4-Flash to judge final-answer correctness.

Evaluation setup: 200 BrowseComp questions are randomly sampled for the RL validation set using seed 42.The sample is drawn from the full BrowseComp set due to computational constraints.
Evaluation setup: Three evaluation runs are averaged to reduce evaluation variance.
Evaluation setup: All evaluations allow up to 200 interaction turns and use DeepSeek-V4-Flash to judge final-answer correctness.The evaluator follows the prompt specified in Appendix C.3.

C Prompt Templates

The prompt templates operationalize ABC through answer-backtracked clue recovery, clue-anchored trajectory-step scoring, and final-answer evaluation. Together, they specify how to recover evidence-bearing clues, assign rubric-based step scores, and test whether a prediction matches the ground truth.

C.1 Answer-Backtracked Clue Recovery: Answer-Backtracked Clue Recovery reconstructs cite-backed intermediate steps linking the query and known answer.The prompt instructs the agent to recover clues from the question and verified answer before searching and verifying them.
C.1 Answer-Backtracked Clue Recovery: The recovery prompt prioritizes conditions such as events, dates, places, and entities, then requires explicitly explaining how they support the answer.It provides the query and known answer as inputs and forbids directly supplying the final answer during clue recovery.
C.2 Clue-Anchored Step Scoring: Clue-Anchored Step Scoring evaluates each trajectory step using only its context, reasoning, and tool call against the recovered core clues.The scoring prompt focuses on intermediate steps and key entities, with the correct answer and core clues supplied as reference inputs.
C.2 Clue-Anchored Step Scoring: Each step starts at 1.0, rewards finding or verifying a correct clue by +0.8, and rewards correctly ruling out a wrong candidate by +0.4.The rubric also penalizes incorrectly dismissing a correct clue by -0.8, and multiple criteria may apply to one step.
C.2 Clue-Anchored Step Scoring: The scorer returns only JSON containing a clipped score from 0.0 to 2.0, applicable criterion numbers, and a clue-specific explanation.The required score begins at 1.0, applies rubric deltas, and clips the result to [0, 2.0].
C.3 Evaluation Prompt: Final Answer Evaluation checks whether the predicted answer refers to the same entity or value as the ground truth.The evaluator receives the question, ground truth, and predicted answer, then decides correctness.
C.3 Evaluation Prompt: The evaluation prompt outputs only JSON with a Boolean correctness field and a brief reason.Its required format is {“correct”: true/false, “reason”: “brief explanation”}.