Multi-hop Knowledge Graph Question Answering (KGQA) requires coherent reasoning across relational paths, yet existing methods often treat each reasoning step independently and fail to effectively leverage experience from prior explorations, leading to fragmented reasoning and redundant exploration. To address these challenges, we propose Trajectoryaware Reasoning with Adaptive Context and Exploration priors (TRACE), an experiential framework that unifies LLM-driven contextual reasoning with exploration prior integration to enhance the coherence and robustness of multihop KGQA. Specifically, TRACE dynamically translates evolving reasoning paths into natural language narratives to maintain semantic continuity, while abstracting prior exploration trajectories into reusable experiential priors that capture recurring exploration patterns. A dualfeedback re-ranking mechanism further integrates contextual narratives with exploration priors to guide relation selection during reasoning. Extensive experiments on multiple KGQA benchmarks demonstrate that TRACE consistently outperforms state-of-the-art baselines.
Figures & tables
Figure 1: Overview of the proposed TRACE. Dynamic Context Generation translates evolving reasoning paths into natural language narratives, preserving semantic coherence across reasoning steps. Exploration Generalization abstracts prior exploration trajectories into reusable experiential priors that capture recurring exploration patterns. Finally, Dual-Feedback Re-ranking integrates contextual narratives with exploration priors to refine relation selection and enhance the robustness of multi-hop reasoning.
Datasets
#Train
#Valid
#Test
WebQSP
2,848
250
1,639
CWQ
27,639
3,519
3,531
Table 1: Statistics of KGQA benchmarks.
Type
Methods
WebQSP
CWQ
Hits@1
F1
Hits@1
F1
Semantic Parsing
KV-Mem
46.7
34.5
18.4
15.7
EmbedKGQA
66.6
-
45.9
-
QGG
73.0
73.8
36.9
37.4
NSM
68.7
62.8
47.6
42.4
TransferNet
71.4
-
48.6
-
Table 2: Performance comparison (%) on WebQSP and CWQ datasets. Bold results indicate the best performance.
Method
WebQSP
CWQ
Hits@1
F1
Hits@1
F1
TRACE (Llama2-13B)
88.1
78.3
74.3
70.7
TRACE (Qwen3-14B)
88.4
79.1
73.9
70.1
TRACE (GPT 4.1-mini)
90.3
80.6
75.7
71.3
TRACE (GPT 4.1)
91.6
81.7
76.9
72.9
Table 3: Performance of TRACE using different LLM-based planners as backbones on the WebQSP and CWQ datasets. Bold values denote the best results.
Method
WebQSP
CWQ
Hits@1
F1
Hits@1
F1
TRACE w/o CT
89.0
78.0
74.1
70.6
TRACE w/o ER
88.6
77.4
74.8
71.1
TRACE w/o ALL
87.5
76.7
73.6
69.9
TRACE
91.6
81.7
76.9
72.9
Table 4: The results of ablation studies on the WebQSP and CWQ datasets. Bold results indicate the best performance.
Figure 2: Sensitivity analysis of hyperparameters on the WebQSP and CWQ datasets.
Method
WebQSP
CWQ
#Tokens
#Calls
#Tokens
#Calls
DoG
22,538
30.9
37,741
58.1
ToG
16,372
23.2
26,183
41.9
RwT
10,680
15.1
17,885
28.6
TRACE
8,782
14.2
16,414
27.8
Table 5: Statistics of average number of LLM calls and token consumption per question on WebQSP and CWQ datasets.
Question
What featured Kim Richards and was producted by Ann Marie Sanerlin?
Answer
Race to Witch Mountain
Llama-2-13B
The TV movie "The Christmas Card" (2006) featured Kim Richards and was produced by Anne Marie Sanerlin, however I couldn’t verify if it matches exactly "Ann Marie Sanerlin".
Qwen-3-14B
The 2019 film "The Last Days of American Crime" featured Kim Richards and was produced by Ann Marie Sanerlin. However, this information is not widely documented, and Sanerlin’s role in the production is not prominently noted in mainstream sources.
GPT 4.1
The project that featured Kim Richards and was produced by Ann Marie Sanerlin is the 1977 television film "The Car." Kim Richards starred in the film, and Ann Marie Sanerlin was credited as the producer.
GPT 4.1-mini
The project featuring Kim Richards and produced by Ann Marie Sanerlin is the reality TV series "The Real Housewives of Beverly Hills." Kim Richards is a cast member, and Ann Marie Sanerlin has served as a producer on the show.
Table 6: Case study of TRACE. We highlight the correct answers in Red and the wrong answers in Blue .
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
WebQSP
CWQ
#Tokens
#Calls
#Tokens
#Calls
Worst
13,787
22.3
29,381
46.3
Failure
10,623
16.3
20,849
34.0
Average
8,782
14.2
16,414
27.8
Appendix
Table 7: Statistics of average number of LLM calls and token consumption per question under worst and failure cases on the WebQSP and CWQ datasets datasets.
Question
What guitar does Corey Taylor play?
Answer
Bass guitar
Llama-2-13B
Corey Taylor, the lead vocalist of Slipknot and Stone Sour, is often seen playing various guitars, but his primary guitar is a custom Ibanez RG, and he also uses other Ibanez models and Dean Guitars .
Qwen-3-14B
Corey Taylor, known for his work with Slipknot and Stone Sour, primarily plays Jackson JS Series guitars , including the JS69 and JS32 models. He also uses his signature Jackson Corey Taylor JS guitars, designed for heavy rock and metal styles.
GPT 4.1
Corey Taylor, primarily known as a vocalist for Slipknot and Stone Sour, occasionally plays guitar. He has been seen using Gibson Explorer, Gibson Les Paul, and Fender Telecaster guitars during live performances and studio sessions, especially with Stone Sour.
GPT 4.1-mini
Corey Taylor, lead vocalist of Slipknot and Stone Sour, primarily plays Gibson guitars , especially the Gibson Les Paul models. He has also been seen using Fender Stratocasters and other custom guitars during performances. His Gibson Les Paul Custom is one of his signature instruments.
Multi-Hop Knowledge Graph Question Answering (KGQA) tasks require models to assemble relational evidence along paths in a KG to answer natural-language questions. However, existing KGQA systems typically focus on predicting the final answer without explicitly modeling or validating the intermediate reasoning steps, obscuring whether the correct answers arise from faithful multi-hop reasoning. To address this limitation, we re-frame multi-hop KGQA as a question-conditioned graph navigation problem. We refer to this formulation as THESEUS - Traceable Hop-wise Evidence SEarch in a Unified Semantics. In this setting, an agent receives a KG, a question, and a topic entity, and traverses a sequence of relations towards the answer, making the reasoning path explicit. To systematically study this formulation, we provide three key contributions. (i) We augment the existing KINSHIP and MQuAKE resources into navigation-ready KGQA datasets with annotated evidence paths and paraphrased questions. (ii) We design evaluation protocols to measure path fidelity, robustness to linguistic variation, and performance across multi-hop and multi-answer questions. (iii) We adapt established path-based KG completion agents - MINERVA, MultiHopKG, and SQUIRE - to operate on full question embeddings rather than symbolic single-relation queries, enabling their trajectories to be guided by natural-language semantics. Together, these contributions advance KGQA research toward systems where traceability is fundamental: answers are accompanied by explicit reasoning paths whose agreement with reference evidence can be systematically evaluated.
Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar +2
National Yang Ming Chiao Tung University, Hsinchu, Taiwan · Independent Researcher
Knowledge Graph-based Question Answering (KGQA) plays a pivotal role in complex reasoning tasks but remains constrained by two persistent challenges: the structural heterogeneity of Knowledge Graphs(KGs) often leads to semantic mismatch during retrieval, while existing reasoning path retrieval methods lack a global structural perspective. To address these issues, we propose Structure-Tracing Evidence Mining (STEM), a novel framework that reframes multi-hop reasoning as a schema-guided graph search task. First, we design a Semantic-to-Structural Projection pipeline that leverages KG structural priors to decompose queries into atomic relational assertions and construct an adaptive query schema graph. Subsequently, we execute globally-aware node anchoring and subgraph retrieval to obtain the final evidence reasoning graph from KG. To more effectively integrate global structural information during the graph construction process, we design a Triple-Dependent GNN (Triple-GNN) to generate a Global Guidance Subgraph (Guidance Graph) that guides the construction. STEM significantly improves both the accuracy and evidence completeness of multi-hop reasoning graph retrieval, and achieves State-of-the-Art performance on multiple multi-hop benchmarks.
Peng Yu, En Xu, Bin Chen +2
AI Product Center, Kingsoft Corporation, Beijing, China
Large Language Models (LLMs) exhibit strong abilities in natural language understanding and generation, yet they struggle with knowledge-intensive reasoning. Structured Knowledge Graphs (KGs) provide an effective form of external knowledge representation and have been widely used to enhance performance in classical Knowledge Base Question Answering (KBQA) tasks. However, performing precise multi-hop reasoning over KGs for complex queries remains highly challenging. Most existing approaches decompose the reasoning process into a sequence of isolated steps executed through a fixed pipeline. While effective to some extent, such designs constrain reasoning flexibility and fragment the overall decision process, often leading to incoherence and the loss of critical intermediate information from earlier steps. In this paper, we introduce KG-Reasoner, an end-to-end framework that integrates multi-step reasoning into a unified "thinking" phase of a Reasoning LLM. Through Reinforcement Learning (RL), the LLM is trained to internalize the KG traversal process, enabling it to dynamically explore reasoning paths, and perform backtracking when necessary. Experiments on eight multi-hop and knowledge-intensive reasoning benchmarks demonstrate that KG-Reasoner achieves competitive or superior performance compared to the state-of-the-art methods. Codes are available at the repository: https://github.com/Wangshuaiia/KG-Reasoner.
Shuai Wang, Yinan Yu
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden