Graph RAG: When Relationships Matter More Than Similarity

Some questions have no answer in any k chunks, no matter how good the retrieval is, because the answer is a property of the corpus rather than a passage in it. That is a structural limit, and it is the one thing graph approaches genuinely address.

The questions top-k cannot answer

Take three questions against a corpus of a thousand incident reports.

• “What happened in incident 4471?” — a local question. One chunk answers it. Vector search is the correct tool and anything more is overhead.
• “Which services were involved in incidents that also involved the payments database?” — a relational question. Answerable by retrieval only if some single document happens to state the relationship. Otherwise you are asking for a join across documents, and similarity does not do joins.
• “What are the recurring root causes across the last two years?” — a global question. The answer exists in none of the thousand reports. It is a property of the set, and no value of k retrieves it, because k = 1000 is just the corpus.

The third case is the honest motivation for graph-style RAG. Microsoft’s GraphRAG paper (Edge et al., arXiv:2404.16130) frames it exactly this way — as query-focused summarisation over an entire corpus, a task it argues conventional top-k RAG fails at by construction rather than by degree.

Two different claims, often conflated

Claim one: traversal for multi-hop

Extract entities and relations into a graph; answer a question by walking edges. The pipeline is: an LLM pass over each chunk emitting (subject, relation, object) triples, entity resolution to merge “the payments DB” with “payments-primary”, then retrieval that seeds on entities mentioned in the question and expands one or two hops.

The hard part is not the graph, it is entity resolution. Get it wrong in the merging direction and two distinct services become one node, producing confident nonsense; get it wrong in the splitting direction and your graph is a dust of singletons with no edges worth walking. This step is where graph RAG projects stall, and no amount of graph database sophistication compensates for it.

Claim two: hierarchical summaries for global questions

Cluster the graph into communities — the published approach uses Leiden community detection — and generate a summary per community, and summaries of summaries above that. A global question is answered by mapping over community summaries at the appropriate level and reducing the partial answers, rather than by retrieving chunks at all.

Notice that this second claim barely needs the graph. What it needs is a clustering and a summarisation hierarchy. You can build one over embedding-space clusters with no entity extraction whatsoever, which is worth knowing before you commit to the full pipeline.

What the index build costs

This is the part that gets left out. Vector indexing is one cheap embedding call per chunk. Graph indexing is at least one generation call per chunk, plus summarisation passes over every community at every level. The difference is two or three orders of magnitude.

Assumptions you should replace with your own:
  10,000 chunks x 600 tokens
  extraction: 800 in / 300 out per chunk
  rates: assume Gin per Mtok input, Gout per Mtok output

  extraction  = 10,000 x (800 Gin + 300 Gout) / 1e6
              = 8.0 Mtok in  +  3.0 Mtok out

  community summaries: ~3 levels, each summarising the level below;
  budget roughly another 30-50% of the extraction token volume.

Compare: embedding the same 10,000 chunks is 6 Mtok through a model
priced one to two orders of magnitude below a generation model.

Fill in your own rates and the ratio is stark. Then multiply by the rebuild frequency, which is the second thing that gets left out: a graph built by LLM extraction is expensive to keep current, because a changed document can invalidate entities, edges and every community summary that touched them. For a corpus that changes daily, this is the dominant operational cost of the whole approach.

A decision list

Build the graph if most of these hold. Do not if they do not.

• A material share of your real queries are global or multi-hop — you have looked at the logs and counted, rather than imagining the questions users might ask.
• The relationships are not already in a database. If your entities live in Postgres with foreign keys, you have a graph; query it with SQL and give the model the result.
• The corpus is stable enough that the build amortises over many queries.
• Entities in your domain are namable and resolvable — people, products, services, statutes. Diffuse domains without a clean entity vocabulary produce weak graphs.

Cheaper things that get most of the way

• Query the real database. The most common global question in a business context — counts, groupings, trends — is a SQL query. A tool call beats a graph.
• Document-level summaries in the index. Embed a summary of each document alongside its chunks. Retrieval on a broad question then matches summaries, and the model gets a coarse view without any graph machinery.
• Map-reduce over a filtered subset. Filter to the relevant partition, summarise each document with a cheap model, reduce the summaries. Linear in corpus size, no index, and frequently the right answer for a report that runs once a month.

If you do commit to the graph, budget for entity resolution as its own workstream rather than as a step. The techniques are unglamorous and well understood outside this field: normalise aggressively, block candidates by a cheap key so you are not comparing every pair, score pairs with a combination of string distance and embedding similarity, and keep an explicit alias table that a human can correct. That last item is the one that makes the system maintainable — when somebody reports that two services were conflated, you want a row to edit, not a pipeline to re-run.

The other thing to plan for is that the graph does not replace the vector index; it sits beside it. Local questions still route to similarity search, and the honest architecture is a router that sends entity-and-relationship questions to traversal, global questions to the community summaries, and everything else — which will be most of the traffic — to ordinary top-k. Systems that put the graph in front of every query pay its cost on the 80% of questions that never needed it.