ABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignment
2026-08-05 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors propose a new way to train computer agents that search for answers by carefully judging each step they take, rather than just looking at whether the final answer is right or wrong. Their method, called Answer-Backtracked Credit Assignment (ABC), traces back from the correct answer to find important clues and scores each step based on how helpful it is. This helps the agent learn better by rewarding good actions and ignoring mistakes. Using ABC, they trained an agent called ABSeeker that performs much better than similar-sized agents and matches bigger ones on difficult search tasks.
long-horizon searchcredit assignmentsupervised fine-tuningreinforcement learningtrajectorystep-level supervisionAnswer-Backtracked Clue RecoveryClue-Anchored Step ScoringGRPOcontext management
Authors
Yijun Lu, Rui Ye, Jiajun Wang, Yuwen Du, Tian Jin, Songhua Liu, Siheng Chen
Abstract
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.