ACL Findings2026
Breaking the Static Graph: Context-Aware Traversal for Graph-Based RAG
Kwun Hang Lau, Fangyuan Zhang, Boyu Ruan, Yingli Zhou, Qintian Guo, Ruiyuan Zhang, Xiaofang Zhou
Abstract
Recent advances in Retrieval-Augmented Generation (RAG) have shifted from simple vector similarity to structure-aware approaches like HippoRAG, which leverage Knowledge Graphs (KGs) and Personalized PageRank (PPR) to capture multi-hop dependencies. However, these methods suffer from a "Static Graph Fallacy": fixed transition probabilities set during indexing ignore query-dependent edge relevance, causing semantic drift where random walks are diverted into high-degree "hub" nodes before reaching critical evidence. Models often achieve high partial recall but fail to retrieve the complete evidence chain for multi-hop queries. To address this, we propose CatRAG, Context-Aware Traversal for robust RAG, which builds on the HippoRAG 2 and transforms the static KG into a query-adaptive navigation structure. CatRAG steers the random walk via three mechanisms: (1) Symbolic Anchoring, injecting weak entity constraints to regularize the random walk; (2) Query-Aware Dynamic Edge Weighting, dynamically modulating graph structure to prune irrelevant paths and amplify query-aligned ones; and (3) Key-Fact Passage Weight Enhancement, a cost-efficient bias anchoring the walk to key evidence. Experiments across multi-hop benchmarks show that CatRAG outperforms state-of-the-art baselines. While standard Recall gains are modest, CatRAG achieves substantial improvements in reasoning completeness-the capacity to recover entire evidence chains without gaps. These results reveal that CatRAG effectively bridges the gap between retrieving partial context and enabling fully grounded reasoning. Resources are available at https://github.com/kwunhang/CatRAG.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on17
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Self-RAG: Learning to Retrieve, Generate, and Critique through Self-ReflectionAkari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil et al.ICLR 2024 · 1,798 citations
- HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language ModelsBernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga et al.NeurIPS 2024 · 395 citations
- Knowledge Graph Prompting for Multi-Document Question AnsweringYu Wang, Nedim Lipka, Ryan A. Rossi, Alexa F. Siu et al.AAAI 2024 · 290 citations
- LightRAG: Simple and Fast Retrieval-Augmented GenerationZirui Guo, Lianghao Xia, Yanhua Yu, Tu Ao et al.EMNLP Findings 2025 · 209 citations
Related papers
- HopRAG: Multi-Hop Reasoning for Logic-Aware Retrieval-Augmented GenerationHao Liu, Zhengren Wang, Xi Chen, Zhiyu Li et al.ACL Findings 2025 · 24 citations
- Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval GuaranteesZhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu et al.ICLR 2026 · 6 citations
- PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented GenerationXiangjun Zai, Xingyu Tan, Xiaoyang Wang, Qing Liu et al.WWW 2026 · 1 citation
- NaviRAG: Learning to Navigate Knowledge Graphs for Retrieval-Augmented GenerationJinghong Lei, Wang Kun, Zhigang Chen, Zhao XinKDD 2026
- FlowRAG: Synergizing Explicit Reasoning via Frequency-Aware Multi-Granularity Graph FlowBihao Zhan, Zongsheng Cao, Jie Zhou, Bo Zhang et al.ACL Findings 2026
