# A Probabilistic Framework for LLM Hallucination Detection via Belief Tree
Propagation

Bairu Hou
UC Santa Barbara
<EMAIL_ADDRESS>
&Yang Zhang
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Jacob Andreas
MIT CSAIL
<EMAIL_ADDRESS>
&Shiyu Chang
UC Santa Barbara
<EMAIL_ADDRESS>

###### Abstract

This paper focuses on the task of hallucination detection, which aims to
determine the truthfulness of LLM-generated statements. To address this
problem, a popular class of methods utilize the LLM’s self-consistencies in
its beliefs in a set of logically related augmented statements generated by
the LLM, which does not require external knowledge databases and can work with
both white-box and black-box LLMs. However, in many existing approaches, the
augmented statements tend to be very monotone and unstructured, which makes it
difficult to integrate meaningful information from the LLM beliefs in these
statements. Also, many methods work with the binarized version of the LLM’s
belief, instead of the continuous version, which significantly loses
information. To overcome these limitations, in this paper, we propose Belief
Tree Propagation (BTProp), a probabilistic framework for LLM hallucination
detection. BTProp introduces a _belief tree_ of logically related statements
by recursively decomposing a parent statement into child statements with three
decomposition strategies, and builds a hidden Markov tree model to integrate
the LLM’s belief scores in these statements in a principled way. Experiment
results show that our method improves baselines by 3%-9% (evaluated by AUROC
and AUC-PR) on multiple hallucination detection benchmarks. Code is available
at https://github.com/UCSB-NLP-Chang/BTProp.

##  1 Introduction

Large language models (LLMs) have shown impressive performance across various
domains. Existing LLMs are recognized for their ability to follow human
instruction and generate outputs that are both grammatically correct and
contextually relevant. However, a notable limitation is their occasional
divergence from factual accuracy and real-world knowledge. This issue,
commonly referred to as “hallucination”, significantly undermines the
reliability and trustworthiness of LLMs.

