# Influence of thermal effects on atomic Bloch oscillation

Guoling Yin  State Key Laboratory of Quantum Optics and Quantum Optics
Devices, Institute of Opto-Electronics, Shanxi University, Taiyuan 030006,
China  Chi-Kin Lai  State Key Laboratory of Advanced Optical Communication
Systems and Networks, School of Electronics, Peking University, Beijing
100871, China  Nana Chang  State Key Laboratory of Advanced Optical
Communication Systems and Networks, School of Electronics, Peking University,
Beijing 100871, China  Institute of Carbon-based Thin Film Electronics, Peking
University, Shanxi, Taiyuan 030012, China  Yi Liang  State Key Laboratory of
Advanced Optical Communication Systems and Networks, School of Electronics,
Peking University, Beijing 100871, China  Dekai Mao  State Key Laboratory of
Advanced Optical Communication Systems and Networks, School of Electronics,
Peking University, Beijing 100871, China  Xiaoji Zhou<EMAIL_ADDRESS>State
Key Laboratory of Quantum Optics and Quantum Optics Devices, Institute of
Opto-Electronics, Shanxi University, Taiyuan 030006, China  State Key
Laboratory of Advanced Optical Communication Systems and Networks, School of
Electronics, Peking University, Beijing 100871, China  Institute of Carbon-
based Thin Film Electronics, Peking University, Shanxi, Taiyuan 030012, China

###### Abstract

Advancements in the experimental toolbox of cold atoms have enabled the
meticulous control of atomic Bloch oscillation within optical lattices,
thereby enhancing the capabilities of gravity interferometers. This work
delves into the impact of thermal effects on Bloch oscillation in 1D
accelerated optical lattices aligned with gravity by varying the system’s
initial temperature. Through the application of Raman cooling, we effectively
reduce the longitudinal thermal effect, stabilizing the longitudinal coherence
length over the timescale of its lifetime. The atomic losses over multiple
Bloch oscillation is measured, which are primarily attributed to transverse
excitation. Furthermore, we identify two distinct inverse scaling behaviors in
the oscillation lifetime scaled by the corresponding density with respect to
temperatures, implying diverse equilibrium processes within or outside the
Bose-Einstein condensate regime. The competition between the system’s
coherence and atomic density leads to a relatively smooth variation in the
actual lifetime versus temperature. Our findings provide valuable insights
into the interaction between thermal effects and Bloch oscillation, offering
avenues for the refinement of quantum measurement technologies.

##  I Introduction

Atomic Bloch oscillation in optical lattices, manifesting as a dynamical
oscillatory response to constant force [1, 2], has become a robust tool for
quantum precision measurement. Compared with this phenomenon in solid-state
materials, where rapid electron-electron and electron-impurity scattering
sufficiently dampens the oscillation, optical lattices provide an impurity-
free platform for exploring Bloch oscillation [3, 4, 5, 6, 7, 8, 9]. The
advancement in laser cooling techniques for cold atoms further facilitates the
observation of the phenomenon by effectively loading atoms into optical
lattices, either with direct loading of a Bose-Einstein condensate (BEC) or
cold atoms combined with Raman cooling techniques [10, 11, 12, 13, 14], while
the former typically results in a denser atomic distribution where interaction
plays the important role.

The oscillation behavior in optical lattices can be achieved by aligning the
lattice along gravitational acceleration, providing a constant force that
drives the oscillatory dynamics [15, 7, 16, 17, 18]. This scheme can extend to
the measurement of local gravitational acceleration, $g$, through the
determination of the Bloch period $T_{\rm B}$ with ultracold atoms in optical
lattices [17, 19, 20]. Furthermore, these setups have been applied to direct
measurements of the gravitational constant, $G$ [21, 22, 23], the curvature of
the gravitational field in ultracold atom systems [24], the fine structure
constant [25, 26], and examination of the equivalence principle [27].
Moreover, the response of atoms to external force or acceleration also offers
potential for high-sensitivity force measurements [28], Alternatively, the
oscillation can be driven by inducing an inertial force on the atoms through
the acceleration of the optical lattice [3, 4, 29, 30]. In such acceleration-
driven scenarios, atoms in different bands exhibit opposite group velocities,
$v_{g}$ [31], and the adiabaticity may be constrained by a time bound that
depends on the lattice’s acceleration [32].

Some studies have proposed utilizing Bloch oscillation in both acceleration-
driven and gravity-driven setups to potentially enhance gravity interferometer
capabilities [33, 34, 35, 36, 37], as the elongated path for atoms to fall
freely leads to an extended interrogation time. However, the detailed thermal
effects on these interferometers, which significantly affect their
performance, have been less demonstrated. The exploration and understanding of
the underlying thermal behaviors are critical, as they can substantially
improve the sensitivity and accuracy of quantum precision measurements.

In this paper, we study Bloch oscillation in optical lattices driven by both
gravity and acceleration, for atoms at different temperatures. Through
systematic measurements of Bloch oscillation, we measure the coherence aligned
with the lattice at different initial temperatures, indicating that the
longitudinal coherence length extends for several lattice sites after applying
the Raman cooling technique, and remains stable when increasing the evolution
time in the lattice. The constant longitudinal coherence suggests the decay
mechanism of Bloch oscillation is primarily linked to transverse excitation
within the lattice. The measured lifetime of Bloch oscillation reveals an
unexpected upward trend at different initial temperatures of the system,
whereas the lifetime scaled by the average atomic density exhibits two
distinct scaling against temperature, implying the varied thermal dynamics for
atoms within or outside the BEC regime.

The structure of this paper is as follows. In Sec. II, we outline the
theoretical model for Bloch oscillation under both gravity and acceleration-
driven conditions. In Sec. III, we provide a comprehensive overview of the
experimental setup and elucidate the process of Bloch oscillation within a 1D
accelerated optical lattice. Experimental results, including observations of
the stable longitudinal coherence length in Bloch oscillation and atomic
lifetime of the oscillation relative to system temperature, are presented in
Sec. IV and Sec. V. We give a conclusion of our findings in Sec. VI.

##  II Theoretical model

In an optical lattice system, we can modulate the frequency difference between
two incident beams, resulting in the movement of the lattice. If the frequency
difference is modulated by a constant acceleration $\alpha$, the lattice will
be accelerated and move along the direction of the lattice. For our
experiment, the lattice aligns with the direction of gravitational
acceleration, $g$, leading to a gradient potential $-mg\hat{x}$ along the
lattice, as shown in Fig. 1(a). Thus, the one dimensional Hamiltonian in the
lab frame reads

$\displaystyle\hat{H}^{\rm
lab}=\frac{\hat{p}^{2}}{2m}+V_{0}\sin^{2}\left[k\left(x-\frac{1}{2}\alpha
t^{2}\right)\right]-mg\hat{x},$ (1)

where $V_{0}$ is the lattice depth, $k=\pi/d$ is the wave vector, $d$ is the
lattice constant, $m$ is the atomic mass, and $\hat{p}$ is the momentum
operator.

Figure 1: Experimental setup for both acceleration and gravity-driven Bloch
oscillation. (a) Longitudinal movement of atoms in the 1D accelerated optical
lattices under gravity, illustrating the periodic potential aligned with
gravity in $x$-axis, depicted as a black arrow, and atoms with a pancake-shape
spatial distribution. The acceleration of the optical lattice is achieved by
modulating the frequency difference $\delta\omega=k\alpha t$ between the two
lattice beams, as indicated by the two red arrows. In the co-moving frame,
atoms are subject to a net force $m(g-\alpha)$. The longitudinal length
$l_{\parallel}$ and lattice constant $d$ are displayed in the figure. (b)
Schematic diagram of the setup, illustrating the atoms are prepared within a
crossed 1064 nm optical dipole trap. It highlights the Raman and lattice beams
in the vertical direction, including the counter-propagating configuration
achieved by reflecting one of the Raman beams. The downward lattice beam is
combined with Raman beams in the same optical fiber, while upward lattice
beams are merged with one Raman beam using a polarizing beam splitter (PBS)
and two half-wave plates (HWP).

Considering the physical equivalence across different frames, analyzing in the
co-moving frame is more convenient. In this frame, atoms experience an
inertial force $-m\alpha$, which leads to the Hamiltonian:

$\displaystyle\hat{H}^{\rm
cm}=\frac{\hat{p}^{2}}{2m}+V_{0}\sin^{2}(kx)-m(g-\alpha)\hat{x}.$ (2)

To further analyse, we employ a unitary transformation:

$\displaystyle\hat{U}(t)=\exp\left(-\frac{\mathrm{i}}{\hbar}p_{0}(t)\hat{x}\right),$
(3)

where $p_{0}(t)=m(g-\alpha)t$. After the transformation, the Hamiltonian
becomes

$\displaystyle\tilde{H}^{\rm cm}=\frac{[\hat{p}+\hbar
q(t)]^{2}}{2m}+V_{0}\sin^{2}(kx),$ (4)

where $q(t)=m(g-\alpha)t/\hbar$ is the quasimomentum in co-moving frame. This
quasimomentum increases linearly under the constant acceleration $g-\alpha$,
until it reaches the boundary of the first Brillouin zone, where Bragg
scattering results in a change in quasimomentum by $2\hbar k$. In contrast,
the momentum of atoms after $n$ times Bragg scattering occurrence is given by
$p(t)=q(t)+2n\hbar k$.

The group velocity oscillation corresponding to the ground state,
instantaneous S band, in the co-moving frame is given by:

$\displaystyle v^{\rm cm}_{\rm g}(t)=\frac{1}{\hbar}\frac{\partial
E(q)}{\partial q}=\frac{2Jd}{\hbar}\sin\left(\frac{2\pi t}{T_{\rm B}}\right),$
(5)

with $E(q)=-2J\cos(qd)$ representing the energy dispersion of the $S$ band
under the tight-binding limit and $J$ being the nearest neighbor tunneling of
the S band. The Bloch period $T_{\rm B}$ is given by:

$\displaystyle T_{\rm B}=\frac{2\pi\hbar}{m|g-\alpha|d}.$ (6)

Furthermore, the group velocity of atoms in the lab frame can be obtained
through Galilean transformation, i.e., $v^{\rm lab}_{\rm g}(t)=v^{\rm cm}_{\rm
g}(t)+\alpha t$.

##  III Experimental demonstration of both gravity and acceleration driven
Bloch oscillation

Figure 2: Experimental sequence for the accelerated optical lattice. (a)
Initial state preparation begins at $t_{0}$ with atoms in $\ket{F=1}$. At
$t_{1}$, a microwave pulse transitions atoms to $\ket{F=2,m_{F}=0}$, while
atoms still in $\ket{F=1}$ are removed using a state-specific clear beam. The
first Raman pulse at $t_{2}$ narrows the velocity distribution and transfers
atoms to $\ket{F=1,m_{F}=0}$. Any remaining atoms in $\ket{F=2}$ are then
cleared. The optical lattice operation commences from $t_{3}$ to $t_{4}$,
ending with a second Raman pulse at $t_{5}$ for velocity measurement by
transferring resonant atoms to $\ket{F=2,m_{F}=0}$, followed by fluorescence
detection at $t_{6}$. (b) The sequence for the accelerated optical lattice is
detailed further: The lattice depth is linearly increased to $V_{0}=15$ Er
within $t_{\rm rise}=1$ ms and is maintained during $t_{\rm hold}$. Phase
modulation initiates by synchronizing the lattice’s velocity with the atoms’
free fall, adjusting the lattice frequency difference $\delta\omega$ at a rate
of $kg$. To induce Bloch oscillation, $\delta\omega$ is modulated at a rate
corresponding to $\alpha=-2g$. Finally, $\delta\omega$ is adjusted at a rate
of $kg$ to ensure zero relative velocity between the lattice and the atoms,
facilitating mapping of the atoms’ states into quasimomentum space. Figure 3:
Bloch oscillation process in the co-moving frame. (a) Illustration of Bloch
oscillation (BO) driven by a constant acceleration $g-\alpha$ in the co-moving
frame, showing atoms initially in the ground state ($q=0$ at the instantaneous
S band). Subject to a constant force $F=m(g-\alpha)$, the atoms’ quasimomentum
increases linearly until reaching the boundary of the first Brillouin zone.
This induces Bragg scattering, resulting in quasimomentum shifts of $2\hbar
k$. The BO process is depicted by black dashed arrows for the trajectory and
red ellipses for atoms, corresponding to the momentum distribution of atoms at
holding time: (A) $t_{\rm hold}=0$, (B) $t_{\rm hold}=T_{\rm B}/4=99\ \mu s$,
(C) $t_{\rm hold}=T_{\rm B}/2=198\ \mu s$.

