Catching Relational Hallucinations with a One-Pass Sparse Graph Denoiser

Large language models often produce claims in which every entity is real but the relation between them is invented: the right drug paired with the wrong trial, a donor's attribute assigned to the recipient, a real author credited with a paper by someone else. The detectors that best catch these errors turn a response into a small knowledge graph of (head, relation, tail) triples and cross-check it. They are also slow, because they sample several alternative answers from the model and then run several more verification prompts for every claim. We propose replacing that sampling loop with a learned graph denoiser. A denoiser here means a model trained to take a corrupted graph and predict which edges belong to the clean version. We train it offline on real knowledge-graph neighborhoods that have been deliberately corrupted, using the same kinds of corruption that language models produce. At test time we extract one graph from one response and run a single forward pass, or at most a few. The denoiser's estimated probability that each edge "survives denoising" becomes that edge's hallucination score. Its proposed replacement edges become candidate corrections.

The three research directions play different roles. Hallucination is the application. Few-step generation, drawn from recent flow-matching work on graphs, is the mechanism that removes the latency of multi-sample verification. Sub-quadratic sparse graph generation is the constraint that keeps this feasible. A response graph with $N$ entities and a vocabulary of relation types has on the order of $N^2$ possible relations, so the denoiser must never evaluate them all. In two sentences: train a sparse discrete flow model on corrupted knowledge-graph neighborhoods, then read off, in one pass, how strongly it wants to delete each triple an LLM asserted. The test is whether this matches multi-sample graph verification at a small fraction of the cost, and whether the generative training actually beats a plain classifier trained on the same corruptions.

Core Claim

The closest existing work is GCA (Zero-resource Hallucination Detection via Graph-based Contextual Knowledge Triples Modeling). GCA extracts triples from several sampled responses, smooths them with a relational graph convolutional network, and verifies each triple through three reverse-question prompts. It motivates this proposal in two ways. It shows that graph structure matters for detection: it reaches 92.7 F1 on TripleCom, a dataset of fabricated relations between real entities, against 75.7 for the Focus baseline. It also shows that doing this with repeated LLM calls is expensive. Our claim is that most of GCA's signal can be moved into a model trained once. The model is a sparse discrete flow network whose denoising posterior serves as a per-edge plausibility score, and it can also propose the edge that should replace a rejected one. GCA only detects errors. It does not correct them, and it pays its cost again for every query. We pay the cost once, at training time.

The mechanism comes from two graph-generation papers. DeFoG trains discrete flow matching on graphs by interpolating between clean graphs and a noise prior, and it predicts clean-graph edge probabilities directly. Its sampling schedule is decoupled from training, which lets it reach 99.5% validity on Planar graphs in 50 steps. DeFoG still works over the full $N \times N$ adjacency matrix, however, and its authors name large graphs as unsolved. SparseDiff and EDGE supply the sparsity. SparseDiff trains discrete diffusion on edge lists plus a subsampled set of candidate "query edges." EDGE restricts each step to a small active set of nodes and generates the 2,485-node Cora graph in about 1.7 seconds, where dense baselines run out of memory. We combine DeFoG's clean-marginal prediction with SparseDiff-style query edges. We use them for a different purpose: we do not sample new graphs, we score an observed one. None of these papers touches language or factuality.

The score for an asserted edge $e$ in the extracted response graph $\hat G$ is

$$s(e) = 1 - p_\theta\big(e \in G_0 \,\big|\, G_t = \hat G,\ c\big),$$

where $G_0$ is the clean graph, $G_t$ is the graph at corruption level $t$, $p_\theta$ is the denoiser's predicted clean-edge probability, and $c$ is optional conditioning (entity text embeddings and, in one setting, a retrieved knowledge-graph neighborhood). The corruption level $t$ is treated as a prior over how much of a response is hallucinated. We either pick it on validation data or average over a few values. This is the part a single-noise-level classifier cannot express.

Research Program

We build the corruption process first, because the whole method depends on it. Clean training graphs are local neighborhoods from the DBpedia subgraphs used by OKGQA and from the Freebase subgraphs of WebQSP used by G-Retriever. Nodes and edges carry SentenceBERT embeddings of their text, as in G-Retriever. The corruption operators mirror the error types catalogued in Siren's Song and the relation-swap and edge-deletion corruptions of OKGQA-P: swapping relation labels, swapping heads with tails (role swaps), rewiring a tail to a type-compatible wrong entity, inserting fabricated edges between real entities, and deleting true edges. The corruption rate is the flow time $t$. Following DeFoG, the forward process interpolates each edge's categorical state toward a corruption prior. Unlike DeFoG, that prior is concentrated on these operators rather than spread uniformly over relation types.

The denoiser is a relational message-passing network over the observed sparse edge list. It predicts clean-edge probabilities for the observed edges and for a budget of query edges. Query edges are proposed from entity-type compatibility and, when retrieval is on, from the retrieved neighborhood. Cost therefore scales with observed plus query edges, not with $N^2$. EDGE notes that message-passing networks of this kind are limited in which substructures they can distinguish. We accept that limit and test whether it matters on TripleCom-style errors. For latency, we evaluate one-step prediction of the clean graph, which is DeFoG's clean-marginal output used directly, and short few-step refinements using DeFoG's time distortion. We do not attempt a discrete version of MeanFlow. MeanFlow achieves one-step image generation (1-step FID of 3.43 on ImageNet 256×256) by learning average velocities, but only in continuous spaces. For scoring, as opposed to sampling, one-step clean-marginal prediction may already be sufficient, and the experiments test whether it is.

We run two deployment settings and keep their claims separate. In the zero-resource setting, the denoiser sees only the response graph, matching GCA's assumptions. It can catch only errors that are structurally or type-implausible, or inconsistent with the rest of the response. It cannot catch a plausible but false fact, and we will measure exactly where that ceiling falls. In the retrieval setting, the response graph is merged with a retrieved neighborhood, and the denoiser reconciles the two. Following OKGQA-P's finding that noisy graphs still help, we also test robustness to corrupted retrieval. Triple extraction remains a single LLM call in both settings. We report its cost honestly instead of hiding it.

Baselines

The naive reference points are flagging nothing and flagging everything, which give the F1 floor on each benchmark. A second naive reference is the extracting LLM's own verbalized confidence for each triple, which costs no extra calls.

The strongest existing method is GCA, which reports 55.4 F1 on PHD, 3.1 points above its best baseline, and 92.7 F1 on TripleCom. We rerun it with the same generator model, the same extraction prompt, and its published number of samples. We report both F1 and end-to-end wall-clock time and LLM tokens per response on identical hardware. Beating GCA means either matching its F1 within about one point at a small fraction of its LLM calls, or exceeding its F1 at comparable cost. Only the second would count as a detection advance and not just an efficiency gain. SelfCheckGPT, which GCA outperforms, is also rerun as the canonical multi-sample consistency method. No reported result was found on Lacuna for its absolute score on these benchmarks.

For the retrieval setting, the strongest competitor is an LLM judge that receives the extracted triples together with the retrieved neighborhood, chosen by prize-collecting Steiner tree subgraph selection in the style of G-Retriever and OKGQA. OKGQA reports that adding knowledge-graph triplets raises GPT-4o's FActScore from 55.35% to 72.55%. The judge receives the same retrieved subgraph as our denoiser, and its prompt tuning budget equals our hyperparameter budget.

The ablation that isolates our key ingredient is a discriminative edge classifier. It has the same architecture, the same corruption data, and the same parameter count and training compute, but it is trained at one fixed corruption rate with a binary real-or-corrupted label. A second ablation removes joint message passing and scores each triple independently, like a link predictor. If the classifier matches the flow model, the generative framing adds nothing and we drop it.

A final fast baseline is a linear probe on the generator's hidden states at each triple's tokens. This follows the observation, in TruthFlow, that truth-related directions exist in activation space but vary across domains. The probe gets the same labeled data.

Why not just…?

Why not just train a classifier on corrupted triples? This is the most serious threat. A one-step denoiser at a single noise level essentially is such a classifier. The generative version has three candidate advantages: training across all corruption rates, calibrating the corruption level to the response at test time, and proposing a repair edge rather than only a flag. Each is testable. The matched-classifier ablation settles the first two. The repair experiment below settles the third. If the classifier wins or ties on detection, the contribution shrinks to the repair capability, and we would say so.

Why not just give an LLM the retrieved subgraph and ask it to verify? It is simple, and OKGQA's results show retrieval-grounded LLMs are strong. It is also one long LLM call per response, which grows with retrieved graph size, and its behavior under corrupted retrieval is not a learned reconciliation. We run it head to head with a matched retrieval budget and on OKGQA-P-style corrupted neighborhoods. If it matches us at similar latency, the retrieval-setting claim fails, and the zero-resource setting has to carry the proposal.

Why not just steer or probe hidden states, as TruthFlow does? TruthFlow raises Llama-3-8B's TruthfulQA "True" score from 52.32% to 64.79% with negligible latency, so hidden-state methods are fast and effective on short factual questions. They operate on isolated token positions, however, and the entity-role swaps that GCA's TripleCom isolates are errors in the relation between two correct entities. The hidden-state probe baseline on TripleCom answers directly whether those representations already encode such errors. If the probe matches us there, the graph is unnecessary.

Why not just paste the whole knowledge neighborhood into a long context? MINDGRAPH finds direct prompting at 64% against 77% for structured concept-graph memory on LONGREASON-200. G-Retriever reports a 99% reduction in graph-description tokens from subgraph retrieval on WebQSP. Both results argue that serializing a large context is both costlier and less reliable. We therefore do not rerun this alternative beyond a single long-context judge variant.

Proposed Experiments

Detection is measured on PHD, WikiBio, and TripleCom, following GCA's protocol. We report F1 at the response and triple level, AUROC, wall-clock time per response, and LLM calls per response. The decisive comparison is a latency–F1 curve: our model at one, two, and five denoising steps against GCA and SelfCheckGPT at varying sample counts. The proposal succeeds if our one-step point lies at or above GCA's curve at lower cost on TripleCom. TripleCom is the benchmark where relational structure should matter most. We expect a smaller or no advantage on PHD, whose errors are more often plausible-but-false facts, and a gap there would confirm the zero-resource ceiling described above.

The generative-versus-discriminative check runs the matched classifier and the independent-edge ablation on all three benchmarks. We also inject synthetic hallucinations at controlled rates from 5% to 50%. If calibrating $t$ matters, the flow model's advantage over the fixed-rate classifier should grow as the test hallucination rate moves away from the classifier's training rate.

The correction check applies the denoiser's proposed repairs in the retrieval setting on OKGQA. An LLM rewrites each answer with rejected triples replaced by the top proposed edges, and we measure FActScore against the KG-triplet-augmented GPT-4o reference of 72.55%. We repeat this on OKGQA-P corruptions to test whether learned reconciliation degrades more gracefully than prompting.

The scaling check confirms that sparsity is real. We score response-plus-neighborhood graphs of increasing size, up to several thousand entities, and report memory and time for our sparse denoiser against a dense DeFoG-style variant. We expect the dense variant to exhaust memory at sizes where EDGE reports dense diffusion baselines failing.