E^2GraphRAG: Streamlining Graph-based RAG for High Efficiency and Effectiveness

• Traditional RAG’s few retrieved chunks may not provide the global context needed to answer questions about a character’s full transformation.The introduction illustrates this with a question about Peter Pettigrew’s character arc in Harry Potter and the Prisoner of Azkaban.Source: §1 · p. 1
• Hierarchical trees support global understanding but miss fine-grained entities and relations, while knowledge graphs integrate dispersed details at high LLM-based extraction cost.Source: §1 · p. 2
• Existing methods face efficiency bottlenecks, limited integration of tree and graph structures, and manually pre-set local or global query modes.The paper frames the research question as developing efficient, effective graph-based RAG that adapts to different query granularities.Source: §1 · p. 2
• E2GraphRAG combines a multi-granularity summary tree with a concise SpaCy-extracted entity graph, bidirectional entity–chunk indexes, and adaptive local or global retrieval.The retrieval strategy selects local mode for densely connected query entities and otherwise uses global retrieval.Source: §1 · p. 2
• Up to 10× faster indexing than GraphRAG and 100× faster retrieval than LightRAG, while maintaining state-of-the-art or highly competitive effectiveness.Source: §1 · p. 2

• Text-based knowledge sources are easy to organize and adaptable, whereas structured entity graphs support multi-hop reasoning and aggregation but are difficult to scale when domain-specific quality requires substantial expert effort.Source: §2 · p. 2
• GraphRAG builds knowledge graphs from raw text, then clusters nodes and summarizes communities, but its LLM-heavy indexing and global retrieval add cost and latency.Its global retrieval uses an LLM to determine which communities are relevant to a query.Source: §2 · p. 2
• RAPTOR recursively clusters and summarizes chunks into a hierarchical summary tree, avoiding LLM entity-and-relation extraction but retaining time-consuming clustering and vector-based retrieval.The supplied discussion also notes that vector-based retrieval may yield inaccurate results.Source: §2 · pp. 2–3
• The paper uses “graph-based RAG” broadly, including tree-based methods because a tree is a special form of graph.Source: §2 · p. 2
• LightRAG and FastGraphRAG reduce GraphRAG’s indexing overhead but still require verbose LLM-generated JSON per chunk; LazyGraphRAG defers LLM calls and incurs high retrieval latency.Source: §2 · p. 3

3.1 Indexing Stage

• The indexing stage splits documents into overlapping 1,200-token chunks, recursively summarizes groups of chunks into a tree, and embeds chunks and summaries for dense retrieval.Adjacent chunks overlap by 100 tokens; tree nodes nearer the root are more global, while leaves retain more specific content.Source: §3.1 · pp. 3–4
• SpaCy extracts named entities and common nouns, which form a weighted co-occurrence graph linked to chunks through entity-to-chunk and chunk-to-entity indexes.Edges connect entities co-occurring in a sentence, with weights reflecting sentence-level co-occurrence frequency; identical entities and edge weights are merged across chunks.Source: §3.1 · p. 4

3.2 Retrieval Stage

• For local retrieval, SpaCy extracts query entities, and graph filtering retains pairs within a hop threshold h before index mapping finds chunks associated with both entities.Entities that cannot be mapped to graph vertices are ignored; the threshold h can be adjusted to balance the number of recalled chunks.Source: §3.2 · pp. 4–6
• When a query has no entities, retrieval uses dense search over the summary tree; when it has no related entity pairs, it uses a coarse-grained global path.The coarse-grained path retrieves 2k candidate chunks by vector similarity, ranks them by entity occurrence, and selects the top k; summary-node weights aggregate child-node weights.Source: §3.2 · p. 5
• For mapped entity pairs, the system intersects their entity-to-chunk index results and unions the resulting chunk sets to form candidate evidence.This uses the index mapping operation to find chunks associated with both entities in each retained pair.Source: §3.2 · p. 6
• If retrieval yields more than k chunks, the system tightens the hop threshold and, if needed, ranks the last non-empty set by entity coverage then occurrence before selecting top-k chunks.It formats evidence as entity pairs with supporting chunks, deduplicates chunks, merges continuous chunks, and orders entity pairs by coverage and chunks by document order.Source: §3.2 · p. 6

4.1 Experiment Settings

• Tests use Qwen2.5-7B-Instruct and Llama3.1-8B-Instruct, BGE-M3, long-document NovelQA and InfiniteBench subsets, and accuracy, ROUGE-L, indexing-time, and retrieval-time metrics.The InfiniteBench subsets are InfiniteChoice and InfiniteQA; the evaluation focuses on close-ended QA and multiple choice.Source: §4.1 · pp. 6–7

4.2 Baselines

• Comparisons include GraphRAG local and global, LightRAG hybrid, and RAPTOR; LazyGraphRAG and FastGraphRAG were excluded because of code availability or local-model compatibility constraints.RAPTOR’s prompting format was aligned with E2GraphRAG’s for comparison.Source: §4.2 · p. 7

4.3 Experimental Results

• Up to 10× faster indexing than GraphRAG and over 100× speedup over LightRAG in retrieval accompany competitive QA, including best NovelQA results with Qwen and InfiniteQA results with both backbones.The reported comparisons are summarized in Table 1.Source: §4.3 · p. 7, Table 1 · p. 7

4.4 Computational Cost Analysis

• Indexing-time curves scale linearly with the lowest slope; E2GraphRAG uses about ⌈n/(g −1)⌉ LLM calls for indexing and none during retrieval.Retrieval’s main computational cost for E2GraphRAG is SpaCy entity extraction from the question.Source: §4.4 · p. 8

4.5 Ablation Study

• Ablations show retrieval enhancements outperform dense-only retrieval, both local modules matter, and Occurrence Ranking appears more impactful globally; dense-removal gains on NovelQA may reflect hallucination.The authors attribute Occurrence Ranking’s apparent impact to its more frequent use in their datasets.Source: §4.5 · p. 9

5 Conclusion

• E2GraphRAG builds document summary trees with LLMs and extracts entity-level knowledge graphs using SpaCy to reduce time costs.The conclusion presents this as a streamlined graph-based RAG pipeline.Source: §5 · p. 9
• Its adaptive retrieval uses graph structure to locate relevant chunks and select local or global retrieval without manually predefined query settings.The summary tree and knowledge graph support adaptive local and global retrieval.Source: §5 · p. 10
• Experiments report up to 10× speedup over GraphRAG in indexing and 100× over LightRAG in retrieval, with competitive effectiveness.The conclusion characterizes efficiency as state-of-the-art across both stages.Source: §5 · p. 10

A Pseudo Code

• The procedure first extracts query entities with SpaCy; when none are found, it returns dense-retrieval chunks.The returned supplemental set is bounded by k chunks.Source: A Pseudo Code · p. 14
• When entities exist, GraphFilter selects entity pairs and IndexMapping maps them to candidate supplementary chunks.The pseudocode invokes these operations as Eqs. (1) and (2).Source: A Pseudo Code · p. 14
• If mapped candidates exceed 25, the procedure adjusts h or l and repeats filtering and mapping before returning candidates.If the candidate set becomes empty, it instead returns an EntityAwareFilter result from the previous candidate set.Source: A Pseudo Code · p. 14

B Dataset Details

• NovelQA contains 89 books and 2,305 questions; InfiniteChoice has 58 books and 229 questions, and InfiniteQA has 20 books and 102 questions.NovelQA includes 65 public-domain and 24 copyright-protected books; the two InfiniteBench datasets are publicly accessible.Source: B Dataset Details · p. 14
• Entity counts are measured in question text, excluding entities that appear only in multiple-choice options.The statistics report average, minimum, and maximum counts per question; Figure 4 groups questions into entity-count buckets.Source: B Dataset Details · p. 14, Figure 4 · p. 15

C Implementation Details of Baseline Methods

• nano-GraphRAG was used instead of the official GraphRAG implementation because its design was considered excessively redundant.LightRAG’s Hugging Face integration code was embedded in nano-GraphRAG for local deployment.Source: C Implementation Details of Baseline… · p. 15
• All methods and baselines were configured to run the full pipeline on one NVIDIA A800 GPU with 80GB of memory.GraphRAG used retrieval level 2, and LightRAG used Hybrid mode, each identified as the best setting in its corresponding paper.Source: C Implementation Details of Baseline… · p. 15
• E2GraphRAG’s k was set according to GPU memory, while h changed automatically during retrieval and was set to 4.Source: C Implementation Details of Baseline… · p. 15

D Proofs for Cost Analysis

• Retrieval-time overhead is described as relatively trivial, so the analysis provides detailed proof only for indexing cost.Source: D Proofs for Cost Analysis · p. 15
• E2GraphRAG’s tree has n leaves and g children per non-leaf node, with non-leaf counts forming a convergent geometric sequence.The passage states that the number of LLM calls equals the number of non-leaf nodes and that the sequence converges to n.Source: D Proofs for Cost Analysis · p. 15
• RAPTOR’s non-leaf nodes exceed E2GraphRAG’s because each may have at most g children, giving a lower bound of n/(g − 1).Source: D Proofs for Cost Analysis · p. 15
• LightRAG uses n LLM calls to extract entities and relations from chunks; graph assembly requires no LLM calls.Source: D Proofs for Cost Analysis · p. 15
• GraphRAG uses n LLM calls for chunk-level extraction and c more calls to summarize communities, totaling n + c.Source: D Proofs for Cost Analysis · p. 15

E Limitations

• The authors cannot exhaust all retrieval pipeline designs, so more optimal strategies may still improve performance.Source: E Limitations · pp. 15–16

F Broader Impact

• Reducing indexing and retrieval costs could improve access to large-scale knowledge systems in low-resource or cost-sensitive settings.The framework may benefit open-domain question answering, knowledge-intensive NLP, and long-document understanding.Source: F Broader Impact · p. 16
• Biased or incorrect indexed documents may produce misleading or harmful outputs, and automatic entity extraction or graph construction may propagate errors or overlook minority perspectives.The model depends heavily on the quality and neutrality of its underlying documents.Source: F Broader Impact · p. 16
• The authors do not directly address fairness or bias mitigation and recommend trustworthy data sources and human oversight; debiasing and retrieval-path transparency remain future-work directions.Source: F Broader Impact · p. 16