Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees
Authors: Zhuoping Zhou
Davoud Ataee Tarzanagh
Sima Didari
Wenjun Hu
Baruch Gutow
Oxana Verkholyak
Masoud Faraki
Heng Hao
Hankyu Moon
Seungjai Min
Venue: ICLR 2026 Poster (2026)
Keywords: Graph-Based RAG
Training-Free Retrieval
Multi-Hop Reasoning
Query-Aware Graph Traversal
Subgraph Recovery Guarantees
Primary area: learning on graphs and other geometries & topologies
TL;DR: QAFD-RAG is a training-free graph-based RAG that dynamically adapts traversal to query semantics via flow diffusion, yielding principled subgraph recovery guarantees and consistent gains on reasoning tasks.

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 \textit{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 \emph{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.

Published as a conference paper at ICLR 2026
QUERY-AWARE FLOW DIFFUSION FOR GRAPH-BASED RAG WITH RETRIEVAL GUARANTEES
Zhuoping Zhou", Davoud Ataee Tarzanagh", Sima Didari", Wenjun Hu, Baruch Gutow, Oxana Verkholyak, Masoud Faraki, Heng Hao, Hankyu Moon, Seungjai Min
Samsung SDS Research America, Mountain View, CA, USA
"Equal Contribution.
Project Page
ABSTRACT
Graph-based Retrieval-Augmentte Generation (RAG) systems leverage intercon- nected knowledge structures to capture complex relationships that flat retrieval struggles with, enabling multi-hop reasoning. Yet most existing graph-based meth- ods 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 's holistic meaning, retrieving neighborhoods or communities regard- less of intent. We propose Query-Aware Flow Diffusion RAG (AAFD-RAG), a training-free framework that dynamically adapts graph traversal to each query's 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 's embedding, guiding flow along semantically relevant paths while avoiding structurally connected but irrelevant regions. These query-specific reason- ing 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-an graph-based RAG methods.
Malus dee
Apple
Malus Mlevrcel
iPiine
Malus Sieversit Mallss
iPhige Steyll Jobs
Figii
Mation dirootica
Malus domestica
Tim Book
Orian Golden Beicove
Reego's Shore
Goldia SriinmiSroit
Inggo
App Store
Golden Dellcttois
Smittt
Store
Amezdon
Audy
Piigu
Begail
Whole Folila Market
Antlos
Sundlle
Amaratai basiin
Jeff Bauon
Iqelbax
Xbbo
Kighte
Ainazon Bliver
Redickesity
Amazon
Hindishrsity
Ecoo
ABN
GraphRAG
LightRAG
QAFD-RAG
Figure 1: Comparison of graph-based RAG methods on Wikipedia pages (Apple fruit, Ap- ple Inc., Amazon River, Amazon.com). Query: "Introduce Steve Jobs's 'ss products in Apple." GraphRAG (Edge et al., 2024b) retrieves entire communities, mixing relevant nodes (e.g., Mac. macOS) with irrelevant ones (e.g., Amazon River, Apple fruit). LightRAG (Guo et al., 2024) 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 's holistic meaning, suppressing irrelevant one-hop neighborhoods and preventing traversal into the Amazon River, Ama- zon.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).

---

Published as a conference paper at ICLR 2026
INTRODUCTION
Retrieval-Augmented Generation (RAG) enhances language models (LMs) by integrating external knowledge during generation (Fan et al., 2024; Gao al., 2023b). retriever first gathers relevant information for query, which is then combined with the input and passed to the generator (Karpukhin et al., 2020). This is especially useful for question answering (QA) (Xiong et al., 2020; Zhu et al., 2021), where added context improves accuracy in domains such as healthcare, law, finance, and education (Xu et al., 2024; Zhang et al., 2023). With recent advances in large LMs (LLMs), RAG has become increasingly important for trustworthy AI, helping mitigate hallucinations (Tonmoy et al., 2024), improve transparency (Kim & Lee, 2024), adaptability (Shi et al., 2024; Wang et al., 2023), privacy (Zeng al., 2024a;b), fairness (Shrestha et al., 2024), and reliability (Fang et al., 2024a).
Although conventional RAG is effective for unstructured document retrieval, real-world knowledge often has graph-structured forms-such 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- Graph-oriented RAG leverages such properties through techniques such as community detection and graph neural networks (Edge et al., 2024b; Wang et al., 2024), extending beyond similarity search to capture topological and semantic relationships (Fan et al., 2024; Gao et al., 2023b). 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 (Chen et al., 2025b; Wigh et al., 2022; Zhang et al., 2024c). For an overview, see the survey by Han et al. (2024).
However, existing graph-based RAG methods (Han et al., 2024) 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 (Edge et al., 2024b) applies uniform community detection regardless of query relevance, while Ligh- tRAG (Guo et al., 2024) extracts ago-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 + MMcc + 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 retriev- ing subgraphs that adapt to a query's '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 (Lovász, 1993; Chung, 1997; Fortunato, 2010; Spielman & Teng, 2013b; Fountoulakis et al., 2023b). 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 's holistic meaning. Specifically, we propose Query-Aware Flow Diffusion RAG (QAFD-RAG), 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-basse edge weighting. QAFD-RAS AAG adapts flow probabilities online, guiding traversal toward semantically relevant regions with complexity scaling with the retrieved subgraph size rather than the full graph (Figures and 2).
We provide the first rigorous analysis of query- aware traversal with provable guarantees. Our results (Theorem 3) show exponential convergence to unique query- query-dependent stationary distribution, and recovery guarantees (Theorem 7) ensuring relevant subgraphs are retrieved with high probability under mild signal-to-noise conditions.
C2. Optimization and Statistical Guarantees:
C3. Experimental Validation: We evaluate DAFD-RAG on general QA (Tables I and 5), multi-hop
QA (Table 3), long-document summarization (Table 2), and text-to-SQI. (Table 4). Across these
2

---

Published as a conference paper at ICLR 2026
Chapter
Question: What nole dics feniriia play is the book's acalysis of Elaine Benss?
Bless, Fovisur
of the Alye7, by
evaltanes
Prosppiay
anorg. indepentere
the
athura rnprosmttttonn
Traleaaction "Churacte excloriis"
LandLaod Keywards "Tl finret sulyead porcowsory
-Raleee
Sisp
You are lejpeid mvisiest sopaedding to grosiion boour in
Indexing siiiing Stuge
Query vvrry Stage
Clanks
Diffuciin
Cencone respe of gegtt longft
infornet sprispeet wibbos appry oprepriato for the lenghhied fnrmat and ixcepprating rolovant pareera Do craes saylling tsleratioo whr the sappetina evidacee for provated.
repooad
inckall
Stop
Extrantien
Fritessed Rebiiceshipe
Targe regunee lingt and Surmaation ereg 1ypec
Kasnleigy
Stop Proppiia
Data tablee
Veesen: vchane: infermation
Eemiiiii Phitrspto: valaier acbrmntion
Dhcadskki and and
Figure 2: Two-stage QAFD-RAG framework: the indexing stage builds a KG from documents, and the query stage applies QAFD to extract and prompt subgraphs for response generation.
benchmarks, QAFD-RAG consistently outperforms state-of-the graph based RAG baselines and improves over text-to-SQL baselines.
Notation. Let Rd be d-dimensional Euclidean space, and let R and R denote the nonnegative and strictly positive orthants. Vectors and matrices are in boldface (e-g.. a, A) with entries a, and aij. For matrix A, A; and A.j denote its ith row and jth column, and A > 0 and A > 0 mean
positive definite and positive semidefinite. For vectors, ||a/]1 := Σ, |a;| and ||a|| := E la,l 1/2
1/2 For n E N, define [m] := [1....,n} We use standard asymptotic notations O, f2. O, and w (as n + oo). We write < for fixed deterministic tic-breaking order on any finite set. For a finite set U and scores f U - R. Top-kueu(f(e) (f(u)) returns the elements of U with largest scores, breaking ties by 4; equivalently, if u()..... M((UD) are sorted in decreasing order of (f(), 4), then Top-kueu (f(u) = {up))..., J.
For matrices, || == (Eis laigl))
n).
2 METHODOLOGY
2.1 FRAMEWORK OVERVIEW
QAFD-RAG a training-free, graph-based reasoning framework for RAG tasks. The framework operates in two phases: Indexing Stage (IS), which builds a knowledge graph (KG) from raw documents (Chen et al., 2025a; Guo et al., 2024), and a Query Stage (QS), which introduces our key contribution- conrrbutionn-query-aaaeaee
flow diffusion. This mechanism integrates query semantics into graph traversal, enabling adaptive retrieval with statistical guarantees. Unlike SOTA RAG methods such as GraphRAG (Edge et al., 2024b), which applies static community detection, or LightRAG (Guo et al., 2024), which extracts ego-nets (Figure 1), QAFD-RAG dynamically reweights edges and diffuses flow according query alignment, suppressing irrelevant clusters and highlighting reasoning paths.
In IS, IS-Step 1: Document Chunking splits documents into context-preserving chunks; 15-Step 2: Entity and Relationship Extraction uses LLM prompting to build structured KG. In QS, QS-Step 1: Keyword Extraction pulls conceptual and surface terms (c.g.. Feminism. Elaine Benes) for broad coverage (Figure 2, Step 1). Next, QS-Step 2: Seed Node Selection and QAFD scores nodes by similarity to query keywords as detailed in Algorithm 1. For example, in Figure 1, Steve Jobs (0.95), Apple (0.92), and iPhone (0.88) are selected, while irrelevant ones (e.g., Amazon, 0.15) are excluded. Top-scoring nodes serve seeds where mass is injected and propagated via flow diffusion (Figure 2, Step 2). Edges are dynamically reweighted to blend structure and semantics through the query-aware edge weighting mechanism described in Section 2.2. suppressing irrelevant expansions (Apple + Amazon River/fruit) and reinforcing meaningful ones. We formulate this diffusion process as a constrained optimization problem, solved efficiently via push-relabel algorithm (Algorithm 2).
3

---

Published as a conference paper at ICLR 2026
Recovery guarantees and algorithm complexity are provided in Section 3. Finally, QS-Step 3: Response Generation summarizes retrieved communities (e.g. Elaine Benes, Feminism) and prompts downstream LLM, yielding grounded, consistent answers along reasoning paths.
2.2 QUERY- FLOW DIFFUSION
We cast subgraph retrieval as a QAFD problem. Given a natural language query E Q and a knowledge graph 9 (V.E, R), with V entities, & edges, and R relations, the task is to retrieve subgraph G, C 9 capturing reasoning paths relevant for downstream language model processing. We first recall flow diffusion from graph diffusion theory (Lovász, 1993; Chung, 1997; Spielman & Teng, 2013b; Fountoulakis et al., 2023b).
Definition 1 (Flow Diffusion). Flow diffusion spreads an initial amount of "mass" or "information" from seed nodes through a graph along its edges. At each step, mass is divided among neighbors by edge weights, so strongly connected nodes receive more and weakly connected ones less.
Intuitively, flow diffusion resembles water or dye moving through pipes: most flow fol- lows stronger pipes neigh- edges), little through weaker ones. While well studied in clustering and community detection, it has not been explored in the presence of queries. We re- formulate diffusion for graph-based RAG, link- ing traversal to query semantics. The first step is seed node selection, as seeds are usually as- sumed priori in diffusion methods (Spielman
Algorithm Seed Node Selection
Input: Query q, graph G = EV,E, R) with node
embeddings } vey, embedding function h(-), similarity Hsim (:, ) number of seeds N
Output: Seed entities Sy S V with Sy =
1: Extract keywords K., = {WI, (WI...... V/cccl
from q using an LLM
2: Compute cy.1 h(w,) for all i
[Kgg
3: for all v E V do
& Teng. 2013b; Wang et al.. 2017). Seed selec- tion identifies query-relevant entities starting points for flow diffusion. We adopt a semantic similarity-based approach and treat seed util- ity as approximately additive under an indepen- dence assumption; see Algorithm 1. Let Q be the query space and W the vocabulary space. Define g 2 + 2 mapping a query q E @ to keywords K., =- [wi,.... Wix, via LLM prompt- ing (Appendices A4 and A5). Let Ky := [kg uU V} be node identifiers. Let h WUV + Rd denote an embedding function that maps query keywords and graph nodes to Rd.
max 4: score(u,g) (E(I....IK,II)
Hsim (eg ev))
5: end for
6: Sy + T-op-Nwvv NNE (scorecr, q))
7: return Sy
Eg = (h(w:) |Ka,| = (cg.s E Ikgl and Ey = (h())) = (e,, E FEEV.
We then define a similarity function Hsm IRd x Rd + R for semantic relatedness, with common choices including cosine similarity e-c' |||||||e|||, [|. dot product e'c,, RBF kernel exp(->/le-e'11?) The relevance score of a node v for query g is the maximum similarity across keywords via Step 4. We then select the N highest-scoring entities via Step 6, breaking ties arbitrarily. For small graphs, keywords and seeds can often be extracted in one LLM prompt (Appendix A5). For large graphs (e.g.. Table 11), we apply Algorithm which runs in O(V) [Kgl + [V] log N)..
Dynamic Query-Aware Edge Weights. Given seeds Sy and query q E Q, we perform flow diffusion to extract reasoning subgraphs. Traditional diffusion uses static edge weights that ignore query context, leading to uniform exploration. Our key insight is to make edges query-aware gates that modulate flow strength using both structural connectivity and query alignment, enabling recovery guarantees. For each y Q edge (u, v) E E, and a, b, 2 0, the query-aware edge weights are w(g, u, v) == c Ham (h(w), h(u)) o (a + b. (H (h(u), h(())) a H (h(w), h(q)))), (1)
where h(-) is the embedding function, Hsim similarity measure, a binary operation (addition or multiplication), and a, b, c 2 0 hyperparameters.
We explore three variants that balance structural and semantic signals differently:
WMaan (g. u, v) 3 (H (k(u), M(r)) H (h(u), h(g)) Ham (())))()))).
(2a)
Urrotuel (g. u, v) = (h(u), h(e)) (h(u), h(g)) H (h(v), h(g).. Wllybrid (g. u, v) H (h(u), h(t) (a + (H (h(u), h(g)) + Ham (M()),
(2b)
(2c)
4

---

Published as a conference paper at ICLR 2026
Here, Him (b((), h(v)) captures structural (ha), h(q)) measures query relevance to nodes u and v. The multiplicative interaction in Product and Hybrid amplifies edges between query-relevant nodes while exponentially suppressing edges to irrelevant regions, transforming diffusion into a semantic filter. Weights are computed online: when query arrives, we first compute its embedding and then update only the edge weights (gg v) encountered during traversal. In experiments, WHybrid (g, u, v) yields slightly better results.
similarity, while Ham(h(u). h(g))
QAFD's Primal-Dual Formulation. Given approaches for seed nodes and dynamic weight compu- tations (g, u, v), we formulate flow diffusion (Definition 1) as constrained optimization problem that minimizes total flow cost while enforcing mass conservation at each node. Let f E glel denote edge flows, (4) E [elE)x (e] the diagonal matrix of query-aware edge weights, and B E RRV x|8] the incidence matrix of g. The optimization is
min 5 W(g)f subj. to A + (W FERIE
A E Q
(3)
Here, A E IR encodes source mass injection and T E RM represents sink capacities. We note that in previous formulations (Wang et al., 2017: Fountoulakis et al., 2020b; 2023b), W(g) query- independent and, in most cases, is restricted to be the identity matrix. Following Definition 1, the sink capacity vector T determines how much mass each node can hold before diffusing to neighbors. A common choice is begree-based capacity where T. degree(v). which allows high-degree nodes to accumulate more mass proportional to their connectivity, though uniform capacity T, = 3 for some constant / provides an alternative that treats all nodes equally regardless of their structural prominence. The source vector A controls the initial mass distribution across nodes, with a common choice A, Evev Tu for source nodes Sy and A. otherwise, where >> 0 controls source strength.
The corresponding Lagrangian of (3) with multiplier vector R M
is
q) = f T w()) T (A (W) T), Vq Q
Taking af/0f = 0 gives the primal-dum relation f = -B Tx. Substituting this into (4) and setting L(q) = BW( yields the dual problem
min F(x; = 1 L(g)x (T - A), xER!
E
(5)
is often more convenient to use (5), which incorporates the T and A constraints into the objective. The solution provides node impor- tance scores E R indicating each en- tity's query relevance. Intuitively, repre- sents edge flow strength- thicker edges in Fig- ure 1(right)-whil x denotes node mass or importance, shown by color in Figure (righht): greener nodes are most relevant, yellow least, with intermediate shades indicating moderate importance.
Algorithm 2 Query-Aware Flow Diffusion
Input: Graph G = (V,E) with node embeddings
[c.)vev, seed node E V (via Algorithm 1), query q and embedding C, h(q), C. 0.
Output: Node importance scores x E RIV
1: Initialize m 4- 0, x + 0
2: Set sink capacities T, = dog(u) for all E
3: Set source mass m, a > egy To
4: while E, max (0, m,
m,, - TT)) > e do
5: Select E {u m. > Tu} u.a.r
6: excess + m. Tv. w. + 0
Algorithm 2 performs coordinate-win optimiza- tion updates on the dual objective (5) for a query and seed node. We set A. a Eney To for E Sy and A. = 0 otherwise. At each step, node e with excess mass (m, > Tτ) is chosen uniformly at random and is in- creased to reduce the objective. The mass vector m tracks the gradient of Fxx), initialized as m A at x = O with ( = T A. More generally, m A- L(g)x, linking to F q) = T m. The condition m, T, is equivalent to 0//ar, < 0, ensuring updates
7:
for E neighbors(u) do Compute w U. u) using Eq. (1)
8:
9:
Wy <- W. + ((g v.
10:
end for
11:
Tu f- x. + excess/ww
my + To
12:
for neighbors(1) do
13:
m, + my + excess w(g, U, w)/we
14:
end for
15: end while
return
5

---

Published as a conference paper at ICLR 2026
decrease the objective. Push operations enforce complementary slackness: active Fa 0 correspond to nodes at capacity (m, = To), satisfying dual optimality.
Afte selecting seedource nodes Sy, Algo- rithm 2 preserves the locality of flow diffusion while enabling online graph traversal. This property is crucial for large-scale KGs with millions of nodes. Unlike SOTA RAGs (Edge al., 2024a), which requires full preprocessing, QAFD-RAG dynamically discovers relevant entities and relationships during traversal. When mass flows from node v to its neighbors, the algorithm: (i) computes query- aware edge weights (1, 0, u) on-demand via (I); (ii) retrieves embeddings eu and properties only when mass reaches u; and (iii determines sink capacities T, dynamically. This lazy evaluation makes complexity scale with the explored subgraph rather than the full graph.
Locality Preservation and On-Demand Computation.
Extension Multi-Subquery Formulation. For complex queries requiring multi-hop reasoning. single embedding via (1) may be insufficient. We address this by decomposing such queries into multiple subqueries, as they often involve distinct reasoning aspects solvable independently and then combined. For example, the Spider 2.0 (Lei et al., 2024) query "Please help me, find the film category with the highest total rental hours in cities whose names either start with 'A' or contain a hyphen." decomposes into filtering cities, linking to addresses and customers, finding rentals, mapping rentals to films, and identifying film categories with the highest totals. This decomposition enables more effective embeddings during traversal by handling reasoning aspects independently before aggregation. Given a complex query g. we decompose it into K subqueries QK = (7), 92.....9x' using LLM-based decomposition (see Prompt 5), where each 9 captures specific reasoning aspect. We then apply flow diffusion to each subquery independently: for each qk. we compute
wi qhe u. v) c Hsim (h(u), h(v)) Ja + b- (Ham h(qx)) Hsim (h(v), h(q))))
(6)
We then solve the flow optimization problem for each subquery. From (5), obtain
min F(x(1) ((x()):))) qx) 1 (x ( T (qx xx)) (2) + (xx*))T (T)))
(K)), Aga. QK (7)
x( MI
Here, L ( (gx) BW (gx) BB is the weighted Laplacian for qk, with W (qx) denoting the diagonal matrix of edge weights w (gg, u, v). The solution yields uubquery-speciff importance scores
x*) with support support = fo= E V xe (k) > c) where >> 0 filters out negligible values. The final retrieved subgraph combines all subqueries, G, U Ga. where each Gr is built from support and its edges. See Figure for an illustrative example.
OPTIMIZATION AND STATISTICAL GUARANTEES
We now provide theoretical guarantees for Algorithm 2, focusing on convergence and locality.
Lemma Let x()) be the optimal solution of (7). The support of each iterate generated by
Algorithm 2 is contained within supp(x(()*). Moreover, (*))) - || (k)
Let d be the maximum degree of node in supp(x"). Since each iteration only touches node u E supp(x") and its neighbors, Lemma 2 implies that the number of nodes ever explored is at most | Thus, if || is small and d does not scale linearly with n, Algorithm 2 remains local, with subgraph size controlled by |||||
Theorem 3. For subquery qu. assume (()))(((())) < 12% where x()) solves (7). After (8) 1). )). where 7(k) = maxuesupp(x(()) Evou w(as, v) and ()( < yeEy log
((k) = 0 (k)
min (v. (ew.)))ss(p(((((( w(gs: u. v). we obtain R. (x((()))) :m)]] F(x(()) SE
Corollary 4. Algorithm 2 converges to (k)+ in O(d ||A||] log(1/e)) iterations, where d the maximum degree in the KG, || 1 is the total injected mass, and is the desired accuracy.
Theorem 3 shows that convergence depends on (8) (x((), where (k)) is the maximum query- weighted degree and (*) the minimum edge weight in the optimal support. Since w0 w(gs, ge. u, u) is derendeennn,nt, convergence adapts to each subquery's 's semantics unlike traditional diffusion with
static weights. The runtime to reach e-accurate solution is O(d ||] z log !). If d, ||||| and

---

Published as a conference paper at ICLR 2026
a/B are sublinear in n, Algorithm 2 achieves sublinear time, scaling to large KGs. This improves over exhaustive subgraph and graph-basee RAG methods with O(D))) complexity, showing QAFD-RAG combines efficiency with semantic adaptability.
Statistical Guarantees under a Random Graph Model. Under appropriate signal-to-noise to-noisc condi- tions, we can provide guarantees about the quality of recovered reasoning paths.
Our analysis relies on a probabilistic framework where the embeddings Cu, Ce, and Cq. for relevant nodes and queries follow structured random model. While this assumption may seem restrictive, these embeddings can capture diverse node and query characteristics beyond simple text. The mathematical foundations for analyzing node-attributed graphs have been extensively developed in prior work on graph clustering (Reid & Yuval, 2009; Allen-Zhu et al., 2013; Andersen et al., 2016; Shi al., 2017; Wang et al., 2017: Fountoulakis al., 2020a: Liu & Gleich, 2020) and diffusion processes (Fountoulakis et al., 2020b; Yang & Fountoulakis, 2023; Fountoulaki et al., 2021). Our novelty lies in incorporating query semanties into this framework, allowing us to analyze how query-dependen edge weights shape traversal dynamics and to provide the subgraph recovery guarantees.
Definition 5. Given schema graph with node set V. for each query qk, define RR S V as the set of relevant nodes (tables/colunns required by the query) with ri = (Ry). The random graph generation is governed by the following edge probubilities: for each pair of nodes (u, v), edges are independently drawn with probability pi uf U RR, with probability p2 if exactly one node is in Rk. and otherwise follow the original schema structure. For each node V, we have e, p + Zus where μ E R is a deterministic vector, and Zu E I$ is random noise with independent mean-zero sub- Sab-Gaussian coordinates Rud, each having variance proxy de.
t² for all t t2 0.
Prob([zuel
20
For each qk. let Osp, = .g.. + Kugu using the same noise model. For nodes the relevant set Rks we set fu = =u = py. for all u, U RA- Finally, for query qe, we define w(gk. u, v) = Produce (Is. u, v). where Ha, b) = exp(-7lla bbll) is an RBF- dBF-kernel similarity function. We also allow distinct bandwidths 7/t for each factor in Producc-
Note that this formulation is chosen for simplicity of analysis. In practice, other measures-such as cosine similarity-en can be used depending on the application. Throughout, we define
= max df and p := min
l| -t,lll
(8)
1sted
RE R
Assumption A (Knowledge Graph Structure and Signal-to-Noisey The knowledge graph satisfies the following: (1) Entities relevant to query q: form a connected subgraph R4; (2) The embedding space preserves semantic similarity with signal-to-noise ratio ju/ā w(Vdlol (V]); (3) Variance concentrates as Ed= 022 Ollog [V]; and (4) Irrelevant entities have embeddings well- separated from query embeddings.
Lemma 6 (Query-Award Edge Weight Separation). Under Assumption A, if similarity function parameters satisfy nō² = o(log [V]) for E (1, then with probability at least 1 1- --(()-22) (i) For all u, u R2, w w(g, u, r) 2 (1 o(1)); (ii) For all R2, v V R2, T(gk, u. v) S exp(-w(log [V)))
Lemma 6 shows that under the signal-to-noie conditions in Assumption A, query-aware edge weights w(g,, u. v) separate relevant nodes R₂ from irrelevant ones V > Rg. With similarity parameters 7 scaled inversely with log [V) the lemma guarantees with high probability that (i) edges within R remain essentially unchanged, preserving reasoning paths, while (ii) edges between relevant and irrelevant nodes become exponentially small, blocking diffusion into contextually irrelevant regions.
Theorem 7. Under the conditions of Lemma 6, assume that either (i) the induced subgraph on Ra (4+c) log for some ò E (0, 1) and > O. If the source mass is set as is connected, or (ii) P1 2 -1)
A (k) = =1+ EVER, for any 8 > O, then with high probability we have
R4 C (k)
and
Σ
Tu Σ Tu-
(9)
"Exupp(x()))
uER
7

---

Published as a conference paper at ICLR 2026
Table I: Comparison of QAFD-RAG and baselines on UltraDomain across five GPT-4o-scored dimensions (0-100). Rows are grouped by dataset and columns by metric; values are mean (# std) over evaluations. Best per dataset/metric is bolded. Continued in Appendix 12.
Dataset
Method
Comprehensive.
Diversity
Logicality
Relevance
Coherence
Agriculture
GraphRAG
(14.44))
(11.733
91.50 84)
94.01 (1.6.22)
90.08 (13,223
LightRAG
83.65 (+5.97)
(17.34))
88.85 (4:3.76)
93.55 (4:4116
88.67 (#22577)
RAPTOR
83.32 (+8.67)
76.65
39.54
44356(#3441
89.47 (#3.01))
HippoRAG
82.51 (+5.14)
(+-262))
(4.326+)))
94.09 (+2.48)
88.79 (+2.733)
QAFD-RAG
(233.6))
84.95 (1:4226)
92.10 (1:2553
95.67 (4:3228)
92.00 (1:1.62)
Biology
GraphRAG
15.76(=10.80)
81.05 10
88.94 (=+1.70))
(+:1.55))
88.57 (.11.10)
LightRAG
(3.92
78.28 (16.446)
38.4.
93.31 (1))422)
88.09 (1:2.
RAPTOR
83.57 (=6.200)
(7.10
88.33 (+:5662)
93.62
88.67 (#:4.21)
HippoRAG
83.07 (#:411)
76.91222.25
88.07 (#3.69)
93.62 (+:3.53)
88.52 (+2.
QAFD-RAG
(+3.92))
(5.13(+
91.19 (++4200
95.05 (+-4.71)
91.33 (+2.599
Cooking
GraphRAG
(67.00))
(28.072)
90.79 (#2.688
(*2241))
90.63 (#1.)5)
LightRAG
(=7.16)
74.97 (+9.46)
87.49 (+5.82)
92.27 (+-5888)
87.98 (+4.09)
RAPTOR
(+..99+)
(5.309+
(+..222
(+5.88)
88.83 (+3.87)
HippoRAG
(24.55)
74.13
48.40
(#2.66)
88.57 (#2.661)
QAFD-RAG
89.25 (+3882)
83.42 (+5.25)
91.35 (+2.733)
95.45 (+22883)
91.58 (#22.04)
History
GraphRAG
84.18(110.30)
78.88 (19.97)
(8.16(1
(113..5))
88.40 (00.771
LightRAG
(26.004)
(+7.51)
86.98 (#5.75)
(2618
87.18 (#:4.24)
RAPTOR
82.08 (+7.43)
75.59
87.67 (+:4663
92.94 (++4.33)
88.13 (+:3.58)
HippoRAG
(+.45(+)
(4-.22)))2)
86.37 (..366)
(+8.222)
86.97 (++4777)
QAFD-RAG
(#3.66)
(=4.40)
90.04 (+:3933
93.77 (#:6.25)
90.55 (+:2.37)
Logal
GraphRAG
(8.74 (49.62)))7
88.67 (++8.58)
91.01 (0.90)0)
88.44 (+5.77)
LighRAG
67.63 (1..22)
86.06 86.06 (+:7.47)
90.77 10
86.12 10)
RAPTOR
(#9.777)
64.97 (+13.11)
88.34 (+6.55)
(1:9.18))
87.70 (#6. 16)
HippoRAG
82.23 (-8.5)
38.56
(3-9044)
87.95 (+6.39)
QAFD-RAG
86.19 (+..86)
77.14
(1-5.66))
(3.30
89.99 (+3.35)
Theorem 7 shows that query-aware flow diffusion reliably recovers the query-relevant subgraph RR, with controlled precision. It provides two guarantees: Complete recovery (R, S (x))(x(())) ensures all semantically relevant nodes to query 9k receive positive flow and are included, so no essential information is lost. Limited leakage ② (spppppp(())) ),) T, S S LnER, Tw)) bounds flow escaping into irrelevant regions. The trade-off parameter controls this balance: smaller 3 enforces tighter focus, while larger 3 allows peripheral context at some cost to precision. Together, these results show that DAFD-RAG's query- edge weighting acts semantic filter, concentrating flow on relevant reasoning paths while minimizing diffusion to unrelated regions.
4 EXPERIMENTAL EVALUATION
We evaluate QAFD-RAG against strong baselines on knowledge graph question-answert and text- to-SQL benchmarks, with particular emphasis query-aware retrieval performance and schema linking capabilities. Code available at anonymous repository.
4.1 KNOWLEDGGE GRAPH QUESTION ANSWERING RESULTS
4.1.1 BASELINES FOR KG-QA
We compare QAFD-RAG
with four recent graph-oriented RAG systems under an identical setup (corpora, prompts, evaluation): GraphRAG (Edge et al., 2024b), which clusters retrieved documents via community detection and builds hierarchical contexts: LightRAG (Guo al., 2024), which performs dual-level retrieval in the indexing graph; HippoRAG (Jimenez Gutierrez et al., 2024), which constructs passage-leve KG and applies Personalized PageRank for single-step multi- hop retrieval; and RA RAPTOR (Sarthi et al., 2024), which forms a hierarchical retrieval tree through recursive clustering and abstractive summarization, enabling multi-level evidence selection.
8

---

Published as a conference paper at ICLR 2026
Table 2: Performance comparison QAFD-RAG against baseline methods on SQuALITY long-
document summarization.
Method
BLEU-1
BLEU-2
ROUGE-IFT
ROUGE-2FT
METEOR
GraphRAG
33.91
16.12
26.38
4.08
24.38
HippoRAG
33.22
16.74
27.29
3.92
23.41
RAPTOR
32.10
16.58
25.13
3.49
22.87
LightRAG
34.17
17.41
28.59
4.31
23.27
QAFD-RAG
35.44
18.63
28.43
4.79
25.59
4.1.2 LLM CONHIGURATION AND HYPERPARAMETERS
Unless otherwise noted, we use -o-ini for all entity/relation extraction, hierarchical key- wording, and cluster summarization, text text-embeddinme embedding small (1536d) for all embeddings, and fixed configuration of 40 seed nodes, diffusion mass 50, and hybrid query-aware edge weights (Eq. (2c)) with a = and b Additional implementation details are provided in Appendix A4.
4.1.3 DATASETS AND EVALUATION PROTOCOL
We evaluate QAFD-RAC across three major settings. General QA uses ten UltraDomain subsets (Qian et al., 2024) spanning long-context reasoning and implicit inference (Agriculture, Biology, Cooking, History, Legal, Mathematics, Mix, Music, Philosophy, Physics), Answers are scored along five axes Sess--Commreeesseeeeete
Diversity, Logicality, Relevance, Coherence- GPT-4o 0 0-100 scale. with five independent evaluations response (Appendix A4). For Long-Document Summarization, we use SQuALITY (Wang al., 2022), where answers are question-focused abstractive summaries benchmarked against multiple human-written references; we report BLEU- BLEU-2, ROUGE-I-FL, ROUGE-2-FI, and METEOR (Appendix A2.1.5). Multi-Hop QA is evaluated HotpotQA (Yang et al., 2018), 2WikiMultiHopQA (Ho et al., 2020), and MuSiQue (Trivedi et al., 2022) which require combining evidence across documents and explicit chains; we report Exact Match (EM) and FI using official evaluation scripts (Appendix A4.1).
4.1.4 EXPECTED RESULTS AND ANALYSIS
On the ten ULTRADOMAIN subsets (Tables 1, 5), QAFD-RAG achieves the strongest overall averages across five axes, with steady gains in Comprehensiveness, Logicality, and Coherence. Baselines show complementary strengthsRRAPON may excel on RelevancelCoherence when hierarchi- cal abstraction fits the domain, HippoRAG performs well on Relevance with local evidence, and AigghRAGG/ihhhteeee can boost Diversity by expanding neighborhoods, often at the cost of Logi- cality. Overall, focusing retrieval on a query-aligned subgraph improves factual alignment without hurting fluency, whereas baselines trade off precision and recall in domain-depended ways.
On the SQuALITY benchmark (Table 2), QAFD-RAG achieves the highest performance on the ma- jority of automated metrics metrics-including BLEU-1, BLEU-2, ROUGE-2 2 F1, and METEOR -neeicatidiinnggg more faithful and coherent long-form summaries compared to GraphRAG, HippoRAG. RAPTOR, and LightRAG. While LightRAG now attains the highest ROUGE- Fl score, QAFD-RAG'S query- aligned retrieval yields stronger overall metric profile, offering a more stable balance between precision and coverage across diverse narrative questions. On HotporQA, MuSiQue, and 2WikiMul- tHooQQA, QAFD-RAG achieves the highest Fl and EM scores on HotpotQA and MuSiQue, and remains competitive with HippoRAG 2WikiMultiHoQQA (Table 3). These improvements in Fl and EM highlight that qwery-aware diffusion more reliably recovers gold evidence under strict match- ing. While HippoRAG also demonstrates strong multi-hop hop reasoning through personalized PageRank, QAFD-RAG's query-aligned pruning produces tighter evidence chains and a stable precision-recall balance, enabling superior competitive performance multi-hop reasoning tasks.
4.2 TEXT-TO-SON SQLL RESULTS
We compare against methods from different paradigms. CHASE-SQL (Pourreza et al., 2024) uses multi-path L.M reasoning (divide-and-conqueer, execution-plan CoT, instance-aware few-shot) with

---

Published as a conference paper at ICLR 2026
Table 3: Performance on Multi-Hop QA (FI, EM).
Method
HotpotQA
2WikiMultthopQA
MuSiQue
F1
EM
F1
EM
F1
E.
GraphRAG
33.40
14.00
15.20
7.00
39.40
17.60
LightRAG
8.80
0.00
8.20
1.00
1.40
0.10
RAPTOR
52.30
25.00
38.80
12.00
28.10
10.50
HippoRAG
58.67
45.27
70.33
61.16
38.33
27.55
QAFD-RAG
73.42
58.10
69.41
59.50
47.99
33.50
pairwise-selection agent for SQL generation and ranking. DIN-SQL (Pourreza & Rafiei, 2024) adopts a decomposition framework with template matching. Spider-Agent (Lei et al., 2024) applies ReAct-style schema exploration and iterative SQL generation. CodeS (I.i et al., 2024b) emphasizes code generation via prompt engineering. DAIL-SQL (Gao et al., 2023a) improves Text-to-SQL. accuracy by selecting and arranging few-shot code examples using masked question-query similarity, All methods are using GPT-4o LLM calls.
We evaluate the Spider 2.0 (Lei et al., 2024), a comprehensive dataset with diverse schema architectures representative of real enterprise environments. The benchmark includes complex SQL queries requiring multi-table reasoning and advanced analyt- ical operations. Our analysis focuses on the Spider 2.0 Local Test Set, which contains 135 SQLite and Snowflake instances fea- turing long join chains and intricate query structures. Table 4 reports execution accu- racy both test sets. Here, SQL-Agent is variant of the Spider-Agent (Lei et al., 2024)
Table 4: SQL execution accuracy on 135 SQLite and Snowflake test sets.
Method
SQLite (%)
Snowflake (%)
CHASE-SQL.
11.85
5.92
DIN-SQL
2.74
0.18
DAIL-SQL
0.00
0.00
CodeS
0.00
0.00
Spider-Agent
21.50
16.30
QAFD-RAG
26.70
23.70
+SQL-Agent
SQL generator. Unlike Spider-Agent, which relies on a ReAct-style agent for exploration and rea- soning, our method converts each database into a knowledge graph and applies QAFD to identify relevant tables and columns. SQL-Agent then uses tailored prompts and QAFD-RAG's subgraphs for SQL generation. An example prompt is shown in Prompt 6.
5 CONCLUSION, LIMITATIONS, AND FUTURE WORK
We presented QAFD-RAG, a training-free framework with query-awart edge reweighting for adaptive graph traversal. Our contributions include: (1) the first principled flow diffusion for graph-based RAG, (2) theoretical guarantees for subgraph recovery, and (3) consistent improvements across benchmarks while reducing LLM calls. QAFD-RAG relies on pre-trained embeddings, which may underperform in domain-specine settings. Besides, the embedding based flow diffusion may struggle with explicit logical negation because embeddings capture semantic relatedness rather than logical operators. While QAFD-RAG partially mitigates this through LLM--based keyword extraction (Prompt 2) and response filtering (Prompt 3), this remains an important challenge.
QAFD-RAG's modularity enables drop-in replacement of retrieval components in existing systems: can replace static Leiden clustering in GraphRAG, enhance Personalized PageRank in HG with query-aware edge weighting, and extend LightR single-hop retrieval to multi-hop flow diffusion all without retraining while providing theoretical guarantees. Future work includes learning edge weights from Future work should also explore contrastive embeddings or hybrid symbolic neural approaches that encode logical distinctions during graph traversal.
pairs and extending to temporal/multi-mon modal graphs.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We would like to thank Samsung SDS Research America for supporting this work. We are also grateful the area chair and the anonymous reviewers for their constructive feedback and valuable suggestions, which helped improve the quality of this paper.
REFERENCES
E. Abbe, J. Fan, and K. Wang. An lp theory of pea and spectral clustering. The Annals of Statisticss 50(4):2359-2338) 2022.
Z. Allen-Zhu, L. Silvio, and S. M. Vahab. A local algorithm for finding well-connected clusters. In International Conference on Machine Learning (ICML), 2013.
Uri Alon, Frank Xu, Jumxian He, Sudipta Sengupta, Dan Roth, and Graham Neubig. Neuro-symbole language modeling with automaton-augment augmented retrieval. In International Conference on Machine Learning, pp. 468-485. PMLR, 2022.
R. Andersen, Chung, and K. Lang. Local graph partitioning using pagerank vectors. IEEE Symposium Foundations of Computer Science (FOCS), 2006.
R. Andersen, S. O. Gharan, Y. Peres, and L. Trevisan. Almost optimal local graph clustering using evolving sets. Journal of the ACM, 63(2), 2016.
E. Arias-Castro, E. J. Candès, H. Helgason, and O. Zeitouni. Searching for a trail of evidence in a maze. The Annals of Statistics, (666):17261177, 2008.
E. Arias-Castro, E. J. Candès, and A. Durand. Detection of an anomalous cluster in network. The Annals of Statistics, pp. 778-304,22 2011.
A. Baranwal, K. Fountoulakis, and A. Jagannath. Graph convolution for semi-supervised classi- fication: Improved linear separability and out-of-distributioo generalization. In International Conference on Machine Learning (ICML), 2021.
A. Baranwal, K. Fountoulakis, and A. Jagamnath. Effects of graph convolutions multi-layer networks. In International Conference Learning Representations (ICLR), 2023a.
A. Baranwal, A. Jagannath, and K. Fountoulakis. Optimality of message- passssggganin architectures for sparse graphs, 2023b.
Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. Large-scale simple question answering with memory networks. arXiv preprint arXiv: 01..5006.007,,000 2015.
G. Braun, H. Tyagi, and C. Biernacki. An iterative clustering algorithm for the contextual stochastic block model with optimality guarantees. In International Conference on Machine Learning (ICML), 2022.
Boyu Chen, Zirui Guo, Zidan Yang. Yuluo Chen, Junze Chen, Zhenghao Liu, Chuan Shi, and Cheng Yang. Pathrag: Pruning graph-base based retrieval augmented generation with relational paths. arXiv preprint arXiv:2502. 14902, 2025a.
Xiaohui Chen, Yinkai Wang, Jiaxing He, Yuanqi Du, Soha Hassoun, Xiaolin Xu, and Li-Ping Liu. Graph generative pre-trained transformer. arXiv preprint arXiv:2501.0107; 20255.
Xin Cheng, Luo, Xiuying Chen, Lemao Liu, Dongyan Zhao, and Rui Yan. Lift yourself up: Retrieval-augmmented text generation with self-memory. Advances in Neural Information Processing Systems, 36, 2024.
U. Chitra, K. Ding. J. C. H. Lee, and B. J. Raphael. Quantifying and reducing bias in maximum likelihood estimation of structured anomalies. In International Conference Machine Learning (ICML), 2021.
Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
11

---

Published as a conference paper at ICLR 2026
Mohammad Dehghan, Mohammad Ali Alomrani, Sunyam Bagga, David Alfonso-Hermllo Khalil Bibi, Abbas Ghaddar, Yingxue Zhang, Xiaoguang Li, Jianye Hao, Qun Liu, et al. Ewek-qa: Enhanced web and efficient knowledge graph retrieval for citation-based question answering systems. arXiv preprint arXiv:2406. 10393, 2024.
Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems (NeurlPS), 2018.
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: A graph rag approach to query-focused summarization. arXiv preprint arXiv:2404. 16130, 2024a.
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: graph rag approach to query-focused summarization. arXiv preprint Xxxv:2404.16130, 2024b.
Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. A survey on rag meeting Ilms: Towards eerrenel-augmenned large language models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 6491-6501, 2024.
Feiteng Fang, Yuelin Bai, Shiwen Ni, Min Yang, Xiaojun Chen, and Ruifeng Xu. Enhancing noise robustness of vetrieval-augmenter language models with adaptive adversarial training. arXiv preprint arXiv:2405. 20978, 2024a.
Jinyuan Fang, Zaiqiao Meng, and Craig Macdonald. Reano: Optimising retrieval- -ugmeente reader models through knowledge graph generation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 2094 2112, 2024b.
Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):55-174 2010. doi: w..1016/j.physrep.p22 20t...0000...0.........1.1 11.002.
K. Fountoulakis, F. Goosta-Khorasaan J. Shun, X. Cheng, and M. W. Mahoney, Variational perspective on local graph clustering. Mathematical Programming. 174:553-573, 2017.
K. Fountoulakis, D. Wang, and S. Yang. p-norm flow diffusion for local graph clustering. International Conference on Machine Learning (ICML), 2020a.
K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, and A. Jagannath. Graph attention retrospective. The Journal of Machine Learning Research, 24, 2023a.
Kimon Fountoulakis, Di Wang, and Shenghao Yang. P-norm flow diffusion for local graph clustering. In International Conference on Machine Learning, pp. 3222-3232. PMLR, 2020b.
Kimon Fountoulakis, Pan Li, and Shenghao Yang. Local hyper-flow diffusion. Advances in neural information processing systems, 34:27633-2769) 2021.
Kimon Fountoulakis, Meng Liu, David F Gleich, and Michael W Mahoney. Flow-based algorithms for improving clusters: unifying framework, software, and performance. SIAM Review, 65(1): 59-143, 2023b.
Dawei Gao, Haibin Wang, Yaliang Li, Xiuyu Sun, Yichen Qian, Bolin Ding, and Jingren Zhou. Text-to-sql empowered by large language models: A benchmark evaluation. arXiv preprint arXiv:2308. 15363, 2023a.
Hanning Gao, Lingfei Wu, Po Hu, Zhihua Wei, Fangli Xu, and Bo Long. Graph-augmented learning to rank for querying large-scale knowledge graph. AACL 2022, 2022.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yixin Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. Retrieval-augmented generation for large language models: A survey. arXiv preprint 23X 2(1), 2023b.
Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su. Beyond iid: three levels of generalization for question answering on knowledge bases. In Proceedings of the Web Conference 2021, pp. 3477-3488, 2021.
12

---

Published as a conference paper at ICLR 2026
Zirui Guo, Lianghao Xia, Yanhua Yu, Tu Ao, and Chao Huang. Lightrag: Simple and fast retrieval- augmented generation. arXiv preprint arXiv:2410.05779, 2024.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training In International conference on machine learning, pp. 3929-3938. PMLR, 2020.
W. Ha, K. Fountoulakis, and M. W. Mahoney. Statistical guarantees for local graph clustering. The Journal of Machine Learning Research, 22(1):6538-655) 2021.
Haoyu Han, Yu Wang. Harry Shomer, Kai Guo, Jiayuan Ding, Yongjia Lei, Mahantesh Halappanavar, Ryan A Rossi, Subhabrata Mukherjee, Xianfeng Tang, et al. Retrieval-augmented generation with graphs (graphrag). arXiv preprint arXiv:2501.00309, 2024.
Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-retriever: augmeeted generation for textual graph understanding and question answering. Advances in Neural Information Processing Systems, 37:132876-132900 2025.
Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing multi-hop qa dataset for comprehensive evaluation reasoning steps. COLING 2020, 2020.
Sebastian Hofstätter, Jiecao Chen, Karthik Raman, and Hamed Zamani. Fid-light: Efficient and effective retrieval-augmentee text generation. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 1437-1447, 2023.
Ziniu Hu, Yichong Xu, Wenhao Yu, Shuohang Wang, Ziyi Yang, Chenguang Zhu, Kai-Wei Chang, and Yizhou Sun. Empowering language models with knowledge graph reasoning for question answering. EMNLP, 2022.
C. Jia, Y. Li, M. B. Carson, X. Wang. and J. Yu. Node attribute-enhanced community detection in complex networks. Scientific reports, 7(1):1-15, 2017.
Zhengbao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi- Yu, Yiming Yang. Jamie Callan, and Graham Neubig. Active retrieval augmented generation. EMNLP 2023, 2023.
Bernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. Hipporag: Neurobio- logically inspired long-term memory for large language models. Advances in Neural Information Processing Systems, 37:59532-59561 2024.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint 1755v:100. 2017.
Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04900 2020.
Kiseung Kim and Jay- Yoon Lee. Re-rag: Improving open-domain qa performance and interpretability with relevance estimator in aeureeeal-uummented generation. arXiv preprint wrXiv:2406.05799 2024.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453-466 2019.
Chankyu Lee, Rajarshi Roy, Mengyao Xu, Jonathan Raiman, Mohammad Shoeybi, Bryan Catanzaro, and Wei Ping. Ny-embed: Improved techniques for training llms as generalist embedding models. arXiv preprint arXiv:2405.17435 2024.
Fangyu Lei. Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin Su, Zhaoqing Suo, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, et al. Spider 2.0: Evaluating language models on weal-world enterprise text-to-sqi workflows. arXiv preprint arXiv:2411.07722 2024.
13

---

Published as a conference paper at ICLR 2026
Fangyu Lei, Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin SU, ZHAOQING SUO, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, Victor Zhong, Caiming Xiong, Ruoxi Sun, Qian Liu, Sida Wang, and Tao Yu. Spider 2.0: Evaluating language models on real-world enterprise text-to-SQI. workflows. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
net/ fww.mmii=ddeiio ro j9cPs.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, al. Rerrieval-augmented genera- tion for nowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33: 9459-9474, 2020.
Chaofan Li, Zheng Liu, Shitao Xiao, Yingxia Shao, and Defu Lian. Llama2vec: Unsupervised adaptation of large language models for dense retrieval. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3490- 3500, 2024a.
Haoyang Li, Jing Zhang, Hanbing Liu, Fan, Xiaokang Zhang. Jun Zhu, Renjie Wei, Hongyan Pan, Cuiping Li, and Hong Chen. Codes: Towards building open-source language models for text-to-sql. Proc. ACM Manag. Data, 2(3), May 2024b. doi: 10.1145/3654930. URL
/ttps://doi... org. 1145/3654930.
Mufei Li, Siqi Miao, and Pan Li. Simple is effective: The roles of graphs and large language models in showledge-graph-beee retrieval-augment generation. ICLR 2025, 2024c.
M. Liu and D. F. Gleich. Strongly local p-norm-cut algorithms for semi-superrised learning and local graph clustering. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
László Lovász. Random walks graphs: A survey. In Combinatorics, Paul Erdös is Eighty, volume 2, pp. 1-46. János Bolyai Mathematical Society, 1993.
LINHAO LUO, Yuan- Yuan-Fang Li, Reza Haf, and Shirui Pan. Reasoning on graphs:
Faithful and
interpretable large language model reasoning. In The Twelfth International Conference on Learning Representations, 2024. URL https: /pwpreveeeeeeeeeeeeeeeeeeeeeeeee net forum? 2 21==2CNW77x200.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv preprint arXiv:2405.20139 2024.
Niklas Muennighoff, SU Hongjin, Liang Wang, Nan Yang, Furu Wei, Tao Yu, Amanpreet Singh, and Douwe Kiela. Generative representational instruction tuning. In The Thirteenth International Conference on Learning Representations, 2024.
Pranoy Panda, Ankush Agarwal, Chaitanya Devaguptapu, Manohar Kaul, al. Holmes: Hyper- relational knowledge graphs for multi-hop question answering using llms. ACL 2024, 2024.
Mohammadreza Pourreza and Davood Rafiei. Din-sql: Decomposed in-context learning of text-to-sql with self-correction. Advances in Neural Information Processing Systems, 36, 2024.
Mohammadreza Pourreza, Hailong Li, Ruoxi Sun, Yeounoh Chung, Shayan Talaei, Gaurav Tarlok Kakkar, Yu Gan, Amin Saberi, Fatma Ozcan, and Sercan O Arik. Chase-sql: Multi-path reasoning and preference optimized candidate selection in text-to-sql. arXiv preprint 11001:2400.01943, 2024.
Hongjin Qian, Peitian Zhang, Zheng Liu, Kelong Mao, and Zhicheng Dou. Memorag: Moving towards next-gen rag via memory-inspired knowledge discovery. arXiv preprint 055551.. 2024.
Qian and V. Saligrama. Efficient minimax signal detection on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
A. Reid and P. Yuval. Finding sparse cuts locally using evolving sets. In ACM Symposium on Theory of Computing (STOC), 2009.
14

---

Published as a conference paper at ICLR 2026
Pranab Sahoo, Prabhash Meharia, Akash Ghosh, Sriparna Saha, Vinija Jain, and Aman Chadha A comprehensive survey of hallucination in large language, image, video and audio foundation models. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 11709-1 1724, Miami, Florida, USA, November 2024. Association for Computational Linguisties. doi: 00.1863//1/2024 http////22.nnnnseeeeeee www.iingeeeeeee..6........ URL https:://///mm
org.:/llyooooooooooooooooooooo.o 2024. findings eemss--mn........ 685/.
Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D Manning.
Raptor: Recursive abstractive processing for tree-organized retrieval. In The Twelfth International Conference on Learning Representations, 2024.
Timo Schick, Jane Dwivedi-YY Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 06:68539-68553 2023.
J. L. Sharpnack, A. Krishnamurthy, and A. Singh. Near-optimal anomaly detection in graphs using lovasz extended scan statistic. In Advances in Neural Information Processing Systems (NeurIPS), 2013.
Shi, K. He, D. Bindel, and J. Hopcroft. Local Lanezos spectral approximation for community detection. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery Databases (ECML-PKDD), 2017.
Yucheng Shi, Qiaoyu Tan, Xuansheng Wu, Shaochen Zhong, Kaixiong Zhou, and Ninghao Liu. Retrieval-enhanced knowledge editing for multi-hop question answering in language models. arXiv preprint arXiv:2403. 1.000.,,9933.. 19631, 2024.
Robik Shrestha, Yang Zou, Qiuyu Chen, Zhiheng Li, Yusheng Xie, and Siqi Deng. Fairrag: Fair human generation via fair retrieval augmentation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 1999, 2024.
D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, 42(1):1-26, 2013a.
Daniel A. Spielman and Shang- -hang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing. 42(1):1-26, 2013b. doi: 10.1 137/080744888.
Saba Sturua, Isabelle Mohr, Mohammad Kalim Akram, Michael Günther, Bo Wang, Markus Krimmel, Feng Wang, Georgios Mastrapas, Andreas Koukounas, Nan Wang, et al. jina-mbeeddings-v:: Multilingual embeddings with task lora. arXiv preprint arXiv:2409. 10173, 2024.
Heli Sun, Fang Hc, Jianbin Huang, Yizhou Sun, Yang Li, Chenyu Wang, Liang He, Zhongbin Sun, and Xiaolin Jia. Network embedding for community detection in attributed networks. ACM Transactions Knowledge Discovery from Data (TKDD), 14(3):1-25, 2020.
Alon Talmor and Jonathan Berant. The web knowledge- base for answering complex questions. NAACL 2018, 2018
SM Tonmoy, SM Zaman, Vinija Jain, Anku Rani, Vipula Rawte, Aman Chadha, and Amitava Das. A comprehensive survey of hallucination mitigation techniques in large language models. arXiv preprint arXiv:2401.01333 2024.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Musique Multihop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539 554, 2022.
R. Vershynin. High- dimh-diimesional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Alex Wang, Richard Yuanzhe Pang. Angelica Chen, Jason Phang, and Samuel Bowman. Squality: Building a long-documen summarization dataset the hard way. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 1139- 1156, 2022.
15

---

Published as a conference paper at ICLR 2026
D. Wang, K. Fountoulakis, M. Henzinger, M. W. Mahoney, and S. Rao. Capacity releasing diffusion for speed and locality. International Conference on Machine Learning (ICML), 2017.
Mingyang Wang, Alisa Stoll, Lukas Lange, Heike Adel, Hinrich Schütze, and Jannik Strötgen. Bring your own knowledge: A survey of methods for I1m knowledge expansion, 2025. URL https: /aaas///aree //tpivaaavvvv/aaa/////eaaaaaaav wwwoooog//ooooo alss 2502. 12598.
Song Wang. Yanchen Zhu, Haochen Liu, Zaiyi Zheng. Chen Chen, et al. Knowledge editing for large language models: A survey. arXiv preprint arXiv:2310. 2023.
Yu Wang, Nedim Lipka, Ryan A Rossi, Alexa Siu, Ruiyi Zhang, and Tyler Derr. Knowledge graph prompting for multi-document question answering. Proceedings of the AAAI Conference on Artificial Intelligence, volume 18-17, pp. 19206-19214, 2024.
R. Wei, H. Yin, J. Jia, A. R. Benson, and P. Li. Understanding non-linearity in graph neural networks from the perspective of bayesian inference. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Yilin Wen, Zifeng Wang, and Jimeng Sun. Mindmap: Knowledge graph prompting sparks graph of thoughts in large language models. arXiv preprint arXiv:2308.0977 2023.
Daniel Wigh, Jonathan M Goodman, and Alexei A Lapkin. review of molecular representation in the age of machine learning. Wiley Interdisciplinary Reviews: Computational Molecular Science, 12(5):e ee 1603, 2022.
X. Wu, Z. Chen, W. Wang, and A. Jadbabaie. An non non-asymptotic analysis of oversmoothing in graph neural networks. In International Conference on Learning Representations (ICLR), 2023.
Wenhan Xiong, Mo Yu, Shiyu Chang, Xiaoxiao Guo, and William Yang Wang. Improving question answering incomplete kbs with knowledge-aware reader. arXiv preprint 1905.0:900.070000 2019.
Wenhan Xiong, Xiang Lorraine Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kicla, et al. Answering complex open-domain questions with multi-hop dense retrieval. arXiv preprint arXiv:2009.12756 2020.
Ran Xu, Wenqi Shi, Yue Yu, Yuchen Zhuang, Bowen Jin, May Wang, Joyce Ho, and Carl Yang. Ram-ehr: Retrieval augmentation meets clinical predictions electronic health records. arXiv preprint arXiv:2403.00815 2024.
B. Yan and P. Sarkar. Covariate regularized community detection in sparse graphs. Journal of the American Statistical Association, 166553))734--45, 2021.
J. Yang. J. McAuley, and J. Leskovec. Community detection in networks with node attributes. In IEEE International Conference on Data Mining (ICDM), 2013.
Shenghao Yang and Kimon Fountoulakis. Weighted flow diffusion for local graph clustering with node attributes: An algorithm and statistical guarantees. In International Conference on Machine Learning, pp.
PMLR, 2023.
Zhilin Yang, Peng Qi. Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. EMNLP 2018, 2018
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. Re- act: synergizing reasoning and acting in language models (2022). arXiv preprint arXiv:2210.03669, 2023.
Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. NAACI 2021, 2021a.
Michihiro Yasunaga. Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gmn: Reasoning with language models and knowledge graphs for question answering. In Proceedings of NAACI-HILT, pp. 535-546, 2021b.
16

---

Published as a conference paper at ICLR 2026
Shenglai Zeng, Jiankun Zhang, Pengfei He, Jie Ren, Tianqi Zheng, Hanqing Lu, Han Xu, Hui Liu, Yue Xing, and Jiliang Tang. Mitigating the privacy issues in aarreval-auggeent generation (rag) via pure synthetic data. arXiv preprint arXiv:2406. 14..24406.4777,, 2024a.
Shenglai Zeng, Jiankun Zhang, Pengfei He, Yue Xing, Yiding Liu, Han Xu, Jie Ren, Shuaiqiang Wang, Dawei Yin, Yi Chang, et al. The good and the bad: Exploring privacy issues in retrieval-augmented generation (rag). arXiv preprint
SDN::402..1692. 2024b.
Boyu Zhang, Hongyang Yang, Tianyu Zhou, Muhammad Ali Babar, and Xiao- Yang Liu. Enhancing financial sentiment analysis via retrieval augmented large language models. In Proceedings of the fourth ACM international conference on Al in finance, pp. 349-356, 2023.
Lingxi Zhang, Yue Yu, Kuan Wang, and Chao Zhang. Arl2: Aligning retrievers for black-box large language models via self- self-guided adaptive relevance labeling. ACL 2024, 2024a.
Qinggang Zhang, Jumnan Dong, Hao Chen, Daochen Zha, Zailiang Yu, and Xiao Huang. Knowgpt: Knowledge graph based prompting for large language models. NeurlPS 2024 Poster, 2024b.
Yue Zhang, Zhihao Zhang, Wenbin Lai, Chong Zhang, Tao Gui, Qi Zhang, and Xuan-Jing Huang. to-tree: Parsing pdf text blocks into a tree. In Findings of the Association for Computational Linguistics:
EMNLP 2024, pp. 10704-10714 2024c.
C. Zhe, A. Sun, and X. Xiao. Community detection large complex attribute network. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Fengbin Zhu, Wenqiang Lei, Chao Wang, Jianming Zheng, Soujanya Poria, and Tat-Seng Chua. Retrieving and reading: comprehensive survey on open-domain question answering. arXiv preprint 2rXiv2201.00774 2021.
17

---

Published as a conference paper at ICLR 2026
Appendix
CONTENTS
A1 Extended Related Work
19
A1.1 Retreeval-Augmenedd Generation.
19
A1.2 Graph Diffusion and Flow Methods
19
A1.3 QAFD-RAG's Positioning within Graph-Barn Based RAG Approaches
20
A2 Extended Experiments
20
A2.1 Question Answering (QA)
20
A2.1.1 Additional Numerical Results for General Question Answering
20
A2.1.2 Sensitivity Analysis for QAFD-RAG
A2.1.3 Runtime and Efficiency of QAFD-RAC for General QA
21
A2.14 Embedding Model Sensitivity Analysis
22
A2.1.5 Long-Document Summarization: SQuALITY Evaluation Details
22
A2.2 Text-toSQL
23
A2.2.1 Hyperparameter Settings
23
A2.2.2 Examples of Schema Identified by QAFD-RAG for Spider2's Queries
23
A2.2.3 LLM Efficiency and Schema Linking Performance
25
A2.2.4 Embedding Model Sensitivity for Text-to-SQL.
25
A3 Proof of Main Results
26
A3.1 Proof of Lemma
26
A3.2 Proof of Theorem 3
26
A3.3 Proof of Lemma 6
27
A3.4 Proof of Theorem 7
28
A4 Overview of Datasets and Prompts Used QAFD-RAG for Question Answering
29
A4.1 Datasets
29
A4.2 Entity and Relationship Extraction Prompt
29
A4.3 Keyword Extraction Prompt
31
A4.4 Query Answering Prompt
................................
A4.5 Evaluation Prompt
32
Overview of Prompts Used in QAFD-RAG Text-to-SQL Tasks
A6 Text-to-SQL. Baselines
35
A7 Usage of Large Language Models (LLMs)
38
18

---

Published as a conference paper at ICLR 2026
A1 EXTENDED RELATED WORK
A1.1 RETRIEVAL-AUGGENTT GENERATION.
LLMs remain prone to hallucinations and a lack of domain knowledge (Sahoo et al., 2024; Wang et al., 2025). Text-based RAG reduces these issues by supplementing LLMs with unstructured external data (Lewis et al., 2020; Guu et al., 2020). These systems employ sparse dense retrieval (Alon et al., 2022; Schick et al., 2023; Jiang et al., 2023; Cheng et al., 2024; Hofstätter et al., 2023; Li al., 2024a; Zhang et al., 2024a), but most treat text flat segments, missing critical context and inter-document relationships (Edge et al., 2024a; Guo et al., 2024).
KG-RAG enhances interpretability and factuality by leveraging structured knowledge graphs (Ya- sunaga et al., 2021a; Gao et al., 2022; Li ct al., 2024c; He et al., 2025). These systems utilize curated (Wen et al., 2023; Dehghan al., 2024) or optimized (Fang et al., 2024b; Panda et al., 2024) graphs to retrieve entity and relational context, typically extracting local subgraphs relevant to a query (Bordes et al., 2015; Talmor& & Berant, 2018; Gu et al., 2021). However, most KG-RAG methods focus on single-hop or shallow queries (Joshi et al., 2017; Yang et al., 2018; Kwiatkowski et al., 2019; Ho et al., 2020) and struggle with scale and multi-step reasoning.
Among training-intensive approaches, QA-GNN (Yasunaga et al., 2021b) combines pre-trained language models and knowledge graphs by using LM-based relevance scoring to select pertinent KG nodes, followed by joint graph neural reasoning for accurate and interpretable question answering. Xiong et al. (2019) proposed knowledge-awai neural retrievers for incomplete KBs. Other works such SubgraphRAG (Li et al., 2024c) train end-to-end retrieval modules extract relevant KG subgraphs for downstream LLM reasoning. Several studies have also integrated knowledge graph structure directly into transformers for enhanced QA (Hu et al., 2022), and KnowGPT (Zhang et al., 2024b) leverages KG-based prompting for large language models. GNN-RAG (Mavromatis & Karypis. 2024) trains GNNs to score answer candidates and retrieve shortest paths, while RoG (LUO et al., 2024) uses LLM prompting to generate relation paths. Both methods incorporate query semantics but require training/finttningg, lack thcoretical guarantees, and operate over static graph structures during retrieval. However, these methods require substantial supervised data and retraining, in contrast to our training-fres query- aware flow diffusion framework with statistical guarantees.
Recent work has explored training- free KG-RAG methods. building rext-associated graphs to support more complex and multi-hop queries (Edge et al., 2024a; Guo et al., 2024), For instance, GraphRAG (Edge et al., 2024a) applies community detection to cluster entities. while LightRAG (Guo et al., 2024) uses multi-stage retrieval and ego-network aggregation. PathRAG (Chen et al., 2025a) further improves graph-based RAG by retrieving key relational paths rather than redundant neighborhood information, using flow-based pruning to identify reliable paths and strategic prompt organization to enhance LLM responses. However, all aforementioned methods still struggle to precisely align query intent with relevant regions of the graph, making it difficult to identify semantically coherent reasoning subgraphs. Furthermore, existing RAG approaches generally lack statistical optimization guarantees, as well as complexity analysis, for their retrieval mechanisms.
A1.2 GRAPH DIFFUSION AND FLOW METHODS
Graph diffusion describes the process of spreading mass from one or more seed nodes to neighboring nodes along graph edges. The empirical and theoretical performance of local diffusion methods is typically evaluated in the context of local graph clustering. Local graph clustering was introduced by Spielman & Teng (2013a) using random-wall walk algorithm, with Andersen et al. (2006) later employing personalized PageRank. Most works analyze these methods via output conductance (Andersen et al., 2006; Reid & Yuval, 2009; Spielman & Teng, 2013a; Allen-Zhu et al., 2013; Andersen et al., 2016; Shi et al., 2017: Wang et al., 2017; Fountoulakis et al., 2020a; Liu & Gleich, 2020). Statistical analysis appeared in Ha et al. (2021) for E f--regularized PageRank (Fountoulakis et al., 2017), though attributed graphs remain unaddressed.
Community/cluster detection methods that combine structure and node or edge attributes (Yang et al., 2013; Jia et al., 2017: Zhe et al., 2019; Sun et al., 2020) benefit from this integration but require global processing, making them unsuitable for local clustering. Contextual random graph models have been employed for attributed community detection (Deshpande et al., 2018; Yan & Sarkar, 2021; Braun al., 2022; Abbe al., 2022), node separability (Baranwal et al., 2021; Fountoulakis et al.,
19

---

Published as a conference paper at ICLR 2026
2023a; Baranwal et al., 2023a), and analysis of graph convolutions and optimal classifiers (Wu et al.,
2023; Wei et al., 2022; Baranwal et al., 2023b). Related anomaly detection (Arias-Castro Castro et al., 2008;
2011; Sharpnack et al., 2013; Qian & Saligrama, 2014) and estimation (Chitra al., 202 1) methods focus on scalar data and global processing, contrasting with our local, attribute-aware approach.
A1.3 QAFD-RAG'S POSITIONING WITHIN GRAAP-BAASE RAG APPROACHES
To our knowledge, none of these works connect the graph structure to the query. Our work is the first to provide principled framework that links given query to the corresponding subgraph in a knowledge graph, and the first to develop and statistically analyze query-awarg flow diffusion in general contextual random graph models with formal recovery guarantees.
Beyond these thcoretical contributions, QAFD-RAG's modular design positions it as a complementary retrieval component for existing graph-based RAG systems, requiring retraining while providing formal guarantees. Specifically:
GraphRAG. GraphRAG (Edge al., 2024a) relies static community detection (Leiden algorithm) to precompute hierarchical clusters and generate community summaries for retrieval. QAFD-RAG offers an alternative through dynamic, query-time subgraph discovery tailored to each query's semantics, climinating the computational overhead of community summary generation while adapting retrieval to query-specific needs.
HippoRAG. HippoRAG (Jimenez Gutierrez et al., 2024) uses Personalized PageRank (PPR) for graph traversal from seed nodes. QAFD-RAG provides principled alternative through query-aware edge reweighting (Equations (4)-(5)). While PPR provides graph-based signals, it lacks query-aware edge modulation our method's 's key innovation that suppresses irrelevant paths while amplifying semantically aligned connections, backed by formal recovery guarantees (Theorem 7).
LightRAG. LightRAG (Guo al., 2024) employs dual-level keyword extraction with single-hop neighborhood aggregation. QAFD-RAG extends this paradigm by enabling multi-hop flow dif- fusion from extracted keywords as seed nodes, discovering reasoning paths that span multiple hops-precisely the capability that Ligs current single-hop approach lacks preserving its efficient indexing structure.
This positioning demonstrates QAFD-RAG's role foundational component that addresses key limitations in existing graph-based RAG approaches through principled, theoretically groundded retrieval.
A2
EXTENDED EXPERIMENTS
A2.1
QUESTION ANSWERING (QA)
A2.1.1
ADDITIONAL. NUMERICAL. RESULTS FOR GENERAL. QUESTION ANSWERING
Table 5 presents comprehensive results across five additional UltraDomain Mix. Music, Philosophy, and RAPTOR, and HíppoRAG across all five GPT-4o-scored dimensions (Comprehensiveness, Diversity, Logicality, Relevance, and Coherence).
QAFD-RAG against GraphRAG, LightRAG,
QAFD-RAG achieves the best performance across all dimensions in four out of five datasets (Mathe- matics, Mix, Philosophy, and Physics), demonstrating consistent superiority with scores typically 3-7 points higher than the strongest baseline. For example, on Physies, QAFD-RAG achieves 89.51 Comprehensiveness compared to GraphRAG's 86.33, and 95.61 Relevance compared to RAPTOR's 94.46. On Music, QAFD-RAG leads in four dimensions (Comprehensiveness: 87.95, Diversity: 83.40, Logicality: 90.56. Coherence: 90.94), with GraphRAG marginally ahead only on Relevance 194.14 vs. 94.08). These results validate QAFD-RAG's robustness across diverse domains spanning technical (Mathematics, Physics), creative (Music), conceptual (Philosophy), and mixed content, consistently outperforming state-of-the the-art graph-based RAG methods through query- aware flow diffusion and dynamic edge reweighting.
20

---

Published as a conference paper at ICLR 2026
Table Comparison of QAFD-RAG and baselines across five GPT-4o-scored dimensions (0-100).
Rows are grouped by dataset; columns are metrics. Each cell shows mean (= std) over 5 independent evaluations. Best scores per dataset/metric are bolded. (continued).
Dataset
Method
Comprehensive.
Diversity
Logicality
Relevance
Coherence
Mathematics
GraphRAG
(1.4661 84.30
88,91 (198.11.200
92.65(1110.4)
89.04(17.52)
LightRAG
(+.944+
74.07 (+ 10.40)
86.30(+6.20)
90.77 (+-8.66
86.29
RAPTOR
81.18
(12.34))
87.30
91.88 (18.73)
87.70(14.57)
HippoRAG
80.77 (+5.31)
(=9.56))
87.05 (++4666)
(+5.53)
(43.664
QAFD-RAG
(+..04))
(2.56(+
(0.04
(4..44+
90.37
Mix
GraphRAG
82.76(=11.41)
74.94 (#11.68)
88.45 (+6.95)
92.81 (#:8.65) 65)
38.90
LightRAG
(1.72(113.12)
70.97 (1.13.39)
85.72
90.37 (19936)
86,26 (14.68)
RAPTOR
(15.50))
73.09 (=7.75)
(3.7011
93.16(+3.47)
87.81 (33,28)
HippoRAG
(=5.20))
71.71 (=6.12)
86.55 (#3.97)
02.11
86.83 (=3,35)
QAFD-RAG
(L.16))
(1.1.611.66)
(1.703)
(1.360))
90,36 (12.07)
Music
GraphRAG
85.32(++6466
(97.72+
(+-4.33
94.14
39.80
LightRAG
(1.144)
75.08 (..13)
86.64 (L1.,29)
91.29
87.34 (1.366)
RAPTOR
(18.4
(411..6
87.81 (+4.36)
(4:391))
88.14 (=:.54)
AG
80.95
(+..6))
(++.98)
92.47644.76
87.53 (+3667)
QAFD-RAG
(+3999)))
83.40
90.56 (#3.77)
94.08 (2:5445444)) (6)
90.94 (#2339)
Philosophy
GraphRAG
24.61441
78.36
88.67 (116,00)
93.53 (1.8.55)
88.83 (16.559
LightRAG
80,92 (+8.88))
74.36
85.74
(0.85
86.44 (24.661)
RAPTOR
82.307))
(5.54
87.30
(14.65)
87.83 (11.45)
HippoRAG
(15.44))
86.66(14.52) (16,75)))75)
92.03 (LL4.69)
87,42 (13.38))
QAFD-RAG
86.78(+4.11)
81.91 (++4.69)
89.35 (++4,55
(+
89.91 (+2.70)
Physics
GraphRAG
(47.32)
(9..0)))
90.29 (+7.688
(#7.71)
(17.37)
LightRAG
84.45 (+4.39)
76.38 (+).19)
89.13 (++4377
93.67 (+5.399)
88.65 (+2.76)
RAPTOR
84..8(+3.98)
(+.27
(+3.2
89.22 94.46++2881
HippoRAG
(23.63)))
(=5.81)
88.667+3)07)
94.09 (+2.43)
88.69 (42.54)
QAFD-RAG
89.51 (#3.14)
84.21 (=3.89)
(+3.26)
05:6.7722.44
91.67 (+2.14)
A2.1.2 SENSITIVITY ANALYSIS FOR QAFD-RAG
To assess the robustness of QAFD-RAS under different configurations, we conduct a sensitivity analysis three key hyperparameters the Mix dataset in framework: the number of seed nodes used for QAFD, the initial mass parameter a in the QAFD process, and the choice of edge weight formulation that governs propagation dynamics. We define the tuning ranges follows:
Number of seed nodes: {20, 30, 40, 50, 60)
a (mass initialization): (5, 10, 20, 50, 100)
Query-aware edge weight: three distinct formulations reflecting different query-to-node
affinity strategies (as presented in Eqn (2a), (2h), and (2c)).
When analyzing single hyperparameter, the others are held constant at their default values: a = 50, the number of seed nodes is 20, and the default query-aware edge weight function is the hybrid formulation.
Figure shows that overall performance is stable across the tested ranges, confirming the robustness of QAFD-RAG, Among all metrics, only relevance exhibits noticeable dependency on the number of seed nodes, slightly improving as fewer seed nodes are introduced, suggesting that 20 seed nodes are already sufficient for most evaluation dimensions. In contrast, = 50 yields the best overall balance across metrics; both very small and very large values tend to slightly degrade performance, likely due to insufficient overly diffused mass concentration during propagation. Surprisingly, the choice of edge weight function has relatively minor effect-all three variants yield comparable results across metrics, with only slight differences in relevance and logicality.
These findings indicate that QAFD-RAG not overly sensitive to hyperparameter settings and performs robustly across wide range of configurations, requiring minimal tuning in practice.
12.13 RUNTIME AND EFFICIENCY QAFD-RAG FOR GENERAL. QA
Table shows that QAFD-RAG matches or outperforms LightRAG in wall-clock time and is substantially faster than GraphRAG. The efficiency gains primarily come from indexing: instead of
21

---

Published as a conference paper at ICLR 2026
Comprehensiveness
Diversity
Logicality
Relevance
Coherence
99
95
Score
Score
75
75
75-
70
30
Number Seed Nodes
Weight Choice
Figure 3: Sensitivity of QAFD-RAG to the number of seed nodes (left), initial mass (middle), and edge weight choice (right), evaluated across five dimensions on the Mix dataset.
Table 6: Total runtime (in seconds) for graph-based RAG on the full Mix dataset.
Method
QAFD-RAG
LightRAG
GraphRAG
Total Time (s)
8948.81
9236.38
50968.59
performing global hierarchical summarization, QAFD-RAG processes only the subgraph retrieved at query time. The diffusion step adds negligible overhead because edge weights are computed on demand and traversal is nearly linear. Overall, these properties provide a favorable balance of accuracy and efficiency.
12.1.4 EMBEDDING MODEL SENSITIVITY ANALYSIS
To assess QAFD-RAG's robustness to embedding quality, we evaluate the framework across five diverse embedding models on the Mix dataset from UltraDomain. We compare: (i) OpenAl's -ext-eembeddin--3----
(1536-dim) and -ext-embeddinee weweeedddinn----rrree- (3072-dim), rep- (Sturua et al., 2024) (1024-dim), an open-source local model; (iii) NVIDIA's nv nnveembe--e v2 (Lee et al., 2024) (4096-dim), optimized for retrieval tasks; and (iv) Gri PrittL-775 (Muennighoff et al., 2024) (4096-dim), unified generative-embeddin model. All other hyperparameters remain fixed across experiments.
resenting cloud-based proprietary embeddings; (ii) Jina Al's anna-emeeddnggs
Table 7 presents results across five evaluation dimensions. QAFD-RAG demonstrates consistent performance across all embedding models, with Comprehensiveness scores ranging from 85.82 to 88.1 12 and Relevance scores from 91.98 to 95.12. Notably, text lext-embedding- maseeeddddnnn--arrgee achieves the best performance on Comprehensiveness, Diversity, and Relevance, while nv www-embbedyye excels on Logicality and Coherence. However, the overlapping standard deviations across models indicate that differences are modest.
Importantly, jina-v3, despite being the lowest-dimensional model (1024-dim) and fully local, achieves competitive results-on only 2-3 points below the best performing models on most metrics. This demonstrates that QAFD-RAG's query-aware flow diffusion mechanism is robust to embed- ding variations and can operate effectively with resource-cones constraiinn or privacy-preserving local embeddings. The consistent performance across diverse architectures (cloud vs. local, 1024-dim to 4096-dim) validates that our theoretical framework successfully leverages semantic similarity regardless of the specific embedding space.
A2.1.5 LONG-DOCUMENT SUMMARIZATION SQUALITY EVALUATION DETAILS
We evaluate all 250 questions from the SQUALITY training dataset (Wang al., 2022), which contains narrative passages paired with comprehension questions and multiple human human-written written refer- answers per question. We compute BLEU-1 and BLEU-- using unigram and bigram modified
22

---

Published as a conference paper at ICLR 2026
Table 7: Embedding sensitivity analysis: QAFD-RAG performance across five embedding models on the Mix dataset. All numbers are mean (# stdev) over 5 runs.
Embedding Model
Comprehensive.
Diversity
Logicality
Relevance
Coherence
rext-embedding-B3 3-mmall (1536d)
87.15 (+3.46)
81.15 (+4.86)
90.70
94,36 (+4.50)
90.36 (#2.07)
text-embedding---luee (3072d)
88.12 (+3.32)
83.08 (=4.71)
91.28 (=2.85)
95.12 (44.35)
90.85 (#2.01)
jina-v3 (1024d)
85,82 (+3.58)
80.18 (+5.02)
89.18 (#3.05)
91.98 (44.68)
87 97 (+2.15)
NVIDIA-ax-embedd22 (4096d)
87.85 (+3,411
82,45 (#4.78)
91.58 (+2.81)
94.78 (#4.42)
91.45 (+1.9))
Griil M-7B (4096d)
87.32 (#3.51)
81.64 (+4.91)
89.82 (+2.97)
93.52 (44.55)
90.28 (+2.
precisions with geometric averaging. BLEU-n is defined as
BLEU-n == exp wy log
where pi is the i-gram precision and (wi,.... W.,) are the weights. For BLEU-1 we use (1,0, 0, 0): for BLEU-2 we use (0.5, 0.5, 0, 0). ROUGE-1 Fl and ROUGE-2 Fl report Fl overlap of unigrams and bigrams using Porter stemming.
METEOR combines unigram precision (P) and recall (R) with a fragmentation penalty:
METEOR == Fmman (1 (1-7-- (1-7-
chunks
)
matches
where harmonic mean Fican- := P R/(aP +1 R). chunks denotes contiguous matched segments and matches denotes total matched unigrams. We use Natural Language Toolkit (NLTK) defaults: a = 0.9, 3 = 3.0, and y = 0.5. All metrics use lowercased, word-tokenized text with BLEUMETEOR computed against all references.
knowledge graph constructed once from all narrative documents and reused across queries. All experiments use hybrid retrieval mode with diffusion parameter 10, 40-node source budget, and minimum flow threshold 0.01. Answers are produced with GPT-4o-mini using greedy decoding and full caching.
A2.2 TEXT-TO-SQL
A2.2.1
HYPERPARAMETER SETTINGS
We report the full of QAFD-RAG hyperparameters used in our implementation. The most critical parameters are the source mass and the target capacity. The source mass is adaptively set based on the degree of the source node, following local clustering strategies in Fountoulakis al. (2020b). Specifically, we define
= EjEr Tj. where P is the set of nodes the shortest path from source to target. The multiplier a = 10 controls the initial injected mass; larger values ensure sufficient propagation across the graph. no path exists between source and target, we apply fallback rule: m, = Σ,ey T,. Each node, including the target, is assigned uniform sink capacity
T; = 1 and initialized with zero mass. During diffusion, nodes absorb incoming flow up to their capacity, with excess redistributed until convergence.
Other hyperparameters regulate the iterative behavior of the algorithm, to which is generally robust. The convergence threshold in Algorithm 2 is set to 0.05, terminating when total excess mass falls below this threshold. To safeguard against non-convergence, we cap iterations at Nmax = 10 and check convergence every 100 steps. For stability during edge reweighting, constant 10 10 is added to all computations.
A2.2.2 EXAMPLES OF SCHEMA IDENTIFIED BY QAFD-RAG FOR SPIDER2'S S QUERIES
The core efficiency of QAFD-RAG stems from its ability to globally reason over the schema graph through flow diffusion, directly identifying the most relevant multi-hop paths between schema elements implicated by the query. As illustrated in Figure 4, DAFD-RAG, unlike Spider-Agent and other ReAct-style sehhods-wiihh must sequentially probe the schema, issuing separate LLM call
23

---

Published as a conference paper at ICLR 2026
Think
Observation:...
Thought: .. will now explore the 'flm'' table to sce how it connects to other tables, especially through 'inventory" _a__________ Se__sSllfflllll outhhr "aggotttttthlliooooee "Fagik command- "PRAGMA teble infolfimi! output="drect"
Thought:.. ... Yow, necescory Information
condruct quarrty SCJ query actteve
Action:
Figure 4: Left: Schema path identified by HAFD-RAGE for SQL generation on query local039 (Lei al., 2025). Right:
Stepwise schema exploration for the same query using Spider-Agent (ReAct) (Lei et al., 2025). QAFD-RAG discovers the full reasoning path in one pass, sharply reducing LLM calls. In contrast, Spider-Agent incrementally explores the schema, requiring 14 calls and higher latency. This comparison highlights QAFD-RAG's 's efficiency and accuracy complex multi-hop queries.
Salesquota
territoryid
Businesaentiryi
ordendate
Inerihoryid
salespersonid
territoryia
FOOLE
Quota
Figure 5: QAFD-RAG retrieved schema for Query-Local141 in the Adventure Workss database KG (Lei et al., 2025).
for each reasoning step, table, or peiin-pefforms single, structured optimization to simultaneously discover all semantically relevant paths. This eliminates redundant exploration and dramatically reduces both the number of LLM calls and overall inference time, especially for queries requiring long complex join paths. Consequently, DAFD-RAG delivers scalable inference for large enterprise databases while maintaining or even improving accuracy.
We provide additional example to illustrate the advantages of our framework in uncovering meaningful schema paths, using Query-Local14] from the Adventure Works database (Lei al., 2025).
24

---

Published as a conference paper at ICLR 2026
Table 8: LLM call efficiency across SQLite and Snowflake. Lower is better.
Method
SQLite LLM Calls
Snowflake LLM Calls
Spider-Agon
724
1482
QAFD-RAG + SQL-Agent
493
674
Table 9: Schema linking performance (precision, recall, F1). Higher is better.
Method
SQLite
Snowflake
Prec
Rec
F1
Prec
Rec
F1
Spider-Agent QAFD-RAG
0.81
0.75
0.78
0.35
0.35
0.35
0.82
0.76
0.79
0.60
0.59
0.60
Example (Query-Local141). How did each salesperson's 's annual total sales compare to their annual sales quota? Provide the difference between their total sales and the quota for each year, organized by salexperson and year
Figure 5 visualizes the relevant portion of the complex database schema as graph, highlighting two distinct schema path decompositions: one corresponding to the sales quota (green path) and the other to the total sales (orange path). These paths not only capture the necessary schema linking but also reveal the underlying reasoning required to answer the query, as seen from the traversal across key nodes such SalesQuota, totaldue, orderdate, and identifiers such as Busuinessee MusinessEntityTT and salespersonid.
While Spider-Agent fails this complex multi-hop reasoning query, QAFD-RAG effectively lever- ages the discovered paths to solve the problem, demonstrating the power of path-based schema linking and reasoning for compositional SQL logic.
A2.2.3 LLM EFFICIENCY AND SCHEMA LINKING PERFORMANCE
Table 8 demonstrates that QAFD-RAG + SQL-Agent significantly reduces LLM call overhead, using 31.9% fewer LLM calls on SQLite and 54.5% fewer calls Snowflake compared the standard Spider-Agent approach. Overall, QAFD-RAG + SQL-Agent consistently outperforms baselines across both environments.
Finally, Table 9 presents detailed schema linking performance measured by precision, recall, and Fl-score. It demonstrates the core advantage of QAFD-RAG in identifying relevant schema elements (tables and columns) for the given queries, explaining both its accuracy improvements and efficiency gains over Spider-Agent.
A2.2.4 EMBEDDING MODEL SENSITIVITY FOR TEXT-TO-SQL.
To evaluate QAFD-RAG's robustness to embedding quality in the Text-to-SQL domain, we as- sess schema linking performance across five diverse embedding models the Local category (SQLite databases). We compare: (i) OpenAl's text-eenbeddlng-3-snmm
(1536-dim) and -exxt-eebbedingg---aaeeeee (3072-dim), representing cloud-base based proprictary embeddings: (ii) Jina Al's
(Sturua et al., 2024) (1024-dim), an open-source local model; (iii) NVIDIA's nv-embed-v2 (lee et al., 2024) (4096-dim), optimized for retrieval tasks; and (iv) GritLM-7B (Muennighoff et al., 2024) (4096-dim), unified generative-embeddiee model. All other hyperparameters remain fixed across experiments.
Table 10 presents schema linking results. QAFD-RAG demonstrates consistent performance across all embedding models, with precision scores ranging from 0.80 to 0.83, recall from 0.76 to 0.81, and Fl scores from 0.78 to 0.82. Notably, nv-embed-v2 achieves the best performance across all metrics (0.83/0.81/0.82)) which is specifically optimized for retrieval tasks, followed closely by text text-eebeddiing ng large (0.82/0.77/0.79) and Grí t.M (0.82/0.78/0.8))
25

---

Published as a conference paper at ICLR 2026
Table 10:
Embedding sensitivity analysis for Text-to-SQL (Local category): QAFD-RAG perfor- mance across five embedding models.
Embedding Model
Precision
Recall
F1-Score
text-embedding-- -eeembbedddnn----maall (1536d)
0.82
0.76
0.79
tcxt-embedding-3-Bllle (3072d)
0.82
0.77
0.79
jina-v3 (1024d)
0.80
0.76
0.78
NVIDIA-ny-embedt (4096d)
0.83
0.81
0.82
GritLM-7B (4096d)
0.82
0.78
0.80
Importantly, jina-v3, despite being the lowest-dimensions model (1024-dim) and fully local, achieves competitive results-only 0.04 points below the best model in F1 score. This demonstrates that QAFD-RAG's query-aware flow diffusion mechanism is robust embedding variations and can operate effectively with resource-constrained or privacy-preserving local embeddings. The consistent performance across diverse architectures (cloud vs. local, 1024-dim to 4096-dim, ranging from 0.78 to 0.82 FI) validates that our framework successfully leverages semantic similarity for schema linking regardless of the specific embedding space, making it practical for deployment in varied infrastructure environments.
A3 PROOF OF MAIN RESULTS
A3.1 PROOF OF LEMMA
Proof. The proof follows from the structure of the push-relabel algorithm and properties of the dual formulation.
Algorithm 2 only increases F, when node has excess mass m. > T,, By the complementary slackness conditions of the dual problem (7), if æu (k) 0 at the optimum, then the corresponding constraint is inactive, meaning m., S T, optimality. Since the algorithm maintains the invariant that mass can only flow from nodes with excess to their neighbors, and the algorithm starts with
xD any node with (k) 0 will never have excess mass during the algorithm's 's exccution. Therefore, x 0 for all iterations t, proving supp(x') S supp(x((*)))
The source mass determines the total amount of "flow" injected into the system. Each unit of flow that reaches node u contributes at least a minimum amount to x, (bounded by the algorithm's 's push operations). Since mass is conserved and each node in the support must receive some positive flow to have Zu > O, the number of nodes that can be in the support is upper bounded by the total mass A (k) ||1. Formally, if supp(x(()
A (k) || then the average flow per supported node would be less than 1, but the discrete nature the push operations and capacity constraints ensure each supported node receives at least minimum quantum of flow, leading contradiction.
A3.2 PROOF OF THEOREM 3
Proof. The proof follows the framework of coordinate descent analysis for flow diffusion problems (Fountoulakis et al., 2020b), adapted handle query-aware edge weights. We analyze the expected decrease in the objective function at each iteration.
For simplicity, let F(x) 1 L(x)) + (T A (k)) be the dual objective from (7), where [(gk) BT (q:) B the query-aware weighted Laplacian. At iteration Algorithm 2 selects a node u with excess mass m., > T, uniformly at random and performs a push operation. The
mass vector maintains the relationship m A (R) L(gg) so the gradient is F = L(g )x
(T A (k)) T 9F Zr.. T, m. < 0. The algorithm increases by exesss where Eneg w(gk; u, v), and redistributes the excess neighbors.
When node is selected, the excess mass is excess M. T, 0.
which corresponds to
us
26

---

Published as a conference paper at ICLR 2026
The key insight is that this corresponds to coordinate descent step. The expected decrease in the objective function
(excess)²
F[F(x!+1) F(x*)] --E
P(node is selected)
(10)
2wa
Since nodes are selected uniformly from the excess set, and by Lemma 2, all iterates have support contained in supp(x(())), we have
())
B[F(x FF(F)) (upp(x(())))
( (y(
IT m'l?
(11)
where we use (A)) < w(gk. u, v) for edges in the optimal support (minimum weight);
Eona w(gk, u, u) S 7 (R) for nodes in the optimal support (maximum weighted degree); and The
excess mass at each node is bounded by the gradient components.
The total excess mass is T m'l and by the optimality conditions, this relates the suboptimality as
F(x') ((x S C. -
(12)
for constant C' depending the problem parameters. Combining these bounds and using the fact that supppxx(P (()))) S (8) 1 from Lemma 2, we get
(2)
E[F(x - F(x(()))) $
B[F(x*) F(x((1))))
(13)
C
(A) (A)
This gives exponential convergence with rate we need
To achieve B[F(x*"))) - s E.
A
(()) [(²== -0(10
(k) 17())
log
(14)
The query-aware nature enters through the weights (Kt,, u, v) in the definitions of (k)) and (k)) meaning the convergence rate adapts to the semantic structure induced by the query, while maintaining the same algorithmic guarantees classical flow diffusion.
A3.3 PROOF OF LEMMA 6
Proof.
Note that for any nodes u, U E V and h E [K], we have
lle, Cqe 11? Mu M 112 + ||zu Zgn 122 2 2/p1.
Mbx Zu Zgeis
(15a)
l|e, - 1 2 |m - M,,12 + ||zu
Moy Zua Zu).
(15b)
To analyze the concentration of ||c. - cqu 2 note that ||z,. - Z =1=== Ei=i 2nne)² Each term
(Zut 2y El( - Zqut) ) |] is sub-exponential with parameter most Co? for some absolute constant C' (see, c.g., (Vershynin, 2018, Theorem 2.7.7)). Applying Bernstein's 's inequality for sums
of independent sub-exponential random variables and setting Ci log [V/, we obtain
Iz, Zqu 11
<
2
of +
C10² log |
(16a)
t=1
with probability at least 2/ where â maxi and é' > 0 is a constant. For the cross term, observe that
( M922 Zn Zoge = Σ (uue (Zue Zqce)
1=1
is sum of independent, mean-zero sub-Gaussian random variables. By standard sub-Gaussian tail bounds (e.g., Hoeffding's inequality), for any C2 > 0,
P (1140 - MMg Zn 2gp)) > C2ô LeāVlog log Dillu, (Mge < 2|1 -c
27

---

Published as a conference paper at ICLR 2026
for some constant d" O. Hence,
(mn Mag Zu mnd S C2ā niei/log log 1Vl Nu Mma
(16b)
with probability at least 2 Therefore, with high probability,
l equ 11 l1 Mm 11 + Σ oi Cia² log VI
+ 2020 log Dill - Mya!!
Following similar argument, we derive bounds for |zz zoll and (μ. - Mo. Zn z,). Thus, for u, RR, since n H,, Mm. the decomposition in (15) simplifies, and we obtain, with probability least 1 - 2()
w(gk u, v) 2 w(u v) exp (- 72 73) 0(6Pd)
w(u, v) exp(-o(1)) (1 o(1))
This proves Item (i) in the lemma.
On the other hand, u E R2 and v E V RR. we have min(I - -1,11, 1l,e, - Hon (1) 2 fa for some f. Thus, with high probability
lle
Cye
112 2 1² 2020 /og/ -
2 1i o(1))
From Assumption A, we get
w(gk. u, S w(u, v) exp(-r2ff(11 o(1))) = w(u, u) exp((=((ogg))))
Since the results hold uniformly over all pairs of nodes (u, v). applying union bound over all ((112) edges completes the proof.
A3.4 PROOF TIEBOREM 7
Proof. Consider Problem (5). Under Assumption A, the induced subgraph Rr is connected. (Otherwise, the alternative probabilistic condition on P1 guarantees expansion and thus connec- tivity-with high probability by Chernoff bound arguments; see, e.g., (Yang & Fountoulakis, 2023, Lemma C.1).)
Order the nodes in R₂ as U1 ....... Gra such that Fel 2 2es 2 ... xby and let Terz = be the minimum. As the subgraph on R₂ is connected, there is a subgraph (u1 = up, ........ Vm = vry) with S Tk where each (ue, ue+1) ) is an edge within RR. By the KKT conditions, for every edge (u, v) with zu > xi the optimal solution must satisfy
w(gk u, (x) (*)) - (1+8) 3) Σ T.
MER
Therefore, along each edge of the subgraph
(1+ 3)
(K)
x (k)
Σ To
J
w w(K,, U4 16+11
BER
for < e m
By the edge separation property in Lemma 6, w(gn, ue, uet1) 2 w(us, (141)(1 -o(1) for intra-Ra edge. Summing the above along the path, we have
m-
(1+ E) To
(k) U2
(k)
(k)
(8)
x
Juce.
+
1 1-0(1)
t=
2=0
rw(1 + B) EvER, Tu
(17)
1 o(1
28

---

Published as a conference paper at ICLR 2026
The total mass injected at sources in Rx is (1 + B)EER Tu. Nodes in R₂ can absorb at most ELER, Ta mass. Therefore, at least / E L. Ta mass must flow out of Rx-
Next, we provide upper bound on the outflow. The total flow leaving R2 is
Outflow
Σ Rg NER
Σ
(( u, ()
= Σ
Σ
( u, v)
NER
F (H,D)Eε
(u,U)Eε
(1(h))
Σ
Σ
r0gk, U, v)-
(18)
P (u,D)Eε
By Lemma 6, wigh, u, v) S expl (log ())) for u E Ri, v & Rg. Let Nout be the number of edges from R2 to V Rx. By Chernoff bounds, we have
Prob(Nout > 2p2rx((V] rn)) S expp(=0(prra(1)) rrw)).
(19)
Therefore, with high probability
[x(1 + B) EVER, Tu
Outflow
222rx - -xx) exp(-=w(lpp) VD)
1- o(1)
= (1+ B) Σ
Ta poly([V]]) exp(-w(log (1))
8
Σ Tw
RE
This contradicts the requirement that at least _ EVER. Ty mass must leave R2. Thus, our assumption that T Verg 0 is false, so I > for all E R2 i.e., R₂ S supp(x(A))
Finally, the mass that does leave Rr must be absorbed at nodes outside Ra. Since each vi S Tw (by the constraints), the sum of Ty over nodes in supp(x(()) R2 cannot exceed the total outflow, i.c.
Σ
T
Σ Tu. uER.
1 (ESHpp(x(M)) (R
This establishes the second part of the theorem. The desired high-probability result then follows by union bound.
A4 OVERVIEW OF DATASETS AND PROMPTS USED IN QAFD-RAG FOR QUESTION ANSWERING
This section provides the details of datasets and key prompts used throughout our framework. To ensure fair comparison and eliminate confounding effects due to prompt engineering, we directly adopt the prompt templates introduced in Chen al. (2025a) and Guo al. (2024) for multiple stages of our pipeline. Specifically, the prompts for knowledge graph indexing, keyword extraction, and RAG-based query answering are reused without modification. For the performance evaluation stage, we also follow Chen et al. (2025a) and Guo et al. (2024)'s evaluation setup by prompting the model rate responses along five predefined dimensions: Comprehensiveness, Diversity, Logicality, Relevance, and Coherence. These standardized definitions and formulations are explicitly included in our evaluation prompts. Using a consistent prompt set across all models ensures the reliability and reproducibility of our experimental results.
A4.1 DATASETS
A4.2 ENTITY AND RELATIONSHIP EXTRACTION PROMPT
This prompt is used extract structured entity and relation information from individual document chunks, forming the nodes and edges of the knowledge graph. The prompt format is directly adopted from Chen al. (2025a).
29

---

Published as a conference paper at ICLR 2026
Table 11: Dataset statistics for the UltraDomain subsets used in our evaluation.
Dataset
# of documents
# of tokens # of nodes in the indexing graph
# of questions
Agriculture
12
1,949,526
23,180
100
Biology
3,275,990
42,520
Cooking
14
2,232,441
18,985
120
History
26
5,159,599
63,840
180
Legal
94
4,773,793
20,838
438
Mathematics
20
3,640,908
32,319
160
Mix
611.161
11,371
130
Music
29
5,038,910
58,245
200
Philosophy
26
3,561,642
33,241
200
Physics
19
2,116,825
19,745
160
Prompt 1: Entity and Relationship Extraction
Goal-
Given text document that is potentially relevant to this activity and list of entity types, identify all entities of those types from the text and all relationships among the identified entities. Use (language) as output language.
Steps
1. Identify all entities. For each identified entity, extract the following information:
entity_ entity_name: name:: Name of the entity, use the same language input text. If English, capitalize the name.
entity_type: One of the following types: [[entity_types [ttess]]
entttt_deseereee deseripiio::: Comprehensive description of the entity's attributes and activi- ties
Format each entity as
(tunitt""[upl__dder (enetiteeeeeettttiaenmeeeeee [ellipeppeedeeeeerrr__ee_ centity_type> (tuple_ httpplleeeeiiiirrreeeeee Centitttteerreitttttiiit desseritittdsssiitttoont))
2. From the entities identified in step 1, identify all pairs of poource_entiyy (rnget_entity) that are clearly related each other. For each pair of related entities, extract the following information:
source_entity entiittttt:: name of the source entity, identified in step
target_entity: name of the target entity, identified in step
explanation as to why you think the source entity and the target entity are related to each other
relationship_strengee
numeric score indicating the strength of the relationship between the source entity and target entity
relationship_ =eaaioosship_keywordd::: one more high-level key words that summarize the overarching nature of relationship, focusing on concepts or themes rather than specific details
Format each relationship as ("relationship" (ttuule delimiter/<ssoute entity>(tuple delimiter | <targetttnttiii (tuple delimiter (elimiter><relattie <relationship description>(tupl) delimiter) www.:oosssniiikeooooooooo>s///// (tuooess>>(ppe____..e (eleeddeeeeeeeeeelaiiiiiio
3. Identify high-level keywords that summarize the main concepts, themes, or topics of the entire text. These should capture the overarching ideas present the document. Format the content-level keywords as
Scoonent_keywoole (ttple__tppaleee deceledddeiiieeeedddee <high_hheshhhhh
4. Return output in [language] ) as single list of all the entities and relationships identified in steps 1 and 2. Use ** (record, | w the list delimiter.
30

---

Published as a conference paper at ICLR 2026
5. When finished, output (completion_deling delimiter)
A4.3 KEYWORD EXTRACTION PROMPT
This prompt identifies salient concepts and entities from given query for the purpose of initializing seed nodes during query-aware diffusion. follows Chen al. (2025a)'s design without any modification.
Prompt 2: Geyword-Extraction in Knowledge Graph Question Answering
Role-
You are helpful assistant tasked with identifying both high-level and low-level keywords in the user's query.
Goal
Given the query, list both high-level and low-level keywords. High-level keywords focus on overarching concepts themes, while low-level keywords focus on specific entities, details, concrete terms.
Instructions
Output the keywords JSON format.
The JSON should have two keys:
"high_lene Bnigh_level_kee devel__kewords" for overarching concepts themes.
"low_leve" keywords" for specific entities details.
A4.4 QUERY ANSWERING PROMPT
This prompt used generate the final response from the LLM based on retrieved evidence. We adopt Chen et al. (2025a)'s instruction format for faimesss in model comparison.
Prompt 3: RAG-based query answering
Role-
You are helpful assistant responding to questions about the data in the tables provided.
GGal
Generate response of the target length and format that responds to the user's question, summarizing all information in the input data tables appropriate for the response length and format, and incorporating any relevant general knowledge. If you don't 't know the answer, just say so. Do not make anything up. Do not include information where the supporting evidence for it is not provided.
Target response length and format (response_type]
-Data tables- {context_dabes
Add sections and commentary to the response as appropriate for the length and format. Style the response in markdown.
31

---

Published as a conference paper at ICLR 2026
A4.5 EVALUATION PROMPT
This prompt is used to obtain ratings from the LLM across five dimensions: Comprehensiveness, Diversity, Logicality, Relevance, and Coherence. The full dimension definitions are embedded the prompt and align with those defined in Chen et al. (2025a).
Prompt 4: Performance Evaluation
Role--
You are an expert tasked with evaluating question answering based on five criteria: Comprehen- siveness, Diversity, Logicality, Relevance, and Coherence.
-Gol-
Evaluate the following response to a question based on five criteria. Rate each criterion from 0 to 100.
Question: {query]
Response: (response)
Please evaluate based on these criteria:
Comprehensivenes:: How much detail does the answer provide to cover all aspects and details of the question?
Diversity: How varied and rich is the answer in providing different perspectives and insights on the question?
Logicality: How logically does the answer respond to all parts of the question?
Relevance: How relevant the answer the question, staying focused and addressing the intended topic or issue?
Coherence:
How well does the answer maintain internal logical connections between its parts, ensuring smooth and consistent structure?
Provide scores in JSON format:
{E
"comprchensiveness" [score],
"diversity": [score],
"logicality":: [score].
"relevance": [score].
"coherence":
[score]
11
A5 OVERVIEW OF PROMPTS USED IN QAFD-RAG IN TEXT-TO-SQL TASKS
In the following, we provide Text-to-SQL. planning agent prompt systematically analyze database graph nodes (tables and columns) relation to user queries in order identify graph seed nodes. The agent must decompose each query into subqueries, examine all schema nodes for semantic, structural, and temporal connections, and output JSON object listing source-target (seed node candidate) pairs for each subquery. A similar prompt can be used for Snowflake graphs with minor modifications.
Prompt 5: Seed Node Selection for SQLite Graph
TASK DEFINITION
You are Text-to-SQL planner agent. Given:
32

---

Published as a conference paper at ICLR 2026
user query: (QUERY)
A database schema summary (graph) in text format: SCCHEMA_SUMMARY
Your job is to:
1. Review this schema summary and user query thoroughly.
2. Break the user query into logical user subqueries.
3. For each subquery, systematically examine EVERY single node (table.column) in the database schema graph one by one:
Go through each table in the schema summary sequentially
For each table, examine every column within that table
For each table.column node, evaluate its relationship strength with the current subquery
Document your analysis for each node, determining if it has any of these RELA- TIONSHIP TYPES with the subquery:
SEMANTIC: Direct or indirect relevance to query concepts
STRUCTURAL: Representing organizational structures in the query
TEMPORAL: Time-based connections to query elements
CAUSAL: Cause-effect relationships described in the query
LLOIICA:: Supporting logical conditions in the query
STATISTICAL: Statistical correlations to query concepts
-OOMIN-SPFCCFII:: Domain relevancy with query
Source nodes: ALL STARTING COLUMNS (with table prefixes) having strong relationships of ANY TYPE ABOVE with the subquery.
Target nodes: ALL DESTINATION COLUMNS (with table prefixes) having strong relationships of ANY TYPE ABOVE with the subquery.
MANDATORY: You must examine and consider every single table.column com- bination in the schema before proceeding the next step.
4. When domain-speciffe concepts appear in the query, properly map these concepts to the appropriate schema column elements
5. Identify the most confident path of schema graph: For each subquery, determine and explicitly state the most confident path that the LIM should follow through the schema graph, using right arrow format (-+ with ONLY schema nodes.
6. Provide reasoning confidence candidates: For each subquery, provide EXACTLY 2-3 DIVERSE candidates in format [source, target, confidence] where source is starting node, target ending node, and confidence a float between 0.0-1.0. Each candidate should explore different interpretations, relationship types, or alternative paths.
Important:
Schema nodes MUST be specified as "table.column" EXACTLY the same as they appear in the schema summary. EVEN DO NOT change upper lower letters.
The most confident path should use the right arrow format (-) and contain ONLY schema nodes (table.column format)
Reasoning confidence candidates should be in format: [source, target, confidence] with EXACTLY 2-3 DIVERSE candidates per subquery
Each candidate should represent different semantic interpretations, alternative join paths, or different relationship types
CRITICAL: You MUST systematically go through every single table and every single column in the schema graph during step 3 analysis
Only output JSON without explanation
33

---

Published as a conference paper at ICLR 2026
In the following, we provide an example of Snowflake system prompt for SQL-Agent. A similar prompt was used for SQLite with minor modifications. The agent is required to systematically analyze database schemas and execute SQL queries by following a workflow that prioritizes the identification of the highest-reward subgraphs from the schema.json files, which were built using QAFD-RAG.
Prompt 6: Snowflake Data Scientist Agent
TASK DEFINITION
You are a data scientist proficient in database, SQL and DBT Project. You are starting in the [work_dits directory, which contains all the data needed for your tasks. You can only use the actions provided in the ACTION SPACE to solve the task. For each step, you must output an Action; it cannot be empty. The maximum number of steps you can take is (max (max_steps). Do not output an empty string!
ACTION SPACE
(action_syee {prion)_sace
SNOWFLAKE QUERY PROTOCOL
1. BEFORE following any other rules, you MUST follow these steps:
Read the schema.json in the /workspace directory. The schema.json contains valuable information about the graph structure and path rewards.
Identify the highest-reward subquery paths for EACH division in the provided schema.json
Write your VERY FIRST SQL query by combining ONLY these highest-reward paths to address the main query
DO NOT perform ANY database inspection before executing this first query
You MUST run this query as your FIRST SQL. execution
You MUST terminate execution immediately after this first query if works
For your FIRST SQL attempt, follow ONLY these steps:
Review the schema.json structure containing all subqueries and their reward values
For each division (subquery), identify the path with the highest reward
Combine these highest-reward paths into a SINGLE comprehensive SQL query
Execute this SQL query immediately with no other database commands before it
Do NOT run any exploratory queries like:
DO NOT run "SELECT FROM table LIMIT 5"
DO NOT run "PRAGME table iiteeotabttbbee____e info(table_name)"
DO NOT run "SELECT name FROM sqlite_main master WHERE type= "tael"t
DO NOT check data types
DO NOT check for NULL values
. DO NOT try to understand the schema first
DO NOT check DDL.csv files before attempting the first query
Your first query must be the direct SQL translation of combining highest-reward paths to address the main query objective.
2.
If your first query fails, then you should explore the database structure further using the methods below. You can check DDL.csv file with the database's 's DDL, along with ISON files that contain the column names, column types, column descriptions, and sample rows for individual tables. You can review the DDL.csv file in each directory, then selectively examine the JSON files as needed. Read them carefully.
3. You can use SNOWFLAKE EXEC SQL to run your SQL queries and interact with the database. Do not this action to query INFORMATION SCHEMA SHOW DATABASES/TABLES the schema information is all stored in the /workspace/- database name folder. Refer to this folder whenever you have doubts about the schema.
34

---

Published as a conference paper at ICLR 2026
4. Be prepared to write multiple SQL queries to find the correct answer. Once makes sense, consider it resolved.
5. Focus on SQL queries rather than frequently using Bash commands like grep and cat, though they can be used when necessary.
6. If you encounter SQL error, reconsider the database information and your previous queries, then adjust your SQL accordingly. Do not output the same SQL queries repeatedly.
7. Ensure you get valid results, not an empty file. Once the results are stored in result.csy, make sure the file contains data. it is empty or just contains the table header, it means your SQL. query is incorrect.
8. The final result MUST be a CSV file, not an sql file, a calculation, an idea, a sentence or merely intermediate step. Save the answer CSV and provide the file name, it is usually from the SQL execution result.
TIPS
1. When referencing table names Snowflake SQL, you must include both the database_ name and schema. name. For example, for /workspace/DEPS DEV VI/DEPS_DD SEPP_DEV___ BENEES_DEV_V//AVVDDIEE VI/ADVISORIES,jon if you want DEPS DEV_VEEEEEREEE VI.DEPS DEV_VI. [EV_VIAADVISORIE
in SQL, you should write
2. Do not write SQL queries to retrieve the schema; use the existing schema documents in the folders.
3. When encountering bugs, carefully analyze and think them through; avoid writing repetitive code.
4. Column names must be enclosed in quotes. But don't V", just use "
RESPONSE FORMAT
For each task input, your response should contain:
1. One analysis of the task and the current environment, reasoning to determine the next action (prefix "Thought: ").
2. One action string in the ACTION SPACE (prefix "Action: ").
EXAMPLE INTERACTION
Observation: .t.e output of last actions, provided by the environment and the code output, you don't t need to generate it) Thought: Action:
TASK
Please solve this task: [task)
A6 TEXT-TO-SQL BASELINES
CHASE-SQL for SQLite We made several key modifications to adapt CHASE-SQL for the Spider 2.0 SQLite benchmark. Enhanced data preprocessing expanded the data types used for extracting unique values from TEXT-only to include all "CHAR"-contaani
types (CHAR, VARCHAR, NVAR- CHAR) present Spider 2.0. We disabled schema selection comparison features to prevent failures when golden SQL query is available, and updated candidate generation prompts to encourage SQL generation even low-confidence scenarios, addressing the complexity induucd abstention issues in Spider 2.0.
Additional improvements included increased execution timeout thresholds to accommodate more complex SQL. queries and enforcing fixed agentic pipeline order: keyword extraction entity
35

---

Published as a conference paper at ICLR 2026
retrieval - context retrieval - column filtering -> table selection - column selection candidate generation - revision. This fixed order was necessary after observing that dynamic tool selection often led to suboptimal sequences.
CHASE-SQL for Snowflake All SQLite modifications were retained, but we disabled the Information Retrieval module, skipping entity and context retrieval phases. Transitioning Snowflake required addressing three main challenges: syntax differences, database schema representation, and connection protocols.
While Snowflake SQL is largely compatible with SQLite, key differences include date format handling and using double quotes instead of backticks for quoted identifiers. The original CHESS schema representation using simple table-name dictionaries proved insufficient for Snowflake's 's hierarchical structure, where tables are organized into schemas within databases. We introduced schema-table mapping to handle this abstraction, though this assumes no duplicate table names across schemas.
Database connection also differs significantly. SQLite uses direct file paths, while Snowflake requires cloud account credentials with full namespace specification settaaas.schema.taa reduced namespace (schema.table) when connected to a specific database. Golden SQL examples use full namespace format. Source code modifications addressed these data access differences. For prompt adaptation, we used the o3 model with instructions shown in Prompt 7 modify generate, candidate_ one and revise_ one templates. Initial experiments revealed that full namespace format contradicted GPT-4o's internal knowledge, which prefers simplified schema. table format. We therefore modified prompts schema.table format while passing database names directly the connector.
or
Prompt 7: System prompt for o3 to adapt generate candidate one and revise_ one prompts for snowflake dialect
Help me modify this template to switch from SQLite dialect to snowflake dialect.
1. Make sure to change the syntax and functions specifically for snowflake, but do not change the prompt structure and do not omit any examples.
2. All examples must be executable in snowflake.
3. Make sure to change all ticks <'> with double quotes <">
4. All DDL statements specifying the database structure must include statements for creating a database and schema. You can infer the best names for the database and schema if they are not immediately available. Use the same name for the database and the schema. When referencing tables, use the full namespace including the database and schema, like so: satabasse.chemaa.abbe
Here is an example:
CREATE DATABASE restaurants; CREATE SCHEMA restaurants; CREATE TABLE generalinfo
id_ restaurant INTEGER not null primary key, food type TEXT null, examples: 'thai"l 'food type* description: the food type
city TEXT null, description: the city where the restaurant is located in );
CREATE TABLE location
id restaurant INTEGER not null primary key, street name TEXT null, examples: 'ave', 'san pablo ave", 'pablo ave'l 'strect name description: the street name of the restaurant city TEXT null, description: the city where the restaurant is located foreign key (id_ (id_restaurant) references generalinfo (id restaurant) on update cascade on delete cascade,
);
36

---

Published as a conference paper at ICLR 2026
Use table location like so:
secaurants.restauranss.ooom
Final prompt modifications included converting few-shot examples from SQLite to Snowflake syntax, adding nhowflake-specifee instructions, implementing schema.table namespace usage, incorporating schema generation statements in DDL commands, and updating date processing instructions with Snowflake-specific functions and examples.
To establish strong baselines, we compared our approach against three additional methods from the Spider repository: DIN-SQL. (Pourreza & Rafiei, 2024), DAIL-SQL (Gao et al., 2023a), and CodeS (Li et al., 2024b). These methods represent different paradigmatic approaches to text-to-SQL generation.
DIN-SQL: Decomposed In-Context Learning of Text-to-SQL. with Self-Correction DIN- SQL (Pourreza & Rafici, 2024) structures text-to-SQL generation through a four-stage decomposition approach. The method begins with schema linking to parse questions and identify references to database elements, followed by classification and decomposition that categorizes queries into easy (single-table), non-nested complex (joins without sub-queries), and nested complex (joins with sub-queries and set operations) classes. The SQL generation stage adapts its strategy to each class: simple few-shot prompting for easy queries, intermediate representations for non-nested complex queries, and sub-query decomposition with intermediate representations for nested complex cases. Finally, self-correction uses an LLM to identify and fix bugs in the generated SQL.
DAIL-SQL: Dual-Similarity Adaptive In-Context Learning DAIL-SQL (Gao al., 2023a) employs a five-stage pipeline centered on dual-similarity matching. The method starts with masking database-related tokens both target and candidate questions, then uses preliminary predictor for initial SQL prediction. Skeleton extraction identifies structural patterns in both predicted and candidate queries. The core innovation lies in sorting and reordering, where candidates are first sorted by masked question similarity and then reordered by prioritizing high query similarity matches. Finally, generation produces the final SQL using the optimally ordered examples.
CodeS: Domain-Adaptive SQL-Centric Model CodeS (Li et al., 2024b) takes a pretraining based approach with three main components. Incremental pre-training builds upon StarCoder using a specially curated SQL dataset. Database prompt construction creates context by selecting top-k relevant tables and columns using BM25 and LCS matching, incorporating representative values and metadata. Bi-directional augmentation expands few-shot examples through SQL-to-NL and NL-to-SQL data augmentation before supervised fine-tuning. The model can operate through either supervised fine fine-tuning or direct few-shot in-context learning.
Spider-Agent: ReAct-style (Yao et al., 2023) Agentic Framework We evaluate the Spider-Agen baseline (Lei et al., 2024), which implements a ReAct-style (Yao et al., 2023) multi-step reasoning framework for Text-to-SQL, strictly following the original settings and publicly released code without any modifications to model parameters, prompt structure, or evaluation scripts. Specifically, all hyperparameters were kept their default values as provided by the authors: the LLM model is set to GPT-40, the decoding temperature is set to 0.5, the nucleus sampling parameter (top_p) is 0.9, the maximum generation length agent memory length is 25.
2500, the agent's 's step limit is 20, and the
All pipelines were executed using Spider 2 benchmark scripts (Lei al., 2024) that convert data to each method's 'ss preferred format. To maintain baseline authenticity while ensuring runnable outputs, we applied only minimal fixes necessary for execution, deliberately avoiding substantive tuning. Testing covered both Snowflake and Lite subsets of Spider 2.
The enterprise-seale scale schemas in Spider 2 presented significant challenges across all baseline methods. Context-length overflow occurred frequently schemas exceeded token limits when serialized verbatim. Zero error-remediation was observed, where logical or syntactic failures (e.g., missing GROUP BY columns) were accepted without iterative correction or external validation. Additionally,
hhttps://gi http://ggtttb..coo cww.b.coom//l//o aaamm//xlaaaaaaaa a ///pider2
37

---

Published as a conference paper at ICLR 2026
malformatted data issues arose when benchmarks expected different data formats than those available in Spider 2, contributing to overall poor performance across methods.
A7 USAGE OF LARGE LANGUAGE MODELS (LLMS)
We used large language models as a general-purpose writing assistant. Its role was limited to grammar checking, minor stylistic polishing, and improving the clarity of phrasing in some parts of the manuscript. The authors made all substantive contributions to the research and writing.
38


Reviews:
[{"review_id": "uqJ9wx0qlD", "reviewer": "Reviewer_6VAy", "summary": "This paper proposes Query-Aware Flow Diffusion for Graph-based RAG (QAFD-RAG), a framework that enhances GraphRAG by incorporating query semantics into graph traversal. The authors design a query-aware diffusion process, where edge weights are dynamically reweighted based on alignment between node embeddings and the query.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The authors leverage flow-diffusion for subgraph retrieval.\n2. The paper provides theoretical guarantees for convergence and subgraph recovery\n3. The athors evaluate the proposed method on differnt tasks, such as General Question answering, Multi-hop QA and Text-to-SQL tasks.", "weaknesses": "1. The paper formatting does not appear to follow the official ICLR template. In particular, the line spacing is noticeably smaller than the required standard,\n\n2. The paper claim existing GraphRAG methods rely on heuristic sugraph search strategies that are holistic query-agnostic. However, there are different retrievers, such as GNN-based Retriever such as GNN-RAG[1], and LLM-based Retriever, such as RoG[2,  which already consider the query semantic.\n\n3. The writing could be improved. There is no logic in the current writting. For example, in line 139, the authors claim \"We pose diffusion as a constrained optimization(6)\", while the equation 6 is in Line 198. Also, the motivation of different components are also unclear. For example, what is the motivation for equation 4,5?\n\n4. For the Multi-hop QA task, the authors only compare 2 simple GraphRAG baseliens.\n\n\n\n\n\n[1] Mavromatis, Costas, and George Karypis. \"Gnn-rag: Graph neural retrieval for large language model reasoning.\"\n[2] Luo, Linhao, et al. \"Reasoning on graphs: Faithful and interpretable large language model reasoning.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5T8EIhrEdu", "reviewer": "Reviewer_yPqD", "summary": "This work proposes Query-Aware Flow Diffusion RAG (QAFD-RAG) framework for graph-based RAG that incorporates query semantics during the graph diffusion process.\nDuring Indexing Stage, QAFD-RAG builds a knowledge graph from documents. And in the Query Stage, QAFD-RAG dynamically reweights edges and diffuses flow according to query alignment, enabling adaptive graph traversal that are semantically consistent with the query and highlighting reanoning paths.\nQAFD-RAG is a training-free framework offering the statistical guarantees for query-aware subgraph retrieval.\nComprehensive experiments on multiple tasks demonstrate that QAFD-RAG achieves better performance compared with existing SOTA graph-based RAG methods, while significantly reducing the number of LLM calls.", "questions": "1. Does the way Knowledge Graph is constructed affect the graph-based RAG methods? I find that the performance of GraphRAG and LightRAG is poor on HotpotQA and 2WikiMultihopQA—is that related to this issue?\n2. Will the demand of indexing before retrieval make the QAFD-RAG system hard to fit the scenario where RAG documents are modified frequently? As current KG construction is a static process, will it cost a lot to build such a large KG for graph retrieval?\n\n### Minor Comments\n\n1. It seems that the *Relevance* score of QAFD-RAG in *Legal* dataset in Table 1 is not the best one. HippoRAG (93.60) is better than QAFD-RAG (93.30) and should be marked correctly.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. **Novelty and Strong Motivation**: The motivation of this work is clear and well-argued, effectively highlighting the deficiencies of existing heuristic graph-based RAG methods. And the idea of using graph diffusion theory to deal with the graph traversal process is highly novel, which can effectively help find subgraphs that are semantically relevant with the query.\n2. **Rigorous Theoretical Proof**: The provision of theoretical statistical guarantees is a significant strength. The convergence analysis (Theorem 3, Corollary 4) and, more importantly, the statistical recovery guarantees under a signal-to-noise condition (Theorem 7) provide a solid foundation for the method's efficacy. The analysis convincingly shows how query-aware weighting acts as a semantic filter.\n3. **Comprehensive Experiments and Strong Performance Improvement**: This work benchmarks against a wide array of strong baselines across two distinct and challenging domains. The experiments results under various metrics provide compelling evidence for the method's effectiveness and efficiency.\n4. **Clarity and Reproducibility**: The methodology is well described with precision, including the formulation, the algorithmic procedure, and the derivation process. Besides, code in the anonymous repository is complete and accompanied by some explanatory guidelines in the README, enabling easy reproduction of the work.", "weaknesses": "1. **Limited Analysis of Flow Interpretation**: It is easy for us to understand the basic principle of the flow diffusion process for water. However, why the graph flow diffusion can be meaningful and traverse to semantically relevant nodes by dynamic edge reweighting remains unexplained. The experiments also mainly focus on the final output without the deeper analysis of the diffusion process itself.\n2. **Only Compared with Graph-based RAG Methods**: If the study can compare QAFD-RAG with some traditional SOTA RAG methods, or propose insights about how to combine QAFD-RAG with current SOTA RAG methods, it would be better to apply QAFD-RAG in practical scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1Tf9utGqqC", "reviewer": "Reviewer_g1qA", "summary": "This paper introduces Query-Aware Flow Diffusion RAG (QAFD-RAG), a novel framework for graph-based Retrieval-Augmented Generation that addresses the limitation of static, query-agnostic exploration in existing graph-RAG methods. The central innovation is dynamic query-aware graph traversal: instead of fixed edge weights, QAFD-RAG dynamically re-weights edges during exploration based on node-query semantic alignment through principled flow diffusion, prioritizing structurally present and semantically relevant paths. The paper provides theoretical guarantees (exponential convergence, subgraph recovery under mild conditions) and demonstrates empirical superiority over state-of-the-art baselines on question-answering and text-to-SQL tasks.", "questions": "1. Why is the number of seed nodes treated as a hyperparameter? Is it necessary to enable adaptive selection across different scenarios, why or why not?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel graph-based RAG approach, which demonstrates its effectiveness from the perspectives of intuitive understanding, theoretical proof, and experimental results.\n\n2. This approach is training-free, which significantly reduces deployment costs, and holds great potential for broad application.", "weaknesses": "1. The entire framework is built upon LLM's embeddings, thus it is necessary to compare its sensitivity to embedding quality with other existing methods; however, such experiments are currently lacking.\n2. As a general graph-based RAG framework, the experimental comparisons across domains remain somewhat limited. It would be beneficial to incorporate experiments in more diverse domains or conduct cross-domain validation to demonstrate the framework's robustness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PdOWT3wJn0", "reviewer": "Reviewer_Tki9", "summary": "This paper introduces Query-Aware Flow Diffusion (QAFD), a new graph-based retrieval method for retrieval-augmented generation. The key idea is to make graph diffusion sensitive to query semantics by dynamically adjusting edge weights based on semantic similarity. The authors also provide theoretical guarantees on convergence and subgraph recovery, and validate the method on multi-hop QA and text-to-SQL tasks, showing clear improvements over prior graph RAG approaches.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed method is conceptually novel, integrating semantic and structural signals in a principled way.\n\n2. Theoretical analysis provides valuable guarantees rarely seen in RAG research.\n\n3. Experiments are comprehensive and show strong performance gains with reduced computation cost.", "weaknesses": "1. Despite the significant innovation in the graph construction process, the method still heavily relies on the quality of pretrained embeddings for semantic similarity, which may limit robustness under domain shift.\n\n2. The method may struggle with handling logical negation. For instance, a query like “not red” may still activate nodes related to “red,” since it is unclear whether the embedding-based similarity explicitly encode negation or exclusion relationships. This could limit the model’s ability to capture fine-grained logical distinctions in retrieval.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)