Organizations: University at Buffalo Buffalo, NY, USA · Amazon Web Services. This publication describes work performed at University at Buffalo, and is not associated with Amazon Web Services.
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.
Figures & tables
Figure 1. k -core decomposition (left) and corresponding hierarchy tree produced by RkH (right).
Model
Dataset
# Docs
|V|
|E|
Km
GPT-3.5-turbo (post-cutoff)
podcast
36
1791
2651
6
news
609
10655
15368
6
semiconductor
183
4324
9546
13
GPT-4o-mini (post-cutoff)
podcast
13
628
882
5
news
331
5312
7316
6
semiconductor
63
2029
4249
9
Table 1. Summary statistics of datasets used in our experiments, showing model, dataset, number of documents, and graph information ( ∣V∣ : nodes, ∣E∣ : edges, Km : maximum core number). Post-cutoff data is used for GPT-3.5-turbo (cutoff: Sep 1, 2021) and GPT-4o-mini (cutoff: Oct 1, 2023), while full data is used for GPT-5-mini .
GPT-3.5-turbo
podcast
news
semiconductor
results for
C2
C3
C2
C3
C2
C3
Comprehensiveness
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
56
36
8
50
42
8
44
44
12
52
38
10
48
48
4
56
42
2
RkH LF
58
42
0
44
52
4
52
42
6
49
47
4
50
50
0
50
48
2
M2hC L1
58
36
6
52
42
6
56
34
10
50
36
14
58
42
0
48
42
10
M2hC LF
58
40
2
52
44
4
54
38
8
56
38
6
54
44
2
54
42
4
Table 2. GPT-3.5-turbo post-cutoff: Head-to-head win rates (%), for comprehensiveness and diversity metrics. C2 and C3 are Leiden community levels from Edge et al. ( Edge et al., 2024 ) . LF is leaf-level communities, and L1 is the level immediately above the leaf.
GPT-5-mini
podcast
news
microsoft
Comprehen.
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
41
47
12
56
42
2
43
43
14
RkH LF
50
48
2
50
45
5
45
40
15
M2hC L1
40
52
8
40
34
26
40
45
15
M2hC LF
52
42
6
40
40
20
48
50
2
MRC L1
48
50
2
42
38
20
45
48
7
Table 3. GPT-5-mini full: Head-to-head win rates (%), for comprehensiveness and diversity metrics against Leiden C2 level from Edge et al. ( Edge et al., 2024 ) . LF indicates leaf-level communities, and L1 indicates the level immediately above the leaf.
Cond.
podcast
news
semiconductor
C2
C3
C2
C3
C2
C3
RkH L1
<0.001
<0.001
1.000
<0.001
1.000
<0.001
RkH LF
<0.001
<0.001
<0.001
0.370
0.982
0.363
M2hC L1
<0.001
<0.001
<0.001
<0.001
<0.001
0.006
M2hC LF
<0.001
<0.001
<0.001
<0.001
<0.001
<0.001
MRC L1
0.007
1.000
<0.001
0.069
<0.001
0.073
Table 4. Wilcoxon signed-rank test p-values for comprehensiveness ( GPT-3.5-turbo ) across datasets and baselines. Values with p<0.005 are highlighted in bold .
Dataset
# Tokens
Metric
C2
C3
RkH LF
M2hC LF
MRC LF
podcast
180,267
# Comm.
291
301
351
311
194
Coverage (%)
68.93
70.87
83.70
75.47
58.08
news
1,340,078
# Comm.
2,019
2,021
2,205
1,863
1,357
Coverage (%)
65.90
71.26
76.46
65.74
55.08
semic.
438,819
# Comm.
627
696
847
705
468
Coverage (%)
66.81
72.67
90.18
76.45
59.94
Table 5. Community statistics across datasets, showing the number of communities and the percentage of source text used at different hierarchy levels and methods.
Dataset
Edge
Relative token
Comp.
Div.
budget
usage (%)
win rate (%)
win rate (%)
(%)
C2
C3
C2
C3
C2
C3
podcast
80
90
88
57
55
64
55
70
79
77
54
52
56
52
60
68
66
47
46
51
49
news
80
81
75
54
54
55
58
Table 6. RRTC ( M2hC Leaf) vs. Leiden C2/C3: Head-to-head win rates (%) on comprehensiveness and diversity
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Condition
podcast
news
semiconductor
C2
C3
C2
C3
C2
C3
RkH L1
0.073
<0.001
0.008
<0.001
0.083
0.083
RkH LF
<0.001
<0.001
0.071
<0.001
0.008
0.007
M2hC L1
<0.001
<0.001
<0.001
0.007
<0.001
0.982
M2hC LF
<0.001
<0.001
<0.001
<0.001
0.083
<0.001
MRC L1
0.982
<0.001
<0.001
0.071
<0.001
<0.001
Appendix
Table 7. Wilcoxon signed-rank test p-values for comparisons across datasets and baselines on Diversity ( GPT-3.5-turbo ). Significant values are highlighted in bold for p<0.005 .
Table 8. GPT-3.5-turbo Head-to-Head Win Rates (%) using Leiden C2 and M2hC Level Variants on microsoft data
GPT-5-mini
podcast
news
microsoft
results for
C3
C3
C3
Comprehensiveness
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
41
41
18
52
39
9
38
43
19
RkH LF
43
43
14
47
45
8
42
48
10
M2hC L1
48
48
4
49
37
14
48
42
10
M2hC LF
50
47
3
47
35
18
47
48
5
Appendix
Table 9. GPT-5-mini full: Head-to-head win rates (%), for comprehensiveness and diversity metrics. C3 is the Leiden community level from Edge et al. ( Edge et al., 2024 ) . LF indicates leaf-level communities, and L1 indicates the level immediately above the leaf.
GPT-3.5-turbo
podcast
news
semiconductor
results for
C0
C1
C0
C1
C0
C1
Comprehensiveness
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
50
42
8
68
24
8
56
32
12
48
42
10
66
30
4
72
26
2
RkH LF
58
42
0
52
44
4
40
50
10
42
44
14
68
32
0
52
46
2
M2hC L1
48
46
6
66
28
6
50
40
10
50
36
14
54
46
0
62
28
10
M2hC LF
58
40
2
68
28
4
44
48
8
44
49
7
60
38
2
72
24
4
Appendix
Table 10. GPT-3.5-turbo post-cutoff: Head-to-head win rates (%), for comprehensiveness and diversity metrics. C0 and C1 are Leiden community levels from Edge et al. ( Edge et al., 2024 ) . LF indicates leaf-level communities, and L1 indicates the level immediately above the leaf.
GPT-4o-mini
podcast
news
semiconductor
results for
C2
C3
C2
C3
C2
C3
Comprehensiveness
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
50
50
0
50
50
0
38
42
20
40
42
18
46
46
8
39
36
25
RkH LF
50
48
2
46
48
6
40
40
20
43
40
17
52
41
7
49
32
19
M2hC L1
48
46
6
48
44
8
42
42
16
44
44
12
44
40
16
51
30
19
M2hC LF
50
48
2
50
46
4
44
40
16
46
42
12
52
38
10
50
24
26
Appendix
Table 11. GPT-4o-mini post-cutoff : Head-to-head win rates (%), for comprehensiveness and diversity metrics. C2 and C3 are Leiden community levels from Edge et al. ( Edge et al., 2024 ) . LF indicates leaf-level communities, and L1 indicates the level immediately above the leaf.
GPT-3.5-turbo
podcast
news
semiconductor
results for
C2
C3
C2
C3
C2
C3
Comprehensiveness
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
Win
Loss
Tie
RkH L1
48
50
2
52
45
3
46
52
2
63
37
0
52
48
0
47
52
1
RkH LF
52
43
5
54
43
3
46
50
4
57
40
3
50
50
0
50
50
0
M2hC L1
54
44
2
59
39
2
63
35
2
55
45
0
40
59
1
53
43
4
M2hC LF
50
46
4
54
46
0
46
51
3
46
54
0
61
38
1
52
44
4
Appendix
Table 12. GPT-3.5-turbo post-cutoff: Head-to-head win rates (%), for empowerment and directness metrics. C2/C3 are Leiden community levels, LF is leaf-level communities, and L1 is the level immediately above the leaf
Retrieval-Augmented Generation (RAG) has emerged as a paradigm for enhancing large language models (LLMs) with external knowledge, yet existing graph-based methods face a fundamental limitation: entity-centric and chunk-centric approaches operate on representations anchored to original text without true knowledge fusion. While entity-centric methods connect logically related content and chunk-centric methods preserve context, both retrieve information separately through similarity search, missing emergent understanding from their synthesis. In this paper, we propose HyGRAG, a hierarchical graph RAG framework that transcends source documents by addressing three core challenges: constructing summaries that genuinely integrate contextual and relational information, leveraging these synthesized representations to access emergent knowledge during retrieval, and efficiently updating hierarchical structures for dynamic corpora. Specifically, we design hierarchical index structures over hybrid graphs with both chunk and entity nodes, then iteratively cluster them and generate LLM-based summaries. Then, we design context and relation-aware retrieval that searches across all abstraction levels while expanding through community membership. Moreover, we enable dynamic knowledge update through attachment-based algorithms with only local re-summarization. Experimental results show that HyGRAG improves the average accuracy of multi-hop reasoning tasks by 9.7%, while maintaining reasonable efficiency.
Haoyang Zhong, Yifei Sun, Antong Zhang +3
Zhejiang University Hangzhou, China · Nanyang Technological University Singapore, Singapore · Finvolution Group Shang Hai, China
Retrieval-Augmented Generation (RAG) mitigates hallucinations in Large Language Models (LLMs) by grounding the generation process on external knowledge. However, standard RAG approaches struggle with multi-hop reasoning. While recent graph-based RAG methods improve the retrieval of interconnected chunks, they often rely on computationally expensive and error-prone LLM-based extraction pipelines. To address these issues, we propose TIGRAG (Token-Induced GraphRAG), an efficient graph-augmented RAG framework based on a token co-occurrence Knowledge Graph. TIGRAG directly models topological relationships between tokens using sliding-window co-occurrence statistics, thus enabling scalable graph construction. During inference, it combines graph-based semantic expansion and neural reranking to retrieve interconnected evidence for multi-hop reasoning. Specifically, it introduces an iterative entity-driven retrieval strategy that progressively expands the query using bridging entities extracted from previously retrieved contexts. We evaluated TIGRAG on three widely adopted multi-hop Question Answering (QA) benchmarks. Experimental results demonstrated that our framework consistently outperforms dense retrieval and graph-based RAG methods in both retrieval and downstream QA tasks, while substantially reducing indexing time, inference latency, and prompt footprint.
Gianluca Bonifazi, Christopher Buratti, Michele Marchetti +5
aUniversità Politecnica delle Marche, Ancona, Italy · bUniversità di Modena e Reggio Emilia, Modena, Italy
Retrieval-Augmented Generation (RAG) systems empower large language models (LLMs) with external knowledge, yet struggle with efficiency-accuracy trade-offs when scaling to large knowledge graphs. Existing approaches often rely on monolithic graph retrieval, incurring unnecessary latency for simple queries and fragmented reasoning for complex multi-hop questions. To address these challenges, this paper propose SPLIT-RAG, a multi-agent RAG framework that addresses these limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval. The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG. The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types, while lightweight LLM agents are assigned to partitioned subgraphs, and only relevant partitions are activated during retrieval, thus reduce search space while enhancing efficiency. Finally, a hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications. Extensive experimental validation demonstrates considerable improvements compared to existing approaches.
Ruiyi Yang, Hao Xue, Imran Razzak +3
University of New South Wales Sydney, NSW, Australia · Mohamed Bin Zayed University of Artificial Intelligence Abu Dhabi, UAE · Griffith University Queensland, Australia +1