# Enhanced phase noise reduction in localized two-way optical frequency
comparison

Long Wang, Ruimin Xue, Wenhai Jiao, Liang Hu, Jianping Chen, and Guiling Wu
Manuscript received xxx xxx, xxx; revised xxx xxx, xxx. This work was
supported by the National Natural Science Foundation of China (NSFC)
(62120106010, 61905143), the Zhejiang provincial Key Research and Development
Program of China (2022C01156) and the National Science Foundation of Shanghai
(22ZR1430200). (Corresponding author: Liang Hu; Guiling Wu)L. Wang, and R. Xue
are with the State Key Laboratory of Advanced Optical Communication Systems
and Networks, Department of Electronic Engineering, Shanghai Jiao Tong
University, Shanghai 200240, China (e-mail<EMAIL_ADDRESS>rmxue96@sjtu.edu.cns)L. Hu, J. Chen, and G. Wu are with the State Key
Laboratory of Advanced Optical Communication Systems and Networks, Department
of Electronic Engineering, Shanghai Jiao Tong University, Shanghai 200240,
China, and also with the SJTU-Pinghu Institute of Intelligent Optoelectronics,
Jiaxing Time-Transfer Photoelectric Co., Ltd., Pinghu 314200, China, China
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>wuguiling@sjtu.edu.cn)Wenhai Jiao is with the Beijing Institute of Tracking
and Telecommunication Technology, Beijing 100094, China (email:
<EMAIL_ADDRESS>
###### Abstract

High-stability optical frequency comparison over fiber link enables the
establishment of ultrastable optical clock networks, having the potential to
promote a series of applications, including metrology, geodesy, and astronomy.
In this article, we theoretically analyze and experimentally demonstrate a
time-delayed local two-way (TD-LTW) optical frequency comparison scheme with
improved comparison stability, showing that the fractional instability of
optical frequency comparison over a 50-km transfer link can be reduced from
$1.30\times 10^{-15}$ to $5.25\times 10^{-16}$ at the 1 s integration time
with an improvement factor of 2.48. Additionally, we also for the first time
model and experimentally verify the effect of the inhomogeneous phase noise
along the fiber link on the system performance. We believe that the theory and
technique proposed here will be helpful in developing the high-stability
optical clock networks over large-area fiber links.

###### Index Terms:

Optical clock, optical frequency comparison, metrology.

##  I Introduction

With the accuracy of optical clocks achieving the level of $10^{-18}$ [1, 2,
3], the large-scale, high-stability optical clock network is of increasing
interest for many applications, including radio astronomy [4, 5], clock-based
geodesy [6], very long baseline interferometry [7, 8], and gravitational-wave
detection [9, 10]. To develop clock networks, fiber-based optical frequency
transfer and comparison are one of the most important ingredients [11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]. Optical frequency transfer gives
the possibility to distribute the frequency standard to different user sites
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20] whereas optical frequency comparison
compares the frequency standards [21, 22, 23, 24] between a wide number of
metrology laboratories.

The basic setups of optical frequency transfer and comparison are both
constructed by an imbalanced Michelson interferometer, whose long arm is
connected with the fiber link and short arm is spliced with a Faraday rotating
mirror (FRM) to provide a local frequency reference [11]. For optical
frequency transfer, the local optical signal is delivered to the remote end
along the transfer link, and then part of the beam is reflected back to the
local site. By comparing the round-trip signal with the local frequency
reference, the link-induced phase noise can be detected, and then the active
noise compensation (ANC) based phase locked loop (PLL) is employed to
compensate the phase noise induced by the fiber link. However, the finite
propagation velocity of the optical signal limits the compensation
performance, leaving a named delay-unsuppressed residual phase noise. The
power spectral density (PSD) of this phase noise was first studied in [14],
whose expression for the ANC scheme at the offset frequency $f\leq 1/(4\tau)$
is,

$S_{\rm r}(\omega)\simeq\frac{1}{3}(2\pi f\tau)^{2}S_{0}(\omega)$ (1)

where $\tau$ is the one-way propagation delay of the optical fiber link [14],
and $S_{0}(\omega)$ is the phase noise PSD accumulated by the single-trip
optical signal.

Taking into account the quadratic relationship between the phase noise PSD and
the propagation delay as illustrated in Eq. (1), Lopez and co-workers proposed
a cascaded optical frequency transfer [25] technique by dividing the whole
transfer link into $N$ sub-links, theoretically resulting in a reduction of
the phase noise PSD with a factor of $N$. However, there are several other
factors practically limit the stability, including the out-of-band phase noise
induced by the laser locking in the cascaded repeaters. Consequently, the
long-term stability could be constrained by the noise floor [26]. In 2015,
Calosso _et al_ proposed a post-processing approach for optical frequency
transfer, which can overcome the classical limit of the delay-unsuppressed
residual phase noise [27]. This scheme is realized by a delay subtraction
algorithm between the optical signal delivered at the remote end and the
round-trip signal detected at the local site. However, it is difficult to put
this proof-of-principle study into practice because the separated data
acquisitions at the different ends of the fiber link limits the real-time
feedback control. On one hand, if the remote signal is sent back to the local
site and a feedback servo is implemented, the residual phase noise will be
determined by Eq. (1) again. On the other hand, if the local beating note is
sent to the remote site to accomplish feedback, it is hardly to generate a
time delay for the transferred optical frequency signal without introducing
additional phase noise. In our pioneering work, a method of phase noise
compensation based on feed-forward control is proposed for the optical
frequency transfer [20, 19, 28, 29]. This scheme can effectively reduce the
system complexity and remove the servo bump induced by the PLL module, but the
residual phase noise PSD presents a factor of 7 higher than that of Eq. (1),
meaning a worse frequency transfer stability compared with the ANC scheme.

In the field of optical frequency comparison, the lower bound of the phase
noise suppression defined by Eq. (1) can be reduced in the two-way optical
frequency comparison (TWC) scheme [21, 22, 23, 24], in which the optical
frequency signals located at two distant sites are delivered to the opposite
ends, and each site detects the beating note between the local reference and
received signals. Under the assumption that the link-induced phase noises are
reciprocal for two propagation directions, the phase noise can be efficiently
suppressed by the post processing [21]. Theoretically, the TWC method provides
a factor of 4 reduction compared to Eq. (1), meaning a lower delay-
unsuppressed residual phase noise [14]. However, in the post-processing, the
timebase mismatch of the data acquisition at two distant sites will sacrifice
the acquired stability improvement in the TWC technique. For example, when the
mismatch is larger than the one-way propagation time such as about 500 $\mu$s
for 100-km fiber link, it will spoil the improvement achieved by the TWC
method [30]. To deal with the time mismatch of the data acquisition process
and enable a real-time measurement, Lee et al proposed a local two-way (LTW)
frequency comparison method [24]. Different from the TWC method, the
ultrastable optical frequency signal arriving at the remote site is reflected
back to the local site, passing through fiber link twice. Under this
circumstance, the relative frequency of the two optical clocks can be obtained
at the local site by comparing the frequency of the round-trip signal and the
single-trip remote optical signal, eliminating the risk of the timebase
mismatch caused by the separated data acquisitions. Nevertheless, its
capability of noise suppression is still determined by the classical limit
expressed in the Eq. (1), illustrating a worse comparison stability than the
well-worked TWC scheme.

In this paper, we propose a time-delayed local two-way comparison (TD-LTW)
technique, enabling a real-time optical frequency comparison by simple
frequency mixing at the local site and more importantly breaking the classical
phase-noise limit expressed by the Eq. (1) in the conventional LTW scheme
[24]. Specifically, the following sections are organized as below: Section II
presents the theoretical foundation of the proposed TD-LTW scheme, and to the
best of our knowledge, the effect of the inhomogeneous phase perturbation on
the fiber link is first studied. Section III demonstrates the experimental
setup and presents the main experimental results, including the comparison
between the proposed TD-LTW technique and the conventional LTW scheme, and the
investigation of the inhomogeneous phase noise perturbation on the fiber link.
Finally, Section IV gives the discussion and conclusion.

##  II Theoretical analysis on the delay-unsuppressed residual phase noise

###  II-A Theoretical foundation of the proposed TD-LTW scheme

Figure 1: The schematic diagram of the proposed TD-LTW optical frequency
comparison (a), in which the time delay can be implemented in the optical
domain (b) or the electrical domain (c). By removing the time delay line, i.e.
setting $\delta\tau=0$, the configuration can function as the conventional LTW
scheme. FRM: Faraday rotating mirror, AOM: acousto-optic modulator, Bi-EDFA:
bidirectional Erbium-doped optical fiber amplifier, DDS: direct digital
synthesizer, PD: photo-detector, O-TDL: optical tunable delay line, E-TDL:
electrical tunable delay line, BPF: band-pass filter.

Figure 1 shows the schematic diagram of the proposed TD-LTW optical frequency
comparison technique. Two distant sites, both equipped with ultrastable
lasers, are connected by an optical fiber link. At the local site, the output
of the ultrastable laser 1 is split into two parts by an optical coupler,
where one indicted by the red arrows is reflected by the local FRM and then
falls into the time-delay frequency comparison module, serving as the
reference beam. The other part, shown by the green arrows, is transferred
towards the remote site via the optical fiber link. At the remote site, there
are two optical frequency signals being injected into the same fiber link and
transferred toward the local site. One comes from the output of the
ultrastable laser 2, indicted by the blue arrow, and the other beam (green
arrow) coming from the local site is reflected by the remote FRM. After the
propagating along the fiber link, these optical frequency signals are both
collected by the time-delayed frequency comparison module. Furthermore, in
this setup, two acousto-optic modulators (AOMs) are placed at the ends of the
fiber link to remove the influence of the backscattering noise and other
unwanted reflections [11]. By this means, three desired optical signals, the
reference beam, the round-trip beam and the single-trip signal coming from the
laser 2, are simultaneously received by the time-delayed frequency comparison
module.

To realize the time-delayed frequency comparison, the time delay can be
implemented in the optical domain (e.g., fiber) or electrical domain, as shown
in Fig. 1 (b) and (c) respectively. In terms of the optical time delay method,
the received signals are split into two unbalanced detection paths, which have
a relative delay $\delta\tau$ generated by the optical delay line. Then, the
relative frequency between the two distant ultrastable lasers can be obtained
by mixing the two filtered beating signals detected by photo-detectors (PDs).
Alternatively, the electrical time delay method implemented in the FPGA
platform can be adopted [31] as schematically illustrated in Fig. 1 (c). In
this method, the optical signals are first converted into the microwave
signals, and then are divided into two paths. One branch is directly filtered
by a band-pass filter and injected into the mixer. The other branch, after
passing through the electrical time delay module and a band-pass filter, is
also injected into the mixer to accomplish the frequency comparison.

