Source-linked AI summary
The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA
Eduin E. Hernandez, Sergio A. Diaz, Luis F. Garcia, Nurassyl Askar, Stefano Rini
TL;DR
End-to-end KGQA combines navigation with other stages, so it is difficult to determine whether an SLM faithfully follows a question’s reasoning path. This paper evaluates frozen SLMs as local graph-action policies and finds that answer accuracy and path fidelity can favor different models, while one demonstrated trajectory can help or hurt depending on the model.
Problem
End-to-end KGQA combines graph access, search, navigation, reasoning, and answer generation, limiting direct evaluation of whether an SLM can faithfully execute a reasoning path.
Source: §1 · p. 1Method
Results
Across KINSHIP and MQUAKE-ST, similarly sized models differ substantially in answer accuracy and path fidelity; the metrics can rank models differently, and a single demonstration can improve or degrade performance depending on the model.
Source: §4 · pp. 3–4, §5 · p. 4Takeaways & Limitations
The results support evaluating SLM graph reasoning beyond endpoint accuracy alone by measuring the executed path as well as the terminal answer.
Source: §1 · p. 1Structured-output compatibility is required for model inclusion, so the evaluation is limited to models meeting that interface requirement.
Source: §3 · p. 3
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
End-to-end KGQA systems combine graph access, search, navigation, and answer synthesis, making it difficult to assess whether an SLM can choose the right graph actions. This work isolates local navigation and evaluates answer correctness alongside path fidelity.
1. INTRODUCTION
- The study isolates whether frozen, off-the-shelf SLMs can select legal local graph actions and decide when to stop, without retrieval, search, or answer synthesis in the decision loop.The controlled setting is intended to distinguish navigation failures from failures in other pipeline stages.Source: §1 · p. 1
- Answer accuracy alone does not establish path fidelity, so the study evaluates terminal correctness alongside ordered trajectory agreement and structural edge overlap.Path Edit Distance (PED) is the primary trajectory metric; the evaluation compares locally deployable SLMs on KINSHIP and MQUAKE-ST under zero-shot and one-shot conditions.Source: §1 · p. 1
- Prior compact KG-agent work emphasizes task-specific training, while this study characterizes frozen SLM navigation and examines a single demonstration and a ToG-style scaffold.The scaffold comparison on MQUAKE-ST examines how explicit search and answer-generation components affect terminal accuracy and trajectory fidelity.Source: §1 · pp. 1–2
2. TASK FORMULATION AND EVALUATION
The paper formulates multi-hop KGQA as executing a valid graph path from a known topic entity to a valid answer. It evaluates the terminal answer and the fidelity of the executed path separately.
2. TASK FORMULATION AND EVALUATION
- A valid KGQA path starts at the known topic entity, follows directed graph triplets, and ends at an entity in the question’s valid answer set.The agent is not given the underlying reasoning length and instead operates under a fixed maximum horizon N.Source: §2 · p. 2
- At each step, the SLM selects an indexed legal graph action or null and decides whether to stop; the controller executes legal transitions and returns the terminal entity as the answer.A null action is valid only when stopping; otherwise navigation continues until stopping or reaching the maximum horizon.Source: §2 · p. 2
- Hits@1 measures whether the terminal entity is a valid answer, while PED measures ordered edge-sequence distance and F1SG measures order-invariant edge overlap.PED is the primary path metric; PED = 0 denotes an exact reference-path match, and lower values indicate closer agreement.Source: §2 · p. 2
- Together, Hits@1 and the path metrics provide a controlled measure of local navigation against which added search or task-specific adaptation can be evaluated.Table 1 summarizes dataset and evaluation settings, with mean reference path length denoted by k̄.Source: §2 · p. 2, Table 1 · p. 2
3. EXPERIMENTAL SETTING
The experiments compare frozen SLMs through a shared structured navigation interface, using zero-shot and one-shot prompting on KINSHIP and MQUAKE-ST. A separate MQUAKE-ST comparison adds a ToG-style search-and-generation scaffold.
3. EXPERIMENTAL SETTING
- All SLMs receive the question, topic and current entities, executed path, and the same indexed legal actions, then return a structured action ID or null and stop flag.Parameters remain frozen, reasoning modes are disabled, and each decision uses one generation without parse-retry or repair calls.Source: §3 · p. 2
- The one-shot condition provides one complete solved training trajectory as an in-context demonstration, while zero-shot removes it and leaves the interface unchanged.Decoding is deterministic, with temperature zero, seed 42, and a 64-token maximum response length.Source: §3 · p. 2
- KINSHIP and MQUAKE-ST provide fixed graphs, topic and valid answer entities, and annotated reasoning paths; MQUAKE-ST is evaluated in Single Answer and Multi Answer settings.Action-display caps are 100 for KINSHIP and 200 for MQUAKE-ST.Source: §3 · p. 2
- The evaluated models are Gemma 4 E4B, Granite 3.3 8B, Llama 3.1 8B, Ministral 3 8B, OLMo-3 7B, Phi-4 Mini 3.8B, Qwen2.5 7B, and Qwen3 8B.Structured-output compatibility is an inclusion requirement, not an ablation dimension.Source: §3 · pp. 2–3
- The MQUAKE-ST Single Answer ToG-style comparison adds relation and entity pruning, retention of w candidate paths, evidence-sufficiency checks, and free-form answer generation.It uses the original ToG prompt templates and reports terminal Hits@1, generated-answer accuracy, highest-ranked-path PED, and mean LLM calls per question for w = 1 and w = 3.Source: §3 · p. 3
4. RESULTS
One-shot local navigation results vary across models and settings: answer accuracy and path fidelity can favor different models, while demonstrations and explicit search have model- and scaffold-dependent effects.
Structural Calibration
- The shortest-path oracle is not a path-fidelity upper bound because its answer-informed shortest route may differ from the annotated reasoning path.Models with better edit distance and overlap than the oracle follow the annotated structure more closely than answer knowledge and shortest-path efficiency alone would achieve.Source: §4 · p. 3
One-Shot Navigation Performance
- On KINSHIP, Ministral 3 leads Hits@1 while Gemma 4 has the strongest path fidelity; Ministral 3 leads both measures on MQUAKE-ST.Several stronger models also exceed the shortest-path oracle on path-fidelity metrics, while weaker models move toward the structural calibration references.Source: §4 · p. 3
Effect of One-Shot Demonstration
- A single demonstration generally improves answer accuracy and path fidelity for Gemma 4, Ministral 3, and Qwen3, but degrades Granite 3.3 and often OLMo-3.Other responses are mixed: Llama 3.1 can improve answer accuracy without improving PED, and Calls/Q changes heterogeneously; interpret Calls/Q relative to reference path length because low values can reflect premature stopping.Source: §4 · pp. 3–4
Effect of Explicit Search
- With ToG-style search, width 1 lowers Hits@1 and raises PED for all three models despite more calls; width 3 further worsens both measures.Generated-answer accuracy exceeds terminal Hits@1 in every setting, while increasing width provides no consistent benefit in generated-answer accuracy.Source: §4 · p. 4
5. CONCLUSION
The conclusion reports substantial model variation in answer accuracy and path fidelity across KINSHIP and MQUAKE-ST, and calls for evaluating graph reasoning beyond endpoint accuracy.
5. CONCLUSION
- Across KINSHIP and MQUAKE-ST, similarly sized frozen SLMs differ substantially in terminal-answer accuracy and path fidelity.On KINSHIP the two criteria can rank models differently, while the strongest MQUAKE-ST model performs well on both.Source: §5 · p. 4
- A single trajectory demonstration can improve or degrade answer accuracy and path fidelity depending on the model.The complementary ToG-style evaluation finds that a multi-stage search-and-generation scaffold does not necessarily preserve strong isolated navigation, and generated answers can partially mask trajectory failures.Source: §5 · p. 4
- The findings motivate component-wise evaluation of relation and entity selection, search control, stopping, and answer synthesis, alongside future study of task-specific adaptation.Source: §5 · p. 4
Compliance with Ethical Standards
The authors report that the study involved no human or animal subjects and required no ethical approval.
Compliance with Ethical Standards
- No human or animal subjects were involved, and no ethical approval was required.Source: Compliance with Ethical Standards · p. 5