Abstract

Existing large language models (LLMs) show exceptional problem-solvingcapabilities but might struggle with complex reasoning tasks. Despite thesuccesses of chain-of-thought and tree-based search methods, they mainly dependon the internal knowledge of LLMs to search over intermediate reasoning steps,limited to dealing with simple tasks involving fewer reasoning steps. In thispaper, we propose \textbf{RAG-Star}, a novel RAG approach that integrates theretrieved information to guide the tree-based deliberative reasoning processthat relies on the inherent knowledge of LLMs. By leveraging Monte Carlo TreeSearch, RAG-Star iteratively plans intermediate sub-queries and answers forreasoning based on the LLM itself. To consolidate internal and externalknowledge, we propose an retrieval-augmented verification that utilizes query-and answer-aware reward modeling to provide feedback for the inherent reasoningof LLMs. Our experiments involving Llama-3.1-8B-Instruct and GPT-4o demonstratethat RAG-Star significantly outperforms previous RAG and reasoning methods.