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.
Figures & tables
Figure 1: Overview of S-Path-RAG. Given a natural language question, the system performs entity linking to obtain top- m seed entities and enters an iterative Neural-Socratic Graph Dialogue loop. In each round, a GNN encodes the current subgraph, a weighted path enumerator proposes candidate paths, and a scorer with a verifier ranks their relevance. A soft mixture of selected path embeddings is injected into a frozen language model via cross-attention, and the resulting answer together with a diagnostic signal is mapped to graph edits that update the subgraph. The loop terminates when the model reaches sufficient confidence or the maximum number of rounds is reached.
Figure 2: Answer coverage versus number of retrieved paths for different retrieval strategies.
Table 1: Performance comparison of different methods on the two KGQA benchmarks. Best results are in bold . Hits@1 denotes the proportion of questions where the top-1 prediction is correct.
Figure 4: Answer coverage versus number of retrieved paths for different retrieval strategies.
Configuration
WebQSP (F1)
CWQ (F1)
Full S-Path-RAG
78.2
75.2
w/o Soft Injection
72.4 ( − 5.8)
68.5 ( − 6.7)
w/o Verifier
74.1 ( − 4.1)
70.7 ( − 4.5)
w/o πmap
73.7 ( − 4.5)
70.3 ( − 4.9)
w/o Alignment Loss
75.8 ( − 2.4)
72.6 ( − 2.6)
Single-round ( T=1 )
75.3 ( − 2.9)
71.8 ( − 3.4)
Table 2: Ablation study on WebQSP and CWQ validation sets (F1 score). The full S-Path-RAG baseline is aligned with Table 1 values.
Retrieval Method
WebQSP (%)
CWQ (%)
#Paths
Random Walk
76.4
79.2
48
Beam Search
82.7
83.5
52
Weighted Shortest Path
88.3
85.9
45
S-Path (Ours)
95.7
95.7
56
Table 3: Path retrieval strategy comparison (Answer Coverage %). The S-Path (Ours) values are aligned with Table 1 to ensure consistency.
Method
#LLM Calls
#Tokens
Latency (s)
GPU RAM (GB)
RoG [ 4 ]
3.0
325 ± 9
4.2 ± 0.3
15.3
ToG+ChatGPT [ 47 ]
4.2
418 ± 12
6.7 ± 0.5
17.1
GNN-RAG [ 7 ]
1.0
207 ± 5
3.1 ± 0.2
10.4
S-Path-RAG (Ours)
2.3
284 ± 7
3.8 ± 0.2
11.2
Table 4: Efficiency comparison (median ± median absolute deviation per question, A100-40GB).
Method
#Params (M)
MRR
Hits@10
TransE [ 51 ]
1250
0.426 ± 0.003
0.512 ± 0.004
ComplEX [ 52 ]
1250
0.503 ± 0.003
0.589 ± 0.003
RotatE [ 53 ]
1250
0.433 ± 0.002
0.527 ± 0.003
PairRE [ 54 ]
500
0.521 ± 0.003
0.608 ± 0.003
TripleRE [ 55 ]
501
0.579 ± 0.002
0.662 ± 0.002
AutoBLM+ [ 56 ]
500
0.546 ± 0.005
0.631 ± 0.004
Table 5: Performance comparison on OGB WikiKG 2.0 [ 50 ] . S-Path-RAG achieves superior efficiency while maintaining competitive accuracy.
Hop Count
Q/A Count
Naive RAG [ 62 ]
Naive RAG+Subquery
Hybrid RAG
Rerank RAG
Naive GraphRAG
KG RAG [ 63 ]
GraphTrace [ 21 ]
S-Path-RAG
MRR
4
1
0.5000
0.5000
0.3333
0.5000
0.0000
0.0000
0.2000
0.2800
5
2
0.7500
0.2667
0.3750
0.5000
0.0000
0.0000
0.7500
0.8200
6
23
0.4094
0.4650
0.5345
0.4301
0.0605
0.0336
0.5765
0.6500
7
47
0.3482
0.3501
0.3055
0.2889
0.0607
0.1606
0.5377
0.6200
8
17
0.2196
0.2908
0.1849
0.1737
0.0580
0.0470
0.1960
0.2700
Table 6: Retrieval performance on the converging dataset by hop count. The table reports MRR, MAP, and Hit@10 for questions requiring four to eight reasoning hops. Best results are shown in bold . S-Path-RAG consistently outperforms all baselines, with larger margins as the hop count increases.
Hop Count
Q/A Count
Naive RAG [ 62 ]
Naive RAG+Subquery
Hybrid RAG
Rerank RAG
Naive GraphRAG
KG RAG [ 63 ]
GraphTrace [ 21 ]
S-Path-RAG
MRR
4
1
0.2500
0.5000
0.2500
0.2500
0.0000
0.0000
0.2000
0.2800
5
10
0.2917
0.2010
0.3617
0.3017
0.0324
0.1091
0.3169
0.4000
6
70
0.4433
0.4037
0.3993
0.3689
0.0148
0.0798
0.4356
0.5200
7
8
0.3937
0.2661
0.3762
0.2958
0.0104
0.0114
0.3721
0.4700
8
1
1.0000
1.0000
0.5000
0.5000
0.0909
1.0000
0.5000
0.6000
Table 7: Retrieval performance on the divergent dataset by hop count. The table reports MRR, MAP, and Hit@10 for questions requiring four to eight reasoning hops. Best results are highlighted in bold . S-Path-RAG shows consistent gains, particularly for more complex multi-hop queries.
Hop Count
Q/A Count
Naive RAG [ 62 ]
Naive RAG+Subquery
Hybrid RAG
Rerank RAG
Naive GraphRAG
KG RAG [ 63 ]
GraphTrace [ 21 ]
S-Path-RAG
MRR
4
4
0.2500
0.3542
0.1542
0.3208
0.0625
0.0000
0.4750
0.5500
5
6
0.3667
0.2750
0.3111
0.3472
0.0833
0.1667
0.3806
0.4800
6
77
0.3498
0.3371
0.3364
0.3292
0.0916
0.0480
0.4475
0.5300
MAP
4
4
0.0625
0.1522
0.0385
0.1576
0.0156
0.0000
0.3552
0.4200
Table 8: Retrieval performance on the linear dataset by hop count. The table reports MRR, MAP, and Hit@10 for questions requiring four to six reasoning hops. Best results are highlighted in bold . S-Path-RAG remains superior across hop levels.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Error Type
Proportion
Underlying Cause
Fixable
■ Entity-link drift
34 %
Ambiguous or incomplete aliases
Yes
■ Path over-scoring
28 %
Semantically plausible but incorrect chains
Yes
■ Premature termination
22 %
Over-confident stopping criterion
Yes
■ Excessive path length
16 %
Hop limit exceeded ( L=4 )
No
Appendix
Table 9: Error categories identified from 200 failure cases and their estimated repairability.
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.
Yasaman Zarrinkia, Venkatesh Srinivasan, Alex Thomo
To augment Large Language Models (LLMs) for multi-hop question answering, a mainstream solution within Graph Retrieval Augmented Generation (GraphRAG) leverages lightweight retrievers to efficiently extract information from a given Knowledge Graph (KG). However, existing methods often overlook the inherent challenge of sparse semantic information in graphs. Specifically, our experiments reveal that these methods produce biased retrieval Semantic Shortcut Bias and Long-Tail Path Bias, leading to inadequate semantic modeling and limited GraphRAG effectiveness. To address these issues, we propose STAR, a semantic-tuned and tail-adaptive retriever for GraphRAG. STAR integrates two key learning paradigms: token-level interaction learning and path-weighted contrastive learning. The former employs a cross-attention architecture and a hard path mining mechanism to jointly model the query and path, thereby mitigating the Semantic Shortcut Bias. The latter introduces a tailored contrastive learning objective that utilizes tail-adaptive path weighting, designed to optimize the training process and ease the Long-Tail Path Bias. Extensive experiments demonstrate that STAR consistently outperforms baselines, achieving average retrieval performance gains of 1.8% and LLM QA performance improvements of 2.2% across all benchmark datasets. Our code is available at https://anonymous.4open.science/r/STAR-C583.
LLM-based knowledge-graph question answering (KGQA) delegates graph traversal to language models, turning each question into a sequence of local relation-selection decisions repeated across beams and hops. A common but untested default is to serialize the complete partial path into every routing prompt, even though the controller already maintains this path as exact symbolic state. Bounded Path Context (BPC) decouples these two roles: the controller retains full paths in symbolic memory for answer extraction and audit, while the relation-selection prompt exposes only the question, the current entity, outgoing relation candidates, and at most the last K hops. A controlled sweep over K -- fixing graph neighborhoods, beam budget, depth, decoding, and answer-extraction format -- shows that bounded histories match or exceed full-history prompting on complete WebQSP and CWQ test sets with Qwen3.5-9B-AWQ: K=1 achieves 0.487 answer-set F1 on WebQSP versus 0.472 for full history, and K=0 reaches 0.287 on CWQ versus 0.274, with 9.7% and 12.1% fewer input tokens respectively. At the 4B scale, K=1 remains the strongest setting on both benchmarks. Per-example analysis reveals that 71-84% of examples are unaffected by history length, while the affected cases expose when prior hops disambiguate versus distract. These results suggest that path serialization length is better treated as a tunable interface variable than as a default assumption in LLM-based graph controllers.
Xihang Shan, Ye Luo
School of Mathematical Sciences Xiamen University · School of Informatics Xiamen University