Skip to content

Sampling Less, Knowing More: Contradiction-aware Adaptive Spectral and Entropic Uncertainty Quantification for LLMs

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM (Other)
Keywords: Uncertainty Quantification, Contradiction Graph, Adaptive Sampling, Spectral Norm, Predictive Entropy

TL;DR

The CASE framework constructs a sparsified bidirectional contradiction graph over sampled LLM candidate responses and computes its normalized spectral norm to quantify semantic disagreement, enabling dynamic early-stopping sampling that cuts generation costs by over 30% while combining token-level predictive entropy from a deterministic anchor to resolve failures on consistent errors.

Background & Motivation

Large language models have demonstrated impressive capabilities across question answering, mathematical reasoning, and knowledge-intensive applications, yet their persistent tendency to hallucinate poses severe risks in high-stakes domains such as medicine and law. To enhance system reliability and safeguard downstream decisions, uncertainty quantification (UQ) has emerged as an indispensable post-generation calibration mechanism. Early single-sample UQ metrics relying on sequence perplexity, maximum token probability, or token-level predictive entropy frequently suffer from superficial phrasing variations and sentence length artifacts. Consequently, recent literature has shifted towards multi-sample UQ strategies such as Semantic Entropy (SE) and Kernel Language Entropy (KLE), which draw multiple stochastic responses for a given query and estimate uncertainty from the semantic diversity across the generated candidate set.

However, prevailing multi-sample UQ paradigms exhibit two critical theoretical and practical bottlenecks. First, existing approaches enforce a rigid, fixed sampling budget (typically 10 responses per query) regardless of query complexity or model confidence. For straightforward queries where model outputs exhibit strong semantic consensus, additional samples introduce minimal incremental information, resulting in substantial computational redundancy and unnecessary inference latency. Second, multi-sample estimators rely almost exclusively on semantic disagreement across sampled generations as their primary uncertainty signal. When a model succumbs to persistent misconceptions and repeatedly generates semantically consistent yet factually incorrect responses (consistent errors), the semantic contradiction structure collapses, yielding spuriously low uncertainty scores and failing to differentiate confident hallucinations from genuine knowledge.

Addressing the dual challenges of excessive sampling overhead and metric degeneration under consistent errors requires a fundamentally different uncertainty formulation: one that can dynamically monitor the marginal stabilization of semantic conflict to stop sampling early, while retaining a complementary internal signal to flag confident errors when structural variance is absent. The authors resolve this tension by modeling response contradictions as an algebraic graph whose normalized spectral norm provides a scale-invariant metric of global semantic conflict, while integrating token-level predictive entropy from a greedy response anchor. Core idea: model mutual contradictions across sampled responses as a sparsified undirected contradiction graph whose normalized spectral norm quantifies semantic disagreement to drive adaptive early stopping, combined with greedy token-level predictive entropy to resolve metric collapse under consistent errors.

Method

Overall Architecture

CASE (Contradiction-aware Adaptive Spectral and Entropic UQ) operates as an inference-time uncertainty quantification framework that requires no parameter updates or fine-tuning of the underlying LLM. The end-to-end pipeline consists of three coordinated processing stages: semantic-level candidate generation and topology construction, where sampled responses are pairwise evaluated by a natural language inference (NLI) model to build a sparsified symmetric contradiction graph; spectral analysis and adaptive sampling, which evaluates the normalized graph spectral norm and tracks its marginal perturbation to dynamically trigger early stopping; and token-semantic fusion, which extracts average predictive entropy from a low-temperature deterministic response and linearly blends it with the spectral contradiction score to produce the final calibrated uncertainty output.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Query x & Target LLM"] --> B["Stage 1: Sparsified Symmetric Contradiction Graph<br/>NLI probability margin truncation + geometric symmetrization"]
    B --> C["Stage 2: Normalized Spectral Norm Semantic Uncertainty<br/>U_spec = ||H||โ‚‚ / (k-1) โˆˆ [0, 1]"]
    C --> D{"Stage 3: Spectral Perturbation Adaptive Sampling<br/>Marginal change |ฮ”U_spec| โ‰ค ฯต for ฯ„ consecutive steps?"}
    D -- No (Unconverged) --> E["Generate next candidate response & update graph"]
    E --> B
    D -- Yes (Converged) / Reach K_max --> F["Stage 4: Token-Level Predictive Entropy Anchor<br/>Average token entropy U_en of greedy response y*"]
    F --> G["Final Calibrated Score: U_CASE = U_spec + ฮฑ ยท U_en"]

Key Designs

1. Sparsified Symmetric Contradiction Graph: Filtering Unidirectional Noise and Entailment Leakage

