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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

When to Trust a Knowledge-Graph Walk: An Empirical Study of Per-Hop Decision Confidence

Manvir Chakal
Zenodo (CERN European Organization for Nuclear Research)
Topic Modeling
preprint

When to Trust a Knowledge-Graph Walk: An Empirical Study of Per-Hop Decision Confidence

Manvir Chakal
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Topic Modeling
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
When to Trust a Knowledge-Graph Walk: An Empirical Study of Per-Hop Decision Confidence — Manvir Chakal · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS