---
kind: concept
slug: graph-based-rag
title: Graph-based RAG
summary: >-
  Answers questions over a whole text collection by having an LLM extract an entity graph, clustering it hierarchically, and pre-writing a summary for each community; queries run map-reduce over those summaries. Trade-off: slow, LLM-heavy indexing, and the evidence is LLM-judged on two corpora of about 1M tokens each. Vector RAG is better for single-fact lookup.
tags: [rag, knowledge-graph, summarization, community-detection]
papers: ["2404.16130"]
related: [retrieval-augmented-generation, community-detection, text-summarization, dense-retrieval, llm-as-a-judge]
status: draft
updated_at: 2026-10-24
---

## Overview

Vector retrieval returns passages similar to the question, which suits
questions whose answer sits in a few passages. It does not suit questions about
the whole collection, such as its main themes [arxiv:2404.16130 §1]. Graph-based
RAG builds a graph from the corpus ahead of time and answers from summaries of
that graph. The shared idea is to index once with an LLM, then answer many
queries from precomputed material [arxiv:2404.16130 §3.1]. The invariant that
the variants share is that the graph is extracted from text and is not given.

## Variants

Only one paper is on the wiki so far, so the variants below are configurations
of that paper's system, not a survey of the field.

### Hierarchical community summaries with map-reduce queries

The indexing phase chunks the corpus, extracts entities and relations per
chunk, optionally gleans missed items, merges duplicates, partitions the graph
with Leiden recursively, and writes an LLM report per community bottom-up
[arxiv:2404.16130 §3.1.1–§3.1.5]. Each query is answered by map-reduce over
those reports: one partial answer per window of about 8k tokens, then a final
answer from the highest-scoring partials [arxiv:2404.16130 §3.1.6]. Card:
[From Local to Global: A Graph RAG Approach to Query-Focused Summarization](/papers/2404.16130).

### Community level as a cost dial

The same index can be queried at different community levels. The paper
compares root-level (C0), two middle levels (C1, C2) and low level (C3)
[arxiv:2404.16130 §4.1.2]. Higher levels hold more text per query, so
root-level answers are cheapest. On the Podcast corpus, C0 uses 26,657 context
tokens, 2.6% of the full corpus, against 746,100 (73.5%) for C3 [arxiv:2404.16130
tab. 2]. Win rates over vector RAG rise from C0 to C3 on comprehensiveness (72%
to 79%) and diversity (77% to 81%) [arxiv:2404.16130 fig. 2]. On the News corpus
C0's claim count per answer is the highest of the graph levels, at 34.18
against 33.14 for C3 [arxiv:2404.16130 tab. 3]. C0 is the cheapest level in
the paper; C3 has the highest Podcast comprehensiveness win rate of the graph
levels.

### Baselines, not graph-based

Two comparison systems appear in the paper: vector RAG (SS) and map-reduce over
the source text (TS) [arxiv:2404.16130 §4.1.2]. TS has the highest
comprehensiveness win rate over vector RAG on the Podcast corpus, 83%, above
every graph level [arxiv:2404.16130 fig. 2]. Against TS, C0 is level on Podcast
comprehensiveness (50%) and ahead on News (56%) [arxiv:2404.16130 fig. 2]. TS
passes the full source text as context, about 1.0M tokens per query on the
Podcast corpus [arxiv:2404.16130 tab. 2].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Single fact in a few passages, or exact-match lookup | Vector RAG | Vector RAG wins on directness by design, which is the paper's control criterion [arxiv:2404.16130 fig. 2] |
| Questions about themes or the whole collection, and the corpus is large | Any graph level (C0 to C3) | All four levels beat vector RAG on comprehensiveness and diversity in the authors' LLM-judged runs [arxiv:2404.16130 fig. 2] |
| Query-time token budget is tight | C0 (root level) | About 2.6% of the corpus tokens per query on Podcast [arxiv:2404.16130 tab. 2] |
| Highest win rate matters more than query cost | C3 (low level) | Highest Podcast comprehensiveness win rate among graph levels [arxiv:2404.16130 fig. 2], at about 73.5% of corpus tokens [arxiv:2404.16130 tab. 2] |
| Indexing budget is small or the corpus changes often | Vector RAG, or re-index rarely | Podcast indexing took 281 minutes on gpt-4-turbo, and indexing token cost is not reported [arxiv:2404.16130 §4.1.3] |
| Corpus well under 1M tokens | Not decided by this paper | Tested only on two corpora of about 1M tokens each [arxiv:2404.16130 §4.1.1] |
| Need for empowerment or specific detail | Check first | Empowerment is mixed, 43–58% over vector RAG on Podcast, and the authors suggest tuning the extraction prompts to keep specific details [arxiv:2404.16130 §5.1] [arxiv:2404.16130 fig. 2] |

