Graph-based Uncertainty Metrics for Long-form Language Model Generations
Authors: Mingjian Jiang
Yangjun Ruan
Prasanna Sattigeri
Salim Roukos
Tatsunori Hashimoto
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Uncertainty Estimation; Large Language Model; Factuality
Primary area: natural_language_processing
TL;DR: This paper introduces a new graph-based method to measure uncertainty in black-box large language model outputs at the claim level, utilizing a semantic entailment bipartite graph.

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.

Graph-based Uncertainty Metrics for Long-form Language Model Outputs
Mingjian Jiang
Yangjun Ruan Stanford University ryoungj @stanf edu
Stanford University
j anngmsstanf ord. edu
Prasanna Sattigeri
Salim Roukos
Tatsunori Hashimoto
IBM Research
IBM Research roukosSus. ibm com
Stanford University
psattigdus- ibm. com
thashim@stanfore edu
Abstract
Recent advancements in Large Language Models (LLMs) have significantly improved text generation capabilities, but these systems are still known hallucinate, and granular un- certainty 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 bipartite graph and estimates the claim-level uncertainty with family of graph centrality metries. Under this view, existing uncertainty estimation methods based be viewed as using degree centrality
the concept of self- consistnnst measure, and we show that more sophisticated alternatives such as closeness centrality provide consistent gains claim-level uncertainty estimation. Moreover, we present uncertainty- aware decoding techniques that leverage both the graph structure and uncertainty estimates 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 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
uncertainty
1 Introduction
Large Language Models (LLMs) [155 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 "hallucinations" [6]. which hinders their ability to provide calibrated 10 and factual [1 12] responses and ultimately undermines the trust users place in their outputs. Improving uncertainty estimation techniques is erucial 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 estimating the uncertainty of their answers multiple-choice questions [3 or their entire generated responses (typically in short form) [8. [4, g 15), they often not sufficiently informative in real-world applications where LLMs generate paragraphs of texts consisting a mixture true and false claims [1]. 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 [6] attempt to measure the uncertainty of each claim by its consistency with randomly sampled responses based on the concept of ceffcconsstency [17]. However, they do not fully leverage the semantic relationships between claims and responses that could support more granular uncertainty estimation.
Our code is available at
hacerrppp--beeed---eetttannn Uncertainty
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(b) Claim Decomposition
poouuli, comanee fiod repullior....
Claim-level uncertainty
estimation with graph contrality
(o) Response Sempling
LLM
Response Bet
Clatm Set
X
City shadier vas an Kuil slla periiaa sird sarveda the bnstrral tiee artery tas m1st
Smooder was in Australaa lickan
Contrality Metrios
Liberal
Tel maia pangraph
LLM
Uegree PageRank Closarees
B Geodden
Ho elected AUS Pariament
inadiss
rols, eludled lau calon artaring pullica saccdd fadiaren 1861 sstred
He was born in Parther in1828
x
Graph Construction
LUM
joury caporrddiyytee
Jesponenj]
Graph Uncertainty for claim-level uncertainty estimation. We first sample several responses from LLMs (a) and decompose each response into atomic claims (b) following Sec. [.1 The key components are the construction of bipartite graph that captures the relations between responses and claims (c) and the use of graph centrality metries to estimate the uncertainty of each claim. We simplify the pipeline and prompt for presentation, see Appx. F for details.
Figure 1:
We introduce Graph Uncertainty (Fig. T. framework for granular, claim-level uncertainty estimation for LLMs which utilizes the fine-grande 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 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 (1 that measure the 'importance' of each claim node within the graph. A notable example the existing uncertainty estimates based on the concept of self- celiisensiy [17 [T], which turns out to be 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 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 [ 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 idcas 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.
2 Related Work
Short-form uncertainty estimation in LLMs Existing approaches for characterizing the uncertainty of LLMs have largely focused multiple-choice classification or short-form generation setups and

---

can be categorized into likelihood-based [3] 7 24 9]. consistency/enseebleebass [T0] 25 and verbalizer-basee [4 [5] methods. In this line of work, Kadavath et al. [8] transforms uncertainty estimation into binary classification task to estimate the probability of whether sample is true or not. Kuhn et al. 9 proposes to estimate the 'semantic entropy' of the sample distribution given 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. [0O] proposes a framework for systematically evaluating verbalizer and consistency strategies of eliciting confidence scores for black-box LLM, without access to model parameters activations. Our work is distinct from these existing works in our focus on the long-form setting, which requires uncertainty estimation at more granular level.
Granular uncertainty estimation 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
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. [[]] 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 [] performs uncertainty estimation at the claim level, combining a selff-consistency style technique with conformal prediction. However, these works purely rely the sample- sufficiently capture the semantic relationships between claims and responses. Our work improves granular uncertainty estimation by considering more fine- aineggained semantic information contained in the entailment graph and its associated centrality measures.
technique [TT) that may not
Factuality of LLMs 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 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, Co [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. (3 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.
3 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 long-form output is factual. Specifically, let denote the set of all characters and E the space of all possible text strings. Given a text prompt E V,, the generation process of a model .M with specified temperature T can be represented as a conditional probability distribution M-=x(-12) over Σ*
Uncertainty estimation for LLMs In the context of LLMs, uncertainty estimation is concerned with the following: given model M, a prompt x E Σ", and a response y E Σ", we seek an uncertainty function U Σ* x E* - R that measures the uncertainty of LLMs about the response. In this work, we define the efficacy of U by how effectively 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 decoding- time intervention.
Claim-level uncertainty estimation In many practical applications, the outputs from an LLM encompass few paragraphs of text containing multiple claims 16]. We consider a claim to be the smallest semantically distinct unit of information presented within the generated output. For example, in Fig. [ "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 then U Σ* x E + R, allowing for granular analysis of factuality at the claim level.
3

---

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-consistency- based estimate corresponds to the specific case of using the degree centrality. V and are the node set and adjacency matrix of the graph G. A full definition of the notations is provided in Appx. F
Metric
Formula
Brief Explanation
Degree
Cn(e) Euev Ann
Number of edges incident node
Betweenness Cn(v) = Esprptt Cat(u)
Fraction of shortest paths dur between other nodes s, & that pass through a node v
Importance of node e measured by the impor- tances its neighboring nodes N(v)
Eigenvector Cε(v)= = Enen())) Ce(u)
PageRank
CrR(v) |vi d ()
Cpglu) M(a)
Stationary distribution a random walk within the graph with restart. d is the damping factor.
Closeness
Cc(v)
IV1-1 Envevdlun d(w,u)
IVI 16
Reciprocal of average shortest path distance to all nodes
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 E C directly, based on the prompt E Σ". The uncertainty is quantified by parsing the verbalized confidence expression "very confident". "onfident"""1000""""" "100%" etc.) and mapping it to a numerical value.
Self-consistency (SC) [17 10, [1] based approaches involve checking the claim e (typically decomposed from the greedily decoded output Mr=o(x)) against a set of sampled responses ]EE[N] where y()) MM=-(-lax) a higher temperature / 0. The uncertainty estimate
R- (r(()) J(ENN of is typically calculated by the proportion of responses r" that entail (denoted by +) the claim c, where N is the total number of generated responses. Formally, the consistency score for claim can be expressed as SC(c) N Σm 1pr()) = 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.
4 Claim-Level Uncertainty Estimation with Semantic Entailment Graphs
Our motivation stems from the observation that given set of generated responses R and their entailed claims C, we can construct bipartite graph G = ((R,C), E)) between R and C with edges & indicating the entailment relationship between each response and claim (Fig. D. 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. motivating example is SC, which turns out to be special case of calculating the degree centrality of each claim node as their uncertainty. This encourages the investigation of 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.I and then describe the graph metries we are exploring in Sec.
4.1 Semantic Entailment Graph Construction
Here we describe the procedure for constructing a bipartite graph G = (R,C),& that captures the generation-claie relationships for a given input using an I.I.M, as illustrated in Fig. [ The graph construction involves multiple LLM interactions, with detailed prompts provided in Appx. F

---

Figure 2: Our uncertainty-aware decoding framework. Based on our claim-wise uncertainty esti- mates obtained from Fig. | we keep low-uncertainty claims above a certain confidence threshold and use LLMs to synthesize them into a coherent response. Varying the threshold enables us to balance fac- tuality and informativeness.
Uncertainty-Awar Decoding
jorompt,
syetthestee
these facts imo cohanent paogmeph Use provited tacts...
Claim
LLM
Sreccen was an Australian politician
Ho was the lead the Libaral Party
ly trnckln Auatrala pullicter vilu actoed the leader Libeal Party and was Ausmaier for Parlanent He was boes Hertien 1926
Hi was eeected to the AUS Parfiament
Ho born Parthin In1926
threshold
Bnaaddnn passed way
Ho majored In oconomics
Step 1: Response sampling (R) Given an input prompt z, we follow the same procedure as SC [T]] to generate set of [R] responses from the LLM, including one greedily decoded response Mr= and [R] -1 responses from Mr=r(-))). This process produces a set of generated responses R = +0=(MMpp (MT=o(=), M (x), M (
(x)}. (x)).
Step 2: Claim decomposition and merging (C) We select subset Rx C R of N responses from R. For each response r E RN. we first prompt the LLM to decompose r into a set of claims, denoted Cr. 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 union function M P(C)= P(e) - P(C), which takes two claim sets C()) C((2) and merges them according to their semantic meaning. This is approximated by prompting the LLM to evaluate whether each claim in ((2) is entailed by any claim in C()) 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 union of all claims in Rx, i.e., final set forms our set of claim nodes C = -((N)
C(I) Cr,, c(+) MM((i-)), C..) for i E N) where ri E Rv. The
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 E R and a claim e E C is established if r entails c. The entailment relation determined by prompting the same LLM M, following the procedure in
4.2 Uncertainty Estimation with Graph Centrality Metrics
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' claim node is to other nodes in the graph, the more likely the claim to hold true. Drawing on this premise, we explore broader family of graph centrality metrics [18 21 that measure the importance of claim node within the graph from different angles, some of which may correlate with the factuality of the node to 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 [ These include the betweenness CB. eigenvalue Cg, PageRank CPR, and closeness centrality Cc- A full definition of the notations is provided in Appx. E Note that we use the Wasserman and Faust (WF) improved formula (00 for closeness centrality 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 priori which types of centrality Therefore, we carefully study all of these centrality metrics in various settings in our experiments (Sec. (..). 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 identify the most empirically effective centrality metric for uncertainty estimation at the granularity of claims.
useful for uncertainty estimation.
5
Uncertainty-Awan Decoding
We have introduced 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-enhancin decoding [6 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 single output,
5

---

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 æ, generate a candidate claim set C. for the final output, along with their uncertainty estimates Uxx c), Ve E 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 5 E R. This creates an operational subset of C, C {c E C)U(,,c) c) 8), containing claims with low uncertainties. The threshold ò can be selected either heuristically in an unsupervised manner or based on percentile g over training data claims, where the latter approach provides correctness guarantees with factuality probability levels determined by [6]. Following the supervised approach, we determine ò by selecting 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") 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 approach provides favorable factuality-informative informativenesss tradcoffs, 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.
Experiments
In Sec. 6.1 we benchmark our proposed graph-based metrics and existing methods adapted for fliimwwis uncertainty on two long-fon form factuality datasets, demonstrating the effectiveness of closeness centrality as reliable uncertainty measure. In Sec. 6.2] we show that applying the closeness centrality metric with our uncertainty-awan seeermaaivveees-aactaaaal 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.
decoding framework demonstrates the best
6.1 Uncertainty Estimation
In this subsection, we empirically analyze different graph centrality metrics for uncertainty estimation and systematically benchmark existing methods adapted for claim-wiss uncertainty estimation.
Datasets and annotation We evaluated the different uncertainty estimation methods two chal- lenging 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, randomly sampled 100 entities and generated a set of claims about each entity with their uncertainty estimates using our
pipeline described in Sec. [.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.
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, employed a similar pipeline to the one in their paper, classifying them as True, False, or Subjective using LLMs conditioned the corresponding Wikipedia article. We specifically used GPT-4-Turbo due to its low classification error rate.
Long-form PopQA (2 comprises of entities covering 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 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 higher rate of false negatives in the auto-annotation pipeline compared to the aforementioned datasets, we have included these results in Appx. C.I

---

Table Our claim-level uncertainty estimate based on the closeness centrality metric consis- tently and significantly outperforms baselines. We assess the AUROC (ROC) and AUPRC-Negation (PRC) to compare baselines and different centrality metrics (Table) with the number of samples [R] E (5. 10] on the FactScore and PopQA datasets. Results with statistically significant gains are bolded. All p-values are significantly less than 0.05 through a pairwise significance test detailed in
Appx. C.2 Each setup is annotated as "model, [R]". Abbreviations are used for baselines, as defined
in the baseline discussion, and for centrality metrics, as defined in Sec. 4.2
Setup Metric
GPT-3.5, 5
GPT-3.5, 10
GPT-4,
GPT-4, 10
Llama-3, 5 ROC
Llama-3, 10
ROC PRC
ROC
PRC
ROC
PRC
ROC
PRC
PRC
ROC
PRC
IL-VC
0.537
0.437
0.537
0.437
0.540
0.394
0,540
0.394
0,536
0.486
0,536
0.486
PH-VC
0.748
0,641
0.748
0,641
0.701
0.531
0.701
0.531
0.675
0.593
0.675
0.593
P(True)
0.609
0.521
0.609
0.521
0.756
0.633
0.756
0.633
0.580
0.500
0.580
0.500
FactScore
SC
0.835
0.726
0.852
0.756
0,812
0.651
0.839
0.708
0.801
0.712
0.829
0.761
SC+VC
0.870
0.781
0.879
0.801
0.827
0.670
0.838
0.701
0.817
0.739
0.833
0.771
Cв
0.765
0.706
0.793
0.731
0.758
0.637
0.780
0.683
0.743
0.695
0.759
0.733
Cg
0.794
0.726
0.809
0.735
0.775
0.623
0.797
0.673
0.732
0.690
0.757
0.722
Crn
0.852
0.776
0.853
0.777
0.791
0.644
0.801
0.675
0.757
0.683
0.764
0.700
Gc
0.892
0.848
0.898
0.859
0.843
0.733
0.855
0.751
0.857
0.837
0.867
0.850
IL-VC
0,508
0.449
0.508
0.449
0.499
0.325
0,499
0.325
0,568
0.473
0.568
0.473
PH-VC
0.623
0.533
0.623
0.533
0.640
0.415
0.640
0.415
0.663
0.556
0.663
0.556
P(True)
0.614
0.656
0.614
0.656
0.642
0.585
0.642
0.585
0.572
0.583
0.572
0.583
SC SC+VC
0.758
0.676
0.789
0.721
0.744
0.516
0.771
0.572
0.735
0.616
0.756
0.652
PopQA
0.778
0.693
0.794
0.716
0.752
0.548
0.762
0.581
0.761
0.666
0.775
0.692
CB
0.650
0.64S
0.683
0.679
0.718
0.514
0.738
0.566
0.702
0.607
0.720
0.638
Cg
0.716
0.666
0.728
0.697
0.703
0.564
0.729
0.604
0.700
0.591
0.725
0.630
OpR
0.734
0.687
0,740
0.713
0.703
0.473
0.723
0,511
0.718
0.617
0.734
0.645
Cc
0.792
0.754
0.809
0.774
0.786
0.668
0.800
0.693
0.772
0.699
0.784
0.713
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 systematic benchmarking of a wide range of methods including:
Post-hoe verbalized confidence (PH-VC) [8] This method is a variant of Verbalized confidence (VC) introduced in Sec. B which elicits the verbalized confidence in post-hoc manner after
the entire claim set C has been decomposed from generations, following Tian et al. [T]].
In-line verbalized confidence (II-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 during Step 2 in Sec. 4.1 and incurs negligible inference overhead in contrast PH-VC.
P(True) g this method elicits the uncertainty estimate of 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 1 as discussed in Sec. 3 this method utilizes the consistency score of one claim across different samples from the same LLM.
PH-VC (SC + VC): 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: between- ness (CB), eigenvalue (Cε), PageRank (CPR), and closeness (Cc). We provide more detailed information about methods and basclines in Appx.
Evaluation metries We assess how well various uncertainty estimation metries 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-Redd for the Negative class AAUPRC-Negative) AUPRC-Negative focuses on the classifier's '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.
Curve
7

---

Figure 3: UAD with better claim- level uncertainty estimates demon- strates better trade-off between factuality and informativeness of the generated responses. We com- pare UAD across different thresh- olds ö and two non-uncertainty de- coding baselines. We assume that random noise applied break ties for each uncertainty method, re- sulting in a horizontal line extend- ing from the leftmost dot to the left. The shaded confidence interval is ob- tained by bootstrapping with confi- dence level of 95%.
Informativeness vs Factuality
1.00
0.95
Precision claims
0.90
0.05
0.80
Greedy Decoding
CoVe
ISC. Greedy!
0.75
UAD (SC. Multi-Sample!
UAD ISC ILVC, Mutti Sample)
(Co.
Mult- Samp-e)mple)
0.70
10
15
20
25
Number true claims
Experimental details Our experiments are conducted on the three most capable LLMs to date (as of June 2024): GPT-3.5-turbo, GPT-4 22, and Llama-3-70B-Instre
[39]. We used the same LLM to sample responses and construct semantic entailment graph for uncertainty estimation as described in Sec. The graph construction is set up follows: To construct the of claims C. we used greedily decoded sample (temperature t 0) and 4 samples with temperature t as Rx. 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 = 1 if needed. The impact of these hyperparameters analyzed Sec. 6.. 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 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-Negaad compared to the SC bascline. To better understand the effectiveness of closeness centrality for uncertainty estimation, we provide an ablation study in Sec. 6.3
Additional analysis Our systematic benchmarking in Table 2 also provides some insights into the effectiveness of baseline methods for claim-level uncertainty estimation:
SC is strong baseline: We find that Self-Consistency (SC) score, which is essentially degree centrality CD, serves as a strong baseline, outperforming all other previous approaches. It some- times underperforms our PageRank centrality metric CpR. but the comparison is sensitive to the specific setup or dataset.
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.
IL-VC usually underperforms PH-VC:
Integrating VC improves SC: We observe that integrating VC into SC can improve its uncertainty estimation in most setups, even when naive addition of their scores (SC + VC) is applied. This probably because VC offers additional information to distinguish claims with tied scores in SC.
6.2 Uncertainty-Awaar Decoding
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.
Experimental setup We tested UAD with our best closeness centrality uncertainty estimate Ce on the FActScore dataset used in Sec. 6. We experimented with GPT-3.5-Turbo that were used for all steps described in Fig. [ aandd 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
Evaluated methods We benchmarked the performance of UAD against several inference-time decod- ing methods. For systematic comparison, we also included inference-time decoding methods that do
8

---

Average Distances betwean Different Claim Pairs
Gae Per Caregery
ABROC
Tue True
AUSOC
Aud Nurrage Oitennss on Groph
2,23
Falce Faise
335
3.1
370
15-GPF33
F3-GPT4
PupGA-GPP-33 1w PopOx4GP-44
Number of samples Cleim Nodes
(a) Average length of shortest paths between claim pairs
(b) Effect of the size of C measured by Rxx
Figure 4: Ablation study: (a) The false claims have greater average distance other claims compared to true ones, indicating the effectiveness of the closeness centrality metric. (b) Performance improves consistently as we increase the number of responses |Rxv used to construct the claim node set C in our uncertainty estimation method. While all evaluations are conducted on the same fixed set of claims, varying |R. alters the graph structure used to estimate these claims' uncertainty values.
not rely on uncertainty estimatiin. For UAD, we evaluated its performance across various uncertainty estimation techniques U and claim candidate set choices C study their impact. Specifically, our evaluated methods include (Appx. B
Greedy Decoding: the most naive baseline that generates response with temperature of t 0 for a given imput prompt æ.
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. [ 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 the previous method, it expands the claim C to in- clude those decomposed from multiple sampled responses R. following our procedure in Fig. 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.I.
UAD (Co, Multi-Sample): it applies our best graph-based uncertainty estimate with the closeness centrality Cc as U, from which we can study how better claim-wise uncertainty estimates may improve the performance of UAD.
Evaluation Metrics 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 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 O, 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 presented in Fig, with factuality on the y-axis and informa- tiveness 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 6, 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 facuualtyyinfrrmattveesss tradeoffs compared 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 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 Cc in Fig. [] find that applying 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 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 8.
best metrie, closeness centrality, also
6.3 Ablation Study
In this section, 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-tum --ttbbb model.
Why is the closeness centrality effective? Closeness centrality is intrinsically related to the distances between nodes in 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 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 i.e., less entailed by generations and having lower co-occurrences with the majority of claims. This insight provides clear explanation for the strong performance of closeness centrality in claim-level uncertainty estimation.
be intuitively interpreted false claims being less centered,
How does the performance change with the number of responses? Fig. 4b explores how the performance changes as we increase the number of responses RN 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 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, attains Pareto optimality for the compute-quality tradeoff compared to existing methods across multiple quality metries. Details are present in Appx. D.2
7 Conclusion
In this work, we propose Graph Uncertainty, a family of graph-based methods for claim-wise wise uncer- tainty estimation in LLM generations. We also present uncertainty-aware decoding framework that integrates these estimates to improve the trade-off between factuality and informativeness. Empirical results demonstrate the effecttivnnes of the proposed approach.
Despite these improvements, we note that the graph construction process increases inference -iree compute and latency. Moreover, our claim decomposition assumes that claims can be decontextualized and separated, which may not always be the case 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.
10

---

References
[1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1 33:1877-1901,, 2020.
[2] OpenAl. Gpt-4 technical report, 2023.
[3] Anthropic. Claude 2, July 2023. URL http://www.attrrrpp....oo//ddeee Accessed: 2023-08-31.
[4] Gemini Team, Rohan Anil, Sehastian Borgeaud, Yonghui Wu, Jean- Bean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023.
[5] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint (rXXi:2307.09288 2023.
[6] Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. arXiv preprint arXiv:2109.0799 2021.
[7] Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How know when language models know? on the calibration of language models for question answering. Transactions of the Association for Computational Linguistics, 9:962-977, 2021.
[8] Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodde Nova DasSarma, Eli Tran-Johnson Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know, 2022.
[9] Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation natural language generation, 2023.
[10] Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li, Jie Fu, Junxian He, and Bryan Hooi. Can lims express their uncertainty? an empirical evaluation of confidence elicitation llms, 2023.
[11] Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models, 2023.
[12] Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen tau Yih, Pang Wei Koh, Mohit Iyyer, Luke Zettlemoyer, and Hannanch Hajishirzi. Factscore: Fine-grained atomic evaluation of factual precision in long form text generation, 2023.
[13] Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. arXiv preprint arXiv:2003.07892. 2020.
[14] Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words, 2022.
[15) Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D. Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback, 2023.
[16] Christopher Mohri and Tatsunori Hashimoto. Language models with conformal factuality guarantecs, 2024.
[17] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023.

---

[18] L Freeman. Centrality in networks: I. conceptual clarifications, social networks. Social Network, 10:0378-877 87738--73,,11 1979.
[19] Phillip Bonacich. Power and centrality: A family of measures, American journal of sociology, 1987.
[20] Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications. 1994.
[21] Stephen P Borgatti. Centrality and network flow. Social networks, (7(1):55-71,200)
[22] Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Ha- jishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories, 2023.
[23] Ante Wang. Linfeng Song, Baolin Peng, Ye Tian, Lifeng Jin, Haitao Mi, Jinsong Su, and Dong Yu. Fine-grained self-endorsement improves factuality and reasoning. arXiv preprint arXiv:2402.15631, 2024.
[24] Andrey Malinin and Mark Gales. Uncertainty estimation in autoregressive structured prediction, 2021.
[25] Mingjian Jiang, Yangjun Ruan, Sicong Huang, Saifei Liao, Silviu Pitis, Roger Baker Grosse, and Jimmy Ba. Calibrating language models via augmented prompt ensembles. 2023.
[26] Ari Holtzman, Peter West, Vered Shwartz, Yejin Choi, and Luke Zettlemoyer. Surface form competition: Why the highest probability answer isn't 't always right. arXiv preprint arXiv:2104.08315. 2021.
[27] Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Generating with confidence: Uncertainty quantification for black-box large language models, 2023.
[28] Jinhao Duan, Hao Cheng, Shiqi Wang, Alex Zavalny, Chenan Wang, Renjing Xu, Bhavya Kailkhura, and Kaidi Xu. Shifting attention to relevance; Towards the uncertainty estimation of large language models, 2023.
[29] Neil Band, Xuechen Li, Tengyu Ma, and Tatsunori Hashimoto. Linguistic calibration of long-form generations, 2024. URL https::t:////xa org/ /aw.ab/...0000000
[30] Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, -ran-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego de Las Casas, Aurelia Guy, Jacob Menick, Roman Ring, Tom Hennigan, Saffron Huang, Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Paganini, Geoffrey Irving, Oriol Vinyals, Simon Osindero, Karen Simonyan, Jack W. Rae, Erich Elsen, and Laurent Sifre. Improving language models by retrieving from trillions of tokens, 2022.
[31] Jiarui Li, Ye Yuan, and Zehua Zhang. Enhancing Ilm factual accuracy with rag to counter hallucinations: case study on domain-specific queries in private knowledge- 2024.
[32] Nañis Sadeq, Byungkyu Kang, Prarit Lamba, and Julian McAuley. Unsupervised improve- ment of factual knowledge in language models. In Andreas Vlachos and Isabelle Augen- stein, editors, Proceedings of the 17th Conference of the European Chapter of the Asso- ciation for Computational Linguistics, pages 2960-2969, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics. doi: 10. 10.18653/v1/2023.eaa 15t.:/202...lllmmim115....... URL
https://aclanthologyy org org/2022 2023 eacl-main 215
[33] Nayeon Lee, Wei Ping, Peng Xu, Mostofa Patwary, Pascale Fung, Mohammad Shoeybi, and Bryan Catanzaro. Factuality enhanced language models for open-ended text generation, 2023.
[34] Katherine Tian, Eric Mitchell, Huaxiu Yao, Christopher D. Manning, and Chelsea Finn. Fine- tuning language models for factuality, 2023.
[35] Oded Ovadia, Menachem Brief, Moshik Mishaeli, and Oren Elisha. Fine-tuning or retrieval? comparing knowledge injection in Ilms, 2024.
12

---

[36] Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston, Chain-of-verificatton reduces hallucination large language models, 2023.
[37]
Yung-Sung Chuang, Yujia Xie, Hongyin Luo, Yoon Kim, James Glass, and Pengcheng He. Dola: Decoding by contrasting layers improves factuality in large language models, 2024.
[38] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming- Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association of Computational Linguistics, 2019.
Ming-Wei
[39] Meta Al. Introducing meta Ilama 3: The most capable openly available I1m date. https 7/ai meta. com haaem//log//nee meta- 11ama-3ammm 3/, 2024. Accessed: 2024-05-13.
13

---

A Data and Annotation Details
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. 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.
FActScore
Long-form PApQA Dataset We also incorporated the PopQA dataset (22]. which comprises entities covering 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 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 their comprehensive coverage of the entity.
For both datasets, we employed a two-stage annotation process. First, we used pipeline generate claims for each sampled entity. Second, we assessed the factuality of the generated claims using the following criteria:
Annotation Process
True: The claim factually accurate and supported by the information provided in the corre-
sponding Wikipedia page.
False: The claim factually incorrect or contradicts the information provided in the corresponding Wikipedia page.
Subjective: The claim subjective, chinion-basede 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 large number of claims while maintaining a high level of accuracy.
B Baselines Details
Verbalized confidence (VC): As introduced in Sec. this method involves prompting the LLM to express its confidence in a claim e 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 given multiple options such as "Very good chance (80%)", "Little chance (20%)" etc.
In-line verbalized confidence (IL-VC) [6) This a straightforward variant of PH-VC, which directly clicits the verbalized confidence about each claim e in an in-line manner right after it is decomposed from the generations during the Step 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.
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 being true as the confidence score. Since the likelihood scores are not available for most close-source black-box LLMs, we modified estimate the likelihoods by sampling multiple times from the I.LMs.
P(True) 88:
As discussed in Sec. 3 this methods utilizes the consistency score of one claim across different samples from the same LLM.
Self-Consister (SC) 17
+ 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 straightforward variant of SC by integrating the PH-VC to break such ties, which serves as strong baseline in our experiments.
14

---

B.1 Uncertainty Estimation Experiments
This section aims to provide comprchensive 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, aim to ensure the reproducibility and transparency of our experimental setup.
Assume that we have a claim to estimate uncertainty and and an entity of claim.
Post-hoc Verbalized Confidence (PH-VC) This method elicits verbalized confidence
post-hoc manner after the entire claim set 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 "Very good chance (80%)", "Little chance (20%)" etc. The specific prompt that we use is as following:
You provided with some possible information about 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. example:
For
<description confidence, without any extra commentary whatsoever; just short phrase!>
Confidence:
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-V 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
smallest possible following paragraph into
standalone self-come self-contained facts without semantic repetition, and return the output as jsonl, where each line claim: [CLAIM], ipt-coofideenc: [CONF]
The confidence score [CONF] should represent your confidence the claim, where 1 is obvious facts and results like 'The earth round? and '1+1=2'. difficult for anyone to know, like the birthdays of non-notable people. The input is: flong-form generation]
is for claims that are very obscure or
P(True) The P(True) method estimates the uncertainty of claim by prompting 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 not available for most closed-source black-box LLMs, modified the method to estimate the likelihoods by prompting the model 10 times and frequency of answering True. The specific prompt that adapted from g is follows:
The following claim is about entity. Is the claim true false? (Answer with only one word True/False) Claim: {claim}
15

---

Self-Con Coffissesste (SC) The Self-Consisteney (SC) method utilizes the consistency score of one claim across different samples from the same LLM. As discussed in Sec. 3l equivalent the degree of claim on the bipartite semantic entailment graph. The whole pipeline used to construct the graph described detailed in Sec.
Coff--sssstency + PH-VC (SC+ + VC) The combination of SC and PH-VC simply the average of the two scores.
Graph Metrics (Our Method) All the graph metries calculated by calling corresponding centrality function in networkx package.
B.2 Uncertainty-Aware Decoding
We also provide detailed explanation of the uncertainty-aware decoding methods used in experiments.
Greedy Decoding Greedy decoding is the most naive baseline that generates response with temperature of L for given input prompt æ. This widely acknowledged method produces outputs with high likelihood but does not incorporate any uncertainty estimates.
Co'Ve [36] CoVe is 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///ittub..co//ituu htt.:///.oooottuuucccoccoooooooo 16Cchain-of-verrficatto
UAD Methods
As the pipeline of UAD described in Sec. involves three steps: Generate claim pool, estimate uncertainty and filter, and merge the claims into 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 [6],, which employs the SC uncertainty estimate to filter out high-uncertainty claims the claim set obtained from the greedily decoded response. The claim pool is obtained by breaking down the greedy output M=), utilizing the break down prompt in Appx. and we use SC detailed in Appx. B. as uncertainty estimation method.
UAD (SC, Multiple-Sample), UAD (IL-SC, Multiple-Sample), UAD (Cc, Multiple-Sample) Similar to the UAD (SC, Greedy) setting, the claim pool is obtained by using R to construct candidate claim C as discussed in Sec. [.1] Then, we use respectively use SC, Cc. SC + IL-VC detailed in Appx. B. as uncertainty estimation method.
B.3 Computing Resources
In this work, only experiments that are using Llama-3 involved computing resources. We use two 80G A100 to run inference for Llama-3- 7-0---nnstuucc
C Additional Results for Uncertainty Quantification
We present additional experimental results and analyses related to uncertainty estimation. These experiments complement the main experiments discussed in Sec. S provide further insights into the performance of different uncertainty estimation methods.
C.1 Natural Question Dataset
To further evaluate the generalizability of our claim-level uncertainty estimation method, 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 outperform baseline approaches most scenarios, aligning with trends observed our primary datasets. However, we noted higher rate of false negatives in the antooanntttioon process for this dataset compared to others. While
16

---

Table 3: Additional Results on Natural Question Datasets: Our claim-level uncertainty estimation method outperforms baseline approaches across most scenarios, maintaining comparable results in others, with a single exception noted.
Setup Metric
GPT-3.5, 5
GPT-3.5, 10 ROC
GPT-4,
GPT-4,
Llama-3, 5
Llama-3, 10
ROC
PRC
PRC
ROC
PRC
ROC
PRC
ROC
PRC
ROC
PRC
IL-VVC
0.536
0.228
0.536
0.228
0.674
0.318
0.674
0.318
0.539
0.252
0.539
0.252
NaturalQ
PH-VC
0,536
0.228
0,536
0.228
0.452
0.176
0.452
0.176
0.465
0.206
0.465
0.206
SC
0.674
0.352
0.683
0.380
0.731
0.384
0.751
0.412
0.737
0.387
0.735
0.353
SC+VC
0.670
0.341
0.677
0.356
0.596
0.280
0.607
0.293
0.634
0.295
0.633
0.268
Cc
0.666
0.38
0.682
0.408
0.734
0.413
0.752
0.439|
0.736
0.432|
0.746
0.403
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-answerrigg contexts, while also highlighting areas for potential refinement in auto-evaluation pipelines for future work.
C.2 Statistical Significance Check
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, calculate the each metric for both the proposed and baseline methods. This results 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, non-parametric test suitable for paired samples. A statis- tically significant result, indicated by a p-value less than 0.05, would confirm that the performance improvement of our method meaningful and consistent.
After the significance check, all p-values for the three models (GPT-3.5-turbo, GPT-4, and Llama- -rtBt-inttuuct) and two datasets (FactScore and PopQA) are significantly smaller than 0.05 when comparing the proposed method against the baseline methods.
C.3 AUROC Plots
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 proposed method outperforms the basclines 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-basee based uncertainty estimation method using closeness central- ity (Cc) 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 higher AUROC than all the baselines (and all points are higher), indicating is more capable to identify false claims.
Figure 5b presents the AUROC curves for the GPT-4 model with | = 10 on the PopQA dataset. Again, we observe that our method using closeness centrality (Cc) 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 certain scenarios.
D Additional Results for Uncertainty-Aware Decoding
D.I Additional Results on the Plot
In this section, we present additional results for the Uncertainty-Aware Decoding (UAD) experiments, where we include the variant using PH-VC HPost-Hoc Verbalized Confidence) to break ties for the
17

---

1.-
0.5
0.6-
0.2
auced, 772 suprewd supriceed sumcc-0
C. suema axprent supre amo aumoemo
auc-0.031 suprowo 28, ni0.775, sumcc=0,320
02-
PHAC,, sureo 403 suprewd, auper nno sumce-Ad1le
Sc. asem0.222 auprema aes, super, pon rwa, aumoembure
SC+VC, wsc 086, sucremd.368 supre sm0.839, 207
Ca 200-0399, sugroeceess aup "_nnssss sumee- 2.55s
SCHME, autoo suprc-ou/te /on, supte twa.ss surcc-0..a25
(a) AUROC curves for the GPT-3.5 model with [ 10 the FActScore dataset. Our method using close- ness centrality (Cc) outperforms baselines.
(b) AUROC curves for the GPT-3.5- model with on the PopQA dataset.
R
SC (Self-Consistency) scores. While the main experiments in Section 6.2 focused on using IL-VC (In-Line Verbalized Confidence) ensure fair comparison with similar inference costs across different methods, here we provide the results using PH-VC for completeness.
Informativeness vs Factuality
1.00
0.95
0.90
Factuality
0.85
0.80
X
Greedy Decoding
CoVe
UAD (SC, Greedy)
0.75
UAD (SC, Multi-Sample)
UAD (SC IL IL-VC, Multi-Sample)
(C., Multi-Sample)
0.70
0
10
20
25
Informativeness
Figure 6: UAD results with PH-VC included for breaking ties in the SC scores. The plot shows the trade-off between factuality and informativeness for various UAD variants and baselines.
Figure presents the updated plot, which includes the additional UAD variant:
UAD (SC PH-VC, Multi-Sample): This method is similar to UAD (SC + IL-VC, Multi- Sample), but it uses PH- VC instead of IL-VC to break ties for the SC scores. As Sec. 6.1 shows, PH-VC achieves better performance on the two datasets than IL-VC.
The results show that UAD (SC+ + PH-VC. Multi Multi-Sample) achieves a better trade-off between factuality and informativeness compared UAD (SC + IL-VC, Multi-Sample especially in the region where more claims are desired. This suggests that using post-hoe verbalized confidence estimates can indeed help to improve the performance of UAD, albeit the cost of additional inference computation.
However, important note that our best graph-based uncertainty estimate, UAD (Cc, Multi- Sample), which still dominates the tradeoff between the baselines. This highlights the effectiveness
18

---

0%s Mudi-Sample
Groedy
Compute Factusiity
Compute vs Informativeness ess
Compute vs factuality Informativeness
Factualitt Informativeness E
6.25
ApD Number of Thuc Claims
6.00
12
150
Computo
Compute
Compute
Figure 7: Computational Cost Analysis of End-to-end Decoding Pipelines. 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 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.
D.2 Computation Analysis
To evaluate the effectiveness and efficiency of our proposed method in improving the quality of LLM's outputs, 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. 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 byperparameter choices, we performed extensive hyperparameter tuning for both our method and the (SC, Greedy) baseline, plotting frontier curves for various configurations.
our analysis, we compared compute costs and quality metries (factuality,
The results of analysis, illustrated in Fig. demonstrate that our method consistently outperforms baseline approaches across all metrics, achieving Pareto optimality in the compute- comute--uality 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.
E Notation Definition
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 nodes and A is the adjacency matrix. The elements of the adjacency matrix Aru indicate the presence of an edge between nodes and u.
The following notations are used in the formulas for the graph centrality metrics in Table
s: node in the graph
w: Another node in the graph G.
8, t: Source and target nodes, respectively, when considering shortest paths.
dxt The number of shortest paths between nodes and t.
aec()) (v): The number of shortest paths between nodes and t that pass through node
N():: The set of neighboring nodes of node
19

---

X: The largest eigenvalue of the adjacency matrix A.
d: The damping factor in the PageRank algorithm, typically set to 0.85.
d(e, u): The shortest path distance between nodes v and
[V] The total number of nodes in the graph.
[Vo]: 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.
F
Prompt Details
In this section, we provide the specific prompts used in our methodology (Sec. Sec. 55) for constructing the semantic entailment graph and performing uncertainty-awar decoding. These prompts are designed to elicit the desired information and behavior from the language model.
F. Claim Decomposition Prompt
Given a LM response, the claim decomposition prompt is used to break down the generated response into of individual claims. The prompt the same the In-Line VC prompt because decomposes and elicit confidence at the same time. The prompt is as follows:
Please deconstruct the following paragraph into the smallest possible facts without semantic repetition, and return the output as a jsonl, where each line is claim: [CLAIM), gpt-confidence: [CONF]
standalone
The confidence score [CONF] should represent your confidence in the claim, where 1 is obvious facts and results like 'The earth round' and '1+1=2'. difficult for anyone to know, like the birthdays of non non-notable people. The input is: flong-form generation]
is for claims that are very obscure or
This prompt is applied each generated response in the set R. obtain the corresponding set of claims Cr for each response r.
F.2
Claim Merging Prompt
Given two sets of claims, the claim merging prompt is used to combine two sets of claims into single set which a union set, ensuring that only unique and semantically distinct claims are retained.
The prompt is follows:
Given two lists titled "Driginal Claim List" and "New Claim List", your task
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:
Task 1. #*Verification Process:** Your goal is to go through each statement in the "New Claim List" one by one, and determine if it is fully entailed or mentioned by any statement in the "Driginal Claim List."
Task **Compilation Non Non-Entailed Claims:** Generate list statements from the "New Claim List" that are not already covered or implied by the "Original Claim List." " each new or unique claim that does not have an equivalent in the original list, format your output by starting each line with dash (1-?). #*Original Claim List:**
(elaim_listil
**New Claim List:** (claim_list2)
20

---

Begin with the Verification Process to assess each claim's relevance and uniqueness, followed by the Compilation of Hon-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; R to accumulatively obtain the final of claim nodes C.
F.3 Edge Construction Prompt
The edge construction prompt used to determine whether generated response entails a specific claim, thereby establishing edge between the response node and the claim node in the bipartite graph. We adapt the prompt from [1] 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 cach pair of response R and claim e C to construct the edge set & of the bipartite graph.
F,4
Claim Integration Prompt
The claim integration prompt is used to synthesize the selected low-uncertainty claims into a single,
coherent output during the uncertainty-awee aware decoding process, as mentioned in Sec. The prompt is as follows:
Task: You are provided with a list of facts about prompt. Your goal is to synthesize these facts into 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 provided facts-shorter for fewer facts and longer for more. Avoid unnecessary filler and focus on presenting the information clearly and concisely. The facts:
{claim_list]
This prompt applied to the operational subset of claims Co obtained after filtering based on the uncertainty threshold generate the final output M (C").
These prompts play a crucial role in the construction the semantic entailment graph and the implementation of uncertainty-aware decoding. By using these prompts, the language model's capabilities to extract claims, establish relationships between responses and claims, and generate coherent outputs based the selected low- oww-uncrrtainty claims.
effectively leverage
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction can be validated by the content in Sec. 4 Sec. ald Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We discussed the limitation of our approaches within Sec.
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-speciffiationn 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., 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or 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 grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't it 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.
3. Theory Assumptions and Proof's
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, theoretical assumptions or proofs are not applicable.
22

---

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 provide short proof sketch to provide intuition.
Inversely. any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that 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 Sec. and Sec. 5 the experiment details in Sec. in the main paper, long as baseline details in Appx. prompt details in Appx. F data and annotation detials in Appx. A, additional notation Appx.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data provided not.
If the contribution is 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary 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 replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 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 way to access this model for reproducing the results or a way to reproduce the model (e.g.. with open-source dataset instructions for how construct the dataset).
new model (e.g., large language model), then there should either be
(d) We recognize that reproducibility may be tricky in welcome to describe the particular way they provide for reproducibility. In the case of closed- source models, it may be that access to the model is limited in way (e.g.. registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
cases, in which case authors
5. Open access to data and code
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.
23

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (lttpss://nips.cc/ppllll
Galldes/Coeeubmicc wtw.uumiisssoooooioi...........e onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurIPS code and data submission guidelines (https: //tips.cc/publlcgguuuiees/////// Sewiiideee//oSSSummmmeae wwtoomsssionooo sooolliccy för more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
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, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined 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
Guidelines:
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, 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 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 the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
24

---

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). error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
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 experi- ments?
Answer: [Yes]
Justification:
We include the information of computing resources in Appx. B.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS http://wwwrr...coooo/occcccccaca
Code of Ethics
Answer:
[Yes]
Justification: This research will not cause any potential harms any potential deviation from the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
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 societal impact of the work performed. If the authors answer NA No, they should explain why their work has societal impact 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., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will foundational research and not tied par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
25

---

The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
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 MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have 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 uncertainty and improve the generations. There's such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 usage guidelines or restrictions access the model 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 best faith effort.
12. Licenses for existing assets
Question: Are the creators 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 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, paperswi thcode. 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 encouraged reach out the asset's creators.
13. 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 well- documented codebase once ready.
Guidelines:
26

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their sub- missions 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not provide crowdsourcing nor research with human subjects. All the involved human annotation conducted by the authors.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human Subjects
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 your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not provide crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
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 include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
27


Reviews:
[{"review_id": "rSCNfEFVHJ", "reviewer": "Reviewer_29kR", "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.", "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.  \n2. It seems like graph-based uncertainty is another form of variance-based uncertainty estimation.\n3. 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. \n4. The paper primarily uses FactScore and PopQA datasets; more diverse datasets could strengthen the generalizability of the results.\n\n\n[1] Ling, Chen, et al., \"Uncertainty Quantification for In-Context Learning of Large Language Models.\" (NAACL 2024)  \n[2] Fadeeva, Ekaterina, et al. \"LM-polygraph: Uncertainty estimation for language models.\" (EMNLP 2023)", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of graph-based uncertainty metrics for claim-level analysis is novel and addresses a critical gap in LLM uncertainty estimation.\n2. The use of various graph centrality metrics to assess claim importance and uncertainty is interesting and systematically explored.\n3. The integration of uncertainty estimates into decoding processes shows practical applications, improving the reliability of LLM outputs.", "weaknesses": "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.\n2. The proposed method's graph construction process is computationally intensive and may not be feasible for all real-world applications.\n3. The framework assumes claims are largely independent, which might not hold in all real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and suggestions. We appreciate that you acknowledge our work is “novel and addresses a critical gap in LLM uncertainty estimation”. We would like to address your remaining questions and concerns in the following response.\n\n### Computational cost\n> *”The proposed method's graph construction process is computationally intensive and may not be feasible for all real-world applications.”*\n\nWe agree that the computation overhead is the major limitation of our method. However, we would like to emphasize that our method offers a desirable option for utilizing more inference-time compute to improve the quality of LLMs’ responses. More importantly, our new results demonstrate that ***our method archives the Pareto optimality for the compute-quality tradeoff*** compared to existing methods.\n\n**Pareto optimality** We calculated the compute cost and various quality metrics (including  ‘factuality’, ‘informativeness’, and the combined metric ‘ factuality x informativeness’ ) of our method and baseline method. We conducted a comprehensive analysis by tuning hyperparameters and plot the frontier curves for each method. We do not include (SC + IL-VC, Multi-Sample) and (SC, Multi-Sample) since they share the same computational cost as ours due to a same graph computation procedure, but their performance is worse than our method (Figure 3). We observe that *our method achieves Pareto optimality in all the metrics.\n\n**Real-world applicability** In real-world applications, time latency is often a more critical consideration than raw computation at inference time. We would like to emphasize that most steps (generating, breakdown, constructing edges) in our pipeline can be *parallelized* and computed in batch, leveraging GPU capabilities to potentially reduce latency to a great extent. \n\n> *”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.”*\n\nWe acknowledge that a direct answer suffices in many scenario. However, in cases where factuality and informativeness are critical, the quality-cost trade-off becomes relevant. Our method provides an option for users to choose when the additional computational investment is warranted by the need for improved output quality.\n### Additional datasets\n> *“The paper primarily uses FactScore and PopQA datasets; more diverse datasets could strengthen the generalizability of the results.”*\n\nThank you for highlighting this important point. We acknowledge that more datasets could strengthen our claims. Our choice of datasets was constrained by two main challenges:\n- The need for datasets challenging enough for state-of-the-art LLMs to ensure a meaningful balance between true and false claims, making uncertainty metrics more informative. \n- The difficulty in constructing accurate auto-annotation pipelines for claims. Given that our previous experiments involved ~6000 claims across six configurations, manual annotation of all claims is impractical. \n\nTo strengthen the generality of our experiments, we have added the Natural Questions dataset, with results in Table 4. The findings show improvements using closeness centrality in most settings. \n\n### Existing work and comparison\n> *”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.”*\n\nWe appreciate this observation. It's important to clarify that our comparison is not limited to graph-based methods. Our aim is to compare various black-box LLM uncertainty estimation methods, aligning with the general problem setting in our paper. This focus on black-box methods excludes many logit-based techniques, which are not applicable in this context.\n\n> *”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.”*\n\nWe appreciate your highlighting these important works. Due to space constraints, we had to condense the Related Work section in the current version. However, we commit to including a more comprehensive review of relevant literature, including the entropy-based framework approaches you mentioned, in the updated version of our paper.\n\n### Empirical assumption\n\n> *“The framework assumes claims are largely independent, which might not hold in all real-world scenarios.”*\n\nWe believe you're referring to the claim breakdown process. It is true that this step assumes claims are separable, which may overlook strong dependencies between claims. However, our uncertainty estimation method actually better considers claim dependencies than previous approaches when measuring uncertainty.\n\nOur approach utilizes broader graph information, including connections beyond immediate neighbors. This allows us to capture more nuanced relationships between claims. For example:\n\nConsider two claims, A and B, each supported by an equal number of generations. In a self-consistency approach, these would receive identical scores. However, our method can differentiate between them based on the broader context:\n\n- If the other claims in generations supporting A are generally more corroborated across the graph than those supporting B, our closeness centrality metric would assign a higher score to A. This is because A's two-hop neighbors (other claims in the same generation) are more connected to other nodes in the graph.\n\nWhen highly supported claims appear in a generation, they may indicate a greater likelihood of reliability for other claims in the same context. Closeness centrality implicitly leverages the dependencies between claims within a generation, offering a more fine-grained approach to uncertainty estimation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ycJPL9hV07", "reviewer": "Reviewer_XiBs", "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.", "questions": "The questions of the paper are listed as follows.   \n1. 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?   \n2. For uncertainty-aware decoding, is the whole workflow different from the existing works except for the source of the uncertainty metric?   \n3. 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": "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.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The strengths of the paper are listed as follows.   \n1. Improving the factuality of the long-form generation is important for the wide application of LLMs and existing methods can still not overcome this challenge with satisfactory performance.  \n2. The proposed method is clearly illustrated in Figure 1.   \n3. The proposed method is reasonable. This pipeline can indeed be performed under black-box settings and with fine-grained (i.e., claim level).", "weaknesses": "The weaknesses of the paper are listed as follows.    \n1. 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.   \n2. 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.    \n3. 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**.    \n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and suggestions. We appreciate that you acknowledged that our method approaches an important problem and offers satisfactory results. We would like to address your remaining questions and concerns in the following response. **Due to the space limitation of the rebuttal section, we've moved responses to some less critical questions to the official comments. Please review both the following response and the accompanying official comments.**\n\n### Results on additional datasets and with more samples\n> *”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.”*\n\n**Additional Dataset**\nThank you for pointing this out. We acknowledge that more datasets could strengthen our claims. Our initial choice of datasets was constrained by two main challenges:\n- The need for datasets challenging enough for state-of-the-art LLMs to ensure a meaningful balance between true and false claims, making uncertainty metrics more informative.\n- The difficulty in constructing accurate auto-annotation pipelines for claims. Given that ~6000 claims involved across six configurations, manual annotation of all claims is impractical.\n\nTo address this concern and strengthen the generality of our experiments, we have added the Natural Questions dataset, with results presented in Table 5. The findings show improvements using closeness centrality in most settings.\n\n**More Samples**\n\nIn fact, in our original study with 50 entities (approximately 1000 claims in each configuration), the results are already statistically significant. However, recognizing that 50 entities might not be intuitively convincing, we have now doubled our sample size to 100 entities (Table 3). Our method continues to outperform baselines across both datasets for every model, further strengthening our findings.\n\n### Computational cost\n> *”The computational cost is heavy due to the frequent use of LLMs.”*\n\nThank you for highlighting this crucial point about computational cost. We agree that the computation overhead is the major limitation of our method. However, we would like to emphasize that our method offers a desirable option for utilizing more inference-time computation to improve the quality of LLMs’ responses. More importantly, our new results demonstrate that ***our method achieves the Pareto optimality for the compute-quality tradeoff*** compared to existing methods.\n\n**Pareto optimality** To evaluate our method's efficiency, we calculated the compute cost and quality metrics  (factuality, informativeness, and the combined metric ‘ factuality x informativeness’ to balance the two) against the baselines. We conducted extensive hyperparameter tuning for all methods, plotting frontier curves for various configurations. We exclude (SC + IL-VC, Multi-Sample) and (SC, Multi-Sample) since they share the same computational cost as ours due to the similar graph construction, but performs worse than our methods (Figure 3). Our analysis reveals that our method consistently outperforms baseline approaches across all metrics, achieving Pareto optimality. This means that to achieve the same level of output quality, our method is relatively computational efficient. \n\n### Potential generalization of the proposed method\n\n> *”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.”*\n\nWe would like to clarify that our method incorporates the inter-claim relationship with graph metrics. A crucial step is the graph propagation (graph-metric calculation), which allows us to consider inter-claim relationships more comprehensively than previous methods. \n\nConsider this example:\nIf Claims A and B are supported by an equal number of generations, but A's co-occurring claims are more corroborated across the graph:\n- Self-consistency (degree centrality) would assign equal scores to A and B.\n- Our method would score A higher, as its two-hop neighbors are more strongly connected.\n\nHighly supported claims may indicate greater reliability for co-occurring claims. By considering these broader relationships, our method provides a more nuanced uncertainty measure. \n\n### Additional questions & suggestions\n\n> *”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?”*\n\nThank you for highlighting this point. We should have clarified it better. In our study, we estimate the uncertainty on a fixed pool of claims entailed by the first generation (as our dataset) to ensure the consistency of measures across different setups, and vary the size of the entire claim set in the graph by using different numbers of sampled responses.\n\nSince self-consistency does not utilize information between claims (such as 2-hop or n-hop relationships in the graph), fixing the number of generations while increasing the number of claims in the graph does not influence the uncertainty estimation performance for the pool of measured claims. In contrast, our method's performance improves, demonstrating that closeness centrality effectively utilizes claim-claim relationship information.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qCL5xxy2mu", "reviewer": "Reviewer_2gkm", "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.", "questions": "1. Just want to double check, is C_D equal to Self-consistency?\n\n2. 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.\n\n3. 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:\n\nQuery: What’s the purpose of statute of limitations?\n\nResponse: 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.\n\nThis is an example supporting the previous claim, “evidence that might prove the defendant’s innocence is lost with time.”\n\n4. The following related work is missing:\n\n[1] LitCab: Lightweight Language Model Calibration over Short- and Long-form Responses", "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: The idea of introducing graph metrics to estimate claim uncertainty is novel. The authors also design a new decoding paradigm for long-form generation.\n\nQuality: Experiments indicate the effectiveness of the proposed methods. The evaluation is thorough, and the analysis is concise and to the point.\n\nClarity: The paper is well-written and easy to follow.\n\nSignificance: The introduced uncertainty estimation method helps users assess the reliability of generated content. The decoding method also contributes to generating more accurate content.", "weaknesses": "1. Both the uncertainty estimation method and UAG require multiple samples from the LLM, which is time-consuming and might significantly increase computational cost.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and suggestions. We appreciate that you acknowledged our method “novel” and our evaluation “thorough”. We would like to address your remaining questions and concerns in the following response.\n\n\n### Computational cost\n\n> *”Both the uncertainty estimation method and UAG require multiple samples from the LLM, which is time-consuming and might significantly increase computational cost.”*\n\n> *”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.”*\n\nWe agree that the computation overhead and time latency is the major limitation of our method. We'll address these concerns by discussing them respectively.  \n\n**Computation cost**  While our method does increase the lower bound of computation, we would like to emphasize that our method offers a desirable option for utilizing more inference-time computation to improve the quality (i.e., factuality & informativeness) of LLMs’ responses. Our approach provides various hyperparameters that allow for flexible adjustment of the performance-cost trade-off. \n\nIn response to your suggestion, we conducted experiments to explore the computational efficiency required to achieve equivalent quality improvements in output. Our new results demonstrate that our method achieves **Pareto optimality in the compute-quality trade-off** compared to existing methods. \n\n**Pareto optimality** Our analysis compares the computational costs and different quality metrics (factuality, informativeness, and their product as a combined metric) for our method against the (SC, Greedy) baseline and greedy decoding. We performed an extensive evaluation by tuning hyperparameters (generation count, claim quantity, and threshold settings) for both our approach and the (SC, Greedy) baseline, then mapped out the efficiency frontiers. We excluded certain baselines with comparable computational demands due to similar graph processing methods, such as (SC + IL-VC, Multi-Sample), and (SC, Multi-Sample), as Figure 3 clearly shows our method's superiority over these. The comprehensive findings are presented in Figure 5 of the supplementary material. Therefore, while the increase of computation cost is noticeable, our method could be an desirable option in scenarios where the quality (factuality or informativeness or both) of the model response is paramount, or when the inference computation is optimized with parallelism or getting much cheaper (as with the current trend). \n\n**Time Latency** The current implementation can be relatively time-consuming. However, we would like to emphasize that most steps (generating samples, breaking down claims, constructing edges) in our pipeline can be *parallelized* and computed in batch, leveraging GPU capabilities to potentially reduce latency to a great extent.\n\n### Empirical assumption\n\n> *”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?”*\n\nWe appreciate this insightful observation and your demonstrating example. While our method implicitly utilizes claim dependencies through closeness centrality, we acknowledge that our initial test datasets may have had fewer inter-claim dependencies. To address this and strengthen the generality of our experiments, we've added the Natural Questions dataset, with results presented in Table 4. One example in the Natural Question is: “When are hops added to the brewing process?” Thus, this dataset probably exhibits more complex inter-sentence relationships.\n\nThe results show that our claim-level uncertainty estimate method improves performance in most settings or remains at least comparable to baseline methods. \n\n### Additional questions & suggestions\n\n> *“Just want to double check, is C_D equal to Self-consistency?”*\nYes, C_D is indeed equivalent to self-consistency.\n\n> *”The following related work is missing…”*\n\nWe appreciate you bringing this to our attention. The work you mentioned is indeed relevant. We commit to including a more comprehensive review of related literature, in the updated version of our paper.\n\n> *”Another suggestion for future work is that the authors could conduct experiments about how these estimated uncertainties benefit users when they are prompting LLMs.”*\n\nThis is an excellent suggestion for future work. The impact of estimated uncertainties on user interactions with LLMs is indeed an under-explored area. We agree that this direction holds significant potential and plan to discuss it in the Future Work section of the arXiv version of our paper. Such research could provide valuable insights into improving user experience and the practical applications of uncertainty estimation in LLM interactions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their helpful feedback and suggestions. 

We are glad that the reviewers found our work our method approaches an important problem [29kR], proposes a novel and interesting method [29kR, 2gkm], offers thorough empirical results [29kR, 2gkm], and “addresses a critical gap in LLM uncertainty estimation” [29kR]. 

We have provided extensive empirical results (included in the supplementary PDF) and responses to address reviewers’ remaining questions. Specifically, we have attempted to address the following major ones:

[Reviewer 29kR, 29kR, 2gkm] Computational cost: Even though our method is indeed introducing additional inference for constructing the graph, our empirical experiments show that our method achieves the **Pareto optimality for the compute-quality tradeoff** compared to other existing methods. These results are illustrated in Figure 5.

[Reviewer 29kR, XiBs] Results on additional datasets and increased sample size: We have enhanced the main table of uncertainty estimation experiments by **doubling the data size** (100 data points with 1700-2400 claims in each experimental setting) for improved statistical power. Furthermore, we have included experiments on **an additional dataset**, Natural Questions, to demonstrate better generalizability. These results are presented in Tables 3 and 4.

[Reviewer 29kR, 2gkm] Empirical assumption of our method: We demonstrate that even though our breakdown process assumes that claims are separable, a key advantage of our method is its implicit utilization of claim dependencies within each graph. This is achieved by leveraging information beyond direct neighbors (degree centrality). The details are discussed in each individual response. 

Please see detailed responses to specific questions below.

Meta-review: 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.
Decision: Accept (spotlight)