MnemoverseDocs

Appearance

Edward Izgorodin·Published Jul 11, 2026

The GraphRAG Tax: When a Knowledge Graph Doesn't Pay ​

GraphRAG is the practice of building an entity-and-relation knowledge graph from a corpus and retrieving over that structure instead of, or alongside, plain vector similarity. The graph tax is the build-time, query-token, and latency cost you pay for that structure. You always pay it. The only question is whether the return clears the cost.

TL;DR

  • Query type decides the case. On GraphRAG-Bench, "RAG (w rerank)" beat "GraphRAG (local)" 60.92 to 49.29 on fact retrieval, while "HippoRAG2" beat "RAG (w rerank)" 53.38 to 42.93 on complex reasoning — one table, both verdicts (arXiv:2506.05690).
  • Cost is a spectrum, not a flat penalty. Query prompts span about 879 tokens for vanilla RAG to about 331,375 for "MS-GraphRAG(global)" on one split; index build runs about 9.2M ("HippoRAG2") to 115.5M (GraphRAG) tokens. The query and build figures come from two different primaries.
  • The strongest graph wins are LLM-judged. Global sensemaking wins under an LLM judge with no gold answers; on ground-truth ROUGE-2 the same comparison flips and GraphRAG loses. Ask which instrument produced the number.
  • The decision is a matrix, not a fashion. A graph pays when multi-hop queries are a real share of traffic, the corpus is stable enough to amortize the index, and the budget absorbs the upfront cost.

As of July 2026, the clearest return appears on multi-hop and relational queries over corpora stable enough to amortize the index. Simple lookup often fails that test. Global sensemaking can pass it — but only under specific evaluation instruments, and that qualifier turns out to matter more than any single score.

GraphRAG vs RAG: one benchmark, two verdicts ​

The strongest argument against a category-level verdict comes from a single table.

On GraphRAG-Bench, "RAG (w rerank)" scored 60.92 on fact retrieval, while "GraphRAG (local)" scored 49.29. The graph method spent far more prompt tokens and returned the lower score (arXiv:2506.05690, Table 2). For direct fact retrieval, the graph was a tax without a return.

The direction reversed on complex reasoning in the same table. "HippoRAG2" scored 53.38 against 42.93 for "RAG (w rerank)", with "GraphRAG (local)" at 50.93 for reference (arXiv:2506.05690, Table 2).

Both verdicts are valid inside that benchmark. Neither shows that all graph methods beat, or lose to, all RAG methods. What the table proves is narrower and more useful: "graphs are better" and "graphs are worse" are both true, depending on the question. The unit of decision is therefore the query class, not the architecture label.

The three GraphRAG costs: build, query, and latency ​

The tax is not one number. It breaks into three costs — build, query, and latency — and they come from different studies, which changes how much any single comparison proves.

Build tax ​

Index construction can consume enough tokens to decide the architecture before the first user query arrives. In the reported construction analysis, "HippoRAG2" used about 9.2 million indexing input tokens against about 115.5 million for GraphRAG — roughly a twelvefold gap (arXiv:2502.14802, Table 12 / Appendix F). A costly index can still pay for itself, but only if enough suitable queries arrive, over enough time, to amortize the offline work.

Query tax ​

Prompt cost is a spectrum, not a fixed GraphRAG penalty. On the Novel split of GraphRAG-Bench, "MS-GraphRAG(global)" used about 331,375 query tokens in total — with single prompts reaching roughly 40,000 tokens — against about 879 for vanilla RAG. Lighter graph methods sat between them: LightRAG at about 100,832, Fast-GraphRAG at about 4,204, and "HippoRAG2" at about 1,008 (arXiv:2506.05690, Section 4.4, Figures 8–9). "Graph equals expensive" is too crude: query cost spans more than two orders of magnitude across methods. Pick the method, not the category.

Disclosure. The build-tax figures ("HippoRAG2" 9.2M vs GraphRAG 115.5M) and the query-tax figures ("MS-GraphRAG(global)" 331,375 vs 879) come from two different primaries with different method sets — arXiv:2502.14802 and arXiv:2506.05690. No single primary places index-build cost and query-token cost for the same method on one axis. Combining them here yields a useful tax model, not one controlled comparison.

