Automatic hallucination checkers usually break a model's answer into small claims, such as "Marie Curie — born in — Warsaw," and ask another language model whether a reference document supports each one. These checkers have a known weakness: the judging model often answers from its own memory instead of reading the reference. Knowledge-Centric Hallucination Detection reports this directly for its RefChecker pipeline. A checker that leans on memory approves claims the document never supports whenever they happen to be true in the world. It also rejects correct claims drawn from documents that are new, private, or counterfactual. In retrieval-augmented generation, where the whole point is to trust the supplied sources, that is exactly the wrong behavior.
We propose a checker whose inputs make memorization useless. The reference passage is turned into a small graph of entities and typed relations. For each claim with head $u$ and tail $v$, we cut out the neighborhood surrounding both entities. Every node in it is then replaced by its pair of shortest-path distances $(d(x,u), d(x,v))$, discarding its name. A small graph neural network (a model that updates each node's vector from its neighbors' vectors) reads only these distance labels and the relation types, and returns entailed, contradicted, or unsupported. This relabeling is "double-radius node labeling," introduced for link prediction in Link Prediction Based on Graph Neural Networks and made entity-independent for knowledge graphs in Inductive Relation Prediction by Subgraph Reasoning. The verifier never sees who "Warsaw" is, so it can only be right by reading the evidence's structure.
Core Claim
The claim has two parts, and they carry different risks. The first part is that a verifier restricted to distance-labeled evidence subgraphs is faithful to the context by construction. On contexts that contradict world knowledge, its accuracy should stay flat, while LLM judges and NLI (natural language inference: models that label a sentence as entailed, contradicted, or neutral given a premise) should degrade. The second part is that structure adds something beyond anonymization. Consider claims whose support runs through two or more hops, or through several partly conflicting sources in noisy retrieved context. On these, the graph model should beat an equally anonymized text judge, because it pools evidence across many paths instead of reading one verbalized chain.
The first part is close to guaranteed by design. The second is the real scientific bet, and the experiments are built so it can fail visibly.
This differs from the closest existing work in a concrete way. GraphEval turns outputs into triples and checks each one against the source with NLI. FactAlign aligns triple embeddings between a source graph and an output graph. RefChecker classifies claim-triplets with an LLM. All three treat the graph as an unordered bag of triples, and all three show the checker entity names. Hallucination Detection from Structural Reasoning Model does propagate scores over a graph, but the graph is the model's own reasoning steps, not the evidence. In the other direction, GraIL and KG-ICL are entity-agnostic subgraph reasoners that have only ever completed symbolic knowledge graphs, never checked language-model text.
Research Program
Every method compared here uses the same claim extractor, the RefChecker-style LLM triplet extractor. Both the reference context and the response pass through it, followed by coreference and entity merging. This pins the known brittleness of text-to-graph extraction, flagged by FactAlign and GraphEval, as a shared cost rather than a confound.
For each response claim $(u, r, v)$, we match $u$ and $v$ to nodes in the context graph. We extract the enclosing subgraph within $h$ hops, capped by degree-aware sampling to handle the hub blow-up that SEAL and GraIL both report. We then label each node $x$ with $(d(x,u), d(x,v))$. The claimed relation enters only as a query type.
The scorer is a relational message-passing network with edge attention in the style of GraIL. It is initialized from KG-ICL, whose distance-based entity tokens already transfer across 43 knowledge graphs. It is followed by a three-way head.
A claim link naively passes a plausibility test when the entities are merely near each other, and LLM hallucinations are, by nature, plausible. Plausibility is therefore the wrong training target. We instead train on hard negatives that mimic observed LLM errors. These include swapping the tail for a same-type entity from the same neighborhood, and reversing argument roles, the patient/donor confusion documented by Léo Milecki. They also include substituting a sibling relation, and deleting the supporting path while leaving nearby distractors, which yields a correct "unsupported" label. Role reversal is where distance labels should help most. Because $(d(x,u), d(x,v))$ is an ordered pair, reversing $u$ and $v$ changes every label.
Training graphs come from Wikidata neighborhoods and from graphs extracted from passages. No evaluation benchmark is used for training. A claim whose entities cannot be matched to the context graph is labeled unsupported outright; we report how often this rule fires.
Baselines
The naive reference point has two parts. One is the rule that a claim is supported if and only if the exact triple appears in the context graph. The other is the reachability rule sketched in the file's fourth gap: supported if $d(u,v) \le h$, extrinsic if $u$ and $v$ are disconnected. These rules show how much of the task is plain lookup. The reachability rule in particular should be fooled by plausible near-miss hallucinations, and that failure is the motivating case.
The strongest existing competitor is RefChecker from Knowledge-Centric Hallucination Detection. It uses the same unit (claim-triplets), the same three-way labels, and was evaluated on KnowHalBench, our main benchmark. The file reports gains for it of 18.2 to 27.2 points over SelfCheckGPT and FacTool on KnowHalBench, and a 10-point Macro-F1 gain of triplets over sentences. The file gives no absolute Macro-F1 for RefChecker, so we will rerun it with our shared extractor and report its numbers ourselves. It is run with the same checker LLM and the same retrieved contexts. Beating it means higher Macro-F1 on the Accurate and Noisy Context settings, together with a clearly smaller drop on counterfactual contexts.
We also run GraphEval-style triple-wise NLI, since it is the graph-flavored flat checker. FactAlign is included on WikiBio, where the file reports F1 0.889. SelfCheckGPT serves as the sampling reference, with AUC-PR 93.42 on WikiBio GPT-3 in SelfCheckGPT; it is given the same total token budget as the LLM judges.
Three ablations isolate the key ingredient. The first is the same network without distance labels, a plain relational GNN on the subgraph. The second is the same network with entity-name text embeddings added back to the nodes. This should raise accuracy on ordinary data and then collapse on counterfactual data, directly measuring the leakage we claim to remove. The third is KG-ICL applied zero-shot with no hallucination-specific training. All learned variants get the same training data and the same hyperparameter search budget.
Why not just…?
Why not just anonymize entity names and ask an LLM judge? Replace names in the context and claim with placeholders such as E1 and E2, then prompt a strong judge. This is the most serious threat. It removes memorization with no graph machinery, and it is a baseline in every experiment, including a variant that feeds the judge the verbalized shortest paths between $u$ and $v$. If it matches our verifier on multi-hop and noisy-context claims, the honest conclusion is that anonymization, not structure, does the work. The note would then report that, and cost would be the graph model's only remaining advantage.
Our prediction is that the graph wins where evidence is spread across many paths or sources. Sun and Yang found that judges reading long linear traces miss breaks in the middle, and that isolating structure raised MATH average precision to 76.59%, 13.8 points above the best non-graph baseline. We test whether the same holds for evidence.
Why not just run NLI on the claim against the passage? Sentence- and passage-level NLI is cheap. But GraphEval already found that decomposing into triples beats whole-text NLI by 6.2% balanced accuracy. NLI models also see entity names and bring their own world knowledge, so they share the contamination problem. They are included as baselines and in the counterfactual test.
Why not just sample several answers and check agreement? SelfCheckGPT needs no reference at all, but that is a different question: it asks whether the model is consistent, not whether the source supports the claim. It also fails on errors that are consistently wrong. Sun and Yang report sampling methods at about 25% average precision on HumanEval, and TruthfulQA shows models repeating popular misconceptions reliably. It stays as a reference point rather than a direct competitor.
Why not just score triples with a standard knowledge-graph embedding? Methods like TransE or RotatE learn one vector per entity, so they cannot score entities first seen in a new context, which GraIL established. They also score plausibility, which is the very quality hallucinations have.
Proposed Experiments
The main evaluation uses KnowHalBench's Accurate Context and Noisy Context settings, with 11,000 annotated claim-triplets, scored by three-way Macro-F1. It also uses WikiBio GPT-3, with Wikipedia passages as context, scored by sentence-level AUC-PR against SelfCheckGPT and FactAlign. The third benchmark is KGHaluBench's depth-of-knowledge items. Here the reference is Wikidata, and the target is fine-detail errors, which the benchmark shows fall only about 24% from 8B models to frontier scale. For these we report agreement with the benchmark labels alongside its verifier's reported human agreement of up to 87.74%.
The decisive check is counterfactual. We rebuild KnowHalBench and KGHaluBench items by consistently permuting same-type entities throughout context and claim. This makes the documents false in the real world while leaving the support relations unchanged, so the gold labels stay the same. By construction, the entity-agnostic verifier's predictions should barely move. RefChecker, NLI, and the name-embedding ablation should lose accuracy in proportion to how much they rely on memory. If the verifier also degrades, extraction or training has leaked identity, and we will trace where.
The second check stratifies claims by the hop distance of their gold support path and by the number of conflicting sources. The structural claim survives only if the verifier's margin over the anonymized path-verbalizing judge grows with hops and conflict count.
A third, smaller study reruns everything with gold triples on a hand-annotated subset. This separates checker errors from extractor errors.
Finally, we report wall-clock time and cost per claim. This matters because the verifier is a small GNN that makes one pass per claim, while the baselines need one or more LLM calls.
References
- Knowledge-Centric Hallucination Detection
- Link Prediction Based on Graph Neural Networks
- Inductive Relation Prediction by Subgraph Reasoning
- GraphEval: A Knowledge-Graph Based LLM Hallucination Evaluation Framework
- FactAlign: Fact-Level Hallucination Detection and Classification Through Knowledge Graph Alignment
- Hallucination Detection from Structural Reasoning Model
- A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning
- MEDIMP: 3D Medical Images and clinical Prompts for renal transplant representation learning
- SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models