% This must be in the first 5 lines to tell arXiv to use pdfLaTeX, which is strongly recommended.
\pdfoutput=1
% In particular, the hyperref package requires pdfLaTeX in order to break URLs across lines.

\documentclass[11pt]{article}

% Remove the "review" option to generate the final version.
\usepackage[final]{ACL2023}
\usepackage{amsfonts}

% Standard package includes
\usepackage{times}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{url}

% For proper rendering and hyphenation of words containing Latin characters (including in bib files)
\usepackage[T1]{fontenc}
% For Vietnamese characters
% \usepackage[T5]{fontenc}
% See https://www.latex-project.org/help/documentation/encguide.pdf for other character sets

% This assumes your files are encoded as UTF8
\usepackage[utf8]{inputenc}

% This is not strictly necessary, and may be commented out.
% However, it will improve the layout of the manuscript,
% and will typically save some space.
\usepackage{microtype}

% This is also not strictly necessary, and may be commented out.
% However, it will improve the aesthetics of text in
% the typewriter font.
\usepackage{inconsolata}

\usepackage{graphicx}
\graphicspath{ {./Figures/} }

% If the title and author information does not fit in the area allocated, uncomment the following
%
%\setlength\titlebox{<dim>}
%
% and set <dim> to something 5cm or larger.
\usepackage{courier}

\author{
 \textbf{Mohamed Rashad},
 \textbf{Ahmed Ismail Zahran},
 \textbf{Abanoub Amgad Amin},
 \\
 \textbf{Amr Yassin Abdelaal},
 \textbf{Mohamed AlTantawy}
\\
\\
 Agolo, New York, NY
\\
 \texttt{
   \{mohamed.rashad,ahmed.zahran,abanoub.amgad,
 }
\\
\texttt{
 amr.yassin,mohamed\}@agolo.com
 }
}


\title{FactAlign: Fact-Level Hallucination Detection and Classification Through Knowledge Graph Alignment}

\begin{document}

\maketitle
\begin{abstract}
Generative Large Language Models (LLMs) have garnered significant attention for their ability to generate human-like text across diverse domains. However, a major obstacle preventing their widespread adoption in production environments is their propensity for 'hallucinations' – the generation of non-factual statements that can erode confidence in their output. Existing hallucination detection approaches either require access to the categorical distribution of the output or rely on external databases to retrieve evidence about generated output. An alternative strategy employs sampling-based techniques, which generate responses multiple times to identify hallucinations. This paper proposes a novel black-box approach to automatically detect and classify hallucinations at a fact level by transforming the problem into a knowledge graph alignment task. This approach, unique in its applications, also allows us to classify detected hallucinations as either intrinsic or extrinsic. Our methodology was evaluated on the WikiBio GPT-3 hallucination dataset for hallucination detection and the XSum hallucination annotations dataset for hallucination classification. Our method achieved a 0.889 F1 for the hallucination detection and 0.825 F1 for the hallucination type classification, without any further training, fine-tuning, or producing multiple samples of the LLM response.
\end{abstract}

\section{Introduction}
Large Language Models (LLMs) have showcased impressive performance in significant tasks such as natural language understanding \cite{du2022shortcut}, language generation \cite{axelsson2023using}, and complex reasoning \cite{hao2023reasoning}.
Despite their widespread applications, LLMs are prone to hallucinate \cite{ji2023survey}, which makes them difficult to rely on. 

Existing literature focuses on robust hallucination detection mechanisms to ensure the reliability and accountability of NLP systems \cite{corlett2019hallucinations}.
However, recent approaches require access to either the token-level probability distribution \cite{manakul2023selfcheckgpt} or external databases \cite{bayat2023fleek} that are rarely available. 
Another approach relies on sampling that requires multiple LLM calls \cite{manakul2023selfcheckgpt}.

Due to these limitations, we introduce a novel approach that transforms hallucination detection into a knowledge graph alignment task.

Our approach is established on the notion that faithful generation should be semantically aligned with the source text. The degree of alignment was modeled as a metric to score the faithfulness of the generated text. Extending beyond mere detection, our approach is capable of classifying detected hallucinations into intrinsic and extrinsic categories. According to \cite{maynez2020faithfulness}, intrinsic hallucinations are defined as manipulation of the information present in the input document, while extrinsic hallucinations involve adding information not directly inferable from the input document.
By distinguishing between these categories, our method enhances the interpretability of detected hallucinations, providing valuable insights into the underlying causes.

\section{Related Work}
\begin{figure*}
    \centering
    \includegraphics[width=0.75\paperwidth]{hallucination_detection_example}
    \caption{Hallucination detection and classification pipeline}
    \label{fig:proposed_architecture}
\end{figure*}\
Current hallucination detection approaches can be classified according to the type of input required from the generative model as grey-box or black-box. Grey-box approaches, such as average and maximum token-level log probabilities \cite{manakul2023selfcheckgpt} are not restricted in their access to the generated text. However, token-level probabilities are not always accessible (e.g.: ChatGPT). Black-box approaches handle this limitation by only requiring the generated text. These approaches include proxy LLM-based approaches, external databases-dependent approaches, and sampling-based approaches.

\paragraph{Proxy LLM-based}
approaches, such as BARTScore \cite{yuan2021bartscore} use a proxy LLM to obtain token-level probabilities given the input text.
% On the SummEval dataset, a BART \cite{lewis2019bart} model fine-tuned on CNNDM \cite{hermann2015teaching} then on ParaBank2 \cite{hu2019large} achieves 0.401 Spearman correlation with the dataset's factuality scores.
% Another similar method, GPTScore \cite{fu2023gptscore}, uses GPT-3 to produce the token output probabilities.
% GPTScore can score multiple perspectives of the generated text by modifying the prompt to state the targeted task (e.g.: summarization, translation, etc.) and the aspect to be scored (e.g.: factuality, fluency, etc.).
The main limitation of these models is that the produced scores cannot be used to classify individual sentences.

% \paragraph{External databases-dependent}
% \textcolor{red}{approaches depend on obtaining data from external sources to judge generated text, which is useful when there is no or limited source text. This task formulation is more compound than mere hallucination detection since it combines resource retrieval with hallucination detection. For example, the FEVER Shared Task \cite{thorne2018fact} required participants to retrieve evidence from Wikipedia for classifying claims as supported or refuted.}

\paragraph{Factual data-dependent}
approaches compare the generated text to factual data.
For example, AlignScore \cite{zha2023alignscore} uses 4.7M training examples from several datasets to train a model on predicting an alignment score between factual and generated data.
Other approaches like \cite{thorne2018fact} utilize external sources, which is useful when there is no or limited source text.

\paragraph{Sampling-based}
approaches stochastically sample multiple outputs and detect hallucinations based on their consistency with the original output.
For example, SelfCheckGPT \cite{manakul2023selfcheckgpt} samples outputs and judges their consistency with the original output using either BERTScore \cite{zhang2019bertscore}, multiple-choice question answering, textual entailment, or prompting an LLM. In HaLo \cite{elaraby2023halo}, a pairwise entailment is computed between pairs of sentences from the original response and other sample responses using SUMMAC \cite{laban2022summac}.
% The main problem with these models is that they require the output to be sampled multiple times, which multiplies the generation cost by the sampling count.
% Another problem with these models is that since their hallucination detection decisions are based on the consistency of parallel sampling outputs, these models are incapable of deciding which of the output samples are factual and which are not. Therefore the actual result obtained from these hallucination detection models is practically a detection of cases where the model seems to be hallucinating instead of a decision that states whether a specific piece of text is hallucinated or not.

\section{Hallucination Detection and Classification Approach}

\begin{figure}
    \centering
    \includegraphics[width=0.31\paperwidth]{hallucination_detection_kg_construction}
    \caption{Knowledge graph construction}
    \label{fig:Knowledge_Graph_Construction}
