Checking whether a long piece of LLM-generated text is factually correct is slow. The standard recipe splits the text into small atomic claims, retrieves evidence for each one, and asks a strong model to judge it. That costs many model calls per document. Sampling-based detectors that regenerate the answer ten or twenty times are no cheaper. This proposal starts from a simple observation: anyone who runs such a checker at scale builds up, as a side effect, a large bank of atomic claims a given model produced, each labeled supported or unsupported. We propose to reuse that bank through nearest-neighbor label propagation, the technique library indexers use to tag a new document by copying tags from its most similar already-tagged documents. For each new claim, we look up similar past claims and their labels and predict how likely the model is to be wrong here. Only the risky claims go to the expensive checker.
The key design choice concerns what gets propagated. Copying truth from similar claims fails, because "X was born in 1931" and "X was born in 1934" sit almost on top of each other in embedding space and have opposite truth values. What should spread smoothly across neighbors is the generator's error tendency: the kind of claim (birth dates, award lists, co-authors), the kind of entity (obscure versus famous), and the position in the output where this particular model tends to fabricate. We will test whether a neighbor graph built over that representation can cut verification cost several-fold while missing almost none of the hallucinated claims. We will also test whether it beats the obvious cheap alternatives: an entity-popularity heuristic and a classifier trained on the same bank.
Core Claim
Hallucination risk for a fixed generator can be predicted from labeled neighbors in a "claim-type × entity-profile" space well enough to act as a triage filter. The target is to keep at least 95% recall of unsupported atomic claims while sending a minority of claims to the full verifier. The filter adds only milliseconds of index lookup per claim. The claim is falsifiable in two directions. It fails if propagation does no better than an entity-frequency rule. It also fails if it does no better than a parametric classifier fit on the same labeled bank, because then the neighbor graph adds nothing over supervision.
Where This Sits
Two sources motivate the work. The first is the label-propagation literature. In MeSH indexing, Huang et al. aggregate tags from nearest annotated neighbors and beat standard classifiers. MaRSI embeds documents, searches neighbors with Faiss, and ranks candidate subjects. It placed first on the SemEval-2025 core subject-indexing task (65.68% average recall, 52.13% precision), ahead of both fine-tuning and retrieval-augmented generation, and it ran much faster. Swarup et al. show that instance-level copying from neighbors stays robust with only 5% of the training data. That robustness matters for long-tail entities. All three assume neighbor labels are gold human annotations of a stable property. We instead propagate a property of the generator, which is noisier and depends on the model.
The second source is the cost and failure profile of factuality checkers. FActScore introduced atomic-claim decomposition with Wikipedia retrieval and documented two patterns. Factuality drops sharply for rare entities, and it decays as the output grows longer. Both patterns are regularities a neighbor model should be able to exploit. VeriFastScore attacks the same cost problem differently. It distills the multi-call pipeline into one model, reaching a 6.6× speedup and r = 0.80 example-level correlation with the full pipeline. Our approach is complementary: it decides which claims need checking at all. SelfCheckGPT detects hallucinations from disagreement among resampled outputs. It needs no external labels, but it pays for many extra generations.
The closest connecting work builds graphs inside a single query. BTPROP prompts the LLM for supporting and contradicting premises, links them with an NLI model, and runs belief propagation over the resulting tree. It reports 3–9% AUROC/AUC-PR gains over SelfCheckGPT. Chen et al. propagate token uncertainty along semantic-parse edges within one passage. Noël analyzes the spectra of attention graphs. None of these carry labels across generations, so each pays its full cost on every query. Our graph spans many past generations and is cheap to query. In exchange, it requires a labeled history and is specific to one generator.
Two results constrain the design. HaluEval and FELM show that models judging hallucinations directly are weak. ChatGPT reaches 58.53% accuracy on summarization, and GPT-4 scores around 40 segment-level F1 on FELM. That argues against using the generator's own verbal judgment as the cheap signal. The near-duplicate-with-opposite-truth problem argues against copying truth values at all.
Research Program
The labeled bank comes from running the FActScore pipeline over generations from one model. The FActScore benchmark already provides atomic claims for roughly 6,500 biographies from 13 LLMs, with an automated estimator within 2% of human judgments. Each claim gets three cheap descriptors. The first is a template embedding: the claim with its entity mention replaced by a placeholder, so "X won the Pulitzer in 1987" and "Y won the Pulitzer in 1990" become neighbors. The second is an entity profile: an estimate of entity popularity, such as Wikipedia page length or link count, plus the entity's occupation category. The third is the claim's relative position in the generation.
We build a k-nearest-neighbor graph over bank claims and incoming claims, then run standard label propagation. Unlabeled nodes iteratively take the similarity-weighted average of their neighbors' unsupported-rate until scores converge. The resulting score ranks claims, and a threshold tuned on a development split routes the top fraction to the full verifier. Claims below the threshold are accepted as supported for scoring purposes.
The study has three analytic parts. First, it measures how risk smoothness depends on the representation, comparing raw sentence embeddings, template embeddings, entity profiles, and their combination. Second, it tests transfer, asking how much a bank built from one generator helps for a different one, and how large a bank must be before propagation beats the popularity rule. Third, it runs a failure analysis on the claims triage misses, checking whether they cluster on common entities with subtle errors. Those are exactly the cases where the rarity prior points the wrong way.
Baselines
The naive reference point is to run the full FActScore verifier on every claim. This defines the cost ceiling and supplies the labels that triage decisions are scored against. Any triage result is reported as the fraction of verifier calls saved at a fixed recall of unsupported claims, alongside the error in the resulting document-level FActScore. A random-routing baseline at the same call budget sets the floor.
The most dangerous cheap competitor is the entity-popularity rule. It ranks claims by how obscure their entity is, which directly encodes the rarity penalty FActScore documents. It uses the same popularity feature our method uses, applied alone, so the comparison isolates what neighbors add beyond rarity.
The strongest supervised competitor is a parametric classifier trained on exactly the same labeled bank and features. We run two versions: gradient-boosted trees over the descriptors, and a small LoRA-tuned open model in the style of OPDAI, which showed small weakly-supervised LLMs competitive on SHROOM (0.836 accuracy, model-agnostic track). Both get the same bank, the same development set, and the same hyperparameter-search budget as the neighbor method.
The strongest existing detector on this data is SelfCheckGPT. On WikiBio GPT-3 its prompt variant reports 93.42 AUC-PR for detecting non-factual sentences. BTPROP reports 3–9% gains over it, but the file gives only relative figures for BTPROP. We run SelfCheckGPT with N = 5 and N = 20 samples on the same claims and compare detection quality per unit of compute. Beating it means matching its AUROC on entity-disjoint WikiBio GPT-3 claims at under a tenth of its generation cost, or exceeding it at equal cost.
The key-ingredient ablation copies truth from the nearest verified Wikipedia-derived facts instead of propagating error history. If that version works as well, our central argument about what should be propagated is wrong.
Why not just…?
Why not just rank claims by entity popularity? This is the real threat, since FActScore shows that rarity alone drives much of the error. Our bet is that error tendency also depends on claim type and position: a model may reliably know famous people's birth years yet fabricate their award lists. Popularity alone cannot see that. The experiment is direct. If adding template and position neighbors does not raise verifier-call savings at 95% recall over the popularity-only rule on entity-disjoint splits, we will report the simpler rule as the answer.
Why not just train a classifier on the labeled bank? A parametric model can learn the same regularities. The case for neighbors is that they update by adding rows with no retraining, which suits a bank that grows with every verification run, and that they hold up in sparse regimes, as Swarup et al. and MaRSI's comparison against fine-tuning suggest. Neither result is on this task. We will compare learning curves across bank sizes. If the classifier matches the neighbor method everywhere, the contribution reduces to "learned triage," and we will state that.
Why not just run a faster verifier like VeriFastScore on everything? Distillation reduces per-claim cost. Triage reduces the number of claims checked, so the two compose. We will measure total wall-clock time and score error for the distilled verifier alone and for triage placed in front of it.
Why not just ask the model or resample it? HaluEval and FELM show that direct self-judgment is unreliable, and resampling multiplies generation cost. SelfCheckGPT is included at matched compute to settle this.
Proposed Experiments
The main experiment uses FActScore atomic claims split by entity, so no test entity appears in the bank. This prevents the neighbor method from simply remembering facts about the same person. We report claim-level AUROC, verifier calls saved at 95% and 99% recall of unsupported claims, and the absolute error of triaged document FActScore relative to the full pipeline. Results are given per generator and for cross-generator transfer, where the bank comes from one of the 13 models and the test claims from another.
A domain-shift check applies a biography-built bank to WikiBio GPT-3 sentences. We report AUC-PR there next to SelfCheckGPT's 93.42.
A second regime uses the ACM CCS reference dataset of Agrawal et al., which contains search-verified hallucination labels on generated paper titles, 46.8% fabricated for GPT-4 and 73.6% for GPT-3. Here we test topic-disjoint propagation. No reported result was found on Lacuna for nearest-neighbor triage on either FActScore or the ACM set, so these establish the first numbers.
FELM's non-biographical domains serve as a stress test where we expect smoothness to break, especially in math and reasoning. A null result there would mark the method's scope.
The decisive check has three parts. On entity-disjoint FActScore claims, the full neighbor method must beat the popularity rule and the same-bank classifier on calls saved at 95% recall. Its triaged FActScore must stay within the reported 2% estimator error. The truth-copying ablation must do clearly worse. If any of these fails, the result tells us which simpler mechanism actually carries the signal.
References
- Learning to Annotate Scientific Publications
- RUC Team at SemEval-2025 Task 5: Fast Automated Subject Indexing: A Method Based on Similar Records Matching and Related Subject Ranking
- An Instance Level Approach for Shallow Semantic Parsing in Scientific Procedural Text
- FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation
- VeriFastScore: Speeding up long-form factuality evaluation
- SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models
- A Probabilistic Framework for LLM Hallucination Detection via Belief Tree Propagation
- Enhancing Uncertainty Modeling with Semantic Graph for Hallucination Detection
- A Graph Signal Processing Framework for Hallucination Detection in Large Language Models
- HaluEval: A Large-Scale Hallucination Evaluation Benchmark for Large Language Models
- FELM: Benchmarking Factuality Evaluation of Large Language Models
- OPDAI at SemEval-2024 Task 6: Small LLMs can Accelerate Hallucination Detection with Weakly Supervised Data
- Do Language Models Know When They're Hallucinating References?