Graph-based RAG

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 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 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 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 2404.16130 §3.1.6. Card: From Local to Global: A Graph RAG Approach to Query-Focused Summarization.

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) 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%) 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 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) 2404.16130 §4.1.2. TS has the highest comprehensiveness win rate over vector RAG on the Podcast corpus, 83%, above every graph level 2404.16130 fig. 2. Against TS, C0 is level on Podcast comprehensiveness (50%) and ahead on News (56%) 2404.16130 fig. 2. TS passes the full source text as context, about 1.0M tokens per query on the Podcast corpus 2404.16130 tab. 2.

When to use which

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.

# 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 before copying any default.

Contradictions

• Headline figures versus the table. The text quotes 72% comprehensiveness and 62% diversity for C0 over vector RAG 2404.16130 §5.1. The table shows these as the Podcast comprehensiveness and News diversity values 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 2404.16130 §5.1.
• Token savings caption versus table. The community-table caption says C0 needs "9x–43x" fewer tokens per query 2404.16130 tab. 2. The table gives about 38x for Podcast and 43x for News 2404.16130 tab. 2.
• Gleaning gain. The appendix says gleaning at 600 tokens gave "almost twice" as many entity references as at 2400 2404.16130 app. A.2. The figure's values give about 1.6x with no gleaning, and about 1.4x after three rounds 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 2404.16130 §5.2. The authors say the claim threshold choice changes the results 2404.16130 §5.2.
• Model name. The introduction says GPT-4 and the appendix says gpt-4-turbo 2404.16130 §1 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: 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.