RAG -Star: Enhancing Deliberative Reasoning with Retrieval Augmented Verification and Refinement (2025)

Abstract: Existing large language models (LLMs) show exceptional problem-solving capabilities but might struggle with complex reasoning tasks. Despite the successes of chain-of-thought and tree-based search methods, they mainly depend on the internal knowledge of LLMs to search over intermediate reasoning steps, limited to dealing with simple tasks involving fewer reasoning steps. In this paper, we propose RAG-Star , a novel RAG approach that integrates the retrieved information to guide the tree-based deliberative reasoning process that relies on the inherent knowledge of LLMs. By leveraging Monte Carlo Tree Search, RAG-Star iteratively plans intermediate sub-queries and answers for reasoning based on the LLM itself. To consolidate internal and external knowledge, we propose a retrieval-augmented verification that utilizes query- and answer-aware reward modeling to provide feedback for the inherent reasoning of LLMs. Our experiments involving Llama-3.1-8B-Instruct and GPT-4o demonstrate that RAG-Star significantly outperforms previous RAG and reasoning methods. Our codes and data are publicly available at https://github.com/RUCAIBox/RAG-Star.

## introduction despite the excellent capabilities of large language models (llms) @xcite , they still face significant challenges in complex reasoning tasks (e.g., multi-hop question answering), which often go beyond simple, single-step problem-solving, demanding a deeper level of cognitive reasoning across multiple facts, sources, or contexts @xcite . great efforts have been made to improve the reasoning effectiveness of llms by conducing step-by-step reasoning, exemplified by chain-of-thought (cot) @xcite . however, as the number of reasoning steps grows, llms are often prone to introduce logical errors, factual hallucinations, or inconsistent statements @xcite . in fact, step-by-step reasoning in the autoregressive generation paradigm can be described as akin to "system 1", a mode of thinking which is fast, instinctive but less accurate @xcite . conversely, solving complex reasoning problems requires more in-depth, deliberative, and logical thinking, known as the "system 2" mode, which requires conscious effort to conduct massive strategic decision-making @xcite . to enhance the "system 2" reasoning capabilities of llms, prior studies have proposed to conduct deliberative generation by leveraging basic tree search algorithms (e.g., monte carlo tree search @xcite ). however, llms in these studies mainly depend on their internal knowledge to search over intermediate reasoning steps, limited to handling problems with relatively simple reasoning process. to leverage external knowledge in model reasoning, extensive research has sought to augment llms with external information sources (a.k.a. retrievalaugmented generation, rag) @xcite , while existing efforts mainly consider sequential reasoning structure, which cannot naturally support more complex reasoning structure like mcts. thus, we raise the following research question: can rag enhance the deliberative reasoning capabilities of llms? in light of this, in this paper, we propose rag-star, a novel rag-enhanced framework designed to improve multi-step reasoning capabilities of llms with deliberative planning. as the major technical contribution, rag-star can fully exploit the internal knowledge of llms to plan the multistep reasoning, and meanwhile integrating the external retrieval to guide the internal reasoning process. to achieve this goal, we first introduce a tree-based search algorithm (i.e., monte carlo tree search, mcts) with llms to search over possible plans for solving the problem at hand where a complete plan is composed of a sequence of sub-queries and corresponding answers. starting from the input question (root node), rag-star iteratively generates and selects an appropriate sub-query and its answer (intermediate node), which aims to maximally explore the optimal sub-query path towards the final answer solely based on the inherent knowledge of llms. second, different from existing deliberation methods @xcite , rag-star proposes retrieval-augmented verification that involves both query-and answer-aware reward modeling, fully exploiting external sources to guide the internal deliberative reasoning. in our approach, instead of directly interfering in the reasoning process of llms, we consider employing rag to refine the derived reasoning steps in mcts, which can effectively reduce the conflicts between inherent and external knowledge, which has been a common issue when using rag methods @xcite . we conduct extensive experiments to verify the effectiveness of rag-star based on llama-3.1-8b-instruct and gpt-4o. our method outperforms the baselines by up to 18.98% and 16.19% on average for llama-3.1-8b and gpt-4o, respectively. our main contributions can be summarized as: ## related work retrieval-augmented llms. augmenting large language models (llms) with retrieval has been extensively studied in existing literature @xcite @xcite , which incorporates a differentiable retriever to provide external sources for llms. furthermore, llms have made significant advancements in many reasoning tasks, such as code generation (openai, 2023), math word problems @xcite and question answering @xcite . chain-of-thought (cot) has been reported as an emergent ability of llms when they are large enough @xcite , which encourages llms to generate explicit intermediate reasoning steps in reasoning rather than simply providing answers directly. to elicit or improve the multi-step reasoning capability of llms, several approaches seek to harness the strengths of both cot and retrieval on knowledge-intensive complex reasoning tasks, such as multi-hop question answering @xcite . the rationales gained from reasoning enhance the retrieval of more relevant information, while the retrieved knowledge improves the factuality of intermediate reasoning steps. however, these approaches primarily take retrieved documents as direct input to the model, easily suffering from knowledge conflicts between the parametric knowledge of llms and the external sources. in contrast, our rag-star framework integrates tree-based search to fully explore the solution space and repurpose the retrieval information as external guidance to the reasoning process. enhancing llms with search. applying search on top of llms has been a topic of much interest. several recent works have explored search algorithms to improve the performance of llms during the inference stage @xcite . the bitter lesson @xcite famously suggests that two forms of scaling, i.e., learning and search, supersede all other approaches. many studies have proven that scaling the inference-time computation can lead to substantial improvements in the performance of llms without training @xcite . these search algorithms, where multiple branches of outcomes are explored during search, have been widely applied in reinforcement learning algorithms @xcite and many real-world applications such as alphago @xcite for their good exploration-exploitation trade-off. however, these approaches mainly rely on the internal knowledge of llms to search potential solutions, which might not be optimal and leads to a amount of rollouts, significantly slowing down the decoding process. in this paper, we leverage the external retrieval sources to enhance the deliberative search process with llms, effectively differentiate the internal reasoning and external retrieval. ## preliminary in this section, we will first formally define our task and then introduce monte carlo tree search which is used in our proposed rag-star approach. task formulation. in this work, we mainly focus on open-domain multi-hop question answering @xcite , which requires multiple steps of reasoning across different documents to answer questions. previous work typically adopts an iterative reason-then-generate pipeline @xcite . at each step, the llm first infers an intermediate sub-query based on the current situation and then generates possible answers to the query. formally, given a natural language input question, at the t-th step, the llm m θ (parameterized by θ) first deliberately reasons about a sub-query q t , followed by generating an answer a t based on its inherent knowledge. in some literature @xcite , retrieval-augmented generation (rag) has been employed to improve the factuality of intermediate reasoning steps. for each subquery q t , the retriever retrieves top-k documents d @xmath0,k } k