Our experiment is carried out in a 1D accelerated optical lattice aligned with
the gravitational acceleration. Initially, we prepare approximately $1\times
10^{5}$ 87Rb atoms in $\ket{F=1}$ state, which is confined in the crossed 1064
nm optical dipole trap, as depicted in Fig. 1(b). The typical temperature of
the system is 50 nK corresponds to harmonic trapping frequencies of
$2\pi\times(29,29,41)$ Hz, which can be adjusted by altering the evaporation
cooling parameters. Additionally, the system’s initial temperature is
determined through absorption imaging after a 20 ms time-of-flight (TOF). The
critical temperature of the BEC phase transition, $T_{c}$, is around 200 nK.
Upon switching off the optical dipole trap, the atoms fall freely. As
illustrated in Fig. 2(a), the microwave pulse transfers atoms to
$\ket{F=2,m_{F}=0}$, and the atoms remaining in $\ket{F=1}$ state are blown by
$\ket{F=1}$ state clear beam. The Raman pulse, composed of two beams with a
frequency difference of $6.8$ GHz, drives the Raman transition and selects a
narrow velocity range of atoms. This process effectively limits the momentum
broadening, $\delta q$, in the direction of the standing wave. The atomic
state also transitions to $\ket{F=1,m_{F}=0}$ following the Raman pulse.
Subsequently, the $\ket{F=2}$ state clear beam blows the atom remaining in
$\ket{F=2}$. These processes not only transfer the atoms in a single $m_{F}$
state, but also ensure the momentum distribution is narrower than the first
Brillouin zone, thereby effectively loading atoms into the optical lattice.
The lattice itself is generated by two counter-propagating laser beams, with
the frequency blue-detuned by $40~{}\mathrm{GHz}$ from the atomic transitions
($\lambda=780.233~{}\mathrm{nm}$), minimizing the heating effect. Then, by
modulating the frequency difference, $\delta\omega$, between the two lattice
beams, the optical lattice is accelerated to load the atoms, achieve Bloch
oscillation (BO), and map the atomic states into quasimomentum space. Finally,
the atoms’ quasimomentum distribution is analyzed by applying the second Raman
pulse. Through sweeping the frequency of this pulse, the atoms with
quasimomentum $q$ are resonant to the Raman frequency of $\omega=k_{\rm
eff}q/m$, where $k_{\rm eff}=2k$ is the effective wave vector caused by the
counter-propagating Raman beams. In the meanwhile, the resonant atoms with
state $\ket{F=1,m_{F}=0}$ transition to $\ket{F=2,m_{F}=0}$. Therefore, the
atoms’ quasimomentum distribution, $f(q)$, can be delineated by the signal
defined as $N_{2}/(N_{1}+N_{2})$, where $N_{i}$ represents the atomic number
in $\ket{F=i,m_{F}=0}$ state. The BO signal is measured through fluorescence
detection following a 160 ms free fall until reaching the observation region.

The experimental sequence for the accelerated optical lattice, depicted in
Fig. 2(b), is detailed as follows. Our method involves initially loading the
atoms into the ground state of the moving periodic potential, namely, the
instantaneous S band. To achieve this, the optical lattice is switched on by
linearly increasing the lattice depth to 15 Er (Er denotes the recoil energy),
which satisfies the tight-binding condition, over a rise time of
$1~{}\mathrm{ms}$ [4]. Concurrently, the frequency difference $\delta\omega$
between the two laser beams is modulated linearly via two acousto-optic
modulators (AOM) at a constant rate of
$\frac{\mathrm{d}\delta\omega}{\mathrm{d}t}=k\alpha=kg$, altering the lattice
phase by $kgt^{2}/2$. This modulation enables the lattice to synchronize with
the velocity of the freely falling atoms and adiabatically load them into the
instantaneous S band. During this stage, BO does not occur due to the absence
of relative acceleration between the atoms and the lattice. After the loading
process, the lattice’s acceleration is set to $\alpha=-2g$, allowing the atoms
to ascend within the lattice, with their states evolving during the holding
time $t_{\rm hold}$. In the co-moving frame, atoms are subjected to the
combination of inertial force and gravity with $F=m(g-\alpha)=3mg$. Thus, BO
is driven by a constant acceleration of $3g$. The BO process is observed by
varying $t_{\rm hold}$ within the optical lattice. Subsequently, the lattice
beams are linearly switched off over a $1~{}\mathrm{ms}$ duration, while
simultaneously modulating $\delta\omega$ at a rate of $kg$ to maintain zero
relative velocity between the lattice and the atoms. In this process, atoms
populated in the instantaneous $S$ band are mapped to the first Brillouin
zone. Therefore, the atoms’ quasimomentum distribution can be measured after
band mapping.

Fig. 3(a) illustrates the Bloch oscillation process of atoms within the first
Brillouin zone at a lattice depth of $V_{0}=15$ Er, where the energy gap
between the $S$ and $P$ bands is $6.3$ Er, effectively suppressing Landau-
Zener tunneling. Initially, atoms are loaded into the ground state. Subject to
a constant external force in the co-moving frame, the atoms’ quasimomentum
linearly increases until it reaches the boundary of the first Brillouin zone.
At this point, Bragg scattering propels the atoms to the opposite zone
boundary, initiating a periodic motion as their quasimomentum continues to
increase and cyclically returns to the starting point. Experimental
observations of the Bloch oscillation process for various holding times
$t_{\rm hold}$ are presented in Fig. 3(b). At $t_{\text{hold}}=0$, atoms
predominantly distribute around $q=0$. As $t_{\rm hold}$ extends, the atoms’
quasimomentum linearly increases as a response of the constant force. At
$t_{\rm hold}=98\ \rm\mu s$, the atoms’ quasimomentum distribution peaks at
$q=0.5\hbar k$, and the central peak of the distribution slightly decreases as
atoms start to appear $2\hbar k$ away from $0.5\hbar k$. At
$t_{\text{hold}}=198\ \rm\mu s$, two symmetrical peaks positioning at
$q=\pm\hbar k$ are observed, indicating Bragg scattering which occurs at
$t_{\rm hold}=T_{\rm B}/2$. Thus, the Bloch period $T_{\rm B}$ is determined
to be $396\ \rm\mu s$, which coincides with the oscillation period driven by a
constant force of $3mg$, as anticipated by the theoretical model.

##  IV Coherence analysis of Bloch oscillation along the optical lattice

Figure 4: Fitting of the Bloch oscillation (BO) signal. Extraction of the
quasimomentum distribution, $f(q)$, from the raw data (black dots) by fitting
with a Lorentzian profile (blue solid line) at $t_{\rm hold}=30T_{\rm B}$. The
BO signal (light-blue solid line) is obtained by subtracting the fitted
offset. The center of the signal, $q=0$, corresponds to a momentum amount of
$2n\hbar k$ after $n$ occurrences of BO, and the central peak $f_{c}$ is
denoted by a black arrow. The momentum broadening, $\delta q$, is extracted
from the signal’s full width at half maximum (FWHM). Figure 5: Measurement of
the longitudinal coherence length. (a) The longitudinal coherence length,
$l_{\parallel}$, for various initial temperatures, remains largely constant
across increasing holding times, $t_{\rm hold}$, for atoms at 50 nK (green
squares) and 500 nK (orange diamonds). The error bar represents the standard
deviation of three repeated measurements. (b) The mean longitudinal coherence
length, $\overline{l_{\parallel}}$, depicted as a function of initial
temperature, shows data for atoms below (purple circles) and above (magenta
triangles) the critical temperature $T_{c}$, averaged across various $t_{\rm
hold}$ periods. Error bars indicate the corresponding standard deviations.

The longitudinal movement of atoms along the optical lattice ($x$-axis) can be
effectively captured by the above theoretical model, particularly after
applying Raman pulse aligned with the lattice. The pulse narrows the momentum
broadening $\delta q$ along the lattice direction, serving as a cooling method
to reduce the system’s temperature. Consequently, the thermal effects in the
longitudinal direction are significantly suppressed, leading to the
enhancement of coherence of the system.

To systematically analyse the coherence along the lattice, we measure the
Bloch oscillation (BO) signal after multiple times of $T_{\rm B}$, and analyse
the underlying coherence. Fig. 4 displays the fitting process from typical BO
signal for $t_{\rm hold}=30T_{\rm B}$. This signal, corresponding to the
quasimomentum distribution $f(q)$, is analyzed by fitting it to a Lorentzian
profile:

$\displaystyle f(q)=\frac{A}{(q-q_{0})^{2}+(\delta q/2)^{2}}+B,$ (7)

where $\delta q$ denotes the momentum broadening, $q_{0}$ is the center of the
quasimomentum peak, $A$ is the amplitude, and $B$ is the signal offset,
corresponding to the incoherent fraction of atoms. The central peak of the
quasimomentum distribution, $f_{c}=f(q_{0})-B$, represents the atomic
occupancy at the quasimomentum state $q_{0}$. When $t_{\rm hold}=nT_{\rm B}$,
where $n$ is an integer, the distribution’s peak occurs at $q_{0}=0$. This
peak corresponds to a physical momentum of $p=2n\hbar k$, indicating the
atoms’ return to their initial quasimomentum state after completing $n$ cycles
of Bloch oscillation.

By adjusting the initial temperature of the system, we measure the
longitudinal coherence length $l_{\parallel}=h/\delta q$ over various $t_{\rm
hold}$ durations, as shown in Fig. 5(a). To ensure statistical reliability,
each $l_{\parallel}$ value is measured three times, from which the mean and
standard deviation are calculated. These observations indicate that
$l_{\parallel}$ remains stable throughout the evolution in the optical
lattice, up to a holding time of $t_{\rm hold}=180T_{\rm B}$. This stability,
observed in both the situation of atoms at $50$ nK and $500$ nK, underscores
the effectiveness of Raman cooling in suppressing thermal effects along the
lattice for different initial states, suggesting the coherence of atoms is not
disrupted in the Bloch oscillation process. The mean longitudinal coherence
length $\overline{l_{\parallel}}$, averaged over various holding times, is
plotted as a function of the initial temperature in Fig. 5(b). A slight
decrease in coherence length with rising temperature is observed, which can be
attributed to the diluter atomic cloud before BEC formation, where Raman
cooling becomes less effective above the critical temperature. However, the
longitudinal coherence length reaches approximately four times the lattice
constant, $d$, implying substantial long-range correlation aligned with the
lattice.

##  V Atomic lifetime of Bloch oscillation at different initial temperature

In a one-dimensional optical lattice, especially within a deep lattice where
$V_{0}>10\,\text{Er}$, atoms typically form a pancake-shaped distribution,
with tunneling along the lattice direction significantly suppressed.
Collisions of atoms mainly occur in the plane perpendicular to the lattice
($y-z$ plane), making transverse movement the principal factor in the decay
mechanism. Consequently, transverse excitation leads to the damping of Bloch
oscillation, with atoms potentially scattering out of the lattice’s pancake-
shaped distribution. The maintained coherence in the longitudinal direction
further suggests that the reduction of the central peak $f_{\rm c}$ in the
quasimomentum distribution over multiples of BO is primarily due to atomic
losses in the transverse, unconfined direction, underscoring transverse
excitation as the key decay mechanism. The direct observation of transverse
momentum distribution, especially in a setup involving a free-falling and
ascending process, is challenging. Nonetheless, the depletion in $f_{\rm c}$
over $t_{\rm hold}$ reveals the significance of the decay mechanism.

Figure 6: Evaluation of Bloch oscillation lifetime. Lifetime values are
derived from the central peak, $f_{c}$, of the quasimomentum distribution for
various holding times, $t_{\rm hold}$. Data points for atoms at 50 nK (purple
circles) are normalized to the value at $t_{\rm hold}=0$. Error bars denote
the standard deviation from three independent measurements. The calculated
lifetime, $\tau$, is indicated by the point where a black dashed line at
$\exp(-1)$ intersects the solid purple fitting curve. Figure 7: Lifetimes of
BO at varying initial temperatures. (a) Lifetimes of BO across different
temperatures for atoms below (purple circles) and above (magenta triangles)
the critical temperature, $T_{c}$, with an upward trend highlighted by a black
dashed guideline. Error bars correspond to fitting uncertainties. (b) Scaled
lifetimes of Bloch oscillation, normalized by the initial average density
$\overline{\rho}$ (illustrated in the inset), exhibit two distinct $T^{-1}$
scaling behaviors for conditions within and outside the BEC regime, depicted
by purple ($T<T_{c}$) and magenta ($T>T_{c}$) dashed lines, respectively.
Error bars are calculated by combining fitting uncertainties in $\tau$ with
the standard deviation of $\overline{\rho}$ from three measurements.

To systematically investigate the decay process of BO, we set
$t_{\text{hold}}=nT_{\text{B}}$ and examine how the lifetime varies with
atoms’ initial temperature. Fig. 6 displays the lifetime fitting for the BO
signal of atoms at 50 nK with the function

$\displaystyle f_{\rm c}(t)=f_{\rm c}(0)\exp(-t/\tau),$ (8)

where $\tau$ is the BO lifetime. For system’s initial temperature of 50 nK,
the lifetime is calculated as $\tau=73.2\pm 8.0$ ms, corresponding to
approximately 185 $T_{\rm B}$. Fig. 7(a) shows a counter-intuitive increase in
BO lifetime versus system’s initial temperature. The atomic lifetime of a
driven one-dimensional optical lattice typically follows the relationship
$\tau\propto\rho^{-1}$, where $\rho$ is the atomic density [38]. Thus, we
measure the initial average atomic density $\overline{\rho}$ of the system
across temperatures through absorption imaging. Notably, atoms at different
temperatures generally show a large discrepancy in atomic density across the
BEC phase transition; for instance, the density of atoms at 50 nK is roughly
an order of magnitude higher than that of atoms at 500 nK, significantly
influencing the atomic lifetime. To exclude the impact of atomic density, we
scale the measured lifetime $\tau$ with the corresponding average atomic
density $\overline{\rho}$ at different temperatures, as illustrated in Fig.
7(b). The scaled lifetime, indicative of the system’s coherence after
excluding scattering-induced decay, exhibits two distinct inverse scaling
behaviors, represented by $T^{-1}$. This distinction implies dissimilar
thermal dynamics among cold atoms with different temperatures subsequent to
Raman cooling.

The counter-intuitive increase in lifetime with temperature, alongside
divergent scaling behaviors, shows unexpected phenomena. These can be
attributed to two primary factors. Firstly, the equilibrium state of atoms at
$T<T_{c}$ is established through thermal exchange between the core BEC atoms
and the surrounding non-condensed atoms, which are in different phases. In
contrast, the equilibrium process for atoms at $T>T_{c}$ occurs within a
single phase. This fundamental difference in how equilibrium is reached
introduces disparate dynamics as the systems approach their final temperatures
$T^{*}$ following Raman cooling, significantly influencing the system’s
coherence. As a result, the scaled lifetime with respect to initial
temperature displays two different scaling. Secondly, while the direct
measurement of BO lifetime exhibits a gradual increase with temperature, both
the density and the scaled lifetime display a sharp transition at $T=200$ nK,
where the BEC phase transition occurs. The interplay between atomic spatial
distribution and the equilibrium process contributes to a relatively smooth
shift in lifetime across the critical temperature. In other words, the abrupt
transitions in both density and scaled lifetime linked to coherence
counterbalance each other, resulting in a gradual increase in the physical
lifetime with temperature. Nonetheless, these results leave room for more
profound theoretical examination and detailed system modeling.

##  VI Conclusion

In summary, we observe Bloch oscillation in 1D accelerated optical lattices
along the gravity, spanning atoms with different temperatures. We demonstrate
that Raman cooling effectively reduces longitudinal thermal effects,
maintaining the stable longitudinal coherence length. Therefore, we attribute
the observed atomic losses primarily to the transverse, unconstrained
direction, caused by transverse excitation. Interestingly, while the lifetime
of Bloch oscillation gradually increases with temperature, the lifetime scaled
by density reveals two unique inverse scaling. This phenomenon demonstrates
the significance of the equilibrium process in the decay mechanisms of Bloch
oscillation and points to the intricate relationship between thermal dynamics
and atomic density distribution. Our experimental results suggest that while a
BEC offers a more suitable environment for exploring lattice dynamics and
quantum simulations due to its enhanced coherence compared to non-condensed
atoms. However, in certain situations, non-condensed atoms may offer
advantages for quantum precision measurements due to their potentially longer
lifetimes. These discoveries not only deepen our understanding of thermal
effects in ultracold atoms systems but also pave the way for advancements in
quantum measurement technologies.

## Acknowledgements

The authors would like to thank Z. Yu and L. Kong for useful discussions. This
work is supported by the National Key Research and Development Program of
China (Grant Nos. 2021YFA0718300 and 2021YFA1400900), the National Natural
Science Foundation of China (Grant Nos. 11920101004, 11934002, and 92365208),
Science and Technology Major Project of Shanxi (Grant No. 202101030201022),
and Space Application System of China Manned Space Program.

## References

  * Bloch [1929] F. Bloch, Zeitschrift für physik 52, 555 (1929), URL https://link.springer.com/article/10.1007/BF01339455.
  * Zener [1934] C. Zener, Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character 145, 523 (1934), URL https://doi.org/10.1098/rspa.1934.0116.
  * Ben Dahan et al. [1996] M. Ben Dahan, E. Peik, J. Reichel, Y. Castin, and C. Salomon, Phys. Rev. Lett. 76, 4508 (1996), URL https://link.aps.org/doi/10.1103/PhysRevLett.76.4508.
  * Peik et al. [1997] E. Peik, M. Ben Dahan, I. Bouchoule, Y. Castin, and C. Salomon, Phys. Rev. A 55, 2989 (1997), URL https://link.aps.org/doi/10.1103/PhysRevA.55.2989.
  * Morsch et al. [2001] O. Morsch, J. H. Müller, M. Cristiani, D. Ciampini, and E. Arimondo, Phys. Rev. Lett. 87, 140402 (2001), URL https://link.aps.org/doi/10.1103/PhysRevLett.87.140402.
  * Hartmann et al. [2004] T. Hartmann, F. Keck, H. J. Korsch, and S. Mossmann, New Journal of Physics 6, 2 (2004), URL https://dx.doi.org/10.1088/1367-2630/6/1/002.
  * Gustavsson et al. [2008] M. Gustavsson, E. Haller, M. J. Mark, J. G. Danzl, G. Rojas-Kopeinig, and H.-C. Nägerl, Phys. Rev. Lett. 100, 080404 (2008), URL https://link.aps.org/doi/10.1103/PhysRevLett.100.080404.
  * Choi and Niu [1999] D.-I. Choi and Q. Niu, Phys. Rev. Lett. 82, 2022 (1999), URL https://link.aps.org/doi/10.1103/PhysRevLett.82.2022.
  * Raizen et al. [1997] M. Raizen, C. Salomon, and Q. Niu, Physics Today 50, 30 (1997), ISSN 0031-9228, URL https://doi.org/10.1063/1.881845.
  * Anderson et al. [1995] M. H. Anderson, J. R. Ensher, M. R. Matthews, C. E. Wieman, and E. A. Cornell, Science 269, 198 (1995), URL https://www.science.org/doi/abs/10.1126/science.269.5221.198.
  * Davis et al. [1995] K. B. Davis, M. O. Mewes, M. R. Andrews, N. J. van Druten, D. S. Durfee, D. M. Kurn, and W. Ketterle, Phys. Rev. Lett. 75, 3969 (1995), URL https://link.aps.org/doi/10.1103/PhysRevLett.75.3969.
  * Kasevich and Chu [1992] M. Kasevich and S. Chu, Phys. Rev. Lett. 69, 1741 (1992), URL https://link.aps.org/doi/10.1103/PhysRevLett.69.1741.
  * Reichel et al. [1995] J. Reichel, F. Bardou, M. B. Dahan, E. Peik, S. Rand, C. Salomon, and C. Cohen-Tannoudji, Phys. Rev. Lett. 75, 4575 (1995), URL https://link.aps.org/doi/10.1103/PhysRevLett.75.4575.
  * Boyer et al. [2004] V. Boyer, L. J. Lising, S. L. Rolston, and W. D. Phillips, Phys. Rev. A 70, 043405 (2004), URL https://link.aps.org/doi/10.1103/PhysRevA.70.043405.
  * Modugno et al. [2004] G. Modugno, E. de Mirandés, F. Ferlaino, H. Ott, G. Roati, and M. Inguscio, Fortschritte der Physik 52 (2004), URL https://api.semanticscholar.org/CorpusID:15240958.
  * Roati et al. [2004] G. Roati, E. de Mirandes, F. Ferlaino, H. Ott, G. Modugno, and M. Inguscio, Phys. Rev. Lett. 92, 230402 (2004), URL https://link.aps.org/doi/10.1103/PhysRevLett.92.230402.
  * Ferrari et al. [2006] G. Ferrari, N. Poli, F. Sorrentino, and G. M. Tino, Phys. Rev. Lett. 97, 060402 (2006), URL https://link.aps.org/doi/10.1103/PhysRevLett.97.060402.
  * Xu et al. [2019] V. Xu, M. Jaffe, C. D. Panda, S. L. Kristensen, L. W. Clark, and H. Müller, Science 366, 745 (2019), URL https://www.science.org/doi/abs/10.1126/science.aay6428.
  * Cladé et al. [2005] P. Cladé, S. Guellati-Khélifa, C. Schwob, F. Nez, L. Julien, and F. Biraben, Europhysics Letters 71, 730 (2005), URL https://iopscience.iop.org/article/10.1209/epl/i2005-10163-6.
  * Poli et al. [2011] N. Poli, F.-Y. Wang, M. G. Tarallo, A. Alberti, M. Prevedelli, and G. M. Tino, Phys. Rev. Lett. 106, 038501 (2011), URL https://link.aps.org/doi/10.1103/PhysRevLett.106.038501.
  * Rosi et al. [2014] G. Rosi, F. Sorrentino, L. Cacciapuoti, M. Prevedelli, and G. Tino, Nature 510, 518 (2014), URL https://www.nature.com/articles/nature13433.
  * Tino [2021] G. M. Tino, Quantum Science and Technology 6, 024014 (2021), URL https://dx.doi.org/10.1088/2058-9565/abd83e.
  * Fixler et al. [2007] J. B. Fixler, G. T. Foster, J. M. McGuirk, and M. A. Kasevich, Science 315, 74 (2007), URL https://www.science.org/doi/abs/10.1126/science.1135459.
  * Rosi et al. [2015] G. Rosi, L. Cacciapuoti, F. Sorrentino, M. Menchetti, M. Prevedelli, and G. M. Tino, Phys. Rev. Lett. 114, 013001 (2015), URL https://link.aps.org/doi/10.1103/PhysRevLett.114.013001.
  * Cladé et al. [2006] P. Cladé, E. de Mirandes, M. Cadoret, S. Guellati-Khélifa, C. Schwob, F. m. c. Nez, L. Julien, and F. m. c. Biraben, Phys. Rev. A 74, 052109 (2006), URL https://link.aps.org/doi/10.1103/PhysRevA.74.052109.
  * Parker et al. [2018] R. H. Parker, C. Yu, W. Zhong, B. Estey, and H. Müller, Science 360, 191 (2018), eprint https://www.science.org/doi/pdf/10.1126/science.aap7706, URL https://www.science.org/doi/abs/10.1126/science.aap7706.
  * Tarallo et al. [2014] M. G. Tarallo, T. Mazzoni, N. Poli, D. V. Sutyrin, X. Zhang, and G. M. Tino, Phys. Rev. Lett. 113, 023005 (2014), URL https://link.aps.org/doi/10.1103/PhysRevLett.113.023005.
  * Guo et al. [2022] X. Guo, Z. Yu, F. Wei, S. Jin, X. Chen, X. Li, X. Zhang, and X. Zhou, Science Bulletin 67, 2291 (2022), ISSN 2095-9273, URL https://www.sciencedirect.com/science/article/pii/S2095927322004881.
  * Berg-Sørensen and Mølmer [1998] K. Berg-Sørensen and K. Mølmer, Phys. Rev. A 58, 1480 (1998), URL https://link.aps.org/doi/10.1103/PhysRevA.58.1480.
  * Denschlag et al. [2002] J. H. Denschlag, J. E. Simsarian, H. Häffner, C. McKenzie, A. Browaeys, D. Cho, K. Helmerson, S. L. Rolston, and W. D. Phillips, Journal of Physics B: Atomic, Molecular and Optical Physics 35, 3095 (2002), URL https://dx.doi.org/10.1088/0953-4075/35/14/307.
  * Yu et al. [2023] Z. Yu, J. Tian, P. Peng, D. Mao, X. Chen, and X. Zhou, Phys. Rev. A 107, 023303 (2023), URL https://link.aps.org/doi/10.1103/PhysRevA.107.023303.
  * Yin et al. [2023] G. Yin, L. Kong, Z. Yu, J. Tian, X. Chen, and X. Zhou, Phys. Rev. A 108, 033310 (2023), URL https://link.aps.org/doi/10.1103/PhysRevA.108.033310.
  * Andia et al. [2013] M. Andia, R. Jannin, F. m. c. Nez, F. m. c. Biraben, S. Guellati-Khélifa, and P. Cladé, Phys. Rev. A 88, 031605 (2013), URL https://link.aps.org/doi/10.1103/PhysRevA.88.031605.
  * Cladé [2015] P. Cladé, La Rivista del Nuovo Cimento 38, 173 (2015), URL https://doi.org/10.1393/ncr/i2015-10111-3.
  * Charrière et al. [2012] R. Charrière, M. Cadoret, N. Zahzam, Y. Bidel, and A. Bresson, Phys. Rev. A 85, 013639 (2012), URL https://link.aps.org/doi/10.1103/PhysRevA.85.013639.
  * Bouchendira [2012] R. Bouchendira, Thèse de doctorat, Université Pierre et Marie Curie, Paris (2012), soutenue publiquement le 17 Juillet 2012.
  * Andia [2015] M. Andia, Thèse de doctorat, Université Pierre et Marie Curie, Paris (2015), soutenue le 25 septembre 2015.
  * Choudhury and Mueller [2015] S. Choudhury and E. J. Mueller, Phys. Rev. A 91, 023624 (2015), URL https://link.aps.org/doi/10.1103/PhysRevA.91.023624.


