PaperlayerView exact revision on arXiv

Source-linked AI summary

KET-RAG: A Cost-Efficient Multi-Granular Indexing Framework for Graph-RAG

Yiqian Huang, Shiqi Zhang, Xiaokui Xiao

arXiv:2502.09304v2cs.IR

TL;DR

KNN-based Graph-RAG misses entity relationships, while LLM-built knowledge graphs are costly to index. KET-RAG combines a skeleton from selected chunks with a text-keyword graph over all chunks; it reports retrieval quality comparable to or better than Microsoft’s Graph-RAG with substantially lower indexing costs.

  • Problem

    KNN graphs miss entity relationships within chunks, while LLM-extracted knowledge-graph triplets improve retrieval and generation quality but incur high indexing costs, especially on large datasets.

    Source: §1 · p. 1

  • Method

    KET-RAG builds an LLM-extracted knowledge-graph skeleton from PageRank-selected core chunks and a lightweight text-keyword bipartite graph from all chunks, searching both during retrieval.

    Source: §1 · p. 2, §5.1 · p. 5

  • Results

    KET-RAG matches or surpasses Microsoft’s Graph-RAG in retrieval quality while reducing indexing costs by over an order of magnitude; generation quality improves by up to 32.4% with 20% lower indexing costs.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The authors conclude KET-RAG is a cost-efficient alternative to full-scale knowledge-graph indexing.

    Source: §6.3 · p. 8, §7 · p. 9

    LightRAG results on MuSiQue are excluded because its original implementation showed unexpected behavior.

    Source: §6.3 · p. 8

Abstract

from arXiv · show

Graph-RAG constructs a knowledge graph from text chunks to improve retrieval in Large Language Model (LLM)-based question answering. It is particularly useful in domains such as biomedicine, law, and political science, where retrieval often requires multi-hop reasoning over proprietary documents. Some existing Graph-RAG systems construct KNN graphs based on text chunk relevance, but this coarse-grained approach fails to capture entity relationships within texts, leading to sub-par retrieval and generation quality. To address this, recent solutions leverage LLMs to extract entities and relationships from text chunks, constructing triplet-based knowledge graphs. However, this approach incurs significant indexing costs, especially for large document collections. To ensure a good result accuracy while reducing the indexing cost, we propose KET-RAG, a multi-granular indexing framework. KET-RAG first identifies a small set of key text chunks and leverages an LLM to construct a knowledge graph skeleton. It then builds a text-keyword bipartite graph from all text chunks, serving as a lightweight alternative to a full knowledge graph. During retrieval, KET-RAG searches both structures: it follows the local search strategy of existing Graph-RAG systems on the skeleton while mimicking this search on the bipartite graph to improve retrieval quality. We evaluate 13 solutions on three real-world datasets, demonstrating that KET-RAG outperforms all competitors in indexing cost, retrieval effectiveness, and generation quality. Notably, it achieves comparable or superior retrieval quality to Microsoft's Graph-RAG while reducing indexing costs by over an order of magnitude. Additionally, it improves the generation quality by up to 32.4% while lowering indexing costs by around 20%.

1 Introduction

KET-RAG pairs a knowledge-graph skeleton built from selected chunks with a lightweight text-keyword bipartite graph built from all chunks. The reported results show substantially lower indexing costs while maintaining or improving retrieval and generation quality.

1 Introduction

  • KNN graphs are inexpensive but miss within-chunk entity relationships, whereas LLM-extracted knowledge-graph triplets improve quality at high indexing cost.Processing a 3.2MB HotpotQA sample costs $21; a single 5GB legal case is estimated at $33K.Source: §1 · p. 1
  • KET-RAG selects core chunks by PageRank centrality for an LLM-built knowledge-graph skeleton and constructs a lightweight text-keyword bipartite graph from all chunks.At retrieval, it extracts ego networks through both entity and keyword channels for LLM-based generation.Source: §1 · p. 2
  • Over an order of magnitude lower indexing costs accompany retrieval quality comparable to or better than Microsoft’s Graph-RAG [8]; generation quality improves up to 32.4% with approximately 20% lower indexing costs.The evaluation covers 13 solutions on three datasets.Source: §1 · p. 2
  • Skeleton-RAG reduces indexing costs by 20% while maintaining retrieval quality; Keyword-RAG improves retrieval and generation over Text-RAG without compromising retrieval latency.Keyword-RAG reports relative improvements of up to 92.4% in Coverage, 133.3% in EM, 118.5% in F1 scores, and 12.9% in BERTScore.Source: §1 · p. 2

2 Preliminaries

The section establishes text-attributed graphs and the local-search Graph-RAG setting, then describes Microsoft’s Graph-RAG indexing and retrieval operations relevant to the paper.

