Title: Efficient GraphRAG Through Core-Based Hierarchies

Abstract: Retrieval-Augmented Generation (RAG) boosts large language models by integrating external knowledge sources. Nevertheless, conventional vector-based techniques frequently struggle with global sensemaking tasks that demand reasoning spanning numerous documents. GraphRAG mitigates this limitation by structuring documents into a knowledge graph featuring hierarchical communities subject to recursive summarization. While current GraphRAG implementations depend on Leiden clustering for community detection, we demonstrate that on sparse knowledge graphs—characterized by a constant average degree and predominantly low-degree nodes—modularity optimization yields exponentially many near-optimal partitions. This characteristic renders Leiden-derived communities inherently non-reproducible. To resolve this issue, we propose substituting Leiden clustering with k-core decomposition, a method that generates a deterministic, density-sensitive hierarchy in linear time. We present a suite of lightweight heuristics that utilize the k-core hierarchy to build connectivity-preserving, size-limited communities for retrieval and summarization, complemented by a token-budget-aware sampling strategy designed to lower LLM expenditures. Our evaluation, conducted on real-world datasets such as financial earnings transcripts, news articles, and podcasts, involves three LLMs for answer generation and five independent LLM judges for comparative assessment. Across various models and datasets, our method consistently enhances answer comprehensiveness and diversity while decreasing token consumption, establishing k-core-based GraphRAG as a robust and efficient framework for global sensemaking.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC