Path-Supported Reranking: Checking Multi-Hop Claims in LLM Candidates with Typed Matrix Products

When a language model answers a question from documents, many of its sentences state a relation that no single sentence in the source says outright. "The director of the film was born in Ohio" is true only because one passage names the director and another gives that person's birthplace. Today's hallucination checkers break a response into atomic (subject, relation, object) facts, called triplets, and test each one against the source on its own. A compressed claim like this one has no matching source triplet. The checker must then call it unsupported, which is a false alarm, or hand the whole context to a language model judge, which may answer from its own memory instead of the documents. We propose to turn the source into a small graph with one adjacency matrix per relation type. A response triplet $(i, r, j)$ is then "path-supported" when a short chain of source relations connects $i$ to $j$, and the number of such chains can be read off products of those matrices. The same products let us rank a pool of sampled answers cheaply. They are computed once per source, after which every claim in every candidate is scored by table lookup.

The opportunity is that two literatures each have half the tool. Overgenerate-and-rank methods sample many answers and pick one, but their rankers check entities or single facts, and they are known to trade one hallucination type for another. The linear-algebra work on counting paths and cycles has exact, fast formulas, but it has never been aimed at text. The test we care about is narrow and falsifiable. On questions that need a bridge entity, path support should catch hallucinated answers and pick correct ones better than a one-hop checker that uses the same extractor. On single-hop questions it should give no gain.

Core Claim

Single-fact verification has a blind spot that is structural, not a matter of model capacity. Knowledge-Centric Hallucination Detection (RefChecker) checks each claim-triplet with a three-way entailment classifier. FactAlign aligns response triplets to source triplets one by one. HalluGraph scores the fraction of response edges found in the source graph. GraphEval runs entailment on each extracted triple. These papers motivate our proposal: they show that structuring the source beats surface similarity, for example HalluGraph's 0.94 AUC against BERTScore's 0.60 on contract QA. All four stop at one hop.

We need to be honest about where higher-order structure helps and where it does not. If every edge of a candidate's graph exists in the source, then every path in the candidate also exists in the source. Checking multi-hop paths inside the candidate therefore adds nothing over checking its edges. Higher-order structure matters in one specific case: the response asserts a single edge that the source supports only as a composition of edges. Multi-hop QA is built on exactly this case. HotpotQA reports that 42% of its questions use a bridge strategy. LLM explanations routinely collapse such bridges into one sentence.

Our claim is that typed path counts in the source graph decide these compressed claims, and they do so in two ways. A claim with supporting chains of the right relation types is grounded. A claim whose endpoints are linked only through chains of the wrong types is the role or relation swap that Improving Faithfulness in Abstractive Summarization with Contrast Candidate Generation and Selection produced at scale. Its entity-swapping ranker cut extrinsic hallucinations on XSum from 71.7% to 9.2%, but intrinsic hallucinations rose from 1.7% to 29.1%.

Concretely, let $A_r$ be the source adjacency matrix for canonical relation type $r$. Let $\Pi(r)$ be a learned set of relation chains $\pi = (r_1, \dots, r_k)$ with $k \le 3$ that can express $r$, and let $w_\pi$ be a learned weight for chain $\pi$. The support score of a response triplet is

$$s(i, r, j) = \sum_{\pi \in \Pi(r)} w_\pi \, \big[\tilde{M}_\pi\big]_{ij}, \qquad M_\pi = A_{r_1} A_{r_2} \cdots A_{r_k},$$

where $\tilde{M}_\pi$ is $M_\pi$ after removing walks that revisit a vertex. A plain matrix product counts walks, which may revisit vertices. The correction terms are the Hadamard and diagonal products studied by Motif-Role-Fingerprints and searched for automatically by Grammar Reinforcement Learning. A candidate's overall score combines its claims' support. The minimum is used for detection, and a length-normalized mean is used for ranking.

Research Program

The pipeline has four parts. First, a fixed extractor turns the source passages and each candidate into triplets. We use spaCy entities plus Llama 3.1 8B relation extraction, the setup HalluGraph found workable. Free-text relation phrases are clustered into a few hundred canonical types by embedding similarity.