2.1 Terminologies and Notations

  • A TAG index represents text chunks as nodes with text embeddings and can represent edges with text attributes and embeddings.The section also introduces notation for sets, concatenated text, and token counts.Source: §2.1 · p. 2, Table 1 · p. 2

2.2 Problem Formulation

  • The objective is to construct a TAG index with lower indexing costs and higher result accuracy in the widely adopted local-search setting.Text-RAG retrieves chunks by embedding similarity, while Graph-RAG retrieves and serializes a locally searched subgraph for LLM generation.Source: §2.2 · p. 2

2.3 Microsoft’s Graph-RAG

  • Microsoft’s Graph-RAG builds a knowledge graph with multi-level communities and supports tailored local and global search; this section focuses on local search.KG-Index uses an LLM to identify entities and extract relationships from each chunk, then links those entities and relationships to the chunk.Source: §2.3 · pp. 2–3
  • Local retrieval selects seed entities by embedding similarity, then prioritizes adjacent relationships and text chunks until the context limit is reached.The retrieved entities, relationships, and chunks are concatenated as generation context.Source: §2.3 · p. 3

3 Related Works

Prior Graph-RAG work spans similarity-based chunk graphs, LLM-extracted knowledge graphs, and varied local-search strategies; these approaches trade indexing cost against relationship detail and retrieval effectiveness.

3 Related Works

  • KNN graph methods connect chunks through physical adjacency, shared keywords, Wikipedia entities, or semantic similarity [21] [35].Li et al. [21] combine structural and lexical similarity; Wang et al. [35] use multiple lexical measures.Source: §3 · p. 3
  • KNNG-RAG is more cost-effective but lacks fine-grained entity relationships, while KG-RAG improves retrieval quality at substantial indexing cost, especially for large collections.LLMs extract entity-relation triplets for knowledge-graph indices [7, 8, 14, 20].Source: §3 · p. 3
  • The review also excludes publicly curated indices that encode explicit links such as co-authorship, citations, and trade relationships.The authors refer readers to surveys [9] [29] [39] for a comprehensive review.Source: §3 · p. 3
  • Local-search alternatives include ego networks, k-hop subgraphs with LLM reranking, shortest paths, personalized PageRank, and query-aware subgraph generation [17] [20] [7] [22] [14] [16].Hybrid-RAG [32] and EWEK-QA [6] query both text and knowledge graphs.Source: §3 · p. 3

4 Proposed Framework: KET-RAG

KET-RAG combines a knowledge-graph skeleton built from selected core chunks with a text-keyword bipartite graph built from all chunks. Its two retrieval channels use entity and keyword seeds to retrieve complementary context.

4 Proposed Framework: KET-RAG

  • KET-RAG integrates keywords, entities, and text chunks through a skeleton graph and a text-keyword bipartite graph.The skeleton comes from selected important chunks, while the bipartite graph is constructed from all chunks.Source: §4 · p. 3, §4.1 · p. 3

4.1 Overview

  • Steps 1–3 build the index; steps 4–5 retrieve context from the skeleton and keyword channels.The skeleton is built from core chunks selected in a KNN graph; the bipartite graph links keyword nodes to chunks, and retrieval divides the context budget between entity and keyword seeds.Source: Figure 1 · p. 4, §4.1 · p. 4

4.2 Rationale and Comparison

  • A skewed KNN degree distribution motivates prioritizing core chunks, whose structural importance helps connect different parts of the graph.The figure presents the degree distribution on MuSiQue; the text-keyword graph’s keyword neighbors serve as candidates for entity ego-network information.Source: §4.2 · p. 4, Figure 2 · p. 4
  • Compared with prior KG-RAG solutions [7] [8] [14] [20], KET-RAG uses a smaller chunk set for LLM-based graph construction and a lightweight keyword channel.The keyword channel limits retrieval to snippets containing seed keywords, rather than searching all text chunks as Text-RAG does.Source: §4.2 · pp. 4–5

5 Detailed Implementations

KET-Index builds the skeleton and keyword graph; KET-Retrieval searches both within a context budget. The cost analysis describes lower indexing costs and equal upper-bounded retrieval and generation costs across solutions.

5.1 KET-Index

  • KET-Index selects ⌈β·|V|⌉ core chunks by PageRank in a hybrid lexical-semantic KNN graph, builds the skeleton, and links chunk subnodes to keyword nodes.It recursively splits chunks over τ iterations and gives each keyword node an average embedding of sentences containing that keyword.Source: §5.1 · p. 5

5.2 KET-Retrieval

  • KET-Retrieval allocates θλ tokens to skeleton retrieval and (1−θ)λ to keyword-seeded retrieval, then combines both contexts.Both channels return fine-grained sub-chunks, which the paper says reduces noise and preserves the context limit.Source: §5.2 · p. 5