# CoDefeater: Using LLMs To Find Defeaters in Assurance Cases

Usman Gohar  Iowa State UniversityAmesIowaUSA<EMAIL_ADDRESS>,  Michael C.
Hunter  Iowa State University30 Shuangqing RdAmesIowaUSA<EMAIL_ADDRESS>,  Robyn R. Lutz  Iowa State University1 Thørväld CircleAmesIowaUSA
<EMAIL_ADDRESS>and  Myra B. Cohen  Iowa State UniversityAmesIowaUSA
<EMAIL_ADDRESS>
(2024)

###### Abstract.

Constructing assurance cases is a widely used, and sometimes required, process
toward demonstrating that safety-critical systems will operate safely in their
planned environment. To mitigate the risk of errors and missing edge cases,
the concept of defeaters - arguments or evidence that challenge claims in an
assurance case - has been introduced. Defeaters can provide timely detection
of weaknesses in the arguments, prompting further investigation and timely
mitigations. However, capturing defeaters relies on expert judgment,
experience, and creativity and must be done iteratively due to evolving
requirements and regulations. This new ideas paper proposes CoDefeater, an
automated process to leverage large language models (LLMs) for finding
defeaters. Initial results on two systems show that LLMs can efficiently find
known and unforeseen feasible defeaters to support safety analysts in
enhancing the completeness and confidence of assurance cases.

Assurance case, Large Language Models, Assurance defeaters, sUAS

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††ccs:
Software and its engineering Software safety††ccs: Computing methodologies
Artificial intelligence††ccs: Software and its engineering Requirements
analysis

##  1\. Introduction

Safety-critical systems have become deeply integrated into many societal
domains, including healthcare, transportation, energy, and aviation (47; 22;
33). Failures in these systems can lead to catastrophic consequences for human
safety, including fatalities and environmental and property damage (60). This
has led to an increased focus on their dependence, reliability, and safety
(58; 39). Many systems must comply with regulations (55; 10), provide evidence
of safety, and undergo rigorous certification processes (36; 54) for approval
from regulatory bodies. _Assurance cases_ (ACs) have emerged as a common
practice for this purpose, facilitating the verification of system correctness
and the validation of specific claims regarding safety, security, and
trustworthiness, among others (46; 8; 6).

Figure 1. Overview of CoDefeater.

An assurance case is a structured hierarchy of claims and arguments supported
by evidence that a system will function as intended in a specified environment
(61; 8). Several formal notations (e.g., Goal Structuring Notation (GSN) (37),
Claims-Arguments-Evidence (CAE) (2), and Eliminative Argumentation (EA) (29)),
along with tools (21; 65; 46), have been proposed. However, concerns arise
over their completeness, uncertainty, and soundness for cyber-physical
systems. (31; 25), leading to false confidence and catastrophic failures (64).
For example, failure of the minimum safe altitude warning system that led to a
major aviation accident was attributed to incomplete and flawed reasoning in
the safety case (32).

To enhance the robustness of assurance cases, it is critical to identify and
mitigate their _defeaters_ (also known as assurance weakeners). Defeaters
highlight gaps in evidence or reasoning that undermine the validity of claims
in the assurance case (34). An example of a defeater, drawn from the assurance
case for the safe operation of an sUAS (small Uncrewed Aircraft System)
battery, challenges the assurance case’s claim that “The sUAS has enough
battery charge to complete its mission.” The defeater casting doubt on this
claim is, “Unless the battery monitor is not calibrated/inaccurate.” The
defeater serves to record, within the assurance case itself, the analyst’s
challenge to the validity of the claim.

Various approaches have been proposed to identify and mitigate defeaters (30;
38). However, manually creating defeaters is a labor-intensive and time-
consuming process (52; 49), relying heavily on safety analysts’ judgment,
experience, creativity, and understanding of the system. This can lead to
confirmation bias (65; 7). As assurance cases evolve with new standards and
technological advances, ongoing efforts are focused on formal and semi-
automated approaches for detecting and managing defeaters (23; 41). Best
practices build assurance cases incrementally, so automating all/or part of
this process is important (68; 23).

Large Language Models (LLMs) are increasingly automating software engineering
tasks like test generation and defect detection (35; 3). In particular, these
models have become valuable in tasks requiring complex understanding, such as
vulnerability detection, requirements elicitation, and code generation (69;
17; 5). Moreover, LLMs have shown promise in automating evaluation tasks and
acting as surrogate evaluators (18; 70). Consequently, we explore whether
LLMs’ capabilities can be harnessed to automate defeater analysis towards the
completeness, soundness, and confidence of assurance cases. Despite calls for
more research into LLMs’ ability to identify defeaters (62; 66), no study has
been conducted to evaluate and investigate their effectiveness.

This new ideas paper presents the first empirical investigation of the
feasibility and utility of LLMs for identifying defeaters, using a process we
call _CoDefeater_. It evaluates their potential to aid practitioners and
safety analysts in the iterative human-in-the-loop process of finding
defeaters, as shown in Figure 1. We evaluate the performance of an LLM
(ChatGPT) in automated defeater analysis on two complex real-world case
studies. Our experimental results suggest that CoDefeater is a promising
approach for identifying and generating novel assurance case defeaters.
Overall, this work makes three key contributions. 1) To the best of our
knowledge, we provide the first empirical results from an investigation of the
effectiveness and usefulness of an LLM (GPT 3.5) in identifying and creating
defeaters for real-world assurance cases. 2) We provide a new assurance case
fragment with defeaters that can be leveraged for further research on
automated defeater identification techniques. 3). Based on our findings, we
outline current challenges and directions for future work. All experimental
artifacts are available here: https://gitlab.com/anonymousdot/codefeater.

##  2\. Background and Related Work

Assurance case arguments typically adopt an inductive approach, where sub-
claims offer direct evidence to support the parent claim but do not ensure it
with certainty (8; 13). Focusing solely on proving a claim may introduce
confirmation bias, as exemplified by the Nimrod aircraft crash (12). Recent
approaches have therefore embraced defeasible reasoning, which acknowledges
that arguments about system properties in practice are inherently defeasible
(28; 43; 57). Defeaters are potential doubts or objections that challenge the
validity of a claim, reflecting gaps in evidence and reasoning (28; 44; 25;
51). Figure 2 shows a fragment of an assurance case for an sUAS battery, with
examples of defeaters (red boxes).

Defeaters are typically represented using EA notation (29) but have also been
integrated into GSN and CAE notations (34; 8). Hence, this study does not aim
to evaluate LLMs’ performance in identifying defeaters in any specific
notation or semantic accuracy but rather to investigate the feasibility of
this approach. Finally, the indefeasibility criterion requires a thorough
search for defeaters in an assurance case (8), motivating our investigation
into LLMs’ potential to assist practitioners and safety analysts in
identifying and generating novel defeaters.

