# Core-based Hierarchies for Efficient GraphRAG Source: [Core-based Hierarchies for Efficient GraphRAG]() Collection index: [llms.txt]() Data updated: 2026-06-04T05:00:05.280Z Authors: Jakir Hossain, Ahmet Erdem Sar{\\i}y\\"uce Published: 2026-03-05T14:17:30.000Z ## 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-core decomposition, which yields a deterministic, density-aware hierarchy in linear time. We introduce a set of lightweight heuristics that leverage the 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-core-based GraphRAG is an effective and efficient framework for global sensemaking. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Community Summary Evaluation on podcast C2 (post-cutoff)](): Community Summary Evaluation; podcast C2 (post-cutoff); Comprehensiveness Win: 58. - [Community Summary Evaluation on podcast C3 (post-cutoff)](): Community Summary Evaluation; podcast C3 (post-cutoff); Comprehensiveness Win: 53. - [Community Summary Evaluation on news C2 (post-cutoff)](): Community Summary Evaluation; news C2 (post-cutoff); Comprehensiveness Win: 56. - [Community Summary Evaluation on news C3 (post-cutoff)](): Community Summary Evaluation; news C3 (post-cutoff); Comprehensiveness Win: 56. - [Community Summary Evaluation on semiconductor C2 (post-cutoff)](): Community Summary Evaluation; semiconductor C2 (post-cutoff); Comprehensiveness Win: 60. - [Community Summary Evaluation on semiconductor C3 (post-cutoff)](): Community Summary Evaluation; semiconductor C3 (post-cutoff); Comprehensiveness Win Count: 67. - [Comprehensiveness on podcast Leiden level C0](): Comprehensiveness; podcast Leiden level C0; Win Rate: 64. - [Comprehensiveness on podcast Leiden level C1](): Comprehensiveness; podcast Leiden level C1; Win Rate (C1 Podcast): 68. - [Comprehensiveness on news Leiden level C0](): Comprehensiveness; news Leiden level C0; Win Rate (C0): 56. - [Comprehensiveness on news Leiden level C1](): Comprehensiveness; news Leiden level C1; Win Rate: 61. - [Comprehensiveness on semiconductor Leiden level C0](): Comprehensiveness; semiconductor Leiden level C0; Win Rate: 68. - [Comprehensiveness on semiconductor Leiden level C1](): Comprehensiveness; semiconductor Leiden level C1; Win Rate (%): 72. - [Comprehensiveness on podcast](): Comprehensiveness; podcast; Win Count: 50. - [Comprehensiveness on news](): Comprehensiveness; News; Wins: 52. - [Comprehensiveness on microsoft](): Comprehensiveness; Microsoft; Wins: 48. - [Directness on podcast C2 community level post-cutoff (test)](): Directness; podcast C2 community level post-cutoff (test); Wins: 62. - [Directness on podcast C3 community level post-cutoff (test)](): Directness; podcast C3 community level post-cutoff (test); Win Count: 64. - [Directness on news C2 community level post-cutoff (test)](): Directness; news C2 community level post-cutoff (test); Wins: 56. - [Directness on C3 news community level post-cutoff (test)](): Directness; C3 news community level post-cutoff (test); Win Percentage: 61. - [Directness on semiconductor C2 community level post-cutoff (test)](): Directness; semiconductor C2 community level post-cutoff (test); Win Rate: 63. - [Directness on semiconductor C3 community level post-cutoff (test)](): Directness; semiconductor C3 community level post-cutoff (test); Wins: 58. - [Diversity on podcast Leiden level C0](): Diversity; podcast Leiden level C0; Win Rate: 68. - [Diversity on podcast Leiden level C1](): Diversity; podcast Leiden level C1; Win Rate: 72. - [Diversity on news Leiden level C0](): Diversity; news Leiden level C0; Win Rate (C0): 0.64. - [Diversity on news Leiden level C1](): Diversity; news Leiden level C1; Win Rate: 67. - [Diversity on semiconductor Leiden level C0](): Diversity; semiconductor Leiden level C0; Win Rate: 64. - [Diversity on semiconductor Leiden level C1](): Diversity; semiconductor Leiden level C1; Win Rate: 70. - [Diversity on podcast](): Diversity; podcast; Win Count: 56. - [Diversity on news](): Diversity; News; Wins: 47. - [Diversity on microsoft](): Diversity; Microsoft; Win Count: 54. - [GraphRAG Content Quality Evaluation on podcast Leiden level C2 post-cutoff](): GraphRAG Content Quality Evaluation; podcast Leiden level C2 post-cutoff; Comprehensiveness Win Count: 50. - [GraphRAG Content Quality Evaluation on podcast Leiden level C3 post-cutoff](): GraphRAG Content Quality Evaluation; podcast Leiden level C3 post-cutoff; Comprehensiveness Win: 50. - [GraphRAG Content Quality Evaluation on news Leiden level C2 post-cutoff](): GraphRAG Content Quality Evaluation; news Leiden level C2 post-cutoff; Comprehensiveness Win: 44. - [GraphRAG Content Quality Evaluation on news Leiden level C3 post-cutoff](): GraphRAG Content Quality Evaluation; news Leiden level C3 post-cutoff; Comprehensiveness Win Score: 46. - [GraphRAG Content Quality Evaluation on semiconductor Leiden level C2 post-cutoff](): GraphRAG Content Quality Evaluation; semiconductor Leiden level C2 post-cutoff; Comprehensiveness Win Count: 52. - [GraphRAG Content Quality Evaluation on semiconductor Leiden level C3 post-cutoff](): GraphRAG Content Quality Evaluation; semiconductor Leiden level C3 post-cutoff; Comprehensiveness Win Count: 51. ## Original sources and implementation [Original paper]() [PDF]()