GraphRAG answers the questions ordinary retrieval quietly fails: not ‘what does chunk 47 say about X’ but ‘what are the main themes across this whole corpus?’ Vanilla RAG embeds text into chunks and fetches the top-k nearest neighbours of a query — excellent for local fact-lookup, useless for global sensemaking, where the answer sits in no single chunk but is spread across hundreds. GraphRAG’s fix is to spend LLM tokens up front turning the corpus into a knowledge graph of entities and relations, cluster it into a hierarchy of communities, pre-summarise each community, then route a query either globally over those summaries or locally around a few entities. This piece walks the pipeline as math: extraction, graph construction, Leiden clustering and modularity, hierarchical summaries, the two query modes, and the token economics — which bite hardest on CPU-class SLMs where every token is wall-clock time.
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?
A worked cost example
Take a 10 million-token corpus split into N = 10,000 chunks of L = 1,000 tokens. Extraction sends each chunk once with a ~500-token instruction, so input ≈ 10,000 × 1,500 = 15M tokens; one gleaning pass roughly doubles that to ~30M. Say it yields |V| = 20,000 entities that Leiden groups into ~400 leaf communities, summarised at ~2,000 tokens each — another ~0.8M tokens, plus a smaller rollup above.
Indexing therefore costs on the order of 30M input tokens, once. A leaf-level global query then costs about 400 × (2,000 + 100) ≈ 0.84M map tokens plus a reduce. Spread over 1,000 such queries the index adds only ~30k tokens each — worth it exactly when those questions have no other answer.
Implications for CPU-class SLMs
On CPU inference the token count is the wall-clock cost — no GPU throughput to hide behind — so GraphRAG’s numbers land harder. The indexing phase is a batch job you run overnight, tolerant of a slow SLM because it is offline and embarrassingly parallel across chunks. The payoff is that query time stays modest: reading a few hundred short community summaries is far cheaper than a small model re-reading thousands of raw chunks it has no window to hold anyway.
The hierarchy also lets a small model punch above its context limit. An SLM with an 8k window can never see a 10M-token corpus, but it can read one community summary at a time in the map step and a ranked handful in the reduce step — trading a big window for pre-computed structure, exactly what a memory-constrained, CPU-bound deployment wants.
Pitfalls and failure modes
The graph is only as good as the extraction. A weak or over-quantised SLM produces inconsistent entity names, missed relations, and hallucinated links, and every downstream community and summary inherits those errors — garbage in, structured garbage out. Entity resolution is the sore spot: fail to merge ‘NYC’ and ‘New York City’ and you split one community in two, distorting modularity and the summaries built on it.
Cost blindness is the other trap. Teams enable gleanings and deep hierarchies without doing the amortisation math, then are shocked by the indexing bill on a corpus that turns over weekly. And GraphRAG is no universal upgrade: for local, single-fact questions it is slower and pricier than plain vector RAG, so a sound system routes — global questions to the community summaries, local ones to entity-anchored traversal or a plain top-k baseline.
Q, and pre-summarise each community bottom-up. That structure buys what vanilla top-k retrieval cannot: global sensemaking, answered by a map-reduce over a few hundred community summaries instead of a lucky draw of k chunks; local questions still route to cheap entity-anchored traversal. The bet is an amortisation — expensive one-time indexing (Θ(N · L) tokens) against cheap, corpus-size-independent global queries — so it wins on a stable corpus asked many global questions and loses on a fast-changing one or pure fact-lookup. On CPU-class SLMs that structure is what lets a small model reason over a corpus far larger than its context window.