One-sentence Summary

Researchers from Shanghai Jiao Tong University propose Answer-Backtracked Credit Assignment (ABC), a fine-grained framework that converts sparse trajectory-level outcomes into dense step-level supervision by backtracking from ground-truth answers to recover intermediate clues and scoring each search step, enabling their ABSeeker agent based on Qwen3.5-4B to achieve 37.3% on BrowseComp and 39.1% on BrowseComp-ZH, significantly outperforming same-scale agents and matching larger models.

Key Contributions

• Answer-Backtracked Credit Assignment (ABC) recovers intermediate evidence clues from verified answers and uses Clue-Anchored Step Scoring to convert sparse trajectory-level outcomes into dense step-level supervision that rewards useful actions and suppresses erroneous or redundant ones.
• ABC-SFT reweights the loss of each turn, and ABC-GRPO uses the step-level scores as rewards in GRPO, enabling fine-grained credit assignment during both supervised fine-tuning and reinforcement learning.
• ABSeeker, trained on Qwen3.5-4B with only 8.5k examples, achieves 37.3% on BrowseComp and 39.1% on BrowseComp-ZH, and with context management reaches 55.3% and 52.9%, outperforming same-scale agents and matching larger models.

Introduction

Search agents that tackle complex, multi-step information-seeking tasks must execute long sequences of queries, evidence inspection, and hypothesis revision. Training these agents is difficult because existing methods assign uniform credit to every step in a trajectory, ignoring the fact that even successful runs contain redundant or erroneous actions while failed runs can include useful evidence-gathering steps. This coarse supervision limits the ability to optimize critical search and reasoning behaviors at a fine grain.

The authors introduce Answer-Backtracked Credit Assignment (ABC), a framework that recovers intermediate clues from a verified answer and then scores each search step according to how it discovers, verifies, or mishandles those clues. This produces dense, turn-level rewards that distinguish productive actions from mistakes, enabling two training variants: ABC-SFT, which reweights the supervised fine-tuning loss per step, and ABC-GRPO, which supplies step-level rewards for reinforcement learning. Using ABC, the authors train ABSeeker, a 4B-parameter agent that achieves strong results on BrowseComp, BrowseComp-ZH, xbench, and GAIA-text, outperforming same-scale baselines and competing with much larger search agents.

Method

The authors propose a training pipeline consisting of two core stages to address the sparse and coarse nature of trajectory-level outcome supervision in search agents.

Given a query and its verified answer, the pipeline first recovers a set of intermediate evidence clues that define meaningful progress toward the answer. Search trajectories are then rolled out, retaining both successful and failed trajectories. Next, a step scoring mechanism evaluates every step against the recovered clue set and produces dense, fine-grained step scores. Finally, these step-level scores directly serve as the reward signal for policy optimization.

The authors consider a set of training questions, each consisting of a query $q$q and a verified answer $a^*$a∗. A search agent interacts with a web environment over $T$T turns to produce a search trajectory:

$$\tau = (s_1, s_2, \dots, s_T, a)$$τ=(s1​,s2​,…,sT​,a)

where $a$a is the final answer submitted by the agent. Each step $s_t$st​ contains the agent's reasoning, the issued tool call, and the corresponding tool response. During training, the agent typically receives a reward based solely on whether the final answer matches the ground truth:

$$r_{\text{ans}}(\tau) = \begin{cases} 1, & \text{if } a = a^*, \\ 0, & \text{otherwise}. \end{cases}$$rans​(τ)={1,0,​if a=a∗,otherwise.​

This trajectory-level signal is sparse and coarse, leading to credit-assignment failures. An incorrect trajectory may contain useful intermediate steps, yet the final reward of zero provides no positive signal. Conversely, a correct trajectory may contain erroneous intermediate steps, yet the final reward of one does not distinguish these flawed actions. The authors address this limitation by constructing a step reward $r_t$rt​ for every step in each trajectory, enabling stable, dense, and fine-grained supervision.

The verified answer specifies where the search should end but provides little supervision about how the agent should reach it. To evaluate the quality of intermediate steps, the authors require a set of answer-backtracked anchors. Answer-Backtracked Clue Recovery maps each training question $(q, a^*)$(q,a∗) to a set of clues:

$$\mathcal{C} = \{c_1, c_2, \dots, c_K\}$$C={c1​,c2​,…,cK​}

where each $c_k$ck​ is a verifiable piece of intermediate evidence relevant to answering $q$q.

The recovery process leverages the fact that benchmarks provide unique and verifiable answers. Given the query and its verified answer, the authors prompt an LLM to reconstruct the evidence chain by identifying the intermediate entities and facts that must be discovered, verified, and cross-referenced. This backtracking is an active ReAct loop where the recovery model conducts web searches and visits pages through the same tool-call protocol as the forward agent, tracing evidence from the answer back toward the query. Clues that survive this verification serve as reliable reference points for subsequent step scoring.

Given the recovered clue set $\mathcal{C}$C for a training question, Clue-Anchored Step Scoring evaluates every step in each collected trajectory. For each step $s_t$st​, the scorer receives the current step, the original query $q$q, and the complete clue set $\mathcal{C}$C. It outputs a step reward $r_t$rt​ together with a brief rationale. Each step starts with a base score of 1.0, ensuring that reasonable exploration without an obvious error is not penalized. A step may exhibit multiple scored behaviors, and the corresponding deltas are accumulated on top of the base score and clipped to $[0, 2.0]$[0,2.0]:

$$r_t = \text{clip}\left(1.0 + \sum_{j \in \mathcal{A}_t} \Delta_j, 0, 2.0\right)$$rt​=clip​1.0+j∈At​∑​Δj​,0,2.0​

where $\mathcal{A}_t$At​ denotes the set of scored behavior instances detected at step $t$t. A step that discovers a correct clue in a trajectory that ultimately fails still receives positive credit, whereas a step that incorrectly dismisses a correct clue in a trajectory that ultimately succeeds still receives a penalty.

Given the step reward $r_t$rt​ assigned to every step in each trajectory, the authors train the agent in two consecutive stages: reward-weighted supervised fine-tuning (ABC-SFT) followed by step-level reinforcement learning (ABC-GRPO). Both successful and failed trajectories are retained.

In the first stage, the authors perform SFT on all collected trajectories. For a trajectory $\tau$τ of length $T$T, let $x_{t,j}$xt,j​ denote the $j$j-th policy-generated token at step $s_t$st​, with environment-provided tool responses excluded from optimization. The training objective is:

$$\mathcal{L}_{\text{SFT}}(\theta) = - \sum_{t=1}^T w(r_t) \sum_j \log p_\theta(x_{t,j} \mid x_{t,<j})$$LSFT​(θ)=−t=1∑T​w(rt​)j∑​logpθ​(xt,j​∣xt,<j​)

where the step-level weight is computed via a sigmoid function $w(r_t) = \sigma(\alpha \cdot (r_t - \beta))$w(rt​)=σ(α⋅(rt​−β)), with $\alpha$α controlling the sharpness of the mapping and $\beta$β the neutral baseline. High-scoring steps contribute more strongly to the gradient, whereas low-scoring steps contribute little training signal.

In the second stage, the authors further optimize the agent through online RL with step-level rewards. For each sampled rollout $i$i, the reward at step $t$t is defined as $R_{i,t} = r_{i,t}$Ri,t​=ri,t​. They normalize rewards within each rollout group to obtain $\widehat{R}_{i,t}$Ri,t​ and compute the discounted step-level advantage:

$$A_{i,t} = \sum_{k=t}^{T_i} \gamma^{k-t} \widehat{R}_{i,k}$$Ai,t​=k=t∑Ti​​γk−tRi,k​

where $\gamma$γ controls how future step rewards are propagated to earlier decisions. The resulting advantage $A_{i,t}$Ai,t​ is assigned to all policy-generated tokens at step $t$t, while environment-provided tool responses are masked from optimization. The policy is optimized using the standard clipped GRPO objective, replacing its trajectory-level advantage with the step-specific advantage $A_{i,t}$Ai,t​.

Experiment

The evaluation uses Qwen3.5-4B as the backbone, with training on OpenSeeker trajectories and testing across BrowseComp, BrowseComp-ZH, xbench, and GAIA benchmarks. ABSeeker achieves the best performance among 4B search agents on every benchmark and remains competitive with much larger 30B agents, while also generalizing effectively to unseen benchmarks. The core insight is that answer-backtracked step-level credit assignment preserves useful actions in failed trajectories and suppresses erroneous ones in successful trajectories, leading to more efficient and deliberate search behavior. Ablation studies confirm that this fine-grained credit assignment improves both supervised fine-tuning and reinforcement learning over standard trajectory-level approaches.

The rubric assigns step-level rewards by accumulating deltas for specific behaviors relative to a base score of 1.0, then clipping to [0, 2.0]. Positive deltas are given for discovering or verifying correct clues and ruling out incorrect candidates, while negative deltas penalize incorrectly dismissing correct clues or submitting wrong answers. This fine-grained credit assignment allows useful steps in failed trajectories to receive positive rewards and erroneous steps in successful trajectories to be penalized. Discovering or verifying a correct clue yields the largest positive delta (+0.8), while submitting an incorrect answer incurs the largest penalty (-1.0). Ruling out an incorrect candidate provides a moderate positive signal (+0.4), and incorrectly dismissing a correct clue carries a symmetric negative delta (-0.8). Submitting the verified answer adds a full +1.0 delta, and all deltas accumulate on a base score of 1.0 before clipping to the range [0, 2.0]. Nearly 10% of steps in failed trajectories receive rewards above 1.0 because they still discover or verify useful clues, and about 4% of steps in successful trajectories fall below 1.0 due to low-quality actions.

The 4B-parameter ABSeeker search agent leads all comparable-sized models on every evaluated benchmark and remains competitive with much larger 30B-class agents, surpassing them on xbench-2505 and GAIA-text. Its performance gains are driven by answer-backtracked step-level credit assignment, which rewards productive steps even in failed trajectories and penalizes low-quality steps in successful ones, and are further amplified by context management on BrowseComp benchmarks. The method also exhibits strong cross-benchmark generalization despite being trained solely on BrowseComp-style questions. ABSeeker achieves the highest scores among all 4B search agents on BrowseComp, BrowseComp-ZH, xbench-2505, xbench-2510, and GAIA-text. Despite its smaller size, ABSeeker outperforms all reported 30B agents on xbench-2505 and GAIA-text and surpasses several 30B systems on BrowseComp and BrowseComp-ZH. Training exclusively on BrowseComp-style questions, ABSeeker generalizes effectively to xbench and GAIA benchmarks. Step-level credit assignment identifies useful actions in nearly 10% of steps from failed trajectories and low-quality steps in about 4% of steps from successful trajectories, enabling more precise supervision than trajectory-level signals. ABC-GRPO training yields consistently stronger BrowseComp validation performance and longer search trajectories compared to standard trajectory-level GRPO. Applying a discard-all context management strategy with a 256K token limit improves ABSeeker from 37.3% to 55.3% on BrowseComp and from 39.1% to 52.9% on BrowseComp-ZH.

Fine-grained step-level credit assignment improves both supervised fine-tuning and reinforcement learning by rewarding useful actions even in failed trajectories and suppressing erroneous ones in successful trajectories. ABC-SFT outperforms standard SFT on four of five benchmarks, and ABC-GRPO consistently surpasses standard trajectory-level GRPO across all benchmarks without context management. The gains are attributed to independent per-step evaluation that preserves productive exploration and corrects mistakes more precisely than trajectory-level signals. ABC-SFT improves performance over standard SFT on BrowseComp, BrowseComp-ZH, xbench-2510, and GAIA-text while remaining comparable on xbench-2505. ABC-GRPO consistently outperforms standard trajectory-level GRPO across all five benchmarks. Even successful trajectories contain about 4% low-quality steps with rewards below 1.0, and nearly 10% of steps in failed trajectories receive rewards above 1.0, motivating step-level credit assignment. The largest absolute gains from ABC-GRPO over standard GRPO appear on BrowseComp and GAIA-text, with smaller but consistent improvements on xbench-2505.

ABSeeker, a 4B-parameter search agent, is evaluated on BrowseComp, xbench, and GAIA-text benchmarks. Its training uses answer-backtracked step-level credit assignment to reward productive steps in failed trajectories and penalize low-quality steps in successful ones, improving both supervised fine-tuning and reinforcement learning over trajectory-level signals. This fine-grained credit assignment, combined with context management on BrowseComp, enables ABSeeker to lead all comparable-sized models and surpass several 30B agents while generalizing effectively despite training only on BrowseComp-style questions.