NaviRAG: Learning to Navigate Knowledge Graphs for Retrieval-Augmented Generation
Jinghong Lei, Wang Kun, Zhigang Chen, Zhao Xin
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.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Dynamic Graph Navigation via Triplet Chains for Structure-Aware Retrieval-Augmented GenerationFeng Zhao, Yufei Wu, Xianggan Liu, Ruilin ZhaoACL Findings 2026
- Towards Open-World Retrieval-Augmented Generation on Knowledge Graph: A Multi-Agent Collaboration FrameworkJiasheng Xu, Mingda Li, Yongqiang Tang, Peijie Wang et al.WWW 2026
- EvoGraph-R1: Self-Evolving Multimodal Knowledge Hypergraphs for Agentic RetrievalJiashi Lin, Changhong Jiang, Xiangru Lin, Ruifei Zhang et al.CVPR 2026 · 2 citations
- You Don't Need Pre-Built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning StructuresShengyuan Chen, Chuang Zhou, Zheng Yuan, Qinggang Zhang et al.AAAI 2026 · 14 citations
- ReGraphRAG: Reorganizing Fragmented Knowledge Graphs for Multi-Perspective Retrieval-Augmented GenerationSoohyeong Kim, Seok Jun Hwang, JungHyoun Kim, Jeonghyeon Park et al.EMNLP Findings 2025 · 5 citations