In software engineering, LLMs are increasingly employed to assist developers
and automate tasks such as discovering requirements, code generation, testing,
and program synthesis (35; 5). Diemert and Weber (24) have reported ChatGPT’s
effectiveness in hazard analysis for safety-critical systems, highlighting
their potential to assist human analysts. In the context of software assurance
cases, Sivakumar et al. (63) assessed LLM’s (GPT-4) proficiency in
understanding GSN representations and its performance in constructing safety
cases. Viger et al. (66) proposed using LLMs to identify defeaters; however,
they did not report an empirical evaluation of their capabilities.
Shahandashti et al. (62) explored LLM’s (GPT-4) understanding of EA notation
and defeater concepts, with empirical validation left as future work. We aim
to address this gap by examining LLM performance in identifying defeaters for
assurance cases in two case studies.

The Machine Learning (ML) community also has explored the reasoning abilities
of LLMs (71; 20; 67). This line of inquiry investigates how LLMs fare in open-
ended tasks and their effectiveness in assisting humans. Findings have
indicated that LLMs can demonstrate consistent responses exhibiting
similarities with human evaluations, suggesting their potential as automated
tools (18).

Figure 2. An Assurance Case fragment with three example defeaters for Claim
1.2.

##  3\. Methodology

We conducted a preliminary exploratory study toward answering the following
two research questions:

  * •

RQ1: (Effectiveness). How effective are LLMs in identifying and analyzing
defeaters in assurance cases?

  * •

RQ2: (Utility). Can LLMs support practitioners in generating novel and
meaningful defeaters?

###  3.1. Experimental Setup

Datasets. We performed our experiments on two assurance cases. The first is
for the CERN Large Hadron Collider (LHC) Machine Protection System (MPS),
which provides assurance that the MPS will prevent damage to the LHC from
unstable, high-energy particle beams (59; 50). The assurance case for the CERN
LHC uses EA notation, and we extracted claim nodes with their corresponding
defeaters for our experiments. The second assurance case is a fragment of a
larger one that our team has recently created for small Uncrewed Aircraft
Systems (sUAS)111Anonymized for submission using GSN. It addresses the claim
“the sUAS has enough charge in its battery to complete the mission” (see claim
1.2 in Figure 2). We include both the assurance case fragment and
corresponding defeaters in the supplementary
material222https://gitlab.com/anonymousdot/codefeater. The real-world
complexity of these systems and the availability of defeaters made them
suitable for our preliminary experiments. Table 1 provides a summary of the
assurance cases.

Model. We used ChatGPT (GPT-3.5) for our study, specifically model
_GPT-3.5-turbo_ released by Open AI (11).

Table 1. Number of claims and defeaters in the ACs. Node Type | LHC MPS | sUAS Battery
---|---|---
Claims | 61 | 6
Defeaters | 103 | 20

###  3.2. Prompt Design

An effective prompt design is crucial for achieving good performance, as the
choice of prompts significantly impacts the quality, relevance, and accuracy
of the LLM’s response (15). It involves crafting a system prompt to establish
the context and prepare the LLM for the task, along with a user prompt that
contains the specific task request (53). We designed the system prompt
following OpenAI’s best practices (53) and relevant literature in software
engineering (72; 14) and open-ended evaluation tasks (18). Our process
identified role-based system prompts (42) as the most effective approach.
Figure 3 shows the system prompt used in our study.

Several user prompting techniques have been proposed, e.g., zero-shot, one-
shot, few-shot, and chain-of-thought (15). Zero-shot learning involves
providing the model with only the task description (system prompt), without
examples of unseen tasks to learn from. In contrast, one-shot and few-shot
learning conditions the model on one or more examples in the prompt,
respectively (11).

For our preliminary study, we adopted the zero-shot learning setting. This
approach both (1) facilitates the immediate, off-the-shelf application of
LLMs, eliminating the need for computationally expensive fine-tuning
procedures, and (2) is naturally suited to scenarios such as ours, with
limited data availability for training or fine-tuning (40). Each prompt was
presented independently to the model to avoid influencing subsequent
responses, allowing us to assess its standalone capabilities (16).

Figure 3. The system prompt used in the study.

###  3.3. Evaluation Criteria

Due to the complexity and open-ended nature of the task (e.g., varying
response length vs. ground truth, and subjectivity), automatic evaluation
metrics were not suitable (18). Therefore, we relied on human evaluation for
assessing LLM performance. For RQ1, we used a deductive coding approach (45;
24), where the first two authors independently reviewed responses and
categorized them as complete match, partial match, or no match based on
similarity to ground-truth defeaters. We used the defeaters in the LHC
assurance case as the ground truth. For the battery assurance case, a set of
ground-truth defeaters was provided by one of the authors (independently)
familiar with the domain, following best practices (50). For RQ2, the
responses were evaluated for being reasonable (14), i.e., the defeater could
reasonably be in the ground truth but had been overlooked. This aimed to
assess the LLM’s capability to identify novel defeaters. Figure 4 shows an
example of each type of match. Next, the reviewers met to discuss and finalize
their assigned codes. In the case of post-discussion disagreement, if one
reviewer labeled a response as a partial match and the other as a complete
match, we categorized it as a partial match to avoid confirmation bias (26).
In the one instance where one reviewer indicated no match while the other
identified a partial or complete match, it was discarded. Last, we calculated
inter-rater agreement using Cohen’s Kappa (19) to evaluate the consistency and
reliability of the coding process.

Figure 4. A sample claim from the LHC assurance case, together with the
claim’s ground-truth defeaters (left) and LLM-generated (ChatGPT) defeaters
(right), color-coded to represent the level of agreement between the two:
complete match (green), partial match (blue), and no match (no color).

###  3.4. Threats to Validity

There is potential subjectivity in the qualitative evaluation of LLM
performance on defeater identification. To address that, two authors
independently coded the LLM responses, following best practices (9; 27), and
held multiple discussions to avoid misinterpretations. We also computed
Cohen’s kappa (19), which indicated substantial inter-reviewer agreement. To
avoid confirmation bias, disagreements were coded as partial or no match. The
non-deterministic nature of LLMs and different versions might produce slightly
different responses; however, we used a single version of ChatGPT. Finally,
the preliminary results presented here lead us to propose that the use of LLMs
to generate defeaters merits further work; however, generalizability awaits
larger studies with improved LLMs.

##  4\. Results

In this section, we present the key findings of our experiments, grouped by
our research questions.

###  4.1. (RQ1): Effectiveness in Identifying Defeaters

Finding 1: The LLM displayed promising zero-shot capabilities for defeater
analysis in assurance cases.

Figure 5 presents the results of our closed coding process, which assessed the
GPT-3.5 model’s performance in identifying defeaters for the two real-world
assurance cases in a zero-shot setting. Our experiments showed that the model
demonstrated unexpectedly good zero-shot capabilities for defeater analysis.
Specifically, it completely identified more than half of all defeaters and
partially identified more than a third in both datasets. Fewer than $15\%$ of
the defeaters created by human analysts were not identified at all by the LLM.
These results were noteworthy given the complexity of the systems under study
and the lack of system information, domain knowledge, or few-shot examples
provided to the LLM. Additionally, the total coded responses achieved high
inter-rater agreement, with a Cohen’s Kappa score of 0.81, (19; 48). Finally,
all of these defeaters were identified in the first prompt, illustrating the
convenience of the approach. Among the unidentified defeaters, some required
specific domain or system knowledge not provided to the model, indicating
areas for potential improvement.

Finding 2: The LLM struggled with defeaters that challenged implicit
assumptions.

We conducted a manual analysis of the unidentified defeaters (n = 17) to
investigate whether there were any patterns behind the LLM’s failure.
Interestingly, we found that the model struggled to identify those defeaters
that implicitly challenged the truth of an assumption. For example, for the
claim ”The BICs will not produce a FALSE BEAM-PERMIT to trigger a beam dump,
unless a loss of the high-frequency signal (10Mhz) in either Beam Permit Loop
(A and B) is detected...”, a (ground-truth) defeater in the LHC assurance case
questions the assumption that the 10Mhz signal is the right signal to monitor.
In other words, the presence of another similar high-frequency signal might
lead to a false indication of TRUE BEAM-PERMIT. Unlike the analysts, the LLM
did not question the underlying assumption in the claim and thus did not
identify the defeater. Consequently, future work should explore integrating
external knowledge sources since, in similar tasks, it significantly enhances
LLM’s performance (72; 56).

Figure 5. (Performance). Distribution of defeaters across coding categories.
Cohen’s kappa showed almost perfect agreement beyond chance.

###  4.2. (RQ2): Utility in Generating Novel Defeaters

To answer RQ2, we evaluated the LLM’s performance on the sUAS battery’s
assurance case, where we have the necessary domain knowledge. Using the same
prompting method, we iteratively requested additional defeaters to assess its
capacity to generate novel defeaters beyond the ones that had been identified
in the building of the assurance case.

Finding 3: LLMs can support practitioners in providing useful and novel
defeaters.

The LLM output was a useful source of five novel defeaters, each of which was
feasible upon further investigation using our evaluation criteria. These were:
(1) an unexpected power drain due to an onboard component failure; (2) an
emergency external to the sUAS that forced the sUAS into a longer flight; (3)
a missed waypoint to which the pilot had to return; (4) unexpected power drain
arising from ongoing efforts to recover a lost GPS; and (5) external
interference that the sUAS had to dodge repeatedly. The last one was
interesting to us because the LLM gave as an example of interference that
birds might attack the sUAS. This, in fact, happens quite often and is
dangerous (4). The response shows how an LLM can offer a creative perspective
that catches missing edge cases.

##  5\. Discussion

Based on our findings, we highlight several challenges and opportunities for
an LLM-based process to help find defeaters.

Designing better prompts. Prompt designing has been shown to significantly
impact LLM performance (42; 15). Many prompting methods have been proposed,
and further investigation for suitability to defeater analysis is needed.
Moreover, our study revealed that the LLM can generate creative, redundant,
and far-fetched scenarios (e.g., defeaters due to budget constraints).
Balancing LLM creativity with defeater relevance poses an important challenge.

Rationale behind defeaters.  In our experiments, we found that the LLM
responses not only identified defeaters but also provided helpful rationale
and examples. For instance, if the ground truth defeater stated, ”Unless there
are incorrect readings,” the LLM suggested, ”The sensors may not be properly
calibrated, leading to inaccurate readings.” These explanations can assist
analysts in understanding and analyzing both a defeater’s feasibility and its
potential mitigations. Investigating explainable prompting techniques such as
Chain-Of-Thought (15) is an important next step.

Towards incremental assurance using LLMs. Our study focused on single claims
and associated defeaters. Future research should evaluate the performance of
LLMs on a combination of claims. It will be interesting to investigate whether
LLMs can identify the impact of defeaters on multiple claims and assess if the
provided evidence adequately addresses them. This direction will require
developing detailed data for evidence analysis and exploring prompts
specifically designed for this purpose.

##  6\. Conclusion and Future Work

We have presented CoDefeater, a process for automated defeater discovery in
assurance cases using LLMs (GPT-3.5). Our evaluation on two real-world case
studies demonstrated the LLM’s zero-shot capabilities in identifying defeaters
and its potential to support practitioners in an iterative human-in-the-loop
process. We make available the portion of a new assurance case and its ground-
truth defeaters used in our experiments for other researchers. Future work
will expand beyond the zero-shot setting to explore one-shot and few-shot
learning approaches for improved performance. Additionally, fine-tuning LLMs
on assurance cases presents an avenue to improve their performance. Our study
provides preliminary results as a starting point for future research to
explore the role of LLMs as a tool to assist with the identification of
defeaters toward the development of improved assurance cases.

