PaperlayerView exact revision on arXiv

Source-linked AI summary

BiG-SURE - Bipartite Graph for Semantic Uncertainty and Reliability Estimation of LLMs

Debarpan Bhattacharya, Malay Phadke, Sriram Ganapathy

arXiv:2608.30646v1cs.CLcs.AIcs.LG

TL;DR

Safety-critical deployment needs uncertainty estimation for black-box LLMs and VLMs, where logits and token probabilities are unavailable. BiG-SURE uses cross-temperature semantic agreement between low-temperature anchors and high-temperature probes, and it improves abstention AUROC over prior black-box estimators in most evaluated settings. The method is presented as simple, interpretable, practical, and unsupervised, but consistency can produce overconfidence on repeated incorrect answers and overlook visual grounding.

  • Problem

    Black-box LLM and VLM deployment lacks accessible logits and token probabilities, while mispredictions and hallucinations make reliable uncertainty estimation important in safety-critical settings.

  • Method

    BiG-SURE constructs an anchor–probe bipartite semantic-similarity graph from low-temperature anchors and high-temperature probes, using normalized squared spectral energy for confidence and its complement for uncertainty.

  • Results

    BiG-SURE achieves strong abstention AUROC across text-only, multilingual, and multimodal QA tasks, improving over prior black-box estimators in most evaluated settings.

  • Takeaways & Limitations

    The results suggest BiG-SURE is a simple, interpretable, practical, and unsupervised approach to black-box uncertainty estimation.

  • Takeaways & Limitations

    Consistency does not guarantee correctness: repeated semantically consistent errors can make SURE overconfident, and textual similarity does not assess visual grounding in visual QA.

Abstract

from arXiv · show

Reliable uncertainty estimation is a crucial requirement for deploying large language models (LLMs) and vision-language models (VLMs) in safety-critical settings, especially when the model parameters are not accessible (black-box). We propose BiG-SURE, an uncertainty estimator based on cross-temperature semantic agreement. The method samples low-temperature responses as stable semantic anchors and high-temperature responses as probes under meaning-preserving input transformations. It then constructs an anchor-probe Bipartite Graph (BiG) using NLI-based entailment scores and defines confidence through the normalized squared spectral energy of this matrix, with uncertainty given by its complement. This bipartite graph-based Semantic Uncertainty and Reliability Estimation (SURE) score measures whether high-temperature probes remain semantically aligned with the model's stable low-temperature belief or not. We evaluate BiG-SURE on text QA, multilingual QA, and multimodal QA tasks across multiple model families. In these experiments, BiG-SURE improves average abstention AUROC over prior black-box uncertainty estimators, while remaining simple, unsupervised, and applicable to black-box model settings.

1 Introduction

Safety-critical deployment requires reliable uncertainty estimates for black-box LLMs and VLMs, while existing methods infer uncertainty from fixed-temperature samples. BiG-SURE instead measures cross-temperature semantic agreement between stable anchors and diverse probes, improving abstention AUROC over prior estimators.

  • Black-box calibration and uncertainty estimation remain deployment bottlenecks because LLM mispredictions and hallucinations can cause substantial losses in finance, legal, and health settings.
  • Existing black-box approaches use semantic clustering, entropy, kernelized similarities, or response graphs, but sample responses at a fixed temperature.
  • BiG-SURE compares stable low-temperature anchors with high-temperature probes to capture semantic drift through a bipartite agreement graph.
  • SURE converts anchor–probe semantic agreement into normalized squared spectral-energy confidence, with uncertainty defined as its complement.
  • SURE improves abstention AUROC over prior black-box estimators across evaluated tasks, with Figure 1 reporting a substantial Trivia-QA improvement averaged over six LLMs.

2 Problem Statement

The problem is to estimate response uncertainty when model logits and token probabilities are inaccessible. The proposed setup uses low-temperature anchors and high-temperature probes, optionally generated from meaning-preserving input augmentations.

  • Black-box uncertainty estimation seeks an uncertainty score U(x; θ) for a generated response y without access to logits or token probabilities.
  • The method samples low-temperature anchor responses A and high-temperature probe responses H from the original input or semantically equivalent augmentations.
  • The objective is to estimate U(x; θ) from the cross-temperature response sets A and H.

3 Cross-temperature Spectral Energy

BiG-SURE represents semantic agreement between low- and high-temperature responses as a weighted bipartite graph and derives confidence from its normalized spectral energy. Its complement is an unsupervised uncertainty score whose value reflects cross-temperature semantic divergence.

  • Graph construction: The weighted bipartite graph G=(A,H,W) uses W_ij to represent semantic similarity between anchor a_i and probe h_j.
  • Spectral energy: SURE measures agreement spectral energy from the singular values of the anchor–probe similarity matrix W and relates that energy to the squared Frobenius norm.
  • Score definition: Normalized confidence lies between 0 and 1, while normalized uncertainty is defined as its complement and therefore also forms a bounded estimate.
  • Interpretation: Accurate predictions show semantically similar low- and high-temperature responses, whereas incorrect predictions show greater variation and higher normalized uncertainty.
  • Computation: The algorithm samples M low-temperature and N high-temperature responses, builds pairwise semantic-similarity edges, and computes uncertainty without ground-truth labels.
  • Properties: The score reaches zero under semantic identity and one under semantic disjointness, while increasing as semantically unique sequences increase in the prediction set.

4 Prior Works

Prior black-box uncertainty estimators include entropy-, similarity-, graph-, and distillation-based approaches, with newer work also targeting multimodal settings. BiG-SURE differs by using cross-temperature anchor–probe agreement without semantic clustering.

  • Prior black-box methods include semantic entropy, evidential semantic entropy, SPUQ, KLE, SNNE, graph-based, and distillation-based approaches.
  • Multimodal uncertainty estimation has been explored by methods including FESTA, TREA, Uncertainty-O, and UMPIRE.
  • Discrete Semantic Entropy clusters responses semantically before computing entropy, whereas BiG-SURE does not require semantic clustering.
  • Graph-based alternatives treat high-temperature outputs as graph nodes and derive uncertainty from measures such as NumSet, EigV, and Deg.

5 Experimental Setup

The experiments evaluate SURE across text-only, multilingual, and multimodal QA using temperature sampling and semantics-preserving input transformations. Uncertainty estimators are assessed by abstention AUROC against correctness labels.

  • Textual QA: Textual QA uses Trivia-QA and SVAMP with six LLMs spanning Llama, Qwen, and Gemma model families.
  • Multilingual QA: Multilingual QA uses SciQ in English, French, Japanese, and Mandarin with Aya-expanse-8b and Apertus-8B-Instruct-2509.
  • Multimodal QA: Multimodal QA uses OK-VQA with Pixtral-12B-2409, Llavav1.6-mistral-7b-hf, and Qwen3-VL-8B-Instruct.
  • Sampling: SURE generates M = 3 low-temperature anchors and N = 10 high-temperature probes from five equivalent input transformations, using TL = 0.1 and TH = 1.0.
  • Semantic similarity: NLI-based entailment probabilities provide anchor–probe edge weights, with fixed DeBERTa backends used across SURE and similarity-based baselines.
  • Evaluation: Abstention AUROC is computed from uncertainty scores and binary labels indicating whether greedy predictions match ground-truth answers.

6 Results

SURE separates reliable and unreliable predictions through cross-temperature semantic agreement and achieves the strongest average abstention AUROC in six of seven dataset/language groups. Gains span text-only, multilingual, and multimodal QA, with specific exceptions among language groups and model baselines.

  • Text-only QA: On TRIVIA-QA, SURE reaches 0.753 ± 0.017 versus Deg at 0.722 ± 0.007, while on SVAMP it reaches 0.877 ± 0.022 versus SNNE at 0.846 ± 0.018.
  • Text-only QA: SURE is best for five of six models on each text-only dataset, with Llama-70B favoring Deg on TRIVIA-QA and Qwen-72B favoring SumEigv on SVAMP.
  • Qualitative patterns: Figure 3 contrasts greedy predictions, low-temperature anchors, and high-temperature probes, marking ground-truth alignment in green and disagreement in red.
  • Multilingual QA: On multilingual SciQ, SURE leads English at 0.677 ± 0.015, Japanese at 0.685 ± 0.013, and Mandarin at 0.691 ± 0.012, while LexSim leads French.
  • Multimodal QA: On OKVQA, SURE achieves 0.752 ± 0.014 versus SNNE at 0.735 ± 0.016 and is best for all three evaluated VLMs.
  • Overall results: SURE achieves the best average AUROC in six of seven groups: TRIVIA-QA, SVAMP, SCIQ en, SCIQ ja, SCIQ zh, and OKVQA.

7 Discussion

The discussion finds that SURE’s useful signal is concentrated in cross-temperature semantic agreement, with mixed equivalent-input probes and moderate probe temperatures improving uncertainty estimation. Performance is more sensitive to probe count than anchor count, while computational cost remains manageable.

  • Spectral mode analysis: Leading singular modes closely match the full SURE score, indicating that useful agreement energy concentrates in the dominant anchor mode.Certain models align probes with the dominant anchor semantics, whereas uncertain models weaken that mode through semantic drift.
  • Effect of input augmentations: Mixed-rephrased probes achieve the best average performance on TriviaQA and SVAMP, while input augmentation improves over the non-rephrased variant.The mixed setup combines five equivalent input augmentations with two high-temperature responses from each.
  • Dissecting cross-temperature agreement: Low-T performs poorly and High-T remains weaker than SURE, supporting stable low-temperature anchors paired with high-temperature probes.Low-temperature generations can be too stable to reveal uncertainty, while high-temperature sampling exposes semantic variability.
  • Temperature sensitivity: Performance remains stable for TL ∈{0.1, 0.2, 0.3, 0.4}, generally improves as TH approaches 0.9-1.0, and declines at higher temperatures.The chosen settings, TL = 0.1 and TH = 1.0, are used across models and datasets without dataset-specific tuning.
  • Sample sensitivity analysis: Increasing probe samples from 5 to 10 gives the largest improvement, with further increases yielding marginal gains and anchor-count increases having little effect.These results suggest that a small number of stable low-temperature anchors is sufficient.
  • Computational complexity: SURE’s uncertainty computation costs O(MN Csem), compared with O(N^2 Csem) for most pairwise baselines and an additional O(N^3) for KLE.Under an equalized inference budget of N = 13, SURE still outperforms prior baselines on text-QA tasks.

8 Conclusion

The conclusion presents BiG-SURE as a black-box uncertainty estimator based on cross-temperature bipartite semantic agreement. Across evaluated QA settings, it improves over prior black-box estimators and is described as simple, interpretable, and practical for reliability-aware deployment.

  • Method: BiG-SURE uses low-temperature anchors and high-temperature probes to compute uncertainty as the complement of normalized squared spectral energy.The method constructs an anchor–probe semantic similarity graph from these responses.
  • Conclusion: BiG-SURE achieves strong abstention AUROC across text-only, multilingual, and multimodal QA, improving over prior black-box estimators in most evaluated settings.The conclusion also identifies cross-temperature comparison and equivalent-input augmentation as major contributors to performance.

9 Limitations

BiG-SURE’s limitations concern its semantic-similarity backend, consistency-based confidence, visual grounding, limited human validation, and evaluation scope. These constraints are especially relevant beyond the tested QA settings and when semantic alignment does not ensure correctness.

  • Backend dependence: The entailment-based semantic-similarity backend may misrepresent uncertainty when semantic equivalence is difficult to capture, especially across languages or visual responses.SURE does not train or fine-tune the similarity model, so backend quality remains a central dependency.
  • Correctness: Consistent sampling can produce overconfidence when the model repeatedly gives the same incorrect answer.This failure can occur even with a perfect semantic-similarity backend because consistency does not guarantee correctness.
  • Visual grounding: For visual QA, SURE evaluates generated text without examining the image, so it may miss failures of visual grounding.The current method can assign high confidence to a visually overlooked answer that is textually consistent.
  • Subjective assessment: Human evaluations of paraphrases and multilingual correctness labels are limited in scale and provide sanity checks rather than comprehensive validation.Systematic human evaluation of the NLI-based semantic-similarity backend remains future work.
  • Evaluation scope: Experiments cover QA benchmarks but do not fully represent long-form generation, summarization, dialogue, planning, or code synthesis.Extending cross-temperature bipartite agreement to these broader tasks remains future work.

A.1 Theoretical properties of SURE as an uncertainty estimator

Theoretical results characterize normalized SURE uncertainty through cross-temperature semantic agreement. Perfect agreement yields zero uncertainty, while weakened or absent agreement increases uncertainty and can correspond to greater semantic diversity among probes.

  • Boundary cases: Perfect semantic agreement across all anchor–probe pairs yields normalized uncertainty 0, while complete semantic disjointness yields normalized uncertainty 1.The all-ones and all-zeros similarity matrices represent these two limiting cases.
  • Monotonicity: Elementwise weakening of anchor–probe similarity monotonically increases normalized uncertainty.If W′ is elementwise no greater than W, then Unorm(W′; θ) ≥ Unorm(W; θ).
  • Characterization: Proposition A.2 establishes that normalized uncertainty approaches 0 if and only if all sampling responses are semantically similar.The result formalizes the interpretation of SURE as a semantic-consistency estimator.
  • Cluster structure: As similarity decreases, the number of feasible semantic clusters increases, while under uniform cluster probabilities E[CN(W)] approaches N.The expected observed-cluster count is monotonic in the number of feasible clusters.
  • Semantic diversity: Increasing semantic uniqueness among high-temperature answers increases uncertainty and the expected number of observed semantic clusters.This links probe diversity with weaker cross-temperature agreement under fixed numbers of anchor and probe responses.

A.2 Full strawman-baseline analysis

The analysis compares BiG-SURE with direct aggregation and input-variation alternatives, then examines inference budget, temperature sensitivity, selective prediction, and failure modes.

  • Direct aggregation baselines: BiG-SURE and AvgSqSim match exactly, while AvgSim, MaxSim, and anchor–probe entropy are weaker on average.The equality follows from the normalized spectral-energy and squared Frobenius-norm identity.
  • Input-variation strategies: Mixed-Rephrased is the default probe construction, using five equivalent augmentations and two high-temperature responses per augmentation.This forms one mixed probe pool of 10 responses while keeping low-temperature anchors sampled from the original input.
  • Input-variation strategies: Input augmentation is the main contributor: Same-Input and Mixed-Rephrased substantially outperform Non-Rephrased, with Mixed-Rephrased adding a modest consistent benefit.Using only rephrasings generally improves methods but incurs additional rephrasing cost.
  • Matched inference-budget analysis: SURE retains its performance advantage when baselines receive 13 samples, indicating the gain comes from cross-temperature anchor–probe construction rather than sampling alone.The default configuration uses 13 total generations per input, compared with commonly evaluated baselines using 10.
  • Temperature sensitivity: AUROC is relatively stable across low-temperature anchors, whereas very high probe temperatures such as TH = 2.0 substantially degrade performance.The paper uses TL = 0.1 and TH = 1.0 without tuning; TH = 1.0 and TH = 1.2 perform best in the sensitivity analysis.
  • Failure analysis: Response-consistency uncertainty can fail when incorrect answers remain semantically consistent or when NLI incorrectly treats non-equivalent answers as equivalent.Visual grounding is not checked by the textual semantic backend, and stronger multilingual and numerical entailment models are suggested for backend errors.
Loading 2608.30646v1…