1 Introduction↩︎

In recent years, LLM-based agents have made tremendous progress [1]–[3]. Based on this, Agentic Search has garnered significant attention from both academia and industry, with LLM-based agents being applied to tackling complex Information Seeking (IS) tasks. Unlike traditional retrieval methods, search agents iteratively interact with external knowledge bases and update their thoughts based on retrieved results [4], [5]. This enables them to solve knowledge-intensive problems beyond single-turn inference. Recent studies further leverage RL [6]–[8] to improve agents’ search capabilities.

Currently, mainstream RL methods typically employ trajectory-level rewards, with Group Relative Policy Optimization (GRPO) and its variants occupying a dominant position [9]–[11]. These methods determine rewards based on the correctness of the final answer and uniformly assign the signal across all steps in the trajectory. In Agentic Search [6], [12], [13], although trajectory-level rewards have achieved significant success, they overlook the fact that different steps in a multi-turn search process contribute differently to the final success. As a result, they fail to accurately measure the quality of individual steps, making it difficult to optimize critical retrieval and citation behaviors in a targeted manner. Therefore, this paper aims to introduce step-level rewards into the policy optimization framework.

Existing step-level policy optimization methods typically rely on sampling-based approaches to assign rewards to each step [14]–[18]. They usually employ tree sampling to explore multiple continuations and back-propagate final rewards from leaf nodes to intermediate steps. However, for complex IS tasks, agent trajectories often extend to dozens of steps, and a large branching factor is required to avoid missing critical decision points. This leads to excessive computational overhead and severely limits training efficiency. This naturally raises a key question: can we obtain effective step-level credit assignment without relying on expensive tree sampling?

To answer this question, we propose an intuitive answer-grounded prior: world knowledge can be viewed as a large latent world graph, and each IS task corresponds to a latent task graph that connects query-conditioned entities to the answer node. Agentic Search can then be viewed as gradually exploring this latent task graph, where an effective step should make graph progress toward the answer node. As shown in Figure 1 (b), for the question “In which city was the director of the movie Inception born?”, retrieving “Christopher Nolan” bridges the query entity “Inception” and the answer “London”, and thus deserves a high reward. In contrast, retrieving “Science Fiction”, though semantically related to the movie, is logically distant from the answer and contributes little. Based on this prior, we construct a training-time Entity-Relation (ER) graph for each Question-Answering (QA) pair as a proxy for the latent task graph, where nodes represent entities and edges represent semantic relationships. We estimate the contribution of a graph-linked entity using its shortest-path distance to the answer node, and define one component of the step-level reward as the sum of the graph-distance contribution scores of newly-retrieved entities.

Furthermore, our analysis in Figure 4 reveals that some retrieved entities, despite being answer-relevant, may not be explicitly cited in later thoughts and thus fail to contribute to the final answer. To address this issue, we further incorporate the graph-distance contribution scores of newly-cited entities in the current thought. Similar to newly-retrieved entities, newly-cited entities closer to the answer node are more likely to move the search path toward the answer and therefore should receive higher reward scores. Consequently, we propose the Graph-Distance Contribution Reward (GDCR), which encourages agents to retrieve and cite entities closer to the answer node for more effective search.

Building on GDCR, we propose Step Advantage Policy Optimization (SAPO). SAPO first normalizes and bounds GDCR signals within each trajectory, and then combines trajectory-level rewards with GDCR-based step-level rewards to formulate the advantage. The trajectory-level reward preserves the final-answer objective, while the step-level reward reinforces critical behaviors and suppresses redundant ones. As shown in Figure 1 (a), SAPO alleviates reward sparsity in long-horizon IS tasks and avoids the prohibitive overhead of sampling-based step-level reward estimation. Experiments on four challenging benchmarks, together with targeted analyses, validate the effectiveness and efficiency of SAPO. Notably, SAPO outperforms ARPO, a representative tree-sampling step-level reward method, in both training efficiency and performance.

