1 Introduction↩︎

1.1 Uncertainty Quantification for LLMs↩︎

Large Language Models (LLMs) have demonstrated remarkable capabilities across diverse natural language processing tasks, from question answering and text generation to complex reasoning and code synthesis [1], enabling their widespread adoption across numerous domains including software development [2], [3], autonomous driving [4] and education [5]. However, despite their impressive performance, LLMs exhibit a critical limitation: they produce responses with varying degrees of uncertainty while maintaining seemingly equal confidence in their outputs. This uncertainty manifests in multiple forms, including factual inaccuracies [6], inconsistent reasoning patterns [7] and hallucinated content [8], [9], where successive generated responses can be mutually contradictory or semantically and logically unrelated. Reliable uncertainty estimates enable more informed decision-making by both human users and downstream systems, while providing useful insights for model calibration and trustworthiness assessment [9]. Moreover, uncertainty quantification (UQ) serves as a foundational component for effective hallucination detection [10], [11], enabling systems to flag potentially unreliable outputs before they propagate through application pipelines.

Current state-of-the-art approaches to UQ in LLMs can be broadly categorized into several paradigms. Token-level methods [12], [13] focus on the distributional confidence of individual token predictions, typically leveraging softmax probabilities or token-level entropy measures. Sequence-level approaches [14], [15] aggregate token-wise uncertainties or employ ensemble methods to assess overall response reliability. Two key semantic-level measures are Semantic Entropy (SE) [16] and Kernel Language Entropy (KLE) [17]. Given an input \(x\), sampled answers are grouped into \(k\) paraphrase-equivalent semantic clusters \(\mathcal{C}=\{c_1,\dots,c_k\}\), and each cluster receives probability mass \(p(c_j\mid x)\) by summing the probabilities of its members. SE then computes \(\mathtt{SE}(x)= -\sum_{j=1}^{k} p(c_j\mid x)\log p(c_j\mid x).\)

KLE replaces semantic grouping with a kernel \(K\in\mathbb{R}^{k\times k}\) over clusters and measures uncertainty via the von Neumann entropy \(\mathtt{KLE}(x)= -\mathrm{Tr}[K\log K] = -\sum_{i=1}^{k}\lambda_i\log \lambda_i,\) where \(\{\lambda_i\}\) are eigenvalues of a unit-trace positive semidefinite \(K\), typically introducing additional kernel hyperparameters.

1.1.0.1 Limitation of Semantic Similarity.

Despite their advances, semantic UQ methods judge only whether answers are paraphrase-equivalent, ignoring logical relationships among non-identical responses. For open-ended questions, multiple correct answers may exist that are not paraphrases yet are logically related; some entail others, some are compatible refinements, and some are genuinely mutually exclusive. SE assigns high entropy because the model generates diverse valid answers, conflating diversity with uncertainty. Figure 1 illustrates this limitation. Naive Entropy (NE)³ treats raw strings as independent categories, inflating uncertainty under superficial variation. SE mitigates paraphrastic variation but fails when answers are logically nested. Consider the question “When was X reflected upon?”: the answer “in the 1920s” logically implies “in the early 20th century”. If we treat these as separate clusters, we double-count probability mass — the precise failure mode our method addresses.

1.2 Our Logical Graph-Based Uncertainty Framework↩︎

We propose a logical graph-based uncertainty framework with two quantities: Implication Graph Entropy (IGE) and Logical Graph Uncertainty (LGU). We construct an Implication Graph (ImG) whose directed edges encode logical implication relations among candidate answers under a shared truth-conditional standard (i.e., within the question-induced hypothesis space). Adopting graph-entropy principles as a measure of structural complexity [19], we aggregate probability mass along implication chains, pushing mass from more general statements toward more specific refinements, and compute entropy over the resulting distribution on logically maximal, non-redundant hypotheses (roots). Because reachability sets may overlap, root scores are normalized to form a valid probability distribution. IGE thus measures how probability mass is distributed over distinct high-level hypotheses, independent of their mutual consistency.

On top of ImG, we build an Incompatible Graph (InG) over the maximal (root) hypotheses and define LGU by penalizing dense patterns of mutual inconsistency. Unlike implication-based aggregation, LGU asks: how much probability mass is spread over hypotheses that cannot simultaneously be true? This distinction is illustrated in Figure 1: a model may commit to a coarse “safe” temporal statement (e.g., “the event occurred in the 1920’s”) while distributing probability mass over mutually exclusive fine-grained timelines (e.g., 1920 vs. vs.). Each candidate year remains internally coherent and is implied by the coarse statement, so IGE can stay low; by contrast, LGU becomes high when these roots form a densely incompatible set, exposing epistemic conflict that NE and SE may miss.

To quantify incompatibility, we model InG as a directed graph and define the incompatibility score InS using graph-density indices: (i) edge density (and a weighted variant), a normalized sparsity measure in network analysis [20], [21]; (ii) average in-/out-degree, a scale-aware statistic capturing how broadly incompatibility is distributed [20]; and (iii) the Estrada index, a walk-based spectral functional linked to matrix-exponential centrality and communicability [22]–[24]. We conduct comparative experiments across all three indices. Edge density yields a size-normalized score in \([0,1]\), delivers strong Area Under the Receiver Operating Characteristic curve (AUROC; \(\uparrow\)) overall, and achieves the lowest Expected Calibration Error (ECE; \(\downarrow\)) in our experiments; average in-/out-degree can be particularly effective on SQuAD in AUROC, with a range that depends on the number of candidate answers, taking values in \([0,n\!-\!1]\) for \(n\) candidates.

A key distinction from SE is that LGU does not merely modify the entropy functional. Rather, it redefines the underlying random variable—the objects over which probability mass is assigned—thereby changing the hypothesis space on which uncertainty is computed. SE assigns mass to flat, mutually exclusive semantic clusters; LGU reassigns mass to logically maximal hypotheses (roots) obtained by propagating probability along implication chains, and further modulates uncertainty by the density of mutual incompatibility among them.

Table 1 compares LGU with NE, SE, and KLE across five features. LGU uniquely incorporates explicit logical relations (implication and incompatibility) without extra hyperparameters, maintaining \(\mathcal{O}(n^2)\) complexity against KLE’s \(\mathcal{O}(n^3)\). Its score range \([0,(1+\mathtt{InS})\log n]\) is wider than that of competing methods by a margin determined by \(\mathtt{InS}\), providing finer granularity to separate benign diversity from genuine conflict.

1.2.0.1 Evaluation.

We validate LGU on four QA benchmarks [25]–[28] for hallucination discrimination and selective prediction. Across datasets, LGU consistently outperforms semantic- and token-level baselines in both ranking and calibration. Notably, it improves upon SE by up to \(\mathbf{+7.1\%}\) AUROC and \(\mathbf{+3.5\%}\) AUARC, and achieves substantially lower ECE than KLE. Further experimental details are provided in Section 3.

To summarize, our contributions towards more precise UQ in LLMs are as follows:

2 Logical Graph Measures↩︎

We model the set of LLM answers as logical graphs: answers are grouped into equivalence classes (clusters), and edges encode implication and incompatibility among these clusters. Based on this structure, we define two uncertainty measures. Implication Graph Entropy (IGE) aggregates probability mass along implication chains and computes entropy over logically maximal clusters (roots). Logical Graph Uncertainty (LGU) further scales IGE by a graph-density–style incompatibility score among these roots, penalizing mutually exclusive high-level hypotheses more strongly than compatible semantic diversity.

2.1 Graph Preliminaries↩︎

A directed graph (digraph) is an ordered pair \(G=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) is a set of vertices and \(\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}\) is a set of ordered pairs called directed edges. An empty graph has \(\mathcal{E}=\emptyset\). A self-loop is an edge \((v,v)\).

For a vertex \(v\in\mathcal{V}\), its in-neighborhood and out-neighborhood are \(N^{-}(v)=\{u\in\mathcal{V}:(u,v)\in\mathcal{E}\}\) and \(N^{+}(v)=\{u\in\mathcal{V}:(v,u)\in\mathcal{E}\}\), respectively. The in-degree and out-degree of \(v\) are \(d^{-}(v)= |N^{-}(v)|\) and \(d^{+}(v)= |N^{+}(v)|.\)

A directed cycle is a sequence of distinct vertices \((v_0,\dots,v_{k-1})\) such that \((v_i,v_{i+1})\in \mathcal{E}\) for \(i=0,\dots,k-2\) and \((v_{k-1},v_0)\in \mathcal{E}\). A directed graph is a directed acyclic graph (DAG) if it has no directed cycles. A vertex \(r\in\mathcal{V}\) is a root if no edge ends at \(r\), i.e., \(d^{-}(r)=0\).

Throughout, all graphs are directed graphs without self-loops.

2.2 Logical Graphs↩︎

This subsection defines two graphs over semantic clusters: the Implication Graph (ImG) and the Incompatible Graph (InG).

2.2.0.1 Implication Graph.

Given a query \(x\) and an LLM \(L\), we sample multiple candidate answers. Two answers \(a,b\) are (logically) equivalent w.r.t.\(x\) if, in every possible situation compatible with \(x\), (i) \(a\) true implies \(b\) true and (ii) \(b\) true implies \(a\) true. We write \(a\equiv b\). Each equivalence class forms an equivalent cluster \(c\). The Implication Graph (ImG) is defined as \(\mathrm{ImG}(x/L)=(\mathcal{V},\mathcal{E}),\) where \(\mathcal{V}=\{\, c_i \mid c_i \text{ is an equivalent cluster} \,\},\) and for \(c_s,c_t\in\mathcal{V}\), \((c_s,c_t)\in\mathcal{E} \iff c_s \Rightarrow c_t \;\text{w.r.t.\;} x,\) i.e., whenever any (equivalently, every) answer in \(c_s\) is true, any (equivalently, every) answer in \(c_t\) is also true, in all situations compatible with \(x\).

These properties serve a dual purpose: they establish the theoretical foundation of ImG as a DAG (Theorem 3), and they provide verifiable criteria for assessing whether a chosen relation extraction method—such as an NLI model—produces predictions consistent with our framework’s assumptions. In particular, transitivity can be empirically checked by verifying that \(A\Rightarrow B\) and \(B\Rightarrow C\) implies \(A\Rightarrow C\) on sampled answer triples.

Implication is antisymmetric at the level of equivalence classes: if two clusters imply each other, they are equivalent and thus identified as one vertex. Suppressing self-loops yields the following.

Let \(\mathcal{R}(\mathrm{ImG}(x/L))\) denote the set of roots of \(\mathrm{ImG}(x/L)\). By Remark 1, \(\mathcal{R}(\mathrm{ImG}(x/L))\neq\emptyset\). This structural guarantee ensures that the root set \(\mathcal{R}(\mathrm{ImG}(x/L))\) is always non-empty and well-defined, which is a necessary precondition for the aggregated distribution in IGE to be valid.

2.2.0.2 Incompatible Graph.

For a query \(x\), two answers \(a\) and \(b\) are compatible w.r.t.\(x\) if there exists at least one situation consistent with \(x\) in which both \(a\) and \(b\) are simultaneously true. Conversely, \(a\) and \(b\) are incompatible w.r.t.\(x\) if no such situation exists. The Incompatible Graph (InG) is defined as \(\mathrm{InG}(x/L)=(\mathcal{V},\mathcal{E}), \mathcal{V}= \mathcal{R}(\mathrm{ImG}(x/L)).\) We encode incompatibility as a symmetric relation on roots; concretely, whenever two roots are incompatible, we include both directed edges \((c_s,c_t)\) and \((c_t,c_s)\) in \(\mathcal{E}\). Formally, \(\mathcal{E} = \Bigl\{ (c_s,c_t) \in \mathcal{V} \times \mathcal{V} \;\Bigm|\; c_s \neq c_t, \;\forall a \in c_s,\;\forall b \in c_t, \;a \text{ and } b \text{ are incompatible w.r.t.\;} x \Bigr\}.\) Since all answers within a cluster are logically equivalent by construction, incompatibility between clusters is well-defined (equivalently, it suffices to check any representatives).

Analogously, symmetry of the incompatibility relation provides an empirical sanity check: a reliable relation extraction method should predict incompatibility consistently in both directions for any answer pair. Non-reflexivity and non-transitivity, by contrast, are structural properties that hold by definition and require no empirical verification.

2.3 Graph-Based Uncertainty↩︎

Let \(C=\{c_1,\dots,c_t\}\) be the equivalent clusters induced by \(L\) for query \(x\), with probabilities \(P=\{p_1,\dots,p_t\}\).

2.3.0.1 Implication Graph Entropy (IGE).

Let \(\mathcal{R}(\mathrm{ImG}(x/L))=\{r_1,\dots,r_k\}\). For each root \(r_i\), define the aggregated mass \(p'(r_i)= \sum_{c_j\in \mathrm{Reach}(r_i)} p_j,\) where \(\mathrm{Reach}(r_i)\) is the set of vertices reachable from \(r_i\) (including \(r_i\)). Since reachability sets may overlap, we normalize \(p(r_i)= \frac{p'(r_i)}{\sum_{j=1}^{k} p'(r_j)}.\)

The Implication Graph Entropy is \(\mathtt{IGE}(x/L)= -\sum_{i=1}^{k} p(r_i)\log p(r_i).\)

2.3.0.2 Discrete IGE (DIGE).

In black-box settings, we sample \(n\) outputs \(a_1,\dots,a_n\) and estimate cluster probabilities by empirical frequencies; \(\mathtt{DIGE}(x/L)\) is computed by substituting these estimates into the definition of \(\mathtt{IGE}(x/L)\).

2.3.0.3 Incompatible Score.

Let \(\mathrm{InG}(x/L)=(\mathcal{V},\mathcal{E})\) be the incompatibility graph (InG), a directed graph with no self-loops. Depending on the data type, \(\mathcal{E}\) can be (i) binary, recording whether two root hypotheses are incompatible, or (ii) weighted, equipped with a weight function \(w:\mathcal{E}\to[0,1]\) where each edge \((u,v)\in\mathcal{E}\) carries a normalized weight \(w_{uv}\) capturing the strength/probability of incompatibility. We view the incompatible score as a family of graph-density metrics that summarize how pervasive mutual inconsistency is among the roots, and we ablate several plausible instantiations:

• (Weighted) Edge Density. Since a loop-free directed graph on \(|\mathcal{V}|\) nodes has at most \(|\mathcal{V}|(|\mathcal{V}|-1)\) edges, we define the directed edge density \[\mathtt{InS}_{\mathrm{dens}}(x/L)= \begin{cases} \displaystyle \frac{|\mathcal{E}|}{|\mathcal{V}|(|\mathcal{V}|-1)}, & |\mathcal{V}|\ge 2,\\[6pt] 0, & |\mathcal{V}|\le 1. \end{cases}\] This yields \(\mathtt{InS}_{\mathrm{dens}}(x/L)\in[0,1]\) and is directly comparable across queries with different numbers of roots. When edge weights \(w_{uv}\in[0,1]\) are available, we replace the edge count with total weight.

• Average In-/Out-Degree. Define the average in- and out-degree over roots as

  \(\mathtt{InS}_{\mathrm{in}}(x/L) = \frac{1}{|\mathcal{V}|}\sum_{u\in\mathcal{V}} d^{-}(u),\) and \(\mathtt{InS}_{\mathrm{out}}(x/L) = \frac{1}{|\mathcal{V}|}\sum_{u\in\mathcal{V}} d^{+}(u).\) For directed graphs, \(\sum_{u} d^{-}(u)=\sum_{u} d^{+}(u)=|\mathcal{E}|\), hence \(\mathtt{InS}_{\mathrm{in}}(x/L)=\mathtt{InS}_{\mathrm{out}}(x/L)=|\mathcal{E}|/|\mathcal{V}|\).

• Estrada Index. To capture global (spectral) connectivity/complexity beyond local edges, we consider the Estrada index of the incompatibility graph. Let \(A\) be the adjacency matrix of \(\mathrm{InG}(x/L)\). Let \(\{\lambda_i\}_{i=1}^{|\mathcal{V}|}\) be the eigenvalues of \(A\) (the adjacency spectrum). The Estrada index is defined as \(\mathtt{EE}(\mathrm{InG}(x/L))= \sum_{i=1}^{|\mathcal{V}|} e^{\lambda_i}.\) We use \(\mathtt{InS}_{\mathrm{EE}}(x/L)= \mathtt{EE}(\mathrm{InG}(x/L)).\)

2.3.0.4 Logical Graph Uncertainty (LGU).

We define \(\mathtt{LGU}(x/L)= \bigl(1+\mathtt{InS}(x/L)\bigr)\,\mathtt{IGE}(x/L).\)

LGU modulates implication-based uncertainty by incompatibility among logically maximal hypotheses. The following results hold for the instantiations of \(\mathtt{InS}\) considered in this paper (i.e., edge density, weighted density, average degree, and Estrada index).

Theorem 6 establishes the attainable range of \(\mathtt{LGU}(x/L)\) and provides a precise graph-theoretic characterization of the configurations that realize its extrema. The upper bound \(\mathtt{LGU}(x/L)\le (1+\mathtt{InS}(x/L))\log |\mathcal{V}(\mathrm{ImG}(x/L))|\) makes explicit the multiplicative contribution of the incompatibility factor \(\mathtt{InS}\), and the accompanying equality conditions delineate the maximally uncertain regime, namely: a uniform distribution over equivalence classes, an empty implication subgraph (so that \(|\mathcal{R}(\mathrm{ImG}(x/L))|=|\mathcal{V}(\mathrm{ImG}(x/L))|\)), and a complete incompatibility subgraph on the roots. In contrast, the lower bound \(\mathtt{LGU}(x/L)\ge 0\) is achieved exactly when the root set collapses to a singleton, \(|\mathcal{R}(\mathrm{ImG}(x/L))|=1\), corresponding to a degenerate case in which all probability mass concentrates on a single maximal hypothesis. In practice, this bounded range facilitates calibration: since the maximum value \((1+\mathtt{InS})\log|\mathcal{V}(\mathrm{ImG}(x/L))|\) is determined entirely by the graph structure given a fixed \(\mathtt{InS}\), uncertainty scores can be normalized in a principled way for ECE evaluation. Full proof is in Appendix 6.1.1.

We next analyze the computational cost of computing \(\mathtt{LGU}(x/L)\) from \(n\) sampled candidate answers.

Full proof is in Appendix 6.1.2.

3 Experiments↩︎

We systematically validate our method’s LLM generation uncertainty estimation performance across diverse QA benchmarks and mainstream LLMs. All details of the following experimental section can be found in Appendix 7.1.

3.0.0.1 Datasets.

To comprehensively evaluate our method, we conduct experiments across five question-answering datasets spanning three diverse categories. For General Knowledge, we utilize TriviaQA [25] and SQuAD [26]; for Specialized Domains, we employ BioASQ [27] within the biomedical field; and for Search Queries, we use Natural Questions (NQ) [28] to represent real-world user search behavior.

r0.6

3.0.0.2 Models.

We evaluate a range of modern language models, including Llama [29], Falcon [30], Mistral [31], Qwen [32], and Gemma [33]. Additionally, we use DeBERTa-Large-MNLI [34] as our Natural Language Inference (NLI) model to construct logical graphs and semantic clusters. To assess the correctness of model generations, we employ GPT-3.5 [35] as the reference judge.

3.0.0.3 Baselines.

We evaluate against three baseline categories: semantic methods, including Semantic Entropy [16], [18] and Kernel Language Entropy (KLE) [17]; token-level metrics, comprising Maximum Sequence Probability (MSP), Perplexity (PPL) [36], and \(\text{Avg}/\text{Max}(-\log p)\) [37]; and a supervised Embedding Regression baseline [14]. Please refer to Appendix 7.1 for exact baseline formulations and implementation details.

3.0.0.4 Evaluation Metrics.

We evaluate performance using three standard metrics: discrimination via AUROC [18], practical utility for selective prediction via AUARC [38], and calibration reliability via Expected Calibration Error (ECE) [39]. Appendix 7.4.1 confirms our evaluation is robust to normalization protocols, where LGU consistently emerges as the best-calibrated method under both theoretical and empirical bounds.

3.1 Results↩︎

Our empirical evaluation demonstrates that LGU consistently yields superior discriminative power, robust cross-model generalization, and reliable calibration compared to existing baselines. All detailed results are provided in Appendix 7.2.

3.1.0.1 Quantitative Superiority.

As detailed in Table ¿tbl:tab:falcon95results?, LGU demonstrates exceptional discriminative capability and reliable calibration on the Falcon-7b-instruct model. It achieves the state-of-the-art results in both AUROC and AUARC across all four evaluated datasets (Trivia QA, SQuAD, BioASQ, and NQ), consistently outperforming strong semantic-level baselines such as Semantic Entropy (SE) and Kernel Language Entropy (KLE). For instance, on the NQ dataset, LGU improves the AUROC to \(0.752\) and the AUARC to \(0.533\).

3.1.0.2 Cross-Model Robustness and Stability.

To ensure that our method’s performance is not an artifact of a specific model architecture, we comprehensively evaluate its stability across six diverse LLM families. Figure 2 visualizes the rank-based performance of each uncertainty method on the SQuAD dataset via radar charts, where a larger shaded area corresponds to a higher and more consistent relative ranking. LGU (depicted by the blue area) encompasses the outermost perimeter in both the AUROC and AUARC plots, confirming its universally robust discriminative power regardless of the underlying model scale (ranging from 7B to 13B) or architecture (including Llama, Mistral, Gemma, and Falcon).

3.1.0.3 Superior Calibration of LGU.

To illustrate the calibration behavior in detail, Figure 3 (a) uses Falcon-7b on the SQuAD dataset as a representative example. The reliability diagram shows that LGU (red curve) aligns most closely with the perfect calibration line, indicating that its predicted confidence scores accurately reflect true correctness across all confidence intervals. Quantitatively, LGU achieves the lowest Expected Calibration Error (ECE) of 0.071, outperforming NE (0.087), KLE (0.270), and SE (0.206). These results verify that LGU delivers more reliable uncertainty estimation than baseline methods.

3.2 Ablation Study↩︎

3.2.0.1 Prevalence of Logical Structure Amplifies LGU’s Advantage.

To investigate the source of LGU’s performance improvement over SE, we analyze the relationship between the Non-empty ImG Rate and the performance gain across data subsets. First, we statistically analyze the non-empty ImG rates across various model-dataset pairs, and the results are presented in Table 2. Further correlation analysis is visualized in Figure 3 (b): the x-axis denotes the proportion of samples whose constructed ImG contains implication edges, and the y-axis represents the AUROC improvement of LGU over SE. The upward regression trend together with a Pearson correlation coefficient of 0.572 demonstrates a moderate-to-strong positive correlation between the two variables.

Specifically, in settings with a low graph construction rate (\(<\)​0.5), the performance gap is negligible, suggesting LGU behaves similarly to SE when logical relations are sparse. In contrast, when the construction rate is high (\(>\)​0.7), LGU’s advantage becomes pronounced, with AUROC gains up to 0.07. These findings confirm that LGU is particularly effective in scenarios rich in logical entailment, effectively capitalizing on the structural information that SE ignores.

3.2.0.2 Role of Incompatibility in Uncertainty Quantification.

To rigorously validate the architectural choices of our framework, we provide a comprehensive ablation study in Appendix 7.3. By comparing LGU against reduced baselines (e.g., IGE), we demonstrate that modeling implication alone is insufficient. The study confirms that constructing the InG with an Edge Density score provides the necessary signal to identify conflicting hallucinations, empirically justifying our default configuration.

4 Related Work↩︎

4.0.0.1 Token- and Semantic-Level UQ.

Early UQ methods for LLMs derive sequence-Level confidence from token probabilities via metrics such as average log-probability, perplexity, or token entropy [14], [40], [41]. These approaches operate at the lexical level and conflate surface variation with genuine uncertainty [16], and token-level calibration is known to degrade under RLHF fine-tuning [13]. Semantic-level methods address lexical sensitivity by clustering sampled answers into meaning-equivalent groups: SE [16], [18] computes entropy over NLI-derived equivalence classes, substantially outperforming token-level baselines on open-ended QA, and KLE [17] extends this via kernels that capture graded similarity between clusters at the cost of additional hyperparameters. Other approaches incorporate logit-based scoring [42] or self-evaluation prompts [13], though the latter tend to be overconfident and generally underperform token-based methods in uncertainty alignment [43]. In contrast to all of these methods, LGU explicitly models implication and incompatibility among generated answers, moving beyond flat semantic clustering toward a structured logical hypothesis space.

4.0.0.2 Graph-Structured Representations and Long-Form UQ.

Structured relational representations have been widely used across causal reasoning [44], reliability engineering [45], graph entropy [19], and network analysis [46]. In LLM UQ, recent work moves beyond semantic clustering toward explicit relational structures: [47] build a response–claim bipartite graph and estimate uncertainty via centrality measures such as degree and PageRank, while [48] define structural entropy over directed semantic dependency graphs. These methods share the graph-based intuition with our work, but neither models truth-conditional implication or mutual incompatibility among hypotheses as LGU does. LUQ [49] aggregates claim-level entailment consistency across sampled responses, while LoGU [50] further distinguishes supported, unsupported, and contradicted claims to produce finer-grained uncertainty signals over extended outputs.

5 Discussion↩︎

This work addresses a fundamental limitation in current uncertainty quantification methods for large language models: the inability to capture the logical structure that underlies model responses. In this paper, we propose a logical-graph-based framework centered on two complementary quantities: Implication Graph Entropy (IGE), which aggregates probability mass along logical entailment chains in an Implication Graph (ImG), and Logical Graph Uncertainty (LGU), which further penalizes dense patterns of mutual incompatibility among the ImG roots via an InG. Across multiple benchmarks and model families, LGU yields substantially improved identification of unreliable outputs—especially in open-ended settings where correct answers are logically rich rather than trivially repetitive—thereby promoting logical coherence to a first-class role alongside semantic equivalence in the uncertainty quantification landscape.

5.0.0.1 Limitation.

First, the framework only supports implication and pairwise incompatibility, lacking modeling for richer logical relations such as causality, temporal order, and defeasible inference. Second, LGU is constrained by the inherent flaws of the underlying NLI model, whose judgment errors will propagate to logical graphs and uncertainty scores. Third, building logical graphs is computationally expensive for long-form and multi-step reasoning, calling for hierarchical or approximate inference solutions. Lastly, evaluations are limited to short-form QA; further validation on dialogue, code generation and other domains is still required.

5.0.0.2 Broader Impact Statement.

This paper proposes a quantitative method for estimating uncertainty in large language model outputs. The primary goal of this work is to advance the understanding and evaluation of model uncertainty within the machine learning research community.

6 Algorithms of Logical Graph Uncertainty↩︎

6.1 Proofs↩︎

6.1.1 Proof of Theorem 6↩︎

6.1.2 Proof of Theorem 7↩︎

6.2 Algorithms↩︎

We now present concrete algorithms for computing our graph-based uncertainty measures. Given a query \(x\) and model \(L\), the pipeline has three stages: (i) group raw answers into equivalent clusters; (ii) construct the Implication Graph (ImG) and compute Implication Graph Entropy (IGE); (iii) build the Incompatibility Graph (InG) over ImG roots, compute an incompatibility score \(\mathtt{InS}(x/L)\), and combine it with IGE to obtain LGU.

6.2.0.1 Equivalent Clustering.

Before constructing logical graphs, we group generated answers into clusters representing the same semantic proposition (Algorithm 4). The inputs are sampled answers \(a_1,\ldots,a_n\) with associated probability masses \((p_1,\ldots,p_n)\), where in the white-box setting \(p_i\) is the sequence-level probability of answer \(a_i\) derived by aggregating token-level log-probabilities, and in the black-box setting \(a_i\) are i.i.d.samples and \(p_i\) are frequencies.

The output is a set (list) of clusters \(\mathcal{C}\) and corresponding masses \(\mathrm{P}\). In later steps we treat \(\mathrm{P}\) as a map \(\mathrm{P}(c)\) assigning each cluster \(c\in\mathcal{C}\) its exact or empirical probability mass.

6.2.0.2 Implication Graph Entropy (IGE).

Given clusters and their masses, Algorithm 5 constructs the ImG by adding an edge for each logical implication between clusters, aggregates probability mass along implication chains into roots, and computes Shannon entropy over the induced distribution on roots.

6.2.0.3 Logical Graph Uncertainty (LGU).

LGU augments implication-based aggregation with an explicit penalty for conflicts between roots. Algorithm 7 first constructs the InG over roots, then computes an incompatibility score \(\mathtt{InS}(x/L)\) using a pluggable graph metric (Algorithm 6), and finally returns \(\mathtt{LGU} = (1+\mathtt{InS})\cdot\mathtt{IGE}\).

Together, Algorithms 4–7 specify an end-to-end, implementation-ready pipeline for our graph-based uncertainty measures. The same procedures apply in both white-box and black-box regimes, differing only in how the answer masses \(\mathrm{P}\) are obtained (model-derived probabilities vs.empirical frequencies). Under the pairwise-check implementation described in the main text, the overall running time is \(\mathcal{O}(n^2)\) in the number of candidate answers.

7 Experiment Details and Ablations↩︎

7.1 Experiments Details↩︎

7.1.0.1 Implementation Details.

Our study leverages the open-source models suite alongside the DeBERTa-Large-MNLI model, both accessed through the HuggingFace Transformers framework to ensure reproducibility. Our experimental setup consists of a single server equipped with four NVIDIA RTX 4090 GPUs. All models were implemented in PyTorch 2.7 and trained using CUDA 12.2. We have made the core code publicly available. Please refer to https://anonymous.4open.science/r/lgu-67E0 for details.

• To obtain the final answer used for accuracy evaluation, we employ a deterministic decoding strategy by disabling sampling (do\(\_\)sample = False) and setting the temperature to zero (temperature = 0.1). This ensures that the model always returns the highest-probability response, providing stable and reproducible outputs.

• For uncertainty estimation, we generate a set of candidate answers using stochastic sampling with (do_sample = True) and a standard temperature setting (temperature = 1). This sampling-based approach produces diverse outputs whose variability reflects the model’s predictive uncertainty. All answer generation prompt templates are referenced from Table 3.

• Statistical Significance: We report 95% confidence intervals for all evaluated metrics (AUROC, AUARC, ECE). These intervals are estimated using a bootstrapping procedure (\(n_\text{bootstrap}=1000\), seed=42) over the test samples to ensure the robustness of our uncertainty estimations against data variance.

7.1.0.2 Baselines.

We benchmark our method against a comprehensive suite of baselines, categorized by their underlying uncertainty mechanism.

• Semantic Uncertainty Methods: These methods estimate uncertainty by considering the meaning of the generated text, rather than just its surface form.

  • Semantic Entropy: Measures uncertainty over a distribution of semantically equivalent paraphrases for a given answer. It conceptually calculates the entropy of this distribution, where higher entropy implies greater semantic ambiguity.

  • Discrete Semantic Entropy: A variant of semantic entropy that operates over a finite set of pre-defined semantic clusters instead of generating paraphrases, calculated without using the token-level log-likelihoods.

  • Kernel Language Entropy (KLE) : A sophisticated method that estimates uncertainty using semantic similarity kernels and von Neumann entropy. It provides a more fine-grained semantic uncertainty quantification than standard semantic entropy. We adopt the default hyperparameters \((t = 0.3, \alpha = 0.5, \nu = 1, \kappa = 1)\) from the original work, which demonstrated robust performance.

• Token-level Uncertainty Methods: These methods directly leverage the model’s token-level output probabilities. Let \(y = (y_1, \dots, y_T)\) be a generated sequence of length \(T\) for an input \(x\). The probability of the sequence is given by the autoregressive factorization \(P(y|x) = \prod_{t=1}^{T} p(y_t | y_{<t}, x)\).

  • Maximum Sequence Probability (MSP): A direct measure of model confidence. The uncertainty is defined as one minus the sequence probability: \[\mathcal{U}_{\text{MSP}}(y|x) = 1 - P(y|x) = 1 - \prod_{t=1}^{T} p(y_t | y_{<t}, x)\] While simple, this metric can be insensitive as the product of many small probabilities quickly approaches zero.

  • Perplexity (PPL): Measures how well the probability distribution of a language model predicts a sample. It is the exponentiated average negative log-likelihood. A lower PPL indicates higher confidence. \[\text{PPL}(y|x) = \exp\left(-\frac{1}{T} \sum_{t=1}^{T} \log p(y_t | y_{<t}, x)\right)\]

  • Average and Max Negative Log-Probability: These metrics, often denoted as \(\text{Avg}(-\log p)\) and \(\text{Max}(-\log p)\), isolate components of perplexity. \(\text{Avg}(-\log p)\) is the sequence-level cross-entropy loss, while \(\text{Max}(-\log p)\) identifies the point of maximum uncertainty within the sequence. \[\begin{align} \mathcal{U}_{\text{AvgNLL}}(y|x) &= -\frac{1}{T} \sum_{t=1}^{T} \log p(y_t | y_{<t}, x) \\ \mathcal{U}_{\text{MaxNLL}}(y|x) &= \max_{1 \le t \le T} \left( -\log p(y_t | y_{<t}, x) \right) \end{align}\]

• Supervised & Calibrated Methods: These approaches require additional training or specialized prompting to estimate correctness.

  • Embedding Regression: A supervised method that trains a simple classifier, such as a logistic regression model, on the final-layer hidden states (\(h_T\)) of the LLM to directly predict the probability of answer correctness.

7.1.0.3 Evaluation Metrics.

We assess all methods using three standard metrics, each evaluating a distinct aspect of uncertainty quality: discrimination, practical utility, and calibration.

• Area Under the Receiver Operating Characteristic Curve (AUROC): Following prior work, we use AUROC to measure an uncertainty score’s ability to rank incorrect predictions higher than correct ones. It plots the true positive rate against the false positive rate across all possible thresholds, with a score of 1.0 indicating perfect discrimination.

• Area Under the Accuracy-Rejection Curve (AUARC): This metric evaluates the practical utility of uncertainty for selective prediction. It measures the area under the curve formed by plotting the accuracy on non-rejected samples versus the fraction of samples rejected, as the rejection threshold is varied. A higher AUARC signifies a better trade-off between accuracy and coverage.

• Expected Calibration Error (ECE): ECE measures the discrepancy between a model’s confidence and its empirical accuracy, quantifying how well-calibrated the uncertainty scores are. Predictions are partitioned into \(M\) bins \(B_m\) based on their confidence scores. The ECE is the weighted average of the absolute difference between the average confidence and accuracy in each bin: \[\text{ECE} = \sum_{m=1}^{M} \frac{|B_m|}{N} \left| \text{acc}(B_m) - \text{conf}(B_m) \right|\] where \(N\) is the total number of samples, \(\text{acc}(B_m)\) is the fraction of correct predictions in bin \(B_m\), and \(\text{conf}(B_m)\) is the average confidence of predictions in that bin. A lower ECE indicates better calibration.

  We adopt an empirical min-max normalization protocol based on the observed data range. While ECE was originally designed for probabilistic predictions, its computation only requires a confidence score in \([0,1]\) rather than strictly calibrated class probabilities. In our setting, uncertainty estimates are mapped to confidence scores via the monotonic transformation \(c = 1 - (u - u_{\min}) / (u_{\max} - u_{\min})\), which preserves the relative ordering of predictions while enabling calibration analysis. This evaluation protocol is standard in LLM uncertainty quantification; recent surveys explicitly identify ECE as a benchmark for assessing whether uncertainty estimates behave as reliable confidence signals, even when they are not calibrated probabilities [51].

7.2 Generalization Study↩︎

Table ¿tbl:tab:main95results? presents the complete experimental results across all dataset-model pairs. The table provides a comprehensive comparison of each method under all evaluation metrics, further substantiating the robustness and generalizability of Logical Graph Uncertainty. These results confirm that our approach consistently outperforms baselines in both semantic and token-level uncertainty estimation, demonstrating its effectiveness in diverse settings.

7.2.0.1 Average Rank Comparison across Models and Datasets.

While absolute metrics (AUROC, AUARC, and ECE) provide detailed performance indicators for individual model-dataset pairs, absolute scores can be heavily influenced by the inherent capabilities of different LLMs (e.g., modern models like LLaMA-3-8B naturally achieve a higher baseline AUROC than earlier models like Falcon-7B). To provide a rigorous, macro-level evaluation of robustness and to mitigate the variance introduced by disparate baseline performances, we conduct a comprehensive rank-based comparison.

For each specific evaluation setting (i.e., a combination of a model and a dataset), we rank the evaluated uncertainty estimation methods from best (rank 1) to worst. For discriminative metrics (AUROC and AUARC), higher numerical values receive better (lower) ranks; for calibration metrics (ECE), lower numerical values receive better ranks. We then average these ranks across all evaluated LLMs and benchmarks from our generalization study to compute the average rank per metric. The Overall Avg Rank is the mean of the ranks across all three metrics.

The average ranking results are summarized in Table 4. We observe the following key findings:

• LGU Achieves State-of-the-Art Robustness: Our proposed Logical Graph Uncertainty (LGU) consistently achieves the best (lowest) average rank across all individual metrics: AUROC (1.5417), AUARC (1.6250), and ECE (2.1250). With an Overall Avg Rank of 1.7639, LGU is firmly established as the most universally reliable method across the diverse spectrum of modern LLMs.

• Superiority over Strong Baselines: Compared to the competitive KLE (Overall Rank: 2.0833), LGU demonstrates a clear advantage, particularly in calibration (ECE rank 2.1250 vs. 2.8750). This indicates that penalizing logical incompatibility not only improves discrimination but also prevents the over-confidence issues frequently observed in semantic-only methods.

• Limitations of Traditional Methods: Standard Semantic Entropy (SE) and Naive Entropy (NE) lag significantly behind graph-based and kernel-based methods, confirming that merely measuring semantic equivalence or token-level uncertainty is insufficient. Furthermore, likelihood-based sequences (PPL) and representation-based methods (ER) consistently rank at the bottom in this unsupervised setting, highlighting their lack of generalizability.

7.3 Ablation Study on Incompatibility Measures↩︎

To scrutinize the contribution of each component in our framework and determine the optimal graph-density metric for the Incompatibility Score (\(InS\)), we conduct a comprehensive ablation study. Table ¿tbl:tab:ablation95results? compares our proposed Logical Graph Uncertainty (LGU) against two reduced baselines and three alternative \(InS\) instantiations. The variants are defined as follows:

• Root Entropy (RE): Computes the entropy over the probability distribution of the root hypotheses without considering implication chains or incompatibility penalties. This serves as a baseline for the logical graph structure.

• Implication Graph Entropy (IGE): Aggregates probability mass along implication chains but calculates entropy over roots without penalizing mutual incompatibility (i.e., \(InS(x/L) = 0\)).

• LGU Variants (Different \(InS\) Metrics): We test four implementations of the incompatibility score \(InS(x/L)\):

  • LGU (Edge Density): Uses the directed edge density of the Incompatible Graph (InG), capturing the normalized sparsity of conflicts.

  • LGUWD (Weighted Density): Uses edge density weighted by the probability mass of conflicting nodes.

  • LGUAD (Average Degree): Uses the average degree of nodes in the InG, reflecting the average number of conflicts per hypothesis.

  • LGUE (Estrada Index): Uses a spectral graph measure based on the matrix exponential of the adjacency matrix, capturing global connectivity.

Analysis of Results. First, we observe that explicitly modeling incompatibility is crucial. As shown in Table ¿tbl:tab:ablation95results?, LGU consistently outperforms IGE across most datasets and models. For instance, on Falcon-7b-instruct with the NQ dataset, LGU improves AUROC from 0.7349 (IGE) to 0.7517, confirming that penalizing mutually exclusive hypotheses provides a stronger signal for uncertainty than implication aggregation alone.

Second, regarding the choice of incompatibility metric, LGU (Edge Density) and LGUWD (Weighted Density) yield the most robust performance. While LGUWD achieves marginal gains in specific cases (e.g., TriviaQA on Falcon-7b), LGU (Edge Density) offers superior calibration (lower ECE) and stability across diverse tasks. In contrast, LGUE (Estrada Index) demonstrates significant instability. Although it captures global structure, its exponential nature makes it overly sensitive to graph density, leading to severe over-estimation of uncertainty and poor calibration (e.g., an ECE of 0.4646 on Falcon-7b/SQuAD compared to LGU’s 0.0708). Similarly, LGUAD often results in higher ECE than density-based methods.

Conclusion. Based on these findings, we select Directed Edge Density as the default implementation for \(InS(x/L)\) in our final LGU framework. It provides the best trade-off between discriminative power (AUROC) and reliability (ECE), while maintaining mathematical simplicity and a bounded range \([0, 1]\).

7.4 Additional Experiments and Analysis↩︎

7.4.1 Limitations of Evaluation Metrics and Bounds of ECE Normalization↩︎

7.4.1.1 Limitations of Using AUROC as the Sole Uncertainty Metric.

Existing studies often rely on AUROC as the sole criterion for evaluating uncertainty estimation. However, AUROC only captures the ranking ability of uncertainty scores in distinguishing correct from incorrect predictions, and therefore fails to assess whether the numerical values of uncertainty are meaningfully calibrated. Since uncertainty fundamentally reflects a model’s confidence about its own predictions, proper calibration is essential. To address this limitation, we incorporate ECE as a complementary metric, providing a direct measure of the alignment between predicted uncertainty levels and actual error frequencies. The joint use of AUROC and ECE yields a more complete and reliable assessment of uncertainty quality.

7.4.1.2 Robustness to ECE Normalization Protocols: Theoretical vs. Empirical Bounds.

Evaluating Expected Calibration Error (ECE) requires transforming unbounded uncertainty measures (e.g., semantic entropy or graph-based uncertainty) into valid confidence scores within \([0, 1]\). This is typically achieved via min-max normalization: \(\text{Confidence} = 1 - \frac{U - U_{\min}}{U_{\max} - U_{\min}}\). However, the choice of the upper bound (\(U_{\max}\)) and lower bound (\(U_{\min}\)) can be determined in two distinct ways:

1. Theoretical Bounds: Derived from the mathematical definitions of the metrics. For example, Shannon entropy over \(N\) candidate answers is bounded by \(\log(N)\), and the theoretical maximum of our Logical Graph Uncertainty (LGU) is strictly delineated by Theorem 3.6.

2. Empirical (Actual) Bounds: Derived directly from the observed dynamic range (i.e., the actual minimum and maximum values generated by a specific model on a specific dataset).

To ensure our calibration evaluation is not an artifact of the normalization strategy, we conduct a comprehensive comparison of the best-performing methods (i.e., the method achieving the lowest ECE) under both theoretical and empirical bounding protocols.

Table 5 summarizes the winning methods across 40 model-dataset pairs. We observe a substantial agreement between the two evaluation protocols, confirming the reliability of our ECE findings. Most importantly, LGU is selected most frequently under both settings. Specifically, under the theoretical upper bound, LGU achieves the lowest ECE in 21 out of 40 cases, followed by NE (10) and SE (9). Under the empirical estimation, LGU remains the dominant method with 19 selections, followed by NE (10), SE (6), and KLE (5).

Given that empirical bounds adapt naturally to the actual dynamic range of model outputs without requiring explicit mathematical derivation for every arbitrary score formulation, and since the relative superiority of the methods remains consistent, we adopt the empirical bounds for the main experiments in this paper. This ablation highlights the robust calibration capabilities of LGU across diverse generation scenarios.

7.4.2 Empirical Verification of NLI-based Logical Properties.↩︎

A critical premise of our proposed framework is that the off-the-shelf Natural Language Inference (NLI) model (DeBERTa-Large-MNLI) can reliably capture formal logical relations to construct valid graph structures. To validate the structural integrity of our logical graphs and support our theoretical claims, we conduct large-scale empirical property testing, detailed as follows.

1. Implication Graph (ImG) and Transitivity. According to Proposition 3.2, the logical implication relation utilized to construct the ImG must be reflexive and transitive. In our implementation, reflexivity holds trivially and does not affect the computation of Implication Graph Entropy (IGE), as self-loops are omitted by definition. However, transitivity is paramount for treating the ImG as a Directed Acyclic Graph (DAG) (Theorem 3.3). To empirically verify this, we randomly sampled 4,863 implication chains from our generated data (i.e., triplets where the NLI model confidently predicts \(A \Rightarrow B\) and \(B \Rightarrow C\)). Among these chains, the NLI model correctly predicted \(A \Rightarrow C\) in 97.0% of the cases. This remarkably high transitivity rate empirically justifies our implication-based probability aggregation and confirms that the NLI model provides a highly reliable directed topology for the ImG.

2. Incompatibility Graph (InG) and Symmetry. Proposition 3.4 defines incompatibility as a symmetric, non-reflexive, and non-transitive relation. Non-reflexivity and non-transitivity hold trivially for mutually exclusive statements (e.g., a hypothesis cannot contradict itself). To verify symmetry, we randomly sampled 5,339 incompatible pairs predicted by the NLI model (i.e., hypothesis \(A\) contradicts hypothesis \(B\)). We observed that 92.8% of these pairs were strictly symmetric (i.e., the model also predicts \(B\) contradicts \(A\)). This robust symmetry ensures that our incompatibility penalty (InS), which relies on an undirected InG graph-density metric (e.g., Edge Density), operates on a mathematically sound foundation.

7.4.3 Impact of Model Quantization on Uncertainty Estimation↩︎

In real-world deployments, large language models are frequently subjected to weight quantization (e.g., 8-bit or 4-bit precision) to reduce memory footprints and accelerate inference. However, quantization introduces noise into the model’s intermediate representations and output logits, which can potentially distort the token-level probability distributions that many uncertainty estimation methods rely on. To evaluate the robustness of our proposed framework against precision degradation, we conduct an additional experiment comparing the performance of uncertainty metrics across three precision levels of the LLaMA-3-8B model: Full Precision (BF16), 8-bit, and 4-bit. The evaluation results are presented in Table 6. This experiment confirms that LGU is not only highly effective in standard settings but is also exceptionally practical for resource-constrained, low-precision deployment scenarios.

3pt

7.4.4 Black-box Uncertainty Estimation↩︎

In addition to white-box methods, we propose a quantitative uncertainty estimation approach tailored for black-box large language models. Table ¿tbl:tab:black95box95full95results? compares our Discrete Logical Graph Uncertainty (DLGU) method with two competitive baselines: Discrete Semantic Entropy (DSE) and Kernel Language Entropy using a heat kernel (KLE(heat)).

DLGU consistently outperforms DSE across nearly all models and datasets, demonstrating stronger discriminative power. Compared to the state-of-the-art KLE(heat), DLGU achieves comparable or better results, especially in calibration. DLGU attains the lowest ECE in most settings, indicating more reliable uncertainty estimates. For example, on the Falcon-7b model with Trivia QA, DLGU reduces ECE to 0.070, substantially lower than KLE(heat)’s 0.183. On discriminative metrics such as AUROC and AUARC, DLGU remains highly competitive, frequently matching or surpassing KLE(heat). These results validate the effectiveness and robustness of DLGU for black-box uncertainty quantification.

7.4.5 Case Study: Logical Entailment and Contradiction Detection↩︎

Table 7 presents a qualitative comparison between our proposed LGU method and baseline metrics (SE and KLE) across three distinct scenarios: consistent correctness, incorrect prediction, and severe hallucination.

Identifying Logical Entailment. The first row demonstrates a case where the model correctly answers "Apollo". Although the sampled responses vary lexically (e.g., "the god of prophecy, apollo" vs. "Apollo"), they are semantically equivalent. While KLE assigns a relatively high uncertainty score (0.89) due to token-level discrepancies, LGU successfully recognizes the logical entailment among these responses, yielding a perfect uncertainty score of 0. This indicates that LGU is robust to surface-level variations when the underlying logic remains consistent.

Penalizing Severe Hallucinations. The third row illustrates a scenario of severe hallucination, where the model generates a "confabulation" regarding the number of times Lake Placid has hosted the Olympics. The sampled responses are riddled with logical contradictions, ranging from "twice" to "Ten times," with various invented years. In this case, LGU calculates a significantly higher uncertainty score (3.42) compared to SE (2.26) and KLE (2.27). This sharp increase demonstrates LGU’s capability to detect and penalize high-entropy logical conflicts, effectively flagging instances where the large language model is "talking nonsense" despite potential confidence in its tone.

3pt

4pt

NeurIPS Paper Checklist↩︎

1. Claims

2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

3. Answer:

4. Justification: The abstract and introduction clearly and accurately state the paper’s main contributions: (1) identifying the limitation of semantic-level uncertainty methods that ignore logical relationships among answers, (2) proposing a logical graph-based framework (IGE and LGU) to model implication and incompatibility, and (3) demonstrating consistent empirical improvements over prior methods on multiple QA benchmarks. The claims regarding performance gains (e.g., improvements in AUROC and calibration) are supported by experimental results reported later in the paper, and the scope is appropriately limited to uncertainty quantification in LLM-generated answers without overstating generalization beyond the evaluated settings.

5. Limitations

6. Question: Does the paper discuss the limitations of the work performed by the authors?

7. Answer:

8. Justification: The paper explicitly discusses key limitations in the discussion section. In particular, it acknowledges that the proposed framework models only implication and pairwise incompatibility, and does not capture richer logical relations such as causality, temporal structure, or defeasible reasoning. It also clearly states that the method depends on the quality of the underlying NLI model, whose errors may propagate into the constructed logical graphs and affect the final uncertainty estimates. These points appropriately reflect important assumptions and potential failure modes of the approach, demonstrating awareness of its scope and practical constraints.

9. Guidelines:

10. Theory assumptions and proofs

11. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

12. Answer:

13. Justification: The paper includes multiple formal theoretical results (e.g., Theorem 3.3, Theorem 3.6, and Theorem 3.7), all of which are clearly stated with necessary assumptions and definitions in the main text. The assumptions underlying the constructions (e.g., graph definitions, pairwise logical relations, and properties of entropy) are explicitly introduced before the theorems. Full formal proofs are provided in the appendix, and the main text offers sufficient intuition and context for understanding the results. Theorems, propositions, and definitions are properly numbered and logically structured, and dependencies are clearly organized, satisfying the checklist requirements.

14. Experimental result reproducibility

15. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

16. Answer:

17. Justification: The paper provides sufficient details to enable reproduction of the main experimental results. It clearly specifies the datasets used (TriviaQA, SQuAD, BioASQ, Natural Questions), the evaluated models (e.g., LLaMA, Falcon, Mistral, Qwen), and the evaluation metrics (AUROC, AUARC, ECE). :contentReference[oaicite:0]index=0 It also describes the overall pipeline, including answer sampling, semantic clustering, logical graph construction via an NLI model, and computation of uncertainty scores. Baselines are comprehensively listed and compared under consistent settings. While some implementation details (e.g., specific prompting strategies, hyperparameters, or NLI thresholds) are not exhaustively specified in the main text, the provided methodological description and experimental setup are sufficiently clear for reproducing the core results and validating the main claims.

18. Open access to data and code

19. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

20. Answer:

21. Justification: Yes, we attach the source code and instructions for reproducing the results in the supplementary materials. We will release the source code and instructions online.

22. Experimental setting/details

23. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?

24. Answer:

25. Justification: We provide all the necessary details in Section 3 and additional details in Appendix 7.1.

26. Experiment statistical significance

27. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

28. Answer:

29. Justification: The paper reports error bars for the main experimental results, providing quantitative information about variability and statistical reliability. The figures and tables include these error bars.

30. Experiments compute resources

31. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

32. Answer:

33. Justification: We have discussed it in Appendix 7.1.

34. Code of ethics

35. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

36. Answer:

37. Justification: Our research conforms, in every respect, with the NeurIPS Code of Ethics.

38. Broader impacts

39. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

40. Answer:

41. Justification: We have discussed broader impact in Section 5.

42. Safeguards

43. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?

44. Answer:

45. Justification:

46. Licenses for existing assets

47. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

48. Answer:

49. Justification: The paper properly cites and credits the original creators of the datasets (e.g., SQuAD, TriviaQA, BioASQ, Natural Questions) and models (e.g., LLaMA, Falcon, Qwen, Gemma) used in the experiments through appropriate academic references. While the paper does not explicitly list license terms in detail, it follows standard academic practice by referencing the original sources, which provide the corresponding licensing and usage conditions. There is no indication of misuse or violation of terms, and all assets are used in a manner consistent with their intended research usage.

50. New assets

51. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

52. Answer:

53. Justification: We document our source code in the README.md file.

54. Crowdsourcing and research with human subjects

55. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

56. Answer:

57. Justification:

58. Institutional review board (IRB) approvals or equivalent for research with human subjects

59. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

60. Answer:

61. Justification:

62. Declaration of LLM usage

63. Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.

64. Answer:

65. Justification: The paper explicitly describes the use of LLMs as a core component of the methodology, including how model-generated samples are obtained and utilized within the uncertainty estimation pipeline. In particular, the appendix provides the prompting details used for answer generation, which clarifies how LLM outputs are produced and incorporated into the framework. This level of disclosure satisfies the requirement to document LLM usage when it is integral to the method.

References↩︎

---

1. Supported by the postdoctoral program at Guangzhou Jiayi Software Technology Co., Ltd. and Nansha IT Park.↩︎

2. These authors contributed equally to this work.↩︎

3. Throughout this paper, we use the NE baseline as implemented in [18].↩︎