## Implementation sketch

Indexing runs once per corpus. Querying runs once per question. Values are the
paper's experimental settings where it gives them. The paper leaves the
clustering options and the indexing summary budget unstated.

```pseudocode
# Indexing, once per corpus  [§3.1.1]
chunks = split(docs, size=600, overlap=100)  # experiment setting [§4.1.1]

# Extract entities and relations per chunk  [§3.1.2] [app. A.1]
entities, rels = [], []
for c in chunks:
    e, r = llm_extract(c)
    # Glean: ask whether items were missed, and add them  [app. A.2]
    e, r = glean(c, e, r)
    entities += e
    rels += r

# Merge duplicates by exact name; summarise descriptions  [§3.1.3]
graph = merge(entities, rels)

# Recursive Leiden: each level covers every node once  [§3.1.4]
levels = hierarchical_leiden(graph)  # options not stated

# Bottom-up community reports under a token budget  [§3.1.5]
reports = summarise_communities(levels, budget=TOKEN_BUDGET)  # not stated


# Query, once per question  [§3.1.6]
def global_answer(query, reports, budget=8000):
    # Shuffle, then pack reports into windows of at most `budget` tokens
    random.shuffle(reports)
    windows = pack_into_windows(reports, budget)

    # Map: one partial answer and a 0-100 score per window, in parallel
    partials = parallel_map(lambda w: answer_and_score(query, w), windows)

    # Drop score-0 answers, then reduce best-first within the budget
    partials = [p for p in partials if p.score > 0]
    partials.sort(key=lambda p: p.score, reverse=True)
    context = pack_in_order(partials, budget)
    return summarise(query, context)  # final answer
```

The paper's settings and the public implementation differ in chunk size,
clustering defaults and query budget. Check the settings in the
[GraphRAG card](/papers/2404.16130) before copying any default.

## Contradictions

- **Headline figures versus the table.** The text quotes 72% comprehensiveness
  and 62% diversity for C0 over vector RAG [arxiv:2404.16130 §5.1]. The table
  shows these as the Podcast comprehensiveness and News diversity values
  [arxiv:2404.16130 fig. 2]. The text gives ranges of 72–83% (Podcast) and
  72–80% (News) for comprehensiveness, and 75–82% (Podcast) and 62–71% (News)
  for diversity [arxiv:2404.16130 §5.1].
- **Token savings caption versus table.** The community-table caption says C0
  needs "9x–43x" fewer tokens per query [arxiv:2404.16130 tab. 2]. The table
  gives about 38x for Podcast and 43x for News [arxiv:2404.16130 tab. 2].
- **Gleaning gain.** The appendix says gleaning at 600 tokens gave "almost
  twice" as many entity references as at 2400 [arxiv:2404.16130 app. A.2]. The
  figure's values give about 1.6x with no gleaning, and about 1.4x after three
  rounds [arxiv:2404.16130 fig. 3].
- **Judge versus claims.** Claim-based counts agree with the LLM judge on 78%
  of non-tied comprehensiveness pairs and 69–70% of diversity pairs, and ties
  are 33–39% of pairs [arxiv:2404.16130 §5.2]. The authors say the claim
  threshold choice changes the results [arxiv:2404.16130 §5.2].
- **Model name.** The introduction says GPT-4 and the appendix says
  gpt-4-turbo [arxiv:2404.16130 §1] [arxiv:2404.16130 §4.1.3]. The answering and
  judging models are not stated.

## Papers

- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](/papers/2404.16130): LLM-extracted entity graph, hierarchical Leiden communities, pre-written community reports, and map-reduce answers over them; author-reported win rates against vector RAG and map-reduce over source text.