The question vanilla RAG cannot answer
Standard RAG is a nearest-neighbour lookup. You embed each chunk to a vector e_c ∈ R^d, embed the query to e_q, and return the k chunks maximising cosine similarity cos(e_q, e_c); the answer is generated from those k chunks alone. This works when the answer lives in a small, findable neighbourhood of text — a definition, a figure, a single passage.
It breaks for query-focused summarisation: ‘what are the recurring risks across these 200 incident reports?’ No single chunk contains the answer; it is an aggregate over the corpus. Top-k retrieval returns k chunks that each mention a risk, but with k fixed (say 10) and hundreds of relevant passages, recall is hopeless. GraphRAG reframes the corpus as structure, so global questions are answered from a compact, pre-computed view instead of a lucky draw.
Step one: entity and relation extraction
The pipeline begins by asking an LLM to read each chunk and emit structured triples. For a chunk of text c, the model returns entities (name, type, description) and relations (source, target, description, strength) — e.g. ‘Ada joined DeepMind’ yields Ada:PERSON, DeepMind:ORG, and (Ada → DeepMind, employed-at, strength=8).
This is the expensive step and the one that defines quality. Every chunk is sent through the LLM at least once, so extraction cost scales linearly with corpus size: for N chunks of L tokens each, input is Θ(N · L) tokens plus the instruction per call. Practitioners often add gleanings — re-prompting ‘did you miss any entities?’ a fixed number of times — multiplying cost by that factor but raising recall. The output is a stream of typed nodes and edges, noisy and duplicated, waiting to be merged into one graph.
Step two: building the knowledge graph
Extraction produces many mentions of the same real entity — ‘DeepMind’, ‘Deep Mind’, ‘DM’ — so construction is a merge. Nodes are grouped by normalised name and type, their descriptions summarised, and duplicate edges collapsed. The result is a weighted undirected graph G = (V, E) where each edge weight w_ij aggregates how often and how strongly entities i and j co-occur across the corpus.
A natural choice is w_ij = Σ strength over all extracted relations between the pair, so a link asserted in fifty chunks outweighs one asserted once. The graph is typically sparse — |E| = O(|V|), not the O(|V|^2) of a dense graph — which is what makes clustering tractable.
Community detection and modularity
The graph is now clustered into communities: groups of entities more densely linked to each other than to the rest of the graph. The standard objective is modularity Q, which scores a partition by comparing observed within-community edge weight against what a random graph with the same degrees would give:
Q = (1 / 2m) Σ_ij [ A_ij − (k_i k_j) / (2m) ] δ(c_i, c_j)
A_ij = edge weight between i and j
k_i = Σ_j A_ij (weighted degree of i)
m = (1/2) Σ_ij A_ij (total edge weight)
δ(c_i, c_j) = 1 if i, j in same community, else 0Q ranges roughly in [-0.5, 1]; higher means crisper structure. The term k_i k_j / 2m is the expected weight between i and j by chance, so Q rewards partitions where real links exceed that baseline. Maximising Q exactly is NP-hard, hence greedy heuristics rather than brute force.
Why Leiden, not just Louvain
The classic modularity optimiser is Louvain: repeatedly move each node to the neighbouring community that most increases Q, then collapse each community into a super-node and recurse. It is fast — near O(|E| · log|V|) in practice — but has a notorious flaw: it can produce communities that are internally disconnected, when a bridge node is abandoned by its own cluster during aggregation.
The Leiden algorithm fixes this with an extra refinement phase that guarantees every community is internally connected, and converges to better partitions faster. GraphRAG uses Leiden for a structural bonus too: in hierarchical mode it yields a tree of communities — fine-grained clusters at leaf level (level 0), coarser groupings above — and that tree is the scaffold the summarisation and global-query steps stand on.
Step three: hierarchical community summaries
Once communities exist, GraphRAG pre-computes a natural-language summary of each. For a leaf community, the LLM is fed the member entities, their descriptions, and the relations among them, and asked for a report: a title, an overview, and key findings. This is the second big token spend, but bounded — its input is the community’s size, not the whole corpus.
The hierarchy makes summaries compositional: a level-1 summary is generated from the summaries of its level-0 children, not from raw text, and so on up the tree. This bottom-up rollup means the top of the hierarchy is a handful of summaries describing the entire corpus at a glance, while lower levels keep detail — at a total cost of Σ_levels |V_level|, a small multiple of |V|, not a re-read of every chunk.
Global query mode: map-reduce over summaries
A global question — ‘what are the major themes?’ — is answered without touching the source chunks at all, by a map-reduce over one community level. In the map step each summary is sent to the LLM with the query, producing a partial answer plus a self-rated helpfulness score in [0, 100]. In the reduce step partials are ranked by score, the highest packed into context, and a final answer synthesised.
Map-phase cost is C_global ≈ n_comm · (s + q) input tokens, where n_comm is the number of communities at the chosen level and s the average summary length, plus one reduce call. Crucially n_comm ≪ N, so global queries read a compressed view of the corpus, not the corpus itself.
Local query mode: anchored graph traversal
Not every question is global. ‘What is Ada’s role and who does she work with?’ is local — it centres on specific entities. Here GraphRAG behaves like enriched vector RAG: it embeds the query, finds the nearest entities in the graph, then expands along edges to pull in their neighbours, the connecting relations, the community summaries they belong to, and the source chunks that mention them.
The retrieved context is thus a small subgraph plus its supporting text, assembled into a prompt under a token budget. Because expansion follows edges rather than raw similarity, local mode surfaces entities relevant by relation even when their text is not lexically close to the query — a colleague never named in the same sentence still surfaces because the graph links them. Cost is bounded by the budget, not corpus size, so local queries stay cheap.
The token-cost tradeoff
GraphRAG’s defining tradeoff is indexing cost versus query cost. Building the graph is expensive — extraction touches every chunk (Θ(N · L) tokens, times any gleaning factor) and summarisation every community — but is paid once, offline. Query cost is then small and, for global questions, independent of N: you read n_comm summaries, not N chunks.
So the economics favour GraphRAG when a stable corpus is queried many times with global questions — the one-time index amortises over thousands of cheap queries. It is a poor fit for a rarely-queried or rapidly-changing corpus, where you keep paying the indexing tax and never amortise it, and for purely local fact-lookup, where plain vector RAG already suffices. The decision is an amortisation calculation: does C_index spread over the expected number of global queries beat a naive baseline?