TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering

Yingxu Wang; Jiaxin Huang; Mengzhu Wang; Nan Yin

cs.CLApr 13, 2026

TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering

Authors: Yingxu Wang, Jiaxin Huang, Mengzhu Wang, Nan Yin

Organizations: Mohamed bin Zayed University of Artificial Intelligence · Hebei University of Technology · City University of Hong Kong

Abstract

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
Type	Methods	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
Method	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
Method	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.

Panel of Figure 2 — Figure 2: Sensitivity analysis of hyperparameters on the WebQSP and CWQ datasets.

Method	WebQSP		CWQ
Method	#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.
TRACE	Reasoning Path : Entity (id: 1384221) $\rightarrow$ film.actor.film $\rightarrow$ film.performance.film $\rightarrow$ Race to Witch Mountain .

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
Setting	#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.
TRACE	Reasoning Path : Entity (id: 1242859) $\rightarrow$ music.group_member.instruments_played $\rightarrow$ Bass guitar .

Appendix

Table 8: Case study of TRACE. We highlight the correct answers in Red and the wrong answers in Blue .

Explore similar work

Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation
Sep 13, 2026Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar +2Multi-Hop QA Knowledge Graph Question Answering
National Yang Ming Chiao Tung University, Hsinchu, Taiwan · Independent Researcher
STEM: Structure-Tracing Evidence Mining for Knowledge Graphs-Driven Retrieval-Augmented Generation
Apr 24, 2026Peng Yu, En Xu, Bin Chen +2Graph Neural Networks Graph Retrieval-Augmented Generation
AI Product Center, Kingsoft Corporation, Beijing, China
KG-Reasoner: A Reinforced Model for End-to-End Multi-Hop Knowledge Graph Reasoning
Apr 14, 2026Shuai Wang, Yinan YuLLM Reasoning with Graphs Graph Reasoning
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden

Sep 13, 2026J/K move · Enter open · S save

Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation

Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar, Sergio A. Diaz+1

National Yang Ming Chiao Tung University, Hsinchu, Taiwan · Independent Researcher

Multi-Hop QA Knowledge Graph Question Answering Multi-Hop Reasoning Knowledge Graphs CoT Faithfulness

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation

STEM: Structure-Tracing Evidence Mining for Knowledge Graphs-Driven Retrieval-Augmented Generation

KG-Reasoner: A Reinforced Model for End-to-End Multi-Hop Knowledge Graph Reasoning