WorksComputer Science
EAGR: Evidence-Guided Adaptive Graph Retrieval
Abstract
Retrieval-Augmented Generation (RAG) for multi-hop reasoning requires retrieval to adapt as intermediate evidence reveals new information needs. Existing approaches support such retrieval through explicit graph structures or iterative query reformulation, introducing graph-construction or query-time overhead. We present Evidence-Guided Adaptive Graph Retrieval (EAGR), a framework in which accumulated evidence dynamically determines which semantic directions to explore next, and which requires no dedicated graph database and no explicit graph materialization. EAGR operates over an implicit semantic graph induced by compact passage metadata pre-ingested into a standard VectorDB. Starting from dense-retrieval seed passages, an LLM iteratively assesses accumulated evidence, identifies promising semantic directions, expands the retrieval frontier through metadata-based neighborhood lookup, and terminates once sufficient evidence has been collected. By precomputing semantic metadata, EAGR enables evidence-conditioned graph exploration without materializing an explicit graph, maintaining a dedicated GraphDB, or iteratively rewriting the query. Across three widely used multi-hop QA benchmarks, EAGR achieves the highest LLM-based answer accuracy among evaluated methods, outperforming the vanilla RAG by 17% and strongest graph-aware baseline by 4% percentage points averaged across three popular benchmarks HotPotQA, 2WikiMultiHopQA, and MuSiQue.
Introduction
Retrieval-Augmented Generation (RAG) grounds Large Language Models (LLMs) in external knowledge (Lewis et al., [19]). Conventional RAG retrieves a fixed set of passages using dense similarity and delegates reasoning to the LLM (Karpukhin et al., [17]). This works for localized evidence, but often struggles when an answer requires combining information across documents through dependent retrieval steps ([40, 36]). Such questions require retrieval to evolve as evidence accumulates.
The full retrieval path is rarely apparent from the original query. For example, a question about a person’s mother-in-law may require first finding a passage about their spouse, then using that evidence to retrieve information about the mother. The next useful retrieval direction thus emerges from intermediate evidence, rather than from the query alone.
Recent work tackles multi-hop retrieval using graph-based structures, including hierarchical summary graphs, knowledge graphs, associative memory graphs, and relation-free passage graphs ([6, 9, 10, 38, 37, 23]). These methods demonstrate the value of semantic connectivity, but commonly add a graph representation or indexing stage to the passage index. Another line of work treats retrieval over explicit knowledge graphs as a planning problem. Systems such as StructGPT, Think-on-Graph, and Plan-on-Graph use LLMs to explore graph neighborhoods and refine their decisions ([15, 34, 2]). They assume a symbolic graph whose entities and relations are known a priori.
We study a different setting: evidence-conditioned traversal over unstructured passages ([21]). Enterprise VectorDBs typically store passages and metadata, not explicit symbolic graphs. We derive passage connections from shared keyword and semantic descriptors in the existing index, then use metadata lookups to retrieve connected passages. This enables GraphRAG-style traversal without a separate graph store or a separately materialized graph. The central challenge is to discover which semantic directions to explore as evidence accumulates, rather than to execute a plan over a known graph.
We propose Evidence-Guided Adaptive Graph Retrieval (EAGR), which views retrieval as an adaptive search process. Each passage is associated with LLM-generated semantic descriptors stored as metadata; shared descriptors induce implicit connections without explicit graph edges. Retrieval starts with dense-retrieved seed passages. At each iteration, an LLM assesses the accumulated evidence, selects promising directions, and expands the retrieval frontier through metadata-based neighborhood lookup. Unlike planning-based approaches, EAGR neither executes an explicit reasoning plan [2, 4] nor repeatedly rewrites the query: its traversal adapts to the evidence gathered so far.
Our contributions are:
Evidence-guided adaptive retrieval. We formulate retrieval decisions around both the original query and accumulated evidence, enabling iterative LLM-guided exploration without repeated query rewriting.
GraphRAG over a standard VectorDB. We derive implicit passage connections from LLM-generated semantic descriptors stored as metadata, enabling neighborhood lookup without materialized graph edges or a separate graph store.
EAGR traversal strategy. We introduce an iterative procedure that selects semantic directions, expands the retrieval frontier, and stops when sufficient supporting context has been collected.
Figure 1 contrasts EAGR with related retrieval approaches. The remainder of the paper is organized as follows. § 2 reviews related work; § 3 presents EAGR; § 4 and 5 describe the experimental setup and results; and § 6 concludes with limitations.

Figure 1. Comparison of various Retrieval Approaches
Related Work
Adaptive retrieval. Dense retrievers rank passages once against the query [17]. Multi-hop methods instead condition later retrieval on earlier passages or the model’s reasoning state [40, 36, 30, 16], and recent work uses intermediate knowledge, sufficiency judgements or identified information gaps to steer subsequent steps [46, 14, 1, 32, 7, 21 a]. Most of these methods adapt by issuing new queries against the entire corpus index. EAGR keeps the original query fixed and adapts through accumulated evidence instead, restricting each step to the neighbourhood of the passages already explored.
Graph-structured retrieval. Graph-based RAG organizes corpora into summary hierarchies, entity–relation graphs or associative networks [29, 5, 9, 10, 44, 8, 39], and lighter designs reduce construction cost with incidence links instead of triples [13, 45]. These structures expose cross-passage connections, but they must be built and stored, and query-time retrieval typically follows community hierarchies, graph scores such as personalized PageRank, or fixed expansion rules. EAGR builds no graph and replaces fixed rules with evidence-guided search.
LLM-guided graph traversal. Think-on-Graph [33], Plan-on-Graph [3] and ToG 2.0 [26] let an LLM navigate symbolic knowledge graphs, and GraphReader [22], GeAR [31] and ReMindRAG [12] navigate graphs extracted from text. All assume a graph built in advance. Closest to EAGR are passage-level methods: KGP links passages via shared keywords and selects neighbours from the retrieval history [37], GNN-Ret propagates relevance over keyword graphs with a graph neural network [23], HopRAG links passages through pseudo-queries [25], and CuriousLLM uses accumulated evidence to generate follow-up queries and decide when to stop Yang et al. [42].
EAGR differs from these approaches in three ways. (i) No materialized graph: adjacency is induced on demand from descriptors stored as ordinary VectorDB metadata, so no edge set, graph index, GNN or pseudo-query index is built. (ii) Evidence-guided expansion without query rewriting: the evidence pooled across explored passages decides which descriptors of the local frontier to follow next, rather than generating new queries over the whole corpus or ranking a fixed candidate pool. (iii) Verified stopping and evidence-based ranking: traversal stops only when the LLM’s reasoning chain is supported by the collected evidence, and the retrieved passages are ranked by that chain, rather than by query similarity alone.
Methodology
Figure 2 illustrates our overall pipeline, consisting of an offline stage that induces an implicit graph over the corpus (Figure 2a) and an online stage that traverses this graph via evidence-guided frontier search (Figure 2b).

