# Faster Game Solving by Fixpoint Acceleration

Daniel Hausmann111Supported by the ERC Consolidator grant D-SynMA (No. 772459)
University of Gothenburg, Sweden<EMAIL_ADDRESS>
###### Abstract

We propose a method for solving parity games with acyclic (DAG) sub-structures
by computing nested fixpoints of a DAG attractor function that lives over the
non-DAG parts of the game, thereby restricting the domain of the involved
fixpoint operators. Intuitively, this corresponds to accelerating fixpoint
computation by inlining cycle-free parts during the solution of parity games,
leading to earlier convergence. We also present an economic later-appearence-
record construction that takes Emerson-Lei games to parity games, and show
that it preserves DAG sub-structures; it follows that the proposed method can
be used also for the accelerated solution of Emerson-Lei games.

##  1 Background

The analysis of infinite duration games is of central importance to various
problems in theoretical computer science such as formal verification (model
checking), logical reasoning (satisfiability checking), or automated program
construction (reactive synthesis). Previous work has shown how fixpoint
expressions can be used to characterize winning in such games, which in turn
has enabled the development of symbolic game solving algorithms that
circumvent the state-space explosion to some extent and therefore perform
reasonably well in practice in spite of the high complexity of the considered
problems.

In this work, we build on the close connection between game solving and
fixpoint computation to obtain a method that accelerates the solution of
parity games with acyclic sub-structures. Intuitively, we base our method on
the observation that cycle-free parts in parity games can be dealt with
summarily by using the computation of attractors in place of handling each
node individually. In games that are largely cycle-free, but in which
attraction along cycle-free parts can be evaluated without exploring most of
their nodes, this significantly speeds up the game solution process.

The close relation between games and fixpoint expression has been well
researched. On one hand, it has been shown that winning regions in games with
various objectives can be characterized by fixpoint expressions [BruseFL14,
BloemJPPS12, PitermanP06, HausmannEA23]. The result for parity games (e.g.
[BruseFL14]) arguably is the best-known case: it has been shown that the
winning region in parity games with $k$ priorities can be specified by a modal
$\mu$-calculus formula (sometimes referred to as _Walukiewicz formulas_) with
alternation-depth $k$; this result connects parity game solving and model
checking for the $\mu$-calculus. It corresponds to arrow (1) in the diagram
below, which is meant to illustrate the context of our contribution.

fixpoint expressionsparity gamesEmerson-Lei gamesfixpoint games (2)Walukiewicz
formulas (1)LAR (3)

A fruitful reduction in the converse direction is more recent. _Fixpoint
games_ , that is, parity games of a certain structure (defined in detail
below), have been used to characterize the semantics of hierarchical fixpoint
equation systems in terms of games [BaldanKMP19]. While this reduction
(corresponding to arrow (2) in the diagram) incurs blow-up that is exponential
in the size of the domain of the equation system, it still proves helpful as
it allows for reasoning about nested least and greatest fixpoints in terms of
(strategies in) parity games. Fixpoint games have also been used to lift the
recent breakthrough quasipolynomial result for parity game solving to the
evaluation of general fixpoint equation systems [HausmannSchroeder21].

Later-appearence-record (LAR) constructions have been used to reduce games
with richer winning objectives to parity games; this subsumes in particular
the LAR-reduction for Emerson-Lei games (arrow (3)), which have recently
garnered attention due to their succinctness and favorable closure properties.

In this context, the contribution of the current work is two-fold. First, we
show how for parity games with cycle-free sub-structures, Walukiewicz’
construction can be adapted to use multi-step attraction along cycle-free
parts (we call such parts _DAGs in games_) in place of one-step attraction. In
consequence, the domain of the resulting fixpoint expression can be restricted
to the parts of the game that are not cycle-free, thereby accelerating
convergence in the solution of the fixpoint expression. If multi-step
attraction can be evaluated without visiting most cycle-free nodes (which is
the case, e.g., when cycle-free parts encode predicates that can be
efficiently evaluated), this trick has been shown to significantly speed up
game solution. Applications can be found in both model checking [HausmannS19]
and satisfiability checking [HausmannS19a] for generalized $\mu$-calculi in
which satisfaction and joint satisfiability, respectively, of the modalities
can be harder to verify than in the standard $\mu$-calculus.

In addition to that, we propose a later-appearance-record construction for the
transformation of Emerson-Lei games to equivalent parity games (corresponding
to arrow (3) in the above diagram) and show that the reduction preserves
cycle-free sub-structures, thereby enabling usage of the proposed acceleration
method also for games with full Emerson-Lei objectives.

##  2 Games and Fixpoint Expressions

We start by introducing notions of games and fixpoint expressions pertaining
to the acceleration method proposed in Sections 3 and 4 below.

_Games._ An _arena_ is a graph $A=(V_{\exists},V_{\forall},E)$, consisting of
a set $V=V_{\exists}\cup V_{\forall}$ of _nodes_ and a set $E\subseteq V\times
V$ of _moves_ ; furthermore, the set of nodes is partitioned into the sets
$V_{\exists}$ and $V_{\forall}$ of nodes _owned_ by player $\exists$ and by
player $\forall$, respectively. We write $E(v)=\\{w\in V\mid(v,w)\in E\\}$ for
the set of nodes reachable from node $v\in V$ by a single move. We assume
without loss of generality that every node has at least one outgoing edge,
that is, that $E(v)\neq\emptyset$ for all $v\in V$. A _play_
$\pi=v_{0}v_{1}\ldots$ on $A$ is a (finite or infinite) sequence of nodes such
that $v_{i+1}\in E(v_{i})$ for all $i\geq 0$. By abuse of notation we denote
by $A^{\omega}$ the set of infinite plays on $A$ and by $A^{+}$ the set of
finite (nonempty) plays on $A$. A _strategy_ for player
$i\in\\{\exists,\forall\\}$ is a function $\sigma:V^{*}\cdot V_{i}\to V$ that
assigns a node $\sigma(\pi v)\in V$ to every finite play $\pi v$ that ends in
a node $v\in V_{i}$. A strategy $\sigma$ for player $i$ is said to be
_positional_ if the prescribed moves depend only on the last nodes in plays;
formally, this is the case if we have $\sigma(\pi v)=\sigma(\pi^{\prime}v)$
for all $\pi,\pi^{\prime}\in V^{*}$ and $v\in V_{i}$. A play
$\pi=v_{0}v_{1}\ldots$ then is _compatible_ with a strategy $\sigma$ for
player $i\in\\{\exists,\forall\\}$ if for all $j\geq 0$ such that $v_{j}\in
V_{i}$, we have $v_{j+1}=\sigma(v_{0}v_{1}\ldots v_{j})$. A strategy for
player $i\in\\{\exists,\forall\\}$ _with memory $M$_ is a tuple
$\sigma=(M,m_{0},\mathsf{update}:M\times E\to M,\mathsf{move}:V_{i}\times M\to
V)$, where $M$ is some set of _memory values_ , $m_{0}\in M$ is the initial
memory value, the _update function_ $\mathsf{update}$ assigns the outcome
$\mathsf{update}(m,e)\in M$ of updating the memory value $m\in M$ according to
the effects of taking the move $e\in E$, and the moving function
$\mathsf{move}$ prescribes a single move $(v,\mathsf{move}(v,m))\in E$ to
every game node $v\in V_{i}$ that is owned by player $i$, depending on the
memory value $m$. We extend $\mathsf{update}$ to finite plays $\pi$ by putting
$\mathsf{update}(m,\pi)=m$ in the base case that $\pi$ consists of a single
node, and by putting
$\mathsf{update}(m,\pi)=\mathsf{update}(\mathsf{update}(m,\tau),(v,w))$ if
$\pi$ is of the shape $\tau vw$, that is, contains at least two nodes. Then we
obtain a strategy (without explicit memory) $\tau_{\sigma}:V^{*}\cdot V_{i}\to
V$ from a strategy $\sigma=(M,m_{0},\mathsf{update}:M\times E\to
M,\mathsf{move}:V_{i}\times M\to V)$ with memory by putting, for all
$v_{0}v_{1}\ldots v_{i}\in V^{*}\cdot V_{i}$,

$\displaystyle\tau_{\sigma}(v_{0}v_{1}\ldots
v_{i})=\mathsf{move}(v_{i},\mathsf{update}(m_{0},v_{0}v_{1}\ldots v_{i})).$

In this work we consider two types of objectives: _parity objectives_ and,
more generally, _Emerson-Lei objectives_.

Emerson-Lei objectives [HunterD05] are specified relative to a coloring
function $\gamma_{C}:V\to 2^{C}$ (for some set $C$ of colors) that assigns a
set $\gamma_{C}(v)\subseteq C$ of colors to each node $v\in V$. A play
$\pi=v_{0}v_{1}\ldots$ then induces a sequence
$\gamma_{C}(\pi)=\gamma_{C}(v_{0})\gamma_{C}(v_{1})\ldots$ of sets of colors.
Emerson-Lei objectives are given as Boolean formulas
$\varphi_{C}\in\mathbb{B}(\\{\mathsf{Inf}(c)\mid c\in C\\})$ over atoms of the
shape $\mathsf{Inf}(c)$; throughout, we write $\mathsf{Fin}(c)$ for
$\neg(\mathsf{Inf}(c))$. Such formulas are interpreted over infinite sequences
$\gamma_{0}\gamma_{1}\ldots$ of sets of colors. We put
$\gamma_{0}\gamma_{1}\ldots\models\mathsf{Inf}~{}c$ if and only if there are
infinitely many positions $i$ such that $c\in\gamma_{i}$; satisfaction of
Boolean operators is defined in the usual way. Then a play $\pi$ on $A$
_satisfies_ the objective $\varphi_{C}$ if and only if
$\gamma_{C}(\pi)\models\varphi_{C}$ and we define the Emerson-Lei objective
induced by $\gamma_{C}$ and $\varphi_{C}$ by putting

$\displaystyle\alpha_{\gamma_{C},\varphi_{C}}=\\{\pi\in
V^{\omega}\mid\gamma_{C}(\pi)\models\varphi_{C}\\}.$

An _Emerson-Lei game_ is a tuple $G=(A,\alpha)$, where
$A=(V_{\exists},V_{\forall},E)$ is an arena and $\alpha$ is an Emerson-Lei
objective. A strategy $\sigma$ for player $\exists$ is _winning_ at some node
$v\in V$ if all infinite plays that start at $v$ and are compatible with
$\sigma$ satisfy the objective $\alpha$. A strategy $\tau$ for player
$\forall$ is defined winning dually. The _winning region_ $\mathsf{Win}_{G}$
of player $\exists$ in the game $G$ is the set of nodes for which there is a
winning strategy for player $\exists$.

As a special case, we define _parity games_ to be Emerson-Lei games
$(A,\alpha)$ where $\alpha$ is the Emerson-Lei objective induced by a coloring
function $\gamma:V\to 2^{\\{p_{1},\ldots,p_{k}\\}}$ that assigns exactly one
of the colors $\\{p_{1},\ldots,p_{k}\\}$ to each game node, and the formula

$\displaystyle\textstyle\bigvee_{i\text{
even}}\mathsf{Inf}(p_{i})\wedge\textstyle\bigwedge_{j>i}\mathsf{Fin}(p_{j}),$

expressing that for some even $i$, color $p_{i}$ is visited infinitely often
and no color $p_{j}$ such that $j$ is larger than $i$ is visited infinitely
often. We denote such games by
$(V_{\exists},V_{\forall},E,\Omega:V\to\mathbb{N})$, where $\Omega$ is a
_priority function_ , assigning to each node $v\in V$ the number $\Omega(v)=i$
such that $\gamma(v)=\\{p_{i}\\}$.

Emerson-Lei games are known to be _determined_ , that is, every node in such
games is won by exactly one of the two players. _Solving_ a game then amounts
to computing the winner for each game node. While the solution of Emerson-Lei
games is known to be a PSpace-complete problem [HunterD05], the precise
complexity of solving parity games remains an open question; it is known
however, that solving parity games is in NP$\cap$Co-NP as well as in QP (that
is, can be done deterministically in quasipolynomial time). Winning strategies
in Emerson-Lei games may require exponential memory (specifically, $k!$, where
$k$ is the number of colors), but parity games have positional strategies
[DziembowskiJW97].

_Fixpoint Expressions._ Let $U$ be a set, $k$ a natural number (we assume
without loss of generality that $k$ is even) and let
$f:\mathcal{P}(U)^{k}\to\mathcal{P}(U)$ be a monotone function (such that
$f(W_{1},\ldots,W_{k})\subseteq f(W^{\prime}_{1},\ldots,W^{\prime}_{k})$
whenever $W_{i}\subseteq W^{\prime}_{i}$ for all $1\leq i\leq k$). This data
induces a fixpoint expression

$\displaystyle e=\nu X_{k}.\,\mu X_{k-1}.\,\ldots\,.\,\mu
X_{1}.\,f(X_{1},\ldots,X_{k}).$

The semantics of such fixpoint expressions is defined as usual, following the
Knaster-Tarski fixpoint theorem. Formally, we put

$\displaystyle\mathsf{LFP}\,g$ $\displaystyle=\bigcap\\{W\subseteq U\mid
g(W)\subseteq W\\}$ $\displaystyle\mathsf{GFP}\,g$
$\displaystyle=\bigcup\\{W\subseteq U\mid W\subseteq G(W)\\}$

for monotone functions $g:\mathcal{P}(U)\to\mathcal{P}(U)$ and define

$\displaystyle\llbracket e\rrbracket_{i}(X_{i+1},\ldots
X_{k})=\begin{cases}\mathsf{LFP}(\lambda X_{i}.\llbracket
e\rrbracket_{i-1}(X_{i},X_{i+1},\ldots X_{k}))&\text{ if $i$ is odd}\\\
\mathsf{GFP}(\lambda X_{i}.\llbracket e\rrbracket_{i-1}(X_{i},X_{i+1},\ldots
X_{k}))&\text{ if $i$ is even}\end{cases}$

for $1\leq i\leq k$ and $X_{i+1},\ldots,X_{k}\subseteq V$, where $\llbracket
e\rrbracket_{0}(X_{1},\ldots X_{k})=f(X_{1},\ldots X_{k})$. Then we say that
$v\in V$ is _contained_ in $e$ (denoted $v\in e$) if and only if
$v\in\llbracket e\rrbracket_{k}$; by abuse of notation, we denote $\llbracket
e\rrbracket_{k}$ just by $e$.

_Relation between Games and Fixpoint Expressions._ The winning region in
parity games can be specified by a fixpoint expression over the underlying
game arena. To see how this works, let $G=(V_{\exists},V_{\forall},E,\Omega)$
be a parity game and define the following notation. Let
$\Omega^{-1}(i)=\\{v\in V\mid\Omega(v)=i\\}$ denote the set of nodes that have
priority $i$. The _controllable predecessor function_
$\mathsf{Cpre}:\mathcal{P}(V)\to\mathcal{P}(V)$ that computes one-step
attraction for player $\exists$ in $G$ is defined, for $X\subseteq V$, by
putting

$\displaystyle\mathsf{Cpre}(X)=\\{v\in V_{\exists}\mid E(v)\cap
X\neq\emptyset\\}\cup\\{v\in V_{\forall}\mid E(v)\subset X\\}.$

Thus $\mathsf{Cpre}(X)$ contains all nodes $v\in V_{\exists}$ for which some
outgoing move leads to $X$, as well as all nodes $v\in V_{\forall}$ for which
all outgoing moves lead to $X$; intuitively, this is the set of nodes from
which player $\exists$ can force that $X$ is reached in one step of the game.
The characterization is given by the fixpoint expression

$\mathsf{parity}_{G}=\nu X_{k}.\,\mu X_{k-1}.\,\ldots\,.\,\mu
X_{1}.\,\bigvee_{1\leq i\leq k}\Omega^{-1}(i)\wedge\mathsf{Cpre}(X_{i}).$ (1)

The characterization result (e.g. [BruseFL14]) then is stated as follows.

######  Lemma 1.

We have $\mathsf{Win}_{G}=\mathsf{parity}_{G}$.

Similar fixpoint characterizations of winning regions have been given for
games with more involved objectives, including GR[1] conditions [BloemJPPS12],
Rabin and Streett objectives [PitermanP06], and most recently, also for full
Emerson-Lei objectives [HausmannEA23]. While the characterizations of winning
according to these more general objectives involve fixpoint expressions of a
more general format (given by hierarchical systems of fixpoint equations) than
the one we have defined above, the fixpoint for the winning region in parity
games will be sufficient for the purposes of this work. All mentioned fixpoint
characterizations of winning regions allow for (symbolic) solution of games by
computing nested fixpoints, using for instance standard fixpoint iteration
[Seidl96], or using more recent techniques that employ universal trees to
obtain quasipolynomial algorithms to compute nested fixpoints
[HausmannSchroeder21, ArnoldEA21].

For the converse direction, that is, going from fixpoints to games, it has
recently been shown (in a more general framework than the one used in this
work, see [BaldanKMP19] for details) that the semantics of fixpoint
expressions can be equivalently given in terms of parity games. The _fixpoint
game_ that is associated with a fixpoint expression

$\displaystyle e=\nu X_{k}.\,\mu X_{k-1}.\,\ldots\,.\,\mu
X_{1}.\,f(X_{1},\ldots,X_{k})$

over $U$ is the parity game
$G_{e}=(V_{\exists},V_{\forall},E,\Omega:V\to\\{1,\ldots,k\\})$ played over
the sets $V_{\exists}=U$ and $V_{\forall}=\mathcal{P}(U)^{k}\cup(U\times[k])$
of nodes; moves and priorities are given by the following table, abbreviating
$(U_{1},\ldots,U_{k})$ by $\overline{U}$.

Node | owner | priority | allowed moves
---|---|---|---
$u\in U$ | $\exists$ | $0$ | $\\{\overline{U}\in\mathcal{P}(U)^{k}\mid u\in f(\overline{U})\\}$
$\overline{U}\in\mathcal{P}(U)^{k}$ | $\forall$ | $0$ | $\\{(u,i)\in U\times[k]\mid u\in V_{i}\\}$
$(u,i)\in U\times[k]$ | $\forall$ | $i$ | $\\{u\\}$

When the game reaches a node $u\in U$, player $\exists$ thus has to provide a
tuple $\overline{U}=(U_{1},\ldots,U_{k})\in\mathcal{P}(U)^{k}$ such that $u\in
f(\overline{U})$. Player $\forall$ in turn can challenge the provided tuple by
moving to any $(u^{\prime},i)$ such that $u^{\prime}\in U_{i}$, and then
continuing the game at the node $u^{\prime}\in U$. Crucially, such a sequence
triggers the priority $i$ which is an even number if $X_{i}$ belongs to a
greatest fixpoint in $e$, and odd otherwise. We observe that the number of
nodes in $G_{e}$ is exponential in $|U|$; however, player $\exists$ owns only
$|U|$ of these nodes.

######  Lemma 2 ([BaldanKMP19]).

We have $e=\mathsf{Win}_{G_{e}}$.

While fixpoint games enable reasoning about fixpoint expressions by reasoning
about parity games, the exponential size of fixpoint games makes it unfeasible
to evaluate fixpoint expressions by solving the associated fixpoint games.

##  3 Game Arenas with DAG Sub-structures

In this section we introduce notions related to cycle-free sub-structures in
(parity) games that will be central to the upcoming acceleration result.

######  Definition 3.

Let $G=(V_{\forall},V_{\exists},E)$ be a game arena. A set $W\subseteq V$ of
nodes is a _DAG_ (directed acyclic graph) if it does not contain an $E$-cycle;
then there is no play of $G$ that eventually stays within $W$ forever. A DAG
is not necessarily connected, that is, it may consist of several subgames of
$G$. Given a DAG $W\subseteq V$, we write $V^{\prime}=V\setminus W$ and refer
to the set $V^{\prime}$ as _real_ nodes (with respect to $W$). A DAG is
_positional_ if for each existential player node $w\in W\cap V_{\exists}$ in
it, there is exactly one real node $v\in V^{\prime}$ from which $w$ is
reachable without visiting any other real node.

We will be interested in parity games over game arenas with DAG structures,
and in the computation of attraction (that is, alternating reachability)
within such DAGs. To this end, we introduce the following notation of DAG
attraction in parity games.

######  Definition 4.

Let $G=(V_{\forall},V_{\exists},E,\Omega)$ be a parity game with priorities
$\\{1,\ldots,k\\}$. Given a DAG $W$ and $k$ sets
$\overline{V}=(V_{1},\ldots,V_{k})$ of real nodes and a real node $v\in
V^{\prime}$, we say that player $\exists$ can _attract_ to $\overline{V}$ from
$v$ within $W$ if there is a positional strategy $\sigma$ for player $\exists$
such that for all plays $\pi$ that start at $v$ and adhere to $\sigma$, the
first node $v^{\prime}$ in $\pi$ such that $v^{\prime}\neq v$ and
$v^{\prime}\in V^{\prime}$ is contained in $V_{p}$, where $p$ is the maximal
priority that is visited by the part of $\pi$ that leads from $v$ to
$v^{\prime}$.

Given a DAG $W$, we define the _DAG attractor function_
$\mathsf{DAttr}_{W}:\mathcal{P}(V^{\prime})^{k}\to\mathcal{P}(V^{\prime})$ by

$\mathsf{DAttr}_{W}(\overline{V})=\\{v\in V\mid\text{player $\exists$ can
attract to $\overline{V}$ from $v$ within $W$}\\}$ (2)

for $\overline{V}=(V_{1},\ldots,V_{k})\in\mathcal{P}(V^{\prime})^{k}$. We
assume a bound $t_{\mathsf{Attr}_{W}}$ on the runtime of computing, for any
input $\overline{V}\in\mathcal{P}(V^{\prime})^{k}$, the dag attractor of
$\overline{V}$ through $W$.

We always have $t_{\mathsf{Attr}_{W}}\leq|E|$, using a least fixpoint
computation to check for alternating reachability, thereby possibly exploring
all DAG edges of the game. The method that we propose in the next section can
play out its strength best in parity games that have large DAGs that can be
efficiently evaluated (more formally, this typically means that we have both
$|V^{\prime}|<\log|V|$ and $t_{\mathsf{Attr}_{W}}<\log|V|$).

##  4 Large-step Solving for Parity Games

In this section we show that a parity game with DAG sub-structure $W$ can be
solved by computing a fixpoint of the DAG attractor function, using
$V^{\prime}=V\setminus W$ as domain of the fixpoint computation, rather than
$V$.

So let $G=(V_{\exists},V_{\forall},E,\Omega)$ be a parity game with
(positional) DAG $W$. Recall (from Lemma 1) that the winning region in $G$ is
given by

$\displaystyle\mathsf{Win}_{G}=\nu X_{k}.\,\mu X_{k-1}.\,\ldots\,.\,\mu
X_{1}.\,\bigvee_{1\leq i\leq k}\Omega^{-1}(i)\wedge\mathsf{Cpre}(X_{i}),$

where $\mathsf{Cpre}$ operates on subsets $X_{i}$ of $V$. We show that

$\mathsf{Win}_{G}\cap V^{\prime}=\nu Y_{k}.\,\mu Y_{k-1}.\,\ldots\,.\,\mu
Y_{1}.\,\mathsf{DAttr}_{W}(Y_{1},\ldots,Y_{k}),$ (3)

pointing out that $\mathsf{DAttr}_{W}(Y_{1},\ldots,Y_{k})$ is a function over
subsets $Y_{1},\ldots Y_{k}$ of $V^{\prime}$. Therefore Equation (3) shows how
attention can be reduced to non-DAG nodes (from $V^{\prime}$) when solving
$G$; however, the price for this is that the function $\mathsf{DAttr}_{W}$ of
which the fixpoint is computed is complex since it computes multi-step
attraction within a DAG in place of one-step attraction as encoded by
$\mathsf{Cpre}$.

We make this intuition precise and prove the main result (that is, Equation
(3)) as follows.

######  Lemma 5.

Let $G$ be a parity game with priorities $1$ to $k$ and set $V$ of nodes, let
$W$ be a positional DAG in $G$, and let $V^{\prime}=V\setminus W$ and
$m:=|V^{\prime}|$. Then $\mathsf{Win}_{G}\cap V^{\prime}$ can be computed with
$\mathcal{O}(m^{\log k})$ computations of a DAG attractor; if $k<\log m$, then
$\mathsf{Win}_{G}\cap V^{\prime}$ can be computed with a number of DAG
attractor computations that is polynomial in $m$.

###### Proof.

We show that the winning regions in $G$ can be computed by a fixpoint
expression (with alternation-depth $k$) of the DAG attractor function given in
Equation (2). Without loss of generality, assume that $k$ is an even number.

We define the fixpoint expression

$\displaystyle d$ $\displaystyle=\nu X_{k}.\,\mu X_{k-1}.\,\ldots\,.\,\mu
X_{1}.\,\mathsf{DAttr}_{W}(X_{1},\ldots,X_{k}),$

noting that the fixpoint variables $X_{i}$ in $d$ range over subsets of
$V^{\prime}$ rather than over subsets of $V$. It has been shown in
[HausmannSchroeder21] how universal trees can be used to compute the nested
fixpoint $d$ with $\mathcal{O}(m^{\log k})$ (that is, quasipolynomially many)
iterations of the function $\mathsf{DAttr}_{W}$. It follows from the results
of the same paper that if $k<\log m$, then $d$ can be computed with a
polynomial (in $m$) number of computations of a dag attractor. It remains to
show that $d$ is the winning region (restricted to $V^{\prime}$) of player
$\exists$ in $G$.

  * $\Rightarrow$

Let $s$ be a strategy with which player $\exists$ wins from all nodes in their
winning region in $G_{d}$. We define a positional strategy $t$ for player
$\exists$ in $G$. The definition proceeds in steps that lead from a real node
to the next real nodes. Given a real node $v\in V^{\prime}$ that is contained
in the winning region of player $\exists$ in $G_{d}$, we have
$s(v)=\overline{V}\in\mathcal{P}(V^{\prime})^{k}$ such that player $\exists$
can attract to $\overline{V}$ from $v$ within $W$. For the dag part of $G$
that starts at $v$, define the strategy $t$ to simply use the positional
strategy that attracts to $\overline{V}$ from $v$ within $W$.

To see that $t$ is a winning strategy, let $\pi$ be a play of $G$ that is
compatible with $t$. Then $\pi$ induces a play $\tau$ of $G_{d}$ that is
compatible with $s$: For any two positions $i$ and $i^{\prime}$ such that
$i<i^{\prime}$, both $\pi(i)$ and $\pi(i^{\prime})$ are real nodes and there
is no $i<j<i^{\prime}$ such that $\pi(j)$ is a real node, let $p$ be the
maximal priority that is visited by the partial play from $\pi(i)$ to
$\pi(i^{\prime})$. By construction we have
$s(\pi(i))=(V_{1},\ldots,V_{p},\ldots,V_{k})$ where $V_{p}$ contains
$\pi(i^{\prime})$. Thus the partial play of $G$ that leads from $\pi(i)$ to
$\pi(i^{\prime})$ induces the partial play
$\tau_{i}=\pi(i)s(\pi(i))(\pi(i^{\prime}),p)\pi(i^{\prime})$ of $G_{d}$. We
define $\tau$ to be the concatenation of all partial plays $\tau_{i}$. By
construction, $\tau$ is compatible with $s$; as $s$ is a winning strategy,
player $\exists$ wins $\tau$. Furthermore, the maximal priorities that are
visited infinitely often in $\tau$ and $\pi$ agree. Thus player $\exists$ wins
$\pi$, as required.

  * $\Leftarrow$

Let $t$ be a positional strategy for player $\exists$ in $G$ with which they
win from all nodes in their winning region. We define a positional strategy
$s$ for player $\exists$ in $G_{d}$ as follows. For each node $v\in
V^{\prime}$ that is contained in the winning region of player $\exists$ in
$G$, $t$ yields a positional strategy that attracts from $v$ to some
$\overline{V}=(V_{0},\ldots,V_{k})\in\mathcal{P}(V^{\prime})^{k}$ within $W$:
For all $v^{\prime}$ and all $0\leq p\leq k$ such that there is a partial play
of $G$ that is compatible with $t$, starts at $v$, ends at $v^{\prime}$, and
in between visits only nodes from $W$, and in which the maximal priority that
is visited is $p$, add $v^{\prime}$ to $V_{p}$. Put $s(v)=\overline{V}$. As
$v$ attracts from $v$ to $\overline{V}$ within $W$ by construction, $s$ is a
valid strategy.

To see that $s$ is a winning strategy, let $\tau$ be a play of $G_{d}$ that
starts at a real node from the winning region of player $\exists$ in $G$ and
that is compatible with $s$. For each partial sub-play
$v_{i}s(v_{i})(v_{i+1},p_{i})v_{i+1}$ of $\tau$, we define $\pi_{i}$ to be
some partial play of $G$ that is compatible with $t$, starts at $v_{i}$, ends
at $v_{i+1}$, and in between visits only nodes from $W$, and in which the
maximal priority that is visited is $p_{i}$. Such a play exists by
construction of $s$. Let $\pi$ denote the concatenation of all $\pi_{i}$.
Again, the maximal priorities that are visited infinitely often in $\tau$ and
$\pi$ agree. As $t$ is a winning strategy, player $\exists$ wins both $\tau$
and $\pi$.

∎

In case that $m<\log n$ and $t_{\mathsf{Attr}_{W}}\in\mathcal{O}(\log n)$
(that is, DAG attractability can be decided without exploring most of the DAG
nodes), this trick leads to exponentially faster game solving.

##  5 Large-step Solving for Emerson-Lei Games

In this section, we show how games with an Emerson-Lei objective can be
transformed to equivalent parity games, using an economic variant of the
later-appearance-record (LAR) construction; we also show that this
transformation preserves dag sub-structures. Thereby we enable usage of the
acceleration method for parity games from the previous section also for
Emerson-Lei games.

The LAR reduction annotates game nodes with permutations that act as a memory
and record the order in which colors have been recently visited; this allows
to identify the set of colors that is visited infinitely often. A parity
condition is used to check whether this set satisfies the Emerson-Lei
objective. A slight difference to previous LAR constructions for Emerson-Lei
automata and games [RenkinDP20, HunterD05] is that our reduction moves at most
one color within the LAR in each game step, thereby allowing to bound the
branching of memory updates along DAG parts of games.

Before we present the formal reduction, we first fix a set $C$ of colors and
introduce notation for permutations over $C$. We let $\Pi(C)$ denote the set
of permutations over $C$, and for a permutation $\pi\in\Pi(C)$ and a position
$1\leq i\leq|C|$, we let $\pi(i)\in C$ denote the element at the $i$-th
position of $\pi$. Let $\pi_{0}$ be some fixed element of $\Pi(C)$. For
$D\subseteq C$ and $\pi\in\Pi(C)$, we let $\pi@D$ denote the permutation that
is obtained from $\pi$ by moving _the_ element of $D$ that occurs at the
right-most position in $\pi$ to the front of $\pi$; for instance, for
$C=\\{a,b,c,d\\}$ and $\pi=(a,d,c,b)\in\Pi(C)$, we have
$\pi@\\{a,d\\}=\pi@\\{d\\}=(d,a,c,b)$ and $(d,a,c,b)@\\{a,d\\}=\pi$.
Crucially, restricting the reordering to single colors, rather than sets of
colors, ensures that for each $\pi\in\Pi(C)$, there are only $|C|$ many
$\pi^{\prime}$ such that $\pi@D=\pi^{\prime}$ for some $D\subseteq C$.
Therefore, the branching in the reduced game is bounded in such a way that a
DAG with $o$ exit points and in which every path from the entry point to some
exit point visits at most one node with non-empty set of colors, is reduced to
a DAG that again has $o$ exit points. Given a permutation $\pi\in\Pi(C)$ and
an index $1\leq i\leq|C|$, we furthermore let $\pi[i]$ denote the set of
colors that occur in one of the first $i$ positions in $\pi$.

######  Definition 6.

Let $G=(V_{\exists},V_{\forall},E,\gamma_{C},\varphi_{C})$ be an Emerson-Lei
game with set $C$ of colors. We define the parity game

$\displaystyle
P(G)=(V_{\exists}\times\Pi(C),V_{\forall}\times\Pi(C),E^{\prime},\Omega)$

by putting $E^{\prime}(v,\pi)=\\{(w,\pi@\gamma_{C}(v))\mid(v,w)\in E\\}$ for
$(v,\pi)\in V\times\Pi(C)$, and

$\displaystyle\Omega(v,\pi)=\begin{cases}2p&\pi[p]\models\varphi_{C}\\\
2p+1&\pi[p]\not\models\varphi_{C}\end{cases}$

for $(v,\pi)\in V\times\Pi(C)$. Here, $p$ denotes the right-most position in
$\pi$ that contains some color from $\gamma_{C}(v)$.

######  Lemma 7.

For all $v\in V$, we have $v\in\mathsf{Win}_{G}$ if and only if
$(v,\pi_{0})\in\mathsf{Win}_{P(G)}$.

###### Proof.

For a finite play $\tau=(v_{0},\pi_{0})(v_{1},\pi_{1})\ldots(v_{n},\pi_{n})$
of $P(G)$, we let $p(\tau)$ denote the right-most position in $\pi_{0}$ such
that $\pi_{0}(p(\tau))\in\gamma_{C}(v_{0}v_{1}\ldots v_{n})$. By slight abuse
of notation, we let $\Omega(\tau)$ denote the maximal $\Omega$-priority that
is visited in $\tau$, having $\Omega(\tau)=2(p(\tau))$ if
$\pi_{0}[p(\tau)]\models\varphi_{C}$ and $\Omega(\tau)=2(p(\tau))+1$ if
$\pi_{0}[p(\tau)]\not\models\varphi_{C}$.

  * $\Rightarrow$

Let $\sigma=(\Pi(C),\mathsf{update}_{\sigma},\mathsf{move}_{\sigma})$ be a
strategy with memory $\Pi(C)$ for player $\exists$ in $G$ with which they win
every node from their winning region. It has been shown in a previous LAR
reduction for Emerson-Lei games [HunterD05] that winning strategies with this
amount of memory always exist. We define a strategy
$\rho=(\Pi(C),\mathsf{update}_{\rho},\mathsf{move}_{\rho})$ with memory
$\Pi(C)$ for player $\exists$ in $P(G)$ by putting
$\mathsf{update}_{\rho}(\pi,((v,\pi^{\prime}),(w,\pi^{\prime\prime})))=\mathsf{update}_{\sigma}(\pi,(v,w))$
and

$\mathsf{move}_{\rho}((v,\pi^{\prime}),\pi)=(\mathsf{move}_{\rho}(v,\pi),\pi@\gamma_{C}(v)).$

Thus $\rho$ updates the memory and picks moves just as $\sigma$ does, but also
updates the permutation component in $P(G)$ according to the taken moves;
hence $\rho$ is a valid strategy.

We show that $\rho$ wins a node $(v,\pi)$ in $P(G)$ whenever $v$ is in the
winning region of player $\exists$ in $G$. To this end, let
$\tau=(v_{0},\pi_{0})(v_{1},\pi_{1})\ldots$ be a play of $P(G)$ that starts at
$(v_{0},\pi_{0})=(v,\pi)$ and is compatible with $\rho$. By construction,
$\theta=v_{0}v_{1}\ldots$ is a play that is compatible with $\sigma$. Since
$\sigma$ is a winning strategy for player $\exists$, we have
$\gamma_{C}(\theta)\models\varphi_{C}$. There is a number $i$ such that all
colors that appear in $\theta$ from position $i$ on occur infinitely often.
Let $p$ be the number of colors that appear infinitely often in $\theta$. It
follows by definition of $\pi@D$ for $D\subseteq C$ (which moves the single
right-most element of $\pi$ that is contained in $D$ to the very front of
$\pi$), that there is a position $j\geq i$ such that the left-most $p$
elements of $\pi_{j}$ are exactly the colors occurring infinitely often in
$\pi$ (and all colors to the right of $\pi_{j}(p)$ are never visited from
position $j$ on). It follows that from position $j$ on, $\tau$ never visits a
priority larger than $2p$. To see that $\tau$ infinitely often visits priority
$2p$ we note that $\pi_{j^{\prime}}[p]\models\varphi_{C}$ for any
$j^{\prime}>j$, so it suffices to show that $p$ infinitely often is the
rightmost position in the permutation component of $\tau$ that is visited.
This is the case since, from position $j$ on, the $p$-th element in the
permutation component of $\tau$ cycles fairly through all colors that are
visited infinitely often by $\theta$.

  * $\Leftarrow$

Let $\rho$ be a positional strategy for player $\exists$ in $P(G)$ with which
they win every node from their winning region. We define a strategy
$\sigma=(\Pi(C),\mathsf{update}_{\sigma},\mathsf{move}_{\sigma})$ with memory
$\Pi(C)$ for player $\exists$ in $G$ by putting
$\mathsf{update}_{\sigma}(\pi,(v,w))=\pi@\gamma_{C}(v)$ and
$\mathsf{move}_{\sigma}(v,\pi)=w$ where $w$ is such that
$\rho(v,\pi)=(w,\pi@\gamma_{C}(v))$. Thus $\sigma$ updates the memory and
picks moves just as plays that follow $\rho$ do.

We show that $\sigma$ wins a node $v$ in $G$ whenever $(v,\pi)$ is in the
winning region of player $\exists$ in $P(G)$. To this end, let
$\theta=v_{0}v_{1}\ldots$ be a play of $G$ that starts at $v_{0}=v$ and is
compatible with $\sigma$. By construction, $\theta$ induces a play
$\tau=(v_{0},\pi_{0})(v_{1},\pi_{1})\ldots$ with $(v_{0},\pi_{0})=(v,\pi)$ and
$\pi_{i+1}=\pi_{i}@\gamma_{C}(v_{i})$ for $i\geq 0$ that is compatible with
$\rho$. Since $\rho$ is a winning strategy for player $\exists$, the maximal
priority in it is even (say $2p$). Again, $p$ is the position such that the
left-most $p$ elements in the permutation component of $\rho$ from some point
on contain exactly the colors that are visited infinitely often by $\theta$.
It follows that $\gamma_{C}(\theta)\models\varphi_{C}$.

∎

The LAR reduction from Definition 6 preserves DAG sub-structures:

######  Lemma 8.

Let $G$ be an Emerson-Lei games with set $C$ of colors. If $W$ is a positional
DAG in $G$, then $W\times\Pi(C)$ is a positional DAG in $P(G)$.

###### Proof.

The claim follows immediately since the LAR reduction just annotates game
nodes with additional memory, meaning that each game node $v$ in $G$ is
replaced with copies $(v,\pi)$ in $P(G)$ so that all cycles in $P(G)$ have
corresponding cycles in $G$. ∎

##  6 Conclusion

We have presented a method for solving parity games with DAG sub-structures by
computing nested fixpoints over the non-DAG nodes only, thereby intuitively
accelerating fixpoint computation by summarizing cycle-free parts during the
solution of parity games. This can significantly reduce the domain of the game
solving process, and in cases where DAG sub-structures in addition can be
evaluated without exploring all nodes in them, it improves the time complexity
of parity game solving. Furthermore, we have proposed a later-appearence-
record construction with linear branching on the memory values that transforms
Emerson-Lei games to parity games, and have shown that this transformation
preserves DAG sub-structures, enabling usage of the proposed method also for
the solution of games with general Emerson-Lei objectives.

## References

  * [1] André Arnold, Damian Niwinski, and Pawel Parys.  A quasi-polynomial black-box algorithm for fixed point evaluation.  In Computer Science Logic, CSL 2021, volume 183 of LIPIcs, pages 9:1–9:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPICS.CSL.2021.9.
  * [2] Paolo Baldan, Barbara König, Christina Mika-Michalski, and Tommaso Padoan.  Fixpoint games on continuous lattices.  Proc. ACM Program. Lang., 3(POPL):26:1–26:29, 2019.  doi:10.1145/3290339.
  * [3] Roderick Bloem, Barbara Jobstmann, Nir Piterman, Amir Pnueli, and Yaniv Sa’ar.  Synthesis of reactive(1) designs.  J. Comput. Syst. Sci., 78(3):911–938, 2012.  doi:10.1016/j.jcss.2011.08.007.
  * [4] Florian Bruse, Michael Falk, and Martin Lange.  The fixpoint-iteration algorithm for parity games.  In Games, Automata, Logics and Formal Verification, GandALF 2014, volume 161 of EPTCS, pages 116–130, 2014.  doi:10.4204/EPTCS.161.12.
  * [5] Stefan Dziembowski, Marcin Jurdzinski, and Igor Walukiewicz.  How much memory is needed to win infinite games?  In Logic in Computer Science, pages 99–110. IEEE Computer Society, 1997.  doi:10.1109/LICS.1997.614939.
  * [6] Daniel Hausmann, Mathieu Lehaut, and Nir Piterman.  Symbolic solution of Emerson-Lei games for reactive synthesis.  In Foundations of Software Science and Computation Structures, FoSSaCS 2024, volume 14574 of LNCS, pages 55–78. Springer, 2024.  doi:10.1007/978-3-031-57228-9\\_4.
  * [7] Daniel Hausmann and Lutz Schröder.  Game-based local model checking for the coalgebraic $\mu$-calculus.  In Concurrency Theory, CONCUR 2019, volume 140 of LIPIcs, pages 35:1–35:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPICS.CONCUR.2019.35.
  * [8] Daniel Hausmann and Lutz Schröder.  Optimal satisfiability checking for arithmetic $\mu$-calculi.  In Foundations of Software Science and Computation Structures, FOSSACS 2019, volume 11425 of LNCS, pages 277–294. Springer, 2019.  doi:10.1007/978-3-030-17127-8\\_16.
  * [9] Daniel Hausmann and Lutz Schröder.  Quasipolynomial computation of nested fixpoints.  In Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2021, volume 12651 of LNCS, pages 38–56. Springer, 2021\.  doi:10.1007/978-3-030-72016-2\\_3.
  * [10] Paul Hunter and Anuj Dawar.  Complexity bounds for regular games.  In Mathematical Foundations of Computer Science, volume 3618 of LNCS, pages 495–506. Springer, 2005.  doi:10.1007/11549345\\_43.
  * [11] Nir Piterman and Amir Pnueli.  Faster solutions of Rabin and Streett games.  In Logic in Computer Science, LICS 2006, pages 275–284. IEEE Computer Society, 2006.  doi:10.1109/LICS.2006.23.
  * [12] Florian Renkin, Alexandre Duret-Lutz, and Adrien Pommellet.  Practical ”paritizing” of Emerson-Lei automata.  In Automated Technology for Verification and Analysis, ATVA 2020, volume 12302 of LNCS, pages 127–143. Springer, 2020.  doi:10.1007/978-3-030-59152-6\\_7.
  * [13] Helmut Seidl.  Fast and simple nested fixpoints.  Universität Trier, Mathematik/Informatik, Forschungsbericht, 96-05, 1996.


# Comparing Hallucination Detection Metrics for Multilingual Generation

