Triangle Closure as a Recall Repair Step for First-Stage Retrieval

Search systems and retrieval-augmented language models nearly all use a two-step pipeline. A cheap first step, either keyword matching or a fast embedding lookup, pulls a few dozen to a few thousand candidate documents out of millions. An expensive second step, typically a cross-encoder (a model that reads query and document together), then reorders those candidates. Anything the first step misses is lost for good. The most common way it misses a document is vocabulary mismatch: the relevant document describes the same thing in different words. This note proposes a cheap repair step that sits between the two stages. We precompute a sparse graph linking documents to their nearest neighbors. At query time we add to the candidate pool documents that form triangles with the retrieved ones. A triangle here means a document is linked to two retrieved documents that are also linked to each other. The intuition is that document-to-document similarity is much more reliable than query-to-document similarity, because documents are long and share vocabulary even when a short query does not. A missed document that closes many triangles with the retrieved set sits inside the same tight cluster of evidence.

The structural choice is the core claim. Simply adding the graph neighbors of retrieved documents is an old and obvious idea, and it tends to pull in "hub" documents that are similar to everything. Requiring triangles, the same principle behind k-truss communities (subgraphs in which every edge lies in at least $k-2$ triangles), should reject those hubs and loosely attached free-riders while keeping the cohesive core. If this holds, a reranker reaches its best accuracy with fewer candidates. The pool also survives query noise, such as typos, that damages embedding retrievers.

Core Claim

Fix the reranker's budget at $B$ candidates. Spending part of that budget on documents chosen by triangle support with the top first-stage results gives higher recall of relevant documents than spending it on deeper first-stage results. It also beats spending it on plain one-hop graph neighbors or on random-walk proximity. The gain should be largest exactly where first-stage retrievers are known to fail: queries with no word overlap with the answer, typo-corrupted queries, and specialized domains.

Let $S$ be the top $s$ first-stage results and $E$ the edge set of a precomputed degree-capped document graph. The triangle support of a candidate document $c \notin S$ is

$$\tau(c) = \sum_{a,b \in S,\ a<b} w_a w_b \,\mathbb{1}[(a,b),(a,c),(b,c) \in E],$$

where $w_a$ is a rank-based weight on seed $a$. With uniform weights, $\tau$ is simply the number of retrieved pairs that $c$ closes into triangles. The pool given to the reranker is $S$ plus the $B-s$ documents with the highest $\tau$.

Relation to Prior Work

The closest work is DA-RAG. It builds an entity graph plus a nearest-neighbor similarity layer and runs a k-truss peeling algorithm to remove free-riders before generation. Its truss computation, however, runs only inside a working subgraph chosen by an ordinary chunk retriever. Triangles therefore act purely as a downstream filter and cannot recover what the chunk retriever dropped. We invert that role: triangles are used to add candidates the first stage missed. Attribute Truss Community Search likewise combines truss cohesion with query relevance. It matches discrete keyword attributes, though, so it inherits the vocabulary gap we are trying to close. It also returns a community for inspection rather than a candidate pool for a ranker.

Several papers motivate the problem. CoRT trains a dual encoder on BM25's mistakes and interleaves the two rankings. This raises MS MARCO Recall@1000 from 85.7% to 94.9% and lets a BERT reranker saturate at 64 candidates instead of 256. That establishes both that recall can be bought cheaply and that the reranker's saturation point is the right metric. Dealing with Typos for BERT-based Passage Retrieval and Ranking shows dense retriever MRR@10 falling from 0.296 to 0.141 under typos, a failure of the query-to-document link that document-to-document edges do not share. University of Tsukuba Team at the TREC 2023 Deep Learning Track reports that GPT-4 reranking cannot compensate for a depleted pool.

