PaperlayerView exact revision on arXiv

Source-linked AI summary

Kernel Token Contradiction: a Fast and Principled Approach for LLM Claim Uncertainty Quantification

Jérémie Dentan, Alexi Canesse, Mahammed El Sharkawy, Sonia Vanier

arXiv:2608.22506v1cs.CL

TL;DR

LLM outputs can contain plausible but non-factual claims, while existing claim-level UQ methods face precision, efficiency, and language limitations. KTC combines token contradiction statistics with predictive probabilities in a PSD kernel and uses Von Neumann entropy to estimate uncertainty. Across two benchmarks, four languages, and 16 LLMs, it matches existing methods on average, outperforms them in high-precision regimes, and is designed for efficient monitoring.

  • Problem

    Claim-level UQ seeks reliable factuality estimates for individual LLM claims, but existing methods have insufficient high-precision recall, high computational cost, and English-centered NLI dependence.

  • Method

    KTC represents candidate tokens as a PSD kernel combining predictive probabilities with contradiction scores derived from Wikipedia neighbour-frequency statistics, then applies Von Neumann entropy.

  • Results

    KTC outperforms all baselines in the high-precision regime and achieves 78% average precision at recall ≤20%, compared with 69% for CCP, across four languages and 16 LLMs.

  • Takeaways & Limitations

    KTC provides a stronger performance–computation trade-off and CPU-only efficiency for real-time monitoring of LLM outputs under production latency constraints.

  • Takeaways & Limitations

    KTC requires white-box access to token-level probabilities, and the evaluation covers only four languages and a focused set of benchmarks.

Abstract

from arXiv · show

Claim-level Uncertainty Quantification (UQ) aims to mitigate the lack of reliability of Large Language Models (LLMs) by evaluating the factuality of each claim in their outputs. We introduce Kernel Token Contradiction (KTC), a lightweight approach to compute claim-level UQ under realistic white-box conditions. KTC represents the candidate tokens involved in LLM generation as a positive semi-definite kernel that integrates both the LLM's conditional distribution and a token contradiction score. We then use the Von Neumann entropy to quantify the uncertainty of this kernel. To estimate token contradiction, we develop a new approach based on frequency statistics from the Wikipedia corpus. Although CPU-only, our approach achieves over an 8.2x speedup compared to state-of-the-art GPU-accelerated methods based on cross-encoders, and over a 65x speedup compared to CPU-only methods with comparable performance. Our evaluation spans two benchmarks across four European languages and 16 different models. KTC not only matches the average performance of existing methods but also outperforms them in high-precision regimes. This combination of computational efficiency and accuracy makes real-time monitoring of LLM outputs practical in production.

1 Introduction

Claim-level UQ targets factuality hallucinations by estimating uncertainty for individual claims, while existing methods face precision, speed, and multilingual limitations. KTC addresses these constraints with token-level contradiction modeling and achieves strong high-precision performance with substantially lower computational cost.

  • Motivation: Claim-level UQ estimates factuality uncertainty for individual claims, allowing users to scrutinize uncertain parts without rejecting complete answers.This targets plausible but non-factual LLM content while preserving the rest of an answer.
  • Limitations of prior methods: 69% average precision at recall ≤20% is achieved by CCP, illustrating the limited high-precision recall of existing methods.Existing approaches also rely on GPU-intensive NLI models and English-trained inference models that can perform differently across languages.
  • KTC approach: KTC detects contradictions among candidate tokens using Wikipedia neighbour-frequency statistics instead of NLI inference.The motivating example contrasts contradictory price candidates such as “699” and “499” with non-contradictory alternatives such as “an” and “the”.
  • KTC approach: KTC combines predictive uncertainty from token probabilities with semantic uncertainty from candidate-token contradictions through a four-stage kernel-and-entropy pipeline.The pipeline constructs a non-contradiction graph, forms a PSD semantic kernel, combines it with a predictive kernel, and computes Von Neumann entropy.
  • Results: 78% average precision at recall ≤20% is achieved by KTC, compared with 69% for CCP, while KTC ranks second overall with a small performance gap.The evaluation covers two benchmarks, four European languages, and 16 LLMs.
  • Results: 8.2× speedup is achieved by KTC over GPU-accelerated methods, with no GPU acceleration required.The authors report that its efficiency and high-precision accuracy support practical real-time monitoring of LLM outputs.

