Graph-based Uncertainty Metrics for Long-form Language Model Generations

Authors: mingjian  jiang
yangjun  ruan
prasanna  sattigeri
salim  roukos
tatsunori  hashimoto
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 09:02:52

Abstract: Recent advancements in Large Language Models (LLMs) have significantly improved text generation capabilities, but these systems are still known to hallucinate, and granular uncertainty estimation for long-form LLM generations remains challenging. 
In this work, we propose Graph Uncertainty -- which represents the relationship between LLM generations and claims within them as a bipartite graph and estimates the claim-level uncertainty with a family of graph centrality metrics. Under this view, existing uncertainty estimation methods based on the concept of self-consistency can be viewed as using degree centrality as an uncertainty measure, and we show that more sophisticated alternatives such as closeness centrality provide consistent gains at claim-level uncertainty estimation.
Moreover, we present uncertainty-aware decoding techniques that leverage both the graph structure and uncertainty estimates to improve the factuality of LLM generations by preserving only the most reliable claims. Compared to existing methods, our graph-based uncertainty metrics lead to an average of 6.8% relative gains on AUPRC across various long-form generation settings, and our end-to-end system provides consistent 2-4% gains in factuality over existing decoding techniques while significantly improving the informativeness of generated responses.

Main paper: 
 introduction: 
 Large Language Models (LLMs) [1] [2] [3] [4] [5] have demonstrated remarkable capabilities and been widely used as an interactive chatbot to provide knowledge and answers to user queries. However, they still struggle with generating false information, often referred to as "hallucinations" [6] , which hinders their ability to provide calibrated [7] [8] [9] [10] and factual [11, 12] responses and ultimately undermines the trust users place in their outputs. Improving uncertainty estimation techniques is crucial for building trust in LLMs and mitigating the risks associated with their deployment in real-world applications.While many existing uncertainty estimation techniques for LLMs primarily focus on estimating the uncertainty of their answers to multiple-choice questions [13, 7, 8] or their entire generated responses (typically in a short form) [8, 14, 9, 15] , they are often not sufficiently informative in real-world applications where LLMs generate paragraphs of texts consisting of a mixture of true and false claims [12] . In such scenarios, more granular uncertainty estimates are needed to help users distinguish the reliability of each individual claim within the generated text. Recent approaches [11, 16] attempt to measure the uncertainty of each claim by its consistency with randomly sampled responses based on the concept of self-consistency [17] . However, they do not fully leverage the semantic relationships between claims and responses that could support more granular uncertainty estimation. The key components are the construction of a bipartite graph that captures the relations between responses and claims (c) and the use of graph centrality metrics to estimate the uncertainty of each claim. We simplify the pipeline and prompt for presentation, see Appx. F for details.We introduce Graph Uncertainty (Fig. 1 ), a framework for granular, claim-level uncertainty estimation for LLMs which utilizes the fine-grained semantic relationships over a claim-response entailment graph. Our key idea is motivated by the observation that given multiple responses sampled from LLMs and a set of claims decomposed from them, we can construct a bipartite graph that captures the semantic entailment relationships between each response and claim, which serves as a summary statistic that captures uncertainty information associated with each response and claim. On this graph, claim-level uncertainties correspond to the importance of each node in the graph, and we extract such information with a family of graph centrality metrics [18] [19] [20] [21] that measure the 'importance' of each claim node within the graph. A notable example is the existing uncertainty estimates based on the concept of self-consistency [17, 11] , which turns out to be a special instantiation of our framework with the degree centrality as the uncertainty measure. Our framework generalizes it to accommodate a broader family of well-studied graph centrality metrics that capture more granular graph information than degree centrality. Through a systematic benchmarking of various graph centrality metrics and different baselines, we demonstrate that closeness centrality [18] is a natural and high-performance uncertainty estimator and outperforms baselines by an average of 6.8% on AUPRC at claim-wise uncertainty estimation for models like GPT-4 [2] on two challenging long-form generation datasets, FactScore [12] and PopQA [22] .Furthermore, we demonstrate that our granular, claim-level uncertainty estimates translate to gains in the factuality of LM outputs by integrating them with an uncertainty-aware decoding process that can leverage these graph metrics. The idea is straightforward and builds upon ideas explored in Mohri and Hashimoto [16] , Wang et al. [23] : after obtaining claim-level uncertainty estimates following our method, we filter the claim set using uncertainty scores and synthesize the remaining claims with low uncertainty to produce the final response. Our empirical analysis demonstrates that our framework generates responses with better factuality without compromising their informativeness, achieving a better tradeoff compared to existing methods. Notably, our approach provides consistent 2-4% gains in factuality and can generate 70% more true claims at the 95% precision level compared to baselines.The main contributions of our work are as follows:• We introduce Graph Uncertainty, a general framework for claim-level uncertainty estimation of long-form LLM generations through the use of semantic graphs and graph centrality metrics. • We demonstrate that our method significantly outperforms existing methods with an average of 6.8% gains on AUPRC for claim-level uncertainty estimation, and provide a systematic benchmarking of different baselines and our method with various graph centrality metrics in these settings. • We present a straightforward and effective framework that integrates granular uncertainty estimates into LLM decoding for both factual and informative generations. Our method provides consistent 2-4% factuality gains and generates 70% more true claims than baselines at 95% precision level. 
related work: 
 Short-form uncertainty estimation in LLMs Existing approaches for characterizing the uncertainty of LLMs have largely focused on multiple-choice classification or short-form generation setups and can be categorized into likelihood-based [13, 7, 24, 9] , consistency/ensemble-based [10, 25] , and verbalizer-based [14, 15] methods. In this line of work, Kadavath et al. [8] transforms uncertainty estimation into a binary classification task to estimate the probability of whether a sample is true or not. Kuhn et al. [9] proposes to estimate the 'semantic entropy' of the sample distribution given a prompt to address the surface-form competition [26] in the generated samples. Lin et al. [27] generalizes it to incorporate more fine-grained similarities between different samples and utilize degree or eigenvalue-related metrics for better discriminative performance. Xiong et al. [10] proposes a framework for systematically evaluating verbalizer and consistency strategies of eliciting confidence scores for black-box LLM, without access to model parameters or activations. Our work is distinct from these existing works in our focus on the long-form setting, which requires uncertainty estimation at a more granular level.Recent works have begun to extend uncertainty estimation to long-form outputs. Duan et al. [28] and Band et al. [29] obtain claim-level uncertainty scores from long-form outputs but operate in a white-box setting -requiring access to model internals -and therefore do not apply to API-based LLMs. Most relevant to our work, Manakul et al. [11] extends the concept of self-consistency [17] to assess uncertainty at the sentence level within long-form outputs, which is applicable to black-box LLM. Building upon this, Mohri and Hashimoto [16] performs uncertainty estimation at the claim level, combining a self-consistency style technique with conformal prediction. However, these works purely rely on the sample-and-count technique [11] that may not sufficiently capture the semantic relationships between claims and responses. Our work improves granular uncertainty estimation by considering more fine-grained semantic information contained in the entailment graph and its associated centrality measures.There have been several works on enhancing the factuality of LLMs at various stages, including retrieval [30, 31] , pretraining [32, 33] , and fine-tuning [34, 35, 29] . These methods typically require a reliable knowledge database for retrieval or extensive model training, which can be impractical and costly. Our work focuses on improving the factuality of LLMs at inference time and can be combined with other techniques. In this context, CoVe [36] proposes that LLMs can enhance their outputs through a series of planning and self-verification steps. DoLA [37] dynamically selects intermediate layers at each decoding step to minimize the generation of incorrect facts, though this method is only applicable to white-box LLMs. Recently, Wang et al. [23] and Mohri and Hashimoto [16] study methods that leverage claim-level uncertainty estimates for more factual LM outputs. We show that improved uncertainty estimators and decoders based on the entailment graph formalism lead to significant improvements in the factuality of LM outputs. 
preliminary: 
 In this work, we focus on the problem of granular uncertainty estimation for LLMs, particularly in the context of distinguishing whether each claim in a long-form output is factual. Specifically, let Σ denote the set of all characters and Σ * the space of all possible text strings. Given a text prompt x ∈ Σ * , the generation process of a model M with a specified temperature T = t can be represented as a conditional probability distributionM T =t (•|x) over Σ * .Uncertainty estimation for LLMs In the context of LLMs, uncertainty estimation is concerned with the following: given a model M , a prompt x ∈ Σ * , and a response y ∈ Σ * , we seek an uncertainty function U : Σ * × Σ * → R that measures the uncertainty of LLMs about the response. In this work, we define the efficacy of U by how effectively it differentiates the true and false claims of y, using classification metrics such as AUROC and AUPRC. We focus on classification metrics rather than calibration or coverage, as our main goal will be using U to identify and remove false claims as part of a decoding-time intervention.Claim-level uncertainty estimation In many practical applications, the outputs from an LLM encompass a few paragraphs of text containing multiple claims [11, 16] . We consider a claim to be the smallest semantically distinct unit of information presented within the generated output. For example, in Fig. 1 , "Snedden was elected to the Australian Parliament" is an example of a single claim. In this work, instead of assigning a single uncertainty score to the entire output, we assess uncertainty at the level of individual claims. Formally, we further define C as a universal set of all unique, semantically distinct claims. The claim-level uncertainty function is then U : Σ * × C → R, allowing for granular analysis of factuality at the claim level.Table 1 : Graph centrality metrics with their formulas and brief explanations. We utilize the centrality metric value for each claim node to measure the uncertainty of the claim. Self-consistencybased estimate corresponds to the specific case of using the degree centrality. V and A are the node set and adjacency matrix of the graph G. A full definition of the notations is provided in Appx. E.Metric Formula Brief Explanation Degree CD(v) = u∈V Avu Number of edges incident to a node v Betweenness CB(v) = s̸ =v̸ =t σ st (v) σ stFraction of shortest paths σst between other nodes s, t that pass through a node vEigenvector CE(v) = 1 λ u∈N (v) AvuCE(u)Importance of a node v measured by the importances of its neighboring nodes N (v)PageRank CP R(v) = 1-d |V | + d u∈N (v) C P R (u) N (u)Stationary distribution of a random walk within the graph with restart. d is the damping factor.Closeness CC (v) = |V |-1 u∈V d(v,u) • |V | |Vv |Black-box LLM setup & Existing approaches We focus on settings where we can only access the LLM outputs for each prompt and not its internal architecture or likelihood estimates. This reflects the real-world scenario for the most capable models, such as GPT-4 [2] and Claude-2 [3] , which are typically accessed through API calls. The black-box assumption restricts the applicability of certain uncertainty estimation methods, such as those that rely on activation layers or logits [24, 37, 29] .There are relatively few methods that apply to this black-box setting. A few examples of uncertainty quantification methods that are applicable include:• Verbalized Confidence (VC) [14, 15] based approaches which involve prompting the LLM to express its confidence in a claim c ∈ C directly, based on the prompt x ∈ Σ * . The uncertainty is quantified by parsing the verbalized confidence expression (e.g.,"very confident","100%", etc.) and mapping it to a numerical value. • Self-consistency (SC) [17, 10, 11] based approaches involve checking the claim c (typically decomposed from the greedily decoded output M T =0 (x)) against a set of sampled responses R = {r (i) } i∈[N ] where r (i) ∼ M T =t (•|x) at a higher temperature t > 0. The uncertainty estimate of c is typically calculated by the proportion of responses r i that entail (denoted by ⇒) the claim c, where N is the total number of generated responses. Formally, the consistency score for a claim c can be expressed as SC(c) = 1 N N i=1 1[r (i) ⇒ c].A higher consistency score indicates lower uncertainty, as the claim is more consistently entailed across the diverse responses.Empirical evidence [10, 16] suggests that SC often surpasses VC in its effectiveness for uncertainty estimation.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [NA] Justification: The method we proposed is based on empirical evidence rather than theoretical analysis, so theoretical assumptions or proofs are not applicable.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
claim-level uncertainty estimation with semantic entailment graphs: 
 Our motivation stems from the observation that given a set of generated responses R and their entailed claims C, we can construct a bipartite graph G = ((R, C), E) between R and C with edges E indicating the entailment relationship between each response and claim (Fig. 1 ). This graph captures the semantic entailment relationship between responses and claims, from which we may extract information that effectively captures the uncertainty of each claim. A motivating example is SC, which turns out to be a special case of calculating the degree centrality of each claim node as their uncertainty. This encourages the investigation of a broad family of graph-based metrics beyond the node degree, potentially offering more robust uncertainty estimates by exploiting intra-graph information.In the following section, we will demonstrate how to construct the semantic entailment graph using an LLM in Sec. 4.1, and then describe the graph metrics we are exploring in Sec. 4.2.Here we describe the procedure for constructing a bipartite graph G = ((R, C), E) that captures the generation-claim relationships for a given input x using an LLM, as illustrated in Fig. 1 . The graph construction involves multiple LLM interactions, with detailed prompts provided in Appx. F. Step 1: Response sampling (R) Given an input prompt x, we follow the same procedure as SC [11] to generate a set of |R| responses from the LLM, including one greedily decoded response M T =0 (x) and |R| -1 responses from M T =t (•|x). This process produces a set of generated responsesEQUATIONT =t (x), . . . , M(|R|-1) T =t (x)}.Step 2: Claim decomposition and merging (C) We select a subset R N ⊂ R of N responses from R. For each response r ∈ R N , we first prompt the LLM to decompose r into a set of claims, denoted as C r , following the procedure in [12] . Since the claims from different responses may semantically overlap, we also utilize an LLM to merge all claims into a comprehensive set of all unique, semantically distinct claims. Specifically, we prompt an LLM to implement a union function M : P(C) × P(C) → P(C), which takes two claim sets C (1) , C (2) and merges them according to their semantic meaning. This is approximated by prompting the LLM to evaluate whether each claim in C (2) is entailed by any claim in C (1) , and only those that are not are kept and appended to the original set. By sequentially prompting the LLM to merge the claim sets, we could get a union of all claims in R N , i.e., C (1) = C r1 , C (i) = M(C (i-1) , C ri ) for i ∈ {2, . . . , N } where r i ∈ R N . The final set forms our set of claim nodes C = C (N ) .Step 3: Edge construction (E) To construct the bipartite graph, we link the responses in R to the claims in C. An edge e between a response r ∈ R and a claim c ∈ C is established if r entails c. The entailment relation is determined by prompting the same LLM M , following the procedure in [11] .Recall that SC corresponds to using the specific claim node degree as the uncertainty estimate.Intuitively, the effectiveness of SC demonstrates that the more 'connected' a claim node is to other nodes in the graph, the more likely the claim to hold true. Drawing on this premise, we explore a broader family of graph centrality metrics [18] [19] [20] [21] that measure the importance of a claim node within the graph from different angles, some of which may correlate with the factuality of the node to a greater extent. Specifically, denoting the graph G = (V, A) here by its node set V and adjacency matrix A, we assess the graph centrality metrics detailed in Table 1 . These include the betweenness C B , eigenvalue C E , PageRank C P R , and closeness centrality C C . A full definition of the notations is provided in Appx. E. Note that we use the Wasserman and Faust (WF) improved formula [20] for closeness centrality to ensure applicability to disconnected graphs.These centrality metrics are pre-defined to measure the importance of a node in a graph in different ways, and it is not clear a priori which types of centrality are useful for uncertainty estimation. Therefore, we carefully study all of these centrality metrics in various settings in our experiments (Sec. 6.1). We use these centrality metric values of the claim nodes within the bipartite graph as their confidence scores (i.e., the negative values as their uncertainty estimates), and evaluate the correlation between these metric values and the claim factualities. This analysis helps us identify the most empirically effective centrality metric for uncertainty estimation at the granularity of claims.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)?Answer: [Yes] Justification: We include all the methodology details in Sec. 4 and Sec. 5, the experiment details in Sec. 6 in the main paper, as long as baseline details in Appx. B, prompt details in Appx. F, data and annotation detials in Appx. A, additional notation in Appx. E. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closedsource models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
