NaviRAG: Learning to Navigate Knowledge Graphs for Retrieval-Augmented Generation

Abstract

Retrieval-Augmented Generation (RAG) has become a fundamental paradigm for enhancing Large Language Models (LLMs) with external knowledge. However, while recent structure-augmented approaches organize documents into graphs to improve information access, their retrieval strategies remain largely static, relying on similarity ranking or static probability diffusion. We identify that this paradigm suffers from two inherent limitations in complex reasoning: popularity bias, where retrieval paths are trapped by high-degree distractors, and signal decay, where relevance signals attenuate over long reasoning chains. To overcome these challenges, we propose NaviRAG, a novel framework that reformulates retrieval as a reinforcement learning-driven dynamic navigation problem on schema-less knowledge graphs (KGs). Unlike passive diffusion, NaviRAG employs an agent that actively traverses the graph to act as a search-space pruning engine, identifying logical multi-hop reasoning paths. Technically, we introduce three key components: (1) Structure-Aware Query Expansion, which bridges the modality gap between unstructured queries and structured graph seeds for precise initialization; (2) Target-Driven Reward Shaping, which provides dense supervision based on semantic progress toward gold documents, effectively mitigating the sparse reward problem in large-scale graph traversal; and (3) a Multi-View Hybrid Reranking strategy that operates on the highly-pruned candidate subgraph, integrating policy confidence, semantic relevance, and global structural importance to ensure robust candidate selection. Extensive experiments on three multi-hop QA datasets and two single-hop QA datasets demonstrate that NaviRAG significantly outperforms baselines, achieving state-of-the-art performance in multi-hop QA while maintaining robustness in single-hop QA. Our code and data are available at https://github.com/CkingEW/NaviRAG.