Other work supplies methods. The free-rider argument and the evidence that triangle constraints break up diffuse, chain-like components come from The Triangle-Densest-K-Subgraph Problem and Experimental Analysis and Evaluation of Cohesive Subgraph Discovery. The first of these also constrains the design. It finds triangle methods clearly beat edge methods mainly when the graph is below 50% edge density, and they degrade on graphs with few triangles, so our graph construction has to produce triangles without becoming dense. A Graph Degeneracy-based Approach to Keyword Extraction is a text-side precedent: truss and core cohesion beat PageRank centrality because high-degree "bridge" words are not thematic. That is the same hub failure we expect from one-hop expansion.

On scale, RWDISK converts high-degree hubs into walk-terminating sinks to make disk-resident search feasible. It runs the 86M-edge LiveJournal graph in 2–4 GB of RAM and improves link prediction about fourfold. The file flags a tension here, since cutting hubs may destroy triangles. We resolve it differently: we cap degree at graph construction using mutual nearest neighbors, so no node needs special-casing at query time. The triangle count then remains well defined on the capped graph.

Research Program

The offline step builds, for each corpus, a document graph in which each document keeps edges to its top-$K$ neighbors under two views: dense embedding similarity and BM25 similarity using the document itself as the query. We retain only mutual-neighbor edges, which caps degree at $K$ and removes most hub attachments. With $K$ around 16 to 32, a corpus of $N$ documents costs $O(NK)$ storage. That is roughly a few hundred million edges for the 8.8M-passage MS MARCO collection, built once with approximate nearest-neighbor search.

At query time, scoring triangle support costs $O(s^2)$ adjacency checks among seeds plus $O(sK)$ neighbor-list reads, independent of $N$. For $s=32$ and $K=32$ this is about a thousand list reads. It is therefore compatible with the millisecond budgets CoRT reports for its own retrieval step: 4ms with approximate search, 17ms exhaustive. Neighbor lists are stored contiguously, so the step stays sequential-read friendly even when the graph lives on disk.

We will study three design questions. The first is whether edges from the lexical view and the dense view complement each other inside a triangle. We will measure whether triangles mixing both edge types are more precise than single-view triangles, since mixing views is how a document with no query overlap can still be reached. The second is how the seed count $s$ trades against expansion slots $B-s$. The third is whether a light truss-style peel over $S$ plus the expansion set (dropping candidates whose support falls below a threshold after removing low-support seeds) adds anything over raw $\tau$ ranking. We will also report, per corpus, the triangle density of the built graph. This lets us check the 50%-density caveat from the triangle-densest-subgraph work: we predict gains shrink on corpora whose graphs have low clustering.

Baselines

The naive reference point is the first-stage retriever alone, filling all $B$ slots with its own top results. We run both BM25 and BM25 interleaved with a dense dual encoder. This tells us whether the expansion slots are worth more than simply looking deeper.

The strongest existing competitor for candidate recall is CoRT-style hybrid retrieval (CoRT). It reports Recall@1000 of 94.9% and end-to-end MRR@10 of 38.4 on MS MARCO, with reranker saturation at 64 candidates. We will reproduce it on MS MARCO and apply the same procedure to BEIR. Our method is then run on top of that same hybrid first stage, with the same reranker, the same candidate budget $B$, and the same tuning budget, which is a small grid over a shared development split for every method. Beating it means reaching the hybrid's peak reranked MRR@10 at a clearly smaller $B$, or achieving higher Recall@$B$ at matched $B$ in the 32–128 range. Gains must hold across query sets, not on one dataset.

Under typos, the strongest reported point is the typo-aware dense retriever at MRR@10 0.219 on typo queries (Dealing with Typos). Recovering a meaningful part of the gap to its clean 0.300 by expansion alone would count as success.

For query rewriting, the reference is InteR, which reports MAP 50.0 on TREC DL'19 against BM25's 30.1 and HyDE's 41.8. Because it uses GPT-3.5 at query time, we compare at matched latency and also report a combined system.

For cross-encoder-only search, ADACUR reports only a relative result (up to 70% lower $k=1$ recall error than ANNCUR), and we found no absolute reported number on Lacuna for it on BEIR. We will run it at matched cross-encoder calls on SciDocs and HotpotQA, where it was evaluated.