uncertainty-aware decoding: 
 We have introduced a graph-based technique for estimating the uncertainty at the level of individual claims. To demonstrate that our uncertainty estimation method translates to more factual LLM outputs, we now present a framework that integrates these uncertainty estimates at decoding time to improve the factuality of LLM outputs (Fig. 2 ). Similar to contemporaneous work on factuality-enhancing decoding [16, 23] , we filter claims by uncertainty score to retain only confident claims. We show in our experiments that our use of the entire claim set (vs claims associated with a single output, compared to other works) and our improved uncertainty metrics lead to improved factuality without compromising the informativeness of LLM outputs.The intuition of our approach is to retain only the most confident claims and to synthesize them into a single coherent response. A detailed description of the steps is provided below.1. Create a candidate claim set with uncertainty estimates: For a given prompt x, generate a candidate claim set C for the final output, along with their uncertainty estimates U (x, c), ∀c ∈ C. Different approaches can apply here, and we follow the same procedure described in Sec. 4.2. 2. Filter claims by uncertainty estimates: Filter out claims from the candidate claim set with a high uncertainty estimate above a certain threshold δ ∈ R. This creates an operational subset of C, C o = {c ∈ C|U (x, c) < δ}, containing claims with low uncertainties. The threshold δ can be selected either heuristically in an unsupervised manner or based on a percentile q over training data claims, where the latter approach provides correctness guarantees with factuality probability levels determined by q [16] . Following the supervised approach, we determine δ by selecting a percentile q and computing the corresponding threshold on a small set of training data. 3. Integrate selected claims: Integrate the selected claims in the operational subset (C o ) into a single, coherent output using an LLM. The prompt details for this step can be found in Appx. F.In subsequent sections, we show that our approach provides favorable factuality-informativeness tradeoffs, where factuality is defined as the precision of the generated claims, and informativeness is defined as the number of true claims included in the output, analogous to the recall of true claims.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? Answer: [Yes] Justification: We include a code piece upon submission. But we will also release a full version within one month after we get it cleaned.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In Sec. 6.1, we benchmark our proposed graph-based metrics and existing methods adapted for claim-wise uncertainty on two long-form factuality datasets, demonstrating the effectiveness of closeness centrality as a reliable uncertainty measure. In Sec. 6.2, we show that applying the closeness centrality metric with our uncertainty-aware decoding framework demonstrates the best informativeness-factuality trade-off for long-form generation and empirically analyze the impact of each component. Additionally, Sec. 6.3 presents an ablation study to investigate the factors contributing to the performance of closeness centrality and provide insights for interpretation.In this subsection, we empirically analyze different graph centrality metrics for uncertainty estimation and systematically benchmark existing methods adapted for claim-wise uncertainty estimation.We evaluated the different uncertainty estimation methods on two challenging datasets, FActScore [12] and (long-form) PopQA [22] , where even the most capable LLMs like GPT-4 [2] demonstrate frequent factuality failures. For each dataset, we randomly sampled 100 entities and generated a set of claims about each entity with their uncertainty estimates using our pipeline described in Sec. 4.1. This process yielded over 2000 claims on average for each evaluation setting. We briefly describe each dataset and their annotation details here, and include additional details in Appx. A:• FActScore [12] is a widely used dataset for evaluating the factuality of long-form text generation for LLMs, containing entities sourced from Wikipedia. To assess the factuality of claims, we employed a similar pipeline to the one in their paper, classifying them as True, False, or Subjective using LLMs conditioned on the corresponding Wikipedia article. We specifically used GPT-4-Turbo due to its low classification error rate. • Long-form PopQA [22] comprises of entities covering a diverse range of subjects. The original PopQA was not designed for long-form generation, we adapted it by adjusting the prompt to "Provide me with a paragraph detailing some facts related to subject".To ensure data quality, we filtered out entities that either lacked a Wikipedia page or had pages shorter than 1500 characters. The factuality of claims was evaluated by GPT-4-Turbo using the associated Wikipedia pages as reference, where longer Wikipedia pages were preferred as they typically provide more comprehensive coverage of entity information, thus reducing the risk of false negative annotations.We also evaluated different methods on the Natural Question dataset [38] and observed consistent gains. Due to a higher rate of false negatives in the auto-annotation pipeline compared to the aforementioned datasets, we have included these results in Appx. C.1. Baseline methods Since existing approaches mostly focus on uncertainty estimation at the generation level, we adapted them to claim-level estimation for the purpose of baseline comparison. In particular, we conducted a systematic benchmarking of a wide range of methods including:• Post-hoc verbalized confidence (PH-VC) [8] This method is a variant of Verbalized confidence (VC) as introduced in Sec. 3, which elicits the verbalized confidence in a post-hoc manner after the entire claim set C has been decomposed from generations, following Tian et al. [15] . • In-line verbalized confidence (IL-VC) [16] This method directly elicits the verbalized confidence about each claim c in an in-line manner right after it is decomposed from the generations duringStep 2 in Sec. 4.1 and incurs negligible inference overhead in contrast to PH-VC. • P(True) [8] : this method elicits the uncertainty estimate of a claim by prompting an LLM to answer whether the claim is true or false, using the likelihood of being true as the confidence score (which we estimated by sampling multiple times from the LLMs). • Self-Consistency (SC) [17, 11] : as discussed in Sec. 3, this method utilizes the consistency score of one claim across different samples from the same LLM. • Self-Consistency + PH-VC (SC + VC): a straightforward variant of SC that integrates the PH-VC by summing their scores to break the frequent ties in confidence scores in SC. For our graph-based uncertainty estimates, we evaluated four graph centrality metrics: betweenness (C B ), eigenvalue (C E ), PageRank (C P R ), and closeness (C C ). We provide more detailed information about our methods and baselines in Appx. B.We assess how well various uncertainty estimation metrics distinguish factual claims from false ones using the Area Under the Receiver Operating Characteristic (AUROC) curve. Since the dataset may be imbalanced, we also compute the Area Under the Precision-Recall Curve for the Negative class (AUPRC-Negative). AUPRC-Negative focuses on the classifier's performance in identifying false claims that are more critical to the factuality compared to true claims. By using AUPRC-Negative, we can better assess the metrics' performance in identifying false claims, which complements the overall performance assessment provided by the AUROC metric. More detailed results are provided in Appx. C. Figure 3 : UAD with better claimlevel uncertainty estimates demonstrates a better trade-off between factuality and informativeness of the generated responses. We compare UAD across different thresholds δ and two non-uncertainty decoding baselines. We assume that random noise is applied to break ties for each uncertainty method, resulting in a horizontal line extending from the leftmost dot to the left. The shaded confidence interval is obtained by bootstrapping with a confidence level of 95%.Experimental details Our experiments are conducted on the three most capable LLMs to date (as of June 2024): GPT-3.5-turbo, GPT-4 [2] , and Llama-3-70B-Instruct [39] . We used the same LLM to sample responses and construct a semantic entailment graph for uncertainty estimation as described in Sec. 4.1. The graph construction is set up as follows: To construct the set of claims C, we used a greedily decoded sample (temperature t = 0) and 4 samples with temperature t = 1 as R N . To construct the set of responses R in the graph, we used |R| = 5 or |R| = 10 samples, where we included those for obtaining the claims and sampled additional ones with temperature t = 1 if needed. The impact of these hyperparameters is analyzed in Sec. 6.3. We collected all the claims in the entities we sampled and labeled their factuality using the method discussed in Sec. 6.1. Then, we only used those claims that are annotated as True or False (but not Subjective) to avoid ambiguity. The results are presented in Table 2 .Closeness centrality consistently and significantly outperforms baselines As illustrated in Table 2 , our closeness centrality metric consistently outperforms other graph centrality metrics and baselines, including those with higher inference costs, such as SC + VC. In some settings, closeness centrality achieves significant gains up to over 6% at AUROC and 12% at AUPRC-Negative compared to the SC baseline. To better understand the effectiveness of closeness centrality for uncertainty estimation, we provide an ablation study in Sec. 6.3. 2 also provides some insights into the effectiveness of baseline methods for claim-level uncertainty estimation:• SC is a strong baseline: We find that Self-Consistency (SC) score, which is essentially degree centrality C D , serves as a strong baseline, outperforming all other previous approaches. It sometimes underperforms our PageRank centrality metric C P R , but the comparison is sensitive to the specific setup or dataset. • IL-VC usually underperforms PH-VC: Comparing the first two rows of each setup, we find that combining the process of claim decomposition and uncertainty elicitation of claims actually hurts the uncertainty estimation performance. • Integrating VC improves SC: We observe that integrating VC into SC can improve its uncertainty estimation in most setups, even when a naive addition of their scores (SC + VC) is applied. This is probably because VC offers additional information to distinguish claims with tied scores in SC.In this subsection, we empirically demonstrate how our improved claim-level uncertainty estimates contribute to a better tradeoff between precision (factuality) and recall (informativeness) of generated responses within our UAD framework, and analyze the impact of each component.We tested UAD with our best closeness centrality uncertainty estimate C C on the FActScore dataset used in Sec. 6.1. We experimented with GPT-3.5-Turbo that were used for all steps described in Fig. 1 and Fig. 2 . We randomly sampled 180 entities and used |R| = 5 to construct candidate claim set C. Additional details can be found in Appx. B.2.We benchmarked the performance of UAD against several inference-time decoding methods. For a systematic comparison, we also included inference-time decoding methods that do not rely on uncertainty estimation. For UAD, we evaluated its performance across various uncertainty estimation techniques U and claim candidate set choices C to study their impact. Specifically, our evaluated methods include (Appx. B) :• Greedy Decoding: the most naive baseline that generates a response with a temperature of t = 0 for a given input prompt x. • CoVe [36] : an inference-time decoding method that improves the factuality of generations by self-verification without any uncertainty estimates being used. • UAD (SC, Greedy): as discussed in Sec. 5, this method corresponds to Conformal Factuality Decoding [16] , which employs the SC uncertainty estimate to filter out high-uncertainty claims in the claim set obtained from the greedily decoded response. • UAD (SC, Multi-Sample): based on the previous method, it expands the claim set C to include those decomposed from multiple sampled responses R, following our procedure in Fig. 1 .Comparing this method with the previous one studies the impact of candidate claim set size |C|. • UAD (SC + IL-VC, Multi-Sample): similar to the previous method, but it utilizes IL-VC to break ties for SC scores. We applied IL-VC instead of PH-VC here to ensure a fair comparison with similar inference costs across different methods (additional results with PH-VC are included in Appx. D.1). • UAD (C C , Multi-Sample): it applies our best graph-based uncertainty estimate with the closeness centrality C C as U , from which we can study how better claim-wise uncertainty estimates may improve the performance of UAD.The efficacy of long-form text generation was assessed along two dimensions: factuality and informativeness of the generated content. The factuality score, ranging from 0 to 1, was measured using FactScore without length penalty [12] , with higher being better. The informativeness score quantified the number of claims within the output. In cases where no claims were included in the output (e.g., "I don't know"), the factuality score is set to 1 but the informativeness score is set to 0, indicating the absence of potentially hallucinated content. These metrics were averaged across data, showing both the truthfulness and utility aspects of the generated text.Results and analysis Our results are presented in Fig. 3 , with factuality on the y-axis and informativeness on the x-axis. Methods positioned towards the upper right are preferred, as they demonstrate desirable performance for both factuality and informativeness. UAD-based methods trace a trajectory in the plot when varying the uncertainty estimation threshold δ, while Greedy decoding and CoVe appear as single points. The results reveal several key findings:• UAD achieves a better tradeoff between factuality and informativeness: We observe that UAD-based methods consistently outperform non-UAD methods, with all UAD variants achieving superior factuality-informativeness tradeoffs compared to Greedy Decoding and CoVe. Specifically, when generating the same number of claims as Greedy Decoding, UAD methods achieve up to 18% higher factuality. This indicates the effectiveness of utilizing uncertainty estimates to steer the response generation.• Expanding the claim candidate set C trades-off factuality for informativeness: Comparing UAD (SC, Multi-Sample) and UAD (SC, Greedy), we find that by expanding C to include those decomposed from multiple samples, we can achieve a better trade-off in setups where more claims are desired, but a lower peak accuracy otherwise. This indicates that the choice of C should be determined based on the desired balance between factuality and informativeness.• Better claim-level uncertainty estimates lead to a better tradeoff: Comparing UAD with SC, SC + IL-VC, and C C in Fig. 3 , we find that applying our best metric, closeness centrality, also leads to a clearly dominating Pareto optimality. Our approach consistently achieves 2-4% gains in factuality and can generate 70% more true claims at the 95% precision level compared to the best baseline. Moreover, because closeness centrality provides a more fine-grained metric than degree centrality (used in SC), it offers a broader range of trade-off options compared to SC (even when combined with IL-VC to break ties), as evidenced by more points in the figure obtained by varying the threshold δ.In this section, we aim to analyze why closeness centrality is effective for discriminating between true and false claims, and how the performance of this method changes as we increase the number of claim nodes in the semantic bipartite graph. For all experiments in the ablation study, we used the FActScore dataset with the GPT-3.5-turbo model.Why is the closeness centrality so effective? Closeness centrality is intrinsically related to the distances between nodes in a graph. To understand its effectiveness, we analyze how the distances between a pair of claims correlate with the factuality of these claims. Specifically, in Fig. 4a , we visualize the distances between true-true claim pairs, true-false pairs, and false-false pairs in the semantic graph. We observe a clear shift in the distance distribution from true claims to false claims across all settings. False claims generally exhibit larger distances to other claims in the semantic entailment graph. This observation can be intuitively interpreted as false claims being less centered, i.e., less entailed by generations and having lower co-occurrences with the majority of claims. This insight provides a clear explanation for the strong performance of closeness centrality in claim-level uncertainty estimation.How does the performance change with the number of responses? Fig. 4b explores how the performance changes as we increase the number of responses R N used to construct the claim set. We find that increasing the number of claim nodes consistently leads to improved performance (despite the increased inference cost). This also indicates that the closeness centrality effectively leverages additional graph information as more nodes are present in the semantic graph.Is our end-to-end decoding pipeline computational intensive? While our pipeline increases the lower bound of computation by introducing the graph construction process, it attains Pareto optimality for the compute-quality tradeoff compared to existing methods across multiple quality metrics. Details are present in Appx. D.2.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: All the experimental details and setting are presented in Sec. 6, Appx. A.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this work, we propose Graph Uncertainty, a family of graph-based methods for claim-wise uncertainty estimation in LLM generations. We also present an uncertainty-aware decoding framework that integrates these estimates to improve the trade-off between factuality and informativeness. Empirical results demonstrate the effectiveness of the proposed approach.Despite these improvements, we note that the graph construction process increases inference-time compute and latency. Moreover, our claim decomposition assumes that claims can be decontextualized and separated, which may not always be the case in real-world applications. Future work may aim to optimize the graph construction process to reduce computational overhead and develop techniques to handle scenarios with dependent claims more effectively. These improvements will further improve the applicability and robustness of our uncertainty estimation framework in complex settings.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We conducted pairwise Wilxicon rank significance test between each baseline method and our proposed method. We report the p-value in Appx. C.2. 
safeguards: 
 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., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper is propose methods at LLM inference time, prompting model to estimate its own uncertainty and improve the generations. There's no such risk.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets 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?Answer: [Yes] Justification: We cite the assets that we used or mentioned in this work.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not release new assets upon submission, we will release welldocumented codebase once ready.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: FActScore FActScore [12] is a widely used dataset for evaluating the factuality of long-form text generation, containing entities sourced from Wikipedia. We utilized the entities from this dataset and applied our pipeline, as discussed in Sec. 4, to generate, break down, and evaluate the uncertainty of claims. To assess the factuality of sub-claims, we employed a similar pipeline, classifying them as True, False, or Subjective using GPT-4-Turbo, which was chosen for its low error rate. We used the 'unlabelled' split of FActScore released dataset.Long-form PopQA Dataset We also incorporated the PopQA dataset [22] , which comprises entities covering a diverse range of subjects. Although PopQA was not originally designed for long-form generation, it contains challenging entities and provides links to corresponding Wikipedia pages. We filtered the dataset based on the length of the Wikipedia pages and the quality of the results. The factuality of claims was evaluated using the information from the associated Wikipedia pages, with longer pages considered more reliable due to their comprehensive coverage of the entity.Annotation Process For both datasets, we employed a two-stage annotation process. First, we used our pipeline to generate claims for each sampled entity. Second, we assessed the factuality of the generated claims using the following criteria:• True: The claim is factually accurate and supported by the information provided in the corresponding Wikipedia page.• False: The claim is factually incorrect or contradicts the information provided in the corresponding Wikipedia page.• Subjective: The claim is subjective, opinion-based, or cannot be verified using the information provided in the corresponding Wikipedia page.To ensure the quality of the annotations, we utilized GPT-4-Turbo, a large language model known for its low error rate, to classify the claims into the three categories mentioned above. This automated annotation process allowed us to efficiently label a large number of claims while maintaining a high level of accuracy.• Verbalized confidence (VC): As introduced in Sec. 3, this method involves prompting the LLM to express its confidence in a claim c directly. Here, we mainly consider two variants:-Post-hoc verbalized confidence (PH-VC) [15] : This method elicits the verbalized confidence in a post-hoc manner after the entire claim set C has been decomposed from generations. We followed Tian et al. [15] to prompt an LLM to express its confidence about each claim c ∈ C given multiple options such as "Very good chance (80%)", "Little chance (20%)" etc. -In-line verbalized confidence (IL-VC) [16] : This is a straightforward variant of PH-VC, which directly elicits the verbalized confidence about each claim c in an in-line manner right after it is decomposed from the generations during the Step 2 in Sec. 4.1. Notably, in contrast to PH-VC which requires an extra stage of prompting for VC, this method adds negligible overhead to the claim decomposition stage.• P(True) [8] : This method elicits the uncertainty estimate of a claim by prompting an LLM to answer whether the claim is true or false, using the likelihood of being true as the confidence score.Since the likelihood scores are not available for most close-source black-box LLMs, we modified it to estimate the likelihoods by sampling multiple times from the LLMs.• Self-Consistency (SC) [17, 11] : As discussed in Sec. 3, this methods utilizes the consistency score of one claim across different samples from the same LLM.• Self-Consistency + PH-VC (SC + VC): Since there are often tied confidence scores in SC (i.e., the frequencies of being it entailed in the sampled generations), rendering them less informative for distinguishing true and false claims at a granular level. We thus include a straightforward variant of SC by integrating the PH-VC to break such ties, which serves as a strong baseline in our experiments.This section aims to provide comprehensive details about the baseline methods used in Sec. 6.1. We will delve into the specifics of each method, including their prompts and implementation, and any preprocessing or postprocessing steps applied. By offering this detailed explanation at these baselines, we aim to ensure the reproducibility and transparency of our experimental setup.Assume that we have a claim c to estimate uncertainty and and an entity of the claim.Post-hoc Verbalized Confidence (PH-VC) This method elicits the verbalized confidence in a post-hoc manner after the entire claim set C has been decomposed from generations. We followed Tian et al. [15] to prompt an LLM to express its confidence about the claim c given multiple options such as "Very good chance (80%)", "Little chance (20%)" etc. The specific prompt that we use is as following:You are provided with some possible information about a person. Describe how likely it is that the possible answer is correct as one of the following expressions: No chance (0%) Little chance (20%) Less than even (40%) Fairly possible (60%) Very good chance (80%) Almost certain (100%) Give ONLY your confidence phrase, no other words or explanation. For example: Confidence: <description of confidence, without any extra commentary whatsoever; just a short phrase!> The entity is: {entity} The possible information is: {claim}In-line Verbalized Confidence (IL-VC) The In-line Verbalized Confidence (IL-VC) method differs from PH-VC in terms of prompting and integration with claim decomposition. Thus, we prompt language model with a long-form generation and instructions to give all the claims with corresponding confidence scores. The specific prompt that we adapted from [16] is as following:Please deconstruct the following paragraph into the smallest possible standalone self-contained facts without semantic repetition, and return the output as a jsonl, where each line is claim:[CLAIM], gpt-confidence:[CONF].The confidence score [CONF] should represent your confidence in the claim, where a 1 is obvious facts and results like 'The earth is round' and '1+1=2'. A 0 is for claims that are very obscure or difficult for anyone to know, like the birthdays of non-notable people.The input is: {long-form generation} P(True) The P(True) method estimates the uncertainty of a claim by prompting an LLM to answer whether the claim is true or false and using the likelihood of being true as the confidence score. Since the likelihood scores are not available for most closed-source black-box LLMs, we modified the method to estimate the likelihoods by prompting the model 10 times and frequency of answering True. The specific prompt that we adapted from [8] is as follows:The following claim is about entity. Is the claim true or false? (Answer with only one word True/False) Claim: {claim} Self-Consistency (SC) The Self-Consistency (SC) method utilizes the consistency score of one claim across different samples from the same LLM. As we discussed in Sec. 3, it is equivalent to the degree of claim on the bipartite semantic entailment graph. The whole pipeline used to construct the graph is described detailed in Sec. 5.Self-Consistency + PH-VC (SC + VC) The combination of SC and PH-VC is simply the average of the two scores.Graph Metrics (Our Method) All the graph metrics are calculated by calling corresponding centrality function in networkx package.We also provide a detailed explanation of the uncertainty-aware decoding methods used in our experiments.Greedy Decoding Greedy decoding is the most naive baseline that generates a response with a temperature of t = 0 for a given input prompt x. This widely acknowledged method produces outputs with high likelihood but does not incorporate any uncertainty estimates.CoVe [36] CoVe is an inference-time decoding method that improves the factuality of generations by self-verification without using any uncertainty estimates. We utilize the code released in this repo: https://github.com/ritun16/chain-of-verification.As the pipeline of UAD described in Sec. 5 involves three steps: Generate claim pool, estimate uncertainty and filter, and merge the claims into a coherent long-form generation. We use the same prompt present in Appx. F for integrating all claims into one sample for all methods.Thus, for each method below, I will talk about the other two steps in details:UAD (SC, Greedy) As discussed in Sec. 5, this method corresponds to Conformal Factuality Decoding [16] , which employs the SC uncertainty estimate to filter out high-uncertainty claims in the claim set obtained from the greedily decoded response. The claim pool is obtained by breaking down the greedy output M t=0 (x), utilizing the break down prompt in Appx. F, and we use SC detailed in Appx. B.1 as uncertainty estimation method. In this work, only experiments that are using Llama-3 involved computing resources. We use two 80G A100 to run inference for Llama-3-70B-Instruct.We present additional experimental results and analyses related to uncertainty estimation. These experiments complement the main experiments discussed in Sec. 6.1 and provide further insights into the performance of different uncertainty estimation methods.To further evaluate the generalizability of our claim-level uncertainty estimation method, we expanded our experiments to include the Natural Questions dataset [38] . Results are presented in Table 3 .Our findings show that the closeness centrality method continues to outperform baseline approaches in most scenarios, aligning with trends observed in our primary datasets. However, we noted a higher rate of false negatives in the auto-annotation process for this dataset compared to others. While this may slightly reduce confidence in these specific results, we believe they remain valuable in demonstrating the potential broader applicability of our method.These results underscore the robustness of our approach across diverse question-answering contexts, while also highlighting areas for potential refinement in auto-evaluation pipelines for future work.To rigorously evaluate the performance differences between our proposed uncertainty estimation method and baseline methods, we conduct a statistical significance check focusing on the two metrics that is reported in Sec. 6.1, AUROC and AUPRC-Negative.We use bootstrapping to generate multiple samples from the original dataset by resampling with replacement. For each bootstrap sample, we calculate the each metric for both the proposed and baseline methods. This results in a distribution of the metric values for each method.Our goal is to validate the effectiveness of our best proposed method. To compare these distributions, we employ the Wilcoxon signed-rank test, a non-parametric test suitable for paired samples. A statistically significant result, indicated by a p-value less than 0.05, would confirm that the performance improvement of our method is meaningful and consistent.After the significance check, all p-values for the three models (GPT-3.5-turbo, GPT-4, and Llama-3-70B-instruct) and two datasets (FactScore and PopQA) are significantly smaller than 0.05 when comparing the proposed method against the baseline methods.To provide a visual comparison of the performance of different uncertainty estimation methods, we present AUROC plots for selected experimental settings. These plots illustrate how our proposed method outperforms the baselines in distinguishing between true and false claims.Figure 5a shows the AUROC curves for the GPT-3.5 model with |R| = 10 on the FActScore dataset. We compare our best-performing graph-based uncertainty estimation method using closeness centrality (C C ) with the baselines, including post-hoc verbalized confidence (PH-VC), self-consistency (SC), and self-consistency combined with verbalized confidence (SC + VC). The plot clearly demonstrates that our method achieves a higher AUROC than all the baselines (and all points are higher), indicating it is more capable to identify false claims.Figure 5b presents the AUROC curves for the GPT-4 model with |R| = 10 on the PopQA dataset. Again, we observe that our method using closeness centrality (C C ) achieves a higher overall AUROC compared to the baselines. Interestingly, while closeness centrality consistently outperforms the SC baseline, the SC + VC method exhibits better performance in the left region of the plot, where the False Positive Rate (FPR) is low. This finding further validates the observation that incorporating VC can potentially enhance the performance of graph-based methods in certain scenarios.In this section, we present additional results for the Uncertainty-Aware Decoding (UAD) experiments, where we include the variant using PH-VC (Post-Hoc Verbalized Confidence) to break ties for the SC (Self-Consistency) scores. While the main experiments in Section 6.2 focused on using IL-VC (In-Line Verbalized Confidence) to ensure a fair comparison with similar inference costs across different methods, here we provide the results using PH-VC for completeness. The results show that UAD (SC + PH-VC, Multi-Sample) achieves a better trade-off between factuality and informativeness compared to UAD (SC + IL-VC, Multi-Sample), especially in the region where more claims are desired. This suggests that using post-hoc verbalized confidence estimates can indeed help to improve the performance of UAD, albeit at the cost of additional inference computation.However, it is important to note that our best graph-based uncertainty estimate, UAD (C C , Multi-Sample), which still dominates the tradeoff between the baselines. This highlights the effectiveness Each plot represents the best performance achieved after hyperparameter tuning at various compute budgets. The x-axis in subplots (a), (b), and (c) represents the computational cost as a multiple of greedy decoding. The y-axes show factuality (accuracy), informativeness (average number of true claims), and their product (a heuristic trade-off metric), respectively. Our method demonstrates Pareto optimality compared to greedy decoding and UAD (SC, Greed) baselines, indicating superior computational efficiency in achieving comparable improvements across different metrics.of our proposed closeness centrality-based uncertainty estimation method in steering the response generation towards more factual and informative outputs.To evaluate the effectiveness and efficiency of our proposed method in improving the quality of LLM's outputs, we conducted an analysis comparing our approach to existing techniques. Our primary goal was to assess the trade-off between computational cost and output quality, focusing on factuality and informativeness. In our analysis, we compared compute costs and quality metrics (factuality, informativeness, and their product as a heuristic trade-off metric) against established baselines such as (SC, Greedy) and greedy decoding. Notably, we excluded baselines with comparable computational costs due to similar graph computation procedures. This decision was based on our previous findings, presented in Figure 3 , which demonstrated that these baselines are outperformed by our method. Since a given compute budget might have different hyperparameter choices, we performed extensive hyperparameter tuning for both our method and the (SC, Greedy) baseline, plotting frontier curves for various configurations.The results of our analysis, illustrated in Fig. 7 , demonstrate that our method consistently outperforms baseline approaches across all metrics, achieving Pareto optimality in the compute-quality trade-off. Ultimately, while our method introduce a higher lower bound of computation, our results underscore the computational efficiency of our approach in achieving comparable improvements across different quality metrics, compared to previous black-box decoding methods.In this section, we provide the definitions of the notations used in Sec. 4.2 for clarity and completeness. Let G = (V, A) denote a graph, where V is the set of nodes and A is the adjacency matrix. The elements of the adjacency matrix A vu indicate the presence of an edge between nodes v and u.The following notations are used in the formulas for the graph centrality metrics in Table 1 :• v: A node in the graph G.• u: Another node in the graph G.• s, t: Source and target nodes, respectively, when considering shortest paths.• σ st : The number of shortest paths between nodes s and t.• σ st (v): The number of shortest paths between nodes s and t that pass through node v.• N (v): The set of neighboring nodes of node v.• λ: The largest eigenvalue of the adjacency matrix A.• d: The damping factor in the PageRank algorithm, typically set to 0.85.• d(v, u): The shortest path distance between nodes v and u.• |V |: The total number of nodes in the graph.• |V v |: The number of nodes in the connected component containing node v.These notations are used consistently throughout the methodology section to define and explain the various graph centrality metrics employed for uncertainty estimation of claims in the bipartite graph representation.In this section, we provide the specific prompts used in our methodology (Sec. 4, Sec. 5) for constructing the semantic entailment graph and performing uncertainty-aware decoding. These prompts are designed to elicit the desired information and behavior from the language model.Given a LM response, the claim decomposition prompt is used to break down the generated response into a set of individual claims. The prompt is the same as the In-Line VC prompt because it decomposes and elicit confidence at the same time. The prompt is as follows:Please deconstruct the following paragraph into the smallest possible standalone self-contained facts without semantic repetition, and return the output as a jsonl, where each line is claim:[CLAIM], gpt-confidence:[CONF].The confidence score [CONF] should represent your confidence in the claim, where a 1 is obvious facts and results like 'The earth is round' and '1+1=2'. A 0 is for claims that are very obscure or difficult for anyone to know, like the birthdays of non-notable people.This prompt is applied to each generated response in the set R to obtain the corresponding set of claims Cr for each response r.Given two sets of claims, the claim merging prompt is used to combine two sets of claims into a single set which is a union set, ensuring that only unique and semantically distinct claims are retained. The prompt is as follows:Given two lists titled "Original Claim List" and "New Claim List", your task is to integrate information from the "New Claim List" into the "Original Claim List". Please follow these detailed steps to ensure accuracy and clarity in the process: Begin with the Verification Process to assess each claim's relevance and uniqueness, followed by the Compilation of Non-Entailed Claims to clearly list any new insights that the "New Claim List" provides.This prompt is used to sequentially merge the claim sets for each response r i ∈ R to accumulatively obtain the final set of claim nodes C.The edge construction prompt is used to determine whether a generated response entails a specific claim, thereby establishing an edge between the response node and the claim node in the bipartite graph. We adapt the prompt from [11] . The prompt is as follows:Context: {generation} Claim: {claim} Is the claim supported by the context above? Answer Yes or No:This prompt is applied to each pair of response r ∈ R and claim c ∈ C to construct the edge set E of the bipartite graph.The claim integration prompt is used to synthesize the selected low-uncertainty claims into a single, coherent output during the uncertainty-aware decoding process, as mentioned in Sec. 5. The prompt is as follows:Task: You are provided with a list of facts about prompt. Your goal is to synthesize these facts into a coherent paragraph. Use all the provided facts where possible, ensuring that no fact is misrepresented or overlooked. If there are redundant facts, choose the most comprehensive one for inclusion. The length of the paragraph should naturally reflect the number of provided facts-shorter for fewer facts and longer for more. Avoid unnecessary filler and focus on presenting the information clearly and concisely.This prompt is applied to the operational subset of claims C o obtained after filtering based on the uncertainty threshold δ to generate the final output M (C o ).These prompts play a crucial role in the construction of the semantic entailment graph and the implementation of uncertainty-aware decoding. By using these prompts, we can effectively leverage the language model's capabilities to extract claims, establish relationships between responses and claims, and generate coherent outputs based on the selected low-uncertainty claims.NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: Our paper focuses on developing methods for detecting non-factual claims and improving the factuality of large language models. As it is primarily methodological research, it does not directly address societal impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Our code is available at https://github.com/Mingjianjiang-1/Graph-based-Uncertainty. 


Decision: The paper introduces a novel method for estimating claim uncertainty in long-form LLM generation using semantic entailment graphs and graph centrality metrics. They also introduce a new decoding approach for long-form generation.  Both methods demonstrate improved performance both in uncertainty estimation and in more accurate generation.  Evaluation is thorough and clear.  Paper is well-written.
The only remaining weakness after the rebuttal/discussion period is computational cost of the method.

Reviews: review: paper_summary: paper_summary: This paper introduces Graph Uncertainty, a novel framework for estimating granular, claim-level uncertainty in long-form LLM outputs using semantic entailment graphs and graph centrality metrics. The authors claim the proposed method can go beyond existing works that can only be applied to multiple-choice questions or their entire generated response. The proposed methods show improvements in claim-level uncertainty estimation and factuality of generated responses. Overall, the paper is easy to follow and comprehensive.
strength_weakness: strength_weakness: 1. The related work section (and possible experiment comparison) lacks some important works. In addition, although various methods are benchmarked, the paper could benefit from additional comparisons with state-of-the-art uncertainty estimation techniques not limited to graph-based methods.
2. The proposed method's graph construction process is computationally intensive and may not be feasible for all real-world applications.
3. The framework assumes claims are largely independent, which might not hold in all real-world scenarios.
questions: questions: 1. The related work section (and possible experiment comparison) lacks some important works [1,2] that leverage the entropy-based framework to decompose the uncertainty of LLM response.  
2. It seems like graph-based uncertainty is another form of variance-based uncertainty estimation.
3. The whole concept of claim extraction seems to create extra work. For some QA tasks, we only need a direct answer, not all the associated replies. Creating the graph would bring lots of computational costs. 
4. The paper primarily uses FactScore and PopQA datasets; more diverse datasets could strengthen the generalizability of the results.


[1] Ling, Chen, et al., "Uncertainty Quantification for In-Context Learning of Large Language Models." (NAACL 2024)  
[2] Fadeeva, Ekaterina, et al. "LM-polygraph: Uncertainty estimation for language models." (EMNLP 2023)
limitations: limitations: N/A
paper_summary: paper_summary: To achieve accurate and fine-grained uncertainty estimation for long-form generation of large language models (LLMs). the authors propose a new framework to measure the uncertainty by building a bipartite graph between the randomly sampled responses from LLMs and the set of the claims within these responses first and then utilizing the existing graph centrality metrics to calculate the uncertainties of each claim. Moreover, the uncertainty metric can further be integrated into the decoding phase of the LLM generation to enhance the factuality of the outputs. Experimental results on two datasets with multiple LLMs show that the proposed method can improve the performance of uncertainty estimation than the baselines with the closeness metric. And the decoding with this metric can achieve a better trade-off between factuality and informativeness.
strength_weakness: strength_weakness: The weaknesses of the paper are listed as follows.    
1. The whole pipeline relies heavily on the LLM for many critical steps such as claim decomposition, causal inference and merging semantically duplicated claims, etc. It can thus cause two main concerns. First, if the LLM is not reliable in any of these steps, then the performance will be significantly degraded. Second, the computational cost is heavy due to the frequent use of LLMs.   
2. According to the experiments, closeness is the most effective metric for uncertainty estimation. Therefore, it would be better if the authors could give more detailed explanations with examples to calculate it in the proposed framework in the section of method.    
3. In the section of related work, the subsection **Granular Uncertainty Estimation** is one type of **Uncertainty Estimation for LLMs**. Therefore, instead of introducing it in a separate subsection, it should be introduced within the section of **Uncertainty Estimation for LLMs**.    
4. It would be better if the authors could evaluate their method on more datasets or at least more samples. Randomly sampling 50 entities is not very convincing for evaluation.
questions: questions: The questions of the paper are listed as follows.   
1. Is this work the first one to formulate the uncertainty estimation as a graph-based problem?  What is the main difference between the pipeline of this work and that of the self-consistency in addition to utilizing different graph centrality metrics?   
2. For uncertainty-aware decoding, is the whole workflow different from the existing works except for the source of the uncertainty metric?   
3. As shown in Figure 4 (b), does it mean that the performance of self-consistency will not change when increasing the number of claim nodes?
limitations: limitations: The authors claim their contributions to the long-form generation. But the claim decomposition is the only step designed specifically for long-form generation. The relationship between the different claims within a single long-form generation is not considered.
paper_summary: paper_summary: In this work, the authors design graph-based uncertainty metrics for long-form generation. Specifically, they sample multiple responses to a query and decompose them into claims. They then create edges between these responses and claims based on their entailment relationships. Using the constructed graph, they found that closeness centrality is the most effective metric for measuring the uncertainty of claims. Additionally, they propose uncertainty-aware decoding (UAG), which enhances the LM’s factuality by filtering out low-confidence claims and reconstructing them into a coherent response.
strength_weakness: strength_weakness: 1. Both the uncertainty estimation method and UAG require multiple samples from the LLM, which is time-consuming and might significantly increase computational cost.
questions: questions: 1. Just want to double check, is C_D equal to Self-consistency?