Various methods have been developed to detect hallucinated statements
generated by LLMs. One naive solution is to directly prompt the LLM to output
confidence scores for the truthfulness of the statements (referred as “model
beliefs" in this paper and prior work [1, 2, 3]). However, due to the LLM’s
limited knowledge and poor calibration of the confidence estimation, such
beliefs may be mistaken. To resolve this problem, one important line of
methods bases the truthfulness decision on the LLM’s internal knowledge as
well as logical consistency[1, 2, 3, 4, 5, 6, 7]. More specifically, these
approaches typically involve two steps. First, generate an augmented set of
statements that are related to the target statements. The augmented statements
can be premises or contradictory statements of the target statements [8, 3],
or extended passages in the same topic of the target statements [4].Second,
ask the LLM to make correctness judgments for every statement in the augmented
set, and then integrate these judgments to determine the truthfulness of the
target statement based on the logical relationships between the augmented
statements and the target statement.

Figure 1: An example constructed belief tree.

To intuitively understand the idea behind such methods, consider the simplest
case where there are two contradictory statements. If the LLM believes both
statements are true, it would lead to a logical inconsistency and indicate
that one of the decisions is flawed. By having a large number of augmented
statements, we could then gather rich information about the LLM’s beliefs and
correct the potential decision mistakes by resolving the logical
inconsistencies. Compared to other hallucination detection methods, such as
retrieval-augmented methods [9, 10, 11] and decisions based on LLM’s internal
states [12, 13, 14], such consistency-based methods do not rely on external
datasets and can work with both black-box and white-box LLMs, and thus gains
wide popularity in the research community.

With the same intuition, we propose Belief Tree Propagation (BTProp), a
probabilistic framework that leverages logical consistency across model’s
beliefs for LLM hallucination detection. Specifically, given a statement from
the LLM’s generation, BTProp first generates a _belief tree_ of logically
connected statements by recursively decomposing a parent statement into child
statements. As the example shown in Figure 1, the root node of the belief tree
is one sentence generated by the LLM about the freezing point of water from
the FELM [15] dataset. Each child node is either supportive or contradictory
to its parent node. To diversify the statements and the logical relationships,
BTProp introduces three types of decomposition paradigms. After that, BTProp
builds a directed graphical model (a “hidden Markov tree") [16, 17] in which
the LLM’s confidence scores are modeled as observed variables, and the ground-
truth truthfulness of the statements as the corresponding hidden variables.
Thus the truthfulness decision is turned into a standard principled
probabilistic inference problem. By estimating the emission probabilities and
transition probabilities properly, we can do inference in this hidden Markov
tree model to correct the potential wrong beliefs of LLMs.

Compared to existing hallucination detection methods [4, 7] that directly
sample additional responses from the LLM as augmentations, our method organize
more diverse statements into a tree structure to better utilize the model’s
beliefs. Furthermore, our method can integrate the model beliefs in a
principled and probabilistic manner. Experiment results show that our method
achieves state-of-the-art performance, improving the hallucination detection
performance (AUROC and AUC-PR) by 3% - 9% on FELM-Science [15] and
FactCheckGPT [18] datasets.

##  2 Related Work

#### Hallucinations in LLMs.

Hallucination has become a prominent topic in the research of LLMs [19, 20,
12, 21, 22]. In existing literature, hallucination typically refers to the
phenomenon where LLMs generate nonfactual, nonsensical, or unfaithful outputs.
Hallucinations have been observed in various tasks such as text summarization
[23, 24, 25, 26], question answering [21], and machine translation [27, 28,
29, 30]. Prior work [31, 32, 32] characterizes hallucination into two main
types: factuality hallucination and faithfulness hallucination. Factuality
hallucinations refer to outputs that are inconsistent with real-world facts or
cannot be verified. In comparison, faithfulness hallucinations shift to the
generated content that deviates from the user’s instruction or user-provided
contextual information. In this paper, we mainly focuses on factuality
hallucinations and aim to better leverage the LLM’s intrinsic capabilities to
detect such nonfactual statements within their generations.

#### Hallucination detection.

Existing approaches to detect factuality hallucination can be divided into two
categories. The retrieval-based methods [33, 34, 35, 36, 11, 37, 38, 10]
involve comparing the LLM’s output with information retrieved from a reliable
knowledge base to assess its factuality. However, these methods depend heavily
on external knowledge bases, making them less flexible.To detect
hallucinations when an external knowledge base is inaccessible, another
category of methods leverages the model’s intrinsic capabilities. Among these
intrinsic methods, some approaches leverage the reasoning ability of LLMs to
detect and reduce hallucinations [15, 20] via chain-of-thought prompting [39].
Uncertainty-based methods perform token-level or sentence-level uncertainty
quantification [40, 18] and use the uncertainty to predict whether the model’s
generation is non-factual. When the model’s parameters and hidden states are
accessible, probing these hidden states has also been shown to be effective in
detecting hallucinations [12, 14, 13]. The sampled-based methods (or
consistency-based methods) [4, 6, 7] sample multiple additional responses to
the user prompt and then perform consistency checks between the augmented
responses and the original model generation. Inconsistencies are then used to
detect hallucinations. Our method also aims to detect hallucinations using the
model’s intrinsic capabilities and is closely related to the consistency-based
methods. Instead of sampling additional responses and performing unstructured
consistency checks, our method generates logically-related statements
organized in a tree structure. We further propose a probabilistic framework
based on the hidden Markov tree model to check consistency and detect
hallucinations.

#### Improving factuality via logical consistency.

A growing body of research explores improving LLMs’ factuality using the
logical consistency across their beliefs [41, 42, 1, 8, 2, 3, 5]. Starting
from an initial text (_e.g._ , a statement requiring truthfulness assessment
or a question), these methods identify additional texts that are logically
connected to the initial text and organize them in tree or graph structures.
The inconsistencies of model’s beliefs on the factual correctness of these
texts are resolved based on the inferential relations among these texts. One
main limitation is that they treat the beliefs (LM-generated truth values or
probabilities) as calibrated, which is generally not the case. Motivated by
this, we build a probabilistic framework to integrate the model’s beliefs and
figure out the most possible and reliable correctness evaluation of the
initial text.

##  3 Methodology

In this section, we will describe the details of the proposed method, which
leverages the inconsistency in model beliefs for hallucination detection.

###  3.1 Problem Formulation

Given a statement $v$ from the LLM-generated text, _e.g._ , _‘A star’s
temperature is determined by the amount of mass and energy it has’_ , and an
LLM, our primary goal is to use the LLM to gauge the correctness of the
statement. Many previous works use simple prompting techniques to directly
elicit the LLM’s belief of the statement, whose output would typically be in
the form of _confidence scores_ between $[0,1]$. For example, one approach is
to directly ask the LLM whether it believes this statement to be true. By
sampling multiple answers from the LLM, we can obtain the confidence score as
the percentage of the answers that say _‘yes’_.

Denote $S_{v}$ as LLM’s confidence score regarding statement $v$ reflecting
the LLM’s original belief of the statement. Then $S_{v}$ should be close to
one if the LLM believes the statement is true, and zero otherwise. However,
due to LLM’s limited knowledge and capability, $S_{v}$ does not always align
with the actual truthfulness of the statement – the scores could be high for
some false statements, and low for true ones. In this paper, we will seek to
improve the truthfulness judgment with the LLM over its confidence score
$S_{v}$.

###  3.2 Our Method: An Intuitive Overview

The basic idea of our approach is to construct a _belief tree_ , denoted as
$\mathcal{T}$, where the root node is the target statement, each child node is
a statement logically related to the parent node, and each edge represents the
logical connection between the two nodes. We then obtain the confidence scores
of all the nodes and use the logical consistency among the scores to correct
any potential mistakes in the scores.

Figure 2 shows an example, where the target statement is _‘A star’s
temperature is determined by the amount of mass and energy it has”_. This
statement is true but assume that the LLM produces a low confidence score,
$0.1$, for the statement. To correct this error, we can construct a belief
tree $\mathcal{T}$ by generating two child nodes from the target node, where
the first, which is true, is entailed by the target statement and the second,
which is false, contradicts the target statement. Assume that the LLM
correctly assigns a high confidence score to the former and a low score to the
latter. In this case, we can easily spot that the belief of the target node is
logically inconsistent with those of the child nodes, and that increasing the
confidence score of the target node would resolve the logical inconsistency,
hence correcting the mistake.

Figure 2: Motivating example for the proposed method.

Of course, the example above shows the simplest case where the LLM’s beliefs
in the child nodes are all correct, whereas, in reality, the child nodes’
beliefs may as well be wrong. To mitigate these additional errors, we can
construct a much larger belief tree with greater depth and many different
statements. Assuming the errors in the confidence scores are sporadic, we can
then expect to correct most of these errors, in both the target and child
nodes, by taking into account all the confidence scores and their logical
consistency. An example of such a full belief tree is shown in Figure 3.

As implied by the discussion above, our algorithm consists of two components:
❶ Constructing the belief tree, and ❷ inferring the truthfulness of the target
statement by integrating the confidence scores across the belief tree. Section
3.3 will discuss the former and Sections 3.4-3.6 the latter.

###  3.3 Belief Tree Construction

Since the belief tree $\mathcal{T}$ consists of nodes as statements and edges
as the logical relationships between parent and child statements, the
construction of the belief tree iterates between the following two steps. Step
1: Given a statement as the parent node, generate a set of logically connected
statements as the children nodes. Step 2: Determine the logical connection
between the children nodes and parent node. The iterative process starts with
the target statement as the root node, and terminates when the maximum tree
depth is reached. Each step is detailed below.

#### Generating Child Statements

The success of our algorithm hinges on the diversity of the generated
statements. Hence, we instruct the LLM to choose from three types of statement
generation strategies.

Strategy 1: Statement Decomposition. For statements containing multiple
facts/claims, we can decompose them into individual sub-statements. Figure 1
shows an example where the target statement (_Node 0_) contains multiple facts
(the atmosphere pressure level and the freezing point of water on Mound
Everest), which is then decomposed into two statements, one on the atmosphere
pressure level and one on the freezing point of water. Statement decomposition
can be achieved by prompting the LLM with in-context examples, as listed in
Appendix A.1.

Strategy 2: Supportive and Contradictory Premises. In this strategy, the LLM
is instructed to generate a set of premises that are each supportive or
contradictory to the parent claim. When verifying the truthfulness of _Node 2_
in Figure 1 about the freezing point of water, we can prompt the model to
generate contradictory premises (_Node 3_ and _Node 4_) that implies the
limited influence of low pressure on the freezing point of water. By
leveraging these generated premises, we can indeed correct the model’s wrong
belief on _Node 2_ since the model’s confidence scores on these generated
premises are high in this example.

Strategy 3: Statement Correction. In this strategy, the LLM is instructed to
generate what it believes to be corrected versions of the parent statement.
The _Node 5_ in Figure 1 shows one example of the statement correction
process, where the statement is about the freezing point of water. Then the
corrected statements would be almost the same as the parent statement (_Node
2_), except that the actual temperature is replaced with alternatives that LLM
believes may be true. This strategy is implemented via a three-step prompting
process. First, the LLM is prompted to generate a question about the key
information in the statement. For example, the key information in _Node 2_ in
Figure 1 is the freezing point. Then, the LLM is instructed to answer the
generated question, and multiple answers will be sampled. Finally, the LLM is
prompted to generate a corrected statement from the original statement if it
is wrong according to each sampled answer. Note that there can be multiple
corrected statements because the LLM may produce different answers when
sampled multiple times. Also, the corrected statements may include the parent
statement itself if the LLM believes the parent statement is a likely answer.
More details about this process can be found in Appendix A.1.

To select the most appropriate strategies for each parent claim, we introduce
the following routing procedure. First, we always start by asking the LLM to
attempt the statement decomposition strategy. If the decomposition returns
multiple statements, which indicates that the decomposition is meaningful and
successful, we would use these decomposed statements as the child statements.
If the decomposition returns only a single statement, indicating that the
parent statement cannot be further decomposed, we will then prompt the LLM to
select between strategies 2 and 3 with a list of rules and examples. The
detailed prompts will be listed in Appendix A.1.

#### Determining Logical Relationships

Given a pair of parent and child statements, $u$ and $v$, we consider the
following four logical relationships: ❶ Equivalence, $u\Leftrightarrow v$, if
$u$ entails $v$ and $v$ entails $u$; ❷ entailment, $u\Rightarrow v$, if $u$
entails $v$ but $v$ is neutral to $u$; ❸ reverse entailment, $u\Leftarrow v$,
if $u$ is neutral to $v$ but $v$ entails $u$; and ❹ contradiction,
$u\Rightarrow\neg v$ (or, equivalently, $v\Rightarrow\neg u$). Note that we do
not consider the completely neutral relationship because any statements
determined as completely neutral to their parent statement will be removed.

For the decomposition strategy (strategy 1), the child node statements are, by
construction, _jointly equivalent to_ the parent statement. Formally, denote
$u$ as the parent node and $\mathcal{C}(u)$ as the set of its child nodes,
then their logical relationship is determined as
$u\Leftrightarrow\cap_{v\in\mathcal{C}(u)}v$.

For strategies 2 and 3, since each child statement is independently generated,
we only need to determine their _individual_ relationship to the parent
statement, rather than the joint relationship. To this end, we leverage an
off-the-shelf natural language inference (NLI) model to infer the entailment,
neutrality, or contradiction between the statements. For each pair of parent
statement $u$ and an _individual_ child statement $v$, we derive two NLI
relationships, one by setting $u$ as the premise and $v$ as the hypothesis,
and the other with $u$ and $v$ switched. The two NLI outputs are then mapped
to the aforementioned logical relationships – (entail, entail) mapped to
equivalence; (entail, neutral) mapped to entailment; (neutral, entail) mapped
to reverse entailment; and any results containing contradict in either
direction mapped to contradiction. As mentioned, if the NLI module returns
(neutral, neutral), the corresponding child statement will be discarded.

#### Prior Belief Estimation

The last step of the belief tree construction is to estimate the model’s
belief (_i.e._ , whether the statement is true) on each node. We adopt the
simple prompting method discussed in Section 3.1 to obtain LLM’s confidence
scores. Specifically, we directly probe the LLM with the prompt ‘True or
False? {target statement}’ and use the next token prediction probabilities of
the words ‘True’ and ‘False’ to compute the model confidence. We normalize the
prediction logits of the two words to get the confidence score of that
statement. The only exception is in the case of statement correction, where
the LLM is already instructed to output alternative statements it believes to
be true. As a result, we simply set the confidence score of each generated
statement to 1. Our empirical analysis shows that this would greatly reduce
the number of LLM queries without deteriorating the performance.

###  3.4 A Hidden Markov Tree Model

After the belief tree is constructed, the next question is how to utilize the
confidence scores across the tree to better determine the truthfulness of the
root statement, namely the target statement. To this end, we introduce a
hidden Markov tree model and frame the truthfulness estimation problem as a
probabilistic inference problem.

Figure 3 shows an example hidden Markov tree model built upon the belief tree,
where there are two layers of variables. The upper layer consists of the
confidence score of each statement, _i.e._ , $\\{S_{u}\\}$, which is estimated
during the belief tree construction process. The lower layer consists of the
binary variables representing the actual correctness of each statement,
denoted as $\\{Z_{u}\\}$. $Z_{u}=1$ if statement $v$ is correct and $Z_{u}=0$
otherwise. $\\{S_{u}\\}$ are observed variables while $\\{Z_{u}\\}$ are hidden
variables.

Given the above hidden Markov tree model, determining the truthfulness of the
target statement can be cast as computing the posterior probability, _i.e._ ,
$p(Z_{0}=1|\\{S_{u}\\})$, which means the truthfulness of the root node given
the confidence scores on all the nodes in this belief tree. According to the
probability graph in figure 3, we need to estimate the following
probabilities.

Figure 3: An example hidden Markov tree model.

The first set is the _emission probability_ , $p(S_{u}|Z_{u})$, which
characterizes the LLM’s confidence score of the statement given its underlying
truthfulness. The emission probability captures the quality of LLM’s original
confidence score. If the confidence score is accurate, then $p(S_{u}|Z_{u}=1)$
will concentrate its probability mass towards $1$, and $p(S_{u}|Z_{u}=0)$ will
concentrate its probability mass towards $0$. Otherwise, the conditional
distributions will be more spread.

The second set of distribution is the _transition probability_ ,
$p(Z_{\mathcal{C}(u)}|Z_{u})$, where $Z_{\mathcal{C}(u)}$ represent the set of
truthfulness variables of all the child nodes of $u$. The transition
probability is the joint probability of the truthfulness of the child
statements given that of the parent statement, which captures the logical
relationships among these statements.

The third set of distribution is the _prior distribution_ of hidden variables,
_i.e._ , $p(Z_{u}=z)$, which refers to the probability of an arbitrary
statement $u$ generated by the LLM being true or false. We use uniform prior
(both 0.5 for $z=1$ and $z=0$) in this paper.

Therefore, the process of computing the posterior probability contains two
steps: ❷ the estimation step, to first estimate these probabilities on a held-
out dataset. ❸ the inference step, to compute the posterior probability for
each testing example. Section 3.5 will discuss how to determine the emission
and transition probabilities and Section 3.6 how to infer
$p(Z_{0}=1|\\{S_{u}\\})$.

###  3.5 Determining Conditional Probabilities

#### Determining Emission Probabilities

The emission probabilities, $p(S_{u}|Z_{u})$, can be estimated from labeled
datasets. Specifically, given a dataset of statements with truthfulness
labels, we can run the LLM to obtain the confidence scores of all the
statements. We can then estimate $p(S_{u}|Z_{u}=1)$ by obtaining the empirical
distribution of the confidence scores within the statements labeled as true,
and $p(S_{u}|Z_{u}=0)$ within the statements labeled as false. To obtain the
empirical distribution of the continuous confidence scores, we first quantize
the support $[0,1]$ into multiple bins, and count the histogram of the
confidence scores falling into each bin. The boundaries of each bin are listed
in Table 1.

Table 1: Empirical estimation of the emission probability on Wikibio-GPT3
dataset [4].

| $S_{u}\in[0.0,0.2)$ | $[0.2,0.4)$ | $[0.4,0.7)$ | $[0.7,0.9)$ | $[0.9,1.0]$
---|---|---|---|---|---
$Z_{u}=\texttt{True}$ | 0.12 | 0.05 | 0.10 | 0.08 | 0.65
$Z_{u}=\texttt{False}$ | 0.30 | 0.10 | 0.15 | 0.13 | 0.32

#### Determining Transition Probabilities

The transition probability, $p(Z_{\mathcal{C}(u)}|Z_{u})$, is a multivariate
Bernoulli distribution with the support $\\{0,1\\}^{m}$, where $m$ is the size
of $\mathcal{C}(u)$. As discussed in Section 3.3, different statement
generation strategies have different logical relationship properties. For the
statement decomposition strategy, the child statements are always jointly
equivalent to the parent statement. Therefore, when the parent claim is true,
_i.e._ , $Z_{u}=1$, we know that all of the child statements must be true, and
thus $p(Z_{\mathcal{C}(u)}=\bm{z}|Z_{u}=1)$ equals one when $\bm{z}$ is an
all-one vector and zero when $\bm{z}$ takes other values. Conversely, when the
parent claim is false, _i.e._ , $Z_{u}=0$, we can infer that at least one
child statement is wrong, so $p(Z_{\mathcal{C}(u)}=\bm{z}|Z_{u}=0)$ is set to
zero when $\bm{z}$ is an all-one vector and uniformly set to $1/(2^{m}-1)$
when $\bm{z}$ takes other values.

For the other two strategies, the child statements of the same parent
statement are considered independent conditional on the parent statement.
Therefore, we can decompose the probability $p(Z_{\mathcal{C}(u)}|Z_{u})$ into
$\prod_{v\in\mathcal{C}(u)}p(Z_{v}|Z_{u})$, where each $p(Z_{v}|Z_{u})$ is the
transitional probability between parent statement $u$ and one child statement
$v$. $p(Z_{v}|Z_{u})$ is determined based on the four different possible
logical relationships between $u$ and $v$ (recall the discussion in Section
3.3), which is listed in Table 2, where $p_{t}$ and $p_{f}$ are two hyper-
parameters.

Table 2: Transition probability given different logical relationships between
two nodes. $p_{t}$ and $p_{f}$ are set to $0.5$ in this paper.

| $u\Leftrightarrow v$ | $u\Rightarrow v$ | $u\Leftarrow v$ | $u\Rightarrow\neg v$
---|---|---|---|---
| $u=\texttt{True}$ | $u=\texttt{False}$ | $u=\texttt{True}$ | $u=\texttt{False}$ | $u=\texttt{True}$ | $u=\texttt{False}$ | $u=\texttt{True}$ | $u=\texttt{False}$
$v=\texttt{True}$ | 1.0 | 0.0 | 1.0 | $p_{t}$ | $p_{t}$ | 0.0 | 0.0 | $p_{t}$
$v=\texttt{False}$ | 0.0 | 1.0 | 0.0 | $p_{f}$ | $p_{f}$ | 1.0 | 1.0 | $p_{f}$

###  3.6 Inferring the Posterior Probability of $Z_{0}$

Inferring the posterior probability $p(Z_{0}=1|\\{S_{u}\\})$ is a standard
inference problem in hidden Markov tree models and we can directly apply the
standard _upward-downward algorithm_ [16] to efficiently compute this
probability. For brevity, we will only describe the gist of the algorithm
here. More details can be found in Appendix A.3 and previous work [16, 17].

The algorithm introduces an auxiliary conditional distribution
$\beta(z,u)\equiv p(S_{\mathcal{T}(u)}|Z_{u}=z)$, where $z\in\\{0,1\\}$ and
$S_{\mathcal{T}(u)}$ represents the confidence scores of all the nodes in the
sub-tree whose root node is $u$. By definition, the posteior probability of
our interest, $p(Z_{0}=1|\\{S_{\mathcal{T}(0)}\\})$, can be represented as
$\beta(z=1,0)/(\beta(z=0,0)+\beta(z=1,0))$. According to the Bayesian rule, we
can derive a recursive relationship between $\beta(z,u)$ of a parent node $u$
and those of the child nodes:

$\small\beta(z,u)=p(S_{u}|Z_{u}=z)\cdot\sum_{Z_{\mathcal{C}(u)}\in\\{0,1\\}^{m}}p(Z_{\mathcal{C}(u)}|Z_{u}=z)\prod_{v\in\mathcal{C}(u)}\beta(Z_{v},v),$
(1)

where $m$ is the size of $\mathcal{C}(u)$ (namely the number of child
statements to node $u$). Note that the first term on the RHS is the emission
probability, and the first term inside the summation is the transition
probability, which are both already known. Therefore, Equation 1 provides a
way to compute $\beta(z,0)$ recursively from the leaf nodes back to the root
node. First, we compute the $\beta(z,u)$ of the leaf nodes as
$\beta(z,u)=p(S_{u}|Z_{u}=z)$. Then, we use Equation 1 to recursively compute
the $\beta(z,u)$ of a parent node $u$ from their child nodes, until the root
node is reached. The entire process is essentially propagating and merging the
beliefs in the confidence scores from sub-trees upward to the parent node. By
the time we reach the root node, we have gathered the information of all the
confidence scores. Hence this process is also referred to as a _belief
propagation_ process.

We summarize the whole algorithm in Appendix A.4.

##  4 Experiments

In this section, we conduct empirical evaluations on commonly-used
hallucination detection benchmarks to demonstrate the effectiveness of the
proposed method.

###  4.1 Experiment Configurations

#### Datasets

We follow the previous work of hallucination detection [4, 15] and use the
following datasets for evaluation: Wikibio-GPT3 [4], FELM-Science [15], and
FactCheckGPT [43]. Wikibio-GPT3 mainly consists of biography articles
generated by LLMs, whereas FELM-Science and FactCheckGPT cover a broader range
of topics such as physics, chemistry, and computer science.

#### Evaluation settings and metrics

Following the default settings on each dataset, we conduct hallucination
detection at sentence-level on Wikibio-GPT3 and FactCheckGPT and segment-level
on FELM-Science. Our evaluation encompasses a comprehensive set of metrics,
including the area under the receiver operator characteristic curve (AUROC),
area under the precision-recall curve (AUC-PR), F1 score, and detection
accuracy. As F1 score and detection accuracy evaluation require a decision
threshold, we search for the optimal threshold to maximize the F1 score for
each method and compute the two metrics. Note that when computing these
metrics, we consider hallucinated examples as positive instances, following
the default configurations of these datasets. Moreover, Wikibio-GPT3 and FELM-
Science exhibit significant class imbalances, so the detection accuracy on
these datasets serve merely as reference points.

#### Baselines

We include the following baselines for comparison. The implementation details
are available in Appendix A.1. (1) Prior confidence, which directly queries
the model’s confidence regarding the truthfulness of each sentence or segment.
(2) Chain-of-thought, which prompts the model to first generate a reasoning
process before deciding the truthfulness. We adopt the Chain-of-thought
prompting method from the official FELM [15] dataset, with slight
modifications for sentence-level and segment-level hallucination detection.
(3) SelfCheckGPT [4], which samples additional responses from the model and
use the inconsistency between each response and the target statement for
hallucination detection. Among the multiple variants, we choose SelfCheckGPT-
prompt for comparison, which achieves the best performance. We sample 20
responses for hallucination detection following its default configuration.(4)
Maieutic-Prompting [8], which first builds a belief tree via backward-chaining
and then infers the truth-value of the original statement that resolves the
inconsistencies.

#### Implementation details

We evaluate our method along with baselines using both closed-sourced and
open-sourced models, including GPT-3.5-turbo-0125 and Llama-3-8B-Instruct. For
our method, we set the maximum belief tree depth to $2$. We employ greedy
decoding during belief tree construction and prior belief estimation. The
exception is the statement correction strategy, where we sample $5$ corrected
statements using temperature $0.7$. Additionally, since each statement in
FactCheckGPT is manually processed to ensure it contains only one property or
fact, we do not apply statement decomposition when build the belief tree for
statements from FactCheckGPT. We use the first 120 examples in the Wikibio-
GPT3 dataset to estimate the emission probability in our method, and validate
it on the remaining examples and two other datasets. More implementation
details can be found in Appendix A.1.

###  4.2 Experiment Results

Table 3: Hallucination detection performance of different methods. We report
AUROC, ROC-PR, F1 score, and detection accuracy(Acc) for all methods with two
different backbone models. The best results are highlighted in bold.

Method | Backbone | AUROC | AUC-PR | F1 |  Acc | Backbone | AUROC | AUC-PR | F1 | Acc
---|---|---|---|---|---|---|---|---|---|---
Wikibio-GPT3
Prior Confidence |  GPT-3.5 -Turbo | 73.1 | 85.7 | 84.5 | 76.3  |  Llama3-8B Instruct | 71.0 | 85.7 | 85.5 | 75.9
Chain-of-thought | 71.3 | 83.4 | 85.2 | 76.4  | 72.0 | 84.4 | 85.3 | 75.7
SelfCheckGPT | 82.6 | 91.3 | 86.6 | 80.0  | 77.0 | 86.8 | 86.1 | 76.8
BTProp |  | 80.7 | 90.4 | 87.6 | 80.4 |  | 74.0 | 86.2 | 86.1 | 77.5
FELM-Science
Prior Confidence |  GPT-3.5 -Turbo | 75.5 | 37.2 | 42.1 | 81.6  |  Llama3-8B Instruct | 76.1 | 38.2 | 44.0 | 80.6
Chain-of-thought | 56.3 | 19.0 | 28.6 | 72.5  | 61.6 | 25.7 | 32.6 | 71.2
SelfCheckGPT | 77.4 | 45.7 | 51.3 |  84.4 | 77.8 | 39.5 | 49.1 | 76.5
Maieutic-Prompting | - | - | 27.2 | 82.6  | - | - | 22.9 | 79.2
BTProp | 79.1 | 52.3 | 56.5 | 81.6  | 77.8 | 48.2 | 51.3 | 82.8
FactCheckGPT
Prior Confidence |  GPT-3.5 -Turbo | 76.0 | 52.6 | 53.6 | 71.5  |  Llama3-8B Instruct | 71.9 | 47.6 | 50.8 | 60.5
Chain-of-thought | 66.5 | 38.9 | 47.7 | 66.4  | 72.5 | 43.3 | 53.2 | 66.1
SelfCheckGPT | 74.9 | 49.7 | 54.4 | 74.0  | 72.5 | 46.4 | 51.9 | 65.9
Maieutic-Prompting | - | - | 35.0 | 72.2  | - | - | 39.8 | 66.8
BTProp | 79.4 | 54.3 | 60.2 | 75.3 | 73.9 | 49.1 | 55.3 | 72.6

#### Overall comparison

We evaluate the effectiveness of BTProp with the experiment results in Table
3. We highlight the following observations. First, our method achieves the
best performance on FELM-Science and FactCheckGPT datasets across different
backbones, demonstrating the superiority of our method. BTProp improves upon
the best baselines by 3% - 9% on AUROC and ROC-PR. The only exception is the
Wikibio-GPT3 dataset, where the SelfCheckGPT is more effective for detection
hallucinated outputs in biographies generated by LLMs. Second, compared to
SelfCheckGPT which leverages contradictions between the target statement and
the sampled responses for hallucination detection, our method is more
effective on detecting hallucinated responses related to scientific knowledge.
Both FELM-Science and FactCheckGPT datasets contain a significant proportion
of questions on scientific knowledge, and our method achieves the best
performance on them. Third, chain-of-thought prompting is less effective in
hallucination detection, especially on the FELM-Science dataset. This finding
aligns with the experimental results in the original FELM dataset paper. Our
experiments show that the model tends to regard the input sentence as true
most of the time, leading to sub-optimal performance. Finally, the Maieutic-
prompting method, which is originall designed to verify the correctness of
statements related to commonsense reasoning, is less effective for
hallucination detection. Even on the FELM-Science and FactCheckGPT datasets
which contain many statements about scientific knowledge, it remains less
effective compared to other methods.

Figure 4: Performance-efficiency comparison.

#### Deployment efficiency

One concern on our method is the belief tree construction would be time-
consuming and inefficient. Therefore, we compare the time cost of our method
with the baselines on the FELM-Science and FactCheckGPT datasets, where our
method significantly outperform baselines. We use the open-sourced
Llama-3-8b-Instruct model as the backbone, and eliminate CoT prompting method
on FELM-Science dataset due to its poor performance. We visualize the trade-
off between hallucination detection performance and the time cost in Figure 4
of different methods. The baseline methods, including SelfCheckGPT and CoT
prompting, samples additional 20 responses for hallucination detection by
default. We vary the number of samples and test the corresponding performance
to visualize the trade-off. As depicted in the graph, the baseline performance
shows diminishing returns in performance improvement with increased
computational complexity. As time cost increases, the performance growth of
the two baseline models gradually levels off, eventually reaching a point
where additional time does not translate into significantly better
performance. In comparison, our method can effectively trades off increased
time cost for significantly improved performance. Despite its higher
computational complexity, it achieves a marked improvement in performance
metrics, underscoring its efficiency and effectiveness in hallucination
detection compared to the baseline models.

#### Qualitative results

We visualize several examples of the constructed belief trees to demonstrate
how the inconsistencies in model’s beliefs help detect the hallucination. Due
to space limit, we put these examples and the corresponding analyses in
Appendix A.2.

Table 4: Performance of BTProp given different child node generation
strategies.

| AUROC | AUC-PR | F1 | Acc
---|---|---|---|---
BTProp | 79.1 | 52.3 | 56.5 | 81.6
Decomposition only | 67.9 | 31.2 | 43.3 | 79.6
Premise only | 70.2 | 30.7 | 40.4 | 78.6
Correction only | 77.4 | 47.5 | 53.0 | 81.5
Prior Conf | 75.5 | 37.2 | 42.1 | 81.6

#### Ablation study: belief tree construction

We introduce three strategies to build the belief tree: statement
decomposition, generating supportive and contradictory premises, and statement
correction. We perform ablation study to demonstrate the necessity to
introduce these different strategies in Table 4 using gpt-3.5-turbo-0125 as
the backbone model. Specifically, we evaluate the performance of our method
when only use one child node generation strategies on the FELM-Science
dataset. We highlight the following observations. First, only applying one
child node generation strategy is sub-optimal. There exist a significant gap
between using one strategy and using them all. Second, statement correction
tends to contribute most to the performance improvement, but when combining it
with other strategies, the performance can still be further improved.

##  5 Conclusion

In this paper, we propose BTProp, a method that leverages the model’s
intrinsic capability for hallucination detection. Given a statement from the
LLM-generated texts, our method organizes the model’s intrinsic beliefs on
neighboring statements in a belief tree. By introducing the hidden Markov tree
model, we convert the the hallucination detection into a posterior probability
estimation problem and propose corresponding solutions to solve it. Experiment
results have demonstrate the effectiveness of our method. The future direction
would be how to further improve the belief tree construction method to make it
more effective and efficient.

##  6 Acknowledgements

The work of Bairu Hou and Shiyu Chang was partially supported by National
Science Foundation (NSF) Grant IIS-2207052 and NSF Grant IIS-2302730. The
computing resources used in this work were partially supported by the
Accelerate Foundation Models Research program of Microsoft.

##  7 Broader Impact

In this paper, our primary goal is to develop an algorithm that can integrate
the model’s internal beliefs on logically-connected statements to detect
hallucinations in texts generated by the LLM. Our method is designed to
improve the trustworthiness of LLMs and make fully use of their intrinsic
capabilities. Therefore, our method is less likely to introduce the unintended
risks. We also assess the experiments to ensure they are devoid of any harmful
content or adverse impacts.

##  8 Limitation

While BTProp improves the hallucination detection performance and enhance the
trustworthiness of LLMs, it involves collecting a set of augmented statements
(the belief tree) to perform inference. Therefore, the main limitation of our
method is its high time cost. Constructing a belief tree necessitates multiple
queries to the large language model, leading to significant delays.
Additionally, the time complexity of generating child nodes increases
exponentially as more layers are added to the tree. A potential solution to
this issue could be to develop a mechanism that selectively expands nodes
within the belief tree, thereby optimizing the process.

## References

  * [1] Eric Mitchell, Joseph Noh, Siyan Li, Will Armstrong, Ananth Agarwal, Patrick Liu, Chelsea Finn, and Christopher D Manning,  “Enhancing self-consistency and performance of pre-trained language models through natural language inference,”  in Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, 2022, pp. 1754–1768.
  * [2] Peter Hase, Mona Diab, Asli Celikyilmaz, Xian Li, Zornitsa Kozareva, Veselin Stoyanov, Mohit Bansal, and Srinivasan Iyer,  “Methods for measuring, updating, and visualizing factual beliefs in language models,”  in Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, 2023, pp. 2714–2731.
  * [3] Nora Kassner, Oyvind Tafjord, Ashish Sabharwal, Kyle Richardson, Hinrich Schuetze, and Peter Clark,  “Language models with rationality,”  in The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
  * [4] Potsawee Manakul, Adian Liusie, and Mark Gales,  “Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models,”  in The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
  * [5] Afra Feyza Akyürek, Ekin Akyürek, Leshem Choshen, Derry Wijaya, and Jacob Andreas,  “Deductive closure training of language models for coherence, accuracy, and updatability,”  arXiv preprint arXiv:2401.08574, 2024.
  * [6] Zouying Cao, Yifei Yang, and Hai Zhao,  “Autohall: Automated hallucination dataset generation for large language models,”  arXiv preprint arXiv:2310.00259, 2023.
  * [7] Niels Mündler, Jingxuan He, Slobodan Jenko, and Martin Vechev,  “Self-contradictory hallucinations of large language models: Evaluation, detection and mitigation,”  in The Twelfth International Conference on Learning Representations, 2023.
  * [8] Jaehun Jung, Lianhui Qin, Sean Welleck, Faeze Brahman, Chandra Bhagavatula, Ronan Le Bras, and Yejin Choi,  “Maieutic prompting: Logically consistent reasoning with recursive explanations,”  in Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, 2022, pp. 1266–1279.
  * [9] Abhika Mishra, Akari Asai, Vidhisha Balachandran, Yizhong Wang, Graham Neubig, Yulia Tsvetkov, and Hannaneh Hajishirzi,  “Fine-grained hallucination detection and editing for language models,”  arXiv preprint arXiv:2401.06855, 2024.
  * [10] Jiawei Zhang, Chejian Xu, Yu Gai, Freddy Lecue, Dawn Song, and Bo Li,  “Knowhalu: Hallucination detection via multi-form knowledge based factual checking,”  arXiv preprint arXiv:2404.02935, 2024.
  * [11] Xiaohua Wang, Yuliang Yan, Longtao Huang, Xiaoqing Zheng, and Xuan-Jing Huang,  “Hallucination detection for generative large language models by bayesian sequential estimation,”  in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 15361–15371.
  * [12] Amos Azaria and Tom Mitchell,  “The internal state of an llm knows when it’s lying,”  in The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
  * [13] Weihang Su, Changyue Wang, Qingyao Ai, Yiran Hu, Zhijing Wu, Yujia Zhou, and Yiqun Liu,  “Unsupervised real-time hallucination detection based on the internal states of large language models,”  arXiv preprint arXiv:2403.06448, 2024.
  * [14] Chao Chen, Kai Liu, Ze Chen, Yi Gu, Yue Wu, Mingyuan Tao, Zhihang Fu, and Jieping Ye,  “Inside: Llms’ internal states retain the power of hallucination detection,”  in The Twelfth International Conference on Learning Representations, 2023.
  * [15] Shiqi Chen, Yiran Zhao, Jinghan Zhang, I-Chun Chern, Siyang Gao, Pengfei Liu, and Junxian He,  “Felm: Benchmarking factuality evaluation of large language models,”  in Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
  * [16] Matthew S Crouse, Robert D Nowak, and Richard G Baraniuk,  “Wavelet-based statistical signal processing using hidden markov models,”  IEEE Transactions on signal processing, vol. 46, no. 4, pp. 886–902, 1998.
  * [17] J-B Durand, Paulo Goncalves, and Yann Guédon,  “Computational methods for hidden markov tree models-an application to wavelet trees,”  IEEE Transactions on Signal Processing, vol. 52, no. 9, pp. 2551–2560, 2004.
  * [18] Ekaterina Fadeeva, Aleksandr Rubashevskii, Artem Shelmanov, Sergey Petrakov, Haonan Li, Hamdy Mubarak, Evgenii Tsymbalov, Gleb Kuzmin, Alexander Panchenko, Timothy Baldwin, et al.,  “Fact-checking the output of large language models via token-level uncertainty quantification,”  arXiv preprint arXiv:2403.04696, 2024.
  * [19] Tianyu Liu, Yizhe Zhang, Chris Brockett, Yi Mao, Zhifang Sui, Weizhu Chen, and William B Dolan,  “A token-level reference-free hallucination detection benchmark for free-form text generation,”  in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2022, pp. 6723–6737.
  * [20] Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston,  “Chain-of-verification reduces hallucination in large language models,”  arXiv preprint arXiv:2309.11495, 2023.
  * [21] Junyi Li, Xiaoxue Cheng, Wayne Xin Zhao, Jian-Yun Nie, and Ji-Rong Wen,  “Halueval: A large-scale hallucination evaluation benchmark for large language models,”  in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 6449–6464.
  * [22] Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A Smith,  “How language model hallucinations can snowball,”  arXiv preprint arXiv:2305.13534, 2023.
  * [23] Esin Durmus, He He, and Mona Diab,  “Feqa: A question answering evaluation framework for faithfulness assessment in abstractive summarization,”  in Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020, pp. 5055–5070.
  * [24] QIU Yifu, Yftah Ziser, Anna Korhonen, Edoardo Ponti, and Shay B Cohen,  “Detecting and mitigating hallucinations in multilingual summarisation,”  in The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
  * [25] Meng Cao, Yue Dong, and Jackie Chi Kit Cheung,  “Hallucinated but factual! inspecting the factuality of hallucinations in abstractive summarization,”  in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2022, pp. 3340–3354.
  * [26] Derek Tam, Anisha Mascarenhas, Shiyue Zhang, Sarah Kwan, Mohit Bansal, and Colin Raffel,  “Evaluating the factual consistency of large language models through news summarization,”  in Findings of the Association for Computational Linguistics: ACL 2023, 2023, pp. 5220–5255.
  * [27] Katherine Lee, Orhan Firat, Ashish Agarwal, Clara Fannjiang, and David Sussillo,  “Hallucinations in neural machine translation,”  2018\.
  * [28] Nuno M Guerreiro, Elena Voita, and André FT Martins,  “Looking for a needle in a haystack: A comprehensive study of hallucinations in neural machine translation,”  arXiv preprint arXiv:2208.05309, 2022.
  * [29] Nuno Miguel Guerreiro, Duarte M Alves, Jonas Waldendorf, Barry Haddow, Alexandra Birch, Pierre Colombo, and André FT Martins,  “Hallucinations in large multilingual translation models,”  Transactions of the Association for Computational Linguistics, vol. 11, 2023.
  * [30] David Dale, Elena Voita, Janice Lam, Prangthip Hansanti, Christophe Ropers, Elahe Kalbassi, Cynthia Gao, Loïc Barrault, and Marta Costa-jussà,  “Halomi: A manually annotated benchmark for multilingual hallucination and omission detection in machine translation,”  in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 638–653.
  * [31] Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung,  “Survey of hallucination in natural language generation,”  ACM Computing Surveys, vol. 55, no. 12, pp. 1–38, 2023.
  * [32] Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, et al.,  “A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions,”  arXiv preprint arXiv:2311.05232, 2023.
  * [33] Kurt Shuster, Spencer Poff, Moya Chen, Douwe Kiela, and Jason Weston,  “Retrieval augmentation reduces hallucination in conversation,”  in Findings of the Association for Computational Linguistics: EMNLP 2021, 2021, pp. 3784–3803.
  * [34] Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen-tau Yih, Pang Koh, Mohit Iyyer, Luke Zettlemoyer, and Hannaneh Hajishirzi,  “Factscore: Fine-grained atomic evaluation of factual precision in long form text generation,”  in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 12076–12100.
  * [35] I Chern, Steffi Chern, Shiqi Chen, Weizhe Yuan, Kehua Feng, Chunting Zhou, Junxian He, Graham Neubig, Pengfei Liu, et al.,  “Factool: Factuality detection in generative ai–a tool augmented framework for multi-task and multi-domain scenarios,”  arXiv preprint arXiv:2307.13528, 2023.
  * [36] Sina Semnani, Violet Yao, Heidi Zhang, and Monica Lam,  “Wikichat: Stopping the hallucination of large language model chatbots by few-shot grounding on wikipedia,”  in Findings of the Association for Computational Linguistics: EMNLP 2023, 2023, pp. 2387–2413.
  * [37] Siqing Huo, Negar Arabzadeh, and Charles LA Clarke,  “Retrieving supporting evidence for llms generated answers,”  arXiv preprint arXiv:2306.13781, 2023.
  * [38] Jifan Chen, Grace Kim, Aniruddh Sriram, Greg Durrett, and Eunsol Choi,  “Complex claim verification with evidence retrieved in the wild,”  arXiv preprint arXiv:2305.11859, 2023.
  * [39] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.,  “Chain-of-thought prompting elicits reasoning in large language models,”  Advances in neural information processing systems, vol. 35, pp. 24824–24837, 2022.
  * [40] Neeraj Varshney, Wenlin Yao, Hongming Zhang, Jianshu Chen, and Dong Yu,  “A stitch in time saves nine: Detecting and mitigating hallucinations of llms by validating low-confidence generation,”  arXiv preprint arXiv:2307.03987, 2023.
  * [41] Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark,  “Explaining answers with entailment trees,”  in Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021, pp. 7358–7370.
  * [42] Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark,  “Entailer: Answering questions with faithful and truthful chains of reasoning,”  arXiv preprint arXiv:2210.12217, 2022.
  * [43] Yuxia Wang, Revanth Gangi Reddy, Zain Muhammad Mujahid, Arnav Arora, Aleksandr Rubashevskii, Jiahui Geng, Osama Mohammed Afzal, Liangming Pan, Nadav Borenstein, Aditya Pillai, et al.,  “Factcheck-gpt: End-to-end fine-grained document-level fact-checking and correction of llm output,”  arXiv preprint arXiv:2311.09000, 2023.
  * [44] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica,  “Efficient memory management for large language model serving with pagedattention,”  in Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
  * [45] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou,  “Self-consistency improves chain of thought reasoning in language models,”  in The Eleventh International Conference on Learning Representations, 2022.

##  Appendix A Appendix / supplemental material

###  A.1 Implementation Details

#### Data preprocessing

We preprocess the data in Wikibio-GPT3 [4] and FELM-Science [15] before
evaluating our method and baselines. The data preprocessing includes two
steps. First, we perform _decontextualization_ since the sentences in a
response generated by the LLM might be context-dependent and contain pronouns
or noun phrases that cannot be understood without full context. Take the first
data instance from Wikibio-GPT3 for demonstration, which is a biography of
“John Russell Reynolds” generated by an LLM. The second sentence within the
biography requiring hallucination detection is “He was born in London, the son
of a barrister, and was educated at Eton College and Trinity College,
Cambridge.” Without the context, we cannot identify the truthfulness of this
sentence due to the pronoun. Therefore, we first decontextualize the sentences
in the two datasets by prompting gpt-3.5-turbo-0125. The prompt is available
in Figure 9.

Second, we further manually clean up the dataset by filtering out some
sentences that are not check-worthy but still annotated as “true” in the
datasets. For example, the FELM contains some sentences such as “Sure!” and
“If you have any further questions or concerns, please let me know.”. These
sentences are annotated as “true” and will be counted into performance
evaluation. Since both two datasets contains not too many examples, we
manually filter out these sentences to exclude them in our evaluation. The
datasets after our preprocessing and filtering are available in the
supplemental material and will be made open-sourced.

#### Implementation of our method

We use the vLLM [44] to perform the inference of Llama-3-8B-Instruct. We use a
single NVIDIA A100 80GB PCIe GPU to evaluate the performance and report the
time cost in Figure 4. For the emission probability estimation (Table 1), we
use the first 120 examples in the Wikibio-GPT3 dataset (50% of it) to compute
the empirical estimation of the emission probability. The model we use is
gpt-3.5-turbo-0125. Then we transfer the estimated emission probabilities to
the remaining examples in Wikibio-GPT3 and other datasets for performance
evaluation. For Llama-3-8B-Instruction, we also use the same estimated
emission probabilities. Additionally, since we set the model confidence on
child nodes generated by statement correction as 1.0 rather than probe the
model’s confidence, we maintain an individual emission probability for those
child nodes ($p(S_{u}=1|Z_{u}=1)=0.8$ and $p(S_{u}=1|Z_{u}=0)=0.2$). During
the belief tree construction process, we add several constraints to boost the
efficiency. Specifically, we only apply statement decomposition to the root
node, assuming the child nodes generated by the LLM is atomic statements that
only contain one aspect of information. Also, we do not expand nodes generated
by statement correction, as they are homogeneous to their parent node.

#### Implementation of baselines

We follow the default configuration of each baselines. For SelfCheckgpt, we
sample 20 additional responses for hallucination detection. Similarly, we also
sample 20 different answers for chain-of-thought prompting and aggregate them
using self-consistency [45]. For Maieutic-Prompting, we use their prompts for
the CREAK datasets to generate belief trees in our evaluation.

###  A.2 Examples of Belief Trees

Figure 5: Belief tree example.

We visualize several constructed belief trees as well as how our method
leverage the inconsistencies in model’s beliefs for hallucination detection.
We start with a simple example from the Wikibio-GPT3 dataset [4] shown in
Figure 5. Starting from the root node about Adiele Afigbo, the first layer
contains 3 child nodes generated by statement decomposition. However, despite
the statement is wrong, the model (gpt-3.5-turbo-0125) assign a high
confidence score to both the original statement and the child nodes decomposed
from the root node. Then, our method further generate child nodes for node
1,2, and 3. We display the child nodes of node 3 in the figure, which is
generated by statement correction. With the three different statements about
the date of death of that person, we decrease the model’s confidence on node 3
and finally correct the model’s belief on the root node. Note that in
statement correction, we directly set the confidence of the generated child
nodes as 1.0. For this example, if we query the model’s confidence scores on
node 4, 5, and 6, we will get confidence scores 0.97, 0.91, 0.88,
respectively, which will still contradicts to their parent node.

Figure 6: Belief tree example.

Another example of the belief tree is shown in Figure 6, which mainly consists
of child nodes generated by supportive and contradictory premises. At the root
node, the model assigns a high confidence score to the statement about
freezing point of water from the FELM dataset [15]. After the statement
decomposition, the inconsistency is triggered due to model’s low confidence on
node 2. Furthermore, if we continuously generate premises for node 1, we get
two additional child nodes (node 3 and 4) that are contradictory to their
parent node. However, the model still assigns a high confidence to node 3 and
4. Within the belief propagation framework, the conditional probability of
node 1 being true given the observations on node 3 and 4 will be decreased.
Similarly, this effect will propagate to the root node and lead to a low
posterior probability of the root node being true.

Figure 7: Belief tree example.

We then show one failure case of our method in Figure 7. The target statements
comes from the FactCheckGPT dataset [43]. Our method first generation two
supportive premises with high confidence. These two child nodes are indeed
reasonable and can support the opinion that “Linux operating system has a
widespread adoption.”, thus contradicting to the root statement and further
decreasing the model’s confidence on the root node. We hypothesize that the
original statement, “Linux adoption has limited compared to other operating
systems like Windows and macOS” lacks sufficient specificity and could be
interpreted from multiple perspectives. For example, it could refer to market
share in personal computing versus cloud computing domains, making the ground-
truth label nondeterministic.

###  A.3 Inferring the Posterior Probability of $Z_{0}$

The posterior probability $p(Z_{0}=1|\\{S_{u}\\})$ can be computed by:

$\displaystyle
p(Z_{0}=1|\\{S_{u}\\})=\frac{p(Z_{0}=1,\\{S_{u}\\})}{p(Z_{0}=1,\\{S_{u}\\})+p(Z_{0}=0,\\{S_{u}\\})},$
(2)

where $\\{S_{u}\\}=\\{s_{u}\\}$ refers to the set of all observed variables in
the belief tree.

Therefore, the key of the inference on the belief tree is to compute the two
joint probabilities $p(Z_{0}=1,\\{S_{u}\\})$ and
$p(S_{1}=\texttt{False},\bar{\bm{X}}_{1}=\bar{\bm{x}}_{1})$. Following the
conditional independence assumption in the hidden Markov model, the
truthfulness (_i.e,_ , states of hidden variables) of each node is determined
by its parent node in the tree and the transition probability. Also, the
model’s confidence (_i.e._ , states of observed variables) on each node is
determined by the state of the corresponding variable and the emission
probability. With such an assumption, they can be decomposed as:

$\displaystyle p(Z_{0}=1,\\{S_{u}\\})$
$\displaystyle=p(\\{S_{u}\\}|Z_{0}=1)*p(Z_{0}=1),$ (3)

where $p(Z_{0}=1)$ is the prior probability of the statement being true (note
that we set it to be 0.5 in this paper). $p(\\{S_{u}\\}|Z_{0}=1)$ is the
conditional probability of all observed variables (exclude the root node)
given the root node being true. Recall that we introduce a notation
$\beta(z,u)=p(S_{\mathcal{T}(u)})|Z_{u}=z$ to represent such conditional
probabilities, where $S_{{\mathbb{T}}(u)}$ refers to the confidence scores
(observed variables) of all nodes on the subtree rooted at node $u$.
Therefore, the conditional probability $p(\\{S_{u}\\}|Z_{0}=1)$ can be denoted
as $\beta(1,0)$ (node $0$, hidden variable $Z_{0}=1$).

Without loss of generality, we discuss below how to compute $\beta(z,u)$ for
an arbitrary node $u$ in the tree. The computation for $\beta(1,0)$ and
$\beta(0,0)$ can be performed in exactly the same way. Specifically, we can
further decompose $\beta(z,u)$ as:

$\displaystyle p(S_{\mathcal{T}(u)})|Z_{u}=z)$
$\displaystyle=\left\\{\prod_{v\in\bm{{\mathcal{C}}}(u)}p(S_{\mathcal{T}(v)}|Z_{u}=z)\right\\}p(S_{u}|Z_{u}=z).$
(4)

The probability $p(S_{\mathcal{T}(v)}|Z_{u}=z)$ can be decomposed as:

$\displaystyle\centering p(S_{\mathcal{T}(v)}|Z_{u}=z)$
$\displaystyle=\sum_{k\in\\{0,1\\}}p(S_{\mathcal{T}(v)}|Z_{v}=k)*p(Z_{v}=k|Z_{u}=z)$
(5) $\displaystyle=\sum_{k\in\\{0,1\\}}\beta(v,k)*p(Z_{v}=k|Z_{u}=z).$

Therefore, the conditional probability
$\beta(z,u)=p(S_{\mathcal{T}(u)})|Z_{u}=z)$ can be computed in a recursive
manner:

$\displaystyle\beta(z,u)=\left\\{\prod_{v\in\bm{{\mathcal{C}}}(u)}\sum_{k\in\\{0,1\\}}\beta(v,k)*\underbrace{p(Z_{v}=k|Z_{u}=z)}_{\text{Transition
Probability}}\right\\}\underbrace{p(S_{u}|Z_{u}=z)}_{\text{Emission
Probability}}.$ (6)

There are two types of probabilities in the above equation. First,
$p(S_{u}|Z_{u}=z)$ is the “emission probability" at node $u$. Second,
$p(Z_{v}=k|Z_{u}=z)$ is the “transition probability" from node $u$ to its
child node $v$. The recursive computation in Equation 6 will starts from the
leaf nodes. When $v$ is the leaf node in the tree, $\beta(v,k)$ is actually
$p(S_{v}|Z_{v}=k)$, which is the emission probability at node $v$. Such a
process propagates from bottom to up. Finally, we can compute $\beta(1,0)$ as
well as the joint probability $p(Z_{0}=1|\\{S_{u}\\})$ according to Equation
3.

#### Beyond conditional independence: transition probability for statement
decomposition.

The above computation of the posterior probability is based on the assumption
of conditional independence. Assume the node $u$ have two child nodes, $v_{1}$
and $v_{2}$. Then we consider the transition probabilities from $u$ to $v_{1}$
and from $u$ to $v_{2}$ independently. However, this does not hold for the
child nodes generated by statement decomposition, in which the truthfulness of
the child nodes are influenced by their parent node simultaneously. If $u$ is
true, then we know that both two child nodes are also true. In contrast, if
$u$ is false, we can only infer that at least one of the child nodes are
false. To handle such a case, we revise the probability computation in
Equation 4 accordingly. Assume node $u$ has $m$ child nodes. The probability
$\beta(z,u)=p(S_{\mathcal{T}(u)})|Z_{u}=z)$ can be computed as:

$\displaystyle\centering p(S_{\mathcal{T}(u)})|Z_{u}=z)$ $\displaystyle
p(S_{u}|Z_{u}=z)\cdot\sum_{Z_{\mathcal{C}(u)}\in\\{0,1\\}^{m}}p(Z_{\mathcal{C}(u)}|Z_{u}=z)\prod_{v\in\mathcal{C}(u)}\beta(Z_{v},v),$
(7)

which is the Equation 1 in the main paper.

###  A.4 Summary of the Algorithm

Algorithm 1 BTProp Algorithm

1:Input: Statement $u_{0}$, maximum tree depth $d_{\mathrm{max}}$

2:Output: The posterior probability $p(Z_{0}=1|S_{\mathcal{T}(0)})$.

3:

4:Initialize the belief tree $\mathcal{T}$ with root node $u_{0}$

5:Initialize the leaf node set $\mathcal{N}=\\{u_{0}\\}$

6:while $\mathcal{N}\neq\oslash$ do $\triangleright$ Belief tree construction

7: Pop an element $u$ from $\mathcal{N}$

8: Generate child nodes $\mathcal{C}(u)$ for $u$

9: for Node $v\in\mathcal{C}(u)$ do

10: Add $v$ to $\mathcal{T}$

11: Add $v$ to $\mathcal{N}$ if $d_{u}<d_{\mathrm{max}}$

