Large language models (LLMs) are increasingly combined with knowledge graphs (KGs) to ground reasoning in structured evidence. However, most LLM-based KGQA methods rely on traversing existing graph edges and become unreliable when reasoning paths are broken by missing facts. Alternatives that ask LLMs to generate missing knowledge risk introducing hallucinated evidence. We introduce XoG (eXplore-over-Graph), a framework for multi-hop question answering over incomplete KGs that recovers missing reasoning paths from learned graph structure rather than LLM parametric knowledge. XoG combines type-level entity-relation statistics to identify candidate relations with KG embeddings to retrieve plausible missing entities, using the LLM as a semantic selector and reasoner. These mechanisms are integrated into an iterative planning-exploration-reasoning process. Experiments on WebQSP, CWQ, and the Wikidata-based BRINK benchmark show that XoG remains competitive on complete KGs and consistently outperforms comparable methods without task-specific KGQA training under KG incompleteness. These gains persist across multiple LLM backbones, indicating that stronger LLMs alone do not resolve missing graph evidence. XoG also reduces LLM token consumption by up to 33% compared with a closely related planning-based approach.
Figures & tables
Figure 1: Comparison of LLM+KG reasoning paradigms.
Figure 2: The iterative exploration-reasoning process in XoG for answering a KG-based question.
Figure 3: Hierarchical bucketing prompt strategy for relation exploration.
Method
WebQSP
CWQ
CKG
IKG-40%
CKG
IKG-40%
CoT (Without Knowledge Graph)
GPT-3.5-Turbo
76.0
54.1
GPT-4
76.4
55.5
GPT-5.5
79.1
74.0
Claude Opus 4.8
80.7
62.8
Table 1: Hits@1 scores on WebQSP and CWQ under complete (CKG) and incomplete (IKG-40%) knowledge graph settings. CoT (No KG) is evaluated without KG access and serves as a backbone-matched LLM-only baseline. Bold indicates the best result and underlined the second best within each “No Task-Specific KGQA Training” paradigm. ▲ marks the best overall result in each column.
Figure 4: Hits@1 results on complete (CKG) and incomplete (IKG-%) knowledge graphs.
LLM Calls
Input Tokens
Output Tokens
Total Tokens
Dataset
Sparsity
PoG
XoG
Δ
PoG
XoG
Δ
PoG
XoG
Δ
PoG
XoG
Δ
CWQ
CKG
14.67
13.59
− 7%
8,852
8,192
− 7%
390
361
− 7%
9,243
8,553
− 7%
IKG-40%
17.68
14.00
− 21%
10,726
8,397
− 22%
464
373
− 20%
11,191
8,770
− 22%
IKG-80%
19.50
14.30
− 27%
11,886
8,638
− 27%
506
386
− 24%
12,393
9,024
− 27%
WebQSP
CKG
9.11
8.90
− 2%
5,391
5,160
− 4%
286
271
− 5%
5,677
5,432
− 4%
IKG-40%
13.70
9.20
− 33%
8,033
5,376
− 33%
376
258
− 31%
8,409
5,634
− 33%
Table 2: LLM usage comparison between PoG and XoG across datasets and KG sparsity versions.
KG Sparsity (%)
Bucket Size
CKG
20
40
60
80
30
80.40
80.62
80.60
80.12
80.22
40
80.32
80.12
80.32
80.02
79.82
50
79.31
78.60
79.10
78.50
78.80
70
77.99
78.29
77.89
78.19
76.98
No Hierarchy
77.38
77.28
77.08
77.28
76.97
Table 3: Effect of bucket size on relation selection hit rate on WebQSP under different KG sparsity levels. Columns are CKG (complete knowledge graph), and missing-triples rates (IKG-%).
Figure 5: Effect of retrieval quality (Hits@100) on LLM entity selection accuracy.
Method
CKG
IKG-40%
IKG-80%
XoG (full)
83.7
77.6
72.3
(a) Recovery mechanisms
w/o Relation Selection
82.9
73.8
68.9
w/o Link Prediction
76.2
62.0
67.0
(b) LLM-guided selection
w/o LLM Entity Prune (Embed top1)
77.9
69.8
65.7
Table 4: Ablation results of XoG under different sparsity levels on WebQSP.
Method
Complete
Incomplete
Supervised KGQA
G-Retriever
0.32
0.30
RoG
0.78
0.62
GNN-RAG
0.79
0.68 ▲
No Task-Specific KGQA Training (GPT-3.5-Turbo)
PoG
0.71
0.34
Table 5: F1 on the BRINK Wikidata benchmark using entity text labels, under complete and incomplete KG settings. Baseline numbers are taken from Zhou et al. (2026) . Bold indicates the best result and underlined the second best within the “No Task-Specific KGQA Training” paradigm. ▲ marks the best overall result in each column.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Metric
CKG
IKG-40%
IKG-80%
WebQSP
Accuracy
83.7
77.6
72.3
Selection Error
15.9
10.3
6.6
Retrieval Gap
84.1
89.7
93.4
CWQ
Accuracy
64.4
55.7
48.7
Selection Error
13.9
10.7
6.5
Retrieval Gap
86.1
89.3
93.5
Appendix
Table 6: Error Analysis of XoG under increasing KG incompleteness (all values in %).
Figure 6: PoG vs. XoG under varying KG sparsity on WebQSP. (a) Graph-grounded answer rate. (b) Average reasoning chain length.
Setting
GPT-3.5
Qwen3
Llama-3.3
GPT-4
GPT-5.5
Opus 4.8
WebQSP
CKG
83.7
77.9
84.9
85.7
87.3
89.2
IKG-40%
77.6
71.8
81.6
83.5
83.8
85.4
CoT
76.0
62.7
76.9
76.4
79.1
80.7
CWQ
CKG
64.4
60.6
66.1
72.0
80.5
77.6
IKG-40%
55.7
53.0
61.3
64.7
75.9
68.8
CoT
54.1
48.0
57.5
55.5
74.0
62.8
Appendix
Table 7: Hits@1 (%) of XoG with different backbone LLMs across complete (CKG), incomplete (IKG-40%), and CoT (No KG) settings.
Method
CKG
IKG-40%
IKG-80%
All Relations
6.20
6.20
6.20
Neighbors only
80.20
35.00
10.54
Relation Selection
77.99
77.89
76.98
Appendix
Table 8: Relation selection hit rate on WebQSP.
Figure 7: Effect of entity context size K on entity selection hit rate. Average answer rank (AAR) is indicated.