2 Background

The background defines entropy-based uncertainty measures and distinguishes predictive uncertainty from semantic distinctions among candidate tokens. It motivates KTC by noting that predictive entropy alone does not capture token semantics, while Figure 3 illustrates how contradiction structure separates uncertainty types.

  • Entropy foundations: Shannon entropy quantifies uncertainty in a finite probability distribution, reaching zero for a certain outcome and log δ when all δ outcomes are equally likely.The definition uses H(X) = −Σ p_i log p_i.
  • Entropy foundations: Von Neumann entropy quantifies uncertainty in a positive semi-definite density matrix through its eigenvalues.The density matrix has trace one, and the entropy is computed from its eigenvalue distribution.
  • Predictive entropy: Predictive entropy applies Shannon entropy to the conditional probabilities of the most likely candidate tokens at a next-token prediction step.The LLM output assigns each candidate token a probability conditioned on the preceding prefix.
  • Uncertainty types: Aleatoric uncertainty reflects inherent generation randomness, whereas epistemic uncertainty reflects missing knowledge and is associated with factual hallucinations.Predictive entropy alone does not account for the semantics of candidate tokens.
  • KTC illustration: Figure 3 contrasts epistemic uncertainty from contradicting prices, aleatoric uncertainty from non-contradictory formulations, and low uncertainty after predictive scaling.The figure shows high KTC for contradictory candidates but low KTC when semantic or predictive uncertainty is not jointly expressed.

3 Kernel Token Contradiction

KTC estimates claim-level uncertainty by combining token predictive probabilities with contradiction-aware semantic structure in a kernel, then applying Von Neumann entropy. Its graph-based pipeline uses Wikipedia neighbour statistics to identify token non-contradiction and integrates both uncertainty sources.

  • 3.1 [Step A] Building a Non-Contradiction Graph over Candidate Tokens: KTC builds a non-contradiction graph whose nodes are candidate tokens and whose edge weights represent how little the candidates contradict each other.Previous methods use NLI models for entailment assessment, whereas KTC replaces this costly component with a token-based graph.
  • 3.1 [Step A] Building a Non-Contradiction Graph over Candidate Tokens: Wikipedia neighbour statistics estimate token non-contradiction by comparing the most frequent neighbouring tokens of candidate pairs.The method counts tokens appearing immediately before or after each candidate in a large tokenized Wikipedia corpus.
  • 3.1 [Step A] Building a Non-Contradiction Graph over Candidate Tokens: Prefix-related candidates are treated as non-contradictory because the language model can generate the missing suffix at the next step.This is encoded through the prefix relation ∆i ⪯∆j or ∆j ⪯∆i.
  • 3.2 [Steps B and D] Building the Semantic Kernel and computing Von Neumann Entropy: KTC constructs a Laplacian-based heat kernel from the graph, normalizes it, and computes its Von Neumann entropy as semantic entropy.The semantic kernel is built from candidate-token semantics represented by the graph.
  • 3.2 [Steps B and D] Building the Semantic Kernel and computing Von Neumann Entropy: Greater graph connectivity corresponds to lower semantic uncertainty, while weak connectivity produces multiple large kernel eigenvalues and higher entropy.The paper links connectivity to the Fiedler value and explains how the heat-kernel spectrum determines entropy.
  • 3.3 [Step C] Incorporating the conditional distribution: KTC combines the semantic kernel with a normalized kernel of candidate-token conditional likelihoods before computing final Von Neumann entropy.The likelihood kernel is formed from the LLM probabilities, while the combined kernel incorporates predictive and semantic information.

4 Related Works

The paper positions KTC within factual, white-box, instance-specific claim-level UQ and contrasts it with generation-level kernel methods and NLI- or likelihood-based baselines. Its main distinction is adapting kernel uncertainty from generated outputs to candidate tokens.

  • Scope of the comparison: KTC targets factuality hallucinations using white-box, instance-specific uncertainty estimates based on model logits and activations.The scope excludes input-conflicting, context-conflicting, and faithfulness hallucinations, as well as black-box approaches using only generated text.
  • Comparison with Kernel-based and Semantic Methods: KLE and related methods construct positive semi-definite kernels from semantic similarities between complete outputs, whereas KTC applies the principle at token level.The paper distinguishes KTC from generation-level methods such as SGPU and SNNE.
  • White-box claim-level UQ methods used as baselines: The evaluated white-box baselines include NLI-based CCP and SAR alongside maximum-likelihood, token-likelihood, and token-entropy methods.These baselines represent both contradiction-based and likelihood-based approaches to claim-level UQ.

5 Empirical Results

Across two benchmarks, four languages, and 16 LLMs, KTC delivers competitive claim-level UQ while substantially reducing computational overhead. It is especially strong in high-precision regimes and maintains this advantage across aggregation strategies and languages.

  • Overall performance: KTC achieves competitive performance across two benchmarks, four languages, and 16 LLMs while being significantly faster than state-of-the-art methods.The evaluation compares KTC with white-box baselines including CCP, SAR, Maximum Likelihood, Token Likelihood, and Token Entropy.
  • Efficiency: 5.6% overhead gives KTC its top ROC-AUC performance on CPU, compared with 46% on GPU and up to 369% on CPU for comparable CCP configurations.These correspond to 8.2× and 65× higher overheads for CCP on GPU and CPU, respectively.
  • High-precision detection: 0.78 PR-AUC at recall ≤20% outperforms CCP’s 0.69 in the high-precision regime despite KTC’s much lower computational cost.KTC also outperforms all baselines by a clear margin in this regime.
  • Cross-language generalization: KTC consistently outperforms all baselines in the low-recall, high-precision regime across languages, with its clearest advantage in English, French, and German.In Spanish, the gap is narrower and CCP surpasses KTC beyond 20% recall.
  • Aggregation ablation: Across mean, maximum, geometric-mean, and product aggregation, KTC dominates baselines in the high-precision regime and achieves competitive ROC-AUC.The curves are averaged over four languages and 16 LLMs, with each strategy evaluated over its full grid search space.
  • Kernel-combination ablation: SCALE consistently outperforms COMB, while COMB performs best around α ∈[0.5, 0.75] and worse at α = 0 or α = 1.The results support coupling semantic and predictive kernels rather than relying on either component alone.
  • Heuristic validation: The Wikipedia heuristic assigns substantially higher non-contradiction scores to synonyms and hypernyms than to other semantically related concepts.This validates the heuristic’s intended distinction between non-contradictory and potentially contradictory token pairs.

6 Limitations and Future Work

KTC’s evaluation is limited to four European languages and assumes access to token-level probabilities. Extending language coverage and supporting black-box settings are identified as future directions.

  • KTC is evaluated only on English, French, German, and Spanish because it relies on the MUCH segmenter.
  • KTC does not dominate every baseline across all operating regimes, but offers a stronger performance–computation trade-off and consistently leads in high-precision settings.
  • KTC assumes access to token-level probabilities, leaving extension to black-box settings with partial or approximate log-probabilities as future work.

7 Conclusion

