# ABSeeker: Training Long-Horizon Search Agents via Answer-Backtracked Credit Assignment > ABSeeker introduces Answer-Backtracked Credit Assignment, converting sparse trajectory rewards into dense step-level supervision, achieving 37.3% on BrowseComp with a 4B model. - **Source:** [arXiv](https://arxiv.org/abs/2608.05102) - **Published:** 2026-08-07 - **Permalink:** https://picx.dev/p/Pz5QzK ## Summary # 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**: | Scored Behavior | Δ | |---|---| | Discovers or verifies a correct clue | +0.8 | | Rules out an incorrect candidate | +0.4 | | Incorrectly dismisses a correct clue | -0.8 | | Submits the verified answer | +1.0 | | Submits an incorrect answer | -1.0 | 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, 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): | Model | BrowseComp | BrowseComp-ZH | xbench-2505 | xbench-2510 | GAIA-text | |---|---|---|---|---|---| | **Qwen3.5-4B** | | | | | | | +Standard SFT | 28.5 | 30.4 | 73.0 | 27.0 | 66.0 | | +ABC-SFT | 30.8 | 31.8 | 72.0 | 35.0 | 72.8 | | **ABSeeker-4B-SFT** | | | | | | | +Standard GRPO | 33.5 | 36.3 | 75.0 | 41.0 | 77.7 | | +ABC-GRPO | 37.3 | 39.1 | 77.0 | 46.0 | 81.6 | 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. --- _Markdown view of https://picx.dev/p/Pz5QzK, served by PicX — AI-generated visual whiteboard summaries of research papers._