Haoqiang Kang Terra Blevins Luke Zettlemoyer
Paul G. Allen School of Computer Science & Engineering,
University of Washington
{haoqik, blvns<EMAIL_ADDRESS>
###### Abstract

While many automatic hallucination detection techniques have been proposed for
English texts, their effectiveness in multilingual contexts remains
unexplored. This paper aims to bridge the gap in understanding how these
hallucination detection metrics perform on non-English languages. We evaluate
the efficacy of various detection metrics, including lexical metrics like
ROUGE and Named Entity Overlap and Natural Language Inference (NLI)-based
metrics, at detecting hallucinations in biographical summaries in many
languages; we also evaluate how correlated these different metrics are to
gauge whether they measure the same phenomena. Our empirical analysis reveals
that while lexical metrics show limited effectiveness, NLI-based metrics
perform well in high-resource languages at the sentence level. In contrast,
NLI-based metrics often fail to detect atomic fact hallucinations. Our
findings highlight existing gaps in multilingual hallucination detection and
motivate future research to develop more robust detection methods for LLM
hallucination in other languages.

##  1 Introduction

Large Language Models (LLMs) have brought about remarkable advances in text
generation. However, they are still prone to factuality hallucination - the
generated text conflicts with established world knowledge Huang et al. (2023);
Zhang et al. (2023). Despite considerable research efforts towards
understanding and detecting hallucinations, the focus has predominantly been
on English texts Huang et al. (2023); Zhang et al. (2023); Ji et al. (2023).
This emphasis has resulted in a significant knowledge gap regarding
hallucinations in multilingual contexts, and it is currently unclear whether
the methods developed for detecting and addressing hallucinations in English
are effective or even applicable in multilingual settings.

In this paper, we address the highlighted issues by evaluating the
effectiveness of various metrics (initially proposed for English generation)
within a multilingual context. Our approach involves a comparative analysis of
traditional lexical metrics, such as ROUGE Lin (2004) and Named Entity
Overlap, alongside Natural Language Inference (NLI) metrics. Additionally, we
compare reference-based metrics with pairwise metrics that are based on the
consistency among generated samples; we also present a correlation study
between these automated metrics and human factuality verification. These
evaluations shed light on the efficacy of these metrics in non-English
languages and aim to establish a more robust framework for hallucination
detection in multilingual language models.

We empirically evaluate different hallucination detection techniques in the
multilingual context and find that:

  * •

Lexical overlap metrics (e.g., ROUGE, named entity overlap) do not correlate
with NLI-based metrics in detecting factual hallucinations in both reference-
free and reference-based settings.

  * •

Pairwise NLI-based metrics strongly correlate with reference-based metrics in
high-resource languages, but this significantly diminishes in low-resource
languages.

  * •

Automatic NLI-based metrics effectively identify sentence-level hallucinations
in high-resource languages when compared to human evaluations. However, their
performance diminishes when assessing simpler atomic facts.

These findings indicate several open problems for multilingual hallucination
detection. While traditional lexical overlap methods and pairwise comparisons
of multiple generated texts are more accessible approaches for low-resource
languages, they are often inadequate for hallucination detection. This
highlights that the effectiveness of hallucination detection is closely tied
to the availability and quality of language resources, following the trend
observed in English that detection accuracy depends on natural language
understanding abilities Manakul et al. (2023); Min et al. (2023). Our work
points to a substantial gap in hallucination detection in multilingual
contexts, necessitating focused future research to bridge this divide.

##  2 Analyzing Methods for Multilingual Hallucination Detection

Hallucination refers to machine-generated content that is not faithful to a
reference. This reference could be source text, preceding generated context,
or world knowledge Ji et al. (2023); Zhang et al. (2023). Hallucinations can
be further classified into two types: verifiable hallucinations, which happen
when the generated content directly contradicts the reference, and
unverifiable hallucinations, meanwhile, refer to generated content that cannot
be verified with the source material.

In this paper, we measure the efficacy of different metrics on detecting
multilingual hallucinations. We focus on biography generation, a domain that
is particularly sensitive to factual accuracy and coherence Min et al. (2023);
Dhuliawala et al. (2023). We test a suite of automatic metrics, each of which
caters to a different aspect of factual generation: ROUGE Lin (2004), named
entity overlap, and Natural Language Inference (NLI)-based methods.

###  2.1 Multilingual Biography Generation

Table 1: Generation quality statistics for BLOOMZ-mt. The languages in bold are the most frequent in the ROOTS pretraining corpus Laurençon et al. (2022), and the underlined languages are covered in the xP3mt fine-tuning dataset Muennighoff et al. (2023). ”FLang.” refers to the most frequently generated language for each prompt language. Lang. | #Token | #Sent. | Valid % | FLang. | Acc.
---|---|---|---|---|---
en | 78.3 | 2.64 | 99.97 | en | 96.0
zh | 115.8 | 4.30 | 100.00 | zh | 92.43
es | 62.8 | 2.01 | 100.00 | es | 92.33
fr | 71.3 | 2.24 | 100.00 | fr | 93.23
vi | 45.6 | 1.66 | 98.92 | vi | 71.67
id | 46.3 | 1.76 | 98.30 | en | 36.45
de | 63.3 | 2.33 | 99.58 | en | 2.79
it | 58.1 | 1.94 | 99.76 | en | 3.31
ja | 50.3 | 1.97 | 90.73 | zh | 21.85
bg | 17.4 | 1.15 | 86.74 | en | 13.69
ro | 9.6 | 0.93 | 80.24 | en | 2.68
sv | 7.6 | 0.51 | 40.73 | en | 1.79
th | 14.8 | 0.81 | 77.08 | th | 94.96
ru | 10.2 | 0.68 | 55.49 | ru | 50.44
uk | 5.7 | 0.40 | 35.24 | uk | 41.87
fa | 3.2 | 0.13 | 10.80 | ur | 29.90
fi | 1.7 | 0.11 | 9.76 | fi | 34.52
ko | 2.0 | 0.09 | 8.37 | ko | 47.30
hu | 0.8 | 0.05 | 6.28 | pt | 14.36
Avg. | 34.8 | 1.35 | 31.65 | - | 50.01

Inspired by prior work measuring factuality in English Min et al. (2023), we
generate parallel biographies in different languages. The generated texts are
then compared against a reference text (for reference-based metrics) and other
generated samples (pairwise metrics) to detect hallucinations.

This section characterizes the generation quality of these biographies (Table
1). We consider the average length of each biography (in tokens and
sentences), along with estimates of how accurate the generation language is to
the prompt language, as in some cases, multilingual LMs will generate
continuations in an unexpected language Kang et al. (2023); Bawden and Yvon
(2023).

The length of the generated texts varies notably across languages. High-
resource languages like English and French average 78.3 and 115.8 tokens per
response, respectively. However, mid-resource languages such as Thai tend to
generate much shorter biographies and incomplete sentences, and low-resource
languages fare even worse (for instance, Ukrainian averages just 5.7 tokens
and 0.40 sentences), demonstrating the significant gap in generation abilities
across languages.

We assess the accuracy of the generated languages through three metrics: the
percentage of valid generations that is detectable for the langdetect package
(Valid %)111Some generations are incomplete, or their language is
undetectable., the most frequently generated language for a given target
language (Flang), and the accuracy of generated language out of the valid
generations (Acc.). For high-resource languages like English, Chinese,
Spanish, and French, the models generally generate text in the correct
language; however, for the languages highlighted with an underwave the model
generates in the wrong language the majority of the time. Often, this is due
to the model generating in a closely related high-resource language. For
languages such as Italian and Bulgarian, many inaccurate generations are in
English. Similarly, Japanese generations often switch to Chinese when mistakes
occur. Languages with more distinctive linguistic features —such as Thai’s
unique script—facilitate more accurate model generations.

###  2.2 Automatic Methods for Multilingual Factuality Detection

Following the language verification and ruling out examples where the
generations are in the wrong languages, the next phase involves the detection
of hallucinations in a multilingual environment by assessing the consistency
between a target generation and either a reference text or its other
generations. This section considers various automatic metrics for detecting
hallucinations in long-form generations.

#### ROUGE

The ROUGE metric is employed to assess the token-level similarity between
texts. We consider the ROUGE 1 (R1), 2 (R2), L (RL), and Lsum (RLsum) scores
of the generated text against the reference.

#### Named Entity Overlap (NEO)

We hypothesize that the sets of named entities in the gold and generated text
will differ if there is hallucination in the generation Nan et al. (2021). We
calculate the F1, precision, and recall scores of named entities between the
generated and reference text as an estimate for factual hallucinations.

#### NLI-based Detection

Following Manakul et al. (2023) and Elaraby et al. (2023), we adopt the NLI-
based zero-shot sentence-level SUMMAC ($SummaC_{zs}$) scoring system Laban et
al. (2021) to evaluate hallucinations. The $SummaC_{zs}$ method was originally
developed to gauge the consistency between a summary $S$ and a document $D$,
by segmenting them into sentences $S_{1},\dots,S_{N}$ and $D_{1},\dots,D_{M}$
respectively. Aligning with the optimal configuration in Laban et al. (2021),
we employ the $max$ operator to compute the score for a sentence. Denote
$e_{S_{n}}^{D_{m}}$ and $c_{S_{n}}^{D_{m}}$ as the entailment and
contradiction score for the generated sentence $S_{n}$ given the reference
sentence $D_{m}$, respectively.

We define three metrics to quantify verifiable hallucination and one metric to
quantify unverifiable hallucination, respectively. At sentence-level
detection, for a generated sentence $S_{i}$ and a reference $D$, to detect
verifiable hallucination, we define the following three metrics:
$\mathbf{ENT_{S_{i}}}=\max_{m}{e_{S_{i}}^{D_{m}}}$,
$\mathbf{CON_{S_{i}}}=\max_{m}{c_{S_{i}}^{D_{m}}}$, and
$\mathbf{DIFF_{S_{i}}}=\max_{m}{e_{S_{i}}^{D_{m}}}-\max_{m}{c_{S_{i}}^{D_{m}}}$.
To detect unverifiable hallucination, we define the following metric:

$\mathbf{UNV_{S_{i}}}=1-\max(\max_{m}{e_{S_{i}}^{D_{m}}},\max_{m}{c_{S_{i}}^{D_{m}}})$

When evaluating each of the above hallucination metrics on a generated text
$\hat{t}$, we consider two settings as the reference text $t$:
Reference-based This setting compares $\hat{t}$ against the relevant
biographical article in Wikipedia.
Pairwise We generate $k$ samples for each biography. In this setting, we
compare $\hat{t}$ against the other generated samples for the same person and
calculate the average score across all generations.

##  3 Experiment Setup

###  3.1 Dataset

Our curated dataset encompasses 19 languages: English, Spanish, Russian,
Indonesian, Vietnamese, Persian, Ukrainian, Swedish, Thai, Japanese, German,
Romanian, Hungarian, Bulgarian, French, Finnish, Korean, Italian, and Chinese.
Using WikiData, we extract 500 human names that are covered by all of these
languages on Wikipedia, based on diverse page view counts from 2022-01-01 to
2023-01-01. For our reference text, we use the Wikipedia API to obtain the
full-page content. We detect instances where the LLMs generate text in an
incorrect language with langdetect.222APIs: https://query.wikidata.org/,
https://pypi.org/project/wikipedia/, and https://pypi.org/project/langdetect/,
respectively

###  3.2 Models and Prompting Details

In our experiments, we deploy the pretrained multilingual BLOOM model as well
as the BLOOMZ-mt model, which is fine-tuned with machine-translated prompts
Workshop (2023). We use nucleus decoding Holtzman et al. (2020) with
$top\\_p=0.9$ and generate five responses per prompt. For each evaluation
language, we generate a prompt template with Google Translate. The template in
English is ”Tell me a biography of ¡Name¿.”; all templates are in Appendix
(Figure 2).

###  3.3 Detection Metric Details

ROUGE scores are calculated with TorchMetrics333https://github.com/Lightning-
AI/torchmetrics, and we remove all stopwords before calculating ROUGE-1.
Entities are extracted with Spacy’s named entity
recognizer444https://spacy.io/api/entityrecognizer; we note that this tagger
only covers 13 of the 19 languages considered in our experiments. For the NLI-
based metric, we finetune the XLMR-large model Conneau et al. (2020) on the
subset of the XNLI dataset Conneau et al. (2018) that intersects with the
languages used in our experiments. The finetuned model has an average
validation accuracy of 85.4% for the nine intersecting languages.

Language | $\mathrm{ENT}$ | $\mathrm{DIFF}$ | $\mathrm{UNV}$
---|---|---|---
# examples in correct language ¿ 1,000
English | 0.55 | 0.38 | 0.19
French | 0.52 | 0.40 | 0.15
Chinese | 0.56 | 0.41 | 0.21
Spanish | 0.46 | 0.41 | 0.17
Thai | 0.36 | 0.39 | 0.32
Vietnamese | 0.35 | 0.31 | 0.00
Indonesian | 0.28 | 0.31 | 0.09
# examples in correct language ¡ 1,000
Russian | 0.16 | 0.21 | 0.11
Japanese | 0.37 | 0.40 | 0.07
Ukrainian | 0.23 | 0.19 | 0.17
Bulgarian | 0.42 | 0.32 | 0.28
Korean | 0.05 | 0.08 | -0.01
# examples in correct language ¡ 100
Finnish | 0.09 | 0.12 | 0.01
Italian | 0.12 | 0.13 | 0.14
Persian | 0.13 | 0.15 | 0.02
German | 0.50 | 0.45 | 0.11
Romanian | 0.00 | 0.00 | 0.14
Hungarian | 0.24 | 0.21 | 0.11
Swedish | 0.30 | 0.27 | -0.29
Table 2: The correlation between the reference-based NLI result and the
pairwise NLI result across different languages. The languages with underline
are covered in the XNLI finetuing dataset. The numbers in yellow have the
p-values larger than 0.05.

##  4 Results

In this section, we compare evaluation metrics to estimate hallucinations in
our generated biographical corpus (Section 4.1). We then perform a correlation
study to test whether the proposed metrics agree when hallucination occurs
(Section 4.2). We find that traditional, reference-based lexical metrics
(i.e., ROGUE and named entity overlap) are likely insufficient to capture
hallucinations, as they rarely correlate with stronger NLI-based approaches.
We also observe that pairwise metrics detect hallucinations less often in
lower-resource languages when compared to reference-based metrics.

###  4.1 Comparison of Automatic Hallucination Metrics

Table 3: Results of different reference-based metrics for the BLOOMZ-mt model. ”-” indicates the language is not covered by the Spacy NER tool. All of the ROUGE and Named Entity Overlap (NEO) results are in percentage (%). Language | R1-F1 | R1-P | R1-R | R2-F1 | R2-P | R2-R | NEO-F1 | NEO-P | NEO-R | $\mathrm{DIFF}$ | $\mathrm{UNV}$
---|---|---|---|---|---|---|---|---|---|---|---
High-Resource Languages
English | 1.83 | 87.58 | 0.94 | 0.87 | 47.38 | 0.44 | 4.27 | 53.41 | 2.26 | -0.60 | 0.19
Chinese | 6.43 | 57.34 | 3.76 | 2.07 | 23.22 | 1.17 | 4.69 | 35.27 | 2.79 | -0.62 | 0.21
Spanish | 2.77 | 85.86 | 1.47 | 1.35 | 49.10 | 0.71 | 3.28 | 48.48 | 1.76 | -0.51 | 0.18
French | 2.18 | 87.78 | 1.13 | 1.06 | 51.41 | 0.55 | 4.35 | 57.41 | 2.31 | -0.54 | 0.16
Vietnamese | 6.82 | 92.92 | 4.22 | 4.10 | 73.28 | 2.43 | - | - | - | -0.49 | 0.15
Indonesian | 7.51 | 68.51 | 4.87 | 2.36 | 26.39 | 1.53 | - | - | - | -0.45 | 0.22
Middle-Resource Languages
German | 0.38 | 71.34 | 0.19 | 0.11 | 35.22 | 0.05 | 0.83 | 36.06 | 0.42 | -0.65 | 0.15
Italian | 0.50 | 69.13 | 0.25 | 0.13 | 29.82 | 0.07 | 1.00 | 30.26 | 0.52 | -0.58 | 0.17
Japanese | 0.73 | 14.62 | 0.40 | 0.05 | 1.50 | 0.03 | 0.47 | 15.52 | 0.25 | -0.72 | 0.21
Bulgarian | 0.16 | 4.92 | 0.09 | 0.01 | 0.37 | 0.01 | - | - | - | -0.61 | 0.19
Romanian | 1.02 | 69.75 | 0.53 | 0.42 | 45.79 | 0.22 | 0.39 | 17.47 | 0.20 | -0.29 | 0.24
Swedish | 0.66 | 86.37 | 0.33 | 0.32 | 77.23 | 0.16 | 1.28 | 45.24 | 0.66 | -0.40 | 0.63
Low-Resource Languages
Thai | 0.04 | 1.14 | 0.02 | 0.00 | 0.00 | 0.00 | - | - | - | -0.56 | 0.38
Russian | 0.09 | 4.69 | 0.05 | 0.01 | 0.28 | 0.00 | 0.48 | 11.28 | 0.25 | -0.58 | 0.47
Ukrainian | 0.04 | 1.53 | 0.02 | 0.00 | 0.00 | 0.00 | 0.70 | 20.64 | 0.36 | -0.53 | 0.66
Persian | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | - | - | - | -0.50 | 0.92
Finnish | 0.89 | 37.70 | 0.46 | 0.20 | 10.03 | 0.10 | 0.58 | 23.71 | 0.30 | -0.59 | 0.91
Korean | 0.18 | 6.58 | 0.09 | 0.01 | 0.88 | 0.00 | 0.24 | 8.48 | 0.12 | -0.53 | 0.94
Hungarian | 0.74 | 64.74 | 0.37 | 0.16 | 23.23 | 0.08 | - | - | - | -0.53 | 0.97

We first consider how different automatic methods for detecting hallucination
perform across languages on the generated biographical data from the BLOOMZ-mt
model (Table 3). High-resource languages, such as English, Chinese, Spanish,
French, Vietnamese, and Indonesian, exhibit higher recall scores, which
suggests that the text generated in these languages has better coverage of the
corresponding Wikipedia reference content. This contrasts sharply with lower-
resource languages, which demonstrate significantly diminished recall.
Interestingly, languages that frequently produce incorrect language outputs
(e.g., German and Italian) or often yield empty or incomplete generations
(e.g., Swedish and Hungarian) still have relatively high precision scores.
While these generations seem to contain few explicit hallucinations, they also
exclude many facts from the reference, as indicated by their correspondingly
low recall scores.

When considering the $\mathrm{DIFF}$ metrics, all languages under scrutiny
resulted in negative scores, which was consistent even among the higher-
resource languages like English and Chinese. This indicates a tendency towards
contradictions in the generated text with their respective reference texts.
For the $\mathrm{UNV}$ scores, higher and middle-resource languages (ranging
from English to Romanian in the table 3) cluster within a similar scope of
0.15 to 0.25. In contrast, low-resource languages that often produce empty or
incomplete generations, such as Ukrainian, Persian, Finnish, and Korean, show
much higher $\mathrm{UNV}$ scores. This implies that the $\mathrm{UNV}$ metric
is sensitive to incomplete text generations and missing information and may
indicate the model’s generation errors beyond hallucination. As for the
reference-free pairwise metrics, we observe similar trends across different
languages (Table 9).

###  4.2 Correlation Study Across Metrics

In this section, we conduct a correlation analysis to determine how various
metrics align in measuring hallucination in multilingual contexts. This
includes (1) the correlation between lexical hallucination metrics and NLI-
based metrics, (2) the performance of the four reference-based NLI metrics,
and (3) the relationship between pairwise metrics and reference-based metrics.

Figure 1: Heat map of the Pearson Correlation between reference-based metrics averaged over high-resource languages. All the P-values are less than 0.05. Entity |  Generation
---|---
Example of Annotation
Alessandro Del Piero |  Gen: Alessandro Del Piero, born on September 28, 1976 in Brescia, Italy, is a former Italian professional football player who served as a forward. Wiki: Alessandro Del Piero, Italian male football player…The old Maldini, who was the head coach of the national team at the time, appointed newcomers Del Piero and Vieri as the main forwards… Comment: There are 4 facts in this sentence, with 1 contradictory hallucination and 1 unverifiable hallucination. The birth date is wrong; Wikipedia doesn’t mention the birth place; for the last entity, the evidence indirectly support it.
Example of Instruction-Conflict Hallucination
Carl Edward Sagan |  Gen: Stephen Hawking (January 8, 1942 -) is a famous British physicist and cosmologist.
Example of Preceding-Context-Conflict Hallucination
Blanca of Castile |  Gen: Blanca of Castile (Blanca of Castile), born in 1188 and died in 1252, was the princess of Castile, queen and regent of France. Blanca is a city in the Autonomous Community of Castilla-La Mancha, Spain.
Table 4: Examples of annotation process and types of hallucinations. Sentences
highlighted in red represent verifiable hallucinations that contradict
evidence found in Wikipedia; those marked in yellow denote unverifiable
hallucinations which lack clear evidence for verification and content
highlighted in green is considered factual.

#### Lexical hallucination metrics do not correlate with NLI-based metrics.

Figure 1 shows that in high-resource languages (i.e., English, Chinese,
French, Spanish, Vietnamese, and Indonesian), ROUGE-1 and ROUGE-L metrics
demonstrate a high degree of correlation, as do the ROUGE metrics and Named
Entity Overlap (NEO). However, we generally find no correlation between
lexical- and NLI-based metrics, indicating that while both lexical- and NLI-
based approaches are commonly proposed as automatic methods for hallucination
detection, they do not measure the same deviations from a reference text.

#### Reference-based NLI-based metrics.

We also observe interesting trends regarding the relationship between
different NLI-based metrics (Figure 1). We find that $\mathrm{ENT}$ scores are
highly correlated with the $\mathrm{DIFF}$ score, indicating that these
metrics identify similar artifacts in the text. Surprisingly, no correlation
is observed between $\mathrm{UNV}$ and $\mathrm{CON}$ scores. Moreover, we
find a negative correlation between $\mathrm{UNV}$ and $\mathrm{CON}$ scores.
This is because sentences that include verifiable hallucinations likely
contradict the reference text. In contrast, sentences with information that is
unsubstantiated by the reference (e.g., unverifiable) will be identified as
neutral instead.

#### Pairwise and reference-based metrics correlate in higher-resource
languages.

For high-resource languages in the XNLI finetuning dataset (English, French,
Chinese, Spanish, Bulgarian, and German), we observe a higher correlation in
the range of 0.35 to 0.56 for pairwise NLI metrics when it comes to detecting
verifiable hallucinations by $\mathrm{ENT}$ score (Table 2). This suggests
pairwise metrics can identify generated content that deviates from the
reference. However, the Pearson Correlation Coefficient shows lower
correlation values (in the range of 0.15 to 0.21) compared to pairwise
$\mathrm{UNV}$. For lower-resource languages, such as Finnish, Italian,
Persian, and others, the correlation coefficients with the entailment score
are often in the range of 0.00 to 0.30 and not statistically significant,
highlighting the challenge of effective hallucination detection in contexts
with limited language resources.

##  5 Human Evaluation of Multilingual Hallucination Metrics

Currently, there are no standard multilingual hallucination detection datasets
available on which to compare the considered methods. We, therefore, annotate
model generations in English and Chinese; annotations are performed by native
speakers of each language. They manually find all verifiable and unverifiable
hallucinations by checking if the generation is supported by the Wikipedia
reference at both the sentence- and atomic-fact-level. Examples of resulting
annotations are shown in Table 4.

l—cccc—cccc

Sentence-Level Atomic-Fact-Level
Metric Pearson AUC${}_{\textit{F}}$ AUC${}_{\textit{NF}}$ Accuracy Pearson
AUC${}_{\textit{F}}$ AUC${}_{\textit{NF}}$ Accuracy
Random - 10.84 82.86 50.00 - 52.1143.56 50.00
Pairwise
R2-P. 0.08 19.78 81.48 - 0.10 51.23 44.23 -
RL-P. 0.11 20.04 83.10 - 0.12 52.18 42.83 -
NEO-P. 0.14 17.49 80.84 - 0.09 53.09 45.32-
$\mathrm{DIFF}$ 0.21 38.46 89.49 68.21 0.19 57.46 54.41 56.26
$\mathrm{ENT}$ 0.31 40.32 90.86 70.97 0.23 60.71 57.48 53.47
$\mathrm{CON}$ 0.11 16.47 80.41 49.13 -0.01 51.49 52.16 50.48

Reference

R2-P. 0.21 30.05 89.08 - 0.19 53.28 46.25 -
RL-P. 0.17 28.54 85.35 - 0.13 50.31 49.93 -
NEO-P. 0.17 16.15 83.75 - 0.12 57.54 47.51 -
$\mathrm{DIFF}$ 0.34 56.11 94.14 75.00 0.31 65.85 60.90 63.19
$\mathrm{ENT}$ 0.49 65.32 94.96 78.97 0.35 68.00 63.6964.18
$\mathrm{CON}$ 0.08 31.56 87.49 69.77 -0.19 53.18 57.43 59.70

Table 5: Sentence- and atomic-fact-level verifiable hallucination detection in
human evaluation. F denotes factual examples and NF denotes non-factual
examples. The numbers in yellow have p-values of the correlation is larger
than 0.05. Note that the correlation coefficient of $\mathrm{CON}$ should be
expected as negative.

###  5.1 Experimental Setup

Annotators manually label all the seven elements mentioned above in each
sentence of the generation. For each sentence, we annotate 1) all relevant
evidence sentences from the entire Wikipedia page; 2) the number of total
facts in a sentence ($N_{t}$); 3) the number of verifiable supported facts
($N_{vs}$); 4) the number of verifiable contradictory facts ($N_{vc}$); 5) the
number of non-verifiable facts ($N_{nv}$); 6) yes/no if the generated sentence
has a conflict with the instruction (e.g., generating in wrong human entity);
7) yes/no if the generated sentence has a conflict with its preceding
generated context. When annotating atomic facts, the annotators also rephrase
the atomic facts from a given sentence into simpler single-fact sentences.
Annotation statistics can be found in Table 8.

#### Metrics

We compare automatic metric performance with human annotations using
correlation and classification. For correlation, we investigate the
relationship of the metrics with the support rate ($N_{vs}/N_{t}$) for
verifiable hallucination detection and with the unverified rate
($N_{nv}/N_{t}$) for unverifiable hallucination detection using their Pearson
correlations. When considering the classification performance of these
metrics, we calculate the Precision-Recall area under the curve (AUC-PR)
between the human annotations and the automatic continuous metrics. We convert
the human annotations into classification labels by labeling an example as
factual only if all its facts are supported by evidence (for verifiable
hallucinations); we consider three label thresholds for estimating
unverifiable hallucination: $N_{nv}\geq 1$, $N_{nv}/N_{t}\geq 50\%$, or
$N_{nv}=N_{t}$ (Table 5.2). We also discretize classification accuracy by
setting thresholds for NLI-based metrics with 0.5 for the entailment and
contradictory scores and 0 for the difference between these two scores. The
thresholds were selected based on the different degrees of tolerance for the
proportions of unverifiable hallucinations in a sentence.

We observe distinct patterns for sentence- and atomic-level annotations:
sentence-level examples typically encompass multiple facts and require several
sentences of evidence, whereas a single sentence of evidence generally
suffices for atomic-fact verification (Table 8). We also note that
unverifiable hallucinations are much more common than supported or
contradictory instances of factuality.

