PRAISE: Prefix-Based Rollout Reuse in Agentic Search Training

Erhan Zhang, Yiqun Chen, Zechun Niu, Wei Yang, Xiaochi Wei, Yan Gao, Yi Wu, Yao Hu, Jiaxin Mao · 2026

Read PRAISE: Prefix-Based Rollout Reuse in Agentic Search Training by Erhan Zhang, Yiqun Chen, Zechun Niu, Wei Yang, Xiaochi Wei, Yan Gao, Yi Wu, Yao Hu, Jiaxin Mao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03675.txt.

Introduction

Erhan Zhang and colleagues built a training method for search agents that learn by trial and reward. Outcome-only rewards give thin guidance for middle search steps, and fixed judges grow stale as the agent improves. Their OASES system therefore scores each intermediate step by how well it supports the final answer. The judge and the search policy train together, and tests on five multi-step question benchmarks beat strong reinforcement-learning rivals.

Catalog record

CREATORErhan Zhang, Yiqun Chen, Zechun Niu, Wei Yang, Xiaochi Wei, Yan Gao, Yi Wu, Yao Hu, Jiaxin Mao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33768
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.03675

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

PRAISE: Prefix-Based Rollout Reuse in Agentic Search Training Erhan Zhang, Yiqun Chen, Zechun Niu, Wei Yang, Xiaochi Wei, Yan Gao, Yi Wu, Yao Hu, Jiaxin Mao Abstract In agentic search, large language models (LLMs) are trained to perform multi-turn retrieval and reasoning for complex tasks such as multi-hop question answering (QA). However, current search-based Reinforcement Learning (RL) methods suffer from two core limitations: expensive long-horizon rollouts are under-utilized during training, and supervision is typically available only at the final answer, resulting in severe reward sparsity. We present P refix-based R ollout reuse for A gentic search with I ntermediate S tep r E wards (PRAISE), a framework for improving both data efficiency and credit assignment in agentic search training. Given a complete search trajectory, PRAISE extracts prefix states at different search turns, elicits intermediate answers from them, and uses these prefixes both to construct additional training trajectories and to derive step-level rewards from performance differences across prefixes. Our method uses a single shared model for both search policy learning and prefix answer evaluation, enabling joint optimization without extra human annotations or a separate reward model. Experiments on multi-hop QA benchmarks show that PRAISE consistently improves performance over strong baselines. 1 Introduction Large language models (LLMs) are increasingly moving beyond one-shot generation toward agentic problem solving, where a model interacts with external tools and environments over multiple steps to reason, plan, and act Yao et al. 2022 ; Schick et al. 2023 . Among these emerging paradigms, agentic search has become a particularly important framework for knowledge-intensive tasks such as multi-hop question answering (QA), deep research, and open-domain reasoning Li et al. 2025 ; Jin et al. 2025 ; Song et al. 2025 . Instead of relying on a fixed retrieval stage as in standard retrieval-augmented generation (RAG) Lewis et al. 2020 , agentic search enables a model to dynamically decide when to search, what to search for, and how to update its reasoning based on newly acquired evidence. This adaptive interaction with external information is crucial for solving problems whose answers cannot be obtained from parametric memory alone. To improve search and reasoning in such systems, recent work increasingly applies reinforcement learning (RL) to agentic search. In this setting, the model executes a multi-turn search trajectory and is trained based on the quality of its final answer or overall task performance. A particularly important paradigm is reinforcement learning with verifiable rewards (RLVR) Lambert et al. 2024 ; Guo et al. 2025 , where supervision comes from automatically checkable signals. By directly optimizing downstream task success, RLVR provides a natural training framework for agentic search. However, current search-based RL methods still face important limitations. A central issue is that supervision in search-based RL is typically available only at the trajectory level. A single rollout often contains multiple rounds of reasoning, querying, reading, and search-state updates, making it substantially more costly than ordinary single-pass generation. Yet, in most existing approaches, the full trajectory is still treated as a single training instance, with learning signals derived primarily from the final answer. This leads to poor data efficiency Liu et al. 2025 ; Huang and Wan : although a rollout contains multiple informative intermediate search states, existing methods typically consume it as a single training instance rather than converting those intermediate states into additional learnable examples, limiting the value extracted from each expensive rollout. At the same time, it also results in reward sparsity : because supervision arrives only at the end of the trajectory, it becomes difficult to determine which intermediate search actions improved answer quality and which were redundant or harmful Zheng et al. 2025 ; Cui et al. 2025 . This combination of under-utilized intermediate information and delayed feedback makes long-horizon credit assignment especially challenging. Prior work has attempted to address these issues from two largely separate directions. One line of research improves sample efficiency through replay buffers Sun et al. 2025 , trajectory reuse Wang et al. 2025b , or off-policy updates Chen et al. 2025a . Another line introduces denser supervision via process rewards Cui et al. 2025 , teacher-based evaluation Xie et al. 2026 , or intermediate annotations Zhang et al. 2025 ; Zheng et al. 2025 . However, these approaches remain limited in the agentic search setting. Existing reuse methods are typically centered around whole trajectories rather than the inherently compositional structure of multi-turn search. Meanwhile, process-supervision methods often rely on additional ingredients such as gold sub-questions, annotated evidence, separately trained reward models, or frozen teacher models, all of which introduce extra cost and may create mismatch between the evaluator and the evolving search policy. In this paper, we ask a simple but important question: how can we maximize the training value of each expensive search rollout? To answer this question, we propose PRAISE , short for P refix-based R ollout reuse for A gentic search with I ntermediate S tep r E wards. The key idea is to exploit the natural prefix structure of search trajectories. Given a complete multi-turn rollout, we extract prefix states at different search turns and prompt the model to produce intermediate answers conditioned only on the information available up to each prefix. These prefix–answer pairs are then used in two complementary ways. First, they provide rollout reuse . PRAISE converts a full rollout into multiple prefix-based training samples. In this way, intermediate search states that would otherwise be ignored are transformed into additional supervision, substantially increasing the amount of learnable signal extracted from each rollout. Second, they provide intermediate step rewards . By evaluating the quality of answers produced from different prefixes and comparing performance across adjacent prefixes, we estimate the marginal contribution of each search step. This converts sparse terminal supervision into fine-grained process rewards aligned with the search trajectory itself. Such reward densification leads to more informative training signals and improves long-horizon credit assignment. A central design choice of PRAISE is that the same model is used both for search policy learning and for prefix answer evaluation. This shared-model formulation avoids the need for an additional reward model, thereby reducing system complexity and annotation cost. More importantly, it allows search policy improvement and prefix evaluation capability to co-evolve through joint optimization, which in turn improves the consistency between the acting policy and the source of intermediate supervision Chen et al. 2026b ; Chen et al. 2026a . We evaluate PRAISE on multi-hop QA benchmarks. Experimental results show that our method consistently outperforms strong search-based RL baselines. Further analysis shows that the method is robust to key hyperparameters and that joint optimization with a shared model performs substantially better than alternatives based on frozen evaluators. Our contributions are summarized as follows: • We propose a prefix-based rollout reuse framework, transforming each expensive multi-turn search trajectory into multiple learnable prefix samples and improves rollout utilization. • We introduce a process reward construction method based on adjacent prefix gains to convert sparse terminal signals into fine-grained, step-aligned rewards. • We develop a joint optimization framework in which a single shared model performs both search decision making and prefix evaluation. • We demonstrate the effectiveness of PRAISE on multi-hop QA benchmarks, showing consistent improvements over strong baselines. 2 Related Work Agentic Search and

Read the complete text