###### Acknowledgements.

This work was funded by grant 80NSSC23M0058 from the National Aeronautics and
Space Administration (NASA).

## References

  * (1)
  * Adelard (2024) Adelard. 2024.  https://www.adelard.com/asce/cae/
  * Ahmed and Devanbu (2022) Toufique Ahmed and Premkumar Devanbu. 2022.  Few-shot training llms for project-specific code-summarization. In _Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering_. 1–5.
  * Alliance (2024) Golden Gate Bird Alliance. 2024\.  https://goldengatebirdalliance.org/conservation/make-the-city-safe-for-wildlife/drone-dangers-and-birds/
  * Arora et al. (2024) Chetan Arora, John Grundy, and Mohamed Abdelrazek. 2024\.  Advancing requirements engineering through generative ai: Assessing the role of llms.  In _Generative AI for Effective Software Development_. Springer, 129–148.
  * Assurance Case Working Group (2021) Assurance Case Working Group. 2021\.  _Assurance Case Guidance_.  Technical Report SCSC-159.
  * Bloomfield et al. (2021) Robin Bloomfield, Gareth Fletcher, Heidy Khlaaf, Luke Hinde, and Philippa Ryan. 2021.  Safety case templates for autonomous systems.  _arXiv preprint arXiv:2102.02625_ (2021).
  * Bloomfield and Rushby (2020) Robin Bloomfield and John Rushby. 2020.  Assurance 2.0: A manifesto.  _arXiv preprint arXiv:2004.10474_ (2020).
  * Braun and Clarke (2006) Virginia Braun and Victoria Clarke. 2006.  Using thematic analysis in psychology.  _Qualitative research in psychology_ 3, 2 (2006), 77–101.
  * Breaux et al. (2006) Travis D Breaux, Matthew W Vail, and Annie I Anton. 2006\.  Towards regulatory compliance: Extracting rights and obligations to align requirements with regulations. In _14th IEEE International Requirements Engineering Conference (RE’06)_. IEEE, 49–58.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Cave (2006) CH Cave. 2006.  An independent review into the broader issues surrounding the loss of the RAF Nimrod MR2 Aircraft XV230 in Afghanistan in 2006\.  _The Stationary Office, Tech. Rep_ (2006).
  * Chechik (2019) Marsha Chechik. 2019\.  Uncertain requirements, assurance and machine learning. In _2019 IEEE 27th International Requirements Engineering Conference (RE)_. IEEE, 2–3.
  * Chen et al. (2023a) Boqi Chen, Kua Chen, Shabnam Hassani, Yujing Yang, Daniel Amyot, Lysanne Lessard, Gunter Mussbacher, Mehrdad Sabetzadeh, and Dániel Varró. 2023a.  On the use of GPT-4 for creating goal models: an exploratory study. In _2023 IEEE 31st International Requirements Engineering Conference Workshops (REW)_. IEEE, 262–271.
  * Chen et al. (2023c) Banghao Chen, Zhaofeng Zhang, Nicolas Langrené, and Shengxin Zhu. 2023c.  Unleashing the potential of prompt engineering in large language models: a comprehensive review.  _arXiv preprint arXiv:2310.14735_ (2023).
  * Chen et al. (2023b) Lingjiao Chen, Matei Zaharia, and James Y. Zou. 2023b.  How is ChatGPT’s behavior changing over time?  _ArXiv_ abs/2307.09009 (2023).  https://api.semanticscholar.org/CorpusID:259951081
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Chiang and Lee (2023) Cheng-Han Chiang and Hung-yi Lee. 2023.  Can large language models be an alternative to human evaluations?  _arXiv preprint arXiv:2305.01937_ (2023).
  * Cohen (1960) Jacob Cohen. 1960\.  A coefficient of agreement for nominal scales.  _Educational and psychological measurement_ 20, 1 (1960), 37–46.
  * Dai et al. (2023) Shih-Chieh Dai, Aiping Xiong, and Lun-Wei Ku. 2023.  LLM-in-the-loop: Leveraging large language model for thematic analysis.  _arXiv preprint arXiv:2310.15100_ (2023).
  * Denney et al. (2012) Ewen Denney, Ganesh Pai, and Josef Pohl. 2012.  AdvoCATE: An assurance case automation toolset. In _Computer Safety, Reliability, and Security: SAFECOMP 2012 Workshops: Sassur, ASCoMS, DESEC4LCCI, ERCIM/EWICS, IWDE, Magdeburg, Germany, September 25-28, 2012. Proceedings 31_. Springer, 8–21.
  * Dey et al. (2018) Nilanjan Dey, Amira S Ashour, Fuqian Shi, Simon James Fong, and João Manuel RS Tavares. 2018\.  Medical cyber-physical systems: A survey.  _Journal of medical systems_ 42 (2018), 1–13.
  * Diemert et al. (2023) Simon Diemert, John Goodenough, Jeff Joyce, and Charles Weinstock. 2023.  Incremental assurance through eliminative argumentation.  _Journal of System Safety_ 58, 1 (2023), 7–15.
  * Diemert and Weber (2023) Simon Diemert and Jens H Weber. 2023.  Can Large Language Models Assist in Hazard Analysis?. In _International Conference on Computer Safety, Reliability, and Security_. Springer, 410–422.
  * Duan et al. (2017) Lian Duan, Sanjai Rayadurgam, Mats PE Heimdahl, Anaheed Ayoub, Oleg Sokolsky, and Insup Lee. 2017\.  Reasoning about confidence and uncertainty in assurance cases: A survey. In _Software Engineering in Health Care: 4th International Symposium, FHIES 2014, and 6th International Workshop, SEHC 2014, Washington, DC, USA, July 17-18, 2014, Revised Selected Papers 4_. Springer, 64–80.
  * Gemalmaz and Yin (2021) Meric Altug Gemalmaz and Ming Yin. 2021.  Accounting for Confirmation Bias in Crowdsourced Label Aggregation.. In _IJCAI_. 1729–1735.
  * Gohar et al. (2024) Usman Gohar, Michael C Hunter, Agnieszka Marczak-Czajka, Robyn R Lutz, Myra B Cohen, and Jane Cleland-Huang. 2024.  Towards Engineering Fair and Equitable Software Systems for Managing Low-Altitude Airspace Authorizations.  _arXiv preprint arXiv:2401.07353_ (2024).
  * Goodenough et al. (2012) J. Goodenough, Charles B. Weinstock, and Ari Z. Klein. 2012\.  Toward a Theory of Assurance Case Confidence.  https://api.semanticscholar.org/CorpusID:13431021
  * Goodenough et al. (2015) John B Goodenough, Charles B Weinstock, and Ari Z Klein. 2015\.  Eliminative argumentation: A basis for arguing confidence in system properties.  _Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU/SEI-2015-TR-005_ (2015).
  * Graydon and Holloway (2017) Patrick J Graydon and C Michael Holloway. 2017.  An investigation of proposed techniques for quantifying confidence in assurance arguments.  _Safety science_ 92 (2017), 53–65.
  * Greenwell et al. (2004a) William S. Greenwell, C. Michael Holloway, and John C. Knight. 2004a.  A Taxonomy of Fallacies in System Safety Arguments.  https://api.semanticscholar.org/CorpusID:267911368
  * Greenwell et al. (2004b) William S Greenwell, Elisabeth A Strunk, and John C Knight. 2004b.  Failure analysis and the safety-case lifecycle. In _Human Error, Safety and Systems Development: IFIP 18th World Computer Congress TC13/WC13. 5 7th Working Conference on Human Error, Safety and Systems Development 22–27 August 2004 Toulouse, France_. Springer, 163–176.
  * Gunes et al. (2014) Volkan Gunes, Steffen Peter, Tony Givargis, and Frank Vahid. 2014.  A survey on concepts, applications, and challenges in cyber-physical systems.  _KSII Transactions on Internet and Information Systems (TIIS)_ 8, 12 (2014), 4242–4268.
  * Hawkins et al. (2011) Richard Hawkins, Tim Kelly, John Knight, and Patrick Graydon. 2011.  A new approach to creating clear safety arguments. In _Advances in Systems Safety: Proceedings of the Nineteenth Safety-Critical Systems Symposium, Southampton, UK, 8-10th February 2011_. Springer, 3–23.
  * Hou et al. (2023) Xinying Hou, Yanjie Zhao, Yue Liu, Zhou Yang, Kailong Wang, Li Li, Xiapu Luo, David Lo, John C. Grundy, and Haoyu Wang. 2023\.  Large Language Models for Software Engineering: A Systematic Literature Review.  _ArXiv_ abs/2308.10620 (2023).  https://api.semanticscholar.org/CorpusID:261048648
  * Johnson et al. (1998) Leslie A Johnson et al. 1998\.  DO-178B: Software considerations in airborne systems and equipment certification.  _Crosstalk, October_ 199 (1998), 11–20.
  * Kelly and Weaver (2004) Tim Kelly and Rob Weaver. 2004.  The goal structuring notation–a safety argument notation. In _Proceedings of the dependable systems and networks 2004 workshop on assurance cases_ , Vol. 6. Citeseer Princeton, NJ.
  * Khakzad Shahandashti et al. (2023) Kimya Khakzad Shahandashti, Alvine Boaye Belle, Timothy Lethbridge, Oluwafemi Odu, and Mithila Sivakumar. 2023\.  A PRISMA-driven Systematic Review on System Assurance Weakeners.
  * Knight (2002) John C Knight. 2002\.  Safety critical systems: challenges and directions. In _Proceedings of the 24th international conference on software engineering_. 547–550.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022\.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ 35 (2022), 22199–22213.
  * Kokaly et al. (2016) Sahar Kokaly, Rick Salay, Valentin Cassano, Tom Maibaum, and Marsha Chechik. 2016.  A model management approach for assurance case reuse due to system evolution. In _Proceedings of the ACM/IEEE 19th International Conference on Model Driven Engineering Languages and Systems_ (Saint-malo, France) _(MODELS ’16)_. Association for Computing Machinery, New York, NY, USA, 196–206.  https://doi.org/10.1145/2976767.2976792
  * Kong et al. (2023) Aobo Kong, Shiwan Zhao, Hao Chen, Qicheng Li, Yong Qin, Ruiqi Sun, and Xin Zhou. 2023.  Better zero-shot reasoning with role-play prompting.  _arXiv preprint arXiv:2308.07702_ (2023).
  * Koons (2008) Robert C. Koons. 2008\.  Defeasible Reasoning.  In _Stanford Encyclopedia of Philosophy_.
  * Koopman (2022) Philip Koopman. 2022\.  _How Safe Is Safe Enough: Measuring and Predicting Autonomous Vehicle Safety_.  Carnegie Mellon University, https://books.google.com/books?id=lNVozwEACAAJ.
  * Kulatunga et al. (2007) Udayangani Kulatunga, Dilanthi Amaratunga, and Richard Haigh. 2007.  Structuring the unstructured data: the use of content analysis.  (2007).
  * Maksimov et al. (2018) Mike Maksimov, Nick LS Fung, Sahar Kokaly, and Marsha Chechik. 2018.  Two decades of assurance case tools: a survey. In _Computer Safety, Reliability, and Security: SAFECOMP 2018 Workshops, ASSURE, DECSoS, SASSUR, STRIVE, and WAISE, Västerås, Sweden, September 18, 2018, Proceedings 37_. Springer, 49–59.
  * Maksimov et al. (2019) Mike Maksimov, Sahar Kokaly, and Marsha Chechik. 2019\.  A Survey of Tool-supported Assurance Case Assessment Techniques.  _ACM Comput. Surv._ 52, 5, Article 101 (sep 2019), 34 pages.  https://doi.org/10.1145/3342481
  * McHugh (2012) Mary L McHugh. 2012\.  Interrater reliability: the kappa statistic.  _Biochemia medica_ 22, 3 (2012), 276–282.
  * Menghi et al. (2023) Claudio Menghi, Torin Viger, Alessio Di Sandro, Chris Rees, Jeff Joyce, and Marsha Chechik. 2023\.  Assurance Case Development as Data: A Manifesto. In _45th IEEE/ACM International Conference on Software Engineering: New Ideas and Emerging Results, NIER@ICSE, Melbourne, Australia, May 14-20, 2023_. IEEE, 135–139.
  * Millet et al. (2023) Laure Millet, Simon Diemert, Chris Rees, Torin Viger, Marsha Chechik, Claudio Menghi, and Jeffrey Joyce. 2023.  Assurance Case Arguments in the Large: The CERN LHC Machine Protection System. In _International Conference on Computer Safety, Reliability, and Security_. Springer, 3–10.
  * Murugesan et al. (2023) Anitha Murugesan, Isaac Hong Wong, Robert J. Stroud, Joaquín Arias, Elmer Salazar, Gopal Gupta, Robin Bloomfield, Srivatsan Varadarajan, and John Rushby. 2023.  Semantic Analysis of Assurance Cases using s(CASP). In _Proceedings of the International Conference on Logic Programming 2023 Workshops co-located with the 39th International Conference on Logic Programming (ICLP 2023), London, United Kingdom, July 9th and 10th, 2023_ _(CEUR Workshop Proceedings, Vol. 3437)_. CEUR-WS.org.
  * Nair et al. (2014) Sunil Nair, Jose Luis De La Vara, Mehrdad Sabetzadeh, and Lionel Briand. 2014.  An extended systematic literature review on provision of evidence for safety certification.  _Information and Software Technology_ 56, 7 (2014), 689–717.
  * OpenAI (2024) OpenAI. 2024.  Retrieved 2024 from https://platform.openai.com/docs/guides/prompt-engineering
  * Palin et al. (2011) Rob Palin, David Ward, Ibrahim Habli, and Roger Rivett. 2011\.  ISO 26262 safety cases: Compliance and assurance.  (2011).
  * Parliament and Council (2016) European Parliament and E Council. 2016.  General data protection regulation.  _official Journal of the European Union_ 59 (2016), 294.
  * Peng et al. (2023) Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, et al. 2023\.  Check your facts and try again: Improving large language models with external knowledge and automated feedback.  _arXiv preprint arXiv:2302.12813_ (2023).
  * Pollock (1987) John L Pollock. 1987\.  Defeasible reasoning.  _Cognitive science_ 11, 4 (1987), 481–518.
  * Rausand (2014) Marvin Rausand. 2014\.  _Reliability of safety-critical systems: theory and applications_.  John Wiley & Sons.
  * Rees et al. (2023) Chris Rees, Rolf Lippelt, Marsha Chechik, Lukas Felsberger, Mateo Delgado, Markus Zerlauth, Jeff Joyce, Claudio Menghi, Jan Uythoven, Simon Diemert, and et al. 2023.  Assessing the usefulness of assurance cases: An experience with the CERN Large Hadron Collider.  http://cds.cern.ch/record/2854725
  * Rushby (1994) John Rushby. 1994\.  Critical system properties: Survey and taxonomy.  _Reliability Engineering & System Safety_ 43, 2 (1994), 189–219.
  * Rushby (2015) John Rushby. 2015\.  The interpretation and evaluation of assurance cases.  _Comp. Science Laboratory, SRI International, Tech. Rep. SRI-CSL-15-01_ (2015).
  * Shahandashti et al. (2024) Kimya Khakzad Shahandashti, Mithila Sivakumar, Mohammad Mahdi Mohajer, Alvine B Belle, Song Wang, and Timothy C Lethbridge. 2024\.  Evaluating the Effectiveness of GPT-4 Turbo in Creating Defeaters for Assurance Cases.  _arXiv preprint arXiv:2401.17991_ (2024).
  * Sivakumar et al. (2023) Mithila Sivakumar, Alvine Boaye Belle, Jinjun Shan, and Kimya Khakzad Shahandashti. 2023\.  GPT-4 and Safety Case Generation: An Exploratory Analysis.  _arXiv preprint arXiv:2312.05696_ (2023).
  * UL Muram et al. (2018) Faiz UL Muram, Barbara Gallina, and Laura Gómez Rodríguez. 2018\.  Preventing Omission of Key Evidence Fallacy in Process-Based Argumentations. In _2018 11th International Conference on the Quality of Information and Communications Technology (QUATIC)_. 65–73.  https://doi.org/10.1109/QUATIC.2018.00019
  * Varadarajan et al. (2023) Srivatsan Varadarajan, Robin Bloomfield, John Rushby, Gopal Gupta, Anitha Murugesan, Robert Stroud, Kateryna Netkachova, and Isaac Hong Wong. 2023.  CLARISSA: Foundations, Tools & Automation for Assurance Cases. In _2023 IEEE/AIAA 42nd Digital Avionics Systems Conference (DASC)_. 1–10.  https://doi.org/10.1109/DASC58513.2023.10311213
  * Viger et al. (2023) Torin Viger, Logan Murphy, Simon Diemert, Claudio Menghi, Alessio Di, and Marsha Chechik. 2023\.  Supporting Assurance Case Development Using Generative AI. In _SAFECOMP 2023, Position Paper_. Toulouse, France.  https://hal.science/hal-04191791
  * Wang et al. (2024) Yiqi Wang, Wentao Chen, Xiaotian Han, Xudong Lin, Haiteng Zhao, Yongfei Liu, Bohan Zhai, Jianbo Yuan, Quanzeng You, and Hongxia Yang. 2024\.  Exploring the Reasoning Abilities of Multimodal Large Language Models (MLLMs): A Comprehensive Survey on Emerging Trends in Multimodal Reasoning.  _ArXiv_ abs/2401.06805 (2024).  https://api.semanticscholar.org/CorpusID:266999728
  * Warg et al. (2019) Fredrik Warg, Hans Blom, Jonas Borg, and Rolf Johansson. 2019\.  Continuous deployment for dependable systems with continuous assurance cases. In _2019 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)_. IEEE, 318–325.
  * Zhang et al. (2023) Chenyuan Zhang, Hao Liu, Jiutian Zeng, Kejing Yang, Yuhong Li, and Hui Li. 2023\.  Prompt-enhanced software vulnerability detection using chatgpt.  _arXiv preprint arXiv:2308.12697_ (2023).
  * Zheng et al. (2024) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. 2024\.  Judging llm-as-a-judge with mt-bench and chatbot arena.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Zheng et al. (2023) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Haotong Zhang, Joseph Gonzalez, and Ion Stoica. 2023.  Judging LLM-as-a-judge with MT-Bench and Chatbot Arena.  _ArXiv_ abs/2306.05685 (2023).  https://api.semanticscholar.org/CorpusID:259129398
  * Zhou et al. (2024) Xin Zhou, Ting Zhang, and David Lo. 2024.  Large language model for vulnerability detection: Emerging results and future directions. In _Proceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results_. 47–51.