2. As mentioned in the weaknesses, computational efficiency might be an issue for your method. I suggest the authors add a discussion on this. At least report the additional cost compared with the vanilla LM and the API cost before and after applying your methods.

3. Based on my understanding, in the responses from the datasets used in this paper, there are fewer dependencies between claims. Do you consider other long-form generation tasks where there are more complex inter-sentence dependencies? For example, a QA pair in the ELI5 style:

Query: What’s the purpose of statute of limitations?

Response: Because evidence that might prove the defendant's innocence is lost with time. For example, ask me what I was doing a month ago, and I can probably find something like a bank statement, etc. to show I was at XYZ bar or something. Ask me for something from 2010? That's harder to track down.

This is an example supporting the previous claim, “evidence that might prove the defendant’s innocence is lost with time.”

4. The following related work is missing:

[1] LitCab: Lightweight Language Model Calibration over Short- and Long-form Responses
limitations: limitations: A clear limitation of this work is computational efficiency, which restricts its practical application. Addressing this issue might not be trivial. Another suggestion for future work is that the authors could conduct experiments about how these estimated uncertainties benefit users when they are prompting LLMs.

Comments: title: Express gratitude to reviewer's comment and further clarification
Continuation of the Rebuttal
comment: Thank you for your response! We appreciate your feedback and understand your decision to maintain the original rating. However, we believe there may be some misunderstandings that we'd like to address:

**Computational Efficiency**: It makes sense that future models might get larger but the trend of inference cost is becoming cheaper in general, these subtasks might be completed more efficiently in the future. 

**Inter-Claim Dependency**: A key advantage of our method is its utilization of claim dependencies within long-form generations, which we should have emphasized more clearly in our initial response. In the example that we provided: 

> Consider this example: If Claims A and B are supported by an equal number of generations, but A's co-occurring claims are more corroborated across the graph:
> - Self-consistency (degree centrality) would assign equal scores to A and B.
> - Our method would score A higher, as its two-hop neighbors are more strongly connected.

Claim A will be assigned a less uncertain score than claim B because the other claims in the same long-form generation are more corroborated, even if they appear in the same number of generations. This example conveys a general idea of utilizing "closeness" on the semantic entailment graph: Claims that are less uncertain will result in less uncertain scores in claims from the same generation, which considers the correlation between uncertainty scores between claims within a long-form generation. In terms of the uncertainty estimation method, this also demonstrates where our method differs from previous methods: not only the graph metric, but also the idea that we should utilize the uncertainty from other claims (in both the same and different generations). To our knowledge, no prior uncertainty method has attempted to break down claims from multiple generations and exploit inter-claim relationships in this manner.

We hope this clarification addresses your concerns and better explains our work. We appreciate your time and consideration.
Thanks for the detailed feedback from the authors. The response addresses some of my concerns. However, the issue of the reliance on the performance of LLM in multiple steps is still not addressed. Although the authors claim that applying more capable LLMs can mitegate this issue, it is highly likely to introduce more computational costs. And intensive computational cost is already an issue of this method. Moreover, the main technical contribution is moderate. The main difference from existing works is the different sources of the uncertainty metric. Besides, this work does not consider the relationship between the different claims within a single long-form generation, which is listed by me in the section of limitations. There, I prefer to maintain my original ratings.
### Reliance on LLMs
> *”The whole pipeline relies heavily on the LLM for many critical steps… if the LLM is not reliable in any of these steps, then the performance will be significantly degraded.”*

We acknowledge this in the Limitation section. However, this concern would be less critical as LLMs are rapidly becoming more capable. Most of the current top-performing LLMs, including open-source models, are undoubtedly able to perform these tasks reliably. This issue is expected to further reduce in the future.

### Additional questions & suggestions

> *”Therefore, it would be better if the authors could give more detailed explanations with examples to calculate it in the proposed framework in the section of method.”*

Thank you for this suggestion. We agree that a detailed example would enhance the clarity of our method and will incorporate a more detailed explanation in the Method section of our revised paper. 

> *”Is this work the first one to formulate the uncertainty estimation as a graph-based problem? What is the main difference between the pipeline of this work and that of self-consistency in addition to utilizing different graph centrality metrics?”*

We are indeed the first to utilize the graph information of the relationship between generations and claims. While previous work extends semantic entropy to soft clustering using similarity between different generations [1], our approach differs significantly in graph construction (the whole procedure is different), the graph information utilized (graph information in semantic entailment graph), and the task focus (claim-wise uncertainty estimation). Using graphs is generally a common approach when relationships are involved; thus, the key contributions lie in how the graph is constructed and the specific relationship information it captures. Our work identifies the method to construct the graph and extract uncertainty-related information to improve methods on a general new problem – claim-wise uncertainty estimation. 

[1] Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models. TMLR 2024. 

> *”For uncertainty-aware decoding, is the whole workflow different from the existing works except for the source of the uncertainty metric?”*

The applicability of a wide range of uncertainty metrics is the major difference of our work compared to existing works, a result of our framework's generality that allows for the plug-and-play integration of various claim-wise uncertainty measures. Closest to our work, [2, 3] is only applicable to self-consistency measures. Additionally, [3] differs in its approach by using claims from a single response (despite sampling multiple responses), trading off informativeness. We will elaborate on these distinctions in our related work section.

[2] Wang et al. Fine-grained self-endorsement improves factuality and reasoning. Findings of ACL 2024.

[3] Mohri and Hashimoto. Language models with conformal factuality guarantees. ICML 2024.