GraphRAG — knowledge-graph retrieval for global sensemaking

For NAO + anyone building retrieval systems. GraphRAG is Microsoft Research's answer to a specific failure of ordinary RAG: questions whose answer is spread across the whole corpus rather than sitting in a few chunks. It's directly relevant to us because [[graphify]] and the Atlas org graph already build entity/relation graphs over our code — GraphRAG is the "retrieve over the graph with community summaries" half we mostly don't do yet. Grounded in the paper From Local to Global (arXiv:2404.16130), the MS Research blogs, the microsoft/graphrag repo, and two independent 2025–2026 benchmark papers so the caveats aren't just the vendor's marketing.

The one-sentence idea

Use an LLM to turn a corpus into an entity–relationship knowledge graph, cluster that graph into a hierarchy of communities, pre-summarize each community, and then answer broad ("global sensemaking") questions by map-reducing over those community summaries instead of over raw retrieved chunks.

Ordinary vector RAG embeds chunks and retrieves the top-k nearest to the query. That's great for "what does the contract say about termination?" — a local lookup. It falls over on "what are the main themes across these 1,500 documents?" because no single chunk contains the answer and top-k can't see the whole corpus. The paper's framing: vector RAG can't do sensemaking — "reasoning over connections… to anticipate their trajectories" — over an entire corpus that exceeds the context window (arXiv:2404.16130 §1).

Why it matters

• It reframes retrieval as graph + summarization, not just nearest-neighbor. The structure of who-relates-to-whom becomes a first-class retrieval signal.
• It targets the question class that breaks naive RAG and is exactly what an analyst wants: themes, trends, "what's the overall story." For a code/knowledge graph like Atlas this is "what are the architectural themes across the org," not "where is symbol X."
• It put "GraphRAG" on the map as a named pattern; there's now a whole zoo (LazyGraphRAG, DRIFT, LightRAG, HippoRAG, entity-event KGs). Knowing the original mechanics lets you read the rest critically.
• Microsoft reports it beating a vector-RAG baseline on comprehensiveness 72–83% and diversity 62–82% head-to-head win rates on million-token corpora (arXiv:2404.16130 §4) — large enough to take seriously, with caveats below.

How it actually works (the real mechanics)

Two phases: an expensive offline index build, then a cheap-ish query.

Phase 1 — Indexing (build the graph + community summaries)

1. Chunk the source. Split documents into text units. The paper uses 600-token chunks with 100-token overlap (Podcast = 1,669 chunks ≈ 1M tokens; News = 3,197 chunks ≈ 1.7M tokens). Chunk size is a real knob: they found 2,400-token chunks roughly halved the number of entities extracted vs 600 — bigger chunks are cheaper (fewer LLM calls) but recall drops because the model "forgets" to extract toward the end of a long chunk.

1. Extract entities, relationships, and claims with the LLM. A single prompt pulls named entities (people, places, orgs), the relationships between them with a short description, and optionally claims ("statements that present verifiable facts"). To recover the recall lost on big chunks they use "gleaning": after the first pass, ask the model "did you miss any entities?" and re-extract, up to a few rounds — self-reflection that lets you use larger, cheaper chunks without tanking recall.

1. Build the graph. Aggregate duplicate mentions of the same entity/relationship across all chunks into single nodes/edges (the reference pipeline matches on normalized name — basically string match, not semantic entity resolution). Edge weight = how many times that relationship was seen. The Podcast graph ended up 8,564 nodes and 20,691 edges.

1. Detect communities (Leiden). Run the Leiden algorithm (via the graspologic library) to partition the graph into communities of densely-related entities. Leiden is hierarchical and recursive: it gives nested levels C0 (root, coarse) → C1 → C2 → C3 (leaf, fine). C0 on Podcast was 34 communities. Every node lands in exactly one community at each level, and the levels nest — this hierarchy is the whole trick.

1. Summarize every community, bottom-up. For each leaf community, feed the LLM the descriptions of its entities, relationships, and claims (prioritized by edge degree, truncated to fit the window) and produce a community report. For higher levels, if the child element-summaries fit the window summarize those directly; if not, substitute shorter community summaries for the largest sub-communities until it fits. Result: a pre-computed, multi-resolution set of summaries of "what this cluster of the corpus is about." Indexing the Podcast set took 281 minutes on one VM — this is the cost you pay up front.

Phase 2 — Query

Global search (the headline mode), map-reduce over community summaries:

1. Pick a community level (e.g. C0 or C1) as the answer's resolution.
2. Map: shuffle that level's community summaries and pack them into chunks. For each chunk, ask the LLM to answer the user's question from that chunk alone and to emit a helpfulness score 0–100 for how much that partial answer contributes. Shuffling deliberately spreads relevant info across chunks instead of letting it concentrate in one and get lost.
3. Filter + Reduce: drop the score-0 partials, sort the rest by helpfulness, greedily concatenate top partials into a fresh context window until the 8k-token limit, then have the LLM synthesize them into one final answer.

Local search (entity-anchored, for specific questions): start from the entities in the query, walk their neighborhood in the graph, and pull in connected entities, relationships, claims, and the original text chunks — closer to classic RAG but graph-guided. DRIFT search (added later in the repo) blends local search with community information for a middle ground.

In prose, global search ≈ "summarize the corpus at the right zoom level, ask every piece, keep the useful answers, merge." That's why it can answer "what are the themes" — every community gets a vote.

Key ideas & tradeoffs

• The hierarchy is the product. C0 is a few coarse summaries (cheap, broad, loses detail); C3 is many fine ones (expensive, detailed). You pick the zoom for the question. The paper found intermediate (C2/C3) and low-level summaries won on comprehensiveness (57–64%) and diversity (57–60%) over vector RAG, and even the coarse root C0 still won 72% comprehensiveness / 62% diversity — while using 97% fewer context tokens than the source-text baseline and ~33% fewer than lower levels. The cheap coarse summaries are a remarkably strong default.
• Pre-computation buys query breadth. You pay a big one-time LLM bill so that query time only touches summaries, not the whole corpus. Good when many queries hit one stable corpus; terrible for one-off queries on fresh data.
• "Directness" is the honest control. They added Directness ("how concise and on- point") expecting GraphRAG to lose it — and it does, to vector RAG. That's the point: comprehensiveness and conciseness trade off, and no method should win all four metrics. Reporting a metric you lose is a credibility signal.
• It generalizes beyond text. The same "extract graph → community-summarize → map-reduce" recipe applies to any entity-rich corpus, including a code graph.
• Tooling. microsoft/graphrag (v3.x, 2026) is a config-driven pipeline; the blog warns up front that indexing "can be an expensive operation… start small."

Honest caveats & limitations

• Indexing cost is the dealbreaker. Multi-pass extraction + gleaning + per- community summarization is a large LLM bill and ~hours of wall-clock per million tokens. Microsoft's own follow-up, LazyGraphRAG, defers all LLM use to query time (uses cheap NLP noun-phrase co-occurrence to build the graph) and claims indexing cost = vector RAG = 0.1% of full GraphRAG, with global-query answer quality "comparable… but >700× lower query cost." That Microsoft shipped this is a tacit admission the original is too expensive for most use.
• Quality of the graph ≠ quality of the answer. A 2026 benchmark ("Do We Still Need GraphRAG?", arXiv:2604.09666) finds indexing quality and query quality are decoupled — bigger graphs / stronger extraction don't reliably yield better answers. Don't assume more graph = better.
• Coverage gaps. Answers are bounded by what got extracted. If the entity/relation extraction misses something, it's invisible to retrieval. Independent work cites ~15–20% extraction error rates for NLP-based graph building and notes GraphRAG can underperform plain RAG on precise QA because critical facts live in text the extractor dropped.
• Naive entity resolution. The reference pipeline merges entities by name match, so "MS" / "Microsoft" / "Microsoft Corp." can fragment into separate nodes — real deployments bolt on semantic dedup.
• Weak on local/precise QA. GraphRAG is built for global sensemaking. For "what's the exact value of X," vector RAG is often as good or better and far cheaper. Several 2025–2026 systematic evaluations (e.g. arXiv:2502.11371) find the win is task-dependent, not universal.
• Domain brittleness + small-model failures. Schema-free extraction degrades in specialized domains (medicine, finance), and on small/local LLMs people see structured-output failures and degenerate repetition.
• Evaluation is LLM-as-judge on questions the LLM also generated. Win rates come from an LLM judge comparing answers to LLM-synthesized sensemaking questions with no gold answers. They validate with SelfCheckGPT-style claim counts, but there's no human ground-truth accuracy number — treat "72–83%" as relative preference, not correctness.

How it connects to OpenAlice

We already build the first half of GraphRAG and barely use the second:

• [[graphify]] + the Atlas org graph are GraphRAG's index, for code. Graphify extracts an entity/relation graph (symbols, files, callers/callees, imports); Atlas serves it via atlas.code.search, callers/callees, repo impact, and the org /api/v1/graph. That's steps 1–3 of GraphRAG's indexing, already done and cron-fresh — and notably built with deterministic AST parsing, not LLM extraction, so we skip GraphRAG's biggest cost and its biggest error source.
• The missing pieces are Leiden communities + community summaries. We don't yet cluster the org graph into a hierarchy and pre-summarize each cluster. Adding a Leiden pass over Atlas's repo/module graph + LLM community reports would give us exactly GraphRAG global search over the codebase: "what are the architectural themes across the 60 repos," "what does the auth subsystem do as a whole" — the org-level sensemaking that today requires a human reading many files.
• Local search ≈ what Atlas already answers. "Who calls X," "blast radius of Y" are GraphRAG local queries we serve natively. The semantic /search (pgvector) is the vector-RAG leg. So Atlas is a partial GraphRAG already; the upgrade is the community layer on top.
• Cost lesson, applied: given the indexing-cost caveat, the LazyGraphRAG stance fits our ecosystem — keep the cheap deterministic AST graph, defer LLM summarization to query time or compute community reports lazily/incrementally so we don't re-summarize 60 repos on every cron tick.
• Fits our retrieval/routing stack. A community-summary global mode is a natural retrieval tool for [[agent-memory-systems]] and [[mempalace]] (graph + summary recall over long histories), can feed a [[model-routing]] decision (route broad "sensemaking" asks to a graph-global path, precise asks to vector/local), and its multi-partial-answer map-reduce rhymes with [[mixture-of-agents]] and [[fusion-and-llm-councils]] — many partial answers reconciled into one.

See also

[[graphify]] · [[agent-memory-systems]] · [[mempalace]] · [[model-routing]] · [[mixture-of-agents]] · [[fusion-and-llm-councils]] · [[llm-maintained-wiki]] · [[llm-from-scratch]] · [[microgpt-build-an-llm-from-scratch]]