12: end for

13:end while

14:

15:function GetBeta($u$, $z$) $\triangleright$ Compute $\beta(z,u)$ in Eq. 1

16: if $\mathcal{C}(u)=\oslash$ then

17: return $p(s_{u}|Z_{u}=z)$

18: end if

19: for $v\in\mathcal{C}(u)$ do

20: $\beta(v,0)=\textsc{GetBeta}(v,0)$

21: $\beta(v,1)=\textsc{GetBeta}(v,1)$

22: end for

23: Compute $\beta(u,z)$ according to Eq. 1

24: return $\beta(u,z)$

25:end function

26:

27:$\beta(1,0)$ = GetBeta($u=0$, $z=1$)

28:$\beta(0,0)$ = GetBeta($u=0$, $z=0$)

29:$p(Z_{0}=1|S_{\mathcal{T}(0)})=\beta(1,0)/(\beta(1,0)+\beta(0,0))$

We summarize the pipeline of our method in Algorithm 1. The root node of the
belief tree is the given statement $u_{0}$. During the belief tree
construction process, we maintain a set $\mathcal{N}$ that contains all
current leaf nodes of the belief tree. We recursively expand each leaf node
$u\in\mathcal{N}$ by its child nodes $\mathcal{C}(u)$ and add these new child
nodes to the belief tree if they are logically-connected to the current leaf
node. These generated child nodes then become new leaf nodes. They will also
be added to $\mathcal{N}$ and be expanded until the maximum depth is reached.
Given the constructed belief tree and the emission and transition
probabilities estimated from a held-out dataset, the posterior probability
$\beta(Z_{0}=1|S_{\mathcal{T}(0)})$ can be then computed in a recursive
manner, which will be further used to predict the truthfulness of the given
statement.