The ablation that isolates the key ingredient is one-hop expansion over the identical capped graph. It ranks non-seed documents by how many seeds they neighbor, which is degree support rather than triangle support, and is given the same $B$. A second structural ablation replaces $\tau$ with truncated random-walk proximity from the seeds, in the style of GRANCH, on the same graph. A third removes the mutual-neighbor cap and instead converts hubs to sinks as in RWDISK, to test our resolution of the hub tension.

Why not just…?

Why not just retrieve deeper with a good hybrid retriever? This is the most serious threat. CoRT already shows hybrid pools reach 94.9% Recall@1000, so the remaining headroom at depth 1000 is small. Our claim is about small budgets, where reranker cost actually matters. The saturation-point experiment settles it directly: if the hybrid at $B=64$ already matches hybrid plus expansion at $B=64$, the proposal adds nothing and we will say so.

Why not just add the graph neighbors of retrieved documents? One-hop expansion is simpler and nearly as cheap. The evidence that degree-style signals favor hubs and free-riders comes from keyword extraction, where truss methods beat TextRank by more than 5.5 F1 (Graph Degeneracy), and from cohesive-subgraph studies. None of that evidence is about retrieval pools, however. The mutual-neighbor cap may already remove most hubs, in which case one-hop and triangle expansion could perform the same. The matched-budget one-hop ablation decides this. If triangles do not beat it, the honest conclusion is that graph expansion helps but triangles do not, and the paper's thesis changes accordingly.

Why not just rewrite the query with a language model? InteR's MAP of 50.0 on TREC DL'19 shows rewriting is strong, and RaFe (RaFe) makes trained rewriters cheaper. Rewriting still needs a generation call per query, InteR degrades beyond two rounds, and it attacks the query side, whereas expansion uses document-to-document evidence. We expect the two to be complementary rather than competing. We will report rewriting alone, expansion alone, and both together at recorded latency. If rewriting alone dominates at equal latency, expansion is only worth recommending for latency-constrained settings.

Why not just score the whole corpus with a cross-encoder via ADACUR? It removes the first-stage bottleneck by design. Its per-round full-corpus update is $O(N)$, however, while our expansion cost does not grow with $N$. On HotpotQA's more than 5 million items we will plot recall against wall-clock time for both methods to show where each wins.

Proposed Experiments

The main experiment uses MS MARCO with TREC DL'19 and DL'20 judgments, plus BEIR subsets chosen for vocabulary gap and specialized domains: TREC-COVID, SciFact, NFCorpus, FiQA-style domains where available, HotpotQA, and SciDocs. We report Recall@$B$ and reranked MRR@10 or nDCG@10 as curves over $B$ from 16 to 256, with the same cross-encoder across all systems.

The first decisive check is gap-stratified recall. We split queries by word overlap between the query and its relevant documents. The prediction is that expansion's gain over the hybrid is concentrated in the zero-overlap stratum. If the gain is uniform or concentrated in high-overlap queries, the vocabulary-gap story is wrong.

The second check is the typo-injected MS MARCO queries from the typo study. The prediction is that expansion recovers more recall than it does on clean queries, because seeds degrade gracefully while document-to-document edges are unaffected.

The third check is the triangle-versus-one-hop-versus-walk ablation at matched $B$. This is the comparison on which the triangle claim stands or falls. Alongside it we measure precision of each expansion set: the fraction of added documents that are relevant.

The fourth check is downstream generation on the DA-RAG benchmark suites. We swap DA-RAG's chunk-level first stage for the expanded pool and keep its truss peeling unchanged, then measure head-to-head win rate and token use against unmodified DA-RAG (DA-RAG). This directly tests whether making triangles act before the gatekeeper, not only after it, fixes the failure the file identifies.

Finally, we report build time, graph memory, and per-query expansion latency on MS MARCO and HotpotQA, together with the clustering coefficient of each built graph. This lets readers see whether gains track triangle availability, as the triangle-densest-subgraph results predict.