11institutetext: Indian Institute of Science Education and Research, Pune,
India 22institutetext: The Institute of Mathematical Sciences, Chennai, India
33institutetext: University of Bergen, Bergen, Norway
33email<EMAIL_ADDRESS>33email:
<EMAIL_ADDRESS>33email<EMAIL_ADDRESS>

# Parameterized Algorithms for Locally Minimal Defensive Alliance

Ajinkya Gaikwad 11 Soumen Maity 11
Saket Saurabh 2233

###### Abstract

A set $D$ of vertices of a graph is a defensive alliance if, for each element
of $D$, the majority of its neighbours are in $D$. We consider the notion of
local minimality in this paper. We are interested in locally minimal defensive
alliance of maximum size. This problem is known to be NP-hard but its
parameterized complexity remains open until now. We enhance our understanding
of the problem from the viewpoint of parameterized complexity. The main
results of the paper are the following: (1) Locally Minimal Defensive Alliance
and Connected Locally Minimal Defensive Alliance are fixed-parameter tractable
(FPT) when parameterized by the solution size and $\Delta$, (2) Locally
Minimal Defensive Alliance on the graphs of minimum degree at least 2, admits
a kernel with at most ${f(k)}^{2k^{2}+4k}$ vertices for some computable
function $f(k)$. In particular, we prove that the problem on triangle-free
graphs of minimum degree at least 2, admits a kernel with at most
$k^{\mathcal{O}(k^{2})}$ vertices, where as the problem on planar graphs of
minimum degree at least 2, admits a kernel with at most
$k^{\mathcal{O}(k^{4})}$ vertices. We also prove that (3) Locally Minimal DA
Extension is NP-complete.

###### Keywords:

Parameterized Complexity FPT locally minimal defensive alliance

##  1 Introduction

A defensive alliance in an undirected graph is a set of vertices with the
property that each vertex has at least as many neighbours in the alliance
(including itself) as neighbours outside the alliance. In 2000, Kristiansen,
Hedetniemi, and Hedetniemi [kris] introduced defensive, offensive, and
powerful alliances, and further studied by Shafique
[HassanShafique2004PartitioningAG] and other authors [small, BAZGAN2019111,
Cami2006OnTC, SIGARRETA20061345, ROD, SIGARRETA20091687, SIGA,
Enciso2009AlliancesIG, BLIEM2018334, Fernau, FERNAU2009177, Lindsay]. In this
paper, we will focus on defensive alliances. A defensive alliance is strong if
each vertex has at least as many neighbours in the alliance (not counting
itself) as outside the alliance. The theory of alliances in graphs have been
studied intensively [frick, Cami2006OnTC, 10.5614/ejgta.2014.2.1.7] both from
a combinatorial and from a computational perspective. As mentioned in
[BAZGAN2019111], the focus has been mostly on finding small alliances,
although studying large alliances do not only make a lot of sense from the
original motivation of these notions, but was actually also delineated in the
very first papers on alliances [kris].

Note that defensive alliance is not a hereditary property, that is, a subset
of defensive alliance is not necessarily a defensive alliance. Shafique
[HassanShafique2004PartitioningAG] called an alliance a locally minimal
alliance if the set obtained by removing any vertex of the alliance is not an
alliance. Bazgan et al. [BAZGAN2019111] considered another notion of alliance
that they called a globally minimal alliance which has the property that no
proper subset is an alliance. In this paper we are interested in locally
minimal alliances of maximum size. Clearly, the motivation is that big
communities where every member still matters somehow are of more interest than
really small communities. Also, there is a general mathematical interest in
such type of problems, see [Manlove1998MinimaximalAM].

##  2 Basic Notations

Throughout this article, $G=(V,E)$ denotes a finite, simple and undirected
graph of order $|V|=n$. The (open) neighbourhood $N_{G}(v)$ of a vertex $v\in
V(G)$ is the set $\\{u\leavevmode\nobreak\ |\leavevmode\nobreak\ (u,v)\in
E(G)\\}$. The closed neighbourhood $N_{G}[v]$ of a vertex $v\in V(G)$ is the
set $\\{v\\}\cup N_{G}(v)$. The degree of $v\in V(G)$ is $|N_{G}(v)|$ and
denoted by $d_{G}(v)$. The subgraph induced by $D\subseteq V(G)$ is denoted by
$G[D]$. We use $d_{D}(v)$ to denote the degree of vertex $v$ in $G[D]$. The
complement of the vertex set $D$ in $V$ is denoted by $D^{c}$.

