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

arXiv: https://arxiv.org/abs/2609.14528 · HTML: https://mlsanity.com/paper/2609.14528/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 13 Sep 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 20 of 20)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [MQuAKE: Assessing Knowledge Editing in Language Models via Multi-Hop Questions](https://mlsanity.com/paper/2305.14795/) (2023)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [KQA Pro: A Dataset with Explicit Compositional Programs for Complex Question Answering over Knowledge Base](https://mlsanity.com/paper/2007.03875/) (2020)
- [TransferNet: An Effective and Transparent Framework for Multi-hop Question Answering over Relation Graph](https://mlsanity.com/paper/2104.07302/) (2021)
- [An Interpretable Reasoning Network for Multi-Relation Question Answering](https://mlsanity.com/paper/1801.04726/) (2018)
- [UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering](https://mlsanity.com/paper/1904.01246/) (2019)
- [Scalable Neural Methods for Reasoning With a Symbolic Knowledge Base](https://mlsanity.com/paper/2002.06115/) (2020)
- [ReaRev: Adaptive Reasoning for Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2210.13650/) (2022)
- [Is Multi-Hop Reasoning Really Explainable? Towards Benchmarking Reasoning Interpretability](https://mlsanity.com/paper/2104.06751/) (2021)
- [Gaussian Attention Model and Its Application to Knowledge Base Embedding and Question Answering](https://mlsanity.com/paper/1611.02266/) (2016)
- [SQUIRE: A Sequence-to-sequence Framework for Multi-hop Knowledge Graph Reasoning](https://mlsanity.com/paper/2201.06206/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA](https://mlsanity.com/paper/2609.27669/) (2026)

## Abstract (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.