\end{figure}\


Our approach detects and classifies hallucinations at a fact level using knowledge graph alignment. As shown in Figure \ref{fig:proposed_architecture}, the KG Constructor takes source and generated text as inputs and generates the corresponding KGs. The constructed KGs are passed to the Alignment module to produce the \textit{alignment score} for each generated triplet which is used to determine whether the generated triplet is hallucinated or factual.
The KG triplets from the source text and the hallucinated KG triplets from the generated text are passed to the Knowledge Change Detector (KCD), which produces a contradiction score for each of the hallucinated triplets, which in turn is used to classify whether the hallucination in this triplet is intrinsic or extrinsic.

\paragraph{Knowledge Graph Construction} We used a simple approach to automatically construct a Knowledge Graph from the text (see Figure \ref{fig:Knowledge_Graph_Construction}). First, we resolved each coreference to its reference using coreference resolution model\footnote{The FastCoref Python package was used \cite{Otmazgin2022FcorefFA}}. The text is then passed to NER\footnote{\href{https://huggingface.co/bert-base-multilingual-cased}{Multi-lingual NER BERT} was used to obtain named entities \cite{DBLP:journals/corr/abs-1810-04805}} to extract the named entities\footnote{We consider the following entity types: Person, Organization, Location, Date.}.
Finally, relation extraction\footnote{Relation Extraction from CoreNLP \cite{manning2014stanford} was used to obtain relational triplets.} is performed on the text. The produced relational triplets are filtered to remove triplets where the subject or the object is not in the named entities produced by the NER model.

% \subsection{Fact Level Processing}
% One edge that our approach has is the idea of Fact Level Processing in which we deal with each fact independently assessing how factual it is concerning the reference text. This allows our approach to look deeper within the generated text and avoid missing out on sub-factual inconsistencies.
% This is done by the process mentioned earlier, where we deal with facts as the input unit instead of full sentences where a fact is represented as a graph triplet <insert example> and that graph triplet independently goes through the alignment process.

\subsection{Hallucination Detection as KG Alignment}
\label{sec:Hallucination_Detection_as KG_Alignment}
% Our methodology can be seen as an abstract graph alignment task where we try to align facts within a generated text to facts from the reference text. This allows us to do a fact-checking process that is tightly bonded with the ground truth of the facts in hand.
% In the next sections, we will discuss the method in detail.

A simple approach for solving the KG alignment is to treat it as an assignment problem \cite{mao2021alignment}.
Given the set of all source entities $E_{s}$ and the set of all generated entities $E_{g}$, the input consists of four matrices: $A_{s} \in \mathbb{R}^{|E_{s}| \times |E_{s}|}$ and $A_{g} \in \mathbb{R}^{|E_{g}| \times |E_{g}|}$, which are the adjacency matrices of $KG_{s}$ and $KG_{g}$, respectively, and $H_{s} \in \mathbb{R}^{|E_{s}| \times d_{e}}$ and $H_{g} \in \mathbb{R}^{|E_{g}| \times d_{e}}$ which are the entity representation matrices for $KG_{s}$ and $KG_{g}$, where $d_e$ is the dimension of the entity representation vector space.
A permutation matrix P is used to represent the entity correspondences between $KG_{s}$ and $KG_{g}$, such that $P_{i,j} = 1$ indicates that $e_{i} \in KG_{s}$ and $e_{j} \in KG_{g}$ are an equivalent entity pair. Then, under the one-to-one constraint, the assignment problem can be solved using the following objective function
\begin{equation}
    \label{eq:assignment_problem_objective_fn}
    \operatorname*{arg\,min}_{P \in \mathbb{P}_{|E|}} \sum_{l=1}^{L} ||PA_{s}^{l}H_{s}-A_{g}^{l}H_{g}||_{F}^{2}
\end{equation}
where $l$ represents the depth of the adjacency matrix, $||.||_{F}$ represents the Frobenius norm and $\mathbb{P}_{N}$ represents
the set of all N-dimensional permutation matrices.

The above equation can be solved using algorithms like the Hungarian algorithm \cite{kuhn1955hungarian} and the Sinkhorn operation \cite{cuturi2013sinkhorn}.


We choose to perform alignment on the level of triplets instead of entities. For each triplet, a triplet representation is calculated by concatenating the elements of the triplet as a piece of text and passing it to a transformer-based model\footnote{\href{https://huggingface.co/sentence-transformers/all-distilroberta-v1}{DistilRoberta} pre-trained model from the SentenceTransformers \cite{reimers-2019-sentence-bert} Python framework was used as our transformer-based model.}.
This results in representation matrices $F_s \in \mathbb{R}^{|T_s|\times d_{t}}$ and $F_g \in \mathbb{R}^{|T_g| \times d_{t}}$, where $T_s$ is the sets of triplets from $KG_s$, $T_g$ is the set of triplets from $KG_g$, and $d_{t}$ is the dimension of the triplet representation vector space.
We simplify Equation \ref{eq:assignment_problem_objective_fn} by relaxing the one-to-one constraint, such that one triplet from the $KG_{s}$ can support multiple triplets from the $KG_{g}$.

The best match for each generated triplet $t_j \in T_{g}$ from all source triplets $t_i \in T_{s}$ is calculated using the following formula
\begin{equation}
    \operatorname*{arg\,min}_{t_{i} \in T_{s}} ||v_i^T  F_{s}  - v_j^T  F_g ||_{2}
\end{equation}
% \begin{equation}
%     v_i = \delta(i, k) = \begin{cases}
%     1 & \text{if } i = k \\
%     0 & \text{if } i \neq k
%     \end{cases}
% \end{equation}
where $v_i$ and $v_j$ are the one-hot vectors corresponding to $t_i$ and $t_j$, respectively.

The corresponding alignment score $s_a$ is computed as
\begin{equation}
    s_a = 1 - \operatorname*{min}_{t_{i} \in T_{s}} ||v_i^T  F_{s}  - v_j^T  F_g ||_{2}
\end{equation}
where $0 \le s_a \le 1$. If $s_a$ is higher than a specific threshold (described in Section \ref{sec:Experimental Setup }), the triplet is considered to be factual, and is considered to be hallucinated otherwise as shown in Figure \ref{fig:proposed_architecture}.

\begin{figure}
    \centering
    \includegraphics[width=0.31\paperwidth]{KGD}
    \caption{Knowledge Change Detector (KCD) takes the sets of triplets $T_g$ of knowledge graph $KG_g$ and $T_s$ of $KG_{s}$. For each triplet $t_j \in T_{g}$, an NLI model is used to compute the contradiction scores between $t_j$ and $t_i$ $\forall t_i \in KG_{s}$ and find the maximum contradiction score.}
    \label{fig:KCD}
\end{figure}

\subsection{Hallucination Classification}
% Aligning the generated triplets with the graph constructed from the source text not only serves as an indicator of potential hallucination but also provides invaluable insights. Recognizing whether a generated triplet results from hallucination holds significant importance in itself. However, our aim extended beyond mere identification; we sought to leverage this insight for making informed, actionable decisions.
We extend our approach beyond hallucination detection to classification using a Knowledge Change Detector (KCD) module (see Figure \ref{fig:KCD}) that computes a \textit{contradiction score} (ranging from 0 to 1) between hallucinated and source triplets using an NLI model \footnote{\href{https://huggingface.co/MoritzLaurer/DeBERTa-v3-base-mnli-fever-anli}{DeBERTa-v3-base-mnli-fever-anli} was used for NLI \cite{laurer2022less}}.
This score quantifies knowledge alteration introduced by LLMs.
If this score is higher than a specific threshold (described in section \ref{sec:Experimental Setup }), the generated knowledge is considered to be manipulated (intrinsic hallucination).
Otherwise, it is considered to be unsupported by the original text (extrinsic hallucination).

% By combining the contradiction score with the alignment score, The Hallucination Classifier module can discern whether the generated text results from unsupported information with a low alignment score (extrinsic hallucination) or from knowledge manipulation in triplets with a high contradiction score (intrinsic hallucination).

\section{Experimental Setup }
\label{sec:Experimental Setup }
\paragraph{Datasets} To evaluate our hallucination detection approach, we used the WikiBio GPT-3 hallucination
dataset \cite{manakul2023selfcheckgpt} which contains 238 Wikipedia-like passages generated using GPT-3 (text-davinci-003).
The passages are divided into sentences, each annotated as containing accurate information, minor inaccuracies, or major inaccuracies. We grouped major and minor inaccurate labels into a hallucinated class, labeled as 1, while the accurate class was labeled as 0.
10\% of the data was reserved for hyperparameter optimization and the results were reported on the rest of the dataset.
For the hallucination classification task, we used the XSum hallucination annotated dataset \cite{maynez2020faithfulness}, containing 500 randomly sampled articles from the XSum dataset \cite{narayan2018don} and the corresponding summaries from multiple generative models.
Hallucinated spans were annotated as containing intrinsic or extrinsic hallucination.

% The dataset contains four generated summaries for each document along with the original gold summary from XSum.
% The four models used to generate these summaries are \textsc{PtGen} \cite{see2017get}, \textsc{TConvS2S} \cite{narayan2018don}, \textsc{TranS2S}, and \textsc{BERTS2S} \cite{rothe2020leveraging}.
% For each summary, if the summary contains a hallucinated span of text, this span is annotated with its start and end offsets and the type of hallucination that occurs in this span (either intrinsic or extrinsic hallucination).

\paragraph{Hyperparameter Optimization} Bayesian optimization \footnote{ Scikit-optimize \cite{head_2020_4014775} was used for Bayesian optimization.} was performed for 30 iterations to decide the alignment and contradiction score thresholds (set to 0.863 and 0.984, respectively).

\paragraph{Baselines}
We evaluate our method against two baselines: SelfCheck with NLI \cite{manakul2023selfcheckgpt} and AlignScore-Large \cite{zha2023alignscore}. For both methods, the threshold is set to the value that maximizes the F1 score (0.54 for SelfCheck and 0.7 for AlignScore).

\section{Results}
\label{sec:results}
The proposed method was evaluated on the tasks of hallucination detection using precision, recall, and F1-score.
The evaluation was performed on the level of sentences to be compared to sentence-level hallucination detection baselines.
Given a generated sentence $s_i \in S$, where $S$ is the set of all generated sentences in the test set, we computed the set of triplets $t_j \in T_g$, where $T_g$ is the set of triplets constructed from the generated sentence $s_i$.
A sentence was classified as hallucinated if it included at least one hallucinated triplet.

As shown in table \ref{tab:results2}, our hallucination detection method achieves a recall of 0.992 on the task of sentence-level hallucination detection on WikiBio, which is higher than that achieved by the reported baselines without any fine-tuning, training, or using of additional generated samples.
While our method obtained less precision compared to the baselines, the overall F1-score of FactAlign is still higher.
The results show the effectiveness of fact-level hallucination detection used in our method.
% A gap exists between the recall 0.9354 and precision 0.7647; this is because (i) using a weaker KG constructor, which may result in producing triplets that are not meaningful enough to obtain a suitable alignment score (ii) not using an embedding model that is fine-tuned for producing knowledge graph embeddings.

Table \ref{tab:results1} reports the fact-level results for intrinsic vs. extrinsic hallucination classification, where each triplet constitutes a generated fact.
For the sets of annotated hallucination spans $P$ and the set of extracted triplets $T_g$ in a test example, a triplet $t_j \in T_G$ was annotated as hallucinated if its text overlapped with a hallucinated span $p_i \in P$.
As shown in the table, FactAlign achieves reasonable fact-level hallucination classification metrics.
% Each span in the list of annotated spans $P = \{{p_1, ..., p_N}\}$ in each example were matched to the list of extracted triplets $T_g = \{{t_1, ..., t_M}\}$ in the same example based on their text overlap.

% \begin{table}[ht]
% \centering
% \caption{Results on the XSum hallucination annotations dataset}
% \label{tab:results1}
% \begin{tabular}{|l|c|c|c|c|}
% \hline
% \multicolumn{4}{|c|}{Factual vs Hallucinated} \\
% \hline
%  Accuracy & Recall & Precision & F1 \\
% \hline
%  98.57\% & 0.9354 & 0.7647 & 0.8414 \\
% \hline
% \multicolumn{4}{|c|}{Intrinsic vs Extrinsic} \\
% \hline
%  Accuracy & Recall & Precision & F1 \\
% \hline
%  71.84\% & 0.8167 & 0.8328 & 0.8247 \\
% \hline
% \end{tabular}
% \end{table}

\begin{table}[ht]
\centering
\caption{Sentence-level hallucination detection results on the WikiBio GPT-3 hallucination dataset}
\label{tab:results2}
\begin{tabular}{l|l|l|l|}
\cline{2-4}
                                 & \multicolumn{1}{c|}{Precision} & \multicolumn{1}{c|}{Recall} & \multicolumn{1}{c|}{F1} \\ \hline
\multicolumn{1}{|l|}{SelfCheck}  & \textbf{0.843}                 & 0.917                       & 0.879                   \\ \hline
\multicolumn{1}{|l|}{AlignScore} & 0.809                          & 0.981                       & 0.886                   \\ \hline
\multicolumn{1}{|l|}{FactAlign}  & 0.805                          & \textbf{0.992}              & \textbf{0.889}          \\ \hline
\end{tabular}
\end{table}

\begin{table}[ht]
\centering
\caption{Fact-level hallucination classification results on the XSum hallucination annotations dataset}
\label{tab:results1}
\begin{tabular}{|c|c|c|}
\hline
Precision & Recall & F1    \\ \hline
0.833     & 0.817  & 0.825 \\ \hline
\end{tabular}
\end{table}

\section{Conclusion}
In this paper, we introduced a black-box hallucination detection technique based on constructing knowledge graphs from the source and generated text, aligning these knowledge graphs, and comparing the aligned triplets.
Our method achieved an F1-score of 0.889 on hallucination detection on the WikiBio dataset and 0.825 on hallucination-type classification on the XSum hallucination annotations dataset.
These results show the effectiveness of the knowledge graph alignment approach in the discovery and classification of individual hallucinated triplets.
Basing our approach on the level of triplets makes the hallucination detection output explainable and highlights the correct triplets that can later be used to correct hallucinations.


\newpage
\section*{Limitations}
Although our method can obtain high scores on the task of hallucination detection and classifying hallucinations, the method contains some limitations. This section highlights the limitations and possible future research directions.

\paragraph{Knowledge Graph Construction}
Our approach limits the entities in the constructed triplets to named entities, which means that this knowledge graph construction method may miss important triplets where the entities are not named entities.
In future studies, we plan to explore further relation extraction techniques to build more reliable knowledge graphs and explore their effect on hallucination detection.

\paragraph{Large-Scale Hallucination Detection}
Detecting Hallucination as a KG alignment task on scale presents a formidable challenge, considering that each generated triplet necessitates alignment with the entire source knowledge graph. In future studies, retrieval augmented generation (RAG) \cite{lewis2020retrieval} is investigated as a way to retrieve relevant triplets. This will allow selective retrieval of the relevant sub-graph that demands alignment, thereby circumventing the need to align with the entirety of the expansive KG.

% Entries for the entire Anthology, followed by custom entries
\bibliography{anthology,custom}
\bibliographystyle{acl_natbib}

\end{document}