Here we choose the first comparison method to deduce the TD-LTW method
proposed, and the same results can also be obtained for the electrical delay
method by following the same procedure. By properly choosing the driving
frequencies of the AOMs ($\Omega_{1}$ for AOM1 and $\Omega_{2}$ for AOM2),
three beating signals recovered by the PD1 can be expressed as,

$E_{\rm PD1,i}\propto\cos\left[\Delta\omega_{i}t+\phi_{i}(t)\right],i=1,2,3,$
(2)

where $\Delta\omega_{i}$ are the frequencies of the beating signals, being
equal to $\Delta\omega_{1}=2(\Omega_{1}+\Omega_{2})$,
$\Delta\omega_{2}=\omega_{1}-\omega_{2}-\Omega_{1}-\Omega_{2}$, and
$\Delta\omega_{3}=\Omega_{1}+\Omega_{2}+\omega_{1}-\omega_{2}$, and
$\phi_{1}=\phi_{\rm RT}(t)$, $\phi_{2}=\Delta\phi-\phi_{\rm R-L}(t)$,
$\phi_{3}=\phi_{\rm L-R}(t)+\Delta\phi$ with $\Delta\phi=\phi_{1}-\phi_{2}$
being the relative phase between the laser 1 and the laser 2, $\phi_{\rm
RT}(t)$ being the fiber-induced phase noise experienced by the round-trip
signal, and $\phi_{\rm R-L}(t)$ ($\phi_{\rm L-R}(t)$) being the fiber-induced
phase noise experienced by the optical frequency signal propagating from the
remote (local) site to the local (remote) site. Moreover, $\omega_{1}$ and
$\omega_{2}$ are the output frequencies of laser 1 and laser 2, respectively.

Likewise, the beating signals recovered by the PD2 can be written as,

$E_{\rm
PD2,i}\propto\cos\left[\Delta\omega_{i}t+\phi_{i}(t-\delta\tau)\right],$ (3)

where $\delta\tau$ is the time delay induced by the optical delay fiber.

By properly setting the frequencies of the band-pass filters (BPF1 and BPF2),
different beating signals can be selected to conduct frequency mixing to
suppressing the link-induced phase noise, and then the mixing output can be
used to extract the relative phase $\Delta\phi$. Here, three kinds of mixing
signals can be used to evaluate the relative phase $\Delta\phi$, which can be
expressed as,

$E_{1}(t)\propto\cos\left[(\Delta\omega_{2}+\Delta\omega_{1}/2)t+\Delta\phi_{\rm
L1}(t)+\Delta\phi\right],$ (4)
$E_{2}(t)\propto\cos\left[(\Delta\omega_{3}-\Delta\omega_{1}/2)t+\Delta\phi_{\rm
L2}(t)+\Delta\phi\right],$ (5)
$E_{3}(t)\propto\cos\left[(\Delta\omega_{3}-\Delta\omega_{2})t/2+\Delta\phi_{\rm
L3}(t)+\Delta\phi\right],$ (6)

respectively. The phase terms, $\Delta\phi_{\rm L1}(t)=\phi_{\rm
RT}(t)/2-\phi_{\rm R-L}(t-\delta\tau)$, $\Delta\phi_{\rm L2}(t)=\phi_{\rm
L-R}(t)-\phi_{\rm RT}(t-\delta\tau)/2$, and $\Delta\phi_{\rm L3}(t)=[\phi_{\rm
L-R}(t)-\phi_{\rm R-L}(t-\delta\tau)]/2$ are the residual phase noises induced
by the optical fiber link, which affect the evaluation of the $\Delta\phi$.

Following the same procedure presented in [14], the accumulated phase noise of
the round-trip and single-trip signal can be written as,

$\displaystyle\phi_{\rm RT}(t)$
$\displaystyle=\int_{0}^{L}h(z)\delta\phi\left[z,t-(2\tau-z/c_{n})\right]{\rm
d}z$ (7) $\displaystyle+\int_{0}^{L}h(z)\delta\phi\left(z,t-z/c_{n}\right){\rm
d}z$ $\phi_{\rm R-L}(t)=\int_{0}^{L}h(z)\delta\phi\left(z,t-z/c_{n}\right){\rm
d}z$ (8) $\phi_{\rm
L-R}(t)=\int_{0}^{L}h(z)\delta\phi\left[z,t-(2\tau-z/c_{n})\right]{\rm d}z$
(9)

where $\delta\phi(z,t)$ is the phase perturbation on the fiber at time $t$ and
position $z$, $\tau=L/c_{n}$ is the propagation delay along the fiber, and
$c_{n}$ is the velocity of the optical frequency signal in the fiber link.
Note that a spatial distribution function $h(z)$ is used to describe the
inhomogeneous phase perturbation on the fiber link. By this means, the
residual phase noises in Eq. (4)-(6) can be expressed as,

$\Delta\phi_{\rm
L1}(t)=\int_{0}^{L}h(z)(z/c_{n}-\tau+\delta\tau)\delta\phi^{\prime}(z,t){\rm
d}z,$ (10) $\Delta\phi_{\rm
L2}(t)=\int_{0}^{L}h(z)(z/c_{n}-\tau+\delta\tau)\delta\phi^{\prime}(z,t){\rm
d}z,$ (11) $\Delta\phi_{\rm
L3}(t)=\int_{0}^{L}h(z)(z/c_{n}-\tau+\delta\tau/2)\delta\phi^{\prime}(z,t){\rm
d}z,$ (12)

where the first-order Taylor approximation of $\delta\phi(z,t)$ is used and
$\delta\phi^{\prime}(z,t)$ represents the first-order derivative of the phase
perturbation $\delta\phi(z,t)$.

Under the assumption that the link-induced phase noise is uncorrelated with
position, the residual phase noise PSDs of the TD-LTW optical frequency
comparison scheme using the different evaluation signals in Eq. (4)-(6) are,

$S_{\rm
L1}(\omega,\delta\tau)={\omega^{2}S_{0}(\omega)}\int_{0}^{L}\frac{h^{2}(z)}{L}(z/c_{n}-\tau+\delta\tau)^{2}{\rm
d}z,$ (13) $S_{\rm
L2}(\omega,\delta\tau)={\omega^{2}S_{0}(\omega)}\int_{0}^{L}\frac{h^{2}(z)}{L}(z/c_{n}-\tau+\delta\tau)^{2}{\rm
d}z,$ (14) $S_{\rm
L3}(\omega,\delta\tau)={\omega^{2}S_{0}(\omega)}\int_{0}^{L}\frac{h^{2}(z)}{L}(z/c_{n}-\tau+\frac{\delta\tau}{2})^{2}{\rm
d}z,$ (15)

respectively. If the perturbation on the fiber link is homogeneous (i.e.
$h(z)=1$) and uncorrelated in position, we can get,

$S_{\rm
L1}(\omega,\delta\tau)=\frac{\omega^{2}}{3\tau}\left[(\delta\tau)^{3}-(\delta\tau-\tau)^{3}\right]S_{0}(\omega),$
(16) $S_{\rm
L2}(\omega,\delta\tau)=\frac{\omega^{2}}{3\tau}\left[(\delta\tau)^{3}-(\delta\tau-\tau)^{3}\right]S_{0}(\omega),$
(17) $S_{\rm
L3}(\omega,\delta\tau)=\frac{\omega^{2}}{3\tau}\left[(\frac{\delta\tau}{2})^{3}-(\frac{\delta\tau}{2}-\tau)^{3}\right]S_{0}(\omega).$
(18)

Once $\delta\tau=0$, the residual phase noise PSDs of Eq. (16)-(18) become,

$S_{\rm LTW}(\omega)=\frac{1}{3}(2\pi f\tau)^{2}S_{0}(\omega),$ (19)

which is the typical residual phase noise PSD acquired by the conventional LTW
optical frequency comparison scheme [24]. Alternatively, by choosing the
optimal time delay $\delta\tau$, the residual phase noise PSDs of Eqs.
(16)-(18) become,

$S_{\rm TD-LTW}(\omega,\delta\tau=\tau)=\frac{1}{12}(2\pi
f\tau)^{2}S_{0}(\omega),$ (20)

where the optimal values for Eqs. (16)-(18) are $\delta\tau=\tau/2$,
$\delta\tau=\tau/2$, and $\delta\tau=\tau$, respectively.

Here, we define an improvement factor as the Allan deviation (ADEV) ratio of
the LTW scheme to that of the proposed TD-LTW scheme. According to Eq. (19)
and (20), it can be inferred that the further suppression of the residual
phase noise by a factor of 4 can result in an improvement factor of 2 in the
ADEV-expressed fractional frequency stability under the assumption of the
homogeneous perturbation. Moreover, compared with Eqs. (16) and (17), we can
be seen that there is a denominator 2 in the term of $\delta\tau$ in Eq. (18),
indicating a smaller influence resulting from the deviation from the optimal
time delay value. Therefore, the method given by Eq. (6) will be adopted in
the following experiments.

###  II-B Inhomogeneous phase perturbation induced by the fiber link

Considering the inhomogeneous phase noise perturbation along the fiber link,
the behaviours of the phase noise suppression and the improvement achieved by
the proposed TD-LTW technique will be different from the homogeneous case.
Here, we assume that the phase noise perturbation distribution follows a
piecewise uniform function,

$h(z)=\sum_{i=1}^{N}h_{i}{\rm rect}\left(\frac{z-z_{i}}{z_{{\rm
d},i}}\right),$ (21)

where ${\rm rect}[(z-z_{i})/z_{{\rm d},i}]$ is equal 1 for
$0\leq[(z-z_{i})/z_{{\rm d},i}]\leq 1$ and 0 otherwise. In the following
simulation, four cases of the perturbation distribution are discussed, as
shown in Fig. 2.

Figure 2: The distribution functions of four kinds of piecewise uniform
functions with the same total integrated phase noise (left and bottom axes)
and the improvement factors achieved by the TD-LTW scheme under different time
delay $\delta\tau$ (top and right axes).

Based on the phase noise perturbations with the same total integrated fiber
phase noise shown in Fig. 2, the phase noise suppression ratios of different
optical frequency comparison schemes are shown in Table 1. Here, the
suppression ratios of the LTW and TD-LTW schemes are obtained by calculating
the integral terms
($\int_{0}^{L}\frac{h^{2}(z)}{L}(z/c_{n}-\tau+\frac{\delta\tau}{2})^{2}{\rm
d}z$) in Eq. (15) with different time delay ($\delta\tau$). The ratio of the
TWC scheme is obtained based on the Eq. (4) in [22] by taking the distribution
function $h(z)$ into account. In the four inhomogeneous cases, all the
integral factors of the conventional LTW scheme are higher than that of the
proposed TD-LTW and TWC schemes, meaning a higher residual phase noise. The
improvement factors of the four distributions are also shown in Table 1,
demonstrating that the proposed TD-LTW technique can enhance the phase noise
reduction under the inhomogeneous perturbation.

Note that the improvement achieved by the TD-LTW scheme with $\delta\tau=\tau$
is better when the perturbation is concentrated on the front part of the fiber
link. In particular, the best improvement can be achieved when the phase noise
perturbation mainly locates at the center. Moreover, for the symmetric
distribution in the case 1 and 3, the difference in the improvement factors
comes from the LTW scheme, where the performances of the TD-LTW scheme in the
phase noise suppression are same. More importantly, the optimal time delay
$\delta\tau$ is different for the different phase noise perturbations. For
example, $\delta\tau=\tau$ is only the optimal choice when the perturbation
follows the symmetric distribution as demonstrated in the case 2 and 4 in Fig.
2. In the case 1 and 3, the optimal time delays are slight deviation from
$\delta\tau=\tau$ and the optimal improvement factors achieved by the TD-LTW
scheme in the case 1 and 3 can reach 3.16 and 1.69, respectively.

TABLE I: The comparison of different schemes under the inhomogeneous phase perturbations. Schemes | Case 1 | Case 2 | Case 3 | Case 4
---|---|---|---|---
LTW | $7.72\cdot 10^{-9}$ | $4.48\cdot 10^{-9}$ | $2.21\cdot 10^{-9}$ | $4.97\cdot 10^{-9}$
TD-LTW | $1.29\cdot 10^{-9}$ | $5.27\cdot 10^{-10}$ | $1.29\cdot 10^{-9}$ | $8.67\cdot 10^{-10}$
TWC | $1.29\cdot 10^{-9}$ | $5.27\cdot 10^{-10}$ | $1.29\cdot 10^{-9}$ | $8.67\cdot 10^{-10}$
IF($\delta\tau=\tau$) | 2.45 | 2.92 | 1.31 | 2.38
IFoptimal | 3.16 | 2.92 | 1.69 | 2.38

##  III Experiment setup and results

###  III-A Experiment setup for investigating the proposed TD-LTW scheme

To prove the stability improvement achieved by the TD-LTW scheme, a
verification experiment is conducted based on the setup illustrated in Fig. 3.
To effectively evaluate the proposed technique, here we use one laser to
simulate two independent lasers at two distant sites and the frequency of the
remote one is downshifted by the acoustic optical modulator 3 (AOM3) with the
value of 38 MHz. To generate the time delay required in Eq. (18), a 50-km
delay fiber is placed before the PD2. The AOM1 ($-1$ order) and AOM2 ($+1$
order) work at the frequency of $78$ MHz and 83 MHz, respectively. In this
configuration, two beating signals at frequency of 43 MHz and 33 MHz are
selected by the BPF1 and BPF2, respectively, each of which represents the
single-pass signal. After frequency mixing the two filtered beating signals,
the mixing output 76 MHz is divided by 2 and then used for evaluating the TD-
LTW optical frequency comparison results. It is worth noting that considering
the coefficient 40 ps/(K$\cdot$km) of the single-mode fiber, the artificial
time delay variations of the delay fiber caused by the temperature
fluctuations is negligible. For example, it will introduce $\sim$ 20 ns delay
variation if the temperature fluctuations of 10 K over a 50 km time delay
fiber. Moreover, to boost the attenuation coming from the 50-km time delay
fiber we add an erbium-doped fiber amplifier (EDFA) before the PD2.

Figure 3: The experimental setup for verifying the improvement achieved by the
proposed TD-LTW optical frequency comparison scheme. One laser is employed to
simulate two independent lasers at two sites, and the frequency of the remote
one is downshifted by the AOM3 with the frequency of 38 MHz. OC: optical
coupler, FRM: Faraday rotating mirror, AOM: acousto-optic modulator, PD:
photo-detector, BPF: band-pass filter.

###  III-B The spectrum characterization of the optical frequency comparison

The frequency-domain characterization of the optical frequency comparison
expressed as the phase noise PSD is shown in Fig. 4. The phase noise PSD of
the free-running fiber link (black line) evaluated by the 33 MHz beating
signal approximately follows a power-law dependence of $S_{\phi}(f)=100f^{-2}$
for $f\leq 1$ kHz. By performing the proposed TD-LTW optical frequency
comparison scheme, the residual phase noise PSD illustrates a $h_{0}f^{0}$
dependence, as drawn by the purple curve, which is almost consistent with the
theoretical prediction as expressed by Eq. (20). As a comparison, by removing
the time delay fiber, the residual phase noise PSD of the conventional LTW
scheme is also measured, as illustrated by the green curve. Its value is about
four times higher than that of the TD-LTW scheme, demonstrating that an 6-dB
enhancement the in phase noise reduction can be achieved by using the proposed
TD-LTW optical frequency comparison scheme.

Figure 4: The measured phase noise PSDs of the 50-km free-running link (black
curve) and the phase noise suppressed link based on the LTW optical frequency
comparison scheme (green curve) and the TD-LTW optical frequency comparison
scheme (violet curve). The theoretical phase PSDs of the delay-unsuppressed
residual phase noise predicted by Eq. 19 (red curve) and Eq. 20 (blue curve)
are also presented. Figure 5: The measured fractional frequency instabilities
of optical frequency comparison using two different fiber spools. The black
triangles, gray triangles, blue squares, orange circles, and red circles are
the results of the 50-km free-running link, noise floor, LTW scheme, TD-LTW
scheme, and TWC scheme, respectively. These measurements are conducted by a
non-averaging ($\Pi$-type) frequency counter, expressed as the ADEV.

###  III-C The stability and accuracy of optical frequency comparison

To further investigate the instability of optical frequency comparison, we
measured the fractional frequency instability characterized by the ADEV as
shown in Fig. 5 (a) and (b). In Fig. 5 (a), it can be seen that the fractional
frequency instability of the free running link (black triangle) fluctuates in
the $10^{-14}$ level, which is not adequate for the current optical clocks. By
removing the time delay fiber, the setup in Fig. 3 functions as the
conventional LTW optical frequency comparison scheme. In this case, the ADEV
decreases from $1.30\times 10^{-15}$ at 1 s integration time to $1.44\times
10^{-19}$ at 10,000 s with a slope of $\tau^{-1}$. After adding a 50 km time
delay fiber, the ADEV scales down from $5.25\times 10^{-16}$ at 1 s to
$9.50\times 10^{-20}$ at 10,000 s, which approaches the performance of the TWC
scheme. The fractional frequency instability of the LTW and TD-LTW schemes
using another fiber spool is shown in Fig. 5 (b), whose values at 1 s
integration time are $1.34\times 10^{-15}$ and $7.25\times 10^{-16}$,
respectively. According to the measured ADEV, the experimental improvement
factors for the two cases are 2.48 and 1.85, respectively. It is important to
stress that the improvement could be achieved by acquiring the frequency
counter with the $\Lambda$-mode [32], which will be comprehensively
investigated in our future work. The deviation from the theoretical
improvement factor by Eq. (19) and (20) can be attributed to the inhomogeneous
phase noise perturbation on the fiber link as discussed in the section II. As
a comparison, we also measured the noise floor by replacing the fiber link
with a short fiber. We can clearly see that the long term stability is limited
by $10^{-19}$, which is mainly due to the phase noise introduced by the out-
of-loop path [33, 34].

Figure 6: Frequency deviation of the optical frequency comparison. These
results were measured by a dead-time free $\Pi$-type frequency counter at 1 s
gate time over 25 hours (green points, left axis). The unweighted mean values
of all all cycle-slip free 100 s intervals are shown by the black points
(right axis).

Considering that the accuracy of the frequency comparison can not be presented
in the instability analysis, we measured the frequency deviation using an
$\Pi$-type frequency counter, which worked at 1 s gate time. Here, we measured
two spool fibers as used in the fractional frequency instability evaluation.
For the first fiber spool, the frequency deviation of the LTW scheme over
successive 90000 s was recorded, shown in Fig. 6 (a) by the green points. By
averaging the data every 100 seconds, 900 data points (black points, right
frequency axis) are produced, as also shown in Fig. 6 (a). The 900 data points
have an arithmetic mean of 41.5 $\mu$Hz ($2.15\times 10^{-19}$) and a standard
deviation of 2.08 mHz ($1.08\times 10^{-17}$). The frequency deviation of the
TD-LTW scheme is shown in Fig. 6 (b), whose 900 averaged points have an
arithmetic mean of 2.95 $\mu$Hz ($1.03\times 10^{-20}$) and a standard
deviation of 0.875 mHz ($4.04\times 10^{-18}$). Thus, the statistical
fractional frequency uncertainties of the conventional LTW and the TD-LTW
optical frequency comparison schemes are $3.60\times 10^{-19}$ and $1.35\times
10^{-19}$, respectively. These values satisfy the requirement of the most
accurate optical clocks to date. Following the same procedure, we also
evaluate the frequency comparison accuracy of the LTW and TD-LTW schemes for
the second fiber spool. The mean frequency offset and the standard deviation
of 792 data points in the total 79200 seconds of the LTW scheme are 36.5
$\mu$Hz ($1.89\times 10^{-19}$) and 2.04 mHz ($1.05\times 10^{-17}$),
respectively, and that of the TD-LTW scheme are 0.65 $\mu$Hz ($3.38\times
10^{-21}$) and 1.27 mHz ($0.65\times 10^{-17}$), respectively. Thus, the
statistical fractional frequency uncertainties of the conventional LTW and the
TD-LTW optical frequency comparison schemes are $3.73\times 10^{-19}$ and
$2.31\times 10^{-19}$, respectively.

Figure 7: The measured improvement factors achieved by the TD-LTW scheme. The
data points here are all obtained by the second fiber spool. The green curve
is calculated under the assumption of homogeneous phase noise perturbation.
The blue curve represents the theoretical improvement factor under the
inhomogeneous phase noise perturbation, whose distribution follows the blue
line in the inset.

To further analyze the dependence of the fractional frequency instability on
the time delays $\delta\tau$, we measured the fractional frequency
instabilities of the optical frequency comparison based on the TD-LTW optical
frequency comparison scheme with the different time delay. The time delay was
changed by changing the length of the delay fiber before the PD2. The
improvement factors of the ADEV using the second fiber spool at the 1 s, 10 s,
100 s, and 1000 s integration time are drawn in Fig. 7. Moreover, the
theoretical improvement factors under the homogeneous and inhomogeneous phase
noise perturbations are plotted by the green and blue curves, respectively. In
this case, it is clear that the 50-km delay fiber approaches the optimal
value.

###  III-D The influence of the inhomogeneous phase noise perturbation

To further investigate the influence of the inhomogeneous phase noise
perturbation on the fractional frequency stability of the LTW and TD-LTW
scheme, an artificial perturbation is applied to stimulate the inhomogeneous
phase noise case. Here, two 25 km optical fiber spools were connected to form
an 50 km fiber link, one of which was blown by an electric fan and the other
was placed in a quiet position. By exchanging two ends of the fiber link, the
phase noise distributions like the case 1 and 3 in Fig. 2 are experimentally
generated, and the measured ADEV of the LTW and TD-LTW schemes is shown in
Fig. 8. It can be seen that the instability of the LTW scheme is higher when
the artificial phase noise perturbation is concentrated on the first span of
the fiber link, which is consistent with the above theoretical analysis.
Quantitatively, when the front 25 km fiber spool is blown by the electric fan,
the ADEV of the LTW and TD-LTW schemes follows the dependence of $3.79\times
10^{-15}/\tau^{\prime}$ and $1.58\times 10^{-15}/\tau^{\prime}$, respectively.
Here, $\tau^{\prime}$ represents the averaging time. After exchanging the
connection ends between the fiber link and the sites, the ADEV of the LTW and
TD-LTW schemes follows the dependence of $2.78\times 10^{-15}/\tau^{\prime}$
and $1.55\times 10^{-15}/\tau^{\prime}$, respectively, demonstrating that the
improvement factors of the two cases are 2.39 and 1.76, respectively.

Figure 8: The measured fractional instability of the optical frequency
comparison under the artificial phase noise perturbation on the fiber link.
The results presented by the blue squares and triangles are measured when the
front 25 km fiber spool was blown by an electric fan and the other was placed
in a quiet position. The red ones are obtained by exchanging the connection
ends between the fiber link and the sites.

##  IV Discussion and conclusion

In section II, two configurations of the frequency comparison module are
proposed to conduct the TD-LTW technique, based on the optical time delay or
the electrical time delay, and the first one was adopted to generate the
desired time delay in this work. For the second method, the configuration
adopted in [21] is recommended, in which the phase variation is converted into
the voltage variation, sampled and processed by a digital circuit. We think
the two methods are suitable for different cases. For the short transfer link,
the method of optical delay is preferable, because a high sampling rate of the
electrical delay method is required to generate the short time delay. However,
for the long transfer link, the optical delay will introduce high attenuation
on the transferred optical frequency signals, which makes the electrical delay
as a better choice. In the practical application, the two methods can be
adopted simultaneously, where the electrical delay generates the coarse time
delay and the optical delay tunes the fine time delay.

In conclusion, we proposed a TD-LTW optical frequency comparison technique,
which can enhance the phase noise reduction in the localized optical two-way
optical frequency comparison. The proposed scheme reserves the advantage of
the LTW optical frequency comparison scheme, which can accomplish the data
acquisition at one site, guaranteeing the synchronization of data acquisition.
This capability also promises the high-performance, real-time frequency
comparison technique for the two distant optical signals rather than post
processing as demonstrated in the TWC optical frequency comparison scheme [22,
23] and the optical frequency transfer scheme [27]. The experimental results
demonstrate that the measured stability of optical frequency comparison is
improved from $1.30\times 10^{-15}$ to $5.25\times 10^{-16}$ at the 1 s
integration time. In the future work, we are planning to integrate the
proposed TD-LTW optical frequency comparison scheme into the bus or ring
topology structures to provide the potential of optical clock comparison over
large area with a higher stability.

## References

  * [1] I. Ushijima, M. Takamoto, M. Das, T. Ohkubo, and H. Katori, “Cryogenic optical lattice clocks,” _Nature Photonics_ , vol. 9, no. 3, pp. 185–189, 2015.
  * [2] S. Brewer, J.-S. Chen, A. Hankin, E. Clements, C.-W. Chou, D. Wineland, D. Hume, and D. Leibrandt, “27Al+ quantum-logic clock with a systematic uncertainty below $10^{-18}$,” _Physical Review Letters_ , vol. 123, no. 3, p. 033201, 2019.
  * [3] T. Nicholson, S. Campbell, R. Hutson, G. Marti, B. Bloom, R. McNally, W. Zhang, M. Barrett, M. Safronova, G. Strouse _et al._ , “Systematic evaluation of an atomic clock at 2$\times 10^{-18}$ total uncertainty,” _Nature Communications_ , vol. 6, no. 1, pp. 1–8, 2015.
  * [4] B. Wang, X. Zhu, C. Gao, Y. Bai, and L. J. Wang, “Square kilometer array telescope - precision reference frequency synchronisation via 1f-2f dissemination,” _Scientific Reports_ , vol. 5, p. 13851, 2015.
  * [5] Y. He _et al._ , “Long-distance telecom-fiber transfer of a radio-frequency reference for radio astronomy,” _Optica_ , vol. 5, no. 2, pp. 138–146, 2018.
  * [6] J. Grotti _et al._ , “Geodesy and metrology with a transportable optical clock,” _Nature Physics_ , vol. 14, pp. 437–441, 2018.
  * [7] C. Clivati, R. Ambrosini, T. Artz, A. Bertarini, C. Bortolotti, M. Frittelli, F. Levi, A. Mura, G. Maccaferri, and M. Nanni, “A VLBI experiment using a remote atomic clock via a coherent fibre link,” _Scientific Reports_ , vol. 7, p. 40992, 2017.
  * [8] C. Clivati _et al._ , “A coherent fiber link for very long baseline interferometry,” _IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control_ , vol. 62, no. 11, pp. 1907–1912, 2015.
  * [9] S. Kolkowitz, I. Pikovski, N. Langellier, M. D. Lukin, and J. Ye, “Gravitational wave detection with optical lattice atomic clocks,” _Physical Review D_ , 2016.
  * [10] L. Hu, N. Poli, L. Salvi, and G. M. Tino, “Atom interferometry with the Sr optical clock transition,” _Physical Review Letters_ , vol. 119, no. 26, p. 263601, 2017.
  * [11] L. S. Ma, P. Jungner, J. Ye, and J. L. Hall, “Delivering the same optical frequency at two places: accurate cancellation of phase noise introduced by an optical fiber or other time-varying path,” _Optics Letters_ , vol. 19, no. 21, pp. 1777–1779, 1994.
  * [12] S. M. Foreman, A. D. Ludlow, M. H. De Miranda, J. E. Stalnaker, S. A. Diddams, and J. Ye, “Coherent optical phase transfer over a 32-km fiber with 1 s instability at 10- 17,” _Physical Review Letters_ , vol. 99, no. 15, p. 153601, 2007.
  * [13] F. Kéfélian, H. Jiang, S. Crane, O. Lopez, M. Lours, J. Millo, D. Holleville, P. Lemonde, C. Chardonnet, and A. Amy-Klein, “Long-distance frequency transfer over an urban fiber link using optical phase stabilization,” _Josab/25/12/josab Pdf_ , vol. 25, no. 12, pp. 2029–0, 2008\.
  * [14] P. A. Williams, W. C. Swann, and N. R. Newbury, “High-stability transfer of an optical frequency over long fiber-optic links,” _J. Opt. Soc. Amer. B_ , vol. 25, no. 8, pp. 1284–1293, 2008.
  * [15] F. Kéfélian, O. Lopez, H. Jiang, C. Chardonnet, and G. Santarelli, “High-resolution optical frequency dissemination on a telecommunication network with data traffic,” _Optics Letters_ , vol. 34, no. 10, pp. 1573–5, 2009.
  * [16] G. Grosche _et al._ , “Optical frequency transfer via 146 km fiber link with $10^{-19}$ relative accuracy,” _Optics Letters_ , vol. 34, no. 15, pp. 2270–2272, 2009.
  * [17] K. Predehl _et al._ , “A 920-kilometer optical fiber link for frequency metrology at the 19th decimal place,” _Science_ , vol. 336, no. 6080, p. 441, 2012.
  * [18] S. Droste, F. Ozimek, T. Udem, K. Predehl, and R. Holzwarth, “Optical-frequency transfer over a single-span 1840 km fiber link.” _Physical Review Letters_ , vol. 111, no. 11, p. 110801, 2014.
  * [19] L. Hu, X. Tian, L. Wang, G. Wu, and J. Chen, “Passive optical phase stabilization on a ring fiber network,” _Journal of Lightwave Technology_ , vol. 38, no. 21, pp. 5916–5924, 2020.
  * [20] L. Hu, X. Tian, G. Wu, and J. Chen, “Passive optical phase noise cancellation,” _Optics Letters_ , vol. 45, no. 15, pp. 4308–4311, 2020.
  * [21] C. E. Calosso, E. Bertacco, D. Calonico, C. Clivati, G. A. Costanzo, M. Frittelli, F. Levi, A. Mura, and A. Godone, “Frequency transfer via a two-way optical phase comparison on a multiplexed fiber network,” _Optics Letters_ , vol. 39, no. 5, pp. 1177–1180, 2014.
  * [22] A. Bercy _et al._ , “Two-way optical frequency comparisons at 5$\times$ 10-21 relative stability over 100-km telecommunication network fibers,” _Physical Review A_ , vol. 90, no. 6, p. 061802, 2014.
  * [23] F. Stefani _et al._ , “Tackling the limits of optical fiber links,” _Journal of the Optical Society of America B_ , vol. 32, no. 5, pp. 787–797, 2015.
  * [24] W. K. Lee, F. Stefani, A. Bercy, O. Lopez, A. Amy-Klein, and P. E. Pottie, “Hybrid fiber links for accurate optical frequency comparisons,” _Applied Physics B_ , vol. 123, no. 5, p. 161, 2017.
  * [25] O. Lopez, A. Haboucha, F. Kéfélian, H. Jiang, and G. Santarelli, “Cascaded multiplexed optical link on a telecommunication network for frequency dissemination,” _Optics Express_ , vol. 18, no. 16, 2010.
  * [26] N. Chiodo, N. Quintin, F. Stefani, F. Wiotte, E. Camisard, C. Chardonnet, G. Santarelli, A. Amy-Klein, P.-E. Pottie, and O. Lopez, “Cascaded optical fiber link using the internet network for remote clocks comparison,” _Optics Express_ , vol. 23, no. 26, pp. 33 927–33 937, 2015.
  * [27] C. Calosso _et al._ , “Doppler-stabilized fiber link with 6-dB noise improvement below the classical limit,” _Optics Letters_ , vol. 40, no. 2, pp. 131–134, 2015.
  * [28] L. Hu, R. Xue, X. Tian, G. Wu, and J. Chen, “All-passive multiple-place optical phase noise cancellation,” _Optics Letters_ , vol. 46, no. 6, pp. 1381–1384, 2021.
  * [29] L. Hu, X. Tian, G. Wu, M. Kong, J. Shen, and J. Chen, “Multi-node optical frequency dissemination with post automatic phase correction,” _Journal of Lightwave Technology_ , vol. 38, no. 14, pp. 3644–3651, 2020.
  * [30] A. Tampellini, C. Clivati, F. Levi, A. Mura, and D. Calonico, “Effect of a timebase mismatch in two-way optical frequency transfer,” _Metrologia_ , vol. 54, no. 6, pp. 805–809, 2017.
  * [31] J. Y. Won and J. S. Lee, “Time-to-digital converter using a tuned-delay line evaluated in 28-, 40-, and 45-nm fpgas,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 65, no. 7, pp. 1678–1689, 2016.
  * [32] S. T. Dawkins, J. J. McFerran, and A. N. Luiten, “Considerations on the measurement of the stability of oscillators with frequency counters,” _IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control_ , vol. 54, no. 5, pp. 918–925, 2007.
  * [33] R. Xue, L. Hu, J. Shen, J. Chen, and G. Wu, “Branching optical frequency transfer with enhanced post automatic phase noise cancellation,” _Journal of Lightwave Technology_ , vol. 39, no. 14, pp. 4638–4645, 2021\.
  * [34] L. Hu, R. Xue, G. Wu, and J. Chen, “Performance of digital servos in an optical frequency transfer network,” _Review of Scientific Instruments_ , vol. 92, no. 5, p. 053709, 2021.


# Cleared for Takeoff? Compositional & Conditional Reasoning may be the
Achilles Heel to (Flight-Booking) Language Agents

Harsh Kohli & Huan Sun
Department of Computer Science and Engineering
The Ohio State University
Columbus, OH 43201, USA
<EMAIL_ADDRESS>

###### Abstract

The rapid progress of large language models (LLMs) has seen them excel and
frequently surpass human performance on standard benchmarks. This has enabled
many downstream applications, such as LLM agents, to rely on their
sophisticated reasoning to navigate complex task requirements. However, LLMs
are known to unexpectedly falter in simple tasks and under seemingly
straightforward circumstances - underscoring the need for better and more
diverse evaluation setups to measure their true capabilities. To this end, we
choose to study compositional and conditional reasoning, two cornerstones of
human cognition, and introduce GroundCocoa - a lexically diverse benchmark
connecting these reasoning skills to the real-world problem of flight booking.
Our task involves aligning detailed user preferences with available flight
options presented in a multiple-choice format. Results indicate a significant
disparity in performance among current state-of-the-art LLMs with even the
best performing model, GPT-4 Turbo, not exceeding 67% accuracy despite
advanced prompting techniques.

##  1 Introduction

Advanced reasoning in LLMs has significantly influenced and effected the rise
to prominence of language agents adept at handling a diverse range of tasks
(Shen et al., 2024; Wu et al., 2023; Schick et al., 2024; Significant
Gravitas, ; Osika, 2023). Among them, web agents (Hong et al., 2023; Furuta et
al., 2023; Deng et al., 2024; Zheng et al., 2024) have demonstrated potential
in automating web-based tasks such as flight booking. While such success
through widespread application of LLMs is indeed promising, it necessitates
ongoing exploration of their core reasoning proficiencies. Conditional and
compositional reasoning play a crucial role in our ability to understand and
interact with complex systems through elaborate decision-making (Oaksford &
Chater, 2010; Simon & Newell, 1971). Conditional reasoning involves the
comprehension and application of logical rules that are typically structured
in “if-then” formats. It is critical to personal decision-making in everyday
life through an evaluation of potential scenarios and anticipation of
consequences. Compositional reasoning, on the other hand, is the ability to
combine solutions to simpler sub-problems, and integrate them in a structured
manner to solve a more complex task. This cognitive process entails
understanding the interplay between different sub-problems. Our paper focuses
on assessing how well current LLMs encapsulate these essential cognitive
functions, which are integral to both human intelligence and advanced
artificial intelligence systems. To that end, we introduce
GroundCocoa111https://osu-nlp-group.github.io/GroundCocoa/ \- a benchmark for
evaluating compositional & conditional reasoning in a grounding task.

GroundCocoa is made up of questions framed as user needs, set within a real-
world inspired flight reservation scenario. User requirements might be many or
could be highly convoluted - leading to higher compositional and conditional
complexity respectively. We leverage a controllable method to create samples
of varying complexity (examples are provided in Appendix B). Our data
generation process, described in greater detail in Section 2, consists of a
5-stage pipeline including online scraping, constraint generation, and
symbolic logic to impose conditionality. In order to test for robustness, we
allow requirements to freely condition on one another and impose no
restrictions on their nature. Additionally, we isolate a subset of more
atypical queries that contain unconventional user needs (e.g., ”I want at
least 2 layovers”) and evaluate their impact on model performance. Samples in
GroundCocoa may also require reasoning about time (e.g. when constraints are
imposed on arrival or departure times) and arithmetic (e.g. when constraints
are imposed on ticket price), thus, integrating logical, temporal,
mathematical, and compositional reasoning.

The statistics of our dataset are shown in Table 1. Our key findings are as
follows:

  1. 1.

Accuracy among contemporary LLMs varies greatly, ranging from a little better
than random guess to about 67% on a five-option multiple-choice question task.
Within this spectrum, GPT-4 Turbo (OpenAI, 2023) stands out, demonstrating a
superior capacity of the GPT line of models to adapt and excel in novel
reasoning tasks. However, conditional reasoning poses a significant challenge
to all evaluated models, even on samples of relatively lower complexity.

  2. 2.

Chain of Thought (COT) prompting (Wei et al., 2022) leads to mixed results,
with only a modest improvement in model performance in some cases. Prior
research has noted that although COT helps decompose problems into steps, LLMs
increasingly struggle as the complexity of the individual steps escalates
(Hendrycks et al., 2021b; Madaan & Yazdanbakhsh, 2022; Nogueira et al., 2021;
Qian et al., 2023). These assertions hold true in our observations.

  3. 3.

Including unconventional user requirements leads to a drop in accuracy of as
much as 6% in GPT-4 Turbo, indicating a pretraining bias towards more typical
needs.

Figure 1: Gemini-Pro and GPT-4 Turbo responses for a flight requirement with
single option and a simplified schema.

##  2 Approach

Figure 2 illustrates our proposed approach. In the process of generating a
natural language user requirement for flight booking, we are faced with the
following considerations:

Conditionality of Constraints: We wish to challenge contemporary models in
their ability to reason through scenarios characterized by conditional
complexity. This is done through mutual dependence of flight features which we
refer to as slots. In the example illustrated in Figure 2, there is an inter-
dependence between the values for price and ticket class. The interplay
between constraints corresponding to the different slots is represented in
logical form through a Product-of-Sums (POS) expression. A POS expression
consists of multiple OR operations (sums) which are later combined through AND
operations (products). The inclusion of OR operations between slots introduces
conditional complexity to our user requirement, necessitating consideration of
potential slot values in if-then scenarios. On the other hand, a greater
number of AND conditions implies a higher number of variables that a model has
to simultaneously reason over resulting in increased compositional complexity.

Satisfiability of POS Expression: While generating the logical form for a user
requirement, we must ensure satisfiability of the generated POS expression.
For this, we use SymPy (Meurer et al., 2017) \- an open-source Python symbolic
mathematics library which generates an optimal POS expression given a minterm
table. This is further described in Section 2.2.

Fuzziness in Slot Values: Corresponding to each occurrence of a slot in the
POS expression there has to be a unique constraint. For the example in Figure
2, the two constraints on the price slot are {$<$$12400$, $<$$500$}. These
constraints are randomly imposed through specialized rule-based systems
corresponding to each slot. However, these might cause the final user criteria
to become impossible to satisfy even if the corresponding POS expression in
satisfiable. Thus, for a generated user requirement we check our flight data
to ensure that there exists at least one route that satisfies the criteria and
at least 4 that do not. This way we ensure there is at least one positive and
4 negative options for a generated requirement.

Statistics of GroundCocoa are shown in Table 1. We also include a separate
validation set which may be used for tuning hyperparameters. Our 5-stage data
creation pipeline is detailed in the subsequent sections.

Figure 2: Stepwise depiction of GroundCocoa query generation using 2 slots and
2 minterms.

###  2.1 Flight Data Collection

We use a list of the top 50 busiest airports by passenger traffic derived from
Wikipedia222https://en.wikipedia.org/wiki/List_of_busiest_airports_by_passenger_traffic.
Source and destination airports are chosen randomly from this list and input
to Google Flights333https://www.google.com/travel/flights with the departure
date set for April 17, 2024. A small number of flights are sampled from search
results for each source-destination pair. The sampled flights are chosen from
each of economy, business, and first class and, for each flight option, all
the relevant details such as the number of layovers, price, departure and
arrival times etc. are saved. A sample flight schema with all the elements is
provided in Appendix A. The entire data collection process is handled through
web scraping using Selenium
Webdriver444https://www.selenium.dev/documentation/webdriver/.

###  2.2 Product-of-Sums Generation

To generate a POS expression, we first randomly select a small number of
flight features or slots. The complete set of slots for any given flight is as
follows:

{airline, ticket class, departure time, arrival time, total travel time,
number of layovers, average carbon emission difference, travel date, price,
layover locations, layover times}

We vary the number of slots between 2 and 6 in order to generate samples of
differing complexity. We then randomly generate 2-3 ”minterms” - the list of
all input combinations of slots that generate a ”1”. A higher number of
minterms results in a greater conditional complexity and leads to more
convoluted user requirements. The slot symbols and generated minterms are
input to SymPy which uses a redundant-group eliminating algorithm to output
the smallest POS expression consistent with the minterm table.