The main contributions of this paper can be summarized as follows:

• We propose the answer-grounded graph-progress prior for Agentic Search, which views each IS task as exploration over a latent task graph within a latent world graph, and we use a training-time Entity-Relation (ER) graph as a proxy for the latent task graph to derive step-level credit from graph-distance progress toward the answer node.

• We propose Graph-Distance Contribution Reward (GDCR), which assigns step-level credit to both newly-retrieved entities and newly-cited entities, encouraging the agent to retrieve and cite entities that make stronger graph progress toward the answer node.

• We propose Step Advantage Policy Optimization (SAPO), which combines trajectory-level rewards with GDCR-based step-level rewards and achieves strong performance on multiple datasets.

2 Preliminaries↩︎

We first formulate information-seeking tasks from the perspective of search agents, and then introduce the graph-augmented data setting that provides supervision for GDCR.

2.1 Task Formulation↩︎

Information-Seeking Task. We consider complex information-seeking (IS) tasks where an agent is given a user query \(q\) and required to produce a final answer by collecting and reasoning over external information. Unlike single-hop retrieval tasks, complex IS tasks often require discovering multiple pieces of evidence and identifying their dependencies before arriving at the answer.

We view world knowledge as a latent world graph: \[\mathcal{G}^{\mathrm{world}} = (\mathcal{V}^{\mathrm{world}}, \mathcal{E}^{\mathrm{world}}),\] where \(\mathcal{V}^{\mathrm{world}}\) denotes entities in world knowledge, and \(\mathcal{E}^{\mathrm{world}}\) denotes semantic or relational dependencies among them. For a query \(q\), the information needed to solve the task corresponds to a latent task graph: \[\mathcal{G}_q = (\mathcal{V}_q, \mathcal{E}_q),\] where \(\mathcal{G}_q \subseteq \mathcal{G}^{\mathrm{world}}\), \(\mathcal{V}_q\) denotes the set of task-relevant entities, and \(\mathcal{E}_q\) denotes their semantic or relational dependencies. The answer corresponds to an answer node \(v_q^\ast \in \mathcal{V}_q\). Under this view, solving an IS task requires the agent to explore the latent task graph from query-conditioned entities toward the answer node. Therefore, an effective step should move the agent closer to \(v_q^\ast\), while redundant or irrelevant steps contribute little to solving the task.

Search Agent. We formalize the search agent using the ReAct paradigm [1]. Given a user query \(q\), an LLM-based agent, governed by a policy \(\pi_{\theta}\), incrementally collects evidence and produces a final response through multiple rounds of interaction with an external search environment. Specifically, the agent executes a thought-action-observation loop in each iteration: it first generates a free-form thought \(\tau_t\) based on the current context, then selects an action \(a_t\), such as submitting a search query, and receives a corresponding observation \(o_t\) from the environment, typically consisting of retrieved document snippets. The interaction terminates when the agent selects <answer> as its action. A complete trajectory of \(T\) iterations is denoted as: \[\mathcal{H}_{T} = \left( q, \tau_1, a_1, o_1, \ldots, \tau_{t}, a_{t}, o_{t}, \ldots, \tau_{T}, a_{T} \right). \label{eq:Ht}\tag{1}\] where \(\tau_t\), \(a_t\), and \(o_t\) represent the thought, action, and observation at step \(t\). At each step, the thought and action are sampled from the policy \(\pi_\theta\) based on the historical context \(\mathcal{H}_{t-1}\). Additional format details can be found in Appendix 7.

Tool Design. Our agent is equipped with a single search tool: a search engine that supports multiple queries and returns the top-5 relevant results for each query, including the corresponding titles, abstracts, and URLs.

2.2 Data Synthesis↩︎

Large-scale and high-quality data are essential for training search agents with reinforcement learning [19], [20]. In addition to QA pairs and search trajectories, our synthesis process constructs a training-time ER graph \(\hat{\mathcal{G}}_q\) for each query-answer pair, with task-relevant entities, relations, and answer-node annotations. This graph serves as an observable proxy for the latent task graph and makes it possible to estimate step-level contribution through graph distance. More discussion of graph construction and quality control can be found in Appendix 8.

