Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees

Zhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu, Baruch GutowOxana Verkholyak, Masoud Faraki, Heng Hao, Hankyu Moon, Seungjai Min [0.5em] Samsung SDS Research America, Mountain View, CA, USA, [0.5em] Equal Contribution. Project Page · 2026

Read Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees by Zhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu, Baruch GutowOxana Verkholyak, Masoud Faraki, Heng Hao, Hankyu Moon, Seungjai Min [0.5em] Samsung SDS Research America, Mountain View, CA, USA, [0.5em] Equal Contribution. Project Page (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18775.txt.

Introduction

Zhuoping Zhou and nine colleagues present Query-Aware Flow Diffusion, a training-free method for graph-based retrieval. Older graph methods explore fixed neighbourhoods and give no promise about the quality of the retrieved subgraph. Their method weights each graph edge by how well its ends fit the query, steering flow along relevant paths only. The resulting subgraphs carry the first statistical promises for query-aware graph retrieval and beat leading graph methods in tests.

Catalog record

CREATORZhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu, Baruch GutowOxana Verkholyak, Masoud Faraki, Heng Hao, Hankyu Moon, Seungjai Min [0.5em] Samsung SDS Research America, Mountain View, CA, USA, [0.5em] Equal Contribution. Project Page
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109134
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18775

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees Zhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu, Baruch GutowOxana Verkholyak, Masoud Faraki, Heng Hao, Hankyu Moon, Seungjai Min [0.5em] Samsung SDS Research America, Mountain View, CA, USA, [0.5em] Equal Contribution. Project Page Abstract Graph-based Retrieval-Augmented Generation (RAG) systems leverage interconnected knowledge structures to capture complex relationships that flat retrieval struggles with, enabling multi-hop reasoning. Yet most existing graph-based methods suffer from (i) heuristic designs lacking theoretical guarantees for subgraph quality or relevance and/or (ii) the use of static exploration strategies that ignore the query’s holistic meaning, retrieving neighborhoods or communities regardless of intent. We propose Query-Aware Flow Diffusion RAG (QAFD-RAG), a training-free framework that dynamically adapts graph traversal to each query’s holistic semantics. The central innovation is query-aware traversal : during graph exploration, edges are dynamically weighted by how well their endpoints align with the query’s embedding, guiding flow along semantically relevant paths while avoiding structurally connected but irrelevant regions. These query-specific reasoning subgraphs enable the first statistical guarantees for query-aware graph retrieval, showing that QAFD-RAG recovers relevant subgraphs with high probability under mild signal-to-noise conditions. The algorithm converges exponentially fast, with complexity scaling with the retrieved subgraph size rather than the full graph. Experiments on question answering and text-to-SQL tasks demonstrate consistent improvements over state-of-the-art graph-based RAG methods. GraphRAG LightRAG QAFD-RAG Figure 1: Comparison of graph-based RAG methods on Wikipedia pages (Apple fruit, Apple Inc., Amazon River, Amazon.com). Query: “Introduce Steve Jobs’s products in Apple.” GraphRAG ( 21 ) retrieves entire communities, mixing relevant nodes (e.g., Mac, macOS) with irrelevant ones (e.g., Amazon River, Apple fruit). LightRAG ( 35 ) focuses on 1-hop neighborhoods, including both relevant nodes (e.g., Steve Jobs, iPhone) and structurally close but irrelevant ones (e.g., Fuji). QAFD-RAG reweights edges by the query’s holistic meaning , suppressing irrelevant one-hop neighborhoods and preventing traversal into the Amazon River, Amazon.com, and Apple fruit clusters. The resulting subgraph is coherent, with edge thickness reflecting weight and node mass indicating importance ( highest , lowest ); see the discussion following Eqn. ( 5 ). 1 Introduction Retrieval-Augmented Generation (RAG) enhances language models (LMs) by integrating external knowledge during generation ( 22 ; 33 ) . A retriever first gathers relevant information for a query, which is then combined with the input and passed to the generator ( 47 ) . This is especially useful for question answering (QA) ( 91 ; 108 ) , where added context improves accuracy in domains such as healthcare, law, finance, and education ( 93 ; 102 ) . With recent advances in large LMs (LLMs), RAG has become increasingly important for trustworthy AI, helping mitigate hallucinations ( 79 ) , improve transparency ( 48 ) , adaptability ( 71 ; 85 ) , privacy ( 100 ; 101 ) , fairness ( 72 ) , and reliability ( 23 ) . Although conventional RAG is effective for unstructured document retrieval, real-world knowledge often has graph-structured forms—such as database schemas, social networks, and biomedical repositories. These structures preserve relational information that similarity-based retrieval misses, including multi-hop dependencies, hierarchies, and complex interactions. Graph-oriented RAG leverages such properties through techniques such as community detection and graph neural networks ( 21 ; 86 ) , extending beyond similarity search to capture topological and semantic relationships ( 22 ; 33 ) . This enables advanced multi-hop reasoning crucial for tasks such as text-to-SQL generation, scientific discovery, and medical diagnosis, where understanding relationships is as important as retrieving facts ( 15 ; 89 ; 105 ) . For an overview, see the survey by 38 . However, existing graph-based RAG methods ( 38 ) suffer from heuristic designs lacking theoretical guarantees for subgraph quality or relevance and/or the use of static exploration strategies that ignore the query’s holistic meaning during traversal. As shown in Figure 1 , GraphRAG ( 21 ) applies uniform community detection regardless of query relevance, while LightRAG ( 35 ) extracts ego-networks around seed nodes without semantic alignment. In contrast, QAFD-RAG incorporates query semantics by reweighting edges and propagating mass along semantically aligned paths. Nodes on the reasoning chain (Apple \rightarrow Mac \rightarrow macOS) are emphasized with stronger colors, while irrelevant ones (Amazon River, Fuji) fade due to suppressed flow. This reweighting turns diffusion into a semantic filter, producing compact, interpretable subgraphs aligned with user intent. By contrast, holistic query-agnostic methods often include irrelevant nodes, omit distant but relevant information, and return unstructured lists rather than coherent reasoning paths. Lacking theoretical foundations, these heuristics also yield unpredictable performance. Given these limitations, we ask: Q: Under what conditions can we establish recovery guarantees for retrieving subgraphs that adapt to a query’s holistic meaning in graph-based RAG? To address this, we turn to graph diffusion theory and in particular flow diffusion —the process of spreading mass from seed nodes to neighbors along graph edges ( 57 ; 18 ; 25 ; 73 ; 29 ) . Spectral diffusion methods are effective for clustering and community detection due to strong guarantees and efficiency, but have not been studied in the presence of queries. We reformulate diffusion for graph-based RAG, linking flow/traversal to a query’s holistic meaning. Specifically, we propose Query-Aware Flow Diffusion RAG (QAFD-RAG), a framework for dynamic, query-aware graph traversal via principled flow diffusion. The main contributions of this work are: C1. Query-Aware Flow Diffusion Framework: We introduce the first principled flow diffusion method for graph-based RAG that incorporates query semantics via alignment-based edge weighting. QAFD-RAG adapts flow probabilities online, guiding traversal toward semantically relevant regions with complexity scaling with the retrieved subgraph size rather than the full graph (Figures 1 and 2 ). C2. Optimization and Statistical Guarantees: We provide the first rigorous analysis of query-aware traversal with provable guarantees. Our results (Theorem 3 ) show exponential convergence to a unique query-dependent stationary distribution, and recovery guarantees (Theorem 7 ) ensuring relevant subgraphs are retrieved with high probability under mild signal-to-noise conditions. C3. Experimental Validation: We evaluate QAFD-RAG on general QA (Tables 1 and 5 ), multi-hop QA (Table 3 ), long-document summarization (Table 2 ), and text-to-SQL (Table 4 ). Across these benchmarks, QAFD-RAG consistently outperforms state-of-the-art graph-based RAG baselines and improves over text-to-SQL baselines. Notation. Let \mathbb{R}^{d} be d -dimensional Euclidean space, and let \mathbb{R}^{d}_{+} and \mathbb{R}^{d}_{++} denote the nonnegative and strictly positive orthants. Vectors and matrices are in boldface (e.g., \mathbf{a} , \mathbf{A} ) with entries a_{i} and a_{ij} . For a matrix \mathbf{A} , \mathbf{A}_{i:} and \mathbf{A}_{:j} denote its i th row and j th column, and \mathbf{A}\succ 0 and \mathbf{A}\succeq 0 mean positive definite and positive semidefinite. For vectors, \|\mathbf{a}\|_{1}:=\sum_{i}|a_{i}| and \|\mathbf{a}\|:=\big(\sum_{i}|a_{i}|^{2}\big)^{1/2} . For matrices, \|\mathbf{A}\|_{F}:=\big(\sum_{i,j}|a_{ij}|^{2}\big)^{1/2} . For n\in\mathbb{N} , define [n]:=\{1,\ldots,n\} . We use standard asymptotic notations O , \Omega , \Theta , o , and \omega (as n\to\infty ). We write \triangleleft for a fixed deterministic tie-breaking order on any finite set. For a finite set U and scores f:U\to\mathbb{R} , Top - k_{u\in U}(f(u)) returns the k elements of U with largest scores, breaking ties by \triangleleft ; equivalently, if u_{(1)},\ldots,u_{(|U|)} are sorted in decreasing order of (f(u),\triangleleft) , then Top - k_{u\in U}(f(u)):=\{u_{(1)},\ldots,u_{(k)}\} . 2 Methodology Figure 2: Two-stage QAFD-RAG framework: the indexing stage builds a KG

Read the complete text