BiG-SURE: Bipartite Graph for Semantic Uncertainty and Reliability Estimation of LLMs¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/iiscleap/BiG-SURE
Area: LLM Reasoning
Keywords: Uncertainty Estimation, Black-Box LLMs, Bipartite Graph Spectral Energy, Semantic Consistency, Selective Prediction
TL;DR¶
BiG-SURE addresses black-box LLM/VLM uncertainty estimation by pairing stable low-temperature responses as semantic anchors with high-temperature responses under meaning-preserving input perturbations as probes, constructing an NLI-weighted bipartite graph and quantifying uncertainty via the complement of normalized squared spectral energy, outperforming prior black-box estimators across text, multilingual, and multimodal QA abstention tasks.
Background & Motivation¶
Large language models (LLMs) and vision-language models (VLMs) have demonstrated exceptional capabilities across natural language question answering, mathematical problem solving, and multimodal perception. However, in open-ended generation, these models frequently suffer from hallucinations, factual inaccuracies, and cross-lingual inconsistencies. In safety-critical domains such as medical diagnosis, financial forecasting, and legal analysis, deploying foundation models without reliable uncertainty measures poses severe risks, making calibration, confidence scoring, and selective abstention paramount prerequisites for deployment readiness. Crucially, contemporary commercial LLMs are predominantly accessible solely via closed-source black-box APIs, where internal model weights, hidden-state representations, and token generation probabilities (logits) are entirely inaccessible, necessitating post-hoc uncertainty estimators operating strictly on surface outputs.
Existing black-box uncertainty quantification methodologies primarily rely on sampling responses at a single, fixed temperature and calculating dispersion statistics across the sampled set. For instance, Discrete Semantic Entropy (DSE) clusters stochastically generated high-temperature outputs using bidirectional natural language inference (NLI) and evaluates entropy over the resulting discrete cluster distribution; similarly, Kernel Language Entropy (KLE) and Semantic Nearest Neighbor Entropy (SNNE) construct continuous pairwise semantic similarity kernels to compute von Neumann entropy or nearest-neighbor distances. However, these fixed-temperature frameworks share fundamental limitations: first, they discard the dynamic response transition across sampling temperatures, failing to differentiate robust, high-confidence semantic beliefs from fragile, stochastic hallucinations; second, because all responses are sampled under high stochasticity without an anchor, lexical and semantic drift compound across pairs, often confusing spurious semantic clusters with legitimate model certainty.
To overcome the blind spots of single-temperature sampling, this work proposes to exploit cross-temperature semantic agreement dynamics. The central intuition is that when a model is confident and correct, its primary semantic belief remains strongly conserved across temperature scales and under meaning-preserving input perturbations; conversely, when uncertain or hallucinating, high-temperature sampling induces pronounced semantic divergence from its low-temperature greedy baseline. Core idea: construct an asymmetric bipartite graph using stable low-temperature outputs as semantic anchors and high-temperature outputs under equivalent input transformations as exploratory probes, quantifying model confidence via the normalized squared spectral energy of the bipartite bi-adjacency matrix and defining uncertainty as its complement in an unsupervised, clustering-free manner.
Method¶
Overall Architecture¶
The operational pipeline of BiG-SURE comprises four sequential stages: dual-path cross-temperature sampling with input augmentations, bipartite semantic similarity graph construction, spectral energy confidence calculation, and complement uncertainty output. Given an input query \(x\) and a black-box model \(\theta\), the pipeline generates a bounded uncertainty estimate \(U_{\text{norm}}(W; \theta) \in [0, 1]\) used directly for selective abstention. The system first samples \(M\) anchor responses from \(x\) at a minimal temperature \(T_L = 0.1\) to capture the model's core belief. Simultaneously, it generates semantics-preserving question paraphrases (and lightweight visual perturbations in multimodal settings) and samples \(N\) high-temperature probe responses at \(T_H = 1.0\). A frozen NLI model then scores pairwise entailment across anchors and probes to populate the bi-adjacency matrix \(W\), from which the normalized squared Frobenius norm directly yields the spectral energy confidence score.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Query x & Black-Box Model θ"] --> B["Cross-Temperature Dual Sampling with Input Perturbations<br/>Low TL yields Anchors A / High TH yields Probes H"]
B --> C["Bipartite Semantic Similarity Graph Construction<br/>Pairwise NLI entailment probabilities populate W"]
C --> D["Normalized Squared Spectral Energy Quantification<br/>Leading singular mode energy Enorm=||W||_F^2 / (MN)"]
D --> E["Spectral Energy Complement Uncertainty Estimation<br/>Unorm = 1 - Enorm for selective abstention"]
Key Designs¶
1. Cross-Temperature Dual-Path Sampling with Meaning-Preserving Perturbations: Decoupling Reference Anchors from Exploratory Probes
Prior sampling techniques draw all candidate sequences from a single high temperature (\(T=1.0\)), which easily introduces erratic semantic drift that misrepresents confident predictions, or from low temperatures where outputs collapse into identical tokens lacking informative diversity. BiG-SURE decouples the candidate space into two functionally specialized sets: an anchor set \(A = \{a_1, \dots, a_M\}\) generated from the original prompt \(x\) at low temperature \(T_L = 0.1\) (\(M=3\)), establishing the model's canonical semantic center; and a probe set \(H = \{h_1, \dots, h_N\}\) generated at high temperature \(T_H = 1.0\) (\(N=10\)). To rigorously challenge model stability, the probe set incorporates 5 distinct meaning-preserving input transformations (syntactic prompt paraphrasing via instruction LLMs for text, and mild affine rotations \(\pm 10^\circ\), Gaussian noise \(\mathcal{N}(0, 10)\), and mean blur for images in vision-language tasks), sampling twice per perturbation. This asymmetric structure ensures probes thoroughly explore the semantic boundary while anchors provide an invariant reference frame.
2. NLI-Based Bipartite Semantic Adjacency Formulation: Eliminating Discrete Clustering Errors via Continuous Edge Weights
Traditional semantic entropy frameworks require threshold-based semantic clustering, which suffers from error propagation at cluster boundaries and high sensitivity to heuristic clustering hyperparameters. BiG-SURE avoids discrete partitioning by constructing a weighted bipartite graph \(G = (A, H, W)\), where each entry \(W_{ij}\) in the bi-adjacency matrix \(W \in \mathbb{R}^{M \times N}\) represents the continuous semantic similarity between anchor \(a_i\) and probe \(h_j\):
Edge weights are populated via the softmax entailment probabilities of a frozen DeBERTa-large-MNLI model (or mDeBERTa-v3 for multilingual evaluation) without task-specific fine-tuning. Evaluating only the \(M \times N\) cross-temperature pairs incurs a computational complexity of \(\mathcal{O}(MN \cdot C_{\text{sem}})\), which represents a 70% reduction in NLI calls compared to the \(\mathcal{O}(N^2 \cdot C_{\text{sem}})\) full pairwise similarity matrix required by standard graph methods (e.g., 30 evaluations versus 100 when \(M=3, N=10\)).
3. Normalized Squared Spectral Energy Quantification: Extracting Robust Reliability Signals from Leading Singular Modes
To aggregate the bipartite affinity matrix \(W\) into a principled scalar metric without arbitrary heuristics, BiG-SURE defines the spectral energy of agreement as the sum of squared singular values \(\sigma_i\) of \(W\). By unitary invariance of the Frobenius norm, this spectral sum algebraically simplifies to the squared Frobenius norm:
Normalizing by the theoretical maximum \(MN\) yields the confidence score \(E_{\text{norm}}(W; \theta)\), with the final Semantic Uncertainty and Reliability Estimation (SURE) metric defined as its complement:
The authors formally prove that \(U_{\text{norm}}(W; \theta)\) satisfies three fundamental uncertainty axioms: (1) Semantic Identity: \(U_{\text{norm}} = 0\) if and only if all sampled responses are semantically identical and fully entail the anchors (\(W_{ij}=1\)); (2) Semantic Disjointness: \(U_{\text{norm}} = 1\) if and only if all probe responses are entirely disjoint from the anchors (\(W_{ij}=0\)); (3) Monotonicity: if semantic dispersion increases such that \(W' \preceq W\) elementwise, \(U_{\text{norm}}(W'; \theta) \ge U_{\text{norm}}(W; \theta)\). Furthermore, spectral decomposition analysis reveals that the dominant singular value \(\sigma_1\) captures over 99% of the total agreement energy, demonstrating that confident predictions concentrate energy into a low-rank principal mode, whereas uncertain predictions dissipate energy across noisy secondary modes.
Benchmark & Evaluation Protocol¶
The empirical evaluation spans three diverse reasoning paradigms: English text-only factual QA and arithmetic reasoning (Trivia-QA and SVAMP, evaluated on Llama-3.1-8B/70B, Qwen-2.5-7B/72B, and Gemma-3-12B/27B); multilingual science QA (SciQ across English, French, Japanese, and Mandarin, evaluated on Aya-expanse-8B and Apertus-8B); and multimodal visual QA (OK-VQA, evaluated on Pixtral-12B, LLaVA-v1.6-7B, and Qwen2-VL-7B). Performance is measured via Abstention Area Under the Receiver Operating Characteristic Curve (AUROC) and Area Under the Risk-Coverage Curve (AURC). Ground truth correctness is defined on greedy decoding responses (\(T=0\)) via SQuAD F1 \(\ge 0.5\) for textual QA, consensus human answer matching for visual QA, and a validated Gemini-2.5-Flash LLM judge for multilingual QA (verified via human evaluation with Cohen's \(\kappa \ge 0.80\)).
Key Experimental Results¶
Main Results¶
Across all evaluated benchmarks, BiG-SURE is compared against seven prominent black-box uncertainty estimators: Discrete Semantic Entropy (DSE), Graph-based metrics (SumEigv, Deg, NumSet), Lexical Similarity (LexSim), Kernel Language Entropy (KLE), and Semantic Nearest Neighbor Entropy (SNNE), using 5-seed repeated trials.
| Dataset [Language / Modality] | Model Family / Scale | Greedy Acc. | Best Prior Baseline AUROC (↑) | BiG-SURE AUROC (↑) | Relative Gain / Significance |
|---|---|---|---|---|---|
| Trivia-QA [Text / English] | 6 LLMs (7B–72B) | 0.668 | 0.722 ± 0.007 (Deg) | 0.753 ± 0.017 | +0.031 (Best in 5 of 6 LLMs) |
| SVAMP [Math / English] | 6 LLMs (7B–72B) | 0.755 | 0.846 ± 0.018 (SNNE) | 0.877 ± 0.022 | +0.031 (Best in 5 of 6 LLMs) |
| SciQ [Multilingual / English] | 2 LLMs (8B) | 0.775 | 0.646 ± 0.021 (Deg) | 0.677 ± 0.015 | +0.031 (Consistent on Aya & Apertus) |
| SciQ [Multilingual / French] | 2 LLMs (8B) | 0.672 | 0.608 ± 0.016 (LexSim) | 0.590 ± 0.019 | -0.018 (LexSim marginal lead) |
| SciQ [Multilingual / Japanese] | 2 LLMs (8B) | 0.490 | 0.632 ± 0.020 (Deg) | 0.685 ± 0.013 | +0.053 (Significant non-Latin boost) |
| SciQ [Multilingual / Mandarin] | 2 LLMs (8B) | 0.507 | 0.644 ± 0.023 (Deg) | 0.691 ± 0.012 | +0.047 (Significant non-Latin boost) |
| OK-VQA [Multimodal / Visual] | 3 VLMs (7B–12B) | 0.637 | 0.735 ± 0.016 (SNNE) | 0.752 ± 0.014 | +0.017 (Best across all 3 VLMs) |
Ablation Study¶
Extensive ablation experiments on Trivia-QA and SVAMP across all six text-generation LLMs isolate the impact of input augmentation strategies, spectral aggregation formulations, and inference budgets (mean ± standard deviation across 5 seeds).
| Ablation Configuration / Variant | SVAMP AUROC (↑) | Trivia-QA AUROC (↑) | Functional Design & Takeaway |
|---|---|---|---|
| BiG-SURE Full Model (Mixed-Rephrased) | 0.8769 ± 0.0221 | 0.7533 ± 0.0168 | Default setting: 3 low-T anchors + 10 mixed high-T probes |
| Top-1 Truncated Energy (\(U_{\text{Top-1}}\)) | 0.8746 ± 0.0205 | 0.7527 ± 0.0170 | Leading singular value captures almost all informative energy |
| Top-2 Truncated Energy (\(U_{\text{Top-2}}\)) | 0.8766 ± 0.0217 | 0.7532 ± 0.0172 | Retaining top-2 singular modes matches full Frobenius energy |
| Mean Similarity Aggregation (AvgSim) | 0.8737 ± 0.0232 | 0.7489 ± 0.0198 | Lacks quadratic penalty for mild cross-temperature drift |
| Maximum Similarity Aggregation (MaxSim) | 0.8724 ± 0.0232 | 0.7443 ± 0.0196 | Overly sensitive to a single spurious high-probability match |
| Anchor-Probe Entropy (Distribution Ent.) | 0.4491 ± 0.0147 | 0.4571 ± 0.0148 | Severe failure: approaches zero when \(W=0\), violating monotonicity |
| Non-Rephrased Control (Original query only) | 0.8018 ± 0.0211 | 0.7072 ± 0.0104 | Removing input perturbations degrades performance by 4.6–7.5% |
| Same-Input Control (Independent rephrases) | 0.8664 ± 0.0110 | 0.7453 ± 0.0087 | Averages independent rephrase runs, trailing mixed sampling |
| Matched-Budget Baseline Control (\(N=13\)) | 0.8346 ± 0.0170 (Deg) | 0.7247 ± 0.0095 (Deg) | Increasing baseline calls to 13 leaves BiG-SURE well ahead |
Risk-Coverage Performance (AURC)¶
In addition to abstention AUROC, selective prediction performance is assessed via Area Under the Risk-Coverage Curve (AURC, lower is better; mean ± standard deviation across models):
| Method | SVAMP AURC (↓) | Trivia-QA AURC (↓) | Operational Takeaway |
|---|---|---|---|
| DSE | 0.1097 ± 0.0441 | 0.2244 ± 0.0577 | Standard discrete semantic clustering entropy |
| SumEigV | 0.1169 ± 0.0487 | 0.2209 ± 0.0560 | Sum of degree-based adjacency eigenvalues |
| Deg | 0.1169 ± 0.0487 | 0.2209 ± 0.0562 | Negative trace of degree matrix |
| NumSet | 0.1104 ± 0.0439 | 0.2230 ± 0.0596 | Discretized semantic set count |
| LexSim | 0.1146 ± 0.0394 | 0.2126 ± 0.0574 | Lexical ROUGE-L surface similarity |
| KLE | 0.1212 ± 0.0398 | 0.2176 ± 0.0619 | Von Neumann entropy of semantic kernel |
| SNNE | 0.1017 ± 0.0391 | 0.2328 ± 0.0535 | Nearest-neighbor soft pairwise similarity |
| BiG-SURE (Ours) | 0.0839 ± 0.0328 | 0.1975 ± 0.0520 | Lowest selective risk across both benchmarks |
Key Findings¶
- Synergy of Cross-Temperature Dynamics and Equivalent Perturbations: Disabling meaning-preserving input transformations causes AUROC to plunge from 0.7533 to 0.7072 on Trivia-QA. Conversely, testing baselines with an equalized inference budget of 13 calls confirms that BiG-SURE's performance edge stems from its bipartite structural inductive bias rather than sample count.
- Spectral Concentration in the Dominant Mode: The Top-1 singular mode accounts for nearly the entire predictive utility (\(0.7527\) vs \(0.7533\)). When the model is confident, anchor-probe interactions collapse onto a single coherent rank-1 subspace; under uncertainty, semantic drift dissolves this dominant mode.
- Hyperparameter Robustness Across Wide Regimes: Performance remains virtually flat across anchor temperatures \(T_L \in [0.1, 0.4]\). For probes, moderate temperatures \(T_H \in [0.9, 1.2]\) provide the optimal exploration-noise trade-off, whereas excessive temperatures (\(T_H = 2.0\)) introduce degenerative lexical noise.
Highlights & Insights¶
- Frobenius-Spectral Equivalence for Ultra-Fast Inference: By exploiting the matrix identity equating the sum of squared singular values to the squared Frobenius norm, BiG-SURE computes rigorous spectral energy via simple elementwise squaring and summation, bypassing explicit SVD routines and achieving millisecond execution.
- Asymmetric Bipartite Topology Over Homogeneous Graphs: Breaking the convention of symmetric \(N \times N\) pairwise comparison, the anchor-probe paradigm provides an explicit reference baseline, cutting NLI backend inference requirements by over 70% while improving calibration fidelity.
- Modal-Agnostic Perturbation Compatibility: The framework accommodates diverse perturbation generators—from syntactic LLM rephrasers to spatial affine image transforms—allowing seamless extension across text, multilingual, and vision-language domains without altering the mathematical core.
Limitations & Future Work¶
- Vulnerability to Systematically Consistent False Beliefs: If a model stubbornly produces the exact same incorrect answer across both low-temperature greedy decoding and perturbed high-temperature probing, BiG-SURE will erroneously report high confidence due to high surface consistency.
- Sensitivity to NLI Backend Failure Modes: In specialized multilingual domains or complex arithmetic expressions, subtle semantic shifts (e.g., confusing "monthly" with "yearly" in Japanese) may be assigned falsely high entailment by the underlying NLI model, distorting the bi-adjacency matrix.
- Absence of Image-Grounded Visual Verification: For visual QA, the semantic similarity backend evaluates only text generation tokens without verifying whether entities are grounded in the visual evidence, occasionally assigning high certainty to visually ungrounded hallucinations.
Related Work & Insights¶
- vs Discrete Semantic Entropy (DSE, Farquhar et al., Nature 2024): DSE performs heuristic bi-directional NLI thresholding to group high-temperature responses into discrete clusters. BiG-SURE eliminates discrete clustering entirely, introducing stable low-temperature anchors and continuous spectral energy to yield an average +3.1% AUROC boost.
- vs Kernel Language Entropy (KLE, Nikitin et al., NeurIPS 2024): KLE computes the von Neumann entropy over an \(N \times N\) normalized kernel matrix, incurring \(\mathcal{O}(N^3)\) computational cost. BiG-SURE uses an asymmetric \(M \times N\) bipartite energy metric that is faster, bounded in \([0, 1]\), and less susceptible to fixed-temperature drift.
- vs Graph Uncertainty Metrics (Deg / SumEigv, Lin et al., TMLR 2024): Standard graph approaches calculate unnormalized node degrees or adjacency eigenvalues over homogeneous response networks. BiG-SURE formalizes a bipartite cross-temperature structure with proven axiomatic properties (identity, disjointness, monotonicity).
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Introduces the first cross-temperature bipartite graph and spectral energy formulation for black-box uncertainty estimation.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across 6 text LLMs, 2 multilingual models, and 3 VLMs across 7 diverse benchmarks with budget-matched controls.
- Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical formulations, clear motivation, elegant graphical illustrations, and exhaustive failure mode analyses.
- Value: ⭐⭐⭐⭐⭐ Unsupervised, clustering-free, and highly practical for deploying reliable abstention mechanisms in safety-critical black-box applications.