3 Methodology↩︎

We first define the training-time Entity-Relation (ER) graph, then introduce Graph-Distance Contribution Reward (GDCR) and Step Advantage Policy Optimization (SAPO).

3.1 Training-Time ER Graph Construction↩︎

As discussed in Section 2, the latent world graph \(\mathcal{G}^{\mathrm{world}}\) is unobservable, and the latent task graph \(\mathcal{G}_q\) for each query is therefore not directly available. During training, we construct a training-time ER graph \(\hat{\mathcal{G}}_q=(\hat{\mathcal{V}}_q,\hat{\mathcal{E}}_q)\) for each query-answer pair, where nodes denote task-relevant entities, edges denote evidential relations, and the answer entity is annotated as the answer node \(v_q^\ast\). Conceptually, the training-time ER graph \(\hat{\mathcal{G}}_q\) serves as an observable proxy for the latent task graph. \(\hat{\mathcal{G}}_q\) helps the model learn to reason over entity relations and use search tools to find answer-relevant entities. The resulting \(\hat{\mathcal{G}}_q\) serves as the graph basis for GDCR, which assigns step-level rewards according to progress toward the answer node. We apply structural checks and LLM-based verification during data synthesis; more details can be found in Appendix 8.

3.2 Graph-Distance Contribution Score↩︎

Given the training-time ER graph \(\hat{\mathcal{G}}_q\) and its answer node \(v_q^\ast\), we estimate the contribution of each graph-linked entity by its shortest-path distance to the answer node. The intuition is that entities closer to the answer node indicate stronger progress toward the answer, and therefore provide a stronger step-level contribution signal.

Formally, for any entity node \(v \in \hat{\mathcal{V}}_q\), let \(\hat{\mathcal{P}}(v, v_q^\ast)\) denote the set of reachable paths from \(v\) to the answer node \(v_q^\ast\) in \(\hat{\mathcal{G}}_q\). We define the shortest-path graph distance as: \[d_q(v, v_q^\ast) = \min_{p \in \hat{\mathcal{P}}(v, v_q^\ast)} |p| ,\] where \(|p|\) is the number of edges in path \(p\). Based on this distance, the graph-distance contribution score of node \(v\) is defined as: \[c_q(v) = k^{-d_q(v, v_q^\ast)},\] where \(k\) is a decay factor. In our experiments, we set \(k=2\).

3.3 Graph-Distance Contribution Reward↩︎

Having established the training-time ER graph \(\hat{\mathcal{G}}_q\) and the graph-distance contribution score \(c_q(v)\) for each node, we define Graph-Distance Contribution Reward (GDCR) to quantify the extent to which a search agent discovers and explicitly cites relevant entities during a single step. Let \(\mathcal{H}_T\), as denoted in Eq. 1 , be a trajectory generated by the agent. We first define the following subsets of nodes: \[T_t \subseteq \hat{\mathcal{V}}_q, \quad O_t \subseteq \hat{\mathcal{V}}_q ,\] where \(T_t\) represents the cumulative set of nodes explicitly cited in the thoughts up to step \(t\) after they have appeared in observations; \(O_t\) denotes the cumulative set of nodes appearing in the external observations up to step \(t\). All sets are initialized as empty sets: \[T_0 = O_0 = \emptyset .\]

Following the step structure in Section 2, GDCR computes rewards in two stages: it first scores newly-cited entities in the current thought, and then scores newly-retrieved entities in the current observation.

Reward for Newly-Cited Entities. In the thought stage, the agent may explicitly cite entities that appeared in previous observations. To keep the reward step-level, we only count entities that are newly cited in the current thought: \[\Delta C_t = T_t \setminus T_{t-1}.\] The reward for newly-cited entities of step \(t\) is defined as: \[r_t^{\mathrm{cite}} = \sum_{v \in \Delta C_t} c_q(v).\] Figures 2 (a) and 2 (b) illustrate how graph distance distinguishes newly-cited entities.

