FINDING NEEDLES · CHAPTER 16
Some answers live in two pages that never mention each other. Search finds pages. A graph finds the link between them.
A small river town keeps five pages of notes on its bakeries, mills, and suppliers. A visitor asks: “Who grinds the flour for the rye bread?”
No page says it. The bakeries page says rye bread is baked at Hollow Bakery. The suppliers page says Hollow Bakery gets its flour from Weir Mill. You only get “Weir Mill” by reading both pages and noticing that “Hollow Bakery” appears in each.
That shared name is the bridge. The question never says it. So a search that scores pages by the question’s words has no reason to fetch the second page.
Ranked search treats each page alone. Some questions need two facts from two pages, joined on a name. A graph stores those names as nodes and the facts as edges, so the join is already made before anyone asks.
Drop the stop words and the question is four words: grinds, flour, rye, bread. Score each page by how many times those words occur in it. This is cruder than BM25, but BM25 fails here for the same reason.
join · entities · filters · multi-hop
| Page | Text | Score |
|---|---|---|
| 1 | Bakeries. Rye bread is baked at Hollow Bakery. Seed rolls are baked at Quay Bakery. | 2 |
| 2 | Suppliers. Hollow Bakery: Weir Mill. Quay Bakery: Bridge Mill. Barge oil: Tolley. | 0 |
| 3 | Rye bread care. Rye bread keeps for a week. Slice rye bread thin. | 6 |
| 4 | Market. Tolley grinds spices and sells flour at the Saturday market. | 2 |
| 5 | Barges. Grain sacks arrive by barge. The barge docks on Monday. | 0 |
The ranking is pages 3, 1, 4, 2, 5. A top-3 retriever hands the model pages 3, 1, 4. Page 1 names Hollow Bakery. Nothing it was given says where Hollow Bakery’s flour comes from. The model either says “I don’t know” or, worse, guesses Tolley, because page 4 says Tolley grinds and sells flour.
Dense retrieval does not rescue this. The suppliers page is a list of bakeries and mills. In meaning, it is nowhere near a question about rye bread. The page that answers the question is about something else.
There are two fixes. One is to search again at question time: read page 1, see “Hollow Bakery”, and run a second search for it. That works, at the cost of an extra round trip for every question. This chapter’s fix is to find the bridges once, when you build the index.
A triple is one fact with three parts: a subject, a relation, and an object. “Rye bread is baked at Hollow Bakery” becomes (rye bread, baked_at, Hollow Bakery). Each triple also remembers the page it came from, so you can cite it later.
| Subject | Relation | Object | Page |
|---|---|---|---|
| rye bread | baked_at | Hollow Bakery | 1 |
| seed rolls | baked_at | Quay Bakery | 1 |
| Hollow Bakery | flour_from | Weir Mill | 2 |
| Quay Bakery | flour_from | Bridge Mill | 2 |
| barge oil | sold_by | Tolley | 2 |
| Tolley | trades_at | Saturday market | 4 |
| grain sacks | arrive_by | barge | 5 |
| barge | docks_on | Monday | 5 |
These eight triples were written by hand for this chapter. A real pipeline asks a language model, or an entity tagger plus a relation classifier, to propose them for every chunk. That step is the expensive one, and the noisy one.
Every distinct subject or object becomes a node. Every triple becomes a directed edge. Eight triples give 12 nodes and 8 edges. Page 3 adds none: “Rye bread keeps for a week” has no second entity here worth linking.
Notice what made the bridge: “Hollow Bakery” is spelled the same way on pages 1 and 2, so both triples land on one node. If page 2 had said “the bakery on Hollow Lane”, you would get two nodes and no path. Merging names that mean the same thing is called entity resolution. It is most of the real work.
Answering now means turning the question into a path: start at the node the question names, then follow named relations.
start at the thing the question names, follow one named edge per hop, and stop where the path ends. Each arrow carries the page it was read from.
Compare the two contexts. Keyword top-3 gave pages 3, 1, 4. The walk gave pages 1 and 2. The walk used fewer pages and got the one the ranking left out.
The same path from seed rolls lands on Bridge Mill, again using pages 1 and 2. The plan, not the data, is what changed.
Standard library only. The ranking, the graph, the two-hop walk, and the groups used in the next section are all in one file.
"""Graph retrieval on five pages about a river town's bakeries and mills.
Keyword search ranks pages by the question's words. The answer page
shares none of them. A small graph of hand-extracted triples joins the
two pages by walking edges instead.
"""
# Five town pages. Ids match the table on the page.
DOCS = {
1: "Bakeries. Rye bread is baked at Hollow Bakery. Seed rolls are baked at Quay Bakery.",
2: "Suppliers. Hollow Bakery: Weir Mill. Quay Bakery: Bridge Mill. Barge oil: Tolley.",
3: "Rye bread care. Rye bread keeps for a week. Slice rye bread thin.",
4: "Market. Tolley grinds spices and sells flour at the Saturday market.",
5: "Barges. Grain sacks arrive by barge. The barge docks on Monday.",
}
QUESTION = "Who grinds the flour for the rye bread?"
STOP = {"who", "the", "for", "a", "at", "and", "is", "are", "on", "by"}
def words(text):
"""Lowercase words, punctuation dropped, stop words removed."""
cleaned = "".join(ch if ch.isalnum() else " " for ch in text.lower())
return [w for w in cleaned.split() if w not in STOP]
def keyword_rank(question=QUESTION):
"""Score = how many times the question's words occur in the page."""
terms = set(words(question))
scores = {d: sum(w in terms for w in words(t)) for d, t in DOCS.items()}
return sorted(scores.items(), key=lambda item: (-item[1], item[0]))
# (subject, relation, object, page it came from). Written by hand here;
# a real pipeline asks an LLM or an entity tagger to propose these.
TRIPLES = [
("rye bread", "baked_at", "Hollow Bakery", 1),
("seed rolls", "baked_at", "Quay Bakery", 1),
("Hollow Bakery", "flour_from", "Weir Mill", 2),
("Quay Bakery", "flour_from", "Bridge Mill", 2),
("barge oil", "sold_by", "Tolley", 2),
("Tolley", "trades_at", "Saturday market", 4),
("grain sacks", "arrive_by", "barge", 5),
("barge", "docks_on", "Monday", 5),
]
def build_graph(triples=TRIPLES):
"""Adjacency list: node -> [(relation, neighbour, page), ...]."""
graph = {}
for subj, rel, obj, page in triples:
graph.setdefault(subj, []).append((rel, obj, page))
graph.setdefault(obj, [])
return graph
def walk(start, relations, graph=None):
"""Follow one named edge per hop. Return the end node and the pages used."""
graph = graph or build_graph()
node, path, pages = start, [start], []
for rel in relations:
hop = [(obj, page) for r, obj, page in graph[node] if r == rel]
if not hop:
return None, path, pages
node, page = hop[0]
path.append(node)
pages.append(page)
return node, path, pages
def communities(graph=None):
"""Connected groups of nodes, ignoring edge direction."""
graph = graph or build_graph()
links = {n: set() for n in graph}
for subj, edges in graph.items():
for _, obj, _ in edges:
links[subj].add(obj)
links[obj].add(subj)
seen, groups = set(), []
for start in graph:
if start in seen:
continue
group, stack = [], [start]
seen.add(start)
while stack:
node = stack.pop()
group.append(node)
for nxt in links[node] - seen:
seen.add(nxt)
stack.append(nxt)
groups.append(sorted(group))
return groups
if __name__ == "__main__":
print(keyword_rank()) # [(3, 6), (1, 2), (4, 2), (2, 0), (5, 0)]
print(walk("rye bread", ["baked_at", "flour_from"])) # Weir Mill, pages [1, 2]
print(communities()) # four groups of three
A missing edge stops the walk and returns None. That is a feature. If flour_from is missing for a bakery, the system can say “no supplier is listed” instead of guessing.
Now ask: “What are the main trades in this town?” There is no start node. No single page answers it. Retrieving the top few pages gives a sample, not a summary.
GraphRAG handles this kind of question ahead of time. It splits the graph into communities: groups of nodes linked more to each other than to the rest. It asks a language model to write a short summary of each community. A broad question is then answered from those summaries: one partial answer per community, then one combined answer.
The town graph is small enough that its communities are simply its connected pieces. Ignore edge direction and you get 4 groups of 3 nodes.
| Group | Nodes | A summary a model might write |
|---|---|---|
| 1 | rye bread, Hollow Bakery, Weir Mill | Hollow Bakery bakes the rye bread with flour from Weir Mill. |
| 2 | seed rolls, Quay Bakery, Bridge Mill | Quay Bakery bakes the seed rolls with flour from Bridge Mill. |
| 3 | barge oil, Tolley, Saturday market | Tolley sells barge oil and trades at the Saturday market. |
| 4 | grain sacks, barge, Monday | Grain arrives by barge, which docks on Mondays. |
Four lines now cover the whole town. The summaries above are written by hand. On a real corpus with thousands of nodes, connected pieces are useless, because almost everything ends up linked to everything. GraphRAG uses the Leiden algorithm instead, which finds tightly knit groups inside one big connected graph, at several levels of detail.
Questions that join facts across pages: who, which, supplied by, part of, depends on. Corpora full of named things that repeat across documents. Broad “what are the themes” questions over a large collection.
Answers that sit in one passage. Corpora that change every hour, because extraction must re-run. Prose where the meaning is in the explanation, not in who-relates-to-what. Start with hybrid search and add the graph when questions keep failing on joins.
Most systems that use a graph also keep the ordinary text index. The graph finds the pages and the bridges. The text gives the model the full sentences to quote.
If the town kept its supplier list in a spreadsheet, you would not need to extract anything. The rows are the triples. A question like “how many bakeries does each mill supply?” is a group-by and a count, and an exact query beats any retrieval.
Text-to-SQL is that route: give a language model the table schema, have it write a query, run the query with a read-only account, and let the model phrase the rows as an answer. The hard parts are naming (which of three date columns did the user mean?) and safety (treat the generated query as untrusted input, with timeouts and row limits).
Fixing a join problem with a bigger top-k. Raising k from 3 to 4 fetches page 2 here only by luck of the ties. On a real corpus the bridge page can sit at rank 400. Wider is not the same as connected.
Skipping entity resolution. “Hollow Bakery”, “hollow bakery”, and “the bakery on Hollow Lane” must be one node. Without that merge, the edge from page 1 and the edge from page 2 never meet, and the walk stops after one hop.
Dropping the page on each triple. A graph that only stores (Hollow Bakery, flour_from, Weir Mill) can answer, but cannot cite. Keep the source page on every edge so the answer can point back to text a person can check.
Trusting extracted edges as facts. A model that extracts triples will sometimes invent one, or flip its direction. A wrong edge gives a confident, wrong, well-cited answer. Spot-check extraction like you would grade retrieval.
It contains none of grinds, flour, rye, or bread. It only lists bakeries and mills. The link to rye bread is on page 1.
It says Tolley grinds and sells flour. A model with pages 3, 1, 4 and no supplier list may stitch that into “Tolley grinds the flour for the rye bread”, which is wrong.
Without entity resolution, “the bakery on Hollow Lane” becomes its own node. The walk reaches Hollow Bakery, finds no flour_from edge, and stops with no answer.
Both join two pages. Searching again finds the bridge while the user waits, with a second search. The graph found it at index time, so the walk is a lookup.
It names no entity, so there is no start node. Pre-written community summaries answer it instead.