Latency tax ​

Extra structure does not guarantee slower queries. On LongMemEval, Zep's temporal-graph memory cut query latency from 28.9 seconds to 2.58 seconds (about 90%) with up to 18.5% relative accuracy gain on gpt-4o (arXiv:2501.13956). A Provenance-Aware Tiered Memory scheme reported 54.1% fewer tokens and 60.7% lower latency at query time on LoCoMo, at a small accuracy cost (0.851 vs 0.873) (arXiv:2602.17913). These are structured-memory results rather than direct GraphRAG comparisons; treat them as directional. The narrow lesson holds either way: build-time work can buy query-time speed, so evaluate the whole path instead of assuming a graph always adds latency.

When GraphRAG pays the tax ​

Multi-hop retrieval ​

Multi-hop retrieval is the clearest case. Against the cited NV-Embed-v2 dense baseline, "HippoRAG2" raised Recall@5 from 76.5 to 90.4 on 2Wiki and from 69.7 to 74.7 on MuSiQue, and moved from 94.5 to 96.3 on HotpotQA (arXiv:2502.14802). This is a graph method that beats dense retrieval on multi-hop questions while spending fewer query tokens than heavy GraphRAG variants.

Agentic search narrows the advantage without erasing it. The averaged Dense-versus-GraphRAG multi-hop advantage barely moved: +27.23 in single-shot retrieval, +26.59 under GraphSearch. Measured separately against the second-best GraphRAG variant, GraphSearch narrowed the gap by 32.3% — a dent, not a collapse. The single-hop advantage, framed there as general question answering, stayed negligible at +0.47 (arXiv:2604.09666). Once its offline index is amortized, GraphRAG keeps a stable multi-hop lead even against agentic RAG.

Global sensemaking and the evaluation seam ​

The strongest graph wins come from a softer instrument. For breadth-oriented sensemaking questions, GraphRAG community summaries reached 72–83% comprehensiveness and 62–82% diversity win rates under an LLM judge with no gold answers, and root-level summaries cut answer tokens by about 97% (arXiv:2404.16130).

Ground-truth scoring tells a different story. On ROUGE-2 against gold answers, the same kind of comparison flips: GraphRAG loses to plain RAG — 6.99 vs 10.08 on SQuALITY and 3.23 vs 6.32 on QMSum — and summary-ordering position bias can even flip the LLM judge's preference (arXiv:2502.11371).

Both results are true. One measures which answer a model prefers; the other measures overlap with a gold answer. Before accepting any GraphRAG win, ask: Was the result judged by a model, or scored against ground truth? That single question separates a benchmark verdict from a decision framework.

A caution from a single knowledge base ​

The newest primary adds one more warning against category-level claims. On a single KB, STaRK-Prime — a precision-medicine knowledge base of about 129,000 entities — "RAG with Entity Description and Relations Documents" scored 0.6972 Hit@1 / 0.7531 MRR, beating "GraphRAG with vector search and predefined KG" at 0.6514 / 0.7072. "Autonomous Agentic RAG with minimal tools" was best overall at 0.6881 / 0.7549, and context optimization cut tokens by 19–53% (arXiv:2606.25656). This is one semi-structured knowledge base; it should not be generalized without a second corpus.

When to use GraphRAG: the decision matrix ​

The decision couples three axes. In short: single-hop lookup → the graph is pure tax; multi-hop or relational → the graph can pay; global sensemaking → the graph wins under an LLM judge only. Corpus churn and budget then decide whether that potential return survives contact with production.

Query mixStable corpus, budget availableStable corpus, tight budgetHigh corpus churn
Mostly single-hop lookupPrefer vector RAG; fact retrieval favored "RAG (w rerank)" (source).Prefer vector RAG; spend on reranking or context selection before graph construction.Prefer the cheaper index; a graph adds cost with no shown lookup return.
Material multi-hop / relational shareTest "HippoRAG2" or another graph method; multi-hop shows the clearest return (source).Test lighter graph methods; prompt cost varies widely across implementations (source).Consider low-cost indexing, but measure freshness in your own system; the churn verdict is inferred.
Global corpus sensemakingA graph may pay when LLM-judged breadth and diversity match the product goal (source).Test LazyGraphRAG or bounded global search; keep judge bias visible.Avoid full rebuilds unless query value covers them; validate any low-cost path under real updates.
Mixed trafficRoute by query class rather than forcing one retriever on every request.Use the cheapest method that preserves measured task quality.Separate fast-changing material from graph-worthy stable relations — an architectural inference, not a benchmark.