Reward for Newly-Retrieved Entities. In the observation stage, the action returns external observations that may contain entities not seen in previous observations. Let the newly-retrieved entities at step \(t\) be denoted as: \[\Delta O_t = O_t \setminus O_{t-1}.\] The reward for newly-retrieved entities of step \(t\) is then defined as: \[r_t^{\mathrm{ret}} = \sum_{v \in \Delta O_t} c_q(v).\] Figures 2 (c) and 2 (d) illustrate the same graph-distance comparison for newly-retrieved entities.

Finally, GDCR for step \(t\) is calculated as the sum of the reward for newly-cited entities and newly-retrieved entities: \[r_{t,g} = r_t^{\mathrm{cite}} + r_t^{\mathrm{ret}} .\]

3.4 Step Advantage Policy Optimization↩︎

Step Advantage Policy Optimization (SAPO) is a general optimization method that converts process rewards into step-level advantages and combines them with trajectory-level outcome advantages. In this work, SAPO operationalizes the step-level credit derived from GDCR for Agentic Search training. For each query \(q\), we sample a group of trajectories \(\{\mathcal{H}^{(i)}\}_{i=1}^{G}\). Each trajectory receives a trajectory-level outcome reward according to final-answer correctness and format validity, which is then group-normalized to obtain the outcome advantage \(\hat{A}^{(i)}_o\). This term anchors optimization to the final answer objective.

To introduce step-level credit assignment, SAPO uses the GDCR sequence \(\mathbf{r}^{(i)}_g=(r^{(i)}_{1,g},\ldots,r^{(i)}_{T_i,g})\) computed along trajectory \(\mathcal{H}^{(i)}\). Since raw GDCR scales vary across tasks and training-time ER graphs, we normalize the GDCR rewards within each trajectory and clip the resulting step-level signal: \[A^{(i)}_{t,g} = \mathrm{clip}\left( \frac{r^{(i)}_{t,g}-\mathrm{mean}_{t=1}^{T_i}(r^{(i)}_{t,g})}{\mathrm{std}_{t=1}^{T_i}(r^{(i)}_{t,g})+\varepsilon}, -1, 1 \right).\] The final advantage assigned to all tokens in step \(t\) combines the outcome advantage and the GDCR-based step advantage: \[A^{(i)}_{t} = \hat{A}^{(i)}_o + \lambda |\hat{A}^{(i)}_o| A^{(i)}_{t,g}, \quad t=1,\ldots,T_i , \label{eq:lambda}\tag{2}\] where \(\lambda\) controls the strength of the step-level signal. Thus, SAPO preserves the trajectory-level correctness objective while assigning different advantages to different steps according to GDCR.

Finally, the policy is optimized with the GRPO-style objective: \[\small \begin{align} J(\theta) = &\mathbb{E}_{(q,y)\sim\mathcal{D},\,\mathcal{B}_q} \Bigg[ \frac{1}{G}\sum_{i=1}^{G} \frac{1}{|\mathcal{H}^{(i)}|} \sum_{j=1}^{|\mathcal{H}^{(i)}|} \\ &\min\!\Big( \rho_{i,j}(\theta) A_{i,j}, \\ &\qquad \mathrm{clip}(\rho_{i,j}(\theta),1-\epsilon_l,1+\epsilon_h) A_{i,j} \Big) \Bigg], \end{align}\] where \(\mathcal{B}_q=\{\mathcal{H}^{(i)}\}_{i=1}^{G}\) denotes the trajectory group, \(\rho_{i,j}(\theta)\) is the token-level importance ratio, \(A_{i,j}\) is the advantage of the step to which token \(j\) belongs, and \(\epsilon_l,\epsilon_h\) are clipping bounds.

4 Experiment↩︎

