The Reasoning Bottleneck in Graph-RAG: Structured Prompting and Context Compression for Multi-Hop QA

Yasaman Zarrinkia; Venkatesh Srinivasan; Alex Thomo

cs.IRMar 14, 2026

The Reasoning Bottleneck in Graph-RAG: Structured Prompting and Context Compression for Multi-Hop QA

Authors: Yasaman Zarrinkia, Venkatesh Srinivasan, Alex Thomo

Organizations: University of Victoria · Santa Clara University

Abstract

Graph-RAG systems achieve strong multi-hop question answering by indexing documents into knowledge graphs, but strong retrieval does not guarantee strong answers. Evaluating KET-RAG, a leading Graph-RAG system, on three multi-hop QA benchmarks (HotpotQA, MuSiQue, 2WikiMultiHopQA), we find that 77% to 91% of questions have the gold answer in the retrieved context, yet accuracy is only 35% to 78%, and 73% to 84% of errors are reasoning failures. We propose two augmentations: (i) SPARQL chain-of-thought prompting, which decomposes questions into triple-pattern queries aligned with the entity-relationship context, and (ii) graph-walk compression, which compresses the context by ~60% via knowledge-graph traversal with no LLM calls. SPARQL CoT improves accuracy by +2 to +14 pp; graph-walk compression adds +6 pp on average when paired with structured prompting on smaller models. Surprisingly, we show that, with question-type routing, a fully augmented budget open-weight Llama-8B model matches or exceeds the unaugmented Llama-70B baseline on all three benchmarks at ~12x lower cost. A replication on LightRAG confirms that our augmentations transfer across Graph-RAG systems.

Figures & tables

Figure 1: SPARQL CoT prompting. The model generates a SPARQL query whose triple patterns align with the retrieved context, then traces variable bindings to produce the answer in a single LLM call.

Figure 2: Graph-walk context compression. BFS from question-anchored seed entities identifies structurally connected entities, assembled into compressed context organized by hop level. No LLM calls required.

Component	Model	Cost
Embeddings	MiniLM-L6-v2 (384d)	Free
Index LLM	Llama-3.1-8B (Groq)	$0.05/M
QA (budget)	Llama-3.1-8B (Groq)	$0.05/M
QA (standard)	Llama-3.3-70B (Groq)	$0.59/M

Table 1: Model stack. The index is built once with the 8B model and reused across all QA configurations.

Dataset	Ours	KET Low	KET High
HotpotQA	90.8 (454/500)	60.2	82.6
MuSiQue	77.2 (386/500)	77.0	79.6
2WikiMHQA	81.0 (405/500)	—	—

Table 2: Context coverage (%) with budget components compared to KET-RAG Huang et al. (2025) with GPT-4o-mini + OpenAI embeddings.

		All Questions									Covered Questions
		Hotpot			MuSiQue			2Wiki			Hotpot (454)			MuSiQue (386)			2Wiki (405)
Method	Model	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM
Base	8B	67.0	59.5	49.4	23.6	18.0	12.4	31.4	29.1	24.2	69.6	62.2	51.5	27.5	21.2	15.8	32.1	30.1	24.7
+GW	8B	63.6	55.9	46.0	19.4	14.6	9.0	30.4	28.1	24.8	66.3	58.3	48.0	22.6	17.0	11.4	33.1	30.8	26.9
SPARQL	8B	70.6	60.8	49.4	28.8	22.6	15.4	45.6	36.9	31.0	74.4	64.2	52.6	34.8	27.4	19.7	49.9	40.6	33.6
+GW	8B	76.6	62.2	50.6	30.6	22.9	15.8	55.8	41.1	34.8	79.5	64.9	52.9	35.1	26.4	20.0	59.5	44.5	37.5

Table 3: Results (%) on 500 paired questions per dataset. “Covered” = gold answer present in context (count in parentheses). Bold = best per column. GW = graph-walk compression. F1/EM use SQuAD normalization; 8B outputs are LLM-normalized to short answers (§ 4 ).

Accuracy $\Delta$ (pp)
Model	Hotpot	MuSiQue	2Wiki
8B	$+3.6$	$+5.2$	$+14.2$
70B	$+2.2$	$+8.6$	$+12.2$
Abstain $\Delta$ (pp)
8B	$-6.4$	$-31.4$	$-24.4$
70B	$+0.4$	$-8.2$	$-4.2$

Table 4: Effect of SPARQL CoT: accuracy

\Delta

(pp) and abstain

\Delta

(pp) vs. baseline, without GW.

Method	8B Acc	8B Abs	70B Acc	70B Abs
Baseline	31.4	46.0	48.8	34.8
Generic CoT	52.6	25.2	56.4	36.8
SPARQL CoT	45.6	21.6	61.0	30.6
Routing	58.4	14.2	66.4	26.8

Table 5: CoT ablation on 2WikiMHQA (without GW).

	Accuracy (%)			Abstain (%)
Dataset	8B	70B	$\Delta$	8B	70B	$\Delta$
HotpotQA	79.8	78.0	$+1.8$	1.0	5.6	$-4.6$
MuSiQue	35.6	35.2	$+0.4$	6.2	16.2	$-10.0$
2WikiMHQA	64.8	48.8	$\mathbf{+16.0}$	7.2	34.8	$\mathbf{-27.6}$

Table 6: 8B with routing + GW vs. unaugmented 70B baseline on KET-RAG. Routing classifies each question, applies the preferred CoT, and falls back on abstain.

Method	Model	Hot.	Mus.	2Wi.	Avg
Base	8B	$-3.4$	$-4.2$	$-1.0$	$-2.9$
Base	70B	$+1.2$	$+4.6$	$+4.8$	$+3.5$
SPARQL	8B	$+6.0$	$+1.8$	$+10.2$	$+6.0$
SPARQL	70B	$-0.6$	$-1.6$	$-1.2$	$-1.1$

Table 7: Effect of graph-walk compression: accuracy

\Delta

(pp) vs. non-GW config.

Config	Hotpot	MuSiQue	2Wiki
8B Baseline	84	73	80
70B + SPARQL CoT	74	64	69

Table 8: Reasoning share of total errors (%): incorrect answers where the gold answer was present in context.

	HotpotQA		2WikiMHQA				MuSiQue
Model	Bri.	Comp.	Comp.	BrCmp.	Cmp.	Inf.	2h	3h	4h
8B	$+3.0$	$+5.9$	$+16.6$	$+18.2$	$+10.9$	$+3.7$	$+8.7$	$-0.6$	$+4.5$
70B	$+2.3$	$+2.0$	$+4.9$	$\mathbf{+28.1}$	$+12.5$	$+3.7$	$+9.4$	$+5.5$	$+11.1$

Table 9: SPARQL CoT accuracy improvement (pp) over baseline, by question type. HotpotQA: bridge (398) and comparison (102). 2WikiMHQA: compositional (205), bridge_comparison (121), comparison (120), inference (54). MuSiQue: by hop depth (264/146/90).

Dataset	Category	SPARQL+8B	Base+70B
Hotpot	Bridge (398)	$+4.3$	$+1.2$
Hotpot	Comparison (102)	$+12.8$	$+1.0$
2Wiki	Composit. (205)	$+5.8$	$-1.0$
	Br-Comp. (121)	$+11.6$	$+17.4$
	Comparison (120)	$+13.3$	$+2.5$
	Inference 00 (54)	$+16.7$	$+3.7$

Table 10: GW accuracy

\Delta

(pp) by question type / hop depth. Counts in parentheses.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

		All Questions									Covered Questions
		Hotpot			MuSiQue			2Wiki			Hotpot (450)			MuSiQue (374)			2Wiki (417)
