Detecting when a language model states something false usually requires labeled examples of false statements, and the standard shortcut is to ask a second model to rewrite a correct answer into a wrong one. That shortcut has two flaws. The rewriter picks errors with no notion of which ones are hard, so it tends to produce easy ones. And the rewriter can slip in its own unplanned mistakes, so labels are noisy. We propose planning the error in the knowledge itself before any text is written. Take the typed knowledge graph that grounds a dialogue, which has distinct kinds of entities (movies, people, genres) and distinct kinds of links (directed, starred in, sequel of). Corrupt one fact by following a specific chain of link types to a plausible near-miss, such as a different movie by the same director. Then have the target model itself verbalize the corrupted fact. Because the corruption was chosen in the graph, the false span is known exactly. Because it was chosen along a short typed path, it is the kind of near-miss real models produce.
The claim is that how far the substituted entity sits from the true one in the typed graph controls how hard a hallucination is to detect. A detector trained on graph-planned errors spread across that distance range should beat a detector trained on free-form LLM rewrites, with the gain concentrated on near-miss errors. Heterogeneous graph structure plays the role of a sampler and a hardness ruler for data augmentation, not a new detector architecture. Hallucination detection on knowledge-grounded dialogue is the test bed.
What exists and what is missing
The closest work is Enhancing Hallucination Detection through Perturbation-Based Synthetic Data Generation in System Responses. It has a rewriting model turn target-model responses into faithful and hallucinated variants, then trains a T5-base detector that reaches 0.762 F1 on OpenDialKG-Eval. That work supplies our main baseline and much of our pipeline, and it also motivates us. It shows that synthetic errors must match the target model's style, yet it treats the Freebase knowledge behind OpenDialKG as flat strings and never asks which wrong entity is chosen. Two other augmentation pipelines also corrupt surface text. From Detection to Diagnosis swaps entities and drops context in Wikipedia passages and has to verify outputs with a GPT-4 and Lynx ensemble. PALE prompts a model to produce a truthful answer and a plausible hallucination for single-turn QA. Neither has relational structure. Both need filtering because the generator may introduce its own errors, which is exactly the inherited-fabrication problem our design removes by construction.
From the graph side, meta-paths are fixed sequences of node and edge types, such as Movie–directed by–Person–directed–Movie. Collective Classification of Spam Campaigners on Twitter and ORANGE show that meta-paths separate semantically related neighbors from unrelated ones. We reuse that idea to define the hardness of a near-miss. HG-MDA is the main precedent for augmenting heterogeneous graphs, and it constrains our design. Its edits are triangle-closure heuristics that fail on graphs without triangles, and it cannot produce new text. We therefore edit facts along typed paths rather than closing triangles. MultiKE-GAT builds a heterogeneous graph for fact verification but uses the LLM only as a keyword extractor and never synthesizes training errors. The motivating observations on what real errors look like come from the survey Siren's Song in the AI Ocean and from the entity and role swapping reported by Milecki. Both suggest that real hallucinations are often substitutions of a related entity, not random ones.
Core Claim
Let $e$ be the true entity in a grounding fact. Let $e'$ be a type-matched substitute reached from $e$ by a meta-path of length $d$, with $d=\infty$ when no typed path connects them within a fixed radius. We claim three things. First, real target-model hallucinations on OpenDialKG are concentrated at small $d$. Second, detectors trained on LLM rewrites lose accuracy as $d$ shrinks. Third, training on graph-planned errors sampled to match the real distribution of $d$ removes most of that loss while keeping exact span labels.
Research Program
The generator works on the Freebase subgraph attached to each OpenDialKG dialogue, about 1.2M triples in total per OpenDialKG. For a grounding path behind a gold response, it applies one of four typed edits.
The first edit, near-miss entity substitution, replaces an entity with a same-type entity reached by a chosen meta-path; the sibling movie of the same director is one example. The second, relation substitution, keeps the entities but swaps the edge type, for example "directed" becomes "starred in", which produces role swaps. The third, hop collapse, asserts a two-hop relationship as a direct one. The fourth, unconnected fabrication, adds an edge between entities with no path between them, and serves as the easy, far end of the range.
The target LLM, the same model whose outputs will be judged, then writes a response from either the original or the edited path, using the same dialogue history. Generating both versions with the target model addresses the style-mismatch finding of the perturbation-rewriting paper.
Labels are checked mechanically rather than by a second LLM. A faithful example is kept only if every entity it mentions links into the original subgraph. A hallucinated example is kept only if it mentions $e'$ (or the swapped relation) and not $e$, and an entailment model confirms that the edited triple is asserted. The false span is then known, so we train span-level detection as well as response-level detection.
The hardness analysis needs the distance $d$ for real errors. We will hand-annotate the hallucinated span in each hallucinated response of OpenDialKG-Eval's 402 GPT-4 responses, link that span to Freebase, and compute $d$ to the entity the gold knowledge supports. That empirical distribution sets the sampling mix for the generator. If the measured distribution shows real errors are not near-misses, the central premise fails. We regard this as the first and cheapest test.
The main detector is the same T5-base used by the closest work, so that any gain is attributable to the data. We also test a secondary, graph-aware detector. It encodes the dialogue's subgraph as typed relation sentences, in the spirit of the RelationPrompts of ELLA, and concatenates them with the response. We report it only as an addition, and drop the claim if it does not beat T5 on the same data.
Baselines
The naive reference points are a zero-shot GPT-4 judge and a detector trained on HaluEval's dialogue split. On OpenDialKG-Eval these score 0.608 and 0.702 F1 respectively, as reported in Enhancing Hallucination Detection. For context, ChatGPT reaches 72.40% accuracy on HaluEval dialogue in HaluEval. These show what a detector achieves without targeted synthetic data.
The strongest existing method is the perturbation-rewriting pipeline with a T5-base detector, at 0.762 F1 on OpenDialKG-Eval. It is the strongest competitor because it already uses the target model's responses and already beats GPT-4 on this exact benchmark. We will reimplement it with the same target LLM, the same number of synthetic training examples, the same T5-base checkpoint, and the same hyperparameter search budget, and report its reproduced score alongside the published one. Beating it means higher response-level F1, with a bootstrap interval over the 402 examples that excludes the baseline. It also means a clear gain on the near-miss stratum (small $d$) without a loss on the far stratum.
Two ablations isolate the key ingredient. The first, random type-matched substitution, swaps in a same-type entity sampled uniformly from the graph, ignoring paths. It tests whether the typed path matters or only type-consistency does. The second, untyped-neighbor substitution, samples a neighbor at the same hop count while ignoring edge types, as a homogeneous graph would. It tests whether heterogeneity specifically matters. A third control trains on our data but with hardness sampled uniformly instead of matched to the measured real distribution.
PALE represents a different family, scoring internal activations with a Mahalanobis distance, and reports 73.20% AUROC on TruthfulQA. We found no reported result on Lacuna for PALE on OpenDialKG-Eval. We will run it with an open target model, feeding it both its own prompt-generated pairs and our graph-planned pairs. This tells us whether graph-planned data also helps activation-based detection.
Why not just…?
Why not just use the LLM rewriter with a stronger prompt asking for subtle errors? This is the real threat. A capable rewriter told to "swap in a closely related entity" might find near-misses from its own knowledge. Two things argue against it. The rewriter's notion of "related" is unverified and can itself be fabricated, which is why From Detection to Diagnosis needs an ensemble verifier. The rewriter also gives no control over the distance distribution. We will include a "subtle-error" prompted rewriter as an extra baseline, measure the $d$ of its substitutions after entity linking, and audit 200 of its examples and 200 of ours for label errors. If it matches our near-miss stratum performance at equal label noise, the graph is unnecessary and we will say so.
Why not just swap entities of the same type at random? That is cheap and needs no meta-paths. It is the first ablation above. Enhancing Hallucination Detection already found that rule-oriented synthetic data (0.702 F1) trails LLM-shaped data (0.762). Our prediction is that random swaps land mostly at large $d$ and do not help on near-misses. The stratified results test this directly.
Why not skip training and let the LLM check its answer against the serialized subgraph? Graph-in-prompt self-checking fails on multi-hop structure. ProGraph reports 36.3% accuracy for GPT-4o reasoning over graphs, and HaluEval finds that comparing correct and hallucinated candidates side by side hurts LLM judges. We will still run GPT-4 with the serialized subgraph in context as a judge, since this is the obvious deployment alternative.
Why not apply heterogeneous-graph augmentation such as HG-MDA directly? HG-MDA edits topology to improve node classification. It produces neither text nor labeled false statements, and its triangle edits do not apply on sparse graphs. It answers a different question, so we use its lesson that augmentation should respect typed relations, not its operators.
Proposed Experiments
Training data comes only from OpenDialKG training dialogues. The primary evaluation is OpenDialKG-Eval, with response-level F1, span-level F1 on our annotated spans, and F1 stratified by meta-path distance. The decisive check is the interaction: our data should help most where $d$ is small, and the uniform-random ablation should not. A flat gain across strata would suggest a generic data-quantity effect rather than the hardness mechanism.
Transfer is tested on the HaluEval dialogue split, which is built on OpenDialKG, and on BEGIN, where we found no reported result on Lacuna. A harder transfer goes to the HaluEval QA split built on HotpotQA, using Wikipedia hyperlinks between entities as a weaker typed graph. This tests whether planning errors on one graph helps detection in another domain.
We will also report synthesis cost per example against the $0.008 reported for rewriting, and the label error rate from the human audit. Mechanically verified labels with lower noise at equal or lower cost would be a useful result even if the F1 gains are modest.
References
- Enhancing Hallucination Detection through Perturbation-Based Synthetic Data Generation in System Responses
- From Detection to Diagnosis: Advancing Hallucination Analysis with Automated Data Synthesis
- Bolster Hallucination Detection via Prompt-Guided Data Augmentation
- Collective Classification of Spam Campaigners on Twitter: A Hierarchical Meta-Path Based Approach
- ORANGE: Text-video Retrieval via Watch-time-aware Heterogeneous Graph Contrastive Learning
- Semi-Supervised Heterogeneous Graph Learning with Multi-Level Data Augmentation
- Multi-source Knowledge Enhanced Graph Attention Networks for Multimodal Fact Verification
- Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models
- MEDIMP: 3D Medical Images and clinical Prompts for renal transplant representation learning
- OpenDialKG: Explainable Conversational Reasoning with Attention-based Walks over Knowledge Graphs
- Towards Efficient LLM-aware Heterogeneous Graph Learning
- HaluEval: A Large-Scale Hallucination Evaluation Benchmark for Large Language Models
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models
- HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering