Escaping Dead Ends in Document-Graph Retrieval with Rules from Geographic Routing

Retrieval systems that walk a graph of a document collection, moving from section to paragraph to linked entity, mostly use one simple rule: step to whichever neighbor looks most relevant to the question. Wireless networks have used the same rule for decades under the name greedy geographic routing, where a packet is forwarded to the neighbor physically closest to its destination. That community has a precise account of why the rule fails. The walk stalls at a local minimum, a node where every neighbor is farther from the goal even though a path exists around an obstacle. It also has cheap fixes that need no global map. This note proposes treating dead ends in document-graph retrieval as routing voids in that sense. The plan is to measure how often they cause retrieval failures and to escape them with a deterministic two-coordinate rule modeled on hybrid greedy routing, without asking a large language model (LLM) to decide every backtrack.

The practical motivation is cost. The strongest current fix for dead ends in document graphs, Failure is Feedback (FiF), uses an LLM orchestrator to re-anchor, rewrite the subquery and escalate. FiF reports Recall@10 gains of +22.03% over the previous best graph retriever, but runs 5–6x slower than single-shot retrieval. If much of that gain comes from simply getting unstuck, a rule with almost no state should recover a large share of it at little cost. If it comes from rewriting the query, the routing view adds little. Either answer is useful, and the experiments below are built to tell the two apart.

Core Claim

Our hypothesis is that a large fraction of failed traversals in heterogeneous document graphs end at local maxima of the relevance score. These are nodes whose unvisited neighbors all score lower than the node itself, although the gold evidence is reachable. Such voids have recurring structural causes that mirror known routing pathologies. We further claim that a hybrid rule escapes them more efficiently than generic search under tight budgets on how many nodes may be read. The rule is greedy on semantic relevance, and on hitting a void it switches temporarily to greedy on an exact structural coordinate that cannot stall.

The structural coordinate rests on an observation from routing theory that becomes almost trivial for documents. Sarkar proves that any tree can be embedded in the hyperbolic plane so that greedy routing never meets a local minimum. On a tree, however, plain tree distance already has this property: from any node, the next node on the unique path to the target is strictly closer. Adding extra edges can only add ways to make progress, never remove them. Most heterogeneous document graphs contain a spanning tree, either the layout hierarchy (document, section, subsection, paragraph) or, for flat corpora, an agglomerative clustering tree of the kind Ψ-RAG builds. That tree therefore supplies a void-free fallback coordinate in which every step lowers tree distance. Lateral citation and entity edges act as shortcuts whenever they help. We use exact ancestor-path labels as the main structural coordinate and treat Sarkar-style or Lorentz embeddings as a variant to test, not a requirement. This also avoids the numerical-precision problems near the disk boundary that Sarkar notes.

Research Program

The first part of the program is a census of voids. We build graphs in two styles. The first is HippoRAG-style passage–entity graphs for MuSiQue and 2WikiMultiHopQA, following HippoRAG, with OpenIE triples, synonymy edges and passage nodes. The second is DocNavRAG-style layout hierarchies with lateral links for ScholarQA, MDAQA and LongBench-v2, following DocNavRAG. On these graphs we run pure relevance-greedy traversal with a fixed cheap scorer, a cross-encoder or dense similarity. We record every stall and classify it by cause using the gold supporting passages.

We expect three classes, each borrowed from routing. Hub-collision voids stall at high-degree or ambiguous entity nodes whose many contexts all look equally relevant. These are the text analogue of the "expanded virtual-coordinate zones" Liu found when discrete hop-count coordinates make distant nodes indistinguishable. Cavern voids occur when evidence lies within a few hops but every connecting path first dips in relevance. This is the misalignment between semantic closeness and graph distance described by Zhong et al. and Nguyen et al.. It is suggested in documents by SiReRAG's finding that similarity clusters and entity-relatedness clusters overlap only 50–68%. Disconnection voids are cases where no path exists at all. The census tells us what fraction of end-to-end retrieval failures are navigation failures and what fraction are targeting failures, where the scorer itself ranks the gold evidence low.

The second part is the escape rule. We call it hybrid void routing, after Liu's Hybrid Greedy Routing (HGR), which goes greedy in physical coordinates, switches to virtual coordinates at a void, and returns once it is closer than the void boundary. Our version has three steps:

  1. Greedy phase. The walker climbs relevance.
  2. Switch at a void. When no unvisited neighbor improves the score and a cheap sufficiency check fails, the walker stores two values. The first is the void's relevance score. The second is an escape target in the tree. To set the target, we retrieve the top-m nodes by dense similarity to the question concatenated with the text already read, which lets the bridge entity from hop one inform hop two. The target is the tree median of those nodes.
  3. Structural phase. The walker moves greedily on tree distance to the target, using lateral edges when they reduce that distance. It returns to relevance-greedy as soon as it reaches a node scoring above the stored void score.

The per-query state is two numbers plus a visited set, against a full search frontier for best-first search or an LLM-maintained memory for FiF. The structural phase is guaranteed to terminate, because tree distance strictly decreases at each step. No LLM call is made during navigation. A fixed reader is used only to answer at the end.

