Core-based Hierarchies for Efficient GraphRAG

Jakir Hossain, Ahmet Erdem Sarıyüce · 2026

Read Core-based Hierarchies for Efficient GraphRAG by Jakir Hossain, Ahmet Erdem Sarıyüce (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05207.txt.

Introduction

Jakir Hossain and Ahmet Erdem Sarıyüce replace Leiden grouping in GraphRAG with k-core decomposition for hierarchical document communities. On sparse knowledge graphs, modularity tuning lets exponentially many near-best partitions, making Leiden communities inherently non-reproducible. K-core decomposition instead gives a fixed, density-aware hierarchy, and lightweight heuristics shape it into size-bounded connected communities for retrieval and summarization, with token-budget-aware sampling cutting model costs. On earnings transcripts, news, and podcasts, the approach raises comprehensiveness and diversity of answers while reducing token usage.

Catalog record

CREATORJakir Hossain, Ahmet Erdem Sarıyüce
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72668
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05207

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Core-based Hierarchies for Efficient GraphRAG Jakir Hossain, Ahmet Erdem Sarıyüce Abstract . Retrieval-Augmented Generation (RAG) enhances large language models by incorporating external knowledge. However, existing vector-based methods often fail on global sensemaking tasks that require reasoning across many documents. GraphRAG addresses this by organizing documents into a knowledge graph with hierarchical communities that can be recursively summarized. Current GraphRAG approaches rely on Leiden clustering for community detection, but we prove that on sparse knowledge graphs, where average degree is constant and most nodes have low degree, modularity optimization admits exponentially many near-optimal partitions, making Leiden-based communities inherently non-reproducible. To address this, we propose replacing Leiden with k k -core decomposition, which yields a deterministic, density-aware hierarchy in linear time. We introduce a set of lightweight heuristics that leverage the k k -core hierarchy to construct size-bounded, connectivity-preserving communities for retrieval and summarization, along with a token-budget–aware sampling strategy that reduces LLM costs. We evaluate our methods on real-world datasets including financial earnings transcripts, news articles, and podcasts, using three LLMs for answer generation and five independent LLM judges for head-to-head evaluation. Across datasets and models, our approach consistently improves answer comprehensiveness and diversity while reducing token usage, demonstrating that k k -core-based GraphRAG is an effective and efficient framework for global sensemaking. 1. Introduction Retrieval-Augmented Generation (RAG) enhances large language models (LLMs) with external knowledge, enabling more grounded and accurate responses to complex queries ( 17 ; 2 ; 33 ; 16 ; 7 ) . It is particularly useful when the corpus is too large to fit within an LLM’s context window ( 15 ; 18 ) . In a typical RAG setup, a small set of relevant records is retrieved and fed, along with the query, to the LLM for response generation. RAG has been widely adopted in domains such as healthcare, law, finance, and education, improving faithfulness, reducing hallucinations, mitigating privacy risks, and enhancing robustness ( 31 ; 30 ; 34 ; 19 ; 35 ) . Most RAG systems rely on lexical/semantic retrieval over text and are effective only for queries answerable from a few documents. These approaches struggle with multi-hop reasoning or queries requiring synthesis across semantically diverse documents or global corpus understanding ( 18 ; 15 ) . For instance, answering “How have patient outcomes in cancer treatment evolved in response to multi-center clinical trials over the last 15 years?” demands aggregating evidence across many sources, which conventional RAG methods cannot easily support. Similarly, a financial analyst asking “What common strategies have semiconductor companies adopted in response to supply chain disruptions over the past decade?” must synthesize themes across hundreds of earnings call transcripts, a task that no single retrieved passage can answer. We refer to such queries as global sensemaking tasks: they require the system to identify recurring themes, reconcile conflicting perspectives, and synthesize evidence distributed across the entire corpus, capabilities that go beyond standard RAG. Graph-based Retrieval-Augmented Generation (GraphRAG) has recently emerged as a promising approach for global sensemaking tasks by representing the corpus as a knowledge graph and organizing it into a hierarchy of communities that can be recursively summarized ( 6 ) . The GraphRAG framework introduced by 6 relies on modularity-based community detection, such as Leiden ( 28 ) . However, Leiden often produces hierarchies that are shallow, overly fragmented, and/or dominated by a few large communities. Building on an observation by Good, de Montjoye, and Clauset ( 9 ) , we prove that when the average degree is constant and most nodes have low degree—the regime of typical knowledge graphs—the number of near-optimal modularity partitions is exponential in the graph size (Theorem 1 ). This implies that Leiden-based communities are inherently non-reproducible on such graphs, compounding known issues with resolution limits and sensitivity to initialization. In practice, this instability causes communities to unpredictably merge or fragment semantically meaningful structures. Motivated by these limitations, we explore k -core–based alternatives for hierarchical graph construction in GraphRAG. The k -core decomposition organizes a network into nested layers of increasing minimum degree ( 23 ) . Each node is assigned a core number: the largest k for which it belongs to a subgraph where every node has at least k neighbors. This creates a deterministic, density-aware hierarchy that can be computed in a single O(|E|) pass. Unlike modularity-driven methods, the k -core hierarchy naturally captures progressively denser and more cohesive substructures, making it well suited for global sensemaking tasks that require integrating evidence across multiple interconnected regions of the corpus. In knowledge graphs specifically, higher k -cores correspond to entities connected through multiple distinct relational paths, providing a natural proxy for topical centrality that modularity’s comparison to a degree-preserving null model cannot capture. We operationalize this hierarchy through a set of lightweight, interpretable community construction heuristics that operate over different levels of the k -core decomposition. Our approach constructs balanced hierarchical communities while explicitly controlling cluster sizes to respect LLM context constraints. These heuristics enable comprehensive and diverse summaries without excessive token usage. Additionally, we introduce a token-budget–aware sampling strategy that further reduces LLM costs while preserving retrieval quality. We make the following key contributions: • We introduce k -core decomposition as a drop-in replacement for Leiden in GraphRAG, yielding deterministic, density-aware hierarchies in linear time. • We prove that modularity optimization on sparse graphs admits exponentially many near-optimal partitions (Theorem 1 ), formally explaining why Leiden-based community detection is unreliable on knowledge graphs. • We propose multiple hierarchical heuristic strategies that exploit different regions of the induced k -core hierarchy to balance coverage, granularity, and efficiency. • We conduct extensive evaluations on three real-world datasets, using three LLMs for answer generation and five independent LLM judges for head-to-head evaluation. 2. Related Work and Background In this section, we review the literature on Graph-based RAG and remind key concepts of GraphRAG workflows and k -core decomposition. Graph-based RAG. Traditional vector-based RAG retrieves relevant passages to augment LLM responses, but is largely limited to single-hop, fact-based queries where the answer resides within one or a few contiguous passages. When reasoning must span multiple documents or synthesize information across a corpus, these approaches fall short ( 10 ; 20 ) . To address this, several methods incorporate graph structures into the retrieval process. One line of work constructs query-focused subgraphs from knowledge graphs and performs reasoning over them. Systems such as KG-GPT ( 14 ) , G-Retriever ( 11 ) , GRAG ( 12 ) , and HLG ( 8 ) follow this paradigm, extracting relevant subgraphs and using LLMs to reason over the retrieved structure, thereby improving multi-hop answer quality. A complementary line of work enhances the retrieval step itself with graph signals, using graph topology to guide which documents or passages are selected ( 25 ; 29 ; 20 ) . However, both subgraph-reasoning and graph-enhanced retrieval methods are primarily designed for queries that require a bounded number of reasoning hops. They do not address global sensemaking , tasks where the answer requires understanding themes, patterns, or relationships that emerge only when considering an entire corpus. GraphRAG ( 6 ) addresses this gap by applying Leiden-based hierarchical community detection on a knowledge graph and using the resulting communities for global sensemaking (see

Read the complete text