Method	Model	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM	Acc	F1	EM
Base	8B	62.2	55.1	45.2	26.6	19.3	12.8	32.2	29.0	24.6	65.8	57.8	47.3	34.2	23.7	16.6	34.5	31.2	26.6
+GW	8B	54.4	47.8	38.4	25.4	18.1	11.8	35.2	31.9	27.6	56.0	49.1	39.1	30.7	22.0	15.2	35.7	32.2	27.6
SPARQL	8B	66.8	57.5	46.6	37.4	26.9	18.6	57.4	44.3	36.2	69.6	59.3	47.8	46.3	33.0	24.1	61.9	47.1	38.8
+GW	8B	66.2	55.2	44.4	33.6	23.5	15.8	56.4	44.6	37.8	69.3	57.0	45.6	40.1	28.1	20.3	60.2	46.6	39.8

Appendix

Table 11: LightRAG generality experiment (%) on 500 paired questions per dataset. “Covered” = gold answer present in LightRAG context (count in parentheses). Bold = best per model group. GW = graph-walk compression. F1/EM use SQuAD normalization; 8B outputs are LLM-normalized to short answers (§ 4 ).

Explore similar work

S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering
Mar 5, 2026Rong Fu, Yemin Wang, Tianxiang Xu +5Knowledge Graph Question Answering Multi-Hop QA
University of Macau · Xiamen University · Peking University +3
Query-Aware Spreading Activation for Multi-Hop Retrieval over Knowledge Graphs
Jun 29, 2026Illia Makarov, Mykola GlybovetsMulti-Hop QA Graph Retrieval-Augmented Generation
National University of Kyiv-Mohyla Academy Kyiv, Ukraine
LivingRAG: Augmenting Graph RAG with Experience
Aug 26, 2026Yuzhuo Cui, Zongye Zhang, Qingjie LiuRetrieval-Augmented Generation Graph Retrieval-Augmented Generation
State Key Laboratory of Virtual Reality Technology and Systems, Beihang University, Beijing, China · Hangzhou Innovation Institute, Beihang University, Hangzhou, Zhejiang, China

Mar 5, 2026J/K move · Enter open · S save

S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering

Rong Fu, Yemin Wang, Tianxiang Xu, Yongtai Liu+4

University of Macau · Xiamen University · Peking University+3

Knowledge Graph Question Answering Multi-Hop QA Graph Retrieval-Augmented Generation LLM Reasoning with Graphs

Open paper AskPDF arXiv

We present S-Path-RAG, a semantic-aware shortest-path Retrieval-Augmented Generation framework designed to improve multi-hop question answering over large knowledge graphs. S-Path-RAG departs from one-shot, text-heavy retrieval by enumerating bounded-length, semantically weighted candidate paths using a hybrid weighted

k

-shortest, beam, and constrained random-walk strategy, learning a differentiable path scorer together with a contrastive path encoder and lightweight verifier, and injecting a compact soft mixture of selected path latents into a language model via cross-attention. The system runs inside an iterative Neural-Socratic Graph Dialogue loop in which concise diagnostic messages produced by the language model are mapped to targeted graph edits or seed expansions, enabling adaptive retrieval when the model expresses uncertainty. This combination yields a retrieval mechanism that is both token-efficient and topology-aware while preserving interpretable path-level traces for diagnostics and intervention. We validate S-Path-RAG on standard multi-hop KGQA benchmarks and through ablations and diagnostic analyses. The results demonstrate consistent improvements in answer accuracy, evidence coverage, and end-to-end efficiency compared to strong graph- and LLM-based baselines. We further analyze trade-offs between semantic weighting, verifier filtering, and iterative updates, and report practical recommendations for deployment under constrained compute and token budgets.

Abstract

Explore similar work

S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering

Query-Aware Spreading Activation for Multi-Hop Retrieval over Knowledge Graphs

LivingRAG: Augmenting Graph RAG with Experience