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.