cs.IRApr 6, 2026
SaveDOTRAG: Retrieval-Time Reasoning Along Paths
Organizations: University of Michigan
Abstract
Graph Retrieval-Augmented Generation (GraphRAG) is dominated by a retrieve-then-reason paradigm, where context is retrieved using heuristics and then reasoned over. Such methods struggle to adapt to the query-specific logic required for complex multi-hop tasks, often accumulating irrelevant context or missing correct relational paths. We propose DotRAG, a training-free GraphRAG framework that reformulates retrieval as a reasoning process over paths. Our approach generates query-conditioned constraints that guide graph exploration, prune irrelevant regions, and iteratively discover relational paths without relying on explicit step-by-step reasoning chains. We introduce Division of Thought (DOT), an abstraction that decomposes retrieval into localized search spaces and adapts the search strategy to each query. DotRAG achieves SOTA performance on MetaQA and UltraDomain, with consistent gains on multi-hop tasks, demonstrating the effectiveness of reasoning-guided retrieval.
Figures & tables
Figure 1: Neighborhood Selection Function. DotRAG grounds queries to regions of the knowledge graph via two alternative concept extraction modes. Low-level extraction uses the query and entity types in the graph schema to identify entity-aligned text spans, which are mapped to high-similarity nodes (e.g., “CEO of Tesla” → Elon, Tesla). High-level extraction uses the query and a global graph description to infer coarse-grained concepts for corpus-level queries, retrieving clusters of semantically similar nodes.
Figure 2: The LLM jointly generates (i) filters to prune the search space preemptively and (ii) intermediate/terminal constraints. The graph is then expanded up to hops, restricted to the filtered nodes. The intermediate and terminal constraints are for a later step that occurs after the search space is fully expanded.
Figure 3: Neighborhood Search (1 Iteration): Given a DOT, the LLM issues a specialized query to its constrained search region (treated as a local vector store) to retrieve the top-K candidate nodes via embeddings. For each retrieved node, we compute top-P shortest paths from each root node to its candidates (e.g. path from NG to each retrieved node). An LLM judge then determines the resulting paths included in the final context based on intermediate and terminal rules, providing a binary decision to keep or discard each discovered path.
| MetaQA | UltraDomain | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PathRAG | LightRAG | TradRAG | PathRAG | LightRAG | TradRAG | ||||||||||
| 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | CS | Mixed | CS | Mixed | CS | Mixed | |
| Compreh. | 45% | 66% | 75% | 81% | 81% | 89% | 76% | 86% | 88% | 52% | 70% | 86% | 86% | 81% | 79% |
| Logicality | 49% | 67% | 74% | 84% | 76% | 85% | 78% | 81% | 85% | 46% | 70% | 82% | 83% | 79% | 78% |
| Relevance | 64% | 71% | 75% | 74% | 72% | 81% | 73% | 78% | 84% | 42% | 66% | 69% | 75% | 71% | 74% |
| Coherence | 46% | 62% | 72% | 83% | 74% | 84% | 77% | 80% | 85% | 35% | 65% | 74% | 80% | 74% | 78% |
Table 1: Generation quality represented by DOTRAG’s win rate against existing methods. Green indicates that DOTRAG outperforms the compared method. We observe that DOTRAG consistently achieves higher win rates across the evaluated settings.
| Recall | Precision | F1 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | |
| DotRAG | 94.91 | 91.90 | 55.31 | 4.07 | 4.99 | 4.96 | 7.48 | 8.55 | 8.24 |
| PathRAG | 94.20 | 81.22 | 44.23 | 1.91 | 3.55 | 1.75 | 3.69 | 6.23 | 3.22 |
| LightRAG | 98.86 | 86.59 | 51.88 | 1.39 | 2.40 | 1.58 | 2.71 | 4.37 | 2.97 |
| TradRAG | 92.87 | 47.71 | 33.04 | 5.53 | 3.80 | 3.15 | 10.24 | 6.60 | 5.11 |
Table 2: Retrieval quality across baselines on MetaQA. Green indicates best performing method, while red indicates weakest performing baseline.
| 1Iter-DotRAG | 6Iter-DotRAG | 1Hop-DotRAG | 10Hop-DotRAG | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1-hop | 2-hop | 3-hop | 1-hop | 2-hop | 3-hop | 1-hop | 2-hop | 3-hop | 1-hop | 2-hop | 3-hop | |
| Compreh. | 48% | 52% | 68% | 49% | 44% | 51% | 54% | 73% | 58% | 69% | 54% | 51% |
| Logicality | 48% | 54% | 67% | 49% | 50% | 51% | 56% | 70% | 54% | 69% | 54% | 51% |
| Relevance | 48% | 56% | 69% | 47% | 55% | 50% | 62% | 70% | 51% | 56% | 52% | 51% |
| Coherence | 46% | 54% | 66% | 48% | 50% | 51% | 59% | 70% | 52% | 61% | 53% | 51% |
| Overall Winrate | 46% | 55% | 67% | 52% | 49% | 51% | 56% | 69% | 53% | 69% | 54% | 51% |
Table 3: Generation quality measured by the win rate of the default DOTRAG configuration against alternative configurations on MetaQA. The default setting uses 3 iterations and 3 hops. Green indicates that DOTRAG outperforms the compared configuration. Overall, the default configuration consistently achieves higher win rates across the evaluated settings.
| Recall | Precision | F1 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | 1 hop | 2 hop | 3 hop | |
| 1Iter-DotRAG | 94.17 | 82.78 | 39.79 | 5.13 | 5.14 | 4.13 | 9.17 | 8.41 | 6.52 |
| 6Iter-DotRAG | 93.23 | 91.25 | 54.76 | 3.77 | 5.46 | 5.28 | 7.02 | 8.84 | 8.32 |
| 1Hop-DotRAG | 80.00 | 44.22 | 34.82 | 3.75 | 5.45 | 3.57 | 7.02 | 8.57 | 6.04 |
| 10Hop-DotRAG | 94.59 | 84.82 | 56.40 | 2.80 | 3.53 | 3.92 | 5.24 | 6.12 | 6.33 |
Table 4: Retrieval quality across alternative configurations of DotRAG on MetaQA. Green indictates best performing method, while red indictates weakest performing baseline.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: End-to-end overview of the DotRAG pipeline: The pipeline first extracts anchor concepts from the query and maps them to graph nodes (e.g., entities such as Elon/Tesla and Andrew Ng). It then defines dot-specific objectives and expansion rules, followed by multi-hop neighborhood expansion to retrieve relevant subgraphs. A bidirectional neighborhood search identifies candidate paths between anchors, which are filtered via LLM-based relevance judgments. Finally, the system aggregates discovered paths and generates a structured response grounded in the retrieved graph evidence.
Figure 5: STAGE 1: Prompt template used to convert MetaQA knowledge graph triplets into synthetic text chunks for GraphRAG pipelines. For each target entity, the prompt aggregates its immediate neighborhood from the graph (i.e., directly connected entities and relations) and instructs the model to generate a coherent Wikipedia-style article centered on the topic. The template enforces that all supporting entities from this local neighborhood are explicitly included, ensuring faithful coverage of the underlying triplets. Additional constraints on tone, structure, formatting (e.g., bracketed entity mentions), and length promote consistency and make the resulting text suitable for retrieval-based pipelines.
Figure 6: STAGE 2: Prompt template used to generate canonical entity descriptions from the synthetic text chunks. For each entity, the model consumes a previously generated chunk (from Stage 1) and produces a concise, self-contained description grounded strictly in that context. The prompt enforces constraints on brevity, factual consistency, and encyclopedic tone, resulting in uniform entity representations suitable for downstream retrieval and reasoning tasks.
Figure 7: STAGE 3: Prompt template used to generate relationship-level descriptions from the synthetic text chunks. Given a target entity, its associated text chunk, and a set of structured triplets, the model produces concise descriptions for each relationship by grounding them strictly in the provided context. Each output explicitly links the source and target entities (via bracketed formatting) and reflects the directionality of the original triplet. This final stage ensures that all edges in the graph are assigned consistent, text-based representations, completing the transformation of the knowledge graph into a fully textualized form suitable for a GraphRAG retrieval quality evaluation.
Figure 8: Prompt used during the Neighborhood Selection Phase
Figure 9: Prompt used during the Neighborhood Construction Phase
Figure 10: Prompt used when the LLM judges the quality of a discovered path
Figure 11: Fallback Prompt for when the LLM rejected or accepted all paths before the max number of iterations have been exhausted
Figure 12: Prompt for the Generation Quality Evaluation
Figure 13: Prompt to Generate Multi-hop Tasks with UltraDomain