###### Definition 1

A non-empty set $D\subseteq V$ is a defensive alliance in $G$ if for each
$v\in D$, $|N[v]\cap D|\geq|N(v)\setminus D|$, or equivalently,
$d_{D}(v)+1\geq d_{D^{c}}(v)$.

A vertex $v\in D$ is said to be protected if $d_{D}(v)+1\geq d_{D^{c}}(v)$.
Here $v$ has $d_{D}(v)+1$ defenders and $d_{D^{c}}(v)$ attackers in $G$. A set
$D\subseteq V$ is a defensive alliance if every vertex in $D$ is protected.

###### Definition 2

A vertex $v\in D$ is said to be marginally protected if it becomes unprotected
when any of its neighbour in $D$ is moved from $D$ to $V\setminus D$. A vertex
$v\in D$ is said to be overprotected if it remains protected even when any of
its neighbours is moved from $D$ to $V\setminus D$.

###### Definition 3

[BAZGAN2019111] An alliance $D$ is called a locally minimal alliance if for
any $v\in D$, $D\setminus\\{v\\}$ is not an alliance.

It is important to note that if $D$ is a locally minimal defensive alliance,
then for every vertex $v\in D$, at least one of its neighbours in $D$ is
marginally protected.

###### Definition 4

[BAZGAN2019111] An alliance $D$ is a globally minimal alliance or shorter
minimal alliance if no proper subset is an alliance.

$1$23456789 Figure 1: The set $D_{1}=\\{2,3,5,6,8,9\\}$ is a locally minimal
defensive alliance of size 6 and $D_{2}=\\{1,2,4,6,8\\}$ is a globally minimal
defensive alliance of size 5 in $G$.

A defensive alliance $D$ is connected if the subgraph induced by $D$ is
connected. An alliance $D$ is called a connected locally minimal alliance if
for any $v\in D$, $D\setminus\\{v\\}$ is not a connected alliance. Notice that
any globally minimal alliance is also connected. In this paper, we consider
Locally Minimal Defensive Alliance and Connected Locally Minimal Defensive
Alliance. We define the problems as follows:
Locally Minimal Defensive Alliance
Input: An undirected graph $G=(V,E)$ and an integer $k$. Question: Does $G$
have a locally minimal defensive alliance $D$ with $|D|\geq k$?

We now recall the definition of height of a tree.

###### Definition 5

The _level_ of a vertex $v$ in a rooted tree is the number of edges along the
unique path between it and the root node. The _height_ of a rooted tree is the
maximum of the levels of vertices.

A parameterized problem $\mathcal{P}$ is _fixed-parameter tractable_ (FPT in
short) if a given instance $(x,k)$ can be solved in time
$f(k)\cdot{|(x,k)|}^{c}$ where $f$ is some (usually computable) function, and
$c$ is a constant. Closely related to fixed-parameter tractability is the
notion of preprocessing. A _reduction to a problem kernel_ , or equivalently,
_problem kernelization_ means to apply a data reduction process in polynomial
time to an instance $(x,k)$ such that for the reduced instance
$(x^{\prime},k^{\prime})$ it holds that $(x^{\prime},k^{\prime})$ is
equivalent to $(x,k)$, $|x^{\prime}|\leq g(k)$ and $k^{\prime}\leq g(k)$ for
some function $g$ only depending on $k$. Such a reduced instance is called a
_problem kernel_. It is easy to show that a parameterized problem is in FPT if
and only if there is kernelization algorithm. We refer to [marekcygan, Downey]
for further details on parameterized complexity.

Our results are as follows:

  * •

Locally Minimal DA Extension is NP-complete.

  * •

Locally Minimal Defensive Alliance and Connected Locally Minimal Defensive
Alliance are FPT when parameterized by the solution size and $\Delta$.

  * •

Locally Minimal Defensive Alliance on the graphs of minimum degree at least 2,
admits a kernel with at most ${f(k)}^{2k^{2}+4k}$ vertices for some computable
function $f(k)$. In particular, we prove that the problem on triangle-free
graphs of minimum degree at least 2, admits a kernel with at most
$k^{\mathcal{O}(k^{2})}$ vertices, where as the problem on planar graphs of
minimum degree at least 2, admits a kernel with at most
$k^{\mathcal{O}(k^{4})}$ vertices.

Known Results: The decision version for several types of alliances have been
shown to be NP-complete. Carvajal et al. [small] proved that deciding if a
graph contains a strong defensive alliance of size at most $k$ is NP-hard. The
defensive alliance problem is NP-complete even when restricted to split,
chordal and bipartite graph [Lindsay]. Bazgan et al. [BAZGAN2019111] proved
that deciding if a graph contains a locally minimal strong defensive alliance
of size at least $k$ is NP-complete, even when restricted to bipartite graphs
with average degree less than 3.6. Gaikwad and Maity showed that Locally
Minimal Defensive Alliance is fixed parameter tractable (FPT) when
parametrized by neighbourhood diversity and it can be solved in polynomial
time for graphs of bounded treewidth. They also proved that Exact Connected
Locally Minimal Defensive Alliance parameterized by treewidth is W[1]-hard and
thus not FPT (unless FPT=W[1]).

##  3 On Locally Minimal Defensive Alliance Extension

Algorithms working on combinatorial graph problems often try to look at local
parts of the graph and then extend some part of the (final) solution that was
found and fixed so far. For many maximisation problems, like Maximum
Independent Set, it is trivial to obtain a feasible solution that extends a
given vertex set by some greedy strategy, or to know that no such extension
exists. This is not true for Locally Minimal Defensive Alliance, as we show
next. Formally, we want to discuss the following problem:

Locally Minimal DA Extension
Input: A graph $G=(V,E)$, a set $S\subseteq V$. Question: Does $G$ have a
locally minimal defensive alliance $D$ with $S\subseteq D$?
Note that given a vertex $v$, there always exists a defensive alliance
containing it. But such a statement does not hold when it comes to locally
minimal defensive alliance, that is, given a vertex $v$ there may or may not
exist a locally minimal defensive alliance containing $v$. For example,
consider the star graph $S_{n}$ with $v\in V(S_{n})$ such that $d(v)=n-1$. We
observe that there is no locally minimal defensive alliance containing $v$. We
show that given an arbitrary set $S\subseteq V$, it is NP-complete to
determine whether there exists a locally minimal defensive alliance containing
$S$. It is not clear if this result holds when $|S|=1$. The example of a star
graph may be a very special case. We do not know of any graph $G$ with minimum
degree two, where given a vertex $v$ there is no locally minimal defensive
alliance containing $v$. It may be possible that such an example does not even
exist. We now show that Locally Minimal DA Extension is NP-hard. Our proof is
based on a reduction from the NP-complete Clique problem.

###### Theorem 3.1

Locally Minimal DA Extension is NP-complete.

###### Proof

It is easy to see that Locally Minimal DA Extension is in NP. NP-hardness can
be shown by reduction from Clique on regular graphs. Let $I=(G,k)$ be an
instance of Clique, where $G$ is an $r$-regular graph. We construct an
instance $I^{\prime}=(G^{\prime},S)$ of Locally Minimal DA Extension as
follows: First, we introduce a set $A=\\{a_{1},\ldots,a_{r-2k+1}\\}$ of
$r-2k+1$ new vertices into $G^{\prime}$. For every vertex $a_{i}\in A$, we
introduce a set $V_{a_{i}}$ of $n-2k-1$ vertices into $G^{\prime}$ and make
them adjacent to $a_{i}$. We make every vertex of $V(G)$ adjacent to every
vertex of $A$. This completes the construction of $G^{\prime}$. Finally, we
set $S=\bigcup\limits_{i=1}^{r-2k+1}V_{a_{i}}$. To prove the correctness of
the reduction, we claim that $G$ has a $k$-clique if and only if $G^{\prime}$
admits a locally minimal defensive alliance containing $S$. Assume first that
$G$ has a clique $C$ of size $k$. We claim that $D=S\cup A\cup C$ is a locally
minimal defensive alliance in $G^{\prime}$. Let $x$ be an arbitrary element of
$D$. If $x$ is an element of $S$, then the only neighbor of $x$ in
$G^{\prime}$ is in $D$, so $x$ can trivially defend itself. If $x$ is an
element of $A$, then including itself $x$ has $(n-2k-1)+k+1=n-k$ neighbours
inside $D$ and $n-k$ neighbours outside $D$, so $x$ is marginally protected.
If $x$ is an element of $C$ then, including itself, $x$ has $(r-2k+1)+k=r-k+1$
neighbours inside $D$ and $r-k+1$ neighbours outside $D$ as $G$ is a
$r$-regular graph. Also every vertex in $D$ have a marginally protected
neighbour. This proves that $D$ is a locally minimal defensive alliance
containing $S$.

To prove the reverse direction of the equivalence, suppose $G^{\prime}$ has a
locally minimal defensive alliance $D$ containing $S$. Since every vertex in
$S$ is of degree one, its only neighbour must be contained in locally minimal
defensive alliance and it must be marginally protected. That means, the
vertices of $A$ are in $D$ and every vertex $a$ of $A$ must be marginally
protected. Note that, including itself, $a$ has total $2n-2k$ neighbours in
$G^{\prime}$. As $a$ is marginally protected, $n-k$ neighbours are inside $D$
and the remaining $n-k$ neighbours are outside $D$. It implies that $|D\cap
V(G)|=k$ as every vertex of $A$ is adjacent to every vertex of $V(G)$. Let
$D\cap V(G)=C$. We will show that $C$ is a clique. Let $u$ be an arbitrary
vertex in $C$, then $d_{G^{\prime}}(u)=2r-2k+1$. Clearly, including itself,
$u$ must have at least $r-k+1$ neighbours inside $D$. The neighbors of $u$
that are also in $D$ consist of the elements of $A$ and at least $k-1$
elements of $C$. Since $|C|=k$, $u$ must be adjacent to all the vertices in
$C$. Therefore $C$ is a clique. This completes the proof of Theorem 3.1. ∎

##  4 Kernelization algorithms parameterized by solution size and $\Delta$

In this section we present a kernelization algorithm for Locally Minimal
Defensive Alliance and a FPT algorithm for Connected Locally Minimal Defensive
Alliance.

###  4.1 Kernelization algorithm for Locally Minimal Defensive Alliance

Algorithm 1 starts with a defensive alliance and returns a locally minimal
defensive alliance.

Algorithm 1

1:A graph $G=(V,E)$ and a defensive alliance $D$

2:a locally minimal defensive alliance

3:for $u\in D$ do

4: if all neighbours of $u$ in $D$ are overprotected then

5: $D=D\setminus\\{u\\}$

6: end if

7:end for

8:return $D$

We now introduce crucial vertices in a defensive alliance and demonstrate a
connection between crucial vertices and locally minimal defensive alliance.

###### Definition 6

Let $D$ be a defensive alliance in $G$. A vertex $u\in D$ is said to be a
_crucial_ vertex in $D$ if $u$ has a marginally protected neighbour $u_{1}$ in
$D$ and $u_{1}$ also has a marginally protected neighbour $u_{2}$ in $D$
($u_{2}$ and $u$ are not necessarily distinct vertices).

###### Lemma 1

Let $D$ be a defensive alliance in graph $G$ and let $S$ be the set of crucial
vertices in $D$. Then the locally minimal defensive alliance obtained by
Algorithm 1 on $D$ always contains $S$.