In this section, we evaluate SAPO through SFT and RL training, and compare it with outcome-reward training and existing search agents.

4.1 Experiment Setup↩︎

Benchmarks. We evaluate our agent on four challenging deep research benchmarks: BrowseComp [21], BrowseComp-ZH [22], xbench-DS [23], and GAIA [24]. For GAIA, we use the text-only validation subset with 103 samples [6]. For the remaining benchmarks, we use the complete test sets.

Metrics. Following prior work [13], we adopt an LLM-as-a-judge evaluation protocol. Model answers are extracted from the final <answer> and </answer> tags of the last response turn, and GPT-4o is used to judge correctness. Additional trajectory-format details can be found in Appendix 7.

Baselines. Our primary baseline is GRPO trained with outcome rewards and format penalties, using the same model architecture, training data, and context length as SAPO. We also include ARPO [14] as a branch-sampling policy optimization baseline at the 8B scale. Fully expanded tree-sampling methods are prohibitively expensive for Agentic Search training because each branch requires additional model generation and search interaction; therefore, we choose ARPO as a practical representative that samples branches according to a fixed strategy. For a controlled comparison, ARPO and SAPO use the same number of rollouts per prompt, which can be viewed as comparing the two methods under the same rollout budget. We also compare with representative open-source search agents under our evaluation environment and report publicly available results of strong closed-source systems as reference points. More experimental details can be found in Appendix 9.

Training Details. We conduct experiments with Qwen3-8B and Qwen3-30B-A3B-thinking-2507. The training pipeline contains a cold-start SFT phase followed by RL. For RL, we synthesize 1,000 graph-augmented QA pairs and 500 development examples for analysis. The 8B RL training uses group size 8 and a 32k context length; additional training and environment details can be found in Appendix 9.

4.2 RQ1: Is Graph Distance a Valid Progress Prior?↩︎

We first validate whether moving closer to the answer node in the training-time ER graph is associated with final-answer correctness.

For each non-final step, we compute the shortest-path distance from the graph-linked entities newly retrieved or newly cited at that step to the answer node: \[d_t = \min_{v \in \Delta O_t \cup \Delta C_t} d_q(v, v_q^\ast).\] Here, \(\Delta O_t\) and \(\Delta C_t\) follow the definitions in Section 3. We then track the best distance reached up to step \(t\): \[d^{\mathrm{best}}_t = \min_{s \le t} d_s .\] This prefix-based measure reflects the closest point reached so far.

4pt max width=.95

Table [tab:rq1-best-distance] shows that correct trajectories consistently reach smaller history-best distances than incorrect ones, and the gap generally expands as search proceeds. As an auxiliary check, the GDCR step score is positively correlated with final-answer correctness (\(r=0.334\), \(p<10^{-179}\)). These results support graph distance as a useful progress prior for GDCR.

4.3 RQ2: Does SAPO Improve Search-Agent Performance?↩︎

4pt max width=.95

Table [tab:main] shows that SAPO consistently improves over SFT and GRPO across both model scales. At the 8B scale, SAPO also outperforms ARPO on all four benchmarks under the same rollout budget; the efficiency comparison in Appendix 9.4 further suggests that ARPO incurs higher training cost. The gains are larger on Qwen3-30B-A3B-thinking, where SAPO achieves the best results among models evaluated in our environment. These results indicate that GDCR provides useful step-level credit beyond trajectory-level outcome rewards while preserving the final-answer objective.

4.4 RQ3: Which Reward Components of GDCR Matter?↩︎

We conduct an ablation study on Qwen3-8B to examine the contribution of the two reward components in GDCR.

Table 1 shows that both GDCR components are needed. Removing either newly-retrieved or newly-cited rewards hurts performance, while the full GDCR achieves the best or tied-best result on all four benchmarks.

4.5 RQ4: How Robust and Efficient Is SAPO?↩︎