The third part asks whether the structure itself earns its place. The question is whether walking through the tree to the escape target, collecting the parent sections and siblings on the way, helps compared with simply jumping to the target. DocNavRAG's gains from vertical navigation suggest it might. Section-level context is plausibly what makes a retrieved paragraph interpretable, but this must be measured, not assumed.

Baselines

The naive reference point is pure relevance-greedy traversal with the same scorer and graph. It reveals the raw void rate, and every method must beat it.

The flat reference is dense passage retrieval in the ColBERTv2 style. HippoRAG reports it trailing graph retrieval by up to 20% on MuSiQue and 2WikiMultiHopQA. It is run on the same passages with the same top-k.

The global-graph competitor is HippoRAG's Personalized PageRank (PPR), a random walk that keeps restarting at the question's entities. It never gets stuck because it never walks greedily, so it tests whether local routing is worth anything at all. It runs on the identical graph, and we compare it on recall at equal output size and on wall-clock time.

The most dangerous simple competitor is best-first search: a priority queue over the frontier that always expands the most relevant unvisited node. It also escapes every void. We give it the same scorer, the same graph and exactly the same budget of node reads, at B = 5, 10, 20 and 50. Beating it means higher support recall at matched B, concentrated in the cavern-void slice of the census.

The strongest existing methods are FiF on the multimodal benchmarks (MultimodalQA, MMCoQA, WebQA) and DocNavRAG on the long-document benchmarks. For FiF, the file reports only relative figures: +22.03% Recall@10 and +18.60% MRR@10 over LILAC, and +16.37% EM downstream. No reported absolute Recall@10 was found on Lacuna for FiF. For DocNavRAG, the file reports a 7.8% average answer-quality gain over its strongest baseline, and no reported absolute score on ScholarQA or MDAQA was found on Lacuna. We therefore rerun both with their released prompts and the same reader LLM. We report recall and EM alongside LLM calls, tokens and latency. Success means retaining at least most of FiF's recall gain over pure greedy at a small fraction of its LLM calls. Beating it outright is not the bar.

Three ablations isolate the key ingredient. The first replaces the structural escape with a uniformly random neighbor. The second replaces the structural walk with a direct jump to the escape target. The third swaps exact tree labels for a Sarkar hyperbolic embedding and for HypRAG-style Lorentz text embeddings.

Why not just…?

Why not just use best-first or beam search? This is the real threat. Any method that keeps a frontier escapes local maxima without any routing theory. Our bet is narrower: under tight read budgets, best-first spends reads on the flat, high-scoring neighborhood around a hub-collision or cavern void, while a directed structural escape leaves it in a few steps. If matched-budget comparisons show no gap, the routing contribution reduces to the void census. We would report that, together with the conclusion that frontier state, not geometry, is what matters.

Why not just run Personalized PageRank over the whole graph? PPR avoids voids by spreading probability globally. HippoRAG itself names PPR on million-node graphs as an unresolved bottleneck, and Chen et al. contrast global path computation with local rules that cost only the node's degree per step. The latency-versus-graph-size curve in our experiments decides whether the local rule's cost advantage holds at no recall loss.

Why not just let an LLM agent backtrack, as in FiF or IRCoT? It works, and FiF shows it is robust, losing under 2% Recall@10 with half the links removed. But it is 5–6x slower than single-shot retrieval, and HippoRAG measures IRCoT at 10–20x the cost of graph retrieval. The census settles which part of FiF matters. If most failures are cavern or hub voids, a deterministic escape should capture most of FiF's gain. If most are targeting failures that only query rewriting fixes, FiF's LLM step is necessary, and our method should be positioned as a cheap first stage before it.

Why not just retrieve flatly in hyperbolic space, as in HypRAG? HypRAG shows that hyperbolic embeddings reduce confusion with sibling and parent passages (96.3% vs 81.0% on MeSH). But it searches isolated chunks and never traverses the graph, so it cannot follow a bridge entity from one hop to the next. We include it as a flat baseline and as an embedding variant inside our rule, to see whether its geometry helps routing beyond exact tree labels.

Proposed Experiments

The first decisive check is the census itself. If voids account for only a small share of failed MuSiQue and long-document traversals, the premise is wrong, and the program stops at a negative diagnostic result. That result would still be worth reporting, because it would show that dead-end handling is the wrong target for cheap fixes. MuSiQue is the main multi-hop testbed because its construction removes single-hop shortcuts: MuSiQue reports a 30-point F1 drop for single-hop models relative to HotpotQA, and human performance of 78.0 answer F1 and 93.9 support F1. HotpotQA is reported only as a secondary benchmark because of its known shortcuts.

The second check is the matched-budget comparison against best-first search, broken down by void class. Our method should win specifically on cavern and hub voids and tie elsewhere. A uniform win or a uniform tie would both undercut the mechanism we propose.

The third check is the jump-versus-walk ablation on the long-document benchmarks. It shows whether structural context, not just the escape target, improves answers from the fixed reader.

Two robustness tests follow FiF's protocol and DocNavRAG's acknowledged weakness. The first removes 10–50% of lateral links at random. The second strips headers so the backbone must come from agglomerative clustering, not from document layout. In every experiment we report support recall, answer F1 or EM with a fixed reader, node reads, LLM calls and latency together, so that accuracy is never claimed apart from cost.