Diffusing Query Relevance over a Learned Chunk Graph for Multi-Hop Retrieval

Retrieval-augmented generation (RAG) means letting a language model answer from documents fetched out of an external collection rather than from memory alone. It works well when the answer sits in one passage. It fails when the answer needs two or three passages, the later of which look nothing like the question. Take "Where was the founder of the company that made X born?" The passage about the birthplace shares almost no words or meaning with the question, so a similarity search never ranks it highly.

Clustering research faces a closely related problem. Direct pairwise similarities between points are sparse and noisy. The fix that works there is graph diffusion: let similarity spread along chains of neighbors, so points that are only indirectly connected still end up close together. We propose to apply this idea at retrieval time. We would build one graph over text chunks, with edges from embedding similarity and from shared named entities, and weight those edges with a local similarity-learning step taken from the clustering literature. We would then spread the query's relevance scores across this graph with a heat kernel and retrieve the chunks that end up with the highest scores. Building the index needs no language-model calls and no summary trees. The question is whether this cheap mechanism recovers the passages for later reasoning steps as well as the expensive indexing pipelines do.

Core Claim

Flat retrieval misses later reasoning steps because the needed passages are linked to the question only through intermediate passages. Diffusion over an affinity graph is a mechanism designed to recover that kind of indirect link. The supporting evidence comes from clustering: in Local-Sample-Weighted Clustering Ensemble with High-Order Graph Diffusion (LSWCEH), a sample-weighted clustering ensemble, the heat-kernel diffusion component alone accounts for an 11.6% accuracy gain and a 17.6% NMI gain over the same model without diffusion.

We claim three things. First, diffusing query relevance over a single fused graph of similarity and entity edges raises recall of the passages for every reasoning step on multi-hop QA, and answer F1 with it. Second, it does so while staying competitive with tree-based indexing that relies on summaries, at a small fraction of the indexing cost. Third, the fusion has to happen at the level of edge weights. Running each graph separately and adding the scores afterwards should not be enough.

The third claim runs directly against a reported negative result. SiReRAG builds one tree from semantic similarity and another from entity relatedness. It reports that the two views overlap only about 50–68%. It also reports that letting the trees interact during construction hurt performance, so it kept them separate and merged them only into a pooled index roughly three times larger. Our reading is that the interaction hurt because it contaminated the language-model summaries, which mix whatever the clusters contain. Edge-level fusion never summarizes anything. We test this reading explicitly rather than assume it.

Method

Each corpus is split into passages, which we call chunks. Each chunk gets a dense embedding and a set of named entities from an off-the-shelf named-entity tagger, with no language model involved. Two candidate edge sets are formed. The first is the $k$ nearest neighbors in embedding space. The second links chunks that share a named entity, with weights reduced for very frequent entities.

We then adapt the local graph learning step of FDC-LGL. That method learns a data-dependent similarity for each point, limited to its second-order neighbors (neighbors of neighbors), inside a fast discrete normalized-cut clustering method. We use the step to reweight and prune the union of the two candidate edge sets, which gives a single sparse affinity matrix $W$. From $W$ we form the normalized graph Laplacian $L = I - D^{-1/2} W D^{-1/2}$, where $D$ is the diagonal matrix of node degrees.

At query time, let $q$ be the vector of query–chunk cosine similarities, truncated to the top $m$ chunks and set to zero elsewhere. The diffused score is

$$s = \exp(-tL)\, q,$$

where $t$ is the diffusion time and controls how many hops relevance can travel. We compute it with a truncated Taylor or Chebyshev expansion, so the cost is a few sparse matrix–vector products. Chunks are ranked by $(1-\beta)\, q + \beta\, s$, where $\beta$ trades direct similarity against diffused relevance. The top $k$ chunks go to the generator.

The clustering literature notes that diffusion step counts are usually fixed by heuristic, often $\theta = 3$. We therefore report full sensitivity curves over $t$ and $\beta$ on a development split rather than a single tuned value.

The clustering direction also supplies a diagnostic that is independent of the generator. For each question we know its gold supporting passages. A good graph should place the passages of one question in the same diffused neighborhood. We cluster the diffused affinity matrix $\exp(-tL)$ and measure how often the supporting passages of a question fall in one cluster, using pairwise co-membership rates together with ARI and NMI against question groupings. We then test whether this clustering-quality score predicts retrieval gains across graph variants. If it does, graph quality can be tuned offline without running the generator.

Relation to Prior Work

Three systems bring clustering into RAG at indexing time.

RAPTOR reduces embedding dimension with UMAP, soft-clusters with Gaussian mixtures, and recursively summarizes the clusters into a tree. It motivates the claim that flat chunks are too fine-grained: over 57% of the nodes it retrieved on NarrativeQA were summary nodes. Its summaries cost language-model calls and carry roughly a 4% hallucination rate. It also queries a collapsed pool of nodes that discards the graph structure.

GraphRAG has a language model extract a knowledge graph, partitions it with Leiden community detection, and summarizes the communities. It targets corpus-wide summarization questions, where it wins 72–83% of comprehensiveness judgments against vector RAG, but it pays a large extraction cost.

SiReRAG, discussed above, supplies both our strongest baseline and the negative result we must explain.

All three turn clusters into text summaries. We turn the affinity graph into a retrieval operator and summarize nothing.

