# The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 19 references that are in the map.
- First posted on arXiv 23 Sep 2026.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Phi-4-Mini Technical Report: Compact yet Powerful Multimodal Language Models via Mixture-of-LoRAs](https://mlsanity.com/paper/2503.01743/) (2025)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [MQuAKE: Assessing Knowledge Editing in Language Models via Multi-Hop Questions](https://mlsanity.com/paper/2305.14795/) (2023)
- [Gemma 4 Technical Report](https://mlsanity.com/paper/2607.02770/) (2026)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering](https://mlsanity.com/paper/2405.13873/) (2024)
- [Decoding on Graphs: Faithful and Sound Reasoning on Knowledge Graphs through Generation of Well-Formed Chains](https://mlsanity.com/paper/2410.18415/) (2024)
- [GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum](https://mlsanity.com/paper/2603.28533/) (2026)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning](https://mlsanity.com/paper/2607.18481/) (2026)
- [The Role of Exploration Modules in Small Language Models for Knowledge Graph Question Answering](https://mlsanity.com/paper/2509.07399/) (2025)
- [GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation](https://mlsanity.com/paper/2604.01610/) (2026)
- [Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation](https://mlsanity.com/paper/2609.14528/) (2026)

## Abstract (arXiv)

Small language models (SLMs) are increasingly paired with knowledge graphs (KGs), yet end-to-end KG question answering conflates graph access, search, navigation, reasoning, and answer generation. This coupling makes it difficult both to determine whether an SLM can faithfully execute the reasoning path implied by a question and to attribute failures to navigation rather than to other stages of the pipeline. We isolate this capability by employing the THESEUS navigation and traceability framework and using frozen, off-the-shelf SLMs as local action policies. At each hop, the environment exposes the legal outgoing graph actions, and the model selects one executable graph action and decides whether to stop, without task-specific parameter updates, model-controlled beam search, or free-form answer generation. This controlled setting allows us to evaluate terminal-answer accuracy with Hits@1 together with path fidelity, using Path Edit Distance (PED) as the primary trajectory metric. Across the Kinship and MQuAKE-ST KGQAs, similarly sized local models differ substantially in answer accuracy and path fidelity, with the two metrics sometimes favoring different models. This model-dependent behavior also extends to prompting, as a single demonstrated trajectory can improve or degrade navigation depending on the model. These results motivate evaluating SLM graph reasoning beyond endpoint accuracy alone.