Figure 2. Overview of EAGR. (a) Offline indexing: an LLM extracts semantic descriptors for each passage and stores them as VectorDB metadata; passages sharing a descriptor form an implicit graph. (b) Online retrieval: dense retrieval yields the seed frontier . For each frontier node, one LLM call (1) assesses relevance, adding grounded facts to the evidence , and (2) selects descriptors to follow. (3) If suffices to answer , traversal stops; otherwise (4) selected descriptors are reranked by and , and (5) neighbours are fetched by metadata lookup, until budget is reached. Retrieved passages are finally reordered evidence-first.
Problem Formulation
Let denote a corpus of passages and denote an information-seeking query. Standard retrieval in RAG systems typically formulates retrieval as a mapping from the query to a ranked set of passages,
where denotes the retrieved passages. Under this formulation, the query serves as the primary conditioning signal throughout retrieval. For multi-hop queries, however, the evidence needed to answer is spread across several passages, and what earlier retrieval uncovers often determines what must be retrieved next. For example, the passage that identifies a film’s director is what reveals which biography to retrieve. Query-only retrieval does not model this evolving context.
We therefore treat adaptive retrieval as a first-class retrieval problem, in which each retrieval step is conditioned jointly on the original query and the evidence accumulated so far. Let denote the evidence accumulated after retrieval iterations. The passages retrieved next depend on both:
where extracts the facts in the newly retrieved passages that bear on . Retrieval thus alternates between retrieving passages and updating the evidence state, and need not search all of at every step: in EAGR it searches only the neighbourhood of the passages explored so far.
The objective is to acquire sufficient evidence to answer while avoiding unnecessary retrieval. Given a retrieval budget , defined as the maximum number of nodes that may be explored, the process terminates when the accumulated evidence is sufficient to answer , or when the exploration budget is exhausted, and returns a relevance-based reordered list of passages. Unlike iterative methods (Yao et al. [43]) that issue new model-generated queries at each step, our formulation keeps the original query fixed throughout retrieval. Adaptation happens instead through the evolving evidence state , which determines what to seek next without altering the original information need.
In the following sections, we instantiate this formulation through an implicit semantic graph abstraction 3.2 and an evidence-guided adaptive graph retrieval procedure 3.3.
Offline Stage: Implicit Graph Construction (Figure 2a)
To enable adaptive retrieval beyond the initial set of retrieved passages, we introduce an implicit semantic graph abstraction over the corpus. Rather than explicitly constructing and storing a graph, we attach to each passage a set of semantic descriptors , the entities and key concepts it mentions, and store them as metadata alongside the passage in the VectorDB. Each passage is thus represented as .
Two passages are connected if they share a descriptor (Wang et al. [37]; ); Li et al. [23]), which defines the implicit graph with
is never materialized: EAGR stores no edges, triples, hierarchical summaries or auxiliary graph index. Instead, the neighbourhood associated with a selected set of descriptors () is retrieved at query time through a metadata lookup in the VectorDB,
where descriptors are matched as phrases (Appendix § 13). The graph is therefore carried entirely by passage metadata, so graph-based retrieval needs no separate graph construction, storage or indexing pipeline. This simplicity is architectural rather than computational: EAGR still issues LLM calls for offline descriptor extraction and online traversal, which we profile in Section 5.
Descriptor Extraction and Adjacency. A single LLM call per passage extracts the named entities it mentions (people, organizations, locations, titles of works, events, products) and a few key concepts. Descriptors are lowercased, stripped of accents and punctuation, and kept only if they occur in the passage, which removes hallucinated descriptors. Dates are not used as descriptors, since they connect many unrelated passages. Finally, because the same person is often named differently across passages (e.g., Clarence Brown in a film’s passage and Clarence Leon Brown in his biography), a corpus-level step links shorter forms of a person’s name to the full name, so that such passages become neighbours. Appendix § 13 gives the prompt and the complete procedure.
Online Stage: Evidence-Guided Frontier Search (Figure 1b)
Given a query , EAGR first retrieves the top- passages by dense passage retrieval (DPR). Each passage is represented as , with content and semantic descriptors . These seed passages form the initial frontier , and the accumulated evidence is initialized as . EAGR then proceeds frontier by frontier: it assesses every node of the current frontier , adding the evidence they contain to , and uses this evidence to decide whether to stop and, if not, which directions of the implicit graph to explore next. Each iteration comprises five stages: Node Assessment and Evidence Accumulation, Edge Selection, Sufficiency Check, Evidence-Guided Edge Reranking and Graph Expansion. Node Assessment and Edge Selection are performed jointly in a single LLM call per node; the prompts are given in Appendix § 17.
Node Assessment and Evidence Accumulation. Nodes of the frontier are assessed in order of their similarity to . For each node , EAGR decides whether it is relevant to the query and extracts the evidence it contributes, conditioned on the query and the evidence accumulated so far:
A node is relevant () if it helps answer any step of the query: it states information the query asks for, or identifies an entity on the path to the answer, such as the director of a film named in the query. It need not contain the final answer. is the set of facts from that fill a step of the query, each written as a short, self-contained sentence; facts about the same entities that would not change the answer are left out. Since the LLM may introduce information that is not in the passage, a fact is kept only if it is grounded in , and facts already in are skipped (Appendix § 17). The evidence of relevant nodes is accumulated,
so each subsequent node, within the same frontier or a later one, is assessed against all evidence found so far. Irrelevant nodes contribute neither evidence nor directions for exploration.
Edge Selection. For each relevant node , EAGR considers its unvisited descriptors as candidate directions for further exploration and selects those most likely to lead to evidence that is still missing, conditioned on the query, the current passage and the accumulated evidence:
Descriptors are thus not chosen solely for their association with the current passage; their utility is judged against what the query still requires given the evidence gathered so far. Each descriptor in defines a direction of traversal, with the passages sharing it forming candidate neighbours in the implicit graph. By selecting directions rather than exploring all descriptors in , EAGR focuses expansion on connections expected to yield useful evidence.
Unlike methods that traverse a knowledge graph through predefined entities and relations, EAGR selects edges using the full content of the current passage together with the accumulated evidence. This lets it distinguish directions that are structurally connected but differ substantially in their usefulness for the query.
Sufficiency Check. Once all nodes of the frontier have been assessed, and if they added new evidence, EAGR checks whether is sufficient to answer :
Rather than asking for a bare yes/no judgement, which we found prone to premature termination, the LLM writes out the chain of steps the query requires, each as an (entity, attribute, value) triple with the value taken from , or left empty if the evidence does not state it. For example, for “Which team did Joe Buck’s father broadcast for?”, the chain is (Joe Buck, father, Jack Buck) followed by (Jack Buck, team, St. Louis Cardinals). EAGR accepts only if the LLM judges the evidence sufficient, every value is filled, and every value appears in , which rejects answers the LLM fills in from its own knowledge. If , retrieval terminates; otherwise EAGR continues with the edges selected in this frontier. Retrieval also terminates when the number of explored passages reaches the budget .
Evidence-Guided Edge Reranking. If the evidence is insufficient, EAGR pools the descriptors selected from relevant nodes on the current frontier into a candidate set:
where denotes the relevant nodes of the frontier. It then ranks these candidates by their usefulness for the query, conditioned on the accumulated evidence:
Unlike Edge Selection, which evaluates each node’s descriptors independently in its local context, reranking compares candidates proposed by different nodes against the same accumulated evidence. This enables EAGR to prioritize directions that address unresolved evidence gaps and adapt its focus as new evidence is gathered.
Graph Expansion. Given the ranked descriptors , EAGR materializes the corresponding neighbourhood through a metadata lookup in the VectorDB (§ 3.2), retrieving up to passages per descriptor. Already visited passages are excluded, and the remaining passages form the next frontier , ordered by the rank of the descriptor that reached them; since the budget may run out partway through a frontier, higher-ranked directions are explored first. Implementation details of candidate edges, such as following other spellings of a selected name, are given in Appendix § 17. The process then iterates, so that the evidence accumulated at each step shapes the directions explored next, without an explicit graph ever being constructed or stored.
Termination and output. Traversal stops when the Sufficiency Check succeeds or when the number of explored passages reaches the budget .
| Method | HotpotQA | 2WikiMultiHopQA | MuSiQue | Average | ||||
| Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | |
| Direct LLM | ||||||||
| Llama-3.3-70B-Instruct | 41.2 | 49.2 | 43.6 | 43.8 | 17.6 | 20.2 | 34.1 | 37.7 |
| Dense Retrieval | ||||||||
| Vanilla RAG | 66.4 | 75.5 | 64.2 | 62.1 | 33.7 | 41.9 | 54.8 | 59.8 |
| Graph-aware Retrieval | ||||||||
| HippoRAG2 | 68.9 | 77.9 | 74.9 | 72.7 | 32.9 | 38.7 | 58.9 | 63.1 |
| LinearRAG | 63.8 | 73.6 | 80.1 | 78.2 | 31.8 | 37.8 | 58.6 | 63.2 |
| MemGraphRAG | 66.6 | 75.5 | 66.7 | 64.6 | 37.0 | 44.2 | 56.8 | 61.4 |
| LogicRAG | 55.7 | 62.4 | 39.3 | 36.7 | 19.9 | 23.6 | 38.3 | 40.9 |
| Agentic / Iterative Retrieval | ||||||||
| ReAct | 42.1 | 49.3 | 44.1 | 44.5 | 18.0 | 21.9 | 34.7 | 38.6 |
| Adaptive Graph Retrieval (Ours) | ||||||||
| EAGR + Accum. Evidence | 66.8 | 75.6 | 67.2 | 65.2 | 43.2 | 51.7 | 59.1 | 64.2 |
| EAGR + Passage (EAGR) | 67.4 | 77.4 | 80.3 | 78.1 | 38.4 | 45.8 | 62.0 | 67.1 |
Table 1. End-to-end question answering performance on multi-hop QA benchmarks. We report String-based accuracy (Str-Acc.) and LLM judge accuracy (LLM-Acc.). The best result in each column is shown in bold, and the second-best is underlined.
The number of passages explored therefore varies across queries: EAGR retrieves only as much additional evidence as each query needs, within a fixed upper bound on retrieval cost. The explored passages are then ranked as described in § 3.4.
All semantic operations in EAGR use three prompts to the same LLM: a joint prompt for Node Assessment and Edge Selection (one call per node), a Sufficiency Check prompt (at most one call per frontier) and an Edge Reranking prompt (at most one call per frontier). The prompts are given in Appendix G, a step-by-step retrieval trace in Appendix F, and the complete procedure in Algorithm 1.
Retrieval Reordering
After traversal terminates, EAGR orders the explored passages using the evidence collected along the way, in three groups: (i) relevant passages whose extracted facts mention the entities or values in the reasoning chain of the last Sufficiency Check, i.e., the evidence for the answer; (ii) other relevant passages that contributed facts; and (iii) all remaining passages, with those judged irrelevant last. Within each group, passages keep their order from the traversal.
This ordering matters most for multi-hop queries, where passages reached after one or more hops (e.g., the biography of a film’s director) are needed to establish the answer but may share little vocabulary with the query. Ranked by query similarity alone, such passages would often fall outside the top-ranked results; ranking by the evidence chain instead places them first, while passages judged irrelevant are moved to the end.
Experiments
In this section, we aim to answer the following research questions: Q1 (Generation Accuracy): How does EAGR compare with state-of-the-art retrieval-augmented generation and GraphRAG methods in terms of end-to-end answer generation performance? Q2 (Retrieval Effectiveness): Does EAGR retrieve the supporting passages more effectively, particularly for multi-hop information needs? Q3 (Ablation Study): What is the contribution of each component of EAGR contribute to the overall retrieval and generation performance?
Experimental Setup
Datasets. We evaluate EAGR on three widely used multi-hop QA benchmarks: HotpotQA, 2WikiMultiHopQA (2Wiki), and MuSiQue [41, 11, 35]. Following prior work [9, 10], we select 1,000 validation questions from each dataset.
Baselines. We compare against direct generation without retrieval, vanilla dense RAG, the graph-based methods HippoRAG2 [10], LinearRAG [45], MemGraphRAG [38] and LogicRAG [4], and the iterative methods ReAct [43]. ReAct use the same retriever, LLM and passage budget as EAGR.
| Method | HotpotQA | 2WikiMultiHopQA | MuSiQue | Average | ||||
| Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | Str-Acc. | LLM-Acc. | |
| EAGR (Full) | 67.4 | 77.4 | <u>80.3</u> | <u>78.1</u> | <u>38.4</u> | <u>45.8</u> | <u>62.0</u> | 67.1 |
| Evidence Assessment | ||||||||
| w/o Relevance Scoring | 67.6 | <u>77.5</u> | 79.0 | 76.4 | 39.6 | 46.1 | 62.1 | <u>66.7</u> |
| w/o Accumulated Evidence | 67.1 | <u>76.1</u> | 74.5 | 71.8 | 34.7 | 40.4 | 58.8 | 62.8 |
| Graph Navigation | ||||||||
| w/o Edge Selection | 40.9 | 48.3 | 44.4 | 44.6 | 32.5 | 38.5 | 39.3 | 43.8 |
| w/o Edge Reranking | <u>67.5</u> | 78.1 | 80.4 | 78.2 | 36.6 | 42.6 | 61.5 | 66.3 |
| Retrieval Policy | ||||||||
| w/o Retrieval Reordering | 65.8 | 74.6 | 73.6 | 70.2 | 36.8 | 44.8 | 58.7 | 63.2 |
Table 2. Ablation study of EAGR components across HotpotQA, 2WikiMultiHopQA, and MuSiQue benchmarks. The best result in each column is shown in bold, and the <u>second-best</u> is underlined.
| Method | Reasoning / Retrieval Breakdown | Generated Answer | Judge |
| Question: Who is the owner of the record label of the performer of What Kind of Love? Gold: Warner Music Group | |||
| Direct LLM | Parametric hallucination; assumes Sony Music without retrieval. | Sony Music Entertainment | ✗ |
| Vanilla RAG | Dense search retrieves song info (Rodney Crowell) but misses label owner. | The information is not provided. | ✗ |
| HippoRAG2 | PPR graph activation disperses across artist albums, missing the owner. | The information is not provided... | ✗ |
| MemGraphRAG | Memory graph clusters song details but fails to jump to parent owner entity. | The information is not provided... | ✗ |
| LogicRAG | Logical decomposition resolves performer but fails to retrieve 3rd-hop owner. | The information is not provided. | ✗ |
| LinearRAG | Linear graph misses multi-hop connectivity between artist and holding entity. | The information is not provided. | ✗ |
| ReAct | Agent repeats sub-query formulation, entering an empty retrieval loop. | [Empty] | ✗ |
| EAGR (Ours) | Hop 1: What Kind of Love → Hop 2: Rodney Crowell → Hop 3: Warner Bros. Records → Warner Music Group (Terminates on sufficiency). | Warner Music Group | ✓ |
Table 3. Qualitative comparison on MuSiQue (3hop1__198276_709625_84283). EAGR recovers the full 3-hop reasoning chain, whereas baselines fail due to missing context hops, search diffusion, or loop breakdown.
Results and Analysis
Evaluation Metrics. We evaluate EAGR from both retrieval and downstream QA perspectives. For retrieval, we report Recall@5, the fraction of gold supporting passages among the top five retrieved, computed on each method’s own ranking. For QA, every method’s top five passages are given to the same LLM generator; String Accuracy (Str-Acc.) checks whether the normalized gold answer appears in the response, and LLM Accuracy (LLM-Acc.) uses an LLM judge ([38]).
Implementation Details. Dense retrieval uses NV-EMBED-V2 ([18]) for all methods. Descriptors are extracted with LLAMA-3.3-70B-INSTRUCT ([27]), and EAGR’s retrieval prompts use QWEN3-8B ([28]) with thinking disabled. EAGR starts from seed passages, with a budget of passages. Answers are generated by LLAMA-3.3-70B-INSTRUCT and judged by DEEPSEEK-V3.2 ([24]). All LLMs use temperature 0. We also report a variant whose reader receives the accumulated evidence instead of passages.
Results and Analysis
Generation accuracy (Q1).
Table 1 shows that EAGR achieves the highest average accuracy, 67.1 LLM-Acc., 3.9 points above the strongest baseline (LinearRAG, 63.2) and 7.3 above vanilla RAG. Its main strength is consistency: the strongest graph-based baselines each excel on some benchmarks but fall below vanilla RAG on others (HippoRAG2 and LinearRAG on MuSiQue, LinearRAG also on HotpotQA), whereas EAGR improves over vanilla RAG on all three. It matches the best baseline on HotpotQA (77.4 vs. 77.9) and 2Wiki (78.1 vs. 78.2) and gives the best result on MuSiQue (45.8 vs. 44.2), the benchmark with the longest reasoning chains. Giving the generator the accumulated evidence instead of passages raises MuSiQue accuracy further to 51.7, suggesting that the evidence collected during traversal is a useful condensed context for long chains.
Retrieval (Q2).
Table 4 shows the largest retrieval gain on 2Wiki, where EAGR reaches 95.5 Recall@5 against 91.0 for HippoRAG2 and 76.7 for dense retrieval; its questions mostly follow explicit entity chains (e.g., a film’s director, then the director’s birthplace), which descriptor edges follow directly. On HotpotQA, EAGR is on par with HippoRAG2 (95.4 vs. 95.9). On MuSiQue, its recall equals dense retrieval and trails HippoRAG2 (71.5 vs. 76.2), yet its answer accuracy is 7.1 points higher, indicating that recall of all gold passages alone does not fully determine downstream accuracy. Figure 3 shows how early stopping criteria in EAGR makes a significant number of queries stop at less than 5 retrieved chunks, this filtering out noisy context and providing better QA accuracy.
| Method | HotpotQA | 2WikiMHQA | MuSiQue |
| Dense Retrieval | |||
| Vanilla RAG (Top-5) | 94.03 | 76.67 | 71.42 |
| Graph-Aware Retrieval | |||
| LogicRAG | 68.40 | 45.10 | 20.90 |
| HippoRAG2 | 95.90 | 91.03 | 76.17 |
| LinearRAG | 66.85 | 80.70 | 65.90 |
| MemGraphRAG | 92.30 | 80.20 | 71.40 |
| Adaptive Graph Retrieval | |||
| EAGR (Ours) | 95.40 | 95.53 | 71.53 |
Table 4. Retrieval performance on multi-hop QA benchmarks measured by Proportion Recall at Top-5 (Recall@5).

Figure 3. Number of passages retrieved per query by EAGR (budget ), per benchmark. Traversal stops as soon as the accumulated evidence is verified to answer the query.
Adaptive retrieval. Because traversal stops once the accumulated evidence is verified to answer the query, EAGR spends retrieval effort where it is needed (Figure 3). On HotpotQA and 2Wiki, about 81% of queries stop within 10 passages, and on HotpotQA 71% need at most 5, i.e., the four seed passages and at most one more; only about 4% reach the budget. MuSiQue, whose questions require up to four hops, shows a different profile: about 46% of queries stop within 10 passages, while 31% explore the full budget. The traversal thus scales with question difficulty rather than retrieving a fixed number of passages per query, which keeps the average cost low on benchmarks dominated by short reasoning chains.
Ablation Study
Each ablation removes one component while keeping the rest of the pipeline unchanged (Table 2). Two components matter consistently. Removing accumulated evidence, so that assessment, edge selection and reranking see only the query and the current passage and traversal never stops early, lowers average accuracy by 4.3 points, and by 6.3 and 5.4 on 2Wiki and MuSiQue: conditioning on evidence is the main source of EAGR’s gains. Removing retrieval reordering costs 3.9 points (7.9 on 2Wiki), showing that passages found through multi-hop expansion need to be ranked by the evidence chain to reach the reader. Edge reranking has a small average effect (0.8) but matters on MuSiQue (3.2), where longer chains make the order of exploration more consequential. Relevance assessment has the smallest effect: it helps on 2Wiki (1.7) and is neutral on HotpotQA and MuSiQue. Edge selection is the most critical component: following every descriptor of a relevant passage instead of the selected ones lowers average accuracy by 23.3 points, below even vanilla RAG. Without selection, the budget is spent within the first expansion on passages that share incidental descriptors with the seeds, so the passages of later hops are rarely reached, and the many loosely related passages explored compete with the actual evidence for the top-ranked positions.
Qualitative Analysis
To examine how evidence guides traversal, we analyze a 3-hop MuSiQue query where all baselines fail (Table 3, Appendix § 11). While dense, graph, and agentic baselines fail to bridge intermediate entities (Rodney Crowell Warner Bros. Records Warner Music Group) due to localization bias, hallucination, or looping, EAGR’s Node Assessment iteratively accumulates evidence across hops and successfully recovers the complete reasoning chain.
Human Evaluation
To validate the LLM judge, three annotators independently labelled 150 sampled predictions across benchmarks and methods. The judge agreed with the human majority on 94.0% of them (Fleiss’ ; Appendix § 12).
Conclusion
We presented EAGR, an adaptive retrieval approach in which accumulated evidence, rather than a rewritten query, determines which directions to explore next. EAGR traverses an implicit graph induced from descriptors stored as ordinary VectorDB metadata, selecting and ranking edges by the evidence collected and stopping once a verified reasoning chain answers the query, all without materializing a graph or rewriting the query. Across HotpotQA, 2WikiMultiHopQA and MuSiQue, it achieves the highest average answer accuracy, 3.9 points above the strongest graph-based baseline, and is the only graph-based method that improves over dense retrieval on all three benchmarks. Ablations show that conditioning on accumulated evidence drives these gains, supporting a view of multi-hop retrieval as an adaptive search process in which accumulated evidence and not the original query alone, determines how the retrieval frontier evolves.
Limitations
All components of EAGR are currently used off-the-shelf without task-specific training. Future work could explore component-specific fine-tuning and stronger foundation models to further improve both retrieval quality and practical viability.
Ethics Statement
We used LLM-based tools to assist with code development and to improve the clarity of the writing. All research ideas, the method, the experimental design, and the analysis and interpretation of results are the authors’ own, and all LLM-assisted text was verified by the authors for correctness.
Reproducibility. EAGR builds only on publicly available datasets and open-weight models. Our experiments use the standard HotpotQA, 2Wiki-MultiHopQA, MuSiQue, and GraphRAG-Bench evaluation sets with the model configuration reported in § 4.1, and all prompts used by the offline and online stages are provided verbatim in Appendices § 13 and § 17. Upon acceptance, we will release the code and the generated passage metadata for all datasets used to enable exact reproduction of the implicit graph and the retrieval procedure.
Appendix
Evidence-Guided Adaptive Graph Retrieval (EAGR) Algorithm
Algorithm 1 provides the complete procedural description of EAGR. The algorithm consists of an offline semantic graph abstraction stage and an online evidence-guided retrieval stage. During the offline stage, each passage is associated with a set of semantic descriptors , which are stored as metadata in the VectorDB. During inference, EAGR first retrieves seed passages using DPR and initializes the retrieval queue and accumulated evidence with these seeds and an empty evidence context, respectively.
The online retrieval procedure follows the four stages described in § 3.3: Node Assessment, Edge Selection, Evidence-Guided Edge Reranking, and Graph Expansion. Relevant but insufficient nodes contribute evidence and selected semantic descriptors to the traversal, while irrelevant nodes are excluded from further expansion. Candidate descriptors proposed across the explored nodes are subsequently reranked using the query and accumulated evidence, after which at most neighboring passages are retrieved through metadata lookup. Already explored nodes are excluded from subsequent expansion.
The procedure terminates when a relevant node is assessed as sufficient or when the exploration budget is exhausted. Finally, the retrieved passages are reordered using the relevance decisions made during traversal, while preserving their relative retrieval order.
Multi-Hop Retrieval Performance
Table 4 reports the retrieval quality of EAGR compared to dense and graph-aware baselines on multi-hop benchmarks using Proportion Recall at top-5 retrieved passages (Recall@5).
Operating strictly over implicit metadata stored within a standard VectorDB, EAGR achieves competitive retrieval quality across all benchmarks (94.5% on HotpotQA, 90.4% on 2WikiMultiHopQA, and 72.6% on MuSiQue), demonstrating that iterative evidence-guided frontier expansion successfully gathers multi-hop supporting context without requiring explicit GraphDB materialization.
Qualitative Case Study
Table 3 presents a detailed qualitative case study on a representative 3-hop question from MuSiQue (3hop1__198276_709625_84283), comparing EAGR against all baselines.
Case Study: 4-Hop Multi-Entity Disambiguation
Table 5 presents a challenging 4-hop question from MuSiQue (4hop3__771862__466199__695123__72134) involving multiple overlapping entities (multiple towns named Springfield across different states).
Human Evaluation and LLM Judge Validation
To rigorously validate automated LLM-as-a-judge evaluation, we conducted a blind human evaluation on a stratified sample of 150 question–answer predictions across HotpotQA, 2WikiMultiHopQA, and MuSiQue (50 questions per benchmark), spanning five retrieval methods (10 samples per method per dataset). Three independent human annotators evaluated all 150 instances using a dedicated Label Studio interface, judging model generations against reference gold answers and supporting context.
As detailed in Table 6, the three human annotators demonstrated high inter-annotator agreement
| (a) Inter-Annotator Agreement () | (b) Judge vs. Majority by Dataset & Method | (c) % Marked Correct on Sample () | ||||||
| Pair / Metric | Agreement | Cohen’s | Data / Method Slice | Agreement | Count | Evaluator | % Correct | Count |
| Annotator 1 – Annotator 2 | 92.0% | 0.833 | HotpotQA | 90.0% | 45/50 | Annotator 1 | 63.3% | 95/150 |
| Annotator 1 – Annotator 3 | 91.3% | 0.822 | 2WikiMultiHopQA | 96.0% | 48/50 | Annotator 2 | 58.0% | 87/150 |
| Annotator 2 – Annotator 3 | 94.0% | 0.878 | MuSiQue | 96.0% | 48/50 | Annotator 3 | 54.7% | 82/150 |
| Fleiss’ (3 Annotators) | 0.844 | Vanilla RAG | 86.7% | 26/30 | Human Majority | 58.0% | 87/150 | |
| Joint Fleiss’ (+ Judge) | 0.854 | HippoRAG2 | 96.7% | 29/30 | LLM Judge | 57.3% | 86/150 | |
| Annotator 1 – Judge | 90.0% | 0.792 | LinearRAG | 96.7% | 29/30 | 3-Human Unanimous | 88.7% | 133/150 |
| Annotator 2 – Judge | 94.0% | 0.877 | MemGraphRAG | 93.3% | 28/30 | All-4 Unanimous | 87.3% | 131/150 |
| Annotator 3 – Judge | 96.0% | 0.919 | EAGR+Passage | 96.7% | 29/30 | Disagreements | 6.0% | 9/150 |
| Overall Automated Judge Alignment with Human Majority: 94.0% (141/150) | Joint Fleiss’ |
Table 6. Human evaluation study () validating automated LLM judging against three independent human annotators across benchmarks and retrieval methods. Annotators achieve high inter-annotator agreement (Fleiss’ ), and the automated judge aligns with human majority consensus on 94.0% of tasks () with calibrated accuracy (57.3% vs. 58.0%).
| Method | Retrieval Behavior & Failure Mode | Generated Output | Judge |
| Direct LLM | Parametric memory fails on 4-hop compositional constraints; returns empty. | [Empty] | ✗ |
| Vanilla RAG | Dense retrieval pulls conflicting Springfield passages across states; fails to synthesize. | [Empty] | ✗ |
| HippoRAG2 | Graph PPR spreads activation to distractor node (Springfield, Ohio), concluding false premise. | “Springfield, Ohio has never been the capital of Indiana.” | ✗ |
| MemGraphRAG | Entity clustering conflates Ohio and Illinois nodes, generating a contradictory claim. | “Springfield, Ohio, has never been the capital of Ohio.” | ✗ |
| LinearRAG | Linear graph misses parallel branch binding Jackson Township to Illinois. | “Never” | ✗ |
| LogicRAG | Sub-question decomposition fails to resolve the joint state constraint. | “There is no information to answer the question.” | ✗ |
| ReAct | Agent converges on the state formation year of Indiana (1816) instead of capital relocation. | “1816” | ✗ |
| EAGR (Ours) | Hop 1: WIZE → town of Springfield. Hop 2: Jackson Township → state of Illinois. Hop 3: Evidence combines (Springfield + Illinois) → prunes Ohio/Indiana distractors. Hop 4: Expands to Springfield history → retrieves capital relocation in 1839 (Sufficiency reached). | “1839” | ✓ |
caption: Qualitative 4-hop case study on MuSiQue (4hop3__771862__466199__695123__72134). Existing graph methods get trapped in spurious entity paths (Springfield, Ohio / Indiana), whereas EAGR’s accumulated evidence enables entity disambiguation across parallel reasoning branches.
:::
with a Fleiss’ of 0.844 (pairwise Cohen’s ranging between 0.822 and 0.878). When comparing the automated LLM judge (DeepSeek-V3.2) against the human majority consensus, the judge achieved an overall agreement of 94.0% (141/150 tasks), with joint Fleiss’ = 0.854. Judge agreement remained high across individual benchmarks (96.0% on both 2WikiMultiHopQA and MuSiQue; 90.0% on HotpotQA) and across retrieval methods (96.7% on EAGR, HippoRAG2, and LinearRAG). Furthermore, the overall proportion of answers judged correct by the automated judge (57.3%) closely matches human majority consensus (58.0%). Qualitative audit of the 9 dissenting cases indicates that discrepancies stem from borderline partial matches (e.g., shortened names or omitted qualifiers) rather than categorical errors, confirming that the LLM judge reliably mirrors human judgment. The exact instructions provided to human annotators are shown in Figure 4.

Figure 4. Instructions provided to human annotators. The same criteria were used for both human evaluation and the LLM judge.
Implicit Graph Construction
This appendix specifies how descriptors are extracted and normalized and how neighbourhoods are looked up, so that the offline stage can be reproduced given the same LLM (temperature 0).
Step 1: Descriptor extraction. Each passage, prefixed with its title, is sent to LLAMA-3.3-70B-INSTRUCT with the prompt in Figure 5. The prompt asks for every named entity and at most five key concepts, as a JSON array of typed items (person, organization, location, work, event, product, other, concept, date). Names are requested in their most complete form in the text; partial names and nationality adjectives are excluded, and no minimum count is imposed.

Descriptor Extraction Prompt (1/2)
Extract the entities and key terms from the text
below. They will be used to link this passage to
other passages that mention the same things.
Output ONLY a JSON array, starting with [ and
ending with ]. No explanations, no reasoning, no
markdown.
Each item is an object: {"name": "...", "type": "..."}
Types:
- person: people and characters
- organization: companies, bands, teams,
institutions, government bodies, political
parties
- location: countries, cities, regions, rivers
and other natural features, buildings, landmarks
- work: titles of creative or published works
(films, songs, albums, books, games, shows,
artworks, publications). Always include titles,
including those in quotation marks.
- event: named events, wars, treaties,
competitions, awards
- product: named products, technologies,
vehicles, models
- other: any other named entity (for example a
named chart, list, style or programme)
- concept: specific multi-word terms central to
the text that other passages would use for the
same thing. At most 5. Never generic words such
as "film", "song", "company", "director",
"album".
- date: dates and years
Rules:
- Include every named entity in the text, however
many there are. Do not pad the list to reach a
number.
- Copy each name exactly as written in the text,
in its most complete form there. Do not invent,
translate, expand or shorten names.
- If the text itself uses several forms for the
same entity (a full name and an abbreviation, or
a title and its translation), output each form
that appears as a separate item.
Descriptor Extraction Prompt (2/2)
- Do not output parts of a name on their own,
unless the text refers to an entity only that
way.
- Nationality and language adjectives ("British",
"French") are not entities. Include a country
only if it is named.
- Pronouns and descriptions ("the singer", "his
wife") are not entities.
- No duplicates.
Example
Text:
"“Northern Lights” is a 1998 song by the Scottish
band Glass Harbour, written by lead singer Mara
Ellison Kent. It appeared on the album "Tidewater"
(French: "Marée"), released by Polar Records, and
reached number 4 on the UK Singles Chart.
Output:
[{"name": "Northern Lights", "type": "work"},
{"name": "Glass Harbour", "type": "organization"},
{"name": "Mara Ellison Kent", "type": "person"},
{"name": "Tidewater", "type": "work"},
{"name": "Marée", "type": "work"},
{"name": "Polar Records", "type": "organization"},
{"name": "UK Singles Chart", "type": "other"},
{"name": "1998", "type": "date"}]
Text:
{content}
Output:Figure 5. Prompt used in the offline stage to extract typed descriptors for each passage, shown in two parts. Line breaks are added for layout. The response is parsed, cleaned, grounded against the passage and normalized as described in Appendix § 13.
Step 2: Parsing, cleaning and grounding. We parse the first well-formed JSON array in the response. If none is found (e.g., a missing closing bracket, or a response cut off at the token limit), the complete entity objects are read individually.
Each name is lowercased, hyphens are replaced by spaces, accents are removed and whitespace is collapsed. A name is kept only if it occurs as a whole-word phrase in the passage (title included), compared after the same normalization with punctuation removed; this discards names the LLM invented or paraphrased. Duplicates are collapsed. Dates are kept in the passage metadata but excluded from the descriptor set . Using the extracted entity types, we collect person names across the corpus and group them by last name and suffix (e.g., Jr., II). Within each group, a name is considered a shorter form of another if its words occur in the same order in the longer name, with initials matching words that begin with the corresponding letter (e.g., Clarence Brown and Clarence Leon Brown; Robert A. Stemmle and Robert Adolf Stemmle). First names must match, suffixes must be identical, and the shorter name’s middle part must match the first middle part of the longer name. Thus, George W. Bush is not merged with George H. W. Bush. Names containing particles or epithets (e.g., de, van, the, of) are excluded from merging. If a shorter form matches at most three full names, all matching full names are added as descriptors to every passage containing that shorter form. If it matches more than three, it is considered ambiguous and left unlinked. Finally, single-word fragments of a person’s name (e.g., Clarence, Brown) are removed from passages containing the full name to prevent spurious connections between different people.
Step 4: Neighborhood lookup. At query time, the neighbours along a selected descriptor are the passages with at least one descriptor that contains as a contiguous word sequence, matched case- and punctuation-insensitively by a phrase query on the descriptor metadata. A descriptor therefore also reaches passages whose descriptors extend it (e.g., the goose woman matches the goose woman remake). Each lookup returns at most matching passages per descriptor, without further ranking among the matches.
Algorithm 1 Evidence-Guided Adaptive Graph Retrieval (EAGR)
Require: Query , seed size , budget , neighbour limit , VectorDB storing each passage with descriptors
Ensure: Ranked list of retrieved passages
Offline: implicit graph construction (Appendix § 13)
for each passage do
Extract, ground and normalize descriptors ; store in
end for
Online: evidence-guided frontier search
▷ seed frontier
▷ explored passages, evidence, expanded descriptors
while and do
for each in order of similarity to do
if then break
end if
Append to
▷ one LLM call
if then
▷ drop ungrounded and repeated facts
if then
end if
end if
end for
if and then
break ▷ verified reasoning chain; § 3.3
end if
▷ next frontier, in rank order
end while
return ▷ § 3.4
| Category | Question (abridged) | Gold | HippoRAG2 | EAGR |
| String false negative | What three other National Forests are administered by the same people who administer the park the Art Loeb trail runs through? | Croatan, Nantahala, Uwharrie | Str= 1, LLMaJ= 1 (exact) | Str= 0, LLMaJ= 1 (lists all three with extra text) |
| String false negative | The Mexican Indignados Movement is a response to a war also known as? | Mexican War on Drugs | Str= 1, LLMaJ= 1 | Str= 0, LLMaJ= 1 (“Mexican Drug War”) |
| Genuine improvement | Who directed a 2006 film where Ron Perkins’s character plays the manager of a hotel? | Christopher Nolan | Str= 0, LLMaJ= 0 (“Todd Field”) | Str= 1, LLMaJ= 1 (“Christopher Nolan”) |
| Genuine improvement | What was the U.S. Army position of the Lieutenant General that Robert E. Lee surrendered to? | Commanding General | Str= 0, LLMaJ= 0 (“General-in-Chief”) | Str= 1, LLMaJ= 1 (“Commanding General”) |
Table 7. Representative HotpotQA cases where String Accuracy and the LLM judge diverge. The first two rows show EAGR answers that are correct but lexically penalized; the last two show questions EAGR answers correctly and HippoRAG2 does not.
Illustrative Retrieval Trace
Figure 6–Figure 8 present a complete recorded retrieval trajectory, from seed retrieval to termination. The organization mirrors the online stages of § 3.3: joint Node Assessment and Edge Selection (one LLM call per passage), the Sufficiency Check (once per frontier), Evidence-Guided Edge Reranking and Graph Expansion, followed by Retrieval Reordering. Passages are abridged to their query-relevant sentences, and long edge-label lists are shortened; everything else is as recorded.

Figure 6. DPR initialization and the joint Node Assessment and Edge Selection output for the first seed, which identifies the husband.

Figure 8. Reranking, Graph Expansion and Frontier 1. The husband’s passage, reached by one hop, completes the reasoning chain; the Sufficiency Check succeeds and traversal stops after 5 of 30 passages. Reordering places both passages of the evidence chain first.
Illustrative Retrieval Trace
Initialization and Frontier 0: Seed 1
Initialization: Dense Passage Retrieval (DPR) of Seed Nodes
Query. What is the place of birth of Atang de la Rama’s husband?
Seed retrieval. Dense retrieval with returns the initial frontier . The accumulated evidence is initialized as .
Reading the Joint Output
| is_relevant () | Selected Edge Labels () | Facts () |
| Does the passage help answer any step of the query? | Which of the passage’s unvisited descriptors should be followed? | Which facts from the passage fill a step of the query? Grounded facts of relevant passages are added to . |
Seed 1 of 4 (): Atang de la Rama
Evidence before assessment. .
Current passage (abridged). Honorata de la Rama-Hernandez (January 11, 1902 – July 11, 1991), commonly known as Atang de la Rama, was a singer and bodabil performer who became the first Filipina film actress. [. . . ] She was married to National Artist for Literature, Amado V. Hernandez.
Edge labels (37, abridged). amado v. hernandez, amado vera hernandez, atang de la rama, pandacan, manila, dalagang bukid, kundiman, . . .
Joint Node Assessment and Edge Selection output
| is_relevant | Selected Edge Labels | Facts |
| True | [amado v. hernandez] | [“Atang de la Rama was married to Amado V. Hernandez.”] |
Retrieval-state update. The passage is a relevant bridge: it identifies the husband. Its fact enters , and amado v. hernandez becomes a candidate edge. Because the passage also contains another spelling of the same name, amado vera hernandez, that label becomes a candidate too (Appendix G), so the husband’s passage is reached whichever spelling it uses.
Figure 7. Frontier 0, continued. One seed is a recorded false positive (a different husband) and two are irrelevant name matches. The Sufficiency Check identifies the missing step, so traversal continues.
Reranking, Graph Expansion, Frontier 1 and Termination
Evidence-Guided Edge Reranking
The candidates selected in frontier 0 are . Given and , the reranker returns , placing the husband’s name first.
Graph Expansion
Metadata lookup along reaches one unexplored passage, which forms the next frontier .
Frontier 1 (): Amado V. Hernandez
Current passage (abridged). Amado Vera Hernandez, commonly known as Amado V. Hernandez (September 13, 1903 – March 24, 1970), was a Filipino writer and labor leader [. . . ]. He was born in Tondo, Manila, to parents from Hagonoy, Bulacan.
Edge labels (unvisited only). american correspondence school, bulacan, gagalangin, hagonoy, manila, manila high school, philippines, tondo
Joint Node Assessment and Edge Selection output
| is_relevant | Selected Edge Labels | Facts |
| True | [“Amado V. Hernandez was born in Tondo, Manila.”; “Amado V. Hernandez was born to parents from Hagonoy, Bulacan.”] |
Table 1 (PDF p. 20).
Sufficiency Check after Frontier 1: Termination
| Entity | Attribute | Value |
| Atang de la Rama | husband | Amado V. Hernandez |
| Amado V. Hernandez | place of birth | Tondo, Manila |
| Amado V. Hernandez | parents’ birthplace | Hagonoy, Bulacan |
Table 2 (PDF p. 20).
Decision. , and every value appears in , so the check succeeds and traversal stops, although the judge had still selected edges for . The chain no longer includes Christopher O’Neill: the false positive from frontier 0 played no part in the answer.
Retrieval Reordering and Cost
| Rank | Passage | Source | Group |
| 1 | Atang de la Rama | Dense seed | (i) supports the chain |
| 2 | Amado V. Hernandez | Graph expansion | (i) supports the chain |
| 3 | Christopher O’Neill | Dense seed | (ii) relevant, contributed facts |
| 4 | Urata Rama | Dense seed | (iii) judged irrelevant |
| 5 | Renaldo Rama | Dense seed | (iii) judged irrelevant |
Table 3 (PDF p. 20).
Retrieval used 5 of the budget of passages and 8 LLM calls (5 joint assessments, 2 sufficiency checks and 1 reranking).
Retrieval Prompts
EAGR uses three prompts, all sent to the same LLM with greedy decoding and thinking disabled. The prompts below are reproduced verbatim; only line breaks are added for layout.
Joint Node Assessment and Edge Selection. One call per explored passage (Figure 9 and Figure 10). In the prompt, Previously Retrieved Facts is the accumulated evidence , Current Passage is (prefixed with its title), and Edge Labels are the passage’s unvisited descriptors. The output fields is_relevant, facts and edge_labels give , and ; the reasons field is generated to encourage deliberate selection but is not used.

Joint Prompt: Instructions (1/2)
You are helping a multi-hop retrieval system answer a query
by moving from passage to passage.
You are given a query, the facts retrieved so far, the
CURRENT passage, and the edge labels of the current
passage. Following an edge label retrieves other
passages that mention that label. The list of edge
labels may be empty.
Fill in these fields:
1. is_relevant: "Yes" if the passage helps answer any step of
the query: it gives information the query asks for, or
it identifies an entity on the path to the answer (for
example the person, place, organization or work that a
query entity points to). The passage does not need to
contain the final answer. "No" if the passage has no
connection to the query, or if it is about a different
entity that merely has the same role or the same kind of
information as an entity the query needs (for example
another person with the same occupation, or another work
with a similar title).
2. facts: if is_relevant is "Yes", list ONLY the facts from
the current passage that fill a step of the query: facts
that state what the query asks about, or facts that
identify the next entity in the chain. Leave out facts
that are true but would not change the answer, such as
other roles, other works, or other events involving the
same entities. For queries that compare entities or ask
what they have in common, include the values or
candidates needed for each compared side. Write each
fact as a short, self-contained sentence (use names, not
pronouns). Use only the current passage: do not copy
facts from the previously retrieved facts or the query,
and do not add anything from your own knowledge. If
is_relevant is "No", return [].
3. edge_labels: if is_relevant is "Yes", select the edge
labels that are likely to lead to NEW passages
containing information still needed to answer the query.
If is_relevant is "No", return [].
4. reasons: one brief reason for each selected edge label, in
the same order.
Joint Prompt: Instructions (2/2)
Rules for selecting edge labels:
- Select a label only if following it from the CURRENT
passage is likely to uncover NEW information needed for
the query. Ask: "If I follow this label, will I find
information I still need?" If not, do not select it.
- Do not select a label just because it appears in the
passage or in the query.
- Do not select broad categories or generic terms unless they
are the only path to information still needed.
- Do not select labels that only match the answer type
without leading to the answer.
- Do not select labels that would only retrieve information
already present in the previously retrieved facts.
- Copy labels exactly as they appear in the Edge Labels list.
Never invent, modify or normalize a label.
- Any number of labels from zero to all of them may be
selected. Do not force a selection.
The previously retrieved facts are context only. They are not
a retrieval source: never select labels or extract
facts from them.
Return ONLY one JSON object with exactly these keys and no
other text:
{"is_relevant": "Yes" or "No", "facts": [...], "edge_labels":
[...], "reasons": [...]}
[Four examples: Figure B.2]
Now the actual input.
Query:
{query}
Previously Retrieved Facts (read-only, never expand):
{accumulated evidence, or None}
Current Passage:
{passage title and text}
Edge Labels:
{JSON list of unvisited descriptors}
Output:Figure 9. Joint Node Assessment and Edge Selection prompt, with its runtime input template. The few-shot examples, which appear between the instructions and the input, are shown in Figure 10.

Figure 10. Few-shot examples of the joint prompt: (1) a relevant passage that identifies the next entity, with two selected edges; (2) a relevant passage that completes the evidence; (3) a passage about a different entity in the same role, judged irrelevant; (4) a relevant passage with no candidate edges, whose fact is still added to the evidence.
Sufficiency Check. At most one call per frontier (Figure 11). The prompt receives the query and the full accumulated evidence and returns the reasoning chain (required) and a judgement (is_sufficient), which is verified as described below.

Figure 11. Figure 11: Sufficiency Check prompt, with its runtime input template and few-shot examples: (1) insufficient, since one director’s nationality is not stated (the film’s country does not count), and (2) sufficient, since every step of the chain is filled from the facts.
Evidence-Guided Edge Reranking. At most one call per frontier, only when the evidence is not yet sufficient (Figure 12). The prompt receives , and and returns the ordered list .

Figure 12. Evidence-Guided Edge Reranking prompt, which orders the candidate set into .
Implementation details.
Candidate edges. The Edge Labels shown for a passage are its descriptors that have not yet been expanded. When a person’s name is selected, other spellings of the same name in that passage (e.g., robert a. stemmle and robert stemmle) are expanded as well, since a neighbouring passage may use only one of them.
Parsing. Selected labels are matched to the candidates ignoring case and whitespace, and labels that are not among the candidates are discarded. If the joint prompt’s output cannot be parsed, the passage contributes no evidence or edges, and its relevance is treated as unknown during reordering.
Fact grounding. Since the LLM may introduce information that is not in the passage, a fact is kept only if every number in it appears in the passage and at least 60% of its content words do (words of five or more letters may match on their first five letters, so that, e.g., married matches marriage). A fact is skipped if an existing fact in already states it, i.e., contains its numbers and at least 85% of its content words.
Sufficiency verification. only if the LLM answers Yes, the chain has at least one step, and every value (every item of a list value) appears in : its numbers must match exactly, and either the whole value or all of its content words must occur.
Reranking fallback. Labels missing from the reranker’s output are appended in their selection order; if the output cannot be parsed, the selection order is kept.
Evidence chain for reordering. A passage supports the reasoning chain if one of its facts contains a chain entity or value as a phrase, or contains all its numbers and at least 75% of its content words.
References
- [1]Akari Asai, Zeqiu Wu, Yizhong Wang, Avipul Sil, and Hannaneh Hajishirzi. 2024. Self-RAG: Learning to retrieve, generate, and critique through self-reflection. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2310.11511
- [2]Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. 2024a. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. Preprint, arXiv:2410.23875.arxiv.org/abs/2410.23875
- [3]Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. 2024b. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. In Advances in Neural Information Processing Systems, volume 37, pages 37665–37691. Curran Associates, Inc.arxiv.org/abs/2410.23875
- [4]Shengyuan Chen, Chuang Zhou, Zheng Yuan, Qinggang Zhang, Zeyang Cui, Hao Chen, Yilin Xiao, Jiannong Cao, and Xiao Huang. 2026. You don’t need pre-built graphs for RAG: Retrieval augmented generation with adaptive reasoning structures. Proceedings of the AAAI Conference on Artificial Intelligence, 40(36):30270–30278.arxiv.org/abs/2508.06105
- [5]Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitsky, Robert Osazua Ness, and Jonathan Larson. 2024. From local to global: A graph RAG approach to query-focused summarization. arXiv preprint arXiv:2404.16130.arxiv.org/abs/2404.16130
- [6]Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitsky, Robert Osazua Ness, and Jonathan Larson. 2025. From local to global: A graph RAG approach to query-focused summarization. Preprint, arXiv:2404.16130.arxiv.org/abs/2404.16130
- [7]Jinyuan Fang, Zaiqiao Meng, and Craig MacDonald. 2025. KiRAG: Knowledge-driven iterative retriever for enhancing retrieval-augmented generation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 18969–18985, Vienna, Austria. Association for Computational Linguistics.arxiv.org/abs/2502.18397
- [8]Zirui Guo, Lianghao Xia, Yanhua Yu, Tu Ao, and Chao Huang. 2025. LightRAG: Simple and fast retrieval-augmented generation. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 10746–10761, Suzhou, China. Association for Computational Linguistics.arxiv.org/abs/2410.05779
- [9]Bernal Jiménez Gutiérrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. 2024. HippoRAG: Neurobiologically inspired long-term memory for large language models. In Advances in Neural Information Processing Systems, volume 37, pages 59532–59569. Curran Associates, Inc.arxiv.org/abs/2405.14831
- [10]Bernal Jiménez Gutiérrez, Yiheng Shu, Weijian Qi, Sizhe Zhou, and Yu Su. 2025. From RAG to memory: Non-parametric continual learning for large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 21497–21515. PMLR.arxiv.org/abs/2502.14802
- [11]Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, pages 6609–6625, Barcelona, Spain (Online). International Committee on Computational Linguistics.
- [12]Yikuan Hu, Jifeng Zhu, Lanrui Tang, and Chen Huang. 2025. ReminDRAG: Low-cost LLM-guided knowledge graph traversal for efficient RAG. In Advances in Neural Information Processing Systems, volume 38, pages 53757–53798. Curran Associates, Inc.arxiv.org/abs/2510.13193
- [13]Yiqian Huang, Shiqi Zhang, and Xiaokui Xiao. 2025. KET-RAG: A cost-efficient multi-granular indexing framework for Graph-RAG. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, KDD ’25, pages 1003–1012, New York, NY, USA. Association for Computing Machinery.arxiv.org/abs/2502.09304
- [14]Soyeong Jeong, Jinheon Baek, Sukmin Cho, Sung Ju Hwang, and Jong C. Park. 2024. Adaptive-RAG: Learning to adapt retrieval-augmented large language models through question complexity. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 7036–7050, Mexico City, Mexico. Association for Computational Linguistics.arxiv.org/abs/2403.14403
- [15]Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen. 2023a. Struct-gpt: A general framework for large language model to reason over structured data. Preprint, arXiv:2305.09645.arxiv.org/abs/2305.09645
- [16]Zhengbao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023b. Active retrieval augmented generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 7969–7992, Singapore. Association for Computational Linguistics.
- [17]Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769–6781, Online. Association for Computational Linguistics.arxiv.org/abs/2004.04906
- [18]Chankyu Lee, Rajarshi Roy, Mengyao Xu, Jonathan Raiman, Mohammad Shoeybi, Bryan Catanzaro, and Wei Ping. 2025. NV-Embed: Improved techniques for training LLMs as generalist embedding models. In International Conference on Learning Representations, volume 2025, pages 79310–79333.arxiv.org/abs/2405.17428
- [19]Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems, volume 33, pages 9459–9474. Curran Associates, Inc.arxiv.org/abs/2005.11401
- [21]Minghan Li, Junjie Zou, Xinxuan Lv, Chao Zhang, and Guodong Zhou. 2026b. S2G-RAG: Structured sufficiency and gap judging for iterative retrieval-augmented QA. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 25846–25862, San Diego, California, United States. Association for Computational Linguistics.
- [22]Shilong Li, Yancheng He, Hangyu Guo, Xingyuan Bu, Ge Bai, Jie Liu, Jiaheng Liu, Xingwei Qu, Yangguang Li, Wanli Ouang, Wenbo Su, and Bo Zheng. 2024. GraphReader: Building graph-based agent to enhance long-context abilities of large language models. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 12758–12786, Miami, Florida, USA. Association for Computational Linguistics.arxiv.org/abs/2406.14550
- [23]Zijian Li, Qingyan Guo, Jiawei Shao, Lei Song, Jiang Bian, Jun Zhang, and Rui Wang. 2025. Graph neural network enhanced retrieval for question answering of large language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 6612–6633, Albuquerque, New Mexico. Association for Computational Linguistics.
- [24]Aixin Liu, Aoxue Mei, Bangcai Lin, Bing Xue, Bingxuan Wang, Bingzheng Xu, Bochao Wu, Bowei Zhang, Chaofan Lin, Chen Dong, et al. 2025a. Deepseek-v3. 2: Pushing the frontier of open large language models. arXiv preprint arXiv:2512.02556.arxiv.org/abs/2512.02556
- [25]Hao Liu, Zhengren Wang, Xi Chen, Zhiyu Li, Feiyu Xiong, Qinhan Yu, and Wentao Zhang. 2025b. Ho-pRAG: Multi-hop reasoning for logic-aware retrieval-augmented generation. In Findings of the Association for Computational Linguistics: ACL 2025, pages 1897–1913, Vienna, Austria. Association for Computational Linguistics.
- [26]Shengjie Ma, Chengjin Xu, Xuhui Jiang, Muzhi Li, Huaren Qu, Cehao Yang, Jixin Mao, and Jian Guo. 2025. Think-on-graph 2.0: Deep and faithful large language model reasoning with knowledge-guided retrieval augmented generation. In International Conference on Learning Representations, volume 2025, pages 52782–52806.arxiv.org/abs/2407.10805
- [27]Meta AI. 2024. Llama 3.3 70B Instruct. Model card.
- [28]Qwen Team. 2025. Qwen3 Technical Report. Preprint, arXiv:2505.09388.
- [29]Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D. Manning. 2024. RAPTOR: Recursive abstractive processing for tree-organized retrieval. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2401.18059
- [30]Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhuo Chen. 2023. Enhancing retrieval-augmented large language models with iterative retrieval-generation synergy. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 9248–9274, Singapore. Association for Computational Linguistics.arxiv.org/abs/2305.15294
- [31]Zhili Shen, Chenxin Diao, Pavlos Vougiouklis, Pascual Merita, Shriram Piramayanagam, Enting Chen, Damien Graux, Andre Melo, Roufei Lai, Zeren Jiang, Zhongyang Li, Ye Qi, Yang Ren, Dandan Tu, and Jeff Z. Pan. 2025. GeAR: Graph-enhanced agent for retrieval-augmented generation. In Findings of the Association for Computational Linguistics: ACL 2025, pages 12049–12072, Vienna, Austria. Association for Computational Linguistics.
- [32]Weihang Su, Yichen Tang, Qingyao Ai, Zhijing Wu, and Yiqun Liu. 2024. DRAGIN: Dynamic retrieval augmented generation based on the real-time information needs of large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12991–13013, Bangkok, Thailand. Association for Computational Linguistics.DOI
- [33]Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung-Yeung Shum, and Jian Guo. 2024a. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In International Conference on Learning Representations, volume 2024, pages 3868–3898.arxiv.org/abs/2307.07697
- [34]Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, and Jian Guo. 2024b. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. Preprint, arXiv:2307.07697.arxiv.org/abs/2307.07697
- [35]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022. MuSiQue: Multi-hop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539–554.DOI
- [36]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2023. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 10014–10037, Toronto, Canada. Association for Computational Linguistics.arxiv.org/abs/2212.10509
- [37]Yu Wang, Nedim Lipka, Ryan A. Rossi, Alexa Siu, Ruiyi Zhang, and Tyler Derr. 2024. Knowledge graph prompting for multi-document question answering. Proceedings of the AAAI Conference on Artificial Intelligence, 38(17):19206–19214.arxiv.org/abs/2308.11730
- [38]Chuanjie Wu, Zhishang Xiang, Yunbo Tang, Zerui Chen, Qinggang Zhang, and Jinsong Su. 2026a. Memgraph: Memory-based multi-agent system for graph retrieval-augmented generation. Preprint, arXiv:2606.00610.arxiv.org/abs/2606.00610
- [39]Chuanjie Wu, Zhishang Xiang, Yunbo Tang, Zerui Chen, Qinggang Zhang, and Jinsong Su. 2026b. Mem-GraphRAG: Memory-based multi-agent system for graph retrieval-augmented generation. arXiv preprint arXiv:2606.00610.arxiv.org/abs/2606.00610
- [40]Wenhan Xiong, Xiang Lorraine Li, Srinivasan Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oğuz. 2021. Answering complex open-domain questions with multi-hop dense retrieval. In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net.arxiv.org/abs/2009.12756
- [41]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2369–2380, Brussels, Belgium. Association for Computational Linguistics.arxiv.org/abs/1809.09600
- [42]Zukang Yang, Zixuan Zhu, and Jennifer Zhu. 2025. CuriousLLM: Elevating multi-document question answering with LLM-enhanced knowledge graph reasoning. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 3: Industry Track), pages 274–286, Albuquerque, New Mexico. Association for Computational Linguistics.arxiv.org/abs/2404.09077
- [43]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR).arxiv.org/abs/2210.03629
- [44]Xiangrong Zhu, Yuexiang Xie, Yi Liu, Yaliang Li, and Wei Hu. 2025. Knowledge graph-guided retrieval augmented generation. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 8912–8924, Albuquerque, New Mexico. Association for Computational Linguistics.arxiv.org/abs/2502.06864
- [45]Luyao Zhuang, Shengyuan Chen, Yilin Xiao, Huachi Zhou, Yujing Zhang, Hao Chen, Qingang Zhang, and Xiao Huang. 2026. LinearRAG: Linear graph retrieval augmented generation on large-scale corpora. In The Fourteenth International Conference on Learning Representations.arxiv.org/abs/2510.10114
- [46]Ziyuan Zhuang, Zhiyang Zhang, Sitao Cheng, Fangkai Yang, Jia Liu, Shujian Huang, Qingwei Lin, Saravan Rajmohan, Dongmei Zhang, and Qi Zhang. 2024. EfficientRAG: Efficient retriever for multi-hop question answering. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 3392–3411, Miami, Florida, USA. Association for Computational Linguistics.arxiv.org/abs/2408.04259