Statistic | (slot, minterm) configurations | Total
---|---|---
(2,2) | (3,2) | (4,2) | (4, 3) | (5,2) | (6,2)
Test Samples | 1511 | 1083 | 710 | 723 | 451 | 371 | 4849
Test Unique Queries | 124 | 136 | 117 | 129 | 121 | 101 | 728
Val. Samples | 17 | 17 | 8 | 5 | 2 | 3 | 52
Val. Unique Queries | 1 | 1 | 1 | 1 | 1 | 1 | 6
Avg. Query Length | 65.04 | 88.33 | 103.88 | 119.14 | 124.56 | 148.87 | 95.95
Avg. Context Length | - | - | - | - | - | - | 1252.27
Vocab Size | - | - | - | - | - | - | 4200
Table 1: Key Statistics of Ground Cocoa.

###  2.3 Primitive Generation

Corresponding to each slot, we have developed a rule-based system that
randomly imposes constraints on its values. These constraints are converted to
natural language through templates. Since a POS expression may contain a
negation, we generate two primitives at each turn - one for the constraint and
one for its negation. A sample primitive for total travel time is shown in
Table 2.

TravelTime | Travel Time should be more than 22 hours and 30 minutes.
---|---
$\neg$TravelTime | Travel Time should not be more than 22 hours and 30 minutes.
Table 2: Sample primitive generated from templates for total travel time.

At this stage, we also isolate samples that include any one of the following
three primitives - (1) carbon emissions must be above the average for that
route, (2) price of the flight must be above a minimum threshold, and (3)
number of layovers on the route should be greater than a minimum. While this
list is not exhaustive, such samples (henceforth referred to as ”atypical”
queries) are able to successfully encapsulate contrarian needs that are
unlikely to manifest often during pretraining.

###  2.4 LLM Paraphrasing and Human Validation

We carry out LLM paraphrasing in two distinct steps described below. The exact
prompts and an example of intermediate results are provided in Appendix D. We
manually verify each query to ensure it is consistent with the primitives and
make changes wherever necessary.

  1. 1.

Individual primitives are substituted into each sum term and combined using
templated rules. We then use GPT-4 Turbo to paraphrase each of the sum terms.

  2. 2.

Next, we combine the individual sum terms into a product (logical AND). This
is done by merging the individual paraphrases of sum terms, separated by
periods. The resulting flight requirement is again paraphrased with GPT-4
Turbo.

###  2.5 Option Matching

We match the generated user requirements with the flight data collected in
Section 2.1. Each route between the source and destination represents a
potential choice in our multiple-choice dataset. Choices are divided into
subsets containing one positive (matching the user requirement) and four
negative (not matching the user requirement) options. This is done to ensure
that each multiple-choice question has only a single correct answer for ease
of evaluation. Many such subsets may be created from a single user requirement
and, consequently, our dataset consists of queries repeated multiple times
with differing choices. Details on the number of unique queries and overall
samples is provided in Table 1.

##  3 Results & Analysis

To measure performance on GroundCocoa, we test several models of different
sizes ranging from open-source to closed-source, including LLAMA 2-chat
(Touvron et al., 2023), Mixtral 8x7B - Instruct (Jiang et al., 2024) / Mistral
7B Instruct(Jiang et al., 2023), Gemini Pro(Team et al., 2023), and GPT-4
Turbo. We also test selected larger models with an in-context example using
chain-of-thought (CoT) (Wei et al., 2022) reasoning. Since our task involves
grounding user requirements to each answer choice, the CoT explanations are
provided for each flight option given the user requirement. Thus, our standard
CoT (CoT-full) consists of 5 distinct explanations. On GPT-4, we empirically
observe that the large resulting context length can often prove detrimental to
model performance with the models often confusing between the requirements and
options of the test case and the exemplar. To address this, we try a different
prompting strategy (CoT-partial) with only two flight choices (1 positive and
1 negative) for the in-context example. Due to limitations on context length
(4096 tokens) we are unable to run LLAMA 2-chat 70B on CoT-full. The exact
prompts are given in Appendix C. Results from our experiments are shown in
Table 3.

| Regular | Atypical | Total
---|---|---|---
Open-source Models |  |  |
LLAMA 2-chat 7B | 14.56 | 14.66 | 14.60
Mistral 7B Instruct | 25.70 | 26.10 | 25.86
LLAMA 2-chat 13B | 16.33 | 16.06 | 16.23
Mixtral 8x7B-Instruct | 45.79 | 42.48 | 44.48
Mixtral 8x7B-Instruct + CoT-full | 34.38 | 32.65 | 33.69
Mixtral 8x7B-Instruct + CoT-partial | 41.38 | 39.85 | 40.15
LLAMA 2-chat 70B | 24.13 | 21.63 | 23.13
LLAMA 2-chat 70B + CoT-partial | 25.73 | 23.97 | 25.03
Closed-source Models |  |  |
Gemini Pro | 42.79 | 40.46 | 41.86
Gemini Pro + CoT-full | 41.14 | 40.87 | 41.04
Gemini Pro + CoT-partial | 34.82 | 33.85 | 34.44
GPT-4 Turbo | 64.66 | 58.81 | 62.34
GPT-4 Turbo + CoT-full | 65.07 | 61.51 | 63.66
GPT-4 Turbo + CoT-partial | 67.77 | 65.62 | 66.92
Table 3: Accuracy Results (in percentage) on GroundCocoa.

As alluded to previously, GroundCocoa presents a substantial challenge for
each of the evaluated models, even with CoT prompting. The CoT-partial
strategy with only 2 options and explanations leads to better results than
CoT-full in 2 out of 3 cases where we have experimented with both, and best
results are obtained using GPT-4 Turbo with CoT-partial. It is noteworthy,
though, that there exists a marked difference in performance between GPT-4
Turbo and the remaining models. Such a degree of variation represents a
significant departure from the usual performance patterns observed in popular
benchmarks such as MMLU (Hendrycks et al., 2021a), HellaSwag (Zellers et al.,
2019), ARC Reasoning Challenge (Clark et al., 2018), WinoGrande (Sakaguchi et
al., 2021), and GSM-8K (Cobbe et al., 2021) among others, where results are
much more comparable.

Beyond assessing the overall model performance, we also investigate the
consequences of varying the complexity of user criteria and presenting
relatively unconventional user needs.

###  3.1 Impact of Increasing Complexity

In our analysis, we observe the performance of GPT-4 Turbo, the most effective
model from among those tested on GroundCocoa across different levels of
conditional and compositional complexity. In their recent work on assessing
the limitations of transformer on compositional tasks, Dziri et al. (2023) use
computational graphs as approximations of the underlying reasoning processes
in such models. They define the terms reasoning depth, the length of the
deepest layer in the computational graph from the source nodes, and reasoning
width, the mode of number of nodes in each layer - indicating the extent of
multi-hop reasoning and compositional parallelism required to solve a given
problem. Considering the characteristics of GroundCocoa we focus on reasoning
width - the number of variables a model has to simultaneously reason over for
a given problem. Intuitively, this may be represented by the number of slots
used during the generation of a particular sample as described in Section 2.2.
However, keeping the number of rows in the minterm table constant while
increasing the slots may often lead to lower conditional complexity as the
number of slots is increased.

Figure 3: An example of POS expression and its corresponding dependency graph.

In order to effectively gauge the compositional and conditional complexity of
a sample in our dataset, we define a dependency graph derived from the POS
expression corresponding to that sample. Vertices represent slots and a
dependency (edge) is created when a particular slot co-occurs with another
slot within a sum term in the POS. A sample POS expression and its
corresponding dependency graph are shown in Figure 3. The graph has 3
connected components with the largest connected component (LCC) of size 4. The
maximum degree is 2 which corresponds to the two connections for nodes
LayoverTime and TicketClass.

Figure 4: Effect of increasing complexity in evaluation samples.

Given a fixed-schema for the flight options, the number of sum terms in the
POS expression as well as the LCC in the dependency graph are indicative of
the reasoning width and, in turn, the compositional complexity of the user
criteria. The LCC is the length of the largest chain of slots - the possible
values of which are dependent on one another through OR conditions
(represented by edges in the dependency graph). This metric effectively
reflects the breadth of parallel computation or reasoning width required to
accurately infer the given user criteria. Since increased branching in the
dependency graph suggests a greater conditional complexity in user criteria,
we also analyze model performance with increasing maximum degree of the
dependency graph. This gives us the extent of conditioning on a single slot
value. In Figure 4 we observe the decline in model performance with increased
complexity as indicated by these factors.

###  3.2 Quantifying Confusion in Answer Choices through Entropy

Numerous recent studies have explored how deep learning models, specifically
transformer-based architectures, achieve success by exploiting shortcuts
(Geirhos et al., 2020; Liu et al., 2022; Tang et al., 2023; Du et al., 2023)
and relying on spurious correlations present in the training data (Zhang et
al., 2023; Saparov & He, 2023; Saparov et al., 2023). Most recently, Dziri et
al. (2023) utilized relative information gain of individual output elements in
partially correct answers to explain surface pattern understanding in LLMs. In
the same vein, we employ entropy as a metric to measure the confusion that
might be caused due to conditions in the user query for a given flight option.
We do this in an attempt to demystify how language models may succeed at some
and fail at other queries with similar levels of complexity. In order to
illustrate this, we take an example user requirement, and two hypothetical and
simplified flight options as shown in Figure 5. Additionally, we show the
reasoning path that must be navigated in each case for a successful outcome.

Figure 5: Sample user requirement and two hypothetical flight options.

We observe how option B in our example leads to a more convoluted reasoning
path, whereas the model is able to bypass considerable conditional overhead in
the case of Option A. For the purpose of quantifying this more generally, we
observe the compositional primitives (values attached to individual slots in
the POS expression) in each sample and attach a binary value indicating if the
primitive is satisfied. For the example in Figure 5, we show the primitives
and the corresponding values of both options in Figure 6. We also show the
probability of a primitive being satisfied($p_{sat}$) and being
unsatisfied($p_{\bar{sat}}$) by the flight option under consideration, as well
as the final entropy.

Figure 6: Satisfaction of individual primitives and corresponding entropy.

Figure 7: Effect of increasing entropy in answer choice of evaluation samples.

Entropy due to user criteria for each option can then be computed using the
formula in Equation 1. Higher uncertainty leads to greater entropy in Option B
as opposed to Option A, indicating a greater conditional overhead.

$H(X)=-(p_{sat}logp_{sat}+p_{\bar{sat}}logp_{\bar{sat}})$ (1)