###  A.5 License of the Datasets Used

FactCheckGPT is under Apache-2.0 license. FELM is under CC-BY-NC-SA-4.0
license, and Wikibio-GPT3 is under CC-BY-SA-3.0 license. We have cited them
accordingly in the main paper.

###  A.6 Prompt

In this section, we list all the prompt used in this paper, including belief
tree construction, prior confidence estimation, and data preprocessing.

#### Belief tree construction

Given a statement from the LLM output, we use the following prompt
gpt-3.5-turbo-0125 to perform _statement decomposition_ , which is shown in
Figure 10. In the instruction, we specify the requirements to extract check-
worthy claims and provide the model with several examples. We also include an
additional special example, where the given sentence is actually a subjective
opinion, to prevent the model from decomposing sentences that are actually not
check-worthy. We use a similar prompt for Llama-3-8b-Instruction as shown in
Figure 11.

To generate _supportive and contradictory premises_ , we prompt the model as
follows: If the model judge the given statement as true, then it needs to
generate several explanations to its judgment, which form the supportive
premises. In contrast, if the model believes the given statement is false,
then it will generate explanations to its judgment, which form the
contradictory premises. The prompts we used are listed in Figure 12 and Figure
13. We first prompt the model with the prompt in Figure 12. If the model
judges the statement as true and generates supportive premises, then these
premises will be returned and contradictory premises will not be generated. If
the model judges the statement as false, then we prompt the model with the
prompt in Figure 13 for contradictory premises. Although there might be better
prompting strategies to generate such premises, finding the optimal prompts
and prompting strategies is out of the scope of this paper. Therefore, we
leave it for future work.

