Source-linked AI summary
Breaking the Static Graph: Context-Aware Traversal for Robust Retrieval-Augmented Generation
Kwun Hang Lau, Fangyuan Zhang, Boyu Ruan, Yingli Zhou, Qintian Guo, Ruiyuan Zhang, Xiaofang Zhou
TL;DR
Static graph transitions in structure-aware RAG can ignore query-dependent edge relevance, causing semantic drift and incomplete evidence chains in multi-hop retrieval. CatRAG converts the graph into a query-adaptive navigation structure using symbolic anchoring, dynamic edge weighting, and key-fact passage enhancement. Across multi-hop benchmarks, it consistently outperforms baselines and substantially improves reasoning completeness, especially full-chain evidence recovery.
Problem
Fixed transition probabilities in graph-based RAG ignore query-dependent edge relevance, allowing semantic drift and preventing complete evidence-chain recovery for multi-hop queries.
Method
CatRAG refines the static transition matrix into a query-specific matrix using symbolic anchoring, query-aware dynamic edge weighting, and key-fact passage weight enhancement.
Results
CatRAG consistently outperforms baselines across multi-hop benchmarks and substantially improves Full Chain Retrieval and Join Set Recall.
Takeaways & Limitations
Context-aware graph steering bridges partial-context retrieval and fully grounded multi-hop reasoning by anchoring traversal to specific evidence chains.
Takeaways & Limitations
Runtime LLM inference for dynamic edge weighting adds computational overhead and latency, making CatRAG more intensive than standard dense retrieval.
Abstract
from arXiv · showhide
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": they rely on fixed transition probabilities determined during indexing. This rigidity ignores the query-dependent nature of edge relevance, causing semantic drift where random walks are diverted into high-degree "hub" nodes before reaching critical downstream evidence. Consequently, models often achieve high partial recall but fail to retrieve the complete evidence chain required for multi-hop queries. To address this, we propose CatRAG, Context-Aware Traversal for robust RAG, a framework that builds on the HippoRAG 2 architecture and transforms the static KG into a query-adaptive navigation structure. We introduce a multi-faceted framework to steer the random walk: (1) Symbolic Anchoring, which injects weak entity constraints to regularize the random walk; (2) Query-Aware Dynamic Edge Weighting, which dynamically modulates graph structure, to prune irrelevant paths while amplifying those aligned with the query's intent; and (3) Key-Fact Passage Weight Enhancement, a cost-efficient bias that structurally anchors the random walk to likely evidence. Experiments across four multi-hop benchmarks demonstrate that CatRAG consistently outperforms state of the art baselines. Our analysis reveals that while standard Recall metrics show modest gains, CatRAG achieves substantial improvements in reasoning completeness, the capacity to recover the entire evidence path without gaps. These results reveal that our approach effectively bridges the gap between retrieving partial context and enabling fully grounded reasoning. Resources are available at https://github.com/kwunhang/CatRAG.
1 Introduction
Structure-aware RAG addresses multi-hop retrieval better than dense similarity, but fixed graph transitions can divert traversal from query-relevant evidence. CatRAG makes traversal context-aware through symbolic anchors, dynamic edge weighting, and passage-level evidence weighting, improving complete-chain retrieval.
- Motivation: Dense retrieval often fails when multi-hop answers require connecting disjoint facts, motivating structure-aware trees and knowledge graphs.HippoRAG uses Personalized PageRank over knowledge graphs to capture long-range dependencies.
- Problem: Fixed transition probabilities make edge relevance context-independent and can cause random walks to drift into generic or high-degree hub nodes.This may retrieve an initial entity while missing downstream evidence, leaving the reasoning chain broken despite high partial Recall.
- Approach: CatRAG injects recognized entities as weak anchors, dynamically reweights outgoing edges by query relevance, and boosts passages containing verified evidentiary triples.These mechanisms constrain starting distributions, prune irrelevant paths, amplify aligned edges, and favor distinct evidence over superficial entity mentions.
- Results: Across multiple multi-hop benchmarks, CatRAG consistently improves standard retrieval metrics and substantially improves Full Chain Retrieval.The reported result links dynamic graph steering with more complete evidence-chain recovery than static baselines.
2 Related Work
RAG has progressed from flat vector matching toward hierarchical, graph-based, and iterative retrieval methods for structural and multi-step reasoning. CatRAG instead modifies graph edges once before traversal, targeting adaptive retrieval while retaining a single-pass graph workflow.
- Vector Retrieval: Large embedding models improve vector-retrieval benchmarks, but vector-space retrieval remains constrained by static representations.This limitation motivates adding explicit structural priors to retrieval.
- Structure-Aware Retrieval: Hierarchical systems organize text into recursive trees, while GraphRAG, LightRAG, HippoRAG, and HippoRAG 2 use knowledge graphs to traverse entity relationships.HippoRAG and HippoRAG 2 simulate associative memory with Personalized PageRank to link disparate facts.
- Iterative Retrieval: Iterative and agentic retrieval frameworks refine searches through multiple steps but incur high latency and computational costs from repeated LLM calls.Their multi-step loops distinguish them from CatRAG’s one-shot graph modification.
- CatRAG: CatRAG dynamically reweights graph edges before traversal, combining adaptive retrieval precision with a single retrieval pass and graph structure.This design is presented as an alternative to iterative search cycles.
3 Methodology
CatRAG converts HippoRAG 2’s static knowledge graph into a query-specific navigation structure by combining symbolic anchors, dynamic edge weighting, and key-fact passage enhancement. The resulting graph is traversed with PPR to prioritize passages reached through query-relevant reasoning paths.
- Overview: CatRAG extends HippoRAG 2 with Symbolic Anchoring, Query-Aware Dynamic Edge Weighting, and Key-Fact Passage Weight Enhancement.These mechanisms jointly optimize retrieval over a knowledge graph.
- Graph Preliminaries: PPR uses a query-specific transition matrix ˆTq instead of the standard static transition matrix T.The query-adapted matrix is designed to better capture the reasoning requirements of each user query.
- Symbolic Anchoring: Weak symbolic seeds place probability on named query entities, resisting diffusion into generic high-degree hubs.The anchors remain subordinate to the initial contextual-triple entity while repeatedly grounding propagation in query-specific entities.
- Adaptive Entity Contextualization: Dense-node context uses concise summaries when |F(v)| exceeds τ and raw triples otherwise, balancing completeness with token efficiency.The context C(v) supports LLM evaluation of transitions from seed u to neighbor v.
- Stage I: Coarse-Grained Candidate Pruning: A topological filter selects up to Nseed entities and Kedge neighbors, assigning bypassed edges minimal Weak weight before semantic scoring.Neighbors are prioritized using similarity between the query embedding and relation-edge fact embeddings, reducing the costly edge-scoring search space.
- Stage II: Fine-Grained Semantic Probability Alignment: An LLM classifies surviving transitions as Irrelevant, Weak, High, or Direct, then maps those tiers to scalar weights for query-conditioned propagation.The model evaluates whether transition u →v is necessary given query q and the neighbor summary C(v).
- Key-Fact Passage Weight Enhancement: Key-Fact Enhancement boosts seed-to-passage edges supported by verified seed triples through an algorithmic triple match.Unlike LLM-based weighting, this adjustment adds zero token cost and negligible latency while prioritizing evidentiary passages.
- Query-Adapted Traversal: Standard PPR runs on the refined graph, and its stationary distribution produces the final passage ranking.The ranking prioritizes nodes reachable through semantically relevant reasoning paths.
4 Experimental Setup
CatRAG is evaluated against standard and structure-aware retrieval baselines on four multi-hop benchmarks covering question answering and fact verification. The evaluation reports retrieval, downstream QA, and reasoning-completeness metrics using a controlled HippoRAG 2-based implementation.
- Baselines: The baseline suite spans standard retrieval methods and structure-aware systems, including BM25, Contriever, GTR, text-embedding-3-small, RAPTOR, LightRAG, and HippoRAG 2.The comparisons cover embedding-based retrieval, recursive trees, and knowledge-graph frameworks.
- Datasets: Experiments use MuSiQue, 2WikiMultiHopQA, HotpotQA, and HoVer across multi-hop question answering and fact verification.The QA datasets require reasoning over multiple passages, while HoVer extends chains to three and four hops.
- Metrics: The evaluation reports Recall@5 for retrieval and F1 for downstream question answering, alongside Full Chain Retrieval and Joint Success Rate.FCR measures whether retrieved context contains all gold supporting documents, while JSR requires joint retrieval and answer success.
- Implementation: Key settings include symbolic anchor reset probability ϵ = 0.2, boost factor β = 2.5, Nseed = 5, and Kedge = 15.These hyperparameters govern symbolic anchoring, key-fact enhancement, and dynamic edge-weighting limits.
5 Results
CatRAG improves retrieval and downstream QA performance across multi-hop benchmarks, while especially strengthening recovery of complete evidence chains. Its components contribute differently, with Key-Fact Enhancement helping unstructured datasets but introducing slight noise on 2WikiMultiHopQA.
- Standard Retrieval and QA: CatRAG achieves Recall@5 of 64.9% on MuSiQue, exceeding text-embedding-3-small by 8.1%, and reaches 89.5% on HotpotQA and 76.8% on HoVer.The reported comparisons cover dense retrieval and the static HippoRAG 2 baseline across multiple benchmarks.
- Standard Retrieval and QA: CatRAG yields the highest downstream F1 scores across datasets, including 45.0% on MuSiQue.Table 3 reports F1 for QA datasets and accuracy for HoVer.
- Strict Reasoning Completeness Evaluation: CatRAG improves Full Chain Retrieval to 34.6% versus 30.5% for HippoRAG 2 and raises Joint Success Rate to 31.1%, a relative gain of 18.7%.These metrics evaluate recovery of complete evidence paths rather than only general relevance.
- Ablation Study: Removing Symbolic Anchoring causes consistent degradation, including a 3.2% drop on HoVer.The ablation isolates Symbolic Anchoring, Query-Aware Dynamic Edge Weighting, and Key-Fact Passage Weight Enhancement.
- Ablation Study: Key-Fact Enhancement provides consistent gains on HotpotQA, MuSiQue, and HoVer but introduces slight noise and a minor regression on 2WikiMultiHopQA.The authors prioritize its gains on unstructured datasets because real-world RAG scenarios involve messy, unstructured corpora.
6 Discussion
CatRAG addresses hub bias in static graph retrieval by measuring and reducing the prominence of generic high-connectivity nodes. Its left-shifted PPR-weighted distributions and lower hub probability mass align with improved reasoning completeness.
- Mitigating Hub Bias: Static graph formulations disproportionately converge on high-degree nodes, diverting retrieval from bridge entities needed to connect disjoint facts.This hub bias is identified as a source of semantic drift in multi-hop retrieval.
- Measuring Structural Prominence: PPR-Weighted Strength (Sppr) measures the effective structural prominence of retrieved context using normalized PPR mass and weighted node degree.Higher Sppr indicates greater reliance on generic, high-connectivity nodes.
- Mitigating Hub Bias: CatRAG shifts the Sppr distribution left relative to HippoRAG 2, indicating reduced retrieval of high-degree hub nodes.The figure compares the two methods’ distributions and marks each method’s mean with dashed lines.
- Mitigating Hub Bias: CatRAG reduces Mean PPR-Weighted Strength from 837.0 to 761.7.The lower mean indicates less structural prominence assigned to generic high-connectivity nodes.
- Mitigating Hub Bias: CatRAG reduces probability mass assigned to Super Hubs from 45.7% to 42.5%.Super Hubs are nodes in the top 1% of weighted degree.
- Reasoning Completeness: The structural shift aligns with improved reasoning completeness by redistributing probability away from topological distractors toward specific bridge entities.The analysis connects this redistribution to preserving complete dependency chains and improving JSR on HoVer.
7 Conclusion
The paper identifies the Static Graph Fallacy as a source of semantic drift and incomplete evidence-chain recovery. CatRAG replaces static knowledge-graph traversal with context-aware navigation that improves benchmark performance and reasoning completeness.
- Conclusion: The Static Graph Fallacy arises when fixed transition probabilities predispose structure-aware retrieval to semantic drift and incomplete evidence chains.The paper frames this as a limitation of current structure-aware RAG systems.
- Conclusion: CatRAG transforms knowledge-graph traversal into a context-aware navigation structure.The framework is presented as a response to fixed transition probabilities in graph retrieval.
- Conclusion: Across multi-hop benchmarks, CatRAG consistently outperforms baselines, including HippoRAG 2, while reducing high-degree hub bias.The conclusion links these topological adjustments to more complete, grounded multi-hop reasoning.
Limitations
CatRAG improves reasoning completeness but trades efficiency for query-aware traversal. Runtime LLM inference adds computational overhead and latency compared with static graph traversal and standard dense retrieval.
- Efficiency Trade-offs: Query-aware dynamic edge weighting requires runtime LLM inference to assess semantic relevance.This mechanism incurs additional computational overhead and latency compared with purely static graph traversals.
- Efficiency Trade-offs: Despite coarse-grained pruning, CatRAG remains more computationally intensive than standard dense retrieval.The limitation concerns efficiency rather than the reported reasoning-completeness gains.
8 Ethical considerations
The evaluation uses four public benchmark datasets derived from Wikipedia and Wikidata and does not collect new personal data or involve human participants. The study also documents its use of external model APIs and generative AI assistance.
- Data and Participants: The study evaluates four publicly available benchmarks derived from Wikipedia and Wikidata: MuSiQue, 2WikiMultiHopQA, HotpotQA, and HoVer.These datasets may include publicly available information about real people and sensitive topics.
- Data and Participants: The study did not collect new personal data or interact with human participants.Its ethical context is limited to using existing benchmark sources.
- Computational Resources: The experiments used GPT-4o mini and text-embedding-3-small through Microsoft Azure and Llama-3.3-70B-Instruct through OpenRouter.The paper also acknowledges generative AI assistance for code implementation.
A.1 Implementation Details and Hyperparameters
CatRAG uses implementation settings that preserve HippoRAG 2’s benchmark prompts while introducing dynamic edge weighting and tiered LLM-based edge scoring.
- CatRAG maintains the QA prompts established in the HippoRAG 2 benchmark for fair comparison.
- Synonym Edge weights are dynamically scaled by vector similarity, unlike HippoRAG 2’s raw vector-similarity weighting.
- LLM semantic scores are projected onto four tiers—Irrelevant, Weak, High, and Direct—to convert relevance assessments into graph weights.
- The scoring schedule prunes scores ≤3 and amplifies high-confidence evidence paths through a nonlinear weight mapping.