🤖 AI

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

The paper introduces ABSeeker, a long-horizon search agent trained via a novel Answer-Backtracked Credit Assignment (ABC) framework that converts sparse trajectory outcomes into dense step-level rewards to distinguish useful actions from errors, enabling a compact 4B model to outperform same-scale agents and rival much larger 30B models on complex search benchmarks.

Original authors: Yijun Lu, Rui Ye, Jiajun Wang, Yuwen Du, Tian Jin, Songhua Liu, Siheng Chen

Published 2026-08-06

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yijun Lu, Rui Ye, Jiajun Wang, Yuwen Du, Tian Jin, Songhua Liu, Siheng Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to solve a massive, multi-step mystery. In the world of artificial intelligence, this is called training a "search agent." These agents are like digital detectives that don't just look up a single fact; they have to wander through the internet, read dozens of websites, connect the dots, and piece together a complex answer. Think of it like a treasure hunt where the map is missing, and the robot has to figure out the path by asking questions, checking clues, and sometimes realizing it's walking in circles. The big challenge scientists face is figuring out how to teach these robots to get better at the hunt. Usually, when a robot finishes a hunt, the teacher only gives a simple "Good job!" or "Try again!" based on whether the final treasure was found. But this is like grading a student's entire semester based only on the final exam score, ignoring the fact that they studied hard for weeks but made one silly mistake at the end, or that they guessed the right answer on the first try without doing any real work.

This paper, titled "ABSeeker," tackles that exact problem. The researchers, working at Shanghai Jiao Tong University, realized that to make search agents truly smart, we need to look at every single step they take, not just the final result. They propose a new training method called "Answer-Backtracked Credit Assignment" (ABC). Instead of just saying "You got the answer right, so every step you took was good," their system works backward from the correct answer to figure out what specific clues should have been found along the way. Then, it goes back through the robot's journey and gives credit for finding those clues, even if the robot eventually got lost, and gives a "time-out" for steps that wasted time or ignored good clues, even if the robot accidentally got the right answer in the end. They tested this on a relatively small AI model (4 billion parameters) and found that it could solve complex search puzzles better than much larger models, proving that teaching the robot how to think step-by-step is more important than just making the robot bigger.

The Mystery of the "All-or-Nothing" Grade

Let's dive into how this works. Imagine you are training a dog to find a specific hidden toy in a giant park. In the old way of training (which the paper calls "trajectory-level supervision"), you would only give the dog a treat if it brought the toy back to you. If the dog found the toy but then dropped it in a puddle on the way back, you'd give no treat. If the dog got lost, ran in circles, and then accidentally bumped into the toy, you'd give a treat. This is confusing for the dog! It doesn't know that finding the toy was good, or that running in circles was bad.

The authors of this paper argue that this "all-or-nothing" approach is a major flaw in training AI search agents. They noticed that even when an AI fails to find the final answer, it often takes many correct steps along the way—like finding the right website or reading the right paragraph. Conversely, an AI might get the right answer by luck or by taking a weird shortcut that skips important facts. The paper argues that we need a way to grade every single move the AI makes, not just the final score.

The "Backtracking" Detective

To fix this, the researchers invented a clever trick called Answer-Backtracked Clue Recovery. Here is the analogy: Imagine the AI is a detective who has just solved a crime and knows the name of the criminal (the "ground-truth answer"). The paper suggests that instead of just celebrating the win, the detective should work backward. "Okay, I know the criminal is John. To prove it's John, I must have found his fingerprint, his alibi, and his car."

In the AI's case, the system takes the correct answer and uses a powerful AI to "backtrack" and list all the intermediate clues that must have been discovered to reach that answer. For example, if the answer is a specific brand of shampoo, the clues might be "the company that owns it," "the year the founder graduated," and "the ingredient list." These clues become the "map" for grading the AI's performance.

Scoring the Steps

Once the map of clues is ready, the system moves to Clue-Anchored Step Scoring. This is where the magic happens. The AI's journey is replayed, and every single step is checked against the clue map.

