DotRAG narrows graph searches by reasoning along likely paths

Why search paths, not just keywords?

Retrieval-augmented generation, or RAG, supplies a language model with information retrieved from an external source. In GraphRAG, that information is organized as a network: entities such as people, companies or products are connected by labeled relationships. This structure can help answer questions requiring multiple steps, but a densely connected network may contain many possible paths. A system can retrieve irrelevant connections, miss useful evidence or spend considerable time exploring.

DotRAG’s central question is whether a language model can help select promising routes through the graph without having to make a costly series of decisions at every step. The researchers describe it as training-free: it does not train a new model for the retrieval task. Instead, it combines language-model guidance with graph information prepared in advance.

Preparing the map, then searching

Before answering queries, DotRAG builds an entity-and-relationship graph and creates two kinds of index. First, a language model produces a broad overview of the graph’s contents, summarizing sampled entities and patterns by entity type. Second, the system precomputes which entities are reachable from each entity within a bounded number of steps, organizing those results by distance and type. That reachability map trades extra storage and offline setup for less graph exploration during a query.

At query time, DotRAG finds possible starting entities, then presents the language model with graph-supported search options, examples of relevant relationships and the graph overview. The model ranks likely routes and can propose what relationship type or search query to follow next. Meanwhile, graph constraints narrow the candidates: instead of comparing a query against everything, the system searches among entities that are reachable at the relevant distance and fit the selected type. It can extend, rank and stop paths, then prioritize retrieved evidence within a context limit.

The evaluation tests retrieval directly on MetaQA and two STaRK settings: STaRK-MAG, an academic graph, and STaRK-Prime, a biomedical graph. These benchmarks provide question anchors and answer entities. For comparisons, the authors use the same graph material and, in their reported main setup, GPT-4o-mini and a 10,000-token retrieval budget. This helps focus the comparison on retrieval methods rather than differences in graph construction or answer-generation models. It does not make the benchmark graphs error-free: the paper notes that their source data can include extraction errors and duplicate or mislabeled entities.

Strong multi-step results—with variation

On MetaQA’s two-hop questions, DotRAG reports 97.78% retrieval recall and 51.27% F1. The best baseline in the paper’s comparison table reports 34.74% recall and 6.33% F1. Recall measures how many answer entities the retrieval found; F1 balances recall with precision, which reflects how much of the retrieved material is relevant under the study’s scoring rules.

On two-hop STaRK-MAG questions, DotRAG reports 85.07% recall and 15.75% F1. The results are not uniformly best on every measure or dataset. On two-hop STaRK-Prime, DotRAG’s recall is 48.52%, below the vector-search baseline’s 54.24%, though its F1 is higher: 12.23% versus 4.27%. The authors identify specialized terminology and complex relationships as challenges in this biomedical setting.

The paper also separates retrieval from the language model’s eventual answer. Retrieved evidence is not automatically used correctly: in the reported downstream tests, answer recall is lower than retrieval recall. For efficiency, DotRAG’s average retrieval latency on STaRK-MAG is 12.91 seconds per query, compared with 156.87 seconds for HopRAG. This is a result for the tested setup, not a guarantee for other systems or hardware.

What remains uncertain

The benchmarks do not label complete ground-truth relational paths. The authors therefore score answer entities and use a “Golden Proximity” measure as a proxy for whether intermediate entities along relevant routes were recovered. That is informative, but it is not a direct judgment that every retrieved path is correct. The STaRK evaluations use constructed subgraphs and question samples, rather than the full source graphs. Results also depend on the language model: the paper reports changes across tested backbones, with performance sometimes falling as reasoning depth increases.

These experiments establish evidence about retrieval on the selected benchmarks; they do not show that DotRAG improves every downstream application or that its generated answers are generally more reliable. The work is available as an arXiv preprint, which may not have undergone peer review. Its reported comparisons should be read in that context. The paper is at https://arxiv.org/abs/2605.18760v2.