Finally, to generate child nodes via _statement correction_ , we adopt the
following pipeline. First, we prompt the model using prompts listed in Figure
14 and Figure 15 to generate a question about the key pieces of information in
the statement. After that, we feed the generated question to the LLM again
without any other prompt to get its answer. Finally, we ask the model to
revise the original statement according to the “background knowledge", which
is the answer generated by itself. By doing this, we expect to better utilize
the inconsistency across model’s beliefs for child node generation. The prompt
for the last step is shown in Figure 16

To select the most appropriate strategies for each node, we use the following
prompts to ask the LLM to output the most suitable strategies, which is
displayed in Figure 17 and Figure 18.

#### Prior confidence estimation

When prompt gpt-3.5-turbo-0125 for the confidence score on the truthfulness of
a statement, we use the following prompt: True or False? {target_statement}.
For Llama-3 model, we find it sometimes refuse to judge the truthfulness and
simply output it requires additional context. To enforce the model to output
the confidence score, we change the prompt accordingly:

⬇ Are the following statements true or false? For each of the following
statements, determine whether it is true or false. Provide a response of
’True’ if the statement is correct, or ’False’ if the statement is incorrect.
Remember: - You **do not** have access to additional information or external
data. - If verifying the statement requires such external data or context,
regard it as false. - Directly output "True" or "False" without adding any
markers. Figure 8: Prompt for confidence estimation (Llama-3-8B-Instruct). ⬇
**Rewrite Texts for Clarity** In this task, you will receive one paragraph and
one target statement extracted from it. The target statement is context-
dependent, which makes the statement hard for us to understand without context
and check its truthfulness. Therefore, your task is to rewrite the statement
to reduce context dependency. Specifically, - Pronoun resolution: Replacing
pronouns like "this," "the," "that," "he," "she," and "they" with specific
nouns or names they refer to in the original paragraph. You should always use
the full names. - If the target statement only use the first/last name to
refer to the main entity, replace the first/last name with the full name of
the entity if available. Note: do not modify the semantics of the sentence. Do
not add new information or your own descriptions into the statement.
**Input/Output Format** The input will be provided with the format as below:
Original paragraph: <the original text> Target statement: <the target
statement needing rewrite> Format your output as: Output: <the target
statement after rewrite> Figure 9: Prompt for data preprocessing. ⬇ **Fact-
Checking Claims Extraction:** **Objective:** Analyze the provided statement to
extract and list all distinct factual claims that require verification. Each
listed claim should be verifiable and not overlap in content with other claims
listed. **Instructions:** 1. **Identify Factual Claims**: - Identify parts of
the statement that assert specific, verifiable facts, including: - Statistical
data and measurements. - Historical dates and events or other information. -
Direct assertions about real-world phenomena, entities, events, statistics -
Conceptual understandings and theories. - In every claim, alway use the **full
names** when referring to any concept, person, or entity. **Avoiding the use
of pronouns or indirect references** that require contextual understanding. 2.
List each verifiable claim separately. Ensure that each claim is distinct and
there is no overlap in the factual content between any two claims. - If a
single claim is repeated in different words, list it only once to avoid
redundancy. 3. **Output:** - If there are multiple check-worthy claims, list
each one clearly and separately. - If there is only one check-worthy claim,
output just that one claim. - If no part of the statement contains verifiable
facts (e.g., purely subjective opinions, hypothetical scenarios), output the
following message: "Claim 1: No check-worthy claims available." **Output
Format**: Your output should be organized as follows: Claim 1: <the first
claim> Claim 2: <the second claim> Claim 3: <the third claim (if necessary)>
... **Examples:** Statement: According to recent data, China has surpassed the
United States in terms of GDP when measured using Purchasing Power Parity
(PPP), and India is projected to overtake China by 2030. Claim 1: China has
surpassed the United States in terms of GDP when measured using Purchasing
Power Parity (PPP). Claim 2: India is projected to overtake China in terms of
GDP by 2030." Statement: The world’s largest desert is Antarctica, and it is
larger than the Sahara. Claim 1: The world’s largest desert is Antarctica.
Claim 2: Antarctica is larger than the Sahara. Statement: I think pizza is the
best food ever! Claim 1: No check-worthy claims available. Statement: The
software ’Photoshop’ was released by Adobe Systems in 1988. Claim 1: The
software ’Photoshop’ was released by Adobe Systems in 1988. Figure 10: The
prompt for statement decomposition using gpt-3.5-turbo-0125. ⬇ **Fact-Checking
Claims Extraction:** **Objective:** Analyze the provided statement to extract
and list all distinct factual claims that require verification. Each listed
claim should be verifiable and not overlap in content with other claims
listed. **Instructions:** 1. Identify parts of the statement that assert
specific, verifiable facts. In every claim, alway use the **full names** when
referring to any concept, person, or entity. **Avoiding the use of pronouns or
indirect references** that require contextual understanding. 2. List each
verifiable claim separately. Ensure that each claim is distinct and there is
no overlap in the factual content between any two claims. 3. Exclude any
statements that are purely hypothetical, assume theoretical scenarios, or are
speculative in nature. These do not contain verifiable factual claims. For
example, statements involving assumptions ("Let’s assume..."), theoretical
discussions ("consider whether..."), or purely speculative scenarios should
not be considered as containing verifiable claims. 4. If the statement does
not contain any verifiable facts, output the following message: "Claim 1: No
check-worthy claims available." **Output Format**: Your output should be
organized as follows: Claim 1: <the first claim> Claim 2: <the second claim>
Claim 3: <the third claim (if necessary)> ... **Examples:** Statement:
According to recent data, China has surpassed the United States in terms of
GDP when measured using Purchasing Power Parity (PPP), and India is projected
to overtake China by 2030. Claim 1: China has surpassed the United States in
terms of GDP when measured using Purchasing Power Parity (PPP). Claim 2: India
is projected to overtake China in terms of GDP by 2030." Statement: The
world’s largest desert is Antarctica, and it is larger than the Sahara. Claim
1: The world’s largest desert is Antarctica. Claim 2: Antarctica is larger
than the Sahara. Statement: I think pizza is the best food ever! Claim 1: No
check-worthy claims available. Statement: Let’s assume there is a highest
prime number and consider its implications on number theory. Claim 1: No
check-worthy claims available. Figure 11: The prompt for statement
decomposition using Llama-3-8b-Instruct. ⬇ **Finding Supportive Premises** Is
the following statement true or false? If it is true, list several supportive
premises for it. **Important Rules:** 1. Each premise should be clearly stated
and directly relevant to the target statement. Avoid ambiguity and ensure that
the connection to the target statement is evident 2. Do not use pronouns in
generated premises. Ensure each premise can be understood clearly without any
context. For each generated premise, you should always use the full name of
each person, event, object, etc. **Input/Output Format**: Your output should
be organized as follows. Judgement: <True or False> Premise 1: <the first
premise> Premise 2: <the second premise> ... In contrast, if the statement is
false, you simly output: Judgement: False Premise 1: No supportive premises
applicable. **Examples:** Target statement: Renewable energy sources will lead
to a decrease in global greenhouse gas emissions. Judgement: True Premise 1:
Renewable energy sources produce electricity without emitting carbon dioxide.
Premise 2: Increasing the adoption of renewable energy reduces reliance on
fossil fuels, which are the primary source of industrial carbon dioxide
emissions. Target statement: Eating carrots improves night vision. Judgement:
False Premise 1: No supportive premises applicable. Statement: Historical
literacy enhances a society’s ability to make informed decisions. Judgement:
True Premise 1: Understanding historical events provides context for current
issues, enabling citizens to make decisions that consider past outcomes and
lessons. Premise 2: Historical literacy fosters critical thinking skills,
which are crucial in analyzing information and making reasoned decisions.
Premise 3: Societies with high levels of historical awareness can recognize
and avoid the repetition of past mistakes. Figure 12: The prompt for
generation of supportive premises. ⬇ **Finding Contradictory Premises** Is the
following statement true or false? If it is false, list several contradictory
premises for it. **Important Rules:** 1. Each premise should be clearly stated
and directly relevant to the target statement. Avoid ambiguity and ensure that
the connection to the target statement is evident 2. Do not use pronouns in
generated premises. Ensure each premise can be understood clearly without any
context. For each generated premise, you should always use the full name of
each person, event, object, etc. **Input/Output Format**: Your output should
be organized as follows. Judgement: <True or False> Premise 1: <the first
premise> Premise 2: <the second premise> ... In contrast, if the statement is
false, you simply output: Judgement: True Premise 1: No contradictory premises
applicable. **Examples:** Target statement: Renewable energy sources will lead
to a decrease in global greenhouse gas emissions. Judgement: True Premise 1:
No contradictory premises applicable. Target statement: Eating carrots
improves night vision. Judgement: False Premise 1: The belief that eating
carrots improves night vision stems from World War II propaganda, not from
scientific evidence. Premise 2: While carrots are rich in vitamin A, which is
necessary for maintaining healthy vision, they do not enhance night vision
beyond normal levels. Statement: The introduction of invasive species does not
impact native biodiversity. Judgement: False Premise 1: Invasive species often
compete with native species for resources, leading to a decline in native
populations. Premise 2: Studies show that invasive species can alter the
natural habitats of native species, negatively affecting their survival rates.
Premise 3: The introduction of the invasive zebra mussel in North American
waterways has led to significant declines in the populations of native
mussels. Figure 13: The prompt for generation of contradictory premises. ⬇
Given the following claim, your tasks include: 1. Identify the key pieces of
information critical for fact-checking to determine its truthfulness. 2.
Create a masked version of the claim by masking these key pieces of
information 3. Generate a question asking for the key pieces of information
Rules: 1. Do not mask the grammatical subject of the sentence \-- the actor,
entity, or object that performs the action in the sentence’s main clause.
Also, following the format of the below examples in your output. **Examples:**
Statement: Bitcoin was created in 2009 by an anonymous entity known as Satoshi
Nakamoto. Masked statement: Bitcoin was created in 2009 by an anonymous entity
known as [which person]. Question: Who created Bitcoin in 2009? Statement: The
iPhone was first released by Apple in 2007. Masked statement: The iPhone was
first released by Apple in [what year]. Question: Was the iPhone first
released by Apple in 2007? Statement: The speed of light in a vacuum is
approximately 299,792 kilometers per second. Masked statement: ’Romeo and
Juliet’ was written by Shakespeare in [what time period]. Question: What is
the speed of light in a certain medium? Statement: "Attention Is All You Need"
is a paper written by Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob
Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin.
Masked statement: "Attention Is All You Need" is a paper written by [whom]
Question: Who was/were the authors of the paper "Attention Is All You Need"?
Statement: The Great Wall of China is visible from space. Masked statement:
The Great Wall of China is [visible or invisible] from space. Question: Is the
Great Wall of China visible from space? Statement: The headquarters of the
United Nations is located in New York City Masked statement: The headquarters
of the United Nations is located in [which city]. Question: Where is the
headquarters of the United Nations located? Figure 14: Step 1 in statement
correction: question generation. This prompt is used for gpt-3.5-turbo-0125. ⬇
Given a statement, your task is to identify a general question that can be
used to check the truthfulness of the statement. The question should directly
address the claim to confirm or refute it without seeking additional detailed
information. **Examples:** Statement: Bitcoin was created in 2009 by an
anonymous entity known as Satoshi Nakamoto. Question: Who created Bitcoin in
2009? Statement: The iPhone was first released by Apple in 2007. Question:
When was iPhone first relased by Apple? Statement: ’Romeo and Juliet’ was
written by Shakespeare in the late 16th century. Question: When was ’Romeo and
Juliet’ was written by Shakespeare? Statement: "Attention Is All You Need" is
a paper written by Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit,
Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin. Question: Who
was/were the authors of the paper "Attention Is All You Need"? Statement: The
Eiffel Tower is located in Paris Question: Where is the Eiffel Tower located?
Statement: Albert Einstein was a physicist. Question: What profession was
Albert Einstein? Figure 15: Step 1 in statement correction: question
generation. This prompt is used for Llama-3-8b-Instruct. We adjust the prompt
since the masked statement is not used in the prompt for gpt-3.5-turbo-0125. ⬇
**Background Knowledge**: {the model answer in step 2} Leverage the above
provided knowledge and your own knowledge to review the correctness of
following statement: **Statement**: {statement} Instruction: - If the
statement is correct, output it unchanged. - If the statement is **not
mentioned in the background knowledge and its correctness cannot be
determined**, you should also directly output the statement **unchanged**. -
If the statement is wrong, revise only the parts of the statement that are
incorrect, to align with the background knowledge. Do not add any additional
sentences or details. **Output Format:** Format your output as: Revised
Answer: <Display the original statement if it is correct or not mentioned in
the background knowledge; display the revised statement if it is inaccurate>
Figure 16: Step 3 in statement correction: statement revision. ⬇ **Task:
Choose the Best Strategy for Premise Generation** We need to generate several
premises for a given target statement. These premises could either support or
contradict the target statement. Particularly, we have 2 techniques for
premise generation: 1. Logical Relationships: This involves creating premises
based on entailment or contradiction. You can generate premises that either
support or contradict the target statement. 2. Statement Perturbation: Create
variations of the statement by altering key details to form contradictory
premises. Given these techniques, your task is to select the most suitable
technique given a particular statement. Follow the guidelines below to select
the most suitable technique. **Important Guidelines**: 1. Prioritize logical
relationships. The logical relation strategy is broadly applicable, as long as
it is straightforward to find supportive or contradictory premises. 2. If a
statement contains particular names, numbers, timestamps, or other conditions
that can be varied to generate contradictory premises, consider statement
perturbation. 3. If both two methods are applicable, select them together and
output "both". **Output Format:** Your selection should be one of "Logical
Relation", "Statement Perturbation", and "both". Target statement: Eating a
balanced diet improves overall health. Output: Logical Relation Target
statement: ’War and Peace’ was a book written by Leo Tolstoy. Output:
Statement Perturbation Target statement: Water boils at 100 degrees Celsius at
sea level Output: both Target statement: Mount Everest is 8,848 meters tall.
Output: Statement Perturbation Target statement: Artificial intelligence will
replace most human jobs in the future Output: Logical Relation Figure 17:
Prompt for strategy selection (gpt-3.5-turbo-0125). ⬇ **Instruction for
Choosing the Best Strategy for Premise Generation** When tasked with
generating premises for a given target statement, the choice of strategy-
Logical Relationships or Statement Perturbation-should be determined based on
the nature of the statement and the desired objectives. Use the following
guidelines to route the choice: ### When to Use Logical Relationships Opt for
Logical Relationships when: - **The Statement is Abstract or Principled**:
Ideal for statements that explore broad principles, ethics, or abstract
concepts. This method helps in drawing deep logical entailments or
contradictions. - **Complex Relationships or Conditions**: When the statement
involves complex logical or conditional relationships, using this method
clarifies or challenges these intricacies. - **Requirement for Detailed
Analysis**: For statements needing precise and formal argumentation,
especially in academic or technical discussions. ### When to Use Statement
Perturbation Choose Statement Perturbation when: - **The Statement is Specific
and Concrete**: Best for statements with explicit details like scenarios,
dates, locations, names, numbers or timestamps. Altering these elements
generates varied premises. - **Exploration of Counterfactuals or
Hypotheticals**: Useful for creating imaginative or scenario-based premises by
modifying key details to envision different outcomes. - **Sensitivity to
Detail Changes**: When minor modifications in the statement can significantly
alter its implications or truth value. **Output Format:** Your selection
should be one of "Logical Relation", "Statement Perturbation", and "both".
Here "both" means both two methods are applicable. **Examples:** Target
statement: Eating a balanced diet improves overall health. Output: Logical
Relation Target statement: Countries with higher investment in education
consistently rank higher in global innovation indexes Output: Logical Relation
Target statement: ’War and Peace’ was a book written by Leo Tolstoy. Output:
Statement Perturbation Target statement: Water boils at 100 degrees Celsius at
sea level Output: both Target statement: Mount Everest is 8,848 meters tall.
Output: Statement Perturbation Target statement: The bridge will remain intact
even if 75 cars drive on it simultaneously if the cars are lightweight Output:
Statement Perturbation Target statement: Artificial intelligence will replace
most human jobs in the future Output: Logical Relation Figure 18: Prompt for
strategy selection (Llama-3-8b-Instruction).