SAPO provides step-level credit without generating additional search branches during training. On Qwen3-8B under the same hardware setting, SAPO takes 13.26 minutes per training step, adding only about 1% overhead over GRPO, while ARPO costs 16.25 minutes per step, or 1.24\(\times\) the GRPO cost, under the same rollout budget. More efficiency results, including the estimated cost of Tree-GRPO [16], can be found in Appendix 9.4.

Table 2 shows that SAPO remains stable under moderate graph corruption. Performance drops more visibly under stronger noise, especially when the answer node is perturbed, confirming that graph quality remains important.

4.6 RQ5: Does GDCR Improve Step-Level Search and Citation Behavior?↩︎

Progress Toward the Answer Node. We evaluate Qwen3-8B models trained with GRPO and SAPO on the development set. As shown in Figure 3, SAPO yields a steeper decrease in average shortest-path distance and maintains a lower distance than GRPO throughout most of the trajectory.

Newly-Cited Entities. Figure 4 shows that adding the newly-cited reward increases the proportion of retrieved entities that are later explicitly cited in the trajectory. This suggests that GDCR not only guides retrieval, but also encourages the agent to explicitly cite retrieved entities.

4.7 Additional Analysis↩︎

Sensitivity to Step-Level Reward Weight. We first examine the sensitivity of SAPO to the step-level reward weight \(\lambda\).

Table 3 shows that removing the GDCR-based step advantage reduces SAPO to GRPO, while \(\lambda=0.5\) gives the best overall performance.

Sensitivity to Distance Decay. We then vary the graph-distance decay factor \(k\) in the graph-distance contribution score.

Table 4 shows that \(k=2\) gives the best overall performance, while \(k=1\) removes the graph-distance distinction and degrades performance.

Inference Budget Scaling. We also include inference budget scaling results under different context-length and tool-call limits in Appendix 9.5.

5 Related Work↩︎

Search Agent. Search agents tackle complex, knowledge-intensive tasks that are difficult for single-pass inference by iteratively invoking external retrieval tools and reasoning over the returned evidence. Existing research in this domain primarily follows two technical trajectories: one line of work constructs large-scale, high-quality synthetic training data to improve complex information retrieval and reasoning capabilities [25]–[27]; the other improves RL algorithms for search agents [28], [29]. However, most RL methods still provide advantage signals at the trajectory level. Although some approaches employ tree sampling to allocate trajectory-level advantages to intermediate steps [14], [15], they remain constrained by high computational overhead, making it difficult to scale toward genuine step-level modeling.

Process Reward in Agent Reinforcement Learning. Process rewards improve agentic reinforcement learning by providing fine-grained credit assignment and more informative optimization signals. Existing research primarily constructs advantage signals at two granularities: one class combines process rewards with outcome rewards at the trajectory level [28]–[32], yet typically broadcasts the aggregated reward uniformly across all steps. The other class uses step-level advantage signals to guide model learning. Within this category, some methods introduce step-wise rewards based on PPO [33], [34], but depend on critic models; others perform dense tree sampling at each step, which becomes expensive for long-horizon multi-turn tasks [35]. Recent works therefore shift toward critical-step branch sampling strategies [14]–[18], but still incur additional rollout cost. SAPO differs from these approaches by using GDCR as a training-time graph-distance reward, avoiding the overhead of critic models or dense tree searches while providing fine-grained step-level advantage assignment.

6 Conclusion↩︎

We presented GDCR, a graph-distance step-level reward for complex information-seeking tasks with definitive answers, and SAPO, an optimization method that converts process rewards into step-level advantages. By using a training-time ER graph to score newly-retrieved entities and newly-cited entities, GDCR provides step-level process rewards for Agentic Search training, while SAPO combines them with the trajectory-level correctness objective. Experiments and analyses show that this design improves Agentic Search training while keeping the overhead substantially lower than rollout-heavy step-level methods.

Limitations↩︎

Our method is designed for complex information-seeking tasks with definitive answers. GDCR requires an answer node in the training-time ER graph, and therefore does not directly apply to open-ended generation, subjective analysis, or tasks without a clear endpoint.

