# Core-based Hierarchies for Efficient GraphRAG

arXiv: https://arxiv.org/abs/2603.05207 · HTML: https://mlsanity.com/paper/2603.05207/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 19 of 19)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries](https://mlsanity.com/paper/2401.15391/) (2024)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [Knowledge Graph Prompting for Multi-Document Question Answering](https://mlsanity.com/paper/2308.11730/) (2023)
- [CBR-RAG: Case-Based Reasoning for Retrieval Augmented Generation in LLMs for Legal Question Answering](https://mlsanity.com/paper/2404.04302/) (2024)
- [Enhancing Financial Sentiment Analysis via Retrieval Augmented Large Language Models](https://mlsanity.com/paper/2310.04027/) (2023)
- [Query Focused Abstractive Summarization: Incorporating Query Relevance, Multi-Document Coverage, and Summary Length Constraints into seq2seq Models](https://mlsanity.com/paper/1801.07704/) (2018)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [In Search of Needles in a 11M Haystack: Recurrent Memory Finds What LLMs Miss](https://mlsanity.com/paper/2402.10790/) (2024)
- [RAM-EHR: Retrieval Augmentation Meets Clinical Predictions on Electronic Health Records](https://mlsanity.com/paper/2403.00815/) (2024)
- [Hierarchical Lexical Graph for Enhanced Multi-Hop Retrieval](https://mlsanity.com/paper/2506.08074/) (2025)
- [AutoPatch: Multi-Agent Framework for Patching Real-World CVE Vulnerabilities](https://mlsanity.com/paper/2505.04195/) (2025)
- [Fine-Tuning vs. RAG for Multi-Hop Question Answering with Novel Knowledge](https://mlsanity.com/paper/2601.07054/) (2026)
- [Fast Hierarchy Construction for Dense Subgraphs](https://mlsanity.com/paper/1610.01961/) (2016)
- [ReTAG: Retrieval-Enhanced, Topic-Augmented Graph-Based Global Sensemaking](https://mlsanity.com/paper/2509.25814/) (2025)

## Built on by (most cited first, 2 of 2)

- [Task-Adaptive Retrieval over Agentic Multi-Modal Web Histories via Learned Graph Memory](https://mlsanity.com/paper/2604.07863/) (2026)
- [Knowledge Graph-Augmented Ambient AI for Clinical Note Generation](https://mlsanity.com/paper/2609.22239/) (2026)

## Abstract (arXiv)

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.