When to Trust a Knowledge-Graph Walk: An Empirical Study of Per-Hop Decision Confidence
LLM-based question answering over knowledge graphs is accurate but expensive, and it rarely says when an answer is likely wrong. We study an old design, in which each hop of a walk is a classification over the current node's relations plus STOP, with a zero-shot, swappable decider, and ask what the walk's path confidence is worth on MetaQA, WebQSP, CWQ and a 2WikiMultiHopQA evidence graph. Where walks fail often enough to matter (MetaQA 3-hop, WebQSP), path confidence ranks right above wrong answers well (AUROC 0.82-0.97): the most confident half of MetaQA 3-hop answers is 99% accurate (81% overall). With the model and prompt fixed, reading token probabilities beats stated confidence by 0.09-0.23 AUROC and matches or beats 5-sample voting at a fifth of its cost. Raw confidence is overconfident, but a two-parameter Platt fit repairs much of that. The walk is less accurate than an LLM writing the relation path in one call, cheaper only on Freebase, and its confidence fails on CWQ. On 2Wiki, walks that never reached a decision were scored as certain; scoring them lowest lifts AUROC from 0.67 to 0.92, and to 0.85 on a held-out sample. As a strong agent's tool, the walk cuts cost by 17% at equal accuracy. The library, every run and the table scripts are released at https://github.com/manvirchakal/graphwalk.
Authors
- Manvir Chakal
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-22
- DOI
- https://doi.org/10.5281/zenodo.24430507
- Primary Topic
- Topic Modeling
- Type
- preprint