The data synthesis and search environment also introduce reproducibility costs. The policy optimization objective and reward computation can be implemented independently of a specific retrieval backend, but absolute benchmark performance may still depend on the search engine, document index, and graph-construction pipeline used during training and evaluation.

7 Format↩︎

Our ReAct framework follows the format shown in Figure 5:

8 QA Pair Synthesis with Graphs↩︎

To facilitate the calculation of GDCR, it is imperative that each QA pair be associated with a training-time ER graph encompassing relevant entities and relationships. Since existing open-source data synthesis workflows fail to meet this requirement, we established two distinct data synthesis pipelines. Specifically, we synthesize data employing the following two methodologies:

Knowledge Graph-Centric Approach. For the Chinese dataset, we constructed a large-scale knowledge graph utilizing page content from Baidu Baike. We initiate the process by selecting an arbitrary starting node within the knowledge graph and employing a random walk strategy to derive a candidate training-time Entity-Relation (ER) graph. To ensure graph quality and reduce shortcut solutions, we apply three validations during synthesis. First, distant unreachability checks that nodes multiple hops away from the answer cannot directly retrieve the answer. Second, intermediate unskippability checks that target nodes cannot be retrieved by skipping their immediate predecessors along the path. Third, connectivity checks that adjacent nodes can retrieve each other, ensuring valid local paths. We then task GPT-4o with generating initial questions based on the validated training-time ER graph, which are further complicated through techniques such as obfuscation. After QA generation, we apply two additional quality-control steps: filtering out trivial questions that can be directly answered by the model, and using LLM-as-a-judge to verify logical consistency and the correspondence among the question, answer, and training-time ER graph.

Search Agent-Centric Approach. For the English dataset, we leverage the open-source data synthesis pipeline from Asearcher [20]. We keep the original QA synthesis process and add an ER graph construction step: after the final questions are generated, we instruct the model to construct a corresponding training-time ER graph for each QA pair based on the Supporting Statements. The specific prompt utilized for this process is illustrated in Figure [fig:prompt95graph].

9 Experiment Detail↩︎

9.1 Evaluation Baselines.↩︎

Regarding open-source models, we evaluated Mirothinker-8B/30B [36], WebSailor-7B/32B [37], WebExplorer-8B [38], and Tongyi DeepResearch [13] under our current experimental conditions. Specifically, we assessed the 30B models using a 128K context budget and the 7B/8B models using a 64K context budget. An exception was made for WebSailor-7B/32B, which was tested at its maximum position embedding limit of 32K. For closed-source models (GLM-4.6 [39], GLM-4.7 [40], OpenAI-o3 [41], Kimi K2 [42], and Web-30B-E-GRPO [28]), we report scores derived from official technical reports or prior papers.

9.2 Search Environment.↩︎

We employed an internal KG-search tool as our primary search interface, which integrates Quark’s third-party search API [43] and leverages approximately 8 billion documents from our proprietary knowledge base for document retrieval. The system performs unified ranking and returns the top 20 search results, with each result providing the most relevant passage from the full text, limited to 300 characters per passage. During the training phase of the 8B model, we used only the top 5 retrieved results. Although our production environment also supports PDF and document parsing capabilities, as well as a visit tool for retrieving complete webpage content, these additional tools were excluded from our experimental comparisons to ensure fair evaluation across all models.

9.3 Training Details.↩︎

Qwen3-8B SFT. For the cold-start SFT phase on the 8B model, we curate 492 high-quality trajectories with a maximum length of 32k tokens. These trajectories are collected through rejection sampling with Qwen3-235B-A22B on our synthesized dataset. We fine-tune the model for 5 epochs with a batch size of 16 and a learning rate of \(4 \times 10^{-5}\).