The Good Steps: If the AI finds a clue (like the ingredient list), it gets a high score, even if the AI eventually gives up and fails to solve the whole puzzle.
The Bad Steps: If the AI ignores a clue or throws away a good lead, it gets a penalty, even if it somehow stumbled onto the right answer later.
The Neutral Steps: Just wandering around without finding anything gets a neutral score.

This turns a simple "Pass/Fail" grade into a detailed report card for every move the AI made. The paper shows that this method allows the AI to learn from its mistakes much faster because it knows exactly which move was wrong, rather than just knowing the whole attempt failed.

The Results: Small Brain, Big Wins

The researchers built a new search agent called ABSeeker using this method. They started with a model called Qwen3.5-4B, which is relatively small in the world of AI (think of it as a smart high schooler compared to a PhD-level supercomputer). They trained it on just 8,500 examples—a tiny amount compared to the millions usually needed.

The results were surprising. On a tough test called BrowseComp, where the AI has to find answers to complex, multi-part questions on the web, ABSeeker scored 37.3%. When they added a feature to help the AI manage its memory (called "context management"), the score jumped to 55.3%.

To put this in perspective, the paper compares ABSeeker to much larger AI agents (around 30 billion parameters, which are like professional detectives). ABSeeker, the "high schooler," managed to beat or match these much larger agents on several difficult tests. For instance, on the Chinese version of the test (BrowseComp-ZH), it scored 52.9%, outperforming larger models that scored lower.

Why This Matters

The paper suggests that the secret sauce isn't just making the AI bigger; it's about teaching it how to evaluate its own progress. By using "Answer-Backtracked Credit Assignment," the AI learns to value useful actions and avoid useless ones, regardless of whether it ultimately wins or loses the game. The authors found that even in failed attempts, about 10% of the steps were actually high-quality discoveries that should have been rewarded. Under the old system, those good steps would have been punished because the final answer was wrong.

In short, this paper shows that if you give an AI a detailed map of what a "good journey" looks like, it can learn to navigate the internet much more efficiently, even if it starts with a smaller brain. The researchers believe this approach could be a game-changer for training future AI agents to solve complex problems, not just by guessing, but by thinking through every step carefully.

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

1. Problem Statement

Long-horizon search agents require multiple sequential actions to retrieve, verify, and integrate evidence to solve complex queries. However, existing training methods for these agents, including both Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL), typically rely on trajectory-level supervision. In this paradigm, all steps within a trajectory are treated uniformly: successful trajectories are rewarded entirely, while failed trajectories are penalized entirely.

This uniform treatment creates a fundamental credit-assignment problem:

False Negatives: A failed trajectory may contain highly useful intermediate steps (e.g., discovering decisive evidence or refining a hypothesis) that receive zero reward because the final answer was incorrect.
False Positives: A successful trajectory may contain erroneous, redundant, or misleading steps that receive full reward despite hindering the search process.
Lack of Granularity: Existing methods fail to distinguish the individual contribution of specific actions, limiting the ability to optimize critical search and reasoning behaviors.

2. Methodology: Answer-Backtracked Credit Assignment (ABC)

The authors propose Answer-Backtracked Credit Assignment (ABC), a fine-grained framework that converts sparse trajectory-level outcomes into dense, step-level supervision. The core insight is that once a ground-truth answer is available, the search task becomes naturally backtrackable. By tracing back from the verified answer, one can recover the intermediate evidence (clues) that should have been discovered.

The framework operates through two primary stages:

2.1 Answer-Backtracked Clue Recovery

Given a query $q$ and its verified ground-truth answer $a^*$ , the system employs an LLM to reconstruct the evidence chain required to solve the question.

Process: The recovery model acts as an active agent, performing web searches and visiting pages (using the same tool-call protocol as the forward agent) to trace evidence from the answer back to the query constraints.
Output: A set of intermediate evidence clues $C = \{c_1, c_2, ..., c_K\}$ . These clues are concrete, verifiable pieces of information (entities, facts, attributes, or relationships) that form a verified evidence chain connecting the query to the answer.
Role: These clues serve as fixed anchors for evaluating the quality of every step in a search trajectory, independent of the final outcome.

2.2 Clue-Anchored Step Scoring

Every step $s_t$ in a collected trajectory (whether successful or failed) is evaluated against the recovered clue set $C$ .

Scoring Mechanism: Each step starts with a base score of 1.0. The score is adjusted based on specific behaviors detected in the step's reasoning, tool calls, and responses:
- Positive Deltas: Discovering/verifying a correct clue (+0.8), ruling out an incorrect candidate (+0.4), or submitting the verified answer (+1.0).
- Negative Deltas: Incorrectly dismissing a correct clue (-0.8) or submitting an incorrect answer (-1.0).
Final Reward: The step reward $r_t$ is the accumulated score clipped to the range $[0, 2.0]$ . Crucially, a step in a failed trajectory that discovers a correct clue receives a positive reward, while a step in a successful trajectory that discards useful evidence receives a penalty.

2.3 Training Pipeline

Based on these dense step rewards, the authors develop two training algorithms:

ABC-SFT (Reward-Weighted Supervised Fine-Tuning): Standard SFT is modified to reweight the loss of each turn. The weight $w(r_t)$ is computed via a sigmoid function of the step reward, allowing high-quality steps to contribute more strongly to the gradient while down-weighting erroneous steps.
ABC-GRPO (Step-Level Reinforcement Learning): The step-level scores serve as rewards in the Group Relative Policy Optimization (GRPO) algorithm. Instead of a single trajectory-level advantage, the algorithm computes a discounted step-level advantage for each token, enabling fine-grained policy updates.

3. Key Contributions

Answer-Backtracked Credit Assignment (ABC): A novel framework that leverages verified answers to reconstruct intermediate evidence clues, enabling the evaluation of individual search steps regardless of the final trajectory outcome.
ABC-SFT and ABC-GRPO: Two training algorithms derived from ABC that utilize dense, step-level rewards to reweight SFT losses and optimize RL policies, respectively.
ABSeeker: A search agent trained on a 4B parameter backbone (Qwen3.5-4B) using only 8.5k examples. It demonstrates that fine-grained process supervision can yield high performance without requiring massive model scales.

4. Experimental Results

The authors evaluated ABSeeker on five benchmarks: BrowseComp, BrowseComp-ZH, xbench-2505, xbench-2510, and GAIA-text.

Performance:
- BrowseComp: 37.3% (without context management), improving to 55.3% with context management.
- BrowseComp-ZH: 39.1% (without context management), improving to 52.9% with context management.
- xbench-2505: 77.0%.
- xbench-2510: 46.0%.
- GAIA-text: 81.6%.
Comparisons:
- ABSeeker achieves the best performance among all 4B search agents (outperforming QUEST-4B, DR-Venus, and AgentCPM-Explore).
- It significantly outperforms same-scale baselines and matches or exceeds the performance of substantially larger agents (~30B), such as Tongyi DeepResearch and OpenSeeker, on several benchmarks.
Ablation Studies:
- Replacing standard SFT with ABC-SFT yields consistent improvements across benchmarks.
- Replacing standard trajectory-level GRPO with ABC-GRPO further boosts performance, demonstrating that step-level credit assignment improves both search accuracy and exploratory behavior.
- Reward distribution analysis reveals that even in successful trajectories, ~4% of steps are low-quality, while ~10% of steps in failed trajectories are high-quality. ABC successfully identifies and rewards the latter while penalizing the former.

5. Significance and Claims

The paper claims that Answer-Backtracked Credit Assignment effectively addresses the credit-assignment challenge in long-horizon search by providing explicit, fine-grained process supervision.

Efficiency: The method enables a compact 4B model to outperform much larger agents, suggesting that the quality of training supervision (distinguishing useful vs. erroneous steps) is more critical than sheer model scale for search tasks.
Generalization: Despite being trained exclusively on BrowseComp-style questions, ABSeeker generalizes effectively to xbench and GAIA, indicating robust cross-benchmark capabilities.
Process Supervision: The results validate that rewarding useful actions in failed trajectories and suppressing errors in successful ones leads to more efficient and deliberate search behaviors.

The authors conclude that this approach highlights the importance of explicit process supervision for scalable search-agent training and propose extending the framework to other long-horizon tasks where outcomes can be backtracked into intermediate evidence.