Relink: Constructing Query-Driven Evidence Graph On-the-Fly for GraphRAG

AI summary

Overview

• Research area: Natural Language Processing; specifically graph-based Retrieval-Augmented Generation (GraphRAG), knowledge-graph reasoning, and multi-hop open-domain question answering.
• Technical level: Advanced. The paper assumes familiarity with knowledge graphs, retrieval-augmented generation, beam search, contrastive learning objectives (InfoNCE), and EM/F1 evaluation.
• Scope: The paper proposes Relink, a framework that abandons the "build-then-reason" GraphRAG paradigm in favor of a "reason-and-construct" paradigm, dynamically building a query-specific evidence graph for each query instead of reasoning over a static, pre-built knowledge graph.

What This Paper Is About

Current GraphRAG systems answer questions by walking over a knowledge graph that was built once, in advance, and never changes. This creates two problems: the graph is incomplete, so reasoning chains break when a needed link was never extracted, and the graph is noisy, so it contains facts that look relevant to the query but actually lead the model astray. Relink's goal is to instead construct the reasoning path at query time, pulling candidate links from both a high-precision knowledge graph and a high-recall pool of relations mined from the raw text corpus, then ranking and instantiating only what the specific query needs.

Key Contributions

1. Diagnosis of the dominant paradigm. The authors systematically analyze the prevailing "build-then-reason" paradigm used by GraphRAG methods and identify two core failure modes: knowledge-graph incompleteness (broken reasoning paths) and low signal-to-noise ratio from distractor facts (query-relevant but goal-misaligned knowledge).

2. The Relink framework. Following a "reason-and-construct" idea, Relink dynamically constructs evidence graphs by jointly evaluating explicit knowledge-graph facts and latent relations, achieving on-the-fly path repair and distractor filtering within a single ranking mechanism.

3. A heterogeneous knowledge source. Relink combines a high-precision factual knowledge graph constructed by an LLM-based extractor with a high-recall latent relation pool built from entity co-occurrences in the corpus and filtered by a Pointwise Mutual Information threshold.

4. Empirical validation. On five ODQA benchmarks, Relink outperforms leading GraphRAG baselines by an average of 5.4% in EM and 5.2% in F1, according to the paper.

Main Findings

• Best overall accuracy across five benchmarks. Relink achieves the top score on all five datasets reported in the main table. Its scores are: 2WikiMultiHopQA EM 0.628 / F1 0.722; HotpotQA EM 0.558 / F1 0.704; ConcurrentQA EM 0.505 / F1 0.596; MuSiQue-Ans EM 0.304 / F1 0.413; MuSiQue-Full EM 0.252 / F1 0.370. The strongest baseline, HippoRAG, scores 0.578 / 0.684, 0.498 / 0.647, 0.458 / 0.536, 0.254 / 0.381, and 0.190 / 0.298 respectively.

• Large gains over LLM-only and text-based retrieval. On 2WikiMultiHopQA, Relink's EM of 0.628 is described as a 115.1% relative improvement over GPT-4o (0.292). Against RAPTOR, the paper reports a relative EM gain of 18.2% on HotpotQA (0.558 vs. 0.472) and 34.5% on 2WikiMultiHopQA (0.628 vs. 0.467).

• The query-driven ranker is the most important single component. In the ablation study, replacing the trained ranker with cosine similarity over OpenAI's text-embedding-3-small embeddings causes the largest degradation: a 19.4% relative EM drop on HotpotQA (0.558 to 0.450), the biggest single drop reported in the ablation table.

• Both knowledge sources are necessary. Removing the latent relation pool (R_c, "w/o Dynamic Repair") causes a 5.7% relative EM drop on HotpotQA (0.558 to 0.526), while removing the explicit graph backbone (G_b) causes a more severe 12.9% drop (0.558 to 0.486).

• Unified alignment matters. Removing the contrastive alignment loss (L_contra) leads to a 7.2% relative EM drop on HotpotQA (0.558 to 0.518), which the authors attribute to the ranker being unable to compare facts from different sources on a common basis.

• Robustness under knowledge sparsity. In the sparsity experiment, the variant without dynamic repair sees its F1 on 2WikiMultiHopQA drop by 34.7% when 90% of edges are removed from the explicit graph, whereas full Relink maintains an F1 of 0.669 under the same 90% edge-removal condition.

• Case study on distractor facts. A qualitative example shows a static baseline misled by a highly relevant but wrong "resides in" relation, while Relink instantiates the missing "composer of" relation from text evidence and its ranker prioritizes the correct "born in" path.

Methodology in Plain English

Relink treats the pre-built knowledge graph not as the answer space but as a trusted skeleton. Alongside it, the authors build a second, noisier resource: a pool of latent relations mined from the original text corpus. This pool is created by finding entity pairs that co-occur in the corpus, keeping only pairs whose Pointwise Mutual Information exceeds a threshold, and encoding each pair's context sentence into a dense vector using a pretrained language model. The vector is taken from the last hidden state of a [MASK] token in an input template that places the sentence and the two entities in sequence.

To make these two very different kinds of evidence comparable, Relink projects each explicit triple (head, relation, tail) into the same vector space as the latent relations. Explicit triples are linearized into a text sequence and encoded by one encoder using the [CLS] token; latent relations use their pre-computed vector directly. A contrastive alignment loss (InfoNCE) pulls a factual triple's embedding toward its corresponding latent relation embedding and away from in-batch negatives.