The paper concludes that KTC combines Wikipedia-based contradiction signals with predictive uncertainty in a CPU-only method. It delivers strong high-precision performance and an accuracy–cost trade-off, while heat kernels are retained because alternatives were less effective.

  • KTC combines predictive uncertainty with a contradiction signal derived from Wikipedia neighbour statistics.
  • KTC ranks second to CCP on overall ROC-AUC but achieves the best accuracy–cost trade-off and dominates baselines in the high-precision regime.These results hold across four languages and 16 LLMs.
  • KTC’s semantic kernels are built from candidate-token relationships represented through a non-contradiction graph and normalized to unit trace.
  • Heat kernels were retained because preliminary experiments found alternative kernels less effective at capturing semantic uncertainty.

B Additional Results

Additional ROC results compare claim-level hallucination detection across languages and token-to-claim aggregation strategies. KTC achieves the second-best performance, closely following CCP.

  • KTC achieves the second-best ROC performance, closely following CCP.
  • Figure 7 reports ROC curves across English, French, Spanish, and German, averaged over 16 LLMs and two benchmarks using product aggregation.Each method is shown at its best-performing configuration across its full grid search space.
  • Figure 8 compares KTC under Mean, Maximum, Geometric mean, and Product token-to-claim aggregation strategies.Results are averaged over all four languages and 16 LLMs.

C Validation of the Wikipedia heuristic

The Wikipedia heuristic estimates token substitutability from neighborhood overlap rather than neural semantic similarity. Validation supports this interpretation, while also exposing limitations of corpus-based scores and motivating graph-level aggregation.

  • KTC estimates token substitutability from overlap between Wikipedia neighborhoods constructed from token occurrences.
  • Synonyms and hypernyms receive substantially higher non-contradiction scores than semantically close non-hypernym pairs.Table 2 reports means and standard deviations over 100 pairs per category.
  • Some categories, including animals and space objects, still receive relatively high scores, reflecting limitations of the corpus-based heuristic.
  • KTC applies heat-kernel diffusion over the full candidate-token graph before computing Von Neumann entropy, aggregating local relationships beyond individual pairwise scores.

D Hyperparameter Tuning and Generalization

The evaluation tunes methods over predefined hyperparameter grids and examines whether selected KTC configurations retain their accuracy–efficiency trade-off on unseen automatically annotated data. A faster Small NLI baseline variant is also tested but does not achieve a better trade-off than KTC.

  • Hyperparameter Tuning: KTC uses 30 evaluated configurations, with eight selected for the main paper by combining the seven best ROC-AUC and seven best PR-AUC configurations after overlap removal.Selection is based on manually annotated evaluation data.
  • Baseline Configurations: The SAR and CCP comparisons include Small, Medium, and Large NLI models to assess whether faster inference improves their accuracy–efficiency trade-off relative to KTC.The Small variant was added specifically for faster inference and was not part of the original papers.
  • Generalization: The Small NLI baseline does not yield a better accuracy–efficiency trade-off than KTC.This comparison is reported across the experiments evaluating the added Small variant.
  • Base Evaluation: CCP and SAR produce identical predictions on CPU and GPU, while only their computation times differ.The base evaluation reports time relative to LLM generation time.
  • Generalization: The selected KTC configurations are evaluated without retuning on 4,673 automatically annotated MUCH samples excluded from the base experiments.Figure 9 assesses whether the accuracy-efficiency trade-off generalizes to unseen data.

E Reproducible Science

The paper uses publicly available datasets and releases code, licensing information, and reproducibility details to support replication. The repository includes environment information, experiment instructions, and exact hyperparameter values.

  • Data and Code Availability: The MUCH and Mu-SHROOM datasets are publicly available, and the paper releases a code repository for reproducing the results.The repository is identified as orailix/kernel_token_contradiction.
  • Licenses: The paper records licenses for both datasets and for the NLI models used in baseline methods.MUCH uses Apache 2.0, Mu-SHROOM uses CC BY 4.0, and the listed NLI models use MIT licensing.
  • Reproducibility: The repository includes library versions, environment instructions, experiment-running information, and exact hyperparameter values.Additional tuning details are provided in Appendix D and the code repository.
Loading 2608.22506v1…