« Phase 06 README · Warmup · Hitchhiker's · Principal Deep Dive · Core Contributor · Staff Notes

Phase 06 — Deep Dive: Advanced Retrieval (GraphRAG & RAPTOR)

This is the mechanism document. Not "what does RAPTOR do" — what happens to the bytes: the data structures, the loop invariants, the complexity, and a step-by-step trace of a query resolving. If you cannot explain why the flat top-k retriever from Phase 05 is structurally incapable of certain answers — not "worse at," incapable of — start here.

Why flat top-k fails at the mechanism level

A flat dense retriever computes argmax_k cos(q, c_i) over a fixed set of chunk vectors {c_i}. Every element of its output range is a member of the input corpus. That is not a tuning weakness; it is a closure property. The retriever is a selection function over an immutable set, and selection cannot produce an element the set does not contain.

Three question shapes need an element the set does not contain:

• Synthesis. "How did this document's argument evolve across three sections?" The answer is a fusion of chunks that appears in none of them. Selection cannot fuse.
• Global/thematic. "What are the recurring themes across 10k documents?" A theme is a property of the set, not of any member — the way a mean is a property of a sample, not of any datapoint. No chunk states it.
• Multi-hop/relational. "Who owns the model that flags the payments the gateway processes?" The answer is a path: payments ← flags ← fraud_model ← owns ← risk_team. A bag of nearest vectors has no edges; there is nothing to walk.

Both fixes in this phase share one move: manufacture the missing element at index time and insert it into the retrievable set. RAPTOR manufactures fused summaries and puts them in the vector pool. GraphRAG manufactures community summaries and graph structure. The query-time retriever stays dumb; the intelligence is precomputed.

RAPTOR: the tree build as a strictly-shrinking fixpoint

The core loop in build_raptor_tree is a bottom-up reduction. Level 0 is one RaptorNode per chunk. Then, while the current level has more than one node:

1. Cluster the current level's embeddings (greedy_cluster).
2. Summarize each cluster's texts into a parent (the injected summarizer).
3. Embed the parent and record its children; the parents become the next level.

The correctness of this as a terminating algorithm rests on one invariant: cluster_size >= 2 forces every cluster to be strictly smaller than the input whenever the input has more than one node, so len(current) strictly decreases each iteration. A strictly decreasing sequence of positive integers reaches 1 in finite steps — that is the whole termination proof, and it is why the constructor rejects cluster_size < 2. Depth is O(log_b N) for N leaves and branching b = cluster_size; total nodes are O(N) (a geometric series, N + N/b + N/b^2 + ... ≈ N·b/(b-1)).

The subtle design decision is that the parent's embedding is embed(summary_text), not a centroid of the children. A centroid would drift toward the mean of the child vectors; the summary is re-embedded from its own text, so the parent's vector reflects what the summarizer chose to keep. That is what lets a summary node compete honestly in the same vector space as the leaves. In our miniature the summarizer (make_frequency_summarizer) keeps the most frequent content words, so the parent literally covers the union of the children's distinctive terms — the property the retrieval math below exploits.

Collapsed-tree vs tree-traversal retrieval

Once the tree exists there are two retrieval modes, and the difference is the classic probe.

Tree traversal: start at the root, score its children against the query, descend into the top scorer(s), repeat. It visits O(log N) nodes, but an early high-level mis-score prunes an entire subtree — you can lose the one leaf you needed because its ancestor summary happened to score low. It is fast and fragile.

Collapsed tree (collapsed_tree_search): flatten every node at every level into one pool and take global top-k by cosine, exactly like flat vector search — except the pool now contains summaries alongside leaves. It scores O(N) nodes and never prunes. The query decides its own abstraction level: a specific question lands on a leaf, a synthesis question lands on a summary, with no routing logic. Sarthi et al. report collapsed-tree matches or beats traversal on QuALITY and NarrativeQA — the extra scoring cost buys robustness against mis-pruning. This is why the lab implements collapsed search as the headline and leaves traversal as an extension.

Why the summary node wins — the inequality

Take a cluster of n leaves where leaf i carries one distinctive term t_i on shared filler. The summary covers the union, so it contains all of t_1..t_n. A synthesis query mentions each distinctive fact, so q contains all t_1..t_n. Ignoring filler (it helps every candidate equally):

• q vs leaf j: they share exactly one distinctive term t_j, so the dot product is ≈ 1.
• q vs summary: they share all n distinctive terms, so the dot product is ≈ n.

With norm(q) ≈ sqrt(n) and norm(summary) ≈ sqrt(n + extras):

cos(q, summary) ≈ n / (sqrt(n)·sqrt(n+extras)) = sqrt(n/(n+extras)), versus cos(q, leaf_j) ≈ 1/(sqrt(n)·norm(leaf_j)).

For n >= 2 the numerator advantage (n vs 1) dominates the length penalty. The summary outscores every single leaf. The lab tests exactly this: a three-chunk Mars theme (perseverance, ingenuity, orbiter), a synthesis query naming all three, and collapsed_tree_search returns the level-1 summary (cosine ≈ 0.68) above the best leaf (≈ 0.34), while flat_leaf_search can only ever return leaves.

GraphRAG: the pipeline as a four-stage reduction

extract_graph → detect_communities → summarize_communities → global_query/local_query. Each stage's output is the next's input; the cost is front-loaded into the first stage.

Stage 1 — extract. For each document, the injected extractor emits (subject, relation, object) triples. KnowledgeGraph.add_triple inserts subject and object into the entity set, appends the triple, and — critically — updates an undirected adjacency map (_adj[s].add(o) and _adj[o].add(s)). The direction is kept in the triple list for traversal answers but dropped for community detection, because "these two entities are related" is a symmetric fact for clustering purposes.

Stage 2 — community detection. The lab uses connected components via sorted-order BFS. Seed entities in sorted order; for each unseen entity, BFS its undirected neighborhood (neighbors visited in sorted order) into one component; order components by smallest member. This is O(V + E) and fully deterministic. It is exact when themes form disjoint subgraphs — the two seeded themes (payments/fraud, cloud-infra) are disconnected, so it recovers them precisely. Its limitation is real: it cannot split a single large connected blob into sub-themes. That is Leiden's job (§ below and the Core Contributor doc).

Stage 3 — summarize. For each community, gather every triple touching a member, render each as a "subject relation object" sentence, and feed the batch to the summarizer. The output is a CommunitySummary — new text that states what the community is about. This text exists in no source document. It is the entire point of GraphRAG; everything else is plumbing.

Stage 4 — query. Two modes:

• Global (global_query): embed the query and each community summary, return top-k communities by cosine. This is the retrieval core of a map-reduce. The full map-reduce sets k = number of communities, asks the question against each summary (map), and combines the partial answers (reduce). A themed question sets k=1.
• Local (local_query): return one entity's 1-hop neighbors and every triple it participates in as subject or object. This is a graph walk, not a vector search — it catches incoming edges a naive "subject-only" scan would miss.

A worked trace: global vs local on the same graph

Corpus: two docs producing two disjoint communities. Community A = {stripe_gateway, fraud_model, payments, transaction_logs, risk_team}; community B = the Kubernetes/Prometheus/SRE cluster.

Global query: "which model flags fraudulent payments and which team owns the risk pipeline." global_query embeds the query and both community summaries. Community A's summary (built from "fraud_model flags payments", "risk_team owns fraud_model", …) shares the terms model, flags, payments, risk, team with the query → cosine ≈ 0.6. Community B's summary shares almost nothing → ≈ 0.25. A is returned. The decisive point: the query phrase "the themes" never appears in any chunk — the answer lives in the manufactured summary text.

Local query: "tell me about fraud_model." local_query("fraud_model", graph) skips vectors entirely. It returns neighbors {payments, risk_team, transaction_logs} (undirected 1-hop) and the incident triples (fraud_model, flags, payments), (fraud_model, trained_on, transaction_logs), (risk_team, owns, fraud_model). That last triple is incoming — caught only because incident scans both t[0] and t[2]. This is precise, cheap, and entity-anchored: LightRAG's low-level retrieval.

Two questions, same graph, two entirely different machines: a vector top-k over manufactured summaries for the global one, a deterministic adjacency walk for the local one. Routing by question shape is not a heuristic bolted on top — it is the recognition that these are different computations.

Where the cost actually lives

Both architectures move work to index time, and that is where the complexity — and the money — concentrates. RAPTOR: one summarizer (LLM) call per cluster per level ≈ O(N/(b-1)) LLM calls plus O(N) embeddings. GraphRAG: one-or-more extraction (LLM) calls per chunk, plus Leiden, plus one summary (LLM) call per community across the whole hierarchy. The query-time cost is trivial by comparison — one ANN lookup (RAPTOR/global) or one adjacency walk (local). Internalize the asymmetry: a global query is cheap precisely because an expensive precomputation already ran. The Principal Deep Dive turns that asymmetry into capacity math.