In our analysis, we take the entropy values of the correct answer choice for
each sample. Figure 7 shows the densities of entropy values for the correct
and wrong predictions of GPT-4 Turbo on GroundCocoa. While correct predictions
exceed wrong predictions at lower entropy values, an abrupt surge in wrong
predictions is observed at higher entropy levels. Thus, entropy gives us yet
another measure of conditional complexity from the perspective of the answer
choices rather than just the query, and helps explain why a model might
exhibit inconsistent results across user queries of similar complexity.

###  3.3 Robustness to Unconventional User Needs

Several contemporary studies have sought to examine the robustness of language
models by studying their resilience to out-of-distribution data (Koh et al.,
2021; Wang et al., 2023) or through adversarial attacks and input
perturbations (Gardner et al., 2020; Goel et al., 2021; Subhash et al., 2023;
Sanyal et al., 2022; Yuan et al., 2023). In our work, we challenge models
through atypical user requirements in order to assess bias from pretraining
and robustness to unorthodox and nontraditional queries. We segregate queries
into ”Regular” and ”Atypical” groups as described in Section 2.3. In Table 3,
we contrast model performance on samples that describe such unconventional
user needs versus those that do not. While most models in our testing show a
decay in performance, the impact is more noticeable on better performing
models such as GPT-4 Turbo. The in-context example used for all queries when
testing with CoT includes two such primitives (ticket price $>$ 1800, carbon
emission above average). We observe that the decline in performance is less
pronounced with CoT.

##  4 Related Work

Reasoning Challenges in NLP. Our work extends the existing line of research on
evaluating natural language processing (NLP) systems on different facets of
reasoning - most notably commonsense question-answering (Talmor et al., 2019;
Huang et al., 2019), physical reasoning (Bisk et al., 2020), social
interaction (Sap et al., 2019), mathematical reasoning (Cobbe et al., 2021;
Amini et al., 2019; Miao et al., 2020; Hendrycks et al., 2021b), story
completion (Zellers et al., 2019), temporal reasoning (Zhou et al., 2019; Tan
et al., 2023) abductive reasoning (Bhagavatula et al., 2020) and pronoun
resolution (Sakaguchi et al., 2021) among others. Different from these
benchmarks, GroundCocoa introduces a unique and substantial challenge for LLMs
in the form of conditional and compositional reasoning.

Benchmarks on Propositional Logic. GroundCocoa also aligns with the
considerable body of work on evaluating logical reasoning in language models.
The RuleTaker (Clark et al., 2021) and ProofWriter (Tafjord et al., 2021)
datasets proposed a modern approach to evaluating logical reasoning through a
task involving assignment of binary labels to candidate implications following
a set of premises expressed in natural language. The datasets emulate a linear
deductive chain of reasoning of varying depths given a set of facts and rules,
with ProofWriter augmenting this task through intermediate conclusions and
proof generation. LogicNLI (Tian et al., 2021) provides a more comprehensive
diagnostic benchmark involving reasoning through all seven fundamental logics
(conjunction, disjunction, negation, implication, equation, universal and
existential quantifiers). It contains an additional ”paradox” label implying a
situation where both the hypothesis as well as its negative proposition can be
simultaneously entailed to the premise through different reasoning paths. This
facilitates a non-linear reasoning, but is still limited to two contradictory
reasoning paths. The FOLIO (Han et al., 2022) dataset boasts a higher
vocabulary size due to a hybrid annotation approach but again consists of
linear reasoning chains. Along similar lines, ProntoQA (Saparov & He, 2022)
proposes a first-order logic benchmark using a linear ontology which might be
fictional. This is done to prevent LLMs from predicting correct outcomes
through spurious correlations in their pretraining corpus.

The benchmarks described here are primarily focused on the evaluation of
deductive reasoning. In contrast, GroundCocoa offers a more realistic
grounding task with an emphasis on if-then reasoning which leads to many
candidate reasoning paths for each answer choice. While deductive reasoning
may involve a broader range of logical structures, conditional reasoning is a
subset which deals specifically with the relationships and implications of
conditional statements. Our dataset consists of a large vocabulary size and
context length per sample, leading to greater linguistic diversity, and a
higher reasoning width than other benchmarks in logical reasoning. Questions
are designed to test for robustness against rare and unconventional user
requirements and bring to the fore model bias from pretraining data. Also,
unlike most other benchmarks, we do not attempt to evaluate logical reasoning
in isolation - our task might require abilities such as temporal or
mathematical reasoning.

Compositional Generalization. Samples in GroundCocoa consist of novel
combination of primitives expressed as user requirements in a flight-booking
task. Such reasoning falls under the umbrella of compositional generalization
- an area that has garnered increasing interest in the scientific community
recently. Hosseini et al. (2022) highlight the relative generalization gap
with in-context learning between in-distribution and out-of-distribution
samples in various semantic parsing tasks. Dziri et al. (2023) demonstrates
how transformer-based LLMs may solve compositional tasks by reducing them to
linearized subgraph matching. By establishing a computational graph for each
problem, the authors are able to define computational complexity by metrics
such as the reasoning depth and width which correspond to levels in multi-hop
reasoning and average parallelism respectively. Unsurprisingly, increased task
complexity leads to a rapid decay in model performance under various settings.

Our findings largely concur with previous literature on compositional
reasoning. However, results on GroundCocoa reveal that even the most advanced
LLMs struggle at relatively low levels of compositional complexity when
juxtaposed with conditional reasoning and grounding. While Dziri et al. (2023)
demonstrated their results using problems such as multi-digit multiplication,
dynamic programming, and Einstein’s puzzle - we release a new dataset that is
anchored on a practical, real world use-case of parsing complex user criteria
and grounding to a fixed schema representing a flight option. GroundCocoa
contains a high semantic coverage and we posit that it would be of interest to
the NLP community as a hard evaluation set to benchmark compositional
generalization in LLMs.

Dialogue-State Tracking. Finally, while our task is reminiscent of a single
turn in a dialogue state tracking system, it goes one step further to test a
language model’s grounding ability to match a flight schema with the user
query. Most schema-guided dialogue datasets (Rastogi et al., 2020; Lee et al.,
2022) consist of fixed slot values and the filtering of available options is
handled through external systems (e.g. api’s). Slot values in GroundCocoa are
fuzzy due to conditional constraints on the primitives. In Figure 5,
TicketPrice may take on different values based on TicketClass. GroundCocoa
consists of examples with varying levels of compositional complexity due to
long and complex user requirements. This differentiates it from the majority
of schema-guided dialogue datasets where the primary objective is goal and
slot identification, and tagging of slot values. These tasks, while
challenging in their own respect, do not engage a models’ compositional
reasoning ability to the same extent.

##  5 Conclusion

Modern LLMs have demonstrated remarkable advancements in many tasks including
those that are inherently compositional and necessitate conditional reasoning
such as mathematical problem solving, and code generation and interpretation.
However, discerning genuine reasoning from mere rote learning and shallow
understanding continues to be a focal point of study. While LLMs have become
exceedingly adept at answering questions of seemingly greater complexity, we
show that they can struggle on the same skills when presented with an
unfamiliar task setting. While problem size does have an impact, even the less
complex samples in our dataset are challenging to the best language models
today.

Beyond introducing a new benchmark dataset, we conduct a thorough analysis of
the effects of increasing complexity, including advanced prompting techniques,
and robustness to atypical queries. Our results uncover a substantial
disparity in the performance of competing language models, a distinction that
is not as pronounced in most other evaluation benchmarks and highlights their
respective abilities in tackling novel challenges. Our data generation process
is largely automatic, with human validation at the last step. In addition to
the dataset and the evaluation script, we release code for the data generation
which can be easily extended to generate more examples, and increase diversity
(through different slots) as well as complexity. With minor modifications, the
task can be further complicated by incorporating queries with multiple answers
and questions that require other forms of logical reasoning such as
aggregation (e.g., ”Give me the cheapest flight matching my criteria?”),
existential quantification (e.g., ”Is there a first class seat under $5000?”)
etc., which we leave for future work.