###  5.2 Analysis Findings

#### NLI entailment outperforms lexical metrics on sentence-level
verification.

We observe low correlation coefficients between lexical metrics like ROUGE-2
(R2) and Named Entity Overlap (NEO) with the human-annotated support rate (SR;
Table 5). Moreover, AUC-PR for these metrics exhibits minor improvements over
the random classification baseline, particularly for non-factual examples
(NF), underscoring the limit of lexical metrics for accurately detecting
factual hallucinations.

In contrast, we observe that NLI-based metrics, particularly $\mathrm{ENT}$,
outperform other metrics in detecting verifiable hallucinations at the
sentence level due to its high correlation with different measures of human
verification (Table 5). These results corroborate the NLI metric results in
English in Manakul et al. (2023). Furthermore, the $\mathrm{DIFF}$ score shows
comparable performance, whereas $\mathrm{CON}$ alone does not demonstrate the
same level of effectiveness.

#### Pairwise metrics underperform reference-based metrics.

When compared against human annotations, pairwise metrics underperform the
reference-based ones across the board: their Pearson correlations, AUCF,
AUCNF, and accuracies are all worse than the metrics using references, and
this holds at both the sentence- and atomic-fact-levels (Table 5). Notably,
pairwise lexical-based metrics like R2-P, RL-P, and NEO-P show relatively
weaker performance than reference-based metrics, indicating a limited
capability in accurately evaluating hallucinations. However, we note that
pairwise NLI-based metrics, particularly the entailment and difference scores,
demonstrate significantly better performance than other pairwise settings
(though they still underperform comparable reference metrics). This suggests
pairwise NLI-based approaches may remain useful in hallucination detection
settings where references are unavailable.

lcccc Metric Pearson AUC${}_{\textit{U}}$ AUC${}_{\textit{NU}}$ Accuracy

At least one unverifiable fact
Random${}_{\textit{Sent}}$ \- 25.45 68.72 50.00
$\mathrm{UNV}$${}_{\textit{Sent}}$ 0.02 22.25 77.50 45.07
Random${}_{\textit{Atom}}$ \- 71.93 17.88 50.00
$\mathrm{UNV}$${}_{\textit{Atom}}$ 0.12 79.26 27.36 57.74
At least 50% unverifiable facts
Random${}_{\textit{Sent}}$ \- 42.02 44.01 50.00
$\mathrm{UNV}$${}_{\textit{Sent}}$ \- 47.25 48.88 57.36
100% unverifiable facts
Random${}_{\textit{Sent}}$ \- 25.01 67.27 50.00
$\mathrm{UNV}$${}_{\textit{Sent}}$ \- 26.79 69.75 59.35

Table 6: Results of unverifiable hallucination detection in human evaluation.
All the p-values of the correlation is less than 0.05. Sent denotes sentence-
level detection, and Atom denotes atomic-fact-level detection. U denotes
unverifiable hallucination, and NU denotes non-unverifiable (i.e., factual or
verifiable).

#### NLI-based metrics struggle to detect unverifiable hallucination.

Comparison of NLI-based metrics against human annotators on unverifiable
hallucination detection reveals significant challenges. Automatic metrics show
marginal improvements over random classification and low correlation with the
human unverifiable annotation. This indicates difficulties in discerning the
nuanced differences between evidence and generated text (e.g., the first
example in Table 4).

#### NLI-based metrics fails to evaluate factuality on simple atomic facts.

Unlike sentence-level verification, NLI metrics encounter significant
challenges in accurately verifying the factuality of simple atomic facts
(Table 5). Metrics such as AUC-PR and accuracy demonstrate a marked decrease
in the effectiveness of NLI-based metrics on atomic facts. This aligns with
Luo et al. (2022), which also highlighted similar limitations in English NLI
metrics for verification, and these findings underscore the need for further
refinement in NLI approaches to handle atomic factuality. This finding
underscores the potential of alternative metrics in addressing the limitations
of current NLI approaches, especially in the critical area of atomic
factuality evaluation.

##  6 Related Work

###  6.1 Factuality Hallucination Detection

Detecting hallucinations in LLMs is crucial for ensuring the reliability of
machine-generated content. One line of work utilizes the uncertainty of LLM
generation. Some studies analyze the probability of tokens Mielke et al.
(2022); Kadavath et al. (2022); Varshney et al. (2023), whereas other methods
evaluate the inconsistency between multiple generated samples, including NLI-
based approaches Elaraby et al. (2023); Manakul et al. (2023). Other work
utilizes external retrieved evidence as reference text and verifies if the
generated text is supported by the reference text Chern et al. (2023); Min et
al. (2023). However, such factuality hallucination evaluations are limited in
multilingual settings. Existing works in this area include prompting methods
Ahuja et al. (2023) and machine translation Lai et al. (2023). Our work aims
to bridge the gap between English and multilingual generation evaluation
settings.

###  6.2 Task-specific Multilingual Hallucination

There are also some existing multilingual hallucination mitigation methods for
specific tasks, such as abstractive summarization and machine translation. Qiu
et al. (2023) introduces the mFACT metric to evaluate the faithfulness of non-
English summaries by transferring English metrics to target languages via
machine translation. To enhance the faithfulness of multilingual
summarization, Aharoni et al. (2022) leverages factual consistency models,
highlighting the importance of addressing hallucinations in languages beyond
English. In the realm of neural machine translation (NMT), Dale et al. (2022)
emphasizes the role of the source’s contribution to detect and alleviate
hallucinations, while another line of works Lee et al. (2019); Raunak et al.
(2021) analyze the NMT’s susceptibility to hallucinations and impact of data-
generation processes like back-translation on hallucination. Xu et al. (2023)
takes a deep dive into the internal workings of neural sequence generation
models. Together, these works underline the pervasive challenge of
hallucinations in multilingual tasks.

##  7 Conclusion

This study investigates the effectiveness of automatic metrics for detecting
factual hallucinations in multilingual contexts. We document the limitations
of traditional lexical metrics, such as ROUGE and Named Entity Overlap, in
detecting factuality hallucinations in these multilingual settings.
Specifically, our work reveals that while NLI-based metrics show promise in
high-resource languages at the sentence level, their effectiveness diminishes
when applied to simpler atomic facts. Moreover, the reliability of NLI-based
metrics is tied to the performance of NLI models, which poses a significant
challenge in languages with lower resources. Therefore, our work highlights
that the ability to detect hallucinations effectively in a multilingual
setting is intrinsically linked to the availability and quality of linguistic
resources in a given langauge. Therefore, automatically detecting factuality
hallucinations in lower-resource languages remains a significant gap in
current NLP methods.

## Limitations

This study focuses on text generation and hallucination in a specific setting
(namely, generating biographical summaries with the BLOOM-mt model) in order
to perform a controlled study on how different automatic metrics detect
factual hallucinations. It remains an open question whether these findings
hold in other generation settings, particularly when there is less reliance on
factual knowledge (such as story generation).

Additionally, portions of our experimental setup rely on automatic methods.
Specifically, we use machine translation to construct the prompt templates,
which may introduce noise into the prompts. Furthermore, due to the
unavailability of native speakers for other languages, our human evaluation
and comparison against automated metrics is limited to Chinese and English.

Finally, we note that we do not include more complex, LLM-based methods of
hallucination detection. The efficacy of these methods is directly linked to
the performance of these models in the target language, which remains an open
question for popular LLMs on many of the languages we consider. We therefore
limit our analysis to simpler lexical- and NLI-based approaches.

## References

  * Aharoni et al. (2022) Roee Aharoni, Shashi Narayan, Joshua Maynez, Jonathan Herzig, Elizabeth Clark, and Mirella Lapata. 2022.  mface: Multilingual summarization with factual consistency evaluation.  _arXiv preprint arXiv:2212.10622_.
  * Ahuja et al. (2023) Kabir Ahuja, Rishav Hada, Millicent Ochieng, Prachi Jain, Harshita Diddee, Samuel Maina, Tanuja Ganu, Sameer Segal, Maxamed Axmed, Kalika Bali, et al. 2023.  Mega: Multilingual evaluation of generative ai.  _arXiv preprint arXiv:2303.12528_.
  * Bawden and Yvon (2023) Rachel Bawden and François Yvon. 2023.  Investigating the translation performance of a large multilingual language model: the case of bloom.  In _Proceedings of the 24th Annual Conference of the European Association for Machine Translation_.
  * Chern et al. (2023) I Chern, Steffi Chern, Shiqi Chen, Weizhe Yuan, Kehua Feng, Chunting Zhou, Junxian He, Graham Neubig, Pengfei Liu, et al. 2023.  Factool: Factuality detection in generative ai–a tool augmented framework for multi-task and multi-domain scenarios.  _arXiv preprint arXiv:2307.13528_.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.
  * Conneau et al. (2018) Alexis Conneau, Guillaume Lample, Ruty Rinott, Adina Williams, Samuel R. Bowman, Holger Schwenk, and Veselin Stoyanov. 2018.  Xnli: Evaluating cross-lingual sentence representations.
  * Dale et al. (2022) David Dale, Elena Voita, Loïc Barrault, and Marta R Costa-jussà. 2022.  Detecting and mitigating hallucinations in machine translation: Model internal workings alone do well, sentence similarity even better.  _arXiv preprint arXiv:2212.08597_.
  * Dhuliawala et al. (2023) Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. 2023.  Chain-of-verification reduces hallucination in large language models.  _arXiv preprint arXiv:2309.11495_.
  * Elaraby et al. (2023) Mohamed Elaraby, Mengyin Lu, Jacob Dunn, Xueying Zhang, Yu Wang, Shizhu Liu, Pingchuan Tian, Yuping Wang, and Yuxuan Wang. 2023.  Halo: Estimation and reduction of hallucinations in open-source weak large language models.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_.
  * Huang et al. (2023) Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, et al. 2023.  A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions.  _arXiv preprint arXiv:2311.05232_.
  * Ji et al. (2023) Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. 2023.  Survey of hallucination in natural language generation.  _ACM Computing Surveys_ , 55(12):1–38.
  * Kadavath et al. (2022) Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, et al. 2022.  Language models (mostly) know what they know.  _arXiv preprint arXiv:2207.05221_.
  * Kang et al. (2023) Haoqiang Kang, Terra Blevins, and Luke Zettlemoyer. 2023.  Translate to disambiguate: Zero-shot multilingual word sense disambiguation with pretrained language models.  _arXiv preprint arXiv:2304.13803_.
  * Laban et al. (2021) Philippe Laban, Tobias Schnabel, Paul N. Bennett, and Marti A. Hearst. 2021.  Summac: Re-visiting nli-based models for inconsistency detection in summarization.
  * Lai et al. (2023) Viet Lai, Nghia Ngo, Amir Pouran Ben Veyseh, Hieu Man, Franck Dernoncourt, Trung Bui, and Thien Nguyen. 2023.  ChatGPT beyond English: Towards a comprehensive evaluation of large language models in multilingual learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 13171–13189, Singapore. Association for Computational Linguistics.
  * Laurençon et al. (2022) Hugo Laurençon, Lucile Saulnier, Thomas Wang, Christopher Akiki, Albert Villanova del Moral, Teven Le Scao, Leandro Von Werra, Chenghao Mou, Eduardo González Ponferrada, Huu Nguyen, et al. 2022.  The bigscience roots corpus: A 1.6 tb composite multilingual dataset.  _Advances in Neural Information Processing Systems_ , 35:31809–31826.
  * Lee et al. (2019) Katherine Lee, Orhan Firat, Ashish Agarwal, Clara Fannjiang, and David Sussillo. 2019.  Hallucinations in neural machine translation.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Luo et al. (2022) Cheng Luo, Wei Liu, Jieyu Lin, Jiajie Zou, Ming Xiang, and Nai Ding. 2022.  Simple but challenging: Natural language inference models fail on simple sentences.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 3449–3462, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Manakul et al. (2023) Potsawee Manakul, Adian Liusie, and Mark JF Gales. 2023.  Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models.  _arXiv preprint arXiv:2303.08896_.
  * Mielke et al. (2022) Sabrina J Mielke, Arthur Szlam, Emily Dinan, and Y-Lan Boureau. 2022.  Reducing conversational agents’ overconfidence through linguistic calibration.  _Transactions of the Association for Computational Linguistics_ , 10:857–872.
  * Min et al. (2023) Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen-tau Yih, Pang Wei Koh, Mohit Iyyer, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2023.  Factscore: Fine-grained atomic evaluation of factual precision in long form text generation.  _arXiv preprint arXiv:2305.14251_.
  * Muennighoff et al. (2023) Niklas Muennighoff, Thomas Wang, Lintang Sutawika, Adam Roberts, Stella Biderman, Teven Le Scao, M Saiful Bari, Sheng Shen, Zheng Xin Yong, Hailey Schoelkopf, Xiangru Tang, Dragomir Radev, Alham Fikri Aji, Khalid Almubarak, Samuel Albanie, Zaid Alyafeai, Albert Webson, Edward Raff, and Colin Raffel. 2023.  Crosslingual generalization through multitask finetuning.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 15991–16111, Toronto, Canada. Association for Computational Linguistics.
  * Nan et al. (2021) Feng Nan, Ramesh Nallapati, Zhiguo Wang, Cicero Nogueira dos Santos, Henghui Zhu, Dejiao Zhang, Kathleen McKeown, and Bing Xiang. 2021.  Entity-level factual consistency of abstractive text summarization.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2727–2733, Online. Association for Computational Linguistics.
  * Qiu et al. (2023) Yifu Qiu, Yftah Ziser, Anna Korhonen, Edoardo M Ponti, and Shay B Cohen. 2023.  Detecting and mitigating hallucinations in multilingual summarisation.  _arXiv preprint arXiv:2305.13632_.
  * Raunak et al. (2021) Vikas Raunak, Arul Menezes, and Marcin Junczys-Dowmunt. 2021.  The curious case of hallucinations in neural machine translation.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1172–1183, Online. Association for Computational Linguistics.
  * Varshney et al. (2023) Neeraj Varshney, Wenlin Yao, Hongming Zhang, Jianshu Chen, and Dong Yu. 2023.  A stitch in time saves nine: Detecting and mitigating hallucinations of llms by validating low-confidence generation.  _arXiv preprint arXiv:2307.03987_.
  * Workshop (2023) BigScience Workshop. 2023.  Bloom: A 176b-parameter open-access multilingual language model.
  * Xu et al. (2023) Weijia Xu, Sweta Agrawal, Eleftheria Briakou, Marianna J Martindale, and Marine Carpuat. 2023.  Understanding and detecting hallucinations in neural machine translation via model introspection.  _Transactions of the Association for Computational Linguistics_ , 11:546–564.
  * Zhang et al. (2023) Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. 2023.  Siren’s song in the ai ocean: A survey on hallucination in large language models.  _arXiv preprint arXiv:2309.01219_.

##  Appendix A Qualitative Analysis of Challenging Cases in Annotation

We identify four challenging categories of hallucination detection for
annotators and NLI metrics (Table 7).

  * •

Inferred: Implicit fact connections between generation and evidence.

  * •

Subjective: Generation contains subjective content, which is challenging for
both human annotators and fact-based NLI models.

  * •

Nuanced Difference: There are subtle distinctions between evidence and
generated text, which is often missed by surface-level text classification in
NLI models.

  * •

Temporal Information: Generation contains time-sensitive information, which
requires models to have an understanding of temporal context.

Type |  Example
---|---
Inferred |  Gen: Alessandro Del Piero is a former Italian professional football player and a forward. Wiki: Maldini, who was the head coach of the national team, appointed Del Piero as the main forward.
Subjective |  Gen: Frida Kahlo is widely regarded as the most influential painter of the 20th century.
Nuanced Difference |  Gen: Louis Pasteur is known as the ”Father of Modern Microbiology”. Wiki: … has been honored as the ”father of microbiology”…
Temporal Information |  Gen: Michelle Bachelet is currently the President of Chile. Wiki: She served as President of Chile from 2006 to 2010 and from 2014 to 2018…
Table 7: Categories of special case in annotation.

Each category presents unique difficulties in determining the factuality of
generated content with its evidence source.

  * •

Inferred connection between generated content and evidence is one of the
biggest challenges for both annotators and NLI models, since they need to
infer the relationship or the factual basis that links them. This requires a
deep understanding of context and the ability to draw inferences from
potentially sparse or indirect evidence.

  * •

Subjective content in generations poses a significant challenge because it
introduces personal opinions, emotions, or interpretations that are inherently
difficult to verify against factual evidence. For human annotators, this can
lead to variability in judgments based on personal biases or interpretations.
For NLI models, which are primarily designed for fact-based analysis, handling
subjective content requires advanced understanding of sentiment, opinion, and
cultural context, areas where current models may fall short.

  * •

Nuanced difference between evidence and generated text highlight the
limitations of surface-level text classification approaches in NLI models.
Detecting nuanced differences demands a granular analysis of semantics,
requiring models to understand context, synonyms, and slight variations in
meaning. This challenge underscores the need for more sophisticated NLI models
capable of deep semantic analysis and the importance of training annotators to
pay attention to detail and understand the significance of minor
discrepancies.

  * •

Time-sensitive information introduces complexity because it requires both
annotators and models to have an understanding of temporal context and the
ability to evaluate statements within the correct time frame. This can be
particularly challenging when information changes over time, requiring up-to-
date knowledge and the ability to discern the relevance of temporal qualifiers
in text. For NLI models, this underscores the need for dynamic knowledge bases
and the ability to reason about time, which are areas where current models may
lack proficiency.

Overall, these challenges highlight the complexities involved in hallucination
detection and the need for advanced capabilities in human annotators and NLI
models.

##  Appendix B Additional Results

We show the pairwise metric results in Table 9. We observe similar trends as
the reference-based metrics. Also, the average statistics of annotation result
are shown in Table 8.

Metric | Sent-Level | Atomic-Level
---|---|---
# Examples | 111 | 102
# Words | 46.21 | 10.21
# Evidence | 2.17 | 1.00
# Total Facts | 4.76 | 1.00
Support Rate | 0.35 | 0.29
Contradictory Rate | 0.15 | 0.24
Unverified Rate | 0.50 | 0.47
Instruction-conflict Rate | 0.03 | 0.07
Context-conflict Rate | 0.13 | 0.06
Table 8: Average statistics of Chinese and English annotation data.  Table 9: Results of different pairwise consistency metrics for the BLOOMZ-mt model. ”-” indicates they have no coverage for the NER tool we use. All of the ROUGE and Named Entity Overlap results are in percentage (%). Language | R1_F1 | R1_P | R1_R | R2_F1 | R2_P | R2_R | NEO_F1 | NEO_P | NEO_R | $\mathrm{DIFF}$ | $\mathrm{UNV}$
---|---|---|---|---|---|---|---|---|---|---|---
English | 12.03 | 14.21 | 14.71 | 5.91 | 7.10 | 7.37 | 4.27 | 53.41 | 2.26 | -0.25 | 0.57
Chinese | 7.57 | 8.56 | 8.55 | 4.00 | 4.55 | 4.55 | 4.69 | 35.28 | 2.79 | -0.29 | 0.57
Spanish | 12.49 | 14.45 | 15.05 | 6.21 | 7.31 | 7.68 | 3.28 | 48.48 | 1.76 | -0.22 | 0.52
German | 4.42 | 10.47 | 4.48 | 1.98 | 5.51 | 2.04 | 0.83 | 36.06 | 0.42 | -0.33 | 0.56
Russian | 0.15 | 0.19 | 0.13 | 0.00 | 0.00 | 0.00 | 0.48 | 11.28 | 0.25 | -0.09 | 0.55
Indonesian | 4.74 | 6.23 | 6.52 | 1.59 | 2.13 | 2.27 | - | - | - | -0.16 | 0.68
Vietnamese | 11.60 | 14.36 | 15.91 | 6.26 | 7.91 | 8.91 | - | - | - | -0.32 | 0.56
Persian | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | - | - | - | -0.31 | 0.52
Ukrainian | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.70 | 20.64 | 0.36 | 0.14 | 0.42
Swedish | 10.04 | 14.69 | 10.82 | 8.53 | 13.23 | 9.74 | 1.28 | 45.24 | 0.66 | -0.20 | 0.54
Thai | 0.01 | 0.02 | 0.01 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | -0.19 | 0.68
Japanese | 0.47 | 0.75 | 0.58 | 0.08 | 0.13 | 0.09 | 0.47 | 15.52 | 0.25 | -0.07 | 0.56
Romanian | 12.21 | 13.95 | 12.68 | 8.57 | 9.40 | 8.70 | 0.39 | 17.47 | 0.20 | -0.30 | 0.44
Hungarian | 0.18 | 0.25 | 0.46 | 0.00 | 0.00 | 0.00 | - | - | - | -0.18 | 0.58
Bulgarian | 0.30 | 0.44 | 0.28 | 0.05 | 0.08 | 0.06 | - | - | - | -0.02 | 0.96
French | 12.02 | 14.03 | 14.61 | 6.26 | 7.43 | 7.76 | 4.35 | 57.41 | 2.31 | -0.05 | 0.92
Finnish | 0.46 | 0.47 | 0.61 | 0.17 | 0.19 | 0.19 | 0.58 | 23.71 | 0.30 | -0.04 | 0.94
Korean | 0.19 | 0.26 | 0.17 | 0.00 | 0.00 | 0.00 | 0.24 | 8.48 | 0.12 | 0.25 | 0.63
Italian | 4.79 | 7.85 | 5.08 | 2.71 | 4.15 | 2.77 | 1.00 | 30.26 | 0.52 | -0.01 | 0.97

##  Appendix C Generation Prompt Templates

We present the full set of prompt templates for all languages from Section 3
in Figure 2.

Figure 2: Prompt templates of all languages used in generating biography. {}
represents human names.