Qwen3-8B RL. For RL, we synthesize 1,000 QA pairs with training-time ER graphs, including 600 Chinese and 400 English samples, and use 500 examples as a development set for analysis. The 8B RL training uses a 32k context length, a tool-call budget of 20, a training batch size of 32, a PPO batch size of 32, a group size of 8, and a learning rate of \(2 \times 10^{-6}\) for approximately 3 epochs. This training run is conducted for 20 hours on 16 H200 141G GPUs.

Qwen3-30B-A3B SFT. For the 30B model, due to differences in context length requirements and MoE architecture demands for training data, we utilize 1,400 high-quality QA pairs generated using the same methodology as the 8B model. Through rejection sampling with Qwen3-235B, we obtain approximately 10,000 training trajectories. The 30B model is trained with a learning rate of \(7 \times 10^{-6}\), batch size of 512, for 3 epochs, with a maximum context length of 64k tokens, warmup ratio of 0.03, and moe-aux-loss-coeff of 0.02.

Qwen3-30B-A3B RL. The 30B model employs similar RL settings as the 8B model, but with key modifications for MoE training stability. We incorporate the router replay method [44] to address the training-inference consistency issues in MoE models, where routing mechanisms can introduce instability and lead to catastrophic RL training collapse. This method records routing distributions from the inference engine and replays them during training to mitigate the discrepancy in routing behaviors. Additionally, leveraging the A3B model’s enhanced context capabilities, we use a 64k context limit (24k for prompts + 40k for responses) during RL training. Due to resource constraints, all reported test results are from single runs.

9.4 Training Efficiency↩︎

4pt max width=

As shown in Table [tab:efficiency], SAPO preserves the training cost profile of linear trajectory optimization, while ARPO incurs additional branch-sampling cost and complete tree expansion becomes substantially more expensive for long-horizon search trajectories.

9.5 Inference Budget Scaling↩︎

We further evaluate how the 30B model scales under different inference budgets. These experiments vary the context-length limit and the tool-call limit on BrowseComp-ZH and BrowseComp. The results are intended as supplementary evidence for inference-time efficiency and are not part of the main controlled training-cost comparison in Table [tab:efficiency].

4pt max width=

4pt max width=

4pt max width=

As shown in Tables [tab:context-scaling]–[tab:tool-call-scaling], SAPO-30B scales steadily as the context budget increases and maintains competitive accuracy with lower average token consumption at the 128K limit. Under increasing tool-call budgets, SAPO-30B remains stable, while GRPO-30B and Miro-30B degrade when the interaction budget becomes large. This suggests that SAPO improves not only final accuracy, but also the agent’s ability to manage long search trajectories under larger inference budgets.

10 Data and Artifact Documentation↩︎

10.1 Data Screening and Anonymization↩︎

We apply automatic filtering and LLM-as-a-judge verification during data synthesis to remove offensive or unsafe content, and we exclude examples involving private personal identifiers. The released data and artifacts are anonymized and do not include author information or annotator identities.

10.2 Dataset Scope↩︎

Our data covers both Chinese and English information-seeking tasks. The Chinese data is synthesized from Baidu Baike-style encyclopedic knowledge, covering broad factual domains such as people, organizations, locations, events, and cultural entities; the English data follows a Wikipedia-based synthesis pipeline and covers similar open-domain encyclopedic topics.

10.3 Licensing and Terms↩︎

We use cited model checkpoints, evaluation benchmarks, and open-source data synthesis methods in accordance with their stated licenses and access terms. For redistributed artifacts, we preserve the required citations and license notices, and release only generated data, code, and prompts that are compatible with research use.

11 Case Study↩︎

To qualitatively illustrate the differences between SAPO and GRPO, we conducted a comparative case study on the same question using trajectories generated by Qwen3-8B-SAPO and Qwen3-8B-GRPO. As shown in Figure 6, SAPO progressively retrieved and cited answer-relevant entities and ultimately answered the question correctly. However, the GRPO trajectory (as shown in Figure [fig:badcase]) gradually deviated from the answer node and ultimately led to an error.

References↩︎