Path construction is a beam search starting from the entities mentioned in the query. At each step, all one-hop neighbors of the current path's last entity are collected from both the explicit graph and the latent pool. Candidates go through a coarse-to-fine ranking: a lightweight trainable ranker first scores all candidates by predicted relevance to the query, then an LLM re-evaluates the top candidates with a structured prompt and returns a relevance score increment. Path scores are updated recursively as a running average, and the top-K paths survive each iteration. When a latent relation wins, the LLM is prompted with the source context sentence and the original query to generate a factual triple (head, relation, tail) — this both repairs the missing link and ensures the newly created fact fits the user's intent rather than being a generic relation from the same text. The final evidence graph, with each triple linked to its source sentence, is handed to a generator LLM together with the query.

Training is staged and alternating: the encoders are frozen while the ranker trains for one epoch on a pairwise ranking loss over (query, better path, worse path) tuples with a margin hyperparameter, then the ranker is frozen while the encoders train for one epoch on the contrastive loss. The cycle repeats until validation-set convergence. All RAG variants, including Relink, use deepseek-v3-0324 as the backbone LLM, and each method is evaluated on 500 randomly sampled questions from the test split of every dataset.

Why This Matters

Impact on research. The paper argues that the field's reliance on a single static, pre-constructed graph is a structural limitation rather than an implementation detail. By showing that dynamic, query-aware path construction beats static traversal even when 90% of the graph is deleted, it reframes robustness in GraphRAG from "build a better graph" to "build the graph the query needs." The reported ablation pattern — that generic embedding similarity is a poor substitute for a trained query-aware ranker — is a concrete finding about what actually drives performance.

Real-world applications.

• Multi-hop question answering over enterprise or scientific document collections, where an offline-extracted graph will always be missing links that a specific question requires.
• Retrieval over knowledge bases that change frequently, such as news archives or clinical literature, where pre-construction becomes stale faster than it can be rebuilt.
• Auditable assistants, since each triple in the constructed evidence graph is linked to a specific source sentence, making answers traceable to provenance.
• Domains with inherently sparse or noisy graphs, such as legal or regulatory text, where relevant-but-misleading relations are common.

Industry relevance. Any production RAG system that pays for graph construction pipelines benefits from a method that tolerates an imperfect graph, since graph quality is usually the bottleneck rather than retrieval speed. The structured evidence output also fits naturally into compliance and verification workflows where an unsourced answer is unacceptable.

Future Directions

• Cost and latency of dynamic construction. Relink invokes an LLM for fine-grained re-ranking and for instantiating latent relations at every search step. The paper does not report latency, token cost, or throughput comparisons against static baselines, so the practical overhead of the reason-and-construct paradigm is an open question.

• Scaling the latent relation pool. The pool is filtered by a PMI threshold and derived from entity co-occurrences. How the threshold affects quality, and how the approach behaves on corpora much larger or much noisier than the ones tested, is not explored in the reported content.

• Beyond open-domain QA. The evaluation covers five ODQA benchmarks. Whether the same dynamic construction helps on tasks with different output structures — summarization, fact verification, or multi-step agentic tool use — is untested.

• Interaction between graph quality and repair. The sparsity experiments remove edges synthetically. It remains open how Relink behaves on graphs whose errors are extraction mistakes rather than deletions, which is the failure mode of real pipelines.

Target Audience

Researchers and engineers working on retrieval-augmented generation, knowledge-graph reasoning, and multi-hop question answering who already understand the standard GraphRAG pipeline. It is most valuable to practitioners deciding whether to invest in expensive static graph construction, and to researchers interested in dynamic or agentic alternatives to retrieval over fixed indexes. Readers without prior exposure to knowledge graphs, beam search, or contrastive representation learning will need background reading first.

Authors’ abstract

Graph-based Retrieval-Augmented Generation (GraphRAG) mitigates hallucinations in Large Language Models (LLMs) by grounding them in structured knowledge. However, current GraphRAG methods are constrained by a prevailing \textit{build-then-reason} paradigm, which relies on a static, pre-constructed Knowledge Graph (KG). This paradigm faces two critical challenges. First, the KG's inherent incompleteness often breaks reasoning paths. Second, the graph's low signal-to-noise ratio introduces distractor facts, presenting query-relevant but misleading knowledge that disrupts the reasoning process. To address these challenges, we argue for a \textit{reason-and-construct} paradigm and propose Relink, a framework that dynamically builds a query-specific evidence graph. To tackle incompleteness, \textbf{Relink} instantiates required facts from a latent relation pool derived from the original text corpus, repairing broken paths on the fly. To handle misleading or distractor facts, Relink employs a unified, query-aware evaluation strategy that jointly considers candidates from both the KG and latent relations, selecting those most useful for answering the query rather than relying on their pre-existence. This empowers Relink to actively discard distractor facts and construct the most faithful and precise evidence path for each query. Extensive experiments on five Open-Domain Question Answering benchmarks show that Relink achieves significant average improvements of 5.4\% in EM and 5.2\% in F1 over leading GraphRAG baselines, demonstrating the superiority of our proposed framework.