5.3 Cost Analysis

  • KET-Index uses a β fraction of KG-Index’s input and output costs, adds 3ℓ·|T| embedding tokens, and shares the same upper-bounded retrieval and generation costs as other solutions.The added embeddings cover chunk, sub-chunk, and sentence levels; retrieval and generation costs are bounded by the maximum token parameter.Source: §5.3 · p. 6

6 Experiments

Across five experimental questions, KET-RAG is evaluated for quality, indexing cost, parameter trade-offs, and retrieval latency. It generally preserves strong retrieval and generation quality at lower indexing cost than competing approaches.

6.1 Experimental Settings

  • The experiments sample 500 QA instances per dataset; MuSiQue and HotpotQA use Coverage, EM, F1, and BERTScore, while RAG-QA Arena uses LLM-judged Win Rate.Low-cost and high-accuracy settings use chunk sizes ℓ=1,200 and ℓ=150, respectively.Source: §6.1 · p. 6, §6.2 · p. 7

6.2 Performance Evaluation (RQ1)

  • KET-RAG-U/-P achieves 77.0%/80.2% coverage on MuSiQue and 81.6%/82.6% on HotpotQA; low-cost KET-RAG-P uses 18.3% of competitors’ indexing cost on HotpotQA.The results compare KET-RAG with existing methods across low- and high-cost settings.Source: Table 2 · p. 7, §6.2 · p. 7, Table 3 · p. 8
  • Low-cost KET-RAG improves Hybrid-RAG’s EM/F1/BERTScore by 37.2%/31.3%/0.3% on MuSiQue and 26.5%/26.9%/0.9% on HotpotQA, while reducing indexing costs by 19%.On RAG-QA Arena, it improves on HippoRAG by 3.1%.Source: §6.2 · p. 7

6.3 Ablation Study (RQ2)

  • Skeleton-RAG reduces indexing cost by 20%, with low-cost EM decreases of 3.5% and 7.4% on MuSiQue and HotpotQA; Keyword-RAG’s low-cost Coverage/EM/F1 gains are 92.4%/133.3%/118.5% and 61.8%/52.5%/58.8%.KET-RAG-P also exceeds KET-RAG-U by up to 1.0%/4.5%/4.4% in Coverage/EM/F1 on MuSiQue.Source: §6.3 · pp. 7–8

6.4 Trade-off Analysis (RQ3)

  • Across β settings, both KET-RAG variants outperform Skeleton-RAG; across θ settings, KET-RAG outperforms Hybrid-RAG, while a small MS-Graph-RAG context fraction improves Keyword-RAG.KET-RAG-P performs better than KET-RAG-U particularly at β∈[0.6, 0.8] on MuSiQue and has superior EM and F1 when θ≤0.4.Source: Figure 3 · p. 8, Figure 4 · p. 8, §6.4 · p. 9

6.5 Parameter Sensitivity (RQ4)

  • On MuSiQue, smaller input chunks or split sub-chunks improve retrieval and generation quality; changing K from 2 to 10 yields only minor metric changes, including Coverage/EM/F1 of 79.6/19.2/26.1 versus 80.4/19.4/26.0.The authors relate K stability to similar KNN-graph degree-distribution shapes across settings.Source: Table 4 · p. 9, Table 5 · p. 9, §6.5 · p. 9

6.6 Retrieval Latency (RQ5)

  • KET-RAG retrieval takes 0.39×/0.73× MS-Graph-RAG/Hybrid-RAG time on MuSiQue, 0.43×/0.80× on HotpotQA, and 0.41×/0.70× on RAG-QA Arena.KET-RAG stays under one second per query; all graph-based variants finish within 0.5 seconds in the low-cost setting.Source: Table 6 · p. 9, §6.6 · p. 9

7 Conclusions

KET-RAG combines a knowledge graph skeleton with a text-keyword bipartite graph. It matches or surpasses Microsoft’s Graph-RAG in retrieval quality while reducing indexing costs and improving generation quality.

7 Conclusions

  • KET-RAG matches or surpasses Microsoft’s Graph-RAG in retrieval quality while reducing indexing costs by over an order of magnitude.It improves generation quality by up to 32.4% with 20% lower indexing costs.Source: §7 · p. 9
  • KET-RAG integrates a knowledge graph skeleton with a text-keyword bipartite graph to improve retrieval and generation quality while reducing indexing costs.Source: §7 · p. 9
  • Future work will extend KET-RAG to global search scenarios and explore adaptive paradigms for scalable real-world deployment.Source: §7 · p. 9

Related papers

Loading 2502.09304v2…