Second, we learn $\Pi(r)$ and $w_\pi$ from training data, in the spirit of rule mining. We count which source chains connect the endpoints of gold-supported claims of type $r$, and which connect the endpoints of known hallucinations. A small logistic model then sets the weights. As a secondary study, we replace this counting with the grammar-guided search of Grammar Reinforcement Learning. That paper discovered cheaper matrix expressions for counting untyped paths and cycles. We extend its grammar to typed matrices and score expressions by how well they separate supported from hallucinated claims, not by how cheaply they count. This is the first application of that search outside pure graph analysis, and it tests whether learned matrix expressions beat hand-enumerated chains.

Third, the scorer is used for selection. The model samples $N$ answers, and we pick the one with the highest support. For the summarization setting we also use it for generation. Following Chen et al., we swap each unsupported entity for same-type source entities, but we keep only swaps that make the resulting claims path-supported.

Fourth, efficiency. Per-query source graphs in HotpotQA and summarization hold only tens of entities. Dense typed products are therefore cheap, and the fill-in problem that hurts large-graph matrix powers does not arise. The cost is computing $\tilde{M}_\pi$ for the chains in $\Pi$ once per source, after which each claim in each candidate costs one lookup. Running entailment once per triplet instead costs one transformer pass per claim per candidate. For OpenDialKG, the source is a larger knowledge-graph neighborhood. There we materialize only the rows for entities mentioned in the dialogue.

Baselines

The naive reference points are greedy single-sample decoding and ranking candidates by the generator's own sequence likelihood. Energy-Based Reranking argues the second is a weak proxy for sequence quality. Any gain must first clear both.

The strongest direct competitor is a one-hop triplet checker in the style of RefChecker, used as the ranker. Each candidate triplet is classified as entailed, contradicted, or neutral against the source. Candidates are ranked by the fraction entailed. RefChecker reports a 10-point Macro-F1 gain over sentence-level checking and an 18.2 to 27.2 point margin over SelfCheckGPT and FacTool on KnowHalBench. The file gives no absolute value on our target sets. We run it with the same extractor, the same candidate pool, and the same DeBERTa-class entailment model we use elsewhere, and we tune it on the same development split.

A second strong competitor is HalluGraph's composite of entity grounding and relation preservation, reimplemented on the same graphs. It is the closest graph-based method and the most auditable one. As a detector it reached 0.94 AUC on contract QA and 0.84 on case-law QA in its own paper.

A third is a language model judge that reads the full source and the candidate. We use the strongest open model we can run, with a prompt and few-shot budget matched to our tuning budget. HaluEval's reported reference point is 62.59% accuracy for ChatGPT on its QA split, as reported by HaluEval.

We also report SelfCheckGPT with its prompt variant on the same samples. It uses no source and reached 93.42 AUC-PR on WikiBio. It measures a different signal, but a cheap ranker should be compared with it.

Three ablations isolate what is new. Setting $k=1$ turns our system into a one-hop checker with identical extraction and canonicalization. This is the key test: any gain we claim must survive it. Using raw walks instead of the corrected $\tilde{M}_\pi$ measures whether removing vertex-revisiting walks matters. Using untyped adjacency measures whether relation typing matters.

A fourth control gives the entailment model the top-scoring source chain as text and asks it to judge the claim. If that control matches our scorer, the matrix algebra is only a fast way to retrieve paths, not a better judge. We would report that plainly.

Beating the field means three things. On bridge questions, path support must beat the $k=1$ ablation and the RefChecker-style ranker, by a margin outside bootstrap confidence intervals, on hallucination-detection AUC and on answer F1 after reranking. It must also be no worse on single-hop questions. Finally, it must score a pool of $N=16$ candidates in substantially less wall-clock time than per-triplet entailment.

Why not just…?

Why not just let a strong language model judge read the source and reason across hops? It may work, and this is the most serious threat. The evidence against relying on it is moderate. ChatGPT detected hallucinations at only 62.59% on HaluEval's QA split. HaluEval also found that showing a model a correct and a hallucinated answer side by side made detection worse, which is exactly the setting of reranking. RefChecker found that model-based checkers often answer from internal memory instead of the given context. Our experiment settles this directly. We hold out bridge questions whose answers we perturb with counterfactual, internally consistent source passages, so that memory gives the wrong verdict. If the judge matches path support there, at its higher cost, the case for our method rests on cost and auditability alone.

Why not just check each triplet with entailment, as RefChecker and FactAlign do? A one-hop checker cannot represent a claim whose support is a composition. It either flags valid bridge claims or, when given loose context, passes fabricated shortcuts. The $k=1$ ablation runs this exact alternative with our extractor. Our prediction is that it ties us on single-hop and comparison questions and loses on bridge questions. If it ties everywhere, the core claim is false.

Why not just retrieve paths with breadth-first search, or learn structure with a message-passing graph network like SURGE? Breadth-first search finds the same simple paths and gives identical accuracy. Matrix products win only on batch throughput, since all candidates share one precomputation, and we will report the timing gap rather than claim an accuracy gain. Graph networks are a different trade-off. Standard message passing has known difficulty counting cycles and other substructures, and its learned embeddings produce no auditable count. SURGE also generates in a single pass, so it does not address selection. We include a CompGCN scorer trained on the same labels as a learned-structure control.

Why not just measure consistency across samples, as SelfCheckGPT does, perhaps on graphs extracted from each sample? Agreement across samples detects uncertainty, not grounding. A model can be consistently wrong about a bridge. A graph version adds little over simple edge agreement unless motif statistics carry extra signal, and we doubt they do. We therefore keep cross-sample consistency only as a reported baseline, not as a component of the method.

Proposed Experiments

The primary testbed is HotpotQA in its distractor setting, where each question comes with gold and distractor paragraphs that form the source graph. The paper's own baseline reached 58.28 answer F1, against 91.40 for humans. That baseline is a pre-LLM reader. We found no reported result on Lacuna for LLM overgenerate-and-rank on HotpotQA, so we will establish one. An open instruction-tuned model samples 16 answers with short justifications per question. We report answer exact match and F1 after reranking, and the rate of unsupported claims in the selected answer, judged by humans on a 300-question sample. Every result is split by HotpotQA's question type. The pre-registered decisive check is a positive gap over the $k=1$ ablation on bridge questions and no gap on comparison questions.

For detection, we use HaluEval's QA split, which is drawn from HotpotQA and pairs knowledge passages with correct and hallucinated answers. We report accuracy and AUC against the 62.59% ChatGPT reference and against all baselines, under the same bridge versus non-bridge split. KnowHalBench supplies triplet-level labels in its noisy-context setting, which tests whether path support stays robust when distractor passages create spurious chains. It reports no absolute baseline value usable here; we rerun RefChecker on it.

The second testbed reproduces Chen et al.'s contrast-candidate pipeline on XSum and replaces only its ranker. The target is to keep extrinsic hallucinations near their 9.2% while pulling intrinsic hallucinations well below their 29.1%. We measure this with FactAlign's intrinsic/extrinsic classifier, which reported 0.825 F1 on XSum, and with a human check of 200 summaries. GraphEval warns that short outputs give sparse graphs, so a null result here is plausible. A null result would bound the method to settings with real multi-hop structure.

OpenDialKG serves as a third, knowledge-graph-native setting. There we compare reranked responses against Neural Path Hunter, which repairs one entity at a time from a $k$-hop subgraph, using FeQA and knowledge-verifying QA F1. SURGE reports 57.63 knowledge-verifying QA F1 there.

Efficiency is measured as end-to-end wall-clock per question, split into extraction, precomputation, and scoring, at pool sizes 4, 16, and 64. We expect extraction to dominate. The fair comparison is therefore scoring cost at a fixed extraction cost, set against per-triplet entailment and against the language model judge.