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
cs.AI
2026-08-06
Answer-Backtracked Credit Assignment scores each search step against clues recovered from the verified answer; the resulting 4B ABSeeker hits 55.3% on BrowseComp, matching 30B agents.
Deep-research search agents like OpenAI Deep Research and Tongyi DeepResearch answer a question through dozens of retrieve-browse-integrate cycles: reformulating queries, reading pages, revising hypotheses. Training them runs into an old credit-assignment problem. Standard SFT and RL treat every step in a trajectory uniformly: a correct trajectory is labeled fully correct, a failed one fully wrong. That does not match reality. A winning trajectory often contains mistaken or redundant steps, and a losing one often contains the single step that surfaced the decisive evidence. Rewarding and penalizing them all the same throws away the most informative signal.
ABC (Answer-Backtracked Credit Assignment), from Shanghai Jiao Tong University, turns sparse final-outcome supervision into dense per-step scores in two stages.
Stage 1 is answer-backtracked clue recovery. Given a question and its verified answer, an LLM (DeepSeek-V4-Flash) traces backward from the answer, running its own web searches, to recover the intermediate clues (entities, facts, relations) needed to solve it. For an answer of CeraVe, recovered clues include ceramides (the clinically supported ingredient), L'Oreal (the acquirer), and founder Eugene Schueller graduating in 1904, each anchored in real web content.
Stage 2 is clue-anchored step scoring. Each step in a trajectory is scored against the clue set from a base of 1.0: +0.8 for discovering or verifying a correct clue, +0.4 for correctly ruling out a wrong candidate, -0.8 for incorrectly dismissing a correct clue, +1.0 for submitting the verified answer, -1.0 for submitting a wrong one, clipped to [0, 2.0]. A good step in a failed trajectory still earns positive credit; a bad step in a successful one is still penalized.
ABC-SFT then reweights each turn's loss by a sigmoid of its step score; ABC-GRPO uses the step scores directly as GRPO rewards with a discounted step-level advantage (gamma 0.25). ABSeeker is trained on Qwen3.5-4B with only 8.5k trajectories (5.5k correct, 3.0k incorrect); both correct and failed trajectories are kept.
Five benchmarks (up to 200 tool calls, averaged over three runs):
| Benchmark | ABSeeker (4B) | 4B peer | 30B reference |
| BrowseComp | 37.3 / 55.3 | QUEST-4B 40.0 | MiroThinker 67.9 |
| BrowseComp-ZH | 39.1 / 52.9 | DR-Venus 37.7 | MiroThinker 72.3 |
| xbench-2505 | 77.0 | DR-Venus 74.7 | Tongyi-DR 75.0 |
| xbench-2510 | 46.0 | DR-Venus 40.7 | MiroThinker 57.2 |
| GAIA-text | 81.6 | QUEST-4B 77.7 | MiroThinker 80.3 |
with context management (256K window, up to 5 discard-all rounds).
With context management, ABSeeker ranks first in the 4B class on every benchmark; without it, BrowseComp sits at 37.3%, slightly below QUEST-4B's 40.0%. On xbench-2505 (77.0) and GAIA-text (81.6) it beats all reported 30B agents. Context management lifts BrowseComp from 37.3% to 55.3% and BrowseComp-ZH from 39.1% to 52.9%. Reward-distribution analysis: about 4% of steps in successful trajectories are low-quality (score below 1.0), and about 10% of steps in failed trajectories score above 1.0. Ablations show ABC-SFT beating standard SFT and ABC-GRPO beating trajectory-level GRPO. The model is trained only on BrowseComp-style questions yet transfers to xbench and GAIA.
The credit-assignment idea is the reusable contribution. Any long-horizon task whose final answer makes the problem backtrackable (math, multi-hop QA, tool use) can adopt answer-backtracked step scoring. Matching 30B agents with 8.5k examples and a 4B model suggests process supervision beats scale for this task class. The scoring rubric and the ABC-SFT and ABC-GRPO recipe are open-sourced (code on GitHub, model on HuggingFace). Caveat: the headline 55.3% depends on a context-management wrapper; without it the number is 37.3%.
Only a 4B model is tested; whether gains hold at larger scale is left open by compute constraints. Both clue recovery and step scoring rely on a strong judge LLM (DeepSeek-V4-Flash), which bounds the pipeline's quality ceiling: a wrong recovered clue or a bad score poisons the supervision, and judge error is not deeply analyzed. Training uses only BrowseComp-style questions with single verifiable answers; the backtracking trick depends on having one, so open-ended research questions without a ground truth do not fit. The 55.3% headline needs a heavy context-management wrapper; the method's own net gain over same-setting baselines is more modest. Correctness is also LLM-judged, so despite three-run averaging, judge variance remains.