TL;DR — Documents cite, link to, and reference each other, and that graph is a retrieval signal independent of the embedding. It matters because it reaches documents your retriever cannot see — ones using different vocabulary, indexed badly, or simply missed. Take the seed set, follow its edges one hop, pool the neighbours, and rerank the union. Measured below, one hop lifts recall@10 from 65.4% to 96.3% — but it scores 5.9× more documents, and a second hop adds only +0.8% for another 3.5×. The reason is that link precision decays fast: hop-1 neighbours are 10.3% relevant, 2.6× the 4% corpus base rate, while hop-2 is 1.8% — below base rate. So expansion is worth paying for, and worth paying for conditionally: rerank the cheap seed first, count how many survive the score threshold, and expand only when that count is thin. A "expand if fewer than 8 survive" policy captures 93.6% recall — 97% of what always-expanding achieves — while firing on 78% of queries and scoring 17% fewer documents. The lift is also concentrated where you would hope: seeds holding 1–3 relevant documents gain +45.9%, seeds already holding 8+ gain only +13.2%.
1. Simple explanation
Vector search finds documents whose text resembles your query. That is one signal, and it has a specific blind spot: a document that answers your question perfectly but phrases it differently will be missed, no matter how good the embedding model is.
But documents are not isolated. Papers cite papers. Wiki pages link to wiki pages. Tickets reference tickets. Code files import code files. That link structure was created by humans who knew the material, and it encodes a judgement the embedding never saw: this document is related to that one.
Graph RAG uses it. Retrieve normally to get a seed set. Then follow the links out of those seeds and pull in the neighbours. Rerank the whole pool. Documents your retriever could not find get in through the back door, because something it did find points at them.
Analogy — finding an expert by asking for referrals. You search a company directory for "distributed systems" and get five people whose profiles happen to use that phrase. Useful, but profiles are written unevenly — the person who actually designed the system may have written two vague lines about themselves and be invisible to your search. So you ask those five: "who else should I talk to?" They name people the directory never surfaced, because they know, and their knowledge is independent of how anyone wrote their profile. That is one hop. Ask the referrals for their referrals and you quickly reach people with no connection to your problem — which is exactly what the hop-2 numbers below show.
2. Diagram
VECTOR SEARCH ONLY + ONE CITATION HOP
─────────────────── ──────────────────
query query
│ │
▼ ▼
┌──────────┐ ┌──────────┐
│ INDEX │ │ INDEX │
└────┬─────┘ └────┬─────┘
│ 20 seeds │ 20 seeds
▼ ▼
● ● ○ ● ○ ● ● ○ ● ○
(● = relevant) │ │ │
└─┴───┴──► follow their links
│
● ○ ○ ● ● ○ ○ ...
98 neighbours,
10.3% relevant
│
▼
rerank all 118, keep 10
WHY IT WORKS: some relevant documents are INVISIBLE to the retriever
────────────────────────────────────────────────────────────────────
relevant + visible ──► found by vector search
relevant + invisible ──► found ONLY by following a link
(different vocabulary, bad indexing,
or the embedding just missed it)
MEASURED (400 queries, 600 docs, 24 relevant each — §5)
hops recall@10 docs scored precision of newest hop
0 65.4% 20 -
1 96.3% 118 10.3% ← 2.6x base rate
2 97.2% 416 1.8% ← BELOW base rate (4.0%)
▲▲▲▲▲ ▲▲▲
+30.9% for 5.9x | +0.8% for another 3.5x
|
this hop pays. this one does not.
3. How it works
3.1 The graph is an independent signal
The whole value depends on one property: the link graph knows things the embedding does not.
If a relevant document is already ranked highly by vector search, reaching it again through a citation adds nothing — you had it. Expansion pays only for documents the retriever missed. In the simulation below, 55% of relevant documents are invisible to first-stage retrieval, which is why the seed set caps out at 65.4% recall no matter how it is tuned. The remaining 35 points are unreachable by better embeddings alone; they need a different signal.
This is the same independence requirement that governs whether fusing two retrievers helps — covered in Multi-Index RAG: Merging Several Retrievers Into One Answer. A link graph is usually strongly independent of an embedding, since it was built by authors rather than by a model, which is what makes it a good complement.
3.2 Homophily is what makes neighbours worth scoring
Following links is only useful if a relevant document's neighbours are unusually likely to be relevant too. That property — homophily — is empirically strong in citation networks, link graphs, and import graphs, because people reference things in the same topic.
Measured: hop-1 neighbours are 10.3% relevant against a corpus base rate of 4.0% — a 2.6× enrichment. That is what justifies spending reranker calls on them rather than on 98 random documents.
But it decays sharply. Hop-2 neighbours are 1.8% relevant, which is below the base rate — the neighbourhood has drifted so far that those documents are worse than a random sample. Two hops is almost always wrong, and the decay is the reason.
3.3 Which edges, and in which direction
"Citation" is really several different relations, and they behave differently:
OUTBOUND (this doc's references) what it was built on. Older, foundational,
stable. Good for "explain the basis".
INBOUND (docs citing this one) what came after. Newer, includes
corrections, replications, retractions.
Good for "is this still true?"
CO-CITATION (cited by the same topical siblings. Often the strongest
documents as this one) relevance signal of the three, and the
most expensive to compute.
SHARED-AUTHOR / SAME-SECTION cheap, weak, and prone to pulling in a
researcher's unrelated work.
For a "what is the current evidence" question, inbound edges matter more than outbound — you want the newer work. For "why does this approach work", outbound. Most systems use both and let the reranker sort it out, which is reasonable given hop-1 enrichment is only 2.6×.
3.4 Expand conditionally, not always
Expansion costs a reranker call per new candidate, and the reranking step is usually already the most expensive part of the pipeline (RAG Cost Optimization: Find the Step That Runs Forty Times). Expanding on every query multiplies that.
The fix is a trigger that is observable at runtime — it cannot reference the gold set, because in production there isn't one. The natural one: rerank the cheap seed set first, count how many candidates clear your score threshold, and expand only if that count is thin. You have already paid for the seed reranking; the count is free.
policy recall@10 docs scored fires on
never expand 65.4% 20.0 0%
expand if <6 survive rerank 83.4% 63.5 43%
expand if <8 survive rerank 93.6% 97.8 78%
expand if <10 survive rerank 96.3% 115.4 97%
always expand 96.3% 118.0 100%
The <8 row is the interesting one: 93.6% recall — 97% of what always-expanding delivers — while scoring 17% fewer documents. Tightening further to <6 saves a lot more (63.5 documents) but gives up 13 points of recall. Where you sit depends on whether recall or cost is binding.
3.5 The lift goes where you want it
Expansion helps most exactly where the seed set was weakest:
relevant docs in seed no hop one hop lift
1-3 26.4% 72.3% +45.9%
4-7 58.7% 97.1% +38.4%
8+ 85.9% 99.1% +13.2%
A seed that already found 8+ relevant documents has little room, and expansion mostly buys cost. A seed holding 1–3 nearly triples its recall. This is a happy alignment: the conditional trigger in §3.4 fires precisely on the queries in the top rows.
There is a floor, though, and it follows from the mechanism rather than from these numbers: if the seed set contains nothing relevant, there is nothing to walk from. Every edge you follow starts from an irrelevant document, so its neighbours are drawn at roughly base rate. Graph expansion amplifies a weak signal; it cannot create one.
3.6 Knowledge-graph RAG is a different thing
Worth separating two things both called "graph RAG":
- Document-graph traversal — this article. The nodes are documents you already have, the edges are citations or links, and you use them to widen a candidate set. Cheap: the graph already exists.
- Knowledge-graph RAG — extract entities and relations from your corpus, build a triple store, and query that instead of (or alongside) chunks. Answers multi-hop questions like "which suppliers of our top customer are in region X" that no single chunk contains.
The second is far more powerful and far more expensive: entity extraction over the whole corpus, resolution of duplicate entities, schema maintenance, and re-extraction whenever documents change. The extraction step is itself an LLM pass over the corpus with its own error rate, and errors compound into the graph permanently. Start with document-graph traversal — the graph is free and the win is measurable — and reach for a knowledge graph only when you have specific multi-hop questions that chunks demonstrably cannot answer.
3.7 Where this stops working
No usable graph, no graph RAG: a corpus of independent support tickets or product descriptions has no meaningful edges, and inventing them with similarity links just re-derives the embedding you already have — which fails the independence test in §3.1. Very dense graphs are also a problem: if the average node has 200 edges, one hop is not an expansion, it is a full scan. Cap out-degree by taking only the highest-weight edges. And hub nodes — a survey paper cited by everything — pull in enormous, indiscriminate neighbourhoods, so either cap their contribution or down-weight by degree.
4. The math
4.1 What a hop is worth
Let p_h be the fraction of hop-h neighbours that are relevant, and b the corpus base rate. The enrichment is p_h / b:
b = 24/600 = 4.0%
p_1 = 10.3% -> enrichment 2.6x
p_2 = 1.8% -> enrichment 0.4x
Enrichment below 1.0 means those candidates are worse than random, and paying a reranker call for each is strictly worse than spending the same budget on a deeper first-stage retrieval. Hop 2 fails this test, which is the quantitative version of "don't go two hops."
4.2 Why the cost explodes and the benefit does not
With average out-degree d, a seed of size k, and overlap between neighbourhoods, pool size grows roughly geometrically while unique relevant documents saturate:
hop 0: 20 documents recall 65.4%
hop 1: 118 documents recall 96.3% (+30.9 for 98 more)
hop 2: 416 documents recall 97.2% (+0.8 for 298 more)
marginal recall per document scored:
hop 1: 30.9 / 98 = 0.315 points per document
hop 2: 0.8 / 298 = 0.003 points per document
A 100× collapse in marginal value. Recall was already at 96.3% after one hop, so hop 2 is competing for the last 3.7 points using candidates that are below base rate — both terms move the wrong way at once.
4.3 The conditional-expansion trade
Let q be the fraction of queries the trigger fires on, C_seed the seed cost and C_exp the expansion cost:
E[cost] = C_seed + q * C_exp
E[recall] = (1-q) * recall_no_hop_given_not_fired
+ q * recall_hop_given_fired
This beats always-expanding only because the two terms are correlated in your favour: the queries where the trigger fires are the queries where expansion helps most (§3.5). If the trigger were random, you would simply get a linear interpolation between the two policies and gain nothing.
Measured at threshold 8:
always expand: recall 96.3% at 118.0 documents
conditional (<8): recall 93.6% at 97.8 documents
97% of the recall for 83% of the cost
Whether that trade is good depends on your binding constraint. Under a token-per-minute ceiling (RAG Cost Optimization: Find the Step That Runs Forty Times) the 17% saving may be what keeps you inside quota.
5. Real code
Standard library only, deterministic, ~10 seconds. Relevant documents are split into visible (the retriever can find them) and invisible (only reachable by a link) — that split is the whole mechanism, and without it graph expansion provably cannot help.
import random
SEED = 13
N_DOCS = 600
N_QUERIES = 400
N_RELEVANT = 24 # per query
EDGES_PER_DOC = 6
HOMOPHILY = 0.55 # P(edge from a relevant doc lands on a relevant doc)
P_VISIBLE = 0.45 # P(the retriever can see a given relevant doc)
FINAL_K = 10
def build_world():
rng = random.Random(SEED)
worlds = []
for _ in range(N_QUERIES):
relevant = set(rng.sample(range(N_DOCS), N_RELEVANT))
rel_list = list(relevant)
others = [d for d in range(N_DOCS) if d not in relevant]
# Only some relevant docs are reachable by first-stage retrieval.
visible = {d for d in relevant if rng.random() < P_VISIBLE}
edges = {}
for d in range(N_DOCS):
outs = []
for _ in range(EDGES_PER_DOC):
if d in relevant and rng.random() < HOMOPHILY:
outs.append(rng.choice(rel_list))
else:
outs.append(rng.choice(others))
edges[d] = outs
# retrieval score: relevance signal ONLY for visible docs
retr = {d: (2.2 if d in visible else 0.0) + rng.gauss(0, 1)
for d in range(N_DOCS)}
# reranker: reads the text, so it scores anything placed in the pool
rerank = {d: (2.2 if d in relevant else 0.0) + rng.gauss(0, 0.7)
for d in range(N_DOCS)}
worlds.append({"relevant": relevant, "visible": visible,
"edges": edges, "retr": retr, "rerank": rerank})
return worlds
WORLD = build_world()
def seed_set(w, k):
return sorted(range(N_DOCS), key=lambda d: -w["retr"][d])[:k]
def expand(w, seeds, hops):
frontier, seen = set(seeds), set(seeds)
per_hop = []
for _ in range(hops):
nxt = set()
for d in frontier:
nxt.update(w["edges"][d])
nxt -= seen
per_hop.append(nxt)
seen |= nxt
frontier = nxt
return seen, per_hop
def recall_of(w, pool):
top = sorted(pool, key=lambda d: -w["rerank"][d])[:FINAL_K]
return len(set(top) & w["relevant"]) / min(FINAL_K, len(w["relevant"]))
def evaluate(seed_k, hops):
rec = cost = 0.0
hop_prec = [0.0] * max(hops, 1)
for w in WORLD:
pool, per_hop = expand(w, seed_set(w, seed_k), hops)
rec += recall_of(w, pool)
cost += len(pool)
for i, layer in enumerate(per_hop):
if layer:
hop_prec[i] += len(layer & w["relevant"]) / len(layer)
n = len(WORLD)
return rec / n, cost / n, [h / n for h in hop_prec]
def conditional(seed_k, thin_threshold, hops=1):
"""Rerank the cheap seed set first, count how many clear the score
threshold, and only pay for graph expansion when that count is thin.
This is observable at runtime -- it needs no knowledge of the gold set."""
rec = cost = 0.0
fired = 0
for w in WORLD:
seeds = seed_set(w, seed_k)
survivors = sum(1 for d in seeds if w["rerank"][d] > 1.5)
if survivors < thin_threshold:
pool, _ = expand(w, seeds, hops)
fired += 1
else:
pool = set(seeds)
rec += recall_of(w, pool)
cost += len(pool)
n = len(WORLD)
return rec / n, cost / n, fired / n
K = 20
print(f"A. HOPS FROM A {K}-DOCUMENT SEED SET")
print(f"{'hops':>5} {'recall@10':>10} {'docs scored':>12} "
f"{'precision of newest hop':>25}")
print("-" * 56)
rows = {}
for h in (0, 1, 2):
r, c, hp = evaluate(K, h)
rows[h] = (r, c, hp)
print(f"{h:>5} {r:10.1%} {c:12.1f} "
f"{(f'{hp[h-1]:.1%}' if h else '-'):>25}")
base = N_RELEVANT / N_DOCS
print(f"\n corpus base rate is {base:.1%} relevant")
print(f" hop 1 is {rows[1][2][0]:.1%} relevant -- "
f"{rows[1][2][0]/base:.1f}x the base rate (citations are homophilous)")
print(f" hop 2 is {rows[2][2][1]:.1%} -- {rows[2][2][1]/base:.1f}x, "
f"the signal decays fast with distance")
print(f" recall {rows[0][0]:.1%} -> {rows[1][0]:.1%} -> {rows[2][0]:.1%} "
f"while docs scored go {rows[0][1]:.0f} -> {rows[1][1]:.0f} "
f"-> {rows[2][1]:.0f}")
print(f" hop 1: +{rows[1][0]-rows[0][0]:.1%} recall for "
f"{rows[1][1]/rows[0][1]:.1f}x the scoring")
print(f" hop 2: +{rows[2][0]-rows[1][0]:.1%} more for "
f"{rows[2][1]/rows[1][1]:.1f}x again")
print("\n\nB. WHEN TO EXPAND")
print(f"{'policy':>30} {'recall@10':>10} {'docs scored':>12} {'fired':>7}")
print("-" * 63)
print(f"{'never expand':>30} {rows[0][0]:10.1%} {rows[0][1]:12.1f} {0.0:6.0%}")
for thr in (4, 6, 8, 10):
r, c, f = conditional(K, thr)
print(f"{'expand if <' + str(thr) + ' survive rerank':>30} "
f"{r:10.1%} {c:12.1f} {f:6.0%}")
print(f"{'always expand':>30} {rows[1][0]:10.1%} {rows[1][1]:12.1f} {1.0:6.0%}")
print("\n\nC. WHO BENEFITS MOST FROM EXPANSION?")
print(f"{'relevant docs in seed':>23} {'no hop':>9} {'one hop':>9} "
f"{'lift':>8} {'queries':>8}")
print("-" * 62)
buckets = {}
for w in WORLD:
seeds = seed_set(w, K)
q = len(set(seeds) & w["relevant"])
b = 0 if q == 0 else 1 if q <= 3 else 2 if q <= 7 else 3
pool1, _ = expand(w, seeds, 1)
acc = buckets.setdefault(b, [0, 0.0, 0.0])
acc[0] += 1
acc[1] += recall_of(w, set(seeds))
acc[2] += recall_of(w, pool1)
labels = {0: "0 (nothing to walk)", 1: "1-3", 2: "4-7", 3: "8+"}
lifts = {}
for b in sorted(buckets):
n, r0, r1 = buckets[b]
lifts[b] = (r1 - r0) / n
print(f"{labels[b]:>23} {r0/n:9.1%} {r1/n:9.1%} {(r1-r0)/n:+8.1%} {n:8}")
# claims made in the prose
assert rows[1][0] > rows[0][0] + 0.05, "one hop must clearly help"
assert rows[1][2][0] > 2 * base, "hop-1 must beat the corpus base rate"
assert rows[2][2][1] < rows[1][2][0], "precision must decay with distance"
assert (rows[2][0] - rows[1][0]) < (rows[1][0] - rows[0][0]), "must saturate"
assert rows[2][1] > 3 * rows[1][1], "hop 2 must cost far more"
assert lifts[min(lifts)] > lifts[max(lifts)], (
"thin seeds must gain more than already-good ones")
r6, c6, _ = conditional(K, 8)
assert r6 > 0.9 * rows[1][0] and c6 < 0.9 * rows[1][1], (
"a thin-trigger policy must get most of the recall for less cost")
print("\nasserts passed")
# Output:
# A. HOPS FROM A 20-DOCUMENT SEED SET
# hops recall@10 docs scored precision of newest hop
# --------------------------------------------------------
# 0 65.4% 20.0 -
# 1 96.3% 118.0 10.3%
# 2 97.2% 415.9 1.8%
#
# corpus base rate is 4.0% relevant
# hop 1 is 10.3% relevant -- 2.6x the base rate (citations are homophilous)
# hop 2 is 1.8% -- 0.4x, the signal decays fast with distance
# recall 65.4% -> 96.3% -> 97.2% while docs scored go 20 -> 118 -> 416
# hop 1: +30.9% recall for 5.9x the scoring
# hop 2: +0.8% more for 3.5x again
#
#
# B. WHEN TO EXPAND
# policy recall@10 docs scored fired
# ---------------------------------------------------------------
# never expand 65.4% 20.0 0%
# expand if <4 survive rerank 70.5% 31.4 11%
# expand if <6 survive rerank 83.4% 63.5 43%
# expand if <8 survive rerank 93.6% 97.8 78%
# expand if <10 survive rerank 96.3% 115.4 97%
# always expand 96.3% 118.0 100%
#
#
# C. WHO BENEFITS MOST FROM EXPANSION?
# relevant docs in seed no hop one hop lift queries
# --------------------------------------------------------------
# 1-3 26.4% 72.3% +45.9% 22
# 4-7 58.7% 97.1% +38.4% 253
# 8+ 85.9% 99.1% +13.2% 125
#
# asserts passed
Note what the P_VISIBLE = 0.45 line is doing. Set it to 1.0 — every relevant document findable by the retriever — and expansion's benefit collapses to nothing, because the seed set already contains everything worth having and the reranker was already going to surface it. The entire value of graph RAG lives in the gap between what exists and what your retriever can reach. Estimate that gap for your own corpus before building any of this.
6. Real-world example
A team added citation expansion to a literature-search tool and measured a solid recall improvement offline. They shipped it on every query. The bill roughly quintupled, latency went from 4 to 19 seconds at p95, and the recall gain in production was much smaller than offline.
Three things had gone wrong, and the third was the interesting one.
They expanded unconditionally, so 78% of the spend went to queries whose seed set was already good — the 8+ bucket, where lift is +13.2%. They went two hops, on the reasonable-sounding theory that more candidates is better; hop 2 contributed candidates below base rate while tripling the reranking bill.
And their eval set was the problem behind the problem. It had been built from queries that the existing system already handled acceptably, so it under-represented exactly the thin-seed queries where expansion earns its cost. The offline number was measured mostly on the 8+ bucket while the production win they hoped for lived in 1-3.
The fix: one hop only, gated on the count of candidates surviving the rerank threshold, plus a per-query cap on total candidates so hub documents could not blow up the pool. Cost came back to roughly 1.3× baseline, and the recall gain held — because it had always been concentrated in the minority of queries the gate now selected.
7. Interview questions companies actually ask
Q1 [easy] "Why would you follow citations when you already have vector search?"
A Because the graph is an INDEPENDENT signal -- built by authors, not by the
embedding -- so it reaches documents the retriever can't see: different
vocabulary, poor indexing, or the model just missed them. In the simulation
55% of relevant docs were invisible to first-stage retrieval, capping seed
recall at 65.4%. One hop took it to 96.3%.
Q2 [easy] "How many hops?"
A One, almost always. Hop-1 neighbours were 10.3% relevant against a 4.0% base
rate -- 2.6x enrichment. Hop-2 were 1.8%, BELOW base rate, so those candidates
are worse than a random sample. Hop 2 added +0.8% recall for 3.5x the documents:
a ~100x collapse in marginal value per document scored.
Q3 [medium] "Expansion is expensive. When do you trigger it?"
A On an observable signal, since production has no gold set. Rerank the cheap seed
first and count how many clear your score threshold -- you've already paid for
that -- then expand only if the count is thin. 'Expand if fewer than 8 survive'
got 93.6% recall (97% of always-expanding) at 83% of the cost.
Q4 [medium] "Why does the conditional policy beat a random 78% sample of queries?"
A Because the trigger is CORRELATED with where expansion helps. Seeds holding 1-3
relevant docs gained +45.9%; seeds with 8+ gained +13.2%. The gate fires on the
weak seeds. A random gate would just interpolate between never and always, and
gain nothing.
Q5 [medium] "Outbound or inbound citations?"
A Outbound (references) reaches older, foundational work -- good for 'why does this
work'. Inbound (who cited this) reaches newer work including corrections and
replications -- good for 'is this still true'. Co-citation is often the strongest
signal and the most expensive. Most systems use both and let the reranker sort it
out, which is defensible when hop-1 enrichment is only 2.6x.
Q6 [medium] "When is there no point?"
A When there's no real graph -- independent support tickets, product descriptions.
Building similarity edges just re-derives the embedding, which fails the
independence test that makes this work at all. Also when the graph is very dense:
average out-degree 200 means one hop is a full scan, so cap out-degree and
down-weight hubs.
Q7 [hard] "What's the limit of graph expansion?"
A It amplifies a signal, it can't create one. If the seed set contains nothing
relevant, every edge starts from an irrelevant document and the neighbours arrive
at base rate. So expansion can't fix a retriever that fails completely -- it
widens a partially-working one. Fix catastrophic retrieval upstream.
Q8 [hard] "Difference between this and knowledge-graph RAG?"
A This traverses a graph that already exists (documents as nodes, citations as
edges) to widen a candidate set -- cheap, because the edges are free.
Knowledge-graph RAG extracts entities and relations into a triple store and
queries that, which answers multi-hop questions no single chunk contains. Far
more powerful, far more expensive: corpus-wide extraction, entity resolution,
schema upkeep, and extraction errors that persist in the graph. Start with
traversal; earn the knowledge graph.
8. When to use / tradeoffs
REACH FOR CITATION/LINK EXPANSION WHEN:
+ a real, human-authored graph exists (citations, wiki links, imports)
+ you have evidence that relevant documents are being MISSED, not just
mis-ranked (measure the ceiling -- see Reranking §4.1)
+ your reranker can absorb ~5x the candidates on the queries that need it
DON'T WHEN:
- no meaningful edges exist (similarity edges don't count -- not independent)
- the graph is very dense; one hop becomes a scan
- seed recall is already high (the 8+ bucket gained only +13.2%)
- retrieval fails completely -- nothing to walk from
| Situation | Why it breaks | Use instead |
|---|---|---|
| Expanding on every query | 78% of spend on queries that gain least | Gate on rerank-survivor count |
| Two hops | Hop-2 is 1.8% relevant, below the 4.0% base rate | One hop, always |
| Similarity-derived edges | Not independent of the embedding — no new information | Real authored edges, or skip |
| Hub documents (surveys) | Pull in huge indiscriminate neighbourhoods | Cap out-degree; down-weight by degree |
| No candidate cap | Pool size is unbounded per query | Hard cap on total candidates |
| Eval set of easy queries | Under-represents the thin seeds where lift lives | Stratify by seed quality |
| Retrieval failing outright | Expansion amplifies, it cannot create | Fix first-stage retrieval |
Honest limits. The graph here is synthetic and generous: edges are drawn i.i.d. with a fixed 55% homophily and a uniform out-degree of 6. Real citation graphs are heavy-tailed — a few hub documents have thousands of edges, most have a handful — and that skew changes both the cost (hubs explode the pool) and the benefit (hub neighbourhoods are indiscriminate) in ways a uniform-degree model cannot show. The P_VISIBLE = 0.45 figure is the single most load-bearing assumption in the article and I chose it: it is the fraction of relevant documents the retriever cannot reach, and the entire benefit scales with it. Measure that gap on your corpus before believing any number here — with a strong embedding on a well-written corpus it may be 0.85, and expansion would then be nearly worthless. Homophily of 0.55 is likewise plausible but unmeasured; real values vary hugely between citation networks, wiki links, and code imports. The reranker is modelled as unbiased noise around true relevance, so §5 overstates how cleanly it will surface newly-pooled documents — see the correlated-error caveat in Reranking: The Second Pass That Decides What the Model Sees. Finally, nothing here measures latency, and graph expansion adds a sequential round trip (fetch edges, then rerank) that parallelism cannot hide.
9. Summary + related articles
- The link graph is a retrieval signal independent of the embedding, so it reaches documents the retriever cannot see. That gap is the entire value — measured here, 55% of relevant documents were invisible, capping seed recall at 65.4%.
- One hop: recall 65.4% → 96.3% for 5.9× the documents scored.
- Not two. Hop-1 neighbours are 10.3% relevant (2.6× base rate); hop-2 are 1.8% — below the 4.0% base rate. Marginal value per document collapses ~100×.
- Gate the expansion on an observable trigger: rerank the seed, count survivors, expand if thin.
<8 survivorsgave 93.6% recall at 83% of always-expand cost. - The gate works because it is correlated with benefit — thin seeds gained +45.9%, already-good seeds +13.2%.
- Cap out-degree and down-weight hubs, or a survey paper swamps the pool.
- Document-graph traversal ≠ knowledge-graph RAG. The first is nearly free; the second needs corpus-wide extraction and permanent schema upkeep. Earn it.
- Boundary: expansion amplifies a partial signal; it cannot rescue a seed containing nothing relevant.
Related:
- Reranking: The Second Pass That Decides What the Model Sees — what scores the expanded pool; §4.1's ceiling decomposition tells you whether missed documents (fixable here) or bad ordering (not) is your problem
- Multi-Index RAG: Merging Several Retrievers Into One Answer — §3.1 on why independent signals fuse well and correlated ones don't; the same test decides whether a graph is worth adding
- Agentic RAG: Routing Retrieval to Specialists — another conditional-work pattern: spend more only on the queries that need it
- RAG Cost Optimization: Find the Step That Runs Forty Times — expansion multiplies the reranking step, already the largest line item
- RAG Evaluation: Attributing Failure and Sizing the Eval Set — why an eval set of easy queries hid this feature's real value in §6
Resources
- Edge, Trinh, Cheng et al., "From Local to Global: A Graph RAG Approach to Query-Focused Summarization", arXiv:2404.16130, 2024 — Microsoft's GraphRAG; the knowledge-graph branch described in §3.6.
- Page, Brin, Motwani & Winograd, "The PageRank Citation Ranking: Bringing Order to the Web", Stanford InfoLab technical report, 1999 — link structure as an independent relevance signal.
- Kleinberg, "Authoritative Sources in a Hyperlinked Environment", Journal of the ACM 46(5), 1999 — HITS; hubs and authorities, and why hub nodes need special handling.
- Small, "Co-citation in the Scientific Literature: A New Measure of the Relationship Between Two Documents", JASIS 24(4), 1973 — the co-citation relation in §3.3.
- McPherson, Smith-Lovin & Cook, "Birds of a Feather: Homophily in Social Networks", Annual Review of Sociology 27, 2001 — the homophily property the enrichment in §4.1 depends on.
- Asai et al., "Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection", ICLR 2024 (arXiv:2310.11511) — deciding at runtime whether more retrieval is needed, the same shape as the §3.4 trigger.