LazyGraphRAG is one escape hatch on the churn axis. Microsoft reports indexing cost identical to vector RAG and 0.1% of full GraphRAG cost. On global queries it matched GraphRAG Global Search quality at more than 700× lower query cost, relative to GraphRAG Global Search only, and its Z500 configuration ran at about 4% of GraphRAG global query cost while winning on both local and global queries (Microsoft Research).

Lower indexing cost makes frequent rebuilding more plausible, but it does not prove better freshness. The churn axis here is inferred from index cost — no cited primary measures re-indexing under corpus churn head-to-head.

What the GraphRAG decision doesn't settle ​

Graph size is a separate ceiling. GraphArena reports Claude-3.5 NP-complete accuracy falling from 47.8 to 7.2 between small and large graphs (arXiv:2407.00379). GraphOmni reports GPT-4o Diameter-task hallucination rising from 16% to more than 80% as graphs grow from 5 to 30 nodes, while serialization format alone swings accuracy by as much as 40% (arXiv:2504.12764). A graph index does not make a language model a reliable graph algorithm; structural operations at scale belong behind algorithm tools.

Once a graph earns its retrieval tax, traversal policy is the next problem. The cost figures reported for GraphRunner need the same care as the rest: its retrieval-cost multiplier is a token-count estimate priced at GPT-4 list rates, while only latency was measured wall-clock. See Navigating knowledge graphs for that evidence and the traversal decision.

Three limits remain. The freshness axis is inferred from index cost, not benchmarked under churn. The June-2026 result stands on a single KB, STaRK-Prime, and should not be generalized. LLM-judged sensemaking stays distinct from gold-answer scoring. No May–July 2026 rebuttal to the base corpus (arXiv:2502.11371, 2506.05690, 2404.16130) surfaced, and the newest primary reinforces the thesis — so the verdict holds as of July 2026, not permanently.

The defensible conclusion: use graph retrieval where relational query value exceeds the build, prompt, and latency tax. Otherwise, keep the simpler path.

Common questions ​

GraphRAG vs RAG: which is better for factual lookup? ​

On GraphRAG-Bench, "RAG (w rerank)" scored 60.92 on fact retrieval while "GraphRAG (local)" scored 49.29, at far lower token cost. The graph advantage appears on multi-hop and relational questions, not simple lookup (arXiv:2506.05690, Table 2).

When should I use GraphRAG instead of RAG? ​

Use GraphRAG when a measurable share of your query traffic is multi-hop or relational and your corpus is stable enough to amortize the index build. For single-hop fact lookup, plain RAG is cheaper and more accurate (arXiv:2506.05690).

How much does a knowledge graph cost to build in tokens? ​

One study reports about 9.2M indexing input tokens for "HippoRAG2" versus about 115.5M for GraphRAG — roughly 12× (arXiv:2502.14802, Table 12 / Appendix F).

How much do GraphRAG query prompts cost? ​

It is a spectrum. On the Novel split of GraphRAG-Bench, "MS-GraphRAG(global)" used about 331,375 prompt tokens versus about 879 for vanilla RAG, with "HippoRAG2" at about 1,008 and LightRAG at about 100,832 (arXiv:2506.05690, Figures 8–9).

Do GraphRAG's sensemaking wins hold up against ground truth? ​

Not always. Global sensemaking wins (comprehensiveness 72–83%, diversity 62–82%) are LLM-judged with no gold answers; on ground-truth ROUGE-2, GraphRAG loses to plain RAG (6.99 vs 10.08 on SQuALITY). Ask which instrument produced a number (arXiv:2404.16130; arXiv:2502.11371).

Can GraphRAG handle frequently changing data? ​

The freshness case is inferred from index cost, not measured by a churn benchmark. LazyGraphRAG indexes at 0.1% of full GraphRAG cost, which makes re-indexing more plausible without proving freshness (Microsoft Research).

Edward Izgorodin · Mnemoverse · last updated 2026-07-11