## References

  * Amini et al. (2019) Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannaneh Hajishirzi.  MathQA: Towards interpretable math word problem solving with operation-based formalisms.  In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 2357–2367, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1245.  URL https://aclanthology.org/N19-1245.
  * Bhagavatula et al. (2020) Chandra Bhagavatula, Ronan Le Bras, Chaitanya Malaviya, Keisuke Sakaguchi, Ari Holtzman, Hannah Rashkin, Doug Downey, Wen tau Yih, and Yejin Choi.  Abductive commonsense reasoning.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=Byg1v1HKDB.
  * Bisk et al. (2020) Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al.  Piqa: Reasoning about physical commonsense in natural language.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pp. 7432–7439, 2020.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _arXiv preprint arXiv:1803.05457_ , 2018.
  * Clark et al. (2021) Peter Clark, Oyvind Tafjord, and Kyle Richardson.  Transformers as soft reasoners over language.  In _Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence_ , pp. 3882–3890, 2021.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Deng et al. (2024) Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Sam Stevens, Boshi Wang, Huan Sun, and Yu Su.  Mind2web: Towards a generalist agent for the web.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Du et al. (2023) Mengnan Du, Fengxiang He, Na Zou, Dacheng Tao, and Xia Hu.  Shortcut learning of large language models in natural language understanding.  _Commun. ACM_ , 67(1):110–120, dec 2023.  ISSN 0001-0782.  doi: 10.1145/3596490.  URL https://doi.org/10.1145/3596490.
  * Dziri et al. (2023) Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi.  Faith and fate: Limits of transformers on compositionality.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=Fkckkr3ya8.
  * Furuta et al. (2023) Hiroki Furuta, Kuang-Huei Lee, Ofir Nachum, Yutaka Matsuo, Aleksandra Faust, Shixiang Shane Gu, and Izzeddin Gur.  Multimodal web navigation with instruction-finetuned foundation models.  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Gardner et al. (2020) Matt Gardner, Yoav Artzi, Victoria Basmov, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, et al.  Evaluating models’ local decision boundaries via contrast sets.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 1307–1323, 2020.
  * Geirhos et al. (2020) Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.  Shortcut learning in deep neural networks.  _Nature Machine Intelligence_ , 2(11):665–673, 2020.
  * Goel et al. (2021) Karan Goel, Nazneen Fatema Rajani, Jesse Vig, Zachary Taschdjian, Mohit Bansal, and Christopher Ré.  Robustness gym: Unifying the nlp evaluation landscape.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Demonstrations_ , pp. 42–55, 2021.
  * Han et al. (2022) Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, David Peng, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Shafiq Joty, Alexander R. Fabbri, Wojciech Kryscinski, Xi Victoria Lin, Caiming Xiong, and Dragomir Radev.  Folio: Natural language reasoning with first-order logic.  _arXiv preprint arXiv:2209.00840_ , 2022.  URL https://arxiv.org/abs/2209.00840.
  * Hendrycks et al. (2021a) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  In _International Conference on Learning Representations_ , 2021a.  URL https://openreview.net/forum?id=d7KBjmI3GmQ.
  * Hendrycks et al. (2021b) Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt.  Measuring mathematical problem solving with the math dataset.  _NeurIPS_ , 2021b.
  * Hong et al. (2023) Wenyi Hong, Weihan Wang, Qingsong Lv, Jiazheng Xu, Wenmeng Yu, Junhui Ji, Yan Wang, Zihan Wang, Yuxiao Dong, Ming Ding, and Jie Tang.  Cogagent: A visual language model for gui agents, 2023.
  * Hosseini et al. (2022) Arian Hosseini, Ankit Vani, Dzmitry Bahdanau, Alessandro Sordoni, and Aaron Courville.  On the compositional generalization gap of in-context learning.  In Jasmijn Bastings, Yonatan Belinkov, Yanai Elazar, Dieuwke Hupkes, Naomi Saphra, and Sarah Wiegreffe (eds.), _Proceedings of the Fifth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pp. 272–280, Abu Dhabi, United Arab Emirates (Hybrid), December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.blackboxnlp-1.22.  URL https://aclanthology.org/2022.blackboxnlp-1.22.
  * Huang et al. (2019) Lifu Huang, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Cosmos QA: Machine reading comprehension with contextual commonsense reasoning.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 2391–2401, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1243.  URL https://aclanthology.org/D19-1243.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_ , 2023.
  * Jiang et al. (2024) Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al.  Mixtral of experts.  _arXiv preprint arXiv:2401.04088_ , 2024.
  * Koh et al. (2021) Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In _International Conference on Machine Learning_ , pp. 5637–5664. PMLR, 2021.
  * Lee et al. (2022) Harrison Lee, Raghav Gupta, Abhinav Rastogi, Yuan Cao, Bin Zhang, and Yonghui Wu.  Sgd-x: A benchmark for robust generalization in schema-guided dialogue systems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 10938–10946, 2022.
  * Liu et al. (2022) Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.  Transformers learn shortcuts to automata.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Madaan & Yazdanbakhsh (2022) Aman Madaan and Amir Yazdanbakhsh.  Text and patterns: For effective chain of thought, it takes two to tango.  _arXiv preprint arXiv:2209.07686_ , 2022.
  * Meurer et al. (2017) Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B. Kirpichev, Matthew Rocklin, Amit Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rathnayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew J. Curry, Andy R. Terrel, Štěpán Roučka, Ashutosh Saboo, Isuru Fernando, Sumith Kulal, Robert Cimrman, and Anthony Scopatz.  Sympy: symbolic computing in python.  _PeerJ Computer Science_ , 3:e103, January 2017.  ISSN 2376-5992.  doi: 10.7717/peerj-cs.103.  URL https://doi.org/10.7717/peerj-cs.103.
  * Miao et al. (2020) Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su.  A diverse corpus for evaluating and developing English math word problem solvers.  In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 975–984, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.92.  URL https://aclanthology.org/2020.acl-main.92.
  * Nogueira et al. (2021) Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin.  Investigating the limitations of transformers with simple arithmetic tasks.  _arXiv preprint arXiv:2102.13019_ , 2021.
  * Oaksford & Chater (2010) Mike Oaksford and Nick Chater.  Cognition and conditionals: Probability and logic in human thought.  2010\.  URL https://api.semanticscholar.org/CorpusID:124383943.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774, 2023.  URL https://arxiv.org/abs/2303.08774.
  * Osika (2023) Anton Osika.  gpt-engineer, April 2023.  URL https://github.com/gpt-engineer-org/gpt-engineer.
  * Qian et al. (2023) Jing Qian, Hong Wang, Zekun Li, Shiyang Li, and Xifeng Yan.  Limitations of language models in arithmetic and symbolic induction.  pp. 9285–9298, 01 2023.  doi: 10.18653/v1/2023.acl-long.516.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 8689–8696, 2020.
  * Sakaguchi et al. (2021) Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Winogrande: An adversarial winograd schema challenge at scale.  _Commun. ACM_ , 64(9):99–106, aug 2021.  ISSN 0001-0782.  doi: 10.1145/3474381.  URL https://doi.org/10.1145/3474381.
  * Sanyal et al. (2022) Soumya Sanyal, Zeyi Liao, and Xiang Ren.  RobustLR: A diagnostic benchmark for evaluating logical robustness of deductive reasoners.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 9614–9631, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.653.  URL https://aclanthology.org/2022.emnlp-main.653.
  * Sap et al. (2019) Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi.  Social IQa: Commonsense reasoning about social interactions.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 4463–4473, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1454.  URL https://aclanthology.org/D19-1454.
  * Saparov & He (2022) Abulhair Saparov and He He.  Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Saparov & He (2023) Abulhair Saparov and He He.  Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=qFVVBzXxR2V.
  * Saparov et al. (2023) Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He.  Testing the general deductive reasoning capacity of large language models using OOD examples.  _CoRR_ , abs/2305.15269, 2023.  doi: 10.48550/arXiv.2305.15269.  URL https://doi.org/10.48550/arXiv.2305.15269.
  * Schick et al. (2024) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom.  Toolformer: Language models can teach themselves to use tools.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Shen et al. (2024) Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang.  Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * (42) Significant Gravitas.  AutoGPT.  URL https://github.com/Significant-Gravitas/AutoGPT.
  * Simon & Newell (1971) Herbert A. Simon and Allen Newell.  Human problem solving: The state of the theory in 1970.  _American Psychologist_ , 26:145–159, 1971.  URL https://api.semanticscholar.org/CorpusID:14405801.
  * Subhash et al. (2023) Varshini Subhash, Anna Bialas, Weiwei Pan, and Finale Doshi-Velez.  Why do universal adversarial attacks work on large language models?: Geometry might be the answer.  In _The Second Workshop on New Frontiers in Adversarial Machine Learning_ , 2023.
  * Tafjord et al. (2021) Oyvind Tafjord, Bhavana Dalvi, and Peter Clark.  Proofwriter: Generating implications, proofs, and abductive statements over natural language.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pp. 3621–3634, 2021.
  * Talmor et al. (2019) Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4149–4158, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1421.  URL https://aclanthology.org/N19-1421.
  * Tan et al. (2023) Qingyu Tan, Hwee Tou Ng, and Lidong Bing.  Towards benchmarking and improving the temporal reasoning capability of large language models.  In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 14820–14835, Toronto, Canada, July 2023. Association for Computational Linguistics.  doi: 10.18653/v1/2023.acl-long.828.  URL https://aclanthology.org/2023.acl-long.828.
  * Tang et al. (2023) Ruixiang Tang, Dehan Kong, Longtao Huang, and Hui Xue.  Large language models can be lazy learners: Analyze shortcuts in in-context learning.  pp. 4645–4657, 01 2023.  doi: 10.18653/v1/2023.findings-acl.284.
  * Team et al. (2023) Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al.  Gemini: a family of highly capable multimodal models.  _arXiv preprint arXiv:2312.11805_ , 2023.
  * Tian et al. (2021) Jidong Tian, Yitian Li, Wenqing Chen, Liqiang Xiao, Hao He, and Yaohui Jin.  Diagnosing the first-order logical reasoning ability through LogicNLI.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 3738–3747, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.303.  URL https://aclanthology.org/2021.emnlp-main.303.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Wang et al. (2023) Jindong Wang, HU Xixu, Wenxin Hou, Hao Chen, Runkai Zheng, Yidong Wang, Linyi Yang, Wei Ye, Haojun Huang, Xiubo Geng, et al.  On the robustness of chatgpt: An adversarial and out-of-distribution perspective.  In _ICLR 2023 Workshop on Trustworthy and Reliable Large-Scale Machine Learning Models_ , 2023.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022.
  * Wu et al. (2023) Chenfei Wu, Shengming Yin, Weizhen Qi, Xiaodong Wang, Zecheng Tang, and Nan Duan.  Visual chatgpt: Talking, drawing and editing with visual foundation models.  _arXiv preprint arXiv:2303.04671_ , 2023.
  * Yuan et al. (2023) Zhangdie Yuan, Songbo Hu, Ivan Vulić, Anna Korhonen, and Zaiqiao Meng.  Can pretrained language models (yet) reason deductively?  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_ , pp. 1439–1454, 2023.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  Hellaswag: Can a machine really finish your sentence?  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 4791–4800, 2019.
  * Zhang et al. (2023) Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck.  On the paradox of learning to reason from data.  In _Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI)_ , aug 2023.  URL http://starai.cs.ucla.edu/papers/ZhangIJCAI23.pdf.
  * Zheng et al. (2024) Boyuan Zheng, Boyu Gou, Jihyung Kil, Huan Sun, and Yu Su.  Gpt-4v (ision) is a generalist web agent, if grounded.  _arXiv preprint arXiv:2401.01614_ , 2024.
  * Zhou et al. (2019) Ben Zhou, Daniel Khashabi, Qiang Ning, and Dan Roth.  “going on a vacation” takes longer than “going for a walk”: A study of temporal commonsense understanding.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Association for Computational Linguistics, 2019.

##  Appendix A Sample Flight Schema

Figure 8: Schema for British Airways flight between Mexico City and Paris on
04/24/2024

##  Appendix B Samples from different slot/minterm configurations

###  B.1 2 slots, 2 minterms

Figure 9: Sample query in GroundCocoa with 2 slots and 2 minterms.

###  B.2 3 slots, 2 minterms

Figure 10: Sample query in GroundCocoa with 3 slots and 2 minterms.

###  B.3 4 slots, 2 minterms

Figure 11: Sample query in GroundCocoa with 4 slots and 2 minterms.

###  B.4 4 slots, 3 minterms

Figure 12: Sample query in GroundCocoa with 4 slots and 3 minterms.

###  B.5 5 slots, 2 minterms

Figure 13: Sample query in GroundCocoa with 5 slots and 2 minterms.

###  B.6 6 slots, 2 minterms

Figure 14: Sample query in GroundCocoa with 6 slots and 2 minterms.

##  Appendix C Prompts used in Model Evaluation

Figure 15: Evaluation prompt without CoT.

Figure 16: Evaluation prompt using CoT-partial.

##  Appendix D End-to-End Generation Process

Figure 17: End-to-End query generation with 2 slots and 2 minterms.