EDC²-RAG clusters only the passages already retrieved, using fixed SimCSE embeddings, and compresses each cluster with a small language model. It cannot recover a passage the first retriever missed, which is precisely the failure we target. The two methods are complementary, and we test stacking them.

Recurrent Meta-Structure shows that several relation types in a heterogeneous network can be combined into one robust similarity measure. It motivates our bet that similarity edges and entity edges can share one graph.

Research Program

The work has three stages.

The first stage builds the fused graph for the corpora of MuSiQue-Ans, 2WikiMultiHopQA and HotpotQA. We record construction time, memory and the number of language-model tokens, which should be zero.

The second stage runs retrieval and generation with a fixed open-weight generator and a fixed retrieval budget $k$. This holds the comparison constant across all retrievers.

The third stage runs the graph-quality diagnostic. It asks whether supporting passages in the same diffused cluster predict recall gains.

Throughout, we split the results by hop count (2, 3 and 4 hops), using MuSiQue's structure from MuSiQue. Diffusion should help most where more hops are needed. A gain that does not grow with hop count would suggest the method is acting as generic re-ranking and not as multi-hop bridging.

Baselines

The naive reference point is flat dense top-$k$ retrieval with the same embedding model, plus BM25. This is diffusion with $\beta = 0$, so it shares every other component with our method. On why this is a weak floor for multi-hop questions, MuSiQue reports that single-hop models drop about 30 F1 points relative to HotpotQA.

The strongest existing method is SiReRAG, which reports an average 1.9% F1 improvement over RAPTOR, HippoRAG and GraphRAG on MuSiQue, 2WikiMultiHopQA and HotpotQA. It also reports up to 7.8% when used upstream of rerankers. We found no absolute SiReRAG F1 on MuSiQue on Lacuna, so we will reproduce it. For reference, human performance on MuSiQue-Ans is 78.0 answer F1. SiReRAG gets the same generator, the same $k$ and the same embedding model. Its language-model indexing calls are reported as cost, not hidden. Beating it means either matching its answer F1 within noise at under a tenth of its indexing tokens, or exceeding it on 3- and 4-hop questions.

RAPTOR is run under the same protocol as the representative of summary trees.

The ablations isolate the key ingredients. The first compares diffusion on the fused graph with diffusion on the similarity graph alone and on the entity graph alone. The second compares the fused graph against late fusion, meaning separate diffusions whose scores are summed. This is the edge-level analogue of SiReRAG's separate silos and directly tests our explanation of its negative result. The third compares learned local edge weights against a fixed equal-weight union. The fourth compares the heat kernel with personalized PageRank on the same graph. All variants share one tuning budget on a development split, with the same grid size over $t$, $\beta$, $m$ and the neighbor count.

Why not just…?

Why not just feed everything to a long-context model? On long-context tasks, Retrieval Augmented Generation or Long-Context LLMs? finds that full-context prompting beats vanilla RAG by 7.6% with Gemini-1.5-Pro and by 13.1% with GPT-4o. The same paper's routing method comes within 0.2–2.2% of full context while cutting token cost by up to 65%. That suggests retrieval quality, not context size, is the lever worth pulling. Our multi-hop corpora far exceed any context window, so full ingestion is not an option there. We will still report a long-context oracle on per-question gold-plus-distractor sets as an upper reference.

Why not just retrieve, then cluster and compress, as EDC²-RAG does? Post-retrieval compression cannot add a passage that was never retrieved. EDC²-RAG's reported gains are strongest under heavy redundancy: +6.18 F1 on WebQ at 95% repetition. We measure supporting-passage recall before any compression. If EDC²-RAG on top of flat retrieval matches our recall-limited answer F1, the bottleneck is noise and not missing hops, and our claim fails. We also run the stacked combination.

Why not just use personalized PageRank over an entity graph, as HippoRAG does? This is the most serious threat. HippoRAG appears in the file only as one of SiReRAG's baselines, so we have no reported numbers for it. Personalized PageRank is itself a form of diffusion. If personalized PageRank on our fused graph performs as well as the heat kernel, then our contribution reduces to the fused, locally learned graph, and the kernel choice does not matter. We will report the result that way. If both kernels perform equally on an entity-only graph, the fused graph adds nothing, and the proposal is refuted.

Why not just swap UMAP and Gaussian mixtures in RAPTOR for a better clustering method such as FDC-LGL? This is the obvious combination of the two directions. We expect it to change little, because the summaries, not the cluster boundaries, carry RAPTOR's benefit. We will run it once as a control. If it closes the gap, better tree clustering is the real lever, not diffusion.

Decisive Checks

The proposal stands or falls on four results.

The first is the 3- and 4-hop recall gain over flat retrieval on MuSiQue-Ans. It must exceed the 2-hop gain, and diffusion must be the source of it: the gain must be present with $\beta > 0$ and disappear at $\beta = 0$.

The second is the comparison of fused-graph diffusion with late fusion. If the fused graph does not win, SiReRAG's case for keeping the two views separate holds and our explanation of its negative result fails.

The third is the comparison with SiReRAG on answer F1 per indexing token.

The fourth is whether the clustering diagnostic predicts which graph variants retrieve best. A clear failure on the first two checks would mean the clustering analogy does not transfer to retrieval.