Standard semantic clustering or similarity graph approaches often yield dense connectivity, as NLI classifiers frequently assign non-zero contradiction probabilities even when sentence pairs exhibit strong entailment. Furthermore, natural language inference relations are inherently directional, meaning asymmetric entailment or prediction artifacts can introduce spurious unidirectional contradictions that do not reflect true semantic conflict. To construct a clean, discriminative topological representation, CASE applies a non-linear margin threshold between directed candidate pairs \((a_i, a_j)\): $\(W_{i,j} = \max\left(0, P_C(a_i, a_j) - P_E(a_i, a_j)\right)\)$ where \(P_C\) and \(P_E\) denote predicted contradiction and entailment probabilities, respectively. Positive edge weights are retained only when contradiction strictly surpasses entailment. Next, to eliminate asymmetric classification noise and focus strictly on mutual semantic opposition, the directed matrix \(W\) is symmetrized into an undirected contradiction matrix \(H^{(k)} \in \mathbb{R}^{k \times k}\) via their geometric mean: $\(H^{(k)}_{i,j} = \sqrt{W_{i,j} W_{j,i}} \quad (i \neq j), \quad H^{(k)}_{i,i} = 0\)$ This construction guarantees that non-zero edges encode genuine bidirectional contradictions, suppressing background entailment noise and asymmetric artifacts.

2. Normalized Spectral Norm Semantic Uncertainty: Scale-Invariant Disagreement Quantification

Once the symmetric non-negative matrix \(H^{(k)}\) is established, quantifying global contradiction intensity without falling prey to arbitrary sample size scaling is non-trivial. While simple edge counts or degree metrics miss higher-order cluster density, algebraic graph theory dictates that for a real symmetric non-negative matrix, the induced \(L_2\) spectral norm \(\|H^{(k)}\|_2\) equals its principal eigenvalue \(\lambda_{\max}(H^{(k)})\) by the Perron-Frobenius theorem. This principal eigenvalue captures how strongly conflicting information aggregates globally across the response network. Because the spectral norm naturally inflates as graph dimension \(k\) increases, CASE introduces a theoretically grounded normalization by the maximum possible row sum: $\(U^{(k)}_{\text{spec}} = \frac{\|H^{(k)}\|_2}{k - 1}\)$ Since all off-diagonal weights satisfy \(H^{(k)}_{i,j} \in [0, 1]\), the maximum row sum degree satisfies \(d_{\max} \le k - 1\). As the spectral norm is strictly bounded by the maximum row sum (\(\|H^{(k)}\|_2 \le d_{\max} \le k - 1\)), dividing by \(k - 1\) strictly bounds the uncertainty score within \(U^{(k)}_{\text{spec}} \in [0, 1]\). A score of 0 denotes complete consensus, while 1 corresponds to an idealized fully connected clique of maximal contradictions, establishing an absolute, scale-invariant reference for multi-stage comparison.

3. Spectral Perturbation Adaptive Sampling: Eliminating Redundant Computation on Stable Queries

Existing entropy-based estimators like SE and KLE alter their empirical probability support and kernel eigenspectra continuously during sequential sampling, making stage-to-stage uncertainty deltas unstable and ill-suited for early stopping. In contrast, incorporating a newly generated candidate \(a_k\) into CASE corresponds to appending a row and column vector \(v \in \mathbb{R}^{k-1}\), representing a rank-2 perturbation matrix \(E^{(k)}\) to the padded previous adjacency matrix. By Weyl's inequality, the step-to-step variation in the normalized spectral uncertainty satisfies a tight finite-sample bound: $\(\Delta U^{(k)} = \left| U^{(k)}_{\text{spec}} - U^{(k-1)}_{\text{spec}} \right| \le \frac{\|E^{(k)}\|_2}{k-1} + \frac{1}{k-1}\)$ As sampling progresses, the diminishing normalization denominator enforces bounded spectral adjustments. CASE implements a patience-based stopping criterion with tolerance \(\epsilon\) and patience \(\tau\): beginning at \(k=2\), the model draws candidates incrementally and terminates sampling whenever \(\Delta U^{(k)} \le \epsilon\) holds for \(\tau\) consecutive steps (or when \(k\) reaches \(K_{\max}\)). When the graph topology reaches spectral stabilization, additional generation yields diminishing information, enabling CASE to safely halt inference and eliminate redundant compute on unambiguous queries.

4. Token-Level Predictive Entropy Anchor: Mitigating Metric Collapse on Consistent Errors

When an LLM repeatedly hallucinates the exact same plausible fallacy due to deeply ingrained parametric biases, every sampled output agrees. Under these consistent errors, all pair-wise contradiction weights vanish, driving \(H^{(k)} \to 0\) and collapsing purely semantic metrics like \(U_{\text{spec}} \approx 0\) into dangerously confident mispredictions. To rectify this structural vulnerability, CASE extracts internal predictive uncertainty directly from the autoregressive token distributions. A deterministic anchor response \(y^* = (y^*_1, \dots, y^*_L)\) is generated under low temperature (\(T=0\)), and its mean token-level Shannon entropy is computed: $\(U_{\text{en}}(x) = \frac{1}{L} \sum_{t=1}^L \sum_{v \in V} - P(v \mid x, y^*_{<t}) \log P(v \mid x, y^*_{<t})\)$ Even when the model's generated text appears superficially uniform, token logits during autoregressive steps often betray internal predictive dispersion. By combining the global topological signal with localized token entropy via scaling factor \(\alpha\): \(U_{\text{CASE}}(x) = U_{\text{spec}}(x) + \alpha U_{\text{en}}(x)\), CASE successfully detects confident hallucinations where graph-based methods alone are blind.

Benchmark & Evaluation Protocol

CASE is an inference-only framework and requires no training or gradient computation. The evaluation setup uses greedy decoding (\(T=0\)) for the base prediction \(y^*\) and for calculating token entropy \(U_{\text{en}}\). Candidate generation utilizes stochastic nucleus sampling with temperature \(T=1.0\), top-\(p=0.9\), and top-\(k=50\). Pairwise contradictions are evaluated using nli-deberta-v3-large. Adaptive sampling boundaries are configured with \(K_{\min}=2, K_{\max}=10\), stopping tolerance \(\epsilon=0.01\), patience \(\tau=2\), and fusion coefficient \(\alpha=1.0\). Experiments span four factual QA benchmarks: Natural Questions (NQ), TriviaQA, HotpotQA (multi-hop reasoning), and PopQA (long-tail entity recall), each sampled at 1,000 queries. Output correctness is judged against reference gold answers using Qwen-Flash under an LLM-as-a-judge protocol. Primary evaluation metrics are the Area Under the Receiver Operating Characteristic curve (AUROC) and the Area Under the Accuracy-Rejection Curve (AUARC).

Key Experimental Results

Main Results

The table below summarizes performance across three open-source LLMs (LLaMA-3-8B-Instruct, Qwen3-8B, and Qwen3-14B) on four factual QA datasets, comparing single-sample baselines (PPL, P(true), Entropy) and multi-sample baselines (SE, KLE, SNNE, all fixed at 10 samples) against CASE:

Model Method PopQA (AUROC / Samp.) HotpotQA (AUROC / Samp.) NQ (AUROC / Samp.) TriviaQA (AUROC / Samp.)
LLaMA-3-8B-Instruct Entropy 78.29% / - 76.12% / - 72.92% / - 80.36% / -
SE 77.32% / 10.0 75.58% / 10.0 71.42% / 10.0 81.06% / 10.0
KLE 82.30% / 10.0 78.61% / 10.0 79.77% / 10.0 84.96% / 10.0
SNNE 68.12% / 10.0 71.10% / 10.0 72.05% / 10.0 75.88% / 10.0
CASE (Ours) 83.22% / 7.50 81.34% / 6.57 80.74% / 6.69 85.28% / 6.40
Qwen3-8B Entropy 73.96% / - 77.86% / - 75.40% / - 79.06% / -
SE 75.68% / 10.0 79.01% / 10.0 76.86% / 10.0 79.56% / 10.0
KLE 80.35% / 10.0 81.08% / 10.0 79.61% / 10.0 80.52% / 10.0
SNNE 75.76% / 10.0 72.01% / 10.0 72.40% / 10.0 75.27% / 10.0
CASE (Ours) 81.43% / 7.27 81.65% / 6.57 80.63% / 6.40 82.45% / 6.41
Qwen3-14B Entropy 69.07% / - 77.60% / - 74.90% / - 77.96% / -
SE 70.24% / 10.0 78.37% / 10.0 72.84% / 10.0 78.30% / 10.0
KLE 76.16% / 10.0 80.99% / 10.0 76.76% / 10.0 79.36% / 10.0
SNNE 68.86% / 10.0 70.10% / 10.0 72.00% / 10.0 73.20% / 10.0
CASE (Ours) 77.00% / 6.98 82.39% / 6.34 79.37% / 6.14 81.65% / 5.88

Ablation Study

An ablation analysis on Qwen3-8B isolates the impact of removing predictive token entropy \(U_{\text{en}}\) and disabling adaptive early stopping:

Configuration PopQA (AUROC / Samp.) HotpotQA (AUROC / Samp.) NQ (AUROC / Samp.) TriviaQA (AUROC / Samp.) Note
CASE (Full framework) 81.43% / 7.27 81.65% / 6.57 80.63% / 6.40 82.45% / 6.41 Optimal trade-off between accuracy and sampling
w/o \(U_{\text{en}}\) (Pure spectral) 80.50% / 7.27 77.62% / 6.57 77.81% / 6.40 78.28% / 6.41 AUROC drops by up to 4.17% due to consistent errors
w/o Adaptive sampling (Fixed 10) 82.64% / 10.0 82.08% / 10.0 81.55% / 10.0 83.29% / 10.0 +37%~56% compute overhead for minimal gain (<1% AUROC)

Key Findings

  • Token entropy resolves consistent error failure: Removing \(U_{\text{en}}\) triggers substantial performance degradation across all datasets, most acutely in AUARC (e.g., dropping from 71.49% to 65.37% on HotpotQA). On subsets of queries where all generated responses agree, spectral divergence vanishes (\(U_{\text{spec}} \approx 0\)); token entropy provides the crucial orthogonal separation between correct answers and confident hallucinations.
  • Adaptive sampling delivers genuine wall-clock speedup: CASE reduces the average sample count to 5.88โ€“7.50 per query, cutting generation overhead by 25%โ€“40% without compromising UQ fidelity. Physical wall-clock profiling on NQ reveals that CASE finishes in 5,826.7s, achieving a 30.6% real-world time reduction compared to SE (8,402.1s) and 24.5% compared to KLE (7,719.4s).
  • Insensitivity to hyperparameters and NLI scale: Performance plateaus smoothly across \(\alpha \in [0.2, 1.0]\), demonstrating that fine-tuning the fusion coefficient is unnecessary. Substituting the default nli-deberta-v3-large with base and small variants incurs negligible variations in AUROC, affirming that CASE is not bound to oversized verifier models. Furthermore, on the GSM8K mathematical reasoning benchmark, CASE scores 74.85% AUROC, outperforming SE (60.91%) and KLE (70.77%).

Highlights & Insights

  • Mathematically grounded scale-invariance: By proving that the spectral norm of a non-negative symmetric matrix cannot exceed its maximum degree (\(d_{\max} \le k - 1\)), normalizing by \(k-1\) ensures \(U_{\text{spec}} \in [0, 1]\), enabling mathematically sound step-to-step convergence tracking that was impossible with unbounded entropy metrics.
  • Contradiction graphs outperform entailment graphs: Pruning positive entailment relationships and focusing solely on non-linear, bidirectional contradiction margins concentrates the graph spectrum on true logical conflict, providing a significantly more discriminative signal for error detection than dense entailment kernels.
  • Orthogonal fusion of internal logits and surface semantics: While internal predictive entropy is susceptible to lexical style and prompt phrasing, surface-level semantic graphs fail when errors are uniform. Marrying greedy token logits with dynamic graph topology neatly cancels out the foundational failure modes of both paradigms.

Limitations & Future Work

  • Dependence on natural language inference accuracy: Although robust across NLI model sizes, the framework relies on sentence-level NLI classifiers, which struggle when evaluating long-form multi-paragraph texts, compositional multi-claim narratives, or low-resource multilingual outputs.
  • Occurrence of premature termination: Empirical tracking indicates that 6.5%โ€“8.6% of queries terminate prematurely before reaching 5 samples due to transient early consensus, where continuing to 10 samples would have uncovered latent contradictions.
  • Uncertainty source ambiguity: CASE outputs a scalar score combining token dispersion and contradiction density, but cannot differentiate whether uncertainty originates from linguistic ambiguity, knowledge voids, multi-hop reasoning complexity, or deliberate hallucination.
  • vs Semantic Entropy (SE, Farquhar et al., 2024): SE clusters sampled outputs via bi-directional entailment and evaluates Shannon entropy over cluster probabilities. It demands a static sample size (typically 10) and collapses to zero entropy under consistent errors. CASE constructs a contradiction graph with a normalized spectral norm that enables dynamic early stopping, resolving consistent error failure via token entropy.
  • vs Kernel Language Entropy (KLE, Nikitin et al., 2024): KLE computes Von Neumann entropy over an entailment kernel matrix. Its continuous spectral redistribution across steps prevents scale-invariant early stopping. CASE provides a strictly normalized metric that slashes sampling overhead by over 30% while achieving superior AUROC.

Rating

  • Novelty: โญโญโญโญโญ [Pioneering integration of algebraic graph spectral norms with adaptive sampling for LLM uncertainty]
  • Experimental Thoroughness: โญโญโญโญโญ [Comprehensive benchmarking across 3 LLM architectures, 4 factual QA datasets, GSM8K reasoning, and wall-clock timings]
  • Writing Quality: โญโญโญโญโญ [Rigorous algebraic derivations, tight conceptual logic, and clear visual layout]
  • Value: โญโญโญโญโญ [High practical impact for reducing real-world inference costs while simultaneously boosting hallucination detection reliability]