Repairable Evidence Sets: Swap-Based Local Search for Multi-Hop Retrieval Across Vocabulary Gaps

Answering a multi-hop question means retrieving a small set of passages that, taken together, connect the question to its answer. The hardest passage to find is usually the middle one, the "bridge." It often shares no words with the question, because it is relevant only through the other passages. Current graph-based retrievers build this set in one forward pass. They seed a graph with query-matched nodes and spread relevance outward, or they let a language model walk forward one hop at a time. Neither can later remove a passage that was picked only because it happened to share words with the question. Neither can admit a passage that looks irrelevant on its own but connects the others.

We propose treating evidence retrieval as a combinatorial set-selection problem and solving it with the kind of local search used for minimum vertex cover: decoupled drop-then-add swaps, rising weights on parts of the question that remain unmet, and an anti-cycling rule. The claim is specific. When the gold bridge passage has no word overlap with the question, a search that repeatedly swaps passages under a coverage-plus-connectivity objective will find it more often than one-shot graph propagation or greedy construction. Each step only examines the graph neighborhood of the current set, so the cost per question is set by the size of that neighborhood and not by the corpus.

Core Claim

Think of the question as a list of "facets." These are the content spans a token-free parser can extract, such as entity mentions and key noun phrases. A candidate evidence set $S$ of $k$ passages, drawn from a passage–sentence–entity graph, is scored by

$$ J(S) = \sum_{f \in F} w_f \max_{p \in S} c(p, f) \; + \; \lambda \, \mathrm{conn}(S), $$

where $F$ is the set of query facets, $c(p,f)\in[0,1]$ is the best sentence-level dense similarity between passage $p$ and facet $f$, $w_f$ is an adaptive weight on facet $f$, $\mathrm{conn}(S)$ is the fraction of passages in $S$ that share an entity with at least one other passage in $S$ (no word overlap with the question is needed), and $\lambda$ trades the two terms off.

The connectivity term gives a lexically mismatched bridge passage a way into the set: it enters because of the graph structure, not because of text matching. The swap moves give a spuriously matching passage a way out. Neither route exists in a forward-only pipeline.

The design borrows from three places. The "structure over surface text" lesson comes from RQUERY. It ranks schema rewrites by how often labels co-occur in actual triples and reports MRR 0.53 on mismatch queries, against 0.34 for an n-gram model. We move this idea from a static hidden-Markov ranking over a curated knowledge graph to an iterative search over a text graph built without an LLM. The search mechanics come from NuMVC and Two New Local Search Strategies for Minimum Vertex Cover. They split a quadratic pairwise swap into a linear drop step and a linear add step, which yields three to four times more iterations per second. NuMVC also raises weights on uncovered constraints, with decay so that old weights fade (its "forgetting"). Finally, it uses configuration checking to stop cycling.

Research Program

The graph. We build the passage–sentence–entity graph exactly as LinearRAG does: spaCy entity recognition, no LLM tokens at indexing time. Its reported indexing time on the 10M-token ATLAS-Wiki corpus is about 3,084 seconds. Keeping the identical graph means every comparison against LinearRAG isolates the retrieval procedure.

Initialization. We take the top-$k$ passages by dense query similarity.

The search loop. Each iteration has three parts.

  1. Drop step. Remove the passage whose loss costs $J$ the least. This is linear in $k$.
  2. Add step. Choose a facet that is still poorly covered, with probability proportional to its weight. Then add the passage that most increases $J$. Candidates come only from the one-hop entity neighborhood of the current set plus that facet's dense nearest neighbors, so the cost is linear in that frontier.
  3. Weight update. After each step, raise the weight of every facet whose coverage is below a threshold. When the average weight passes a ceiling, scale all weights down by a decay factor $\rho$, as NuMVC does.

The weight update is the part we expect to matter specifically for vocabulary gaps. A facet phrased in vocabulary the corpus does not share stays uncovered, so its weight keeps growing. That pushes the add step to try passages that cover it only weakly or only through the connectivity term, instead of settling on the easy facets.

Avoiding cycles. A dropped passage may not be re-added until some passage adjacent to it in the graph has entered or left $S$. This adapts configuration checking to the passage graph.

Hub entities. Very high-degree entities such as "United States" would flood the frontier. Following the observation in RWDISK that hubs should be handled separately, we treat such entities as non-expandable. We identify them with the inverse-connectivity "node specificity" score of HippoRAG.

Stopping. The search stops after a fixed iteration budget or after a set number of steps without improvement.

Answering. The final set goes to a fixed reader LLM. Retrieval itself uses no LLM calls.

How this differs from the closest work.

  • LinearRAG activates entities through query–sentence similarity, prunes them, and runs Personalized PageRank (PPR). It has no step that revisits a selected passage, and the file notes that a missed entity severs the bridge entirely. We keep its graph and replace its retrieval stage.
  • QAFD-RAG spreads continuous relevance mass through query-gated edges with a local push algorithm. It reports F1 73.42 on HotpotQA, against 58.67 for HippoRAG. Its output is a ranking derived from a diffusion, not an explicitly chosen set, and it depends on an LLM-extracted knowledge graph.
  • Call Neighbours Yourself walks a text graph with a language model that judges neighbors from title previews. It cannot backtrack, and it is blind to bridges whose previews use unfamiliar terms.
  • Evidence Tree Search searches over sentences with a learned policy and value model. It works inside a single context of up to 70k tokens, not over a corpus graph.

What our method adds to all four is reversible, discrete repair of the evidence set under an objective in which bridges can be valuable without matching the question's words.

Two further points need stating. First, the facet-coverage part of $J$ is submodular, meaning each added passage helps less as the set grows. The connectivity term breaks this property, so greedy construction loses its usual guarantee. Fujii's notion of localizability for non-submodular functions suggests restricted local search can still be analyzed in this setting; a bound is a secondary goal, not a promise. Second, parameterized guarantees of the Fellows et al. kind require sparse structure that text graphs lack. We therefore claim only per-step cost bounded by frontier size.

Baselines

Naive dense top-k retrieval. This is the "do nothing" reference: dense top-$k$ retrieval with the same encoder and the same $k$, which is also our initialization. Every gain is measured from here. HippoRAG reports graph retrieval beating ColBERTv2 by up to 20% on MuSiQue and 2WikiMultiHopQA, so we expect this baseline to be clearly weaker on multi-hop questions. It may be competitive on single-hop-like HotpotQA items.

LinearRAG. This is the strongest competitor that shares our cost profile: the same graph built with zero LLM tokens, and fixed seeding followed by PPR. LinearRAG reports 66.95% average accuracy on 2WikiMultiHopQA, against 63.00% for HippoRAG. We rerun it on our exact graph with the same encoder, reader, and $k$. Its pruning threshold gets the same validation tuning budget as our $\lambda$, $\rho$, and iteration cap.

QAFD-RAG. This is the strongest reported accuracy on HotpotQA in the file, at F1 73.42. It needs an LLM-extracted knowledge graph, so we run it on its native graph and report indexing tokens alongside accuracy. We do not force it onto ours.

For MuSiQue, no reported result was found on Lacuna for LinearRAG or QAFD-RAG, so both are rerun.

What counts as winning. Beating these baselines means higher passage recall@$k$ on the lexical-gap slice defined below, with a 95% bootstrap interval that excludes zero, together with no loss on the overlap slice. End-to-end answer F1 must also match or exceed LinearRAG at equal reader cost.

Ablations. Three ablations isolate the ingredients:

  • greedy forward construction under the same $J$, with no drops;
  • the full search without facet weighting;
  • the full search with $\lambda=0$.

The first tests whether reversibility matters. The second tests whether rising weights are what reach mismatched facets. The third tests whether bridges really enter through structure.

Why not just…?

Why not just run Personalized PageRank from good seeds, as LinearRAG and HippoRAG do? Propagation does reach bridge passages. This is the real threat, and the reported 66.95% on 2WikiMultiHopQA shows it works well. Its weakness is that it cannot demote a seed that matched the question only on the surface; it can only add mass around that seed. Running on the identical graph and seeds, the LinearRAG comparison on the lexical-gap slice decides this. If PPR matches us there, the swap mechanism adds nothing and we will report that.

Why not just build the set greedily under the same objective? Greedy construction is cheaper. If the connectivity term behaves almost submodularly in practice, greedy could match us. The no-drop ablation tests exactly this. We expect the gap to appear mainly on MuSiQue, whose filtering against disconnected shortcuts removes single-hop answers (MuSiQue reports a 30-point F1 drop for single-hop models relative to HotpotQA). On shortcut-prone HotpotQA, we would not be surprised by parity.

Why not let an LLM iterate retrieval, as IRCoT does, or walk the graph, as in Call Neighbours Yourself? These approaches can rewrite queries to cross vocabulary gaps. However, HippoRAG reports IRCoT to be 10–20 times more expensive and 6–13 times slower than single-step graph retrieval. A walker that judges frontier previews inherits exactly the surface-text blindness we target. We will include an IRCoT-style loop with the same reader as a quality-versus-cost reference, reporting LLM tokens per question. We concede it may win on raw accuracy. The claim we defend is accuracy at zero retrieval-time LLM cost.

Proposed Experiments

Datasets. We use HotpotQA (distractor and full-wiki), MuSiQue-Ans, and 2WikiMultiHopQA. The main metrics are passage recall@$k$ and answer F1.

The lexical-gap slice. On each dataset we split questions into two groups: those whose gold supporting passages include one sharing zero content words with the question (mirroring the 20.3% zero-overlap statistic in WikiQA), and the rest. We also run a controlled perturbation: replace query entity mentions with WordNet synonyms absent from the gold passages, then measure how much each method's recall drops.

Scaling. We report per-question latency and frontier size as the corpus grows from the distractor setting to the 5M-article full-wiki setting and the 10M-token ATLAS-Wiki corpus. For full-wiki HotpotQA, the original baseline joint F1 is 17.73.

Decisive checks. The first decisive check is whether the full search beats both LinearRAG and greedy-under-$J$ on lexical-gap recall while tying on the overlap slice. The second is whether removing facet weighting erases most of that gain. If both hold, then the swap-and-reweight mechanics of combinatorial local search are what carry multi-hop retrieval across vocabulary gaps, and they do so at no LLM cost during retrieval.