# Fourier, Gabor, Morlet or Wigner:
Comparison of Time-Frequency Transforms

Stefan Scholl
<EMAIL_ADDRESS>
###### Abstract

In digital signal processing time-frequency transforms are used to analyze
time-varying signals with respect to their spectral contents over time. Apart
from the commonly used short-time Fourier transform, other methods exist in
literature, such as the Wavelet, Stockwell or Wigner-Ville transform.
Consequently, engineers working on digital signal processing tasks are often
faced with the question which transform is appropriate for a specific
application. To address this question, this paper first briefly introduces the
different transforms. Then it compares them with respect to the achievable
resolution in time and frequency and possible artifacts. Finally, the paper
contains a gallery of time-frequency representations of numerous signals from
different fields of applications to allow for visual comparison.

##  I Introduction

In many fields of engineering and science it is vital to analyze the spectral
content of time-varying signals as it changes over time. This includes medical
signals (EEG, ECG, ultrasonic), music and speech, animal voices, seismic
activity, vibrations, fluctuations in power grids, radar and communication
signals and many more.

For that purpose many different types of time-frequency transforms have been
introduced in literature. Some of the transforms have a high practical impact,
others are more of theoretical interest. The available methods provide largely
different properties such as time resolution, frequency resolution, accuracy
and the potential introduction of artifacts that do not correspondent to
actual signal components.

This paper considers the STFT, Gabor, Wavelet and Stockwell (S) transform as
well as the Wigner-Ville distribution (WVD) and its smoothed pseudo variant
(SPWVD). Section II provides a brief introduction to these methods. Readers
that are interested in more in-depth information and the theoretical
backgrounds are referred to [1, 2, 3]. Section III compares the transforms
with respect to resolution and artifacts. Finally, the transforms are applied
to numerous different signals to form a gallery of time-frequency transforms.
The purpose of this gallery is to show the properties, advantages and
disadvantages of the transforms on actual signals in order to support
engineers selecting the right transform for their application.

##  II Time-Frequency Transforms

###  II-A Short-Time Fourier and Gabor Transform

The STFT is the most widely known and commonly used time-frequency transform.
It is well understood, easy to interpret and there exist fast implementations
(FFT). Its drawbacks are the limited and fixed resolution in time and
frequency.

The idea of the STFT is to move a sliding window $w(t)$ over the signal $x(t)$
to be analyzed, such that a particular time span of the signal is selected.
For each position of the window a Fourier transform is calculated, that
represents the frequency content of that time span. The STFT results in the
two dimensional time-frequency representation:

$X(t,f)=\intop_{-\infty}^{\infty}x(t_{1})w^{*}(t_{1}-t)e^{-j2\pi
ft_{1}}dt_{1}$

For spectral analysis the squared magnitude of the STFT is considered, which
is called spectrogram:

$S_{x}(t,f)=\left|X(t,f)\right|^{2}$

Time and frequency resolution can be controlled by the window length, as shown
in Figures 2 and 3: A short window captures only a short period of time and
has thus a precise time resolution. However, the frequency resolution is poor,
because the windowed signal contains only few time samples resulting in only
few frequency bins. Contrary, a long window provides poor time resolution, but
creates precise frequency information due to the larger number of samples.
This phenomenon is known as the uncertainty principle, that states that the
product of resolution in time and frequency is limited: $BT\geq\frac{1}{4\pi}$
(with B being the bandwidth of one frequency bin) [2].

A special case of the STFT, where the uncertainty equation above is fulfilled
with equality (i.e. having the best joint time and frequency resolution), is
known as the Gabor transform. The Gabor transform is simply a STFT with the
window being a Gaussian function

$w(t)=e^{-\alpha t^{2}}$

where the parameter $\alpha$ controls the window length, i.e. the emphasis on
time or frequency resolution.

Figure 1: Exemplary signal in the time domain Figure 2: STFT (spectrogram)
with short and long windows of the exemplary signal in Figure 1, showing the
difference in frequency and time resolution

Figure 3: Resolution of the STFT with long (upper) and short window (lower)

###  II-B Wavelet Transform

The result of the wavelet transform differs from the STFT in that its time-
frequency resolution is not fixed and depends on the frequency (multi-scale
property, see Fig. 5). In general, the wavelet transform represents lower
frequency components with finer frequency resolution and coarser time
resolution. For higher frequencies the reverse is true: frequency resolution
is coarser and time resolution is finer. This variable resolution property of
the wavelet transform is sometimes superior to the Fourier approach, because
it may give clearer spectral information for certain applications, such as
audio signal processing.

The wavelet transform compares the time domain signal $x(t)$ with a short
analysis function $\varPsi(t)$. $\varPsi(t)$ is called the wavelet and can
take on many forms as will be described below. During the calculation of the
transform the wavelet is repeatedly moved over the signal (time shifted) –
each pass with a different scale factor in time, that dilates the wavelets to
a different length (dilation or scale). This creates a two dimensional
representation of time (i.e. shift) and scale (can be related to frequency).
The time shift is denoted by $b$, the scale by $a$. The continuous wavelet
transform (CWT) is defined as:

$CWT(a,b)=\frac{1}{\sqrt{a}}\intop_{-\infty}^{\infty}x(t)\varPsi^{*}\left(\frac{t-b}{a}\right)dt$

Analog to the spectrogram of the STFT, the scalogram of the wavelet transform
is defined as

$\left|CWT(a,b)\right|^{2}$

Different wavelet functions are available for analysis. For the CWT commonly
Morlet wavelets (also called Gabor wavelets) are used, that consist of a
complex sine wave with Gaussian envelope

$\varPsi_{Morlet}(t)=e^{-\alpha t^{2}}e^{j2\pi f_{c}t}$

Here, the parameters “center frequency” $f_{c}$ and “width of Gaussian”
$\alpha$ control the trade-off between time and frequency resolution and need
to be selected before conducting the transform. Basically, wavelet functions
need to be functions that are both local in time and frequency to provide
adequate time and frequency resolution. Figure 4 shows an example of the
scalogram of a CWT.

Note, that besides the CWT, the discrete wavelet transform (DWT) exists.
Different from the CWT, the DWT preserves the complete information of the time
domain signal and is thus invertible. Therefore the DWT is often used to
create sparse signal representations that can be used for data compression
(e.g. widely applied in image processing). Usually different types of wavelets
are used for the DWT, such as the Haar or Daubechies wavelets. The DWT is
often considered less suitable for time-frequency representation, because it
creates less readable plots.

Figure 4: CWT (scalogram): note the varying resolution of frequency and time
Figure 5: Variable resolution property of the CWT and S transform

###  II-C Stockwell Transform

The Stockwell or S-transform [4] is basically a STFT with a Gaussian (Gabor)
window, whose length is frequency dependent. This results in a varying time-
frequency resolution similar to the wavelet transform (Figure 5). The
Stockwell transform is defined as

$ST(t,f)=\intop_{-\infty}^{\infty}x(t_{1})\frac{\left|f\right|}{\sqrt{2\pi}}e^{\frac{-f^{2}(t_{1}-t)^{2}}{2}}e^{-j2\pi
ft_{1}}dt_{1}$

It is also similar to the CWT with a Morlet wavelet. However, in contrast to
the CWT, the Stockwell transform has absolute referenced phase information.
This means that the phase of the kernel functions, which are multiplied with
the signal for analysis, at t = 0 is zero. Moreover, the Stockwell transform
tends to emphasize higher frequency content due to the factor $|f|$ in its
formula. Figure 6 shows an example.

Figure 6: S transform: note the varying resolution of frequency and time and
the emphasis on the higher frequency component

###  II-D Wigner-Ville Distribution

The Wigner-Ville distribution (WVD) [1] overcomes the limited resolution of
the Fourier and wavelet based methods using an autocorrelation approach.

The standard version of the autocorrelation function (ACF) considers the
pointwise multiplication of a signal with a lagged version of itself and
integrates the results over time. It is defined as

$r{}_{xx}(\tau)=\intop_{-\infty}^{\infty}x(t)x^{*}(t+\tau)dt$

The standard ACF is only dependent on the lag $\tau$, because time is
integrated out of the result. The WVD uses a variation of the ACF, called the
instantaneous autocorrelation, which omits the integration step. Thus time
remains in the result. The instantaneous autocorrelation is therefore a two
dimensional function, depending on $t$ and the lag $\tau$:

$R_{xx}(t,\tau)=x(t+\frac{\tau}{2})x^{*}(t-\frac{\tau}{2})$

As an example, Figure 7 shows the instantaneous autocorrelation of a
triangular shaped signal.

The WVD calculates the frequency content for each time step $t$ by taking a
Fourier transform of the instantaneous autocorrelation across the axis of the
lag variable $\tau$ for that given $t$ (depicted in Figure 7) :

$\displaystyle W(t,f)$ $\displaystyle=$
$\displaystyle\intop_{-\infty}^{\infty}R_{xx}(t,\tau)e^{-j2\pi f\tau}d\tau$
$\displaystyle=$
$\displaystyle\intop_{-\infty}^{\infty}x(t+\frac{\tau}{2})x^{*}(t-\frac{\tau}{2})e^{-j2\pi
f\tau}d\tau$

The result is real-valued. This way of calculation is related to the fact,
that the Fourier spectrum of a signal equals the Fourier transform of its ACF.

The WVD offers very high resolution in both time and frequency, this is much
finer than of the STFT.

Figure 7: Depiction of the instantaneous autocorrelation $R_{xx}(t,\tau)$ and
the calculation of the WVD of a triangular signal. The slices represent the
pointwise multiplication of the signal with a lagged version of itself for a
specific lag value $\tau$. Calculating a Fourier transform across the
$\tau$-axis for every value of $t$ creates the WVD. If one would integrate
over $t$ instead, the result would be the standard ACF.

An important disadvantage of the WVD are the so-called cross terms. These are
artifacts occurring in the result, if the input signal contains a mixture of
several signal components, see Figure 8. They stem from the fact, that the WVD
is a quadratic (and therefore a non-linear) transform due to the way the
instantaneous autocorrelation is calculated. The WVD of the superposition of
two signals is

$W{}_{x_{1}+x_{2}}=W{}_{x_{1}}+W{}_{x_{2}}+2\Re\left\\{W_{x_{1},x_{2}}\right\\}$

and may be dominated by the cross term $W_{x_{1},x_{2}}$, which may have twice
the amplitude of the auto terms $W{}_{x_{1}}$and $W{}_{x_{2}}$. Unfortunately,
the occurrence of these cross terms limits the usefulness for many practical
signals.

The WVD is usually calculated with the analytic version of the input signal
that does not contain negative frequency components. This avoids cross terms
between positive and negative frequency content that may mask low frequency
components in the WVD.

The cross terms occur midway between the auto terms and often have an
oscillatory (high-frequency) pattern. A method to reduce cross terms is to
suppress the oscillating components by additional low-pass filtering in time
and frequency. However, this suppression of cross terms comes at the expense
of reduced resolution. This idea of additional cross term suppression leads to
the more general formulation of time-frequency transforms called Cohen’s class
[1, 3]. From Cohen’s class many different variants can be deduced, that
basically differ in the way the low-pass filter is designed. A prominent one
is the smoothed pseudo Wigner-Ville distribution (SPWVD) [3]. Other variants
such as Choi-Williams, Margenau-Hill or Rihaczek can be found in literature,
but often provide very similar results to the SPWVD for practical signals. The
SPWVD is defined as the WVD filtered by two separate kernels $g(t)$ and $H(f)$
(need to be chosen prior to the transform), that smooth the WVD in frequency
and time:

$SPWVD(t,f)=\intop_{t_{1}}\intop_{f_{1}}g(t-t_{1})H(f-f_{1})W(t_{1,}f_{1})dt_{1}df_{1}$

Figure 8 shows an example of the WVD and Figure 9 its smoothed version, the
SPWVD.

Figure 8: Wigner-Ville distribution: Cross term artifacts occur with high
amplitude and oscillating behavior Figure 9: Smoothed pseudo WVD: cross terms
are suppressed

##  III Comparison and Time-Frequency Gallery

The introduced time-frequency transforms are now compared with respect to
their resolution in time and frequency. Figure 10 presents an overview of the
schematic resolution grids. It visualizes the impact of the transforms and
their parameters on the resolution. For completeness, the figure also shows
the plain time domain and spectrum representations, that do not resolve
frequency and time, respectively.

Furthermore, the transforms are compared for various synthetic signals and
signals from real sources that cover different applications. The signals used
for analysis consist of both synthetic and real-world signals. Synthetic
signals include sweeps, pulses, frequency steps or short sine bursts. Some
signals are composed of several of these elements. The results for synthetic
signals are shown in Fig. Fourier, Gabor, Morlet or Wigner: Comparison of
Time-Frequency Transforms and Fourier, Gabor, Morlet or Wigner: Comparison of
Time-Frequency Transforms. Real-world signals include audio signals from
speech and music (Fig. Fourier, Gabor, Morlet or Wigner: Comparison of Time-
Frequency Transforms), radio signals with different modulation types (Fig.
Fourier, Gabor, Morlet or Wigner: Comparison of Time-Frequency Transforms) and
signals from nature and medical applications such as ECG, ultrasonic, bat
sound, earthquake (Fig. Fourier, Gabor, Morlet or Wigner: Comparison of Time-
Frequency Transforms).

The considered purpose of a transform is to visually present discriminative
time and frequency features. Therefore only the magnitudes of the results are
shown. Some transforms require certain parameters to be tuned, e.g. window
length of the STFT or the center frequency of the Morlet mother wavelet. These
parameters have been chosen such that the features of the signals become
easily visible. According to common practice in literature, all transforms are
typically plotted on linear frequency scale, except for the wavelet transform,
which occurs both in logarithmic and linear scale.

Finally, the choice of the transform depends on the signal properties and the
further use or subsequent processing of the results. Important aspects to
consider are the desired resolution in time and frequency as well as the
tolerability of artifacts. Table I summarizes the transforms and provides
recommendations when to use which transform.

Transform |  Time-Frequency Resolution |  Artifacts |  Application
---|---|---|---
Short-Time Fourier (STFT) / Gabor |  poor |  no |  general purpose
Continuous Wavelet (CWT) |  poor, |  |
frequency dependent |  no |  when variable time-frequency resolution required, e.g. audio |
Stockwell (S) |  poor, |  |
frequency dependent |  no |  when variable time-frequency resolution with a fixed phase alignment required, emphasizes higher frequencies |
Smoothed Pseudo Wigner-Ville (SPWVD) |  good |  sometimes |  general purpose, when high resolution required and some artifacts can be tolerated
Wigner-Ville (WVD) |  excellent |  strong |  for simple signals or when artifacts can be tolerated
Table I: When to use which transform Figure 10: Schematics of the resolutions
of the transforms, including the time domain representation and the standard
Fourier spectrum for comparison

## References

  * [1] J. Semmlow and B. Griffel, _Biosignal and Medical Image Processing_. CRC Press, 2014.
  * [2] M. Sandsten, “Time-frequency analysis of time-varying signals and non-stationary processes,” _Lund University_ , 2018.
  * [3] F. Hlawatsch and G. F. Boudreaux-Bartels, “Linear and quadratic time-frequency signal representations,” _IEEE Signal Processing Magazine_ , vol. 9, no. 2, pp. 21–67, 1992.
  * [4] R. Stockwell, L. Mansinha, and R. Lowe, “Localization of the complex spectrum: the s transform,” _IEEE Transactions on Signal Processing_ , 1996.

Synthetic signals (1)

Synthetic signals (2)

Audio signals

Radio signals

Signals from nature and medical applications


# Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning
with Knowledge Graphs

Minh-Vuong Nguyen Linhao Luo∗♢ Fatemeh Shiri♢ Dinh Phung♢
Yuan-Fang Li♢ Thuy-Trang Vu♢ Gholamreza Haffari♢
♢Department of Data Science & AI, Monash University
<EMAIL_ADDRESS>The first two authors contributed equally to
this work.

###### Abstract

Large language models (LLMs) demonstrate strong reasoning abilities when
prompted to generate chain-of-thought (CoT) explanations alongside answers.
However, previous research on evaluating LLMs has solely focused on answer
accuracy, neglecting the correctness of the generated CoT. In this paper, we
delve deeper into the CoT reasoning capabilities of LLMs in multi-hop question
answering by utilizing knowledge graphs (KGs). We propose a novel
discriminative and generative CoT evaluation paradigm to assess LLMs’
knowledge of reasoning and the accuracy of the generated CoT. Through
experiments conducted on 5 different families of LLMs across 2 multi-hop
question-answering datasets, we find that LLMs possess sufficient knowledge to
perform reasoning. However, there exists a significant disparity between
answer accuracy and faithfulness of the CoT reasoning generated by LLMs,
indicating that they often arrive at correct answers through incorrect
reasoning.

Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning
with Knowledge Graphs

Minh-Vuong Nguyen††thanks:  The first two authors contributed equally to this
work. Linhao Luo∗♢ Fatemeh Shiri♢ Dinh Phung♢ Yuan-Fang Li♢ Thuy-Trang Vu♢
Gholamreza Haffari♢ ♢Department of Data Science & AI, Monash University
<EMAIL_ADDRESS>

##  1 Introduction

While large language models (LLMs) have shown great potential as general-
purpose task solvers, they tend to be unreliable reasoners (Bang et al.,
2023). Prior research suggests that LLMs demonstrate reasoning-like behaviors
as the number of parameters increases (Wei et al., 2022). Notably, Chain-of-
Thought (CoT) prompting, where LLMs are explicitly instructed to decompose
questions into a sequence of logical steps before generating answers, has
achieved impressive performance in various reasoning tasks (Wei et al., 2022;
Kojima et al., 2022). However, as LLMs function as black-box models, the
mechanism behind their reasoning processes remains largely unknown.

Figure 1: Examples of different CoT reasoning errors and a faithful CoT
grounded by KGs.

Previous research measures the reasoning ability of LLMs by reporting their
performance, e.g. accuracy, on the downstream tasks that require reasoning
(Huang and Chang, 2023). This evaluation strategy cannot provide a direct
assessment of the reasoning steps. Hence, it remains unclear whether their
strong performance is the result of true reasoning ability or simple
heuristics. Recent studies on analyzing CoT reasoning introduce perturbations
to prompts, including the injection of invalid reasoning paths, incorrect
facts, or the addition of arbitrary symbols to the few-shot examples (Madaan
et al., 2023; Wang et al., 2023a; Ye et al., 2023). These studies show that
various aspects of prompts, such as query relevance, style patterns, and the
correct ordering of reasoning steps, are more important than the validity of
reasoning in the in-context demonstrations. While revealing interesting
insights into the reasoning process of LLMs, prompt perturbation-based methods
still cannot directly evaluate the correctness of reasoning steps.
Automatically verifying CoT reasoning steps is still an open challenge due to
the unstructured nature of its freeform rationales.

In this paper, we go beyond evaluating only the final answers to directly
analyzing the intermediate reasoning steps generated by CoT prompting in
multi-hop question-answering (QA) tasks. To tackle the unstructured nature of
CoT, we introduce a novel evaluation framework that grounds LLMs’ responses in
knowledge graphs (KGs) and verify whether it forms a faithful path to the
given KGs. Before evaluating more open-ended generative reasoning skills, we
design discriminative tests to assess whether LLMs can identify faithful
reasoning paths when perturbed with factual errors, incoherent, and misguided
reasoning steps. Our discriminative evaluation results reveal that LLMs
possess certain knowledge of valid reasoning under sufficient knowledge
conditions. Building on this observation, we further propose the generative
evaluation to measure the reasoning ability of LLMs and detect fine-grained
reasoning errors (see Figure 1). In the generative evaluation, we instruct
LLMs to generate CoT in a structured format, enabling us to parse their
responses into a structured reasoning path and validate against KGs. Our
ablation study with human experts shows that our framework achieves good
accuracy in reasoning path retrieval and evaluation.

We use the proposed evaluation framework to understand the CoT reasoning
process of five state-of-the-art LLMs on two complex QA tasks, which require
performing multi-step reasoning to answer the questions. Our study reveals
that

  * •

LLMs contain sufficient knowledge to conduct reasoning. However, they are
still limited in considering the coherence of the reasoning and hallucinations
during CoT generation.

  * •

The correct final answer may not necessarily follow from faithful reasoning.
We observe a significant gap between answer accuracy and reasoning
faithfulness. It highlights the necessity of directly evaluating the reasoning
steps rather than solely scoring the final answers.

  * •

The performance gap between the final answer and reasoning worsens as the
model size increases. As the answer accuracy also increases with the model
size, it suggests that the bigger models may have the knowledge of the final
answer without the need to perform reasoning.

  * •

Better prompting strategies such as self-consistency or instructing LLMs with
planning can further improve both the final answer and reasoning faithfulness.

##  2 Preliminaries

##### Chain-of-thought (CoT) Reasoning

Chain-of-thought (CoT) Wei et al. (2022) is a reasoning framework that prompts
LLMs to generate a step-by-step reasoning process
$S=\\{s_{1},s_{2},\ldots,s_{n}\\}$ to a question $q$, where $s_{i}$ is a
natural language sentence describing a step in the reasoning process.

##### Faithful CoT

A faithful CoT should satisfy the following properties Creswell and Shanahan
(2022): (i) there are no factual errors, (ii) the reasoning process is
coherent (i.e., the conclusion of previous step $s_{i-1}$ should be the
prerequisite of the current step $s_{i}$), (iii) the reasoning process leads
to the correct answers. Examples of violations of these properties are shown
in Figure 1.

##### Knowledge Graphs (KGs)

Knowledge graphs (KGs) are structured representations of knowledge that
contain abundant facts in the form of triples
$\mathcal{G}=\\{(e_{h},r,e_{t})\mid
e_{h},e_{t}\in\mathcal{E},r\in\mathcal{R}\\}$, where $e_{h}$ and $e_{t}$ are
head and tail entities, and $r$ is the relation between them. A path in KGs is
a sequence of triples:
$P=e_{0}\xrightarrow{r_{1}}e_{1}\xrightarrow{r_{2}}\ldots\xrightarrow{r_{l}}e_{l}$,
connecting the entity $e_{0}$ to the entity $e_{l}$.

##### Reasoning Paths

Given a question $q$ and the answer $a$, a valid reasoning path
$P^{*}=e_{q}\xrightarrow{r_{1}}e_{1}\xrightarrow{r_{2}}\ldots\xrightarrow{r_{l}}e_{a}$
is a path that connects the topic entity $e_{q}$ of $q$ to the answer entity
$e_{a}$ of $a$ in KGs. The reasoning path $P^{*}$ expresses a valid reasoning
process for answering the question according to the KG.

######  Example 1.

Given a question “Who is the brother of Justin Biber?”, we can find a valid
reasoning path $P^{*}$ in KGs as: $\text{Justin
Bieber}\xrightarrow{\texttt{child\\_of}}\text{Jeremy
Bieber}\xrightarrow{\texttt{father\\_of}}\text{Jaxon Bieber}$. It indicates:
(i) Justin Bieber is the child of Jeremy Bieber, and (ii) Jeremy Bieber is the
father of Jaxon Bieber. Thus, the brother of Justin Bieber is Jaxon Bieber.

##### Faithful CoT Grounded by KGs

We verify the faithfulness of the LLMs’ CoT reasoning by grounding it with
KGs. By treating each reasoning step as a triple in KGs, we convert the CoT
into a reasoning path. If a reasoning path starting from the question and
ending at the answers exists in KGs, we deem the CoT of LLMs faithful. A
grounded example is shown at the bottom of Figure 1.

Figure 2: The overall framework of evaluating the CoT reasoning of LLMs, which
contains two evaluation modules: discriminative evaluation and generative
evaluation. The orange and red rectangles denote the entities mentioned in the
question and answer, respectively.

##  3 Evaluating the CoT Reasoning of LLMs

We propose a framework to evaluate the CoT reasoning process of LLMs with the
help of KGs. Specifically, we propose two evaluation modules: discriminative
evaluation and generative evaluation. The discriminative evaluation
investigates whether LLMs possess enough knowledge for conducting faithful
reasoning and the generative evaluation further analyzes whether LLMs can
provide faithful reasoning process during CoT generation. The overall
framework is shown in Figure 2.

###  3.1 Discriminative Evaluation

The discriminative evaluation aims to analyze whether the LLMs possess enough
knowledge to conduct faithful reasoning. We hypothesize that if the LLMs
possess sufficient knowledge for faithful reasoning, they should be able to
distinguish valid reasoning paths from invalid ones given the question and
answer. Following previous studies that evaluate the factual knowledge inside
LLMs Luo et al. (2023b), we feed both the valid and invalid reasoning paths to
the LLMs and ask them to predict the validity of these paths. This allows us
to assess the reasoning knowledge inside LLMs by analyzing their prediction
accuracy.

We carefully design prompts to describe the task and instruct LLMs to provide
the prediction. Below is an example of the zero-shot prompt template.

Zero-shot Discriminative Evaluation Prompt A reasoning path is a sequence of
triples that can be used to derive the answer of given question. Given this
reasoning path, do you think this is a valid path to derive the answer of
given question? If yes please answer "YES", otherwise please answer "NO
Question: <Question> Answer: <Answer> Reasoning path: <Reasoning Path>

where <Question> indicates the question, <Answer> denotes the corresponding
answer, and <Reasoning Path> denotes the input reasoning path, which is
verbalized as a structured sentence.

A valid reasoning path is a sequence of triples that can be used to derive the
answer of given question. The valid reasoning paths are extracted from the
ground-truth reasoning paths111The ground-truth reasoning paths are
constructed from the SPARQL queries provided in the datasets. The detailed
construction is shown in Appendix A. $P^{*}\in\mathcal{P}^{*}$.

We generate three types of invalid reasoning paths $P^{\prime}$ by breaking
specific properties of a faithful CoT:

  * •

Factual error reasoning path: we construct the invalid paths with factual
errors by randomly corrupting entities within the valid reasoning path. This
would result in some factual errors in the reasoning path, which are not valid
for answering the question.

  * •

Incoherent reasoning path: we shuffle the triples of valid paths to construct
an incoherent reasoning path. Even though the facts within the paths are
accurate, the overall coherence of the path is compromised.

  * •

Misguided reasoning path:  we randomly sample the paths starting from other
questions in KGs. These paths are factually correct and coherent, but they are
not related to the questions and lead to incorrect answers.

To thoroughly assess the reasoning abilities of LLMs, in addition to the zero-
shot prompt, we have also developed few-shot, zero-shot CoT, and few-shot CoT
prompts. The details of these prompts are shown in Section E.1.

##### Findings

The results of the discriminative assessment are shown in §5.1. From the
results, we can conclude that LLMs possess enough knowledge to identify
factual errors as well as reasoning path relatedness, but have limitations in
considering the coherence of reasoning paths and CoT generation. Therefore, we
propose the generative evaluation to further assess the faithfulness of CoT
reasoning in LLMs’ generation.

###  3.2 Generative Evaluation

The generative evaluation aims to assess the faithfulness of the CoT reasoning
process generated by LLMs. Our main idea is to ground LLMs’ CoT into KG and
verify whether it forms a valid path. To address the challenge of evaluating
unstructured CoT, we carefully design a prompting strategy to instruct LLMs to
output the CoT in a structured format. This enables us to parse LLM’s response
into a structured reasoning path, which can then be validated against KG. The
example prompts and structured CoT output are provided in Section E.2.

Specifically, given a generated CoT response $S$ of question $q$, we first
construct a reasoning path $\hat{P}$ by retrieving triples from the KGs. Then,
we evaluate the validity of the reasoning path by checking whether the path
coherently connects the question and answer entities in the KGs. The details
of these steps are explained in the following subsections.

####  3.2.1 Reasoning Path Construction

Given a CoT response $S=\\{s_{1},s_{2},\ldots,s_{n}\\}$, we first retrieve a
triple222We noticed in almost all cases in our experiments, a CoT step
corresponds to one KG triplet. The extension to multiple triplets per CoT step
is left for future work.  $T=(e_{h},r,e_{t})$ for each step $s_{i}$ in the CoT
response. The retrieved triple is the structural representation of each
reasoning step, which can be used to construct the reasoning path for
evaluation.

Previous works usually retrieve triples by identifying the entities and
relations mentioned in the sentence and linking them to the KGs Lan et al.
(2021); Wang et al. (2021). However, this process is not scalable to KGs.
Inspired by the recent fact retrieval method Baek et al. (2023), we represent
the reasoning step $s$ and triples in a unified embedding space and retrieve
the triple $T$ based on their embedding similarity.

For all the triples in a KG $\mathcal{G}$, we verbalize each triplet into a
sentence by concatenating the entities and relation $x="e_{h}~{}r~{}e_{t}."$.
Then, we use the Sentence-BERT model (Reimers and Gurevych, 2019) to obtain
its embedding $h_{T}=E(x)$. These embeddings are constructed in advance and
saved in a vector database for efficient retrieval. Similarly, the embedding
of a given reasoning step $s$ is computed as $h_{s}=E(s)$. Then we retrieve
the top-$K$ triples from KG by calculating the embedding similarity between
$h_{s}$ and $h_{T}$ as:

$\centering\tau_{i}=f(h_{s},h_{T_{i}}),\quad
T_{i}=(e_{h},r,e_{t})\in\mathcal{G},\@add@centering$ (1)

where $\tau_{i}$ denotes the similarity score of triple $T_{i}$, and
$f(\cdot,\cdot)$ is a non-parametric scoring function that measures the
similarity between two embeddings. We adopt cosine similarity as the scoring
function.

The embedding-based retrieval method may lead to the omission of entities
mentioned in the reasoning step. To solve this problem, we also take into
account the presence of head and tail entities in the reasoning step in the
scoring function. The final score for each retrieved triple is calculated as,

$\centering\tilde{\tau_{i}}=\frac{\tau_{i}+\epsilon_{h}+\epsilon_{t}}{3},\@add@centering$
(2)

where $\epsilon_{h}$ and $\epsilon_{t}$ represent the fuzzy-match ratio of
head and tail entities in the reasoning step, which are range from 0 to 1,
where 0 denotes no existence, 1 denotes a complete match. The overall
retrieval process is presented in the Algorithm 1 in the Appendix B.

Thus, we could obtain a set of triples
$\mathcal{T}=\\{T_{1},T_{2},\ldots,T_{n}\\}$ for the CoT response $S$. Then,
we construct the reasoning path $\hat{P}$ by connecting the triples in
$\mathcal{T}$.

####  3.2.2 Reasoning Path Evaluation

By evaluating the validity of constructed reasoning paths, we can assess the
faithfulness of the CoT reasoning process generated by LLMs. Specifically, we
evaluate the validity of the constructed path $\hat{P}$ from three aspects:

  * •

Factual correctness: $\hat{P}$ contains factual error if the similarity score
$\tilde{\tau_{i}}$ of any retrieved triples are below a factual threshold
$\sigma$.

  * •

Coherence: given a factually correct path, it is incoherent if there exists a
step where its premise is not the conclusion of the previous step.

  * •

Final answer correctness:  given a factually correct and coherent path,
whether the final answer is correct, i.e. matched with ground-truths.

##### Validity of Reasoning Path

The prerequisite and conclusion at each reasoning step are considered head and
tail entities, respectively. If the reasoning path $\hat{P}$ can connect the
question and answer entities in the KG, we can conclude that it is a valid
path. The detailed algorithm is shown in the Algorithm 2 in the Appendix B.

##### Fine-grained Assessment

In addition to the binary evaluation, we also report the minimum edit distance
between the constructed reasoning path $\hat{P}$ and the ground-truth path
$P^{*}$. This serves as a fine-grained assessment of CoT reasoning capability.
We adopt a widely used sequence alignment algorithm - Needleman Wunsch
algorithm (Needleman and Wunsch, 1970) to obtain continuous alignment scores
(i.e., edit distance), which indicate how close the constructed reasoning path
is to the ground-truth reasoning paths. If multiple ground-truth paths exist,
we report the score against one with the highest match rate. The detailed
algorithm is shown in the Algorithm 3 in the Appendix B.

##  4 Experimental Conditions

We use the proposed evaluations to understand the CoT reasoning process of the
state-of-the-art LLMs on complex question-answering (QA) tasks which requires
performing multi-step reasoning to answer the questions. Through analysis, we
seek to answer the following research questions (RQs)

  * •

RQ1: Do LLMs have the knowledge of faithful reasoning? We leverage the
discriminative evaluation to test whether LLMs can identify valid reasoning
paths. This evaluation focuses on assessing LLMs’ knowledge about faithful
reasoning.

  * •

RQ2: Can LLMs express such knowledge to generate faithful reasoning? Utilizing
our generative evaluation framework, we assess the capacity of LLMs to produce
coherent and correct reasoning. We also investigate various factors, such as
model size and prompting strategies, to understand their impact on reasoning
capability.

Dataset | #Test | #2hop | #$\geq$3hop
---|---|---|---
CWQ | 1421 | 1386 | 35
GrailQA | 1813 | 1528 | 285

Table 1: Statistic of datasets.

##### Dataset

We conduct experiments on two QA datasets: Complex WebQuestions (CWQ) Talmor
and Berant (2018) and GrailQA Gu et al.  which contain up to 4-hop questions.
To evaluate multi-step reasoning capability, we filter out single-hop
questions in the test set. Table 1 shows the statistics of the filtered test
set. The generated reasoning paths are validated against Freebase Bollacker et
al. (2008) \- an open knowledge graph containing around 88M entities, 20K
relations, and 126M triples. More details can be found at Section C.1.

##### Large Language Models

We evaluate the reasoning capability of several LLMs with instruction-
following capability at different sizes, including Mistral (7B) Jiang et al.
(2023), Qwen (7B, 14B) Bai et al. (2023), Vicuna (33B) Chiang et al. (2023),
LLaMA2-Chat (70B) Touvron et al. (2023) and ChatGPT (175B) OpenAI (2023). The
details of model versions are available in Section C.2. We set temperature as
0.7 and top p as 0.9 for generation in all models.

##### Prompting Strategies

We experiment with multiple CoT prompting strategies, including

  * •

Few-shot CoT Five examples with structured CoT followed by the answer are
added to the prompt (Figure 11 in Section E.2).

  * •

Few-shot CoT with planning (CoT-Plan) We also explore the ability of LLMs to
plan and decompose the relations required to reach the answer before
verbalizing the CoT reasoning. In particular, we add the ground-truth plan Luo
et al. (2023a) (i.e., a relation path pointing to the answers) into each
example. An example prompt is given in Figure 12 in Section E.2.

  * •

Few-shot CoT with self-consistency (CoT-SC) Beyond the conventional CoT
prompting, we also experiment with Self-Consistency (Wang et al., 2023c), a
more sophisticated method designed to mitigate the inconsistencies in CoT
reasoning by aggregating the final answer through majority votes. In our
evaluation, we sample four outputs, and report the maximum performance across
all the outputs.

LLMs | Size | Zero-shot | Zero-shot CoT | Few-shot | Few-shot CoT
---|---|---|---|---|---
Mistral | 7B | 87.59 | 89.88 | 56.91 | 69.98
Qwen | 7B | 74.76 | 76.13 | 79.64 | 73.23
Qwen | 14B | 88.59 | 88.86 | 88.81 | 75.87
Vicuna-1.5 | 33B | 92.79 | 92.88 | 84.91 | 67.05
LLaMA2-Chat | 70B | 77.96 | 80.71 | 56.99 | 47.76
ChatGPT | 175B | 89.86 | 90.17 | 87.09 | 80.15

Table 2: Discriminative evaluation results of different LLMs on CWQ. We use
binary accuracy as the metric. The best results of each column and row are
highlighted in bold and underlined.

##### Evaluation Framework Implementation

Given a question from the benchmark, in discriminative evaluation, we
construct the invalid paths by randomly perturbing the ground-truth paths
extracted from SPARQL (Kumar et al., 2019). The implementation detail is
described in Appendix A. In generative mode, we use FAISS (Johnson et al.,
2019) as the vector database, Sentence-BERT (Reimers and Gurevych, 2019) as
the employed embedding model and partial ratio fuzzy
matching333https://github.com/seatgeek/thefuzz as the entity scoring function.
We retrieve top-$10$ triples and set the factual threshold $\sigma$ of $0.7$.

##### Evaluation Metrics

For discriminative evaluation, we report the accuracy of detecting valid
reasoning paths from invalid ones. For generative evaluation, we report CoT
reasoning performance of LLMs with the following metrics: (i) final answer
accuracy, (ii) faithful reasoning score, and (iii) minimum edit distance
between the generated and ground truth paths. As different LLMs vary in
instruction-following capabilities and guardrail implementations, we may
encounter responses with unstructured format or abstained answers Luo et al.
(2023b). Therefore, we classify LLMs’ responses into four groups: abstained
(A), unstructured (U), faithful reasoning (FR), and unfaithful reasoning (UR).
We use the F1 score to measure the faithfulness of CoT reasoning where
precision and recall are calculated as
$P=\frac{\textrm{FR}}{\textrm{FR}+\textrm{UR}}$ and
$R=\frac{\textrm{FR}}{\textrm{FR}+\textrm{UR}+\textrm{A}+\textrm{U}}$.
Detailed implementations are described in Section C.3. Results of precision
and recall are presented in Sections D.2 and D.3.

##  5 Main Results

###  5.1 Discriminate Evaluation

##### Finding 1: LLMs possess knowledge of valid reasoning

The overall discriminative evaluation results are shown in Table 2. Based on
the results, it is evident that all LLMs achieve a high level of accuracy in
distinguishing valid reasoning paths. This indicates that LLMs, which are pre-
trained on large-scale corpora, already possess certain knowledge to perform
reasoning tasks effectively. However, when using few-shot prompts, there is a
noticeable decrease in performance for Mistral and LLaMA2. This could be
attributed to the sensitivity of these particular LLMs towards the provided
few-shot examples. The detailed results of each perturbation type are
illustrated in Section D.1, where the accuracy of incoherent paths is lower
than other types. This can be attributed to the fact that LLMs cannot capture
structural information in the context Guo et al. (2023). Moreover, the few-
shot CoT fails to improve the accuracy in identifying valid paths. We
speculate that LLMs are prone to hallucination during CoT generation,
resulting in incorrect predictions. we can conclude that despite having enough
reasoning knowledge, LLMs still face limitations in conducting faithful
reasoning during CoT generation.

LLMs | Size | CWQ | GrailQA
---|---|---|---
Answer$\uparrow$ | Reasoning$\uparrow$ | Gap$\downarrow$ | Edit Dist.$\downarrow$ | Answer$\uparrow$ | Reasoning$\uparrow$ | Gap$\downarrow$ | Edit Dist.$\downarrow$
|  | Fewshot CoT
Mistral | 7B | 36.45 | 25.18 | 11.27 | 69.86 | 16.35 | 2.12 | 14.23 | 94.03
Qwen | 7B | 32.52 | 19.38 | 13.14 | 76.78 | 13.35 | 1.63 | 11.72 | 94.69
Qwen | 14B | 40.39 | 27.38 | 13.01 | 74.49 | 18.83 | 2.13 | 16.70 | 92.90
Vicuna | 33B | 44.50 | 15.92 | 28.58 | 74.60 | 18.26 | 0.95 | 17.31 | 95.39
LLaMA2 | 70B | 49.80 | 33.98 | 15.82 | 62.23 | 22.05 | 2.88 | 19.17 | 92.58
ChatGPT | 175B | 49.85 | 37.13 | 12.72 | 57.94 | 23.69 | 4.17 | 19.52 | 90.13
|  | Fewshot CoT - Plan |  |
Mistral | 7B | 37.14+0.69 | 25.69+0.51 | 11.45 | 70.01 | 17.30+0.95 | 3.36+1.24 | 13.94 | 94.46
Qwen | 7B | 35.35+2.91 | 21.57+2.19 | 13.86 | 74.74 | 13.74+0.39 | 2.06+0.43 | 11.68 | 94.61
Qwen | 14B | 40.86+0.47 | 27.97+0.59 | 12.02 | 73.68 | 19.00+0.17 | 2.48+0.35 | 15.43 | 92.58
Vicuna | 33B | 48.80+4.30 | 20.24+4.32 | 28.56 | 63.93 | 20.84+2.58 | 2.09+1.14 | 18.75 | 92.12
LLaMA2 | 70B | 50.26+0.46 | 37.08+3.10 | 13.18 | 57.81 | 22.35+0.30 | 3.29+0.41 | 19.06 | 89.61
ChatGPT | 175B | 51.74+1.89 | 38.60+1.47 | 13.14 | 56.61 | 24.21+0.52 | 4.32+0.15 | 19.11 | 89.84
|  | Fewshot CoT - SC |  |
Mistral | 7B | 40.86+4.41 | 30.38+5.20 | 10.48 | 65.21 | 16.70+0.35 | 2.60+0.48 | 14.10 | 94.10
Qwen | 7B | 34.75+6.08 | 23.21+3.83 | 15.39 | 74.24 | 14.00+0.65 | 2.32+0.69 | 11.68 | 94.35
Qwen | 14B | 41.01+0.62 | 29.26+1.88 | 11.75 | 73.21 | 21.00+2.17 | 3.24+1.11 | 17.76 | 92.50
Vicuna | 33B | 45.43+2.18 | 21.32+5.40 | 25.36 | 66.17 | 18.92+0.66 | 1.88+0.93 | 17.04 | 94.23
LLaMA2 | 70B | 50.42+0.62 | 37.00+3.02 | 13.42 | 58.55 | 22.35+0.30 | 3.29+0.41 | 19.06 | 91.50
ChatGPT | 175B | 51.74+1.89 | 40.73+3.60 | 11.01 | 52.57 | 24.97+1.28 | 4.86+0.69 | 20.11 | 89.22

Table 3:  Generative evaluation performance of different LLMs on CWQ and
GrailQA datasets. F1-scores of the final answer and reasoning accuracy are
reported in Answer Reasoning respectively. The Gap column denotes the
differences between Answer and Reasoning. The Edit Dist. denotes the edit
distance metric described in Section C.3. +x.xx denotes the improvement in
comparison to few-shot CoT.

###  5.2 Generative Evaluation

Table 3 shows the performance of LLMs in generative evaluation mode. Overall,
ChatGPT demonstrate superior performance in terms of both final answer
accuracy and faithfulness of the reasoning. Surprisingly, Mistral 7B, despite
being the smallest model, exhibits competitive performance comparable to
larger models within the <50B range. Furthermore, enhancing prompting
strategies with planning (CoT-Plan) and self-consistency (CoT-SC) results in
substantial improvements across all LLMs, especially for smaller models.

##### Finding 2: The correct final answer may not necessarily result from
faithful reasoning

As shown in Table 3, there is a notable discrepancy between the accuracy of
the final answer and the reasoning process. The average gap is 15.76% for CWQ,
and 16.44% for GrailQA. While advanced prompting may improve answer and
reasoning accuracy, this performance gap mostly stays consistent.
Interestingly, Vicuna achieves reasonable answer accuracy but has the lowest
reasoning performance of all the models, suggesting its reasoning ability is
inferior, even when compared to small models like Mistral and Qwen-7B. This
finding highlights the inadequacy of relying on final answer accuracy as a
proxy to gauge reasoning ability.

##### Finding 3: The reasoning gap worsens as the model size increases

It can be seen that the reasoning performance increases gradually with model
size, proving the reasoning ability of bigger models. However, the gap between
answer and reasoning performance also gradually increases with model size and
the correctness of the answer. While LLaMA2-70B and ChatGPT rank first in
performance, their gaps are also the highest. Meanwhile, the smallest-size
models, including Mistral-7B and Qwen-7B, hold the lowest gap on CWQ and
GrailQA, respectively. We speculate that larger LLMs may grasp the question
context better or have more knowledge to provide the correct answer directly
without performing reasoning.

##### Finding 4: Better prompting strategy can improve both the answer and
reasoning accuracy

The use of enhanced prompting strategies such as CoT-Plan and CoT-SC lead to
improvement of both the answer and reasoning accuracy across most LLMs.
However, the gap between them remains consistent, regardless of prompt
strategy.

|
---|---

Figure 3: The breakdown of reasoning error types in CWQ and GrailQA.

###  5.3 Analysis

##### Reasoning Errors

We present a detailed breakdown of the reasoning errors in Figure 3. The
results reveal that factual errors account for the majority of errors,
indicating that LLMs tend to generate incorrect information during reasoning.
As GrailQA is a more complex dataset, LLMs have a higher percentage of
coherence errors on GrailQA than CWQ. Interestingly, even when the generated
CoT paths are free from factual and coherent errors, LLMs may fail to produce
correct answers, evidenced by a substantial amount of answer errors. Error
case examples are shown in Section D.4.

##### Ablation Study

To ensure the effectiveness of our generative evaluation framework, we
randomly select 100 CoT responses generated by ChatGPT in CWQ dataset and
asked two human experts to evaluate the constructed reasoning path. The
results presented in Table 4 demonstrate that our method can accurately detect
both faithful and unfaithful reasoning paths. This further confirms the
efficacy of our approach in evaluating CoT reasoning.

Reasoning Types | Precision | Recall | F1
---|---|---|---
Faithful Reasoning | 95.42 | 83.88 | 89.28
Unfaithful Reasoning | 86.12 | 96.01 | 90.80

Table 4: Precision, Recall, and F1 score of the framework on human annotated
datasets.

##### Parsing Error

While we carefully design prompts to instruct LLMs to generate a structured
CoT, there are still corner cases where LLMs generate unstructured and
abstention responses due to their unpredicted behaviors. As reported in
Section D.2, the unstructured and abstention rates are less than 20% in CWQ
dataset and can be mitigated with CoT-Plan and CoT-SC.

##  6 Related Work

##### Reasoning with LLMs

While LLMs have proven to offer a variety of reasoning abilities, they still
tend to hallucinate facts, making them unreliable and imperfect (Qiao et al.,
2022). Several studies have concentrated on improving their reasoning capacity
through prompting (Wang et al., 2023c; Ye and Durrett, 2022; Wiegreffe et al.,
2022). CoT (Wei et al., 2022) is a prompting approach that has demonstrated
notable improvements in reasoning performance. A significant enhancement
compared to CoT, self-consistency (Wang et al., 2023c), is a scheme where
multiple CoTs are generated and the most consistent self-generated answer is
selected. Recently, self-consistency was extended with Tree of Thoughts (ToT)
(Yao et al., 2023), which models the reasoning process with a tree. ToT allows
LLMs to interactively backtrack and explore alternate chains of reasoning,
avoiding getting stuck on a single line of incorrect reasoning. Ye and Durrett
(2022) mitigate the effect of unreliable rationales by calibrating the
prediction probability based on the factuality of CoT. Wiegreffe et al. (2022)
train a Seq2Seq model to filter out unacceptable rationale. Liu et al. (2021)
utilize GPT-3 (Brown et al., 2020) with few-shot prompting to generate
knowledge and prompts the downstream language models.

##### Reasoning Evaluation

Evaluation of the reasoning ability of LLMs has been undertaken for two main
purposes: to enhance the reasoning ability of LLMs (Lyu et al., 2023; Li et
al., 2023; Tyen et al., 2023; Chen et al., 2023) and to quantify the reasoning
ability of LLMs (Wang et al., 2023b; Atanasova et al., 2023). For instance,
Huang and Chang (2023) gauges the reasoning ability of LLMs by assessing their
performance on reasoning benchmarks such as GSM8K and BIG-bench for downstream
tasks. However, this evaluation strategy is unable to offer a direct
assessment of the reasoning steps. Tyen et al. (2023) release the BIG-Bench
Mistake dataset, which includes logical errors in CoT reasoning steps. Using
this benchmark, Tyen et al. (2023); Chen et al. (2023) illustrate the
inability of state-of-the-art LLMs to identify mistakes and reasoning errors,
even in unequivocal cases.

##  7 Conclusion

We propose an evaluation framework to understand the CoT reasoning capability
of LLMs beyond the sole assessment of final answer accuracy. With the help of
a KG and a careful prompting strategy, we can turn the unstructured CoT into a
structured format for automatic evaluation. Our framework consists of two
evaluation modules: (i) a discriminative module that isolates the effects of
different reasoning errors to verify LLMs’ knowledge about reasoning, and (ii)
a generative module to assess the generated CoT reasoning. While LLMs showcase
remarkable capabilities in generating correct answers, our study emphasizes
the need for more nuanced evaluations of their reasoning processes. Addressing
the gap between the final answer and reasoning accuracy remains a critical
area for further exploration in enhancing the true reasoning capabilities and
interpretability of LLMs.

## Limitation

The limitation of our work includes:

  * •

Assuming a CoT step corresponding to one KG triple. LLMs sometimes return a
sentence containing more than two relations. Thus, it is a comprehensive
evaluation that finds out all of the possible candidate triples and assesses
them. It can be tackled by returning top-K candidates from Algorithm 1 and a
dynamic program algorithm expanded from Algorithm 2.

  * •

Assuming a completed knowledge graph. In this work, we use knowledge graphs
(KGs) to retrieve the facts and the connections of facts. However, knowledge
graphs are often incomplete which could contain implicit facts for faithful
reasoning. Thus, it could be inadequate to evaluate the LLMs with the existing
KGs. In the future, we plan to incorporate the knowledge graph completion
methods to improve the comprehension of the retrieval algorithm.

  * •

Checking a reasoning path for a final answer. In reality, there are a number
of questions that return more than a correct answer which corresponds to many
reasoning paths. It is possible that LLM only returns one correct reasoning
path while the others are incorrect. This is an interesting issue to solve in
the future.

## References

  * Atanasova et al. (2023) Pepa Atanasova, Oana-Maria Camburu, Christina Lioma, Thomas Lukasiewicz, Jakob Grue Simonsen, and Isabelle Augenstein. 2023.  Faithfulness tests for natural language explanations.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 283–294, Toronto, Canada. Association for Computational Linguistics.
  * Baek et al. (2023) Jinheon Baek, Alham Fikri Aji, Jens Lehmann, and Sung Ju Hwang. 2023.  Direct fact retrieval from knowledge graphs without entity linking.  In _EMNLP_.
  * Bai et al. (2023) Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu. 2023.  Qwen technical report.  _arXiv preprint arXiv:2309.16609_.
  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. 2023.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.  _arXiv preprint arXiv:2302.04023_.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _Proceedings of the 2008 ACM SIGMOD international conference on Management of data_ , pages 1247–1250.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chen et al. (2023) Shiqi Chen, Yiran Zhao, Jinghan Zhang, I Chern, Siyang Gao, Pengfei Liu, Junxian He, et al. 2023.  Felm: Benchmarking factuality evaluation of large language models.  _arXiv preprint arXiv:2310.00741_.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. 2023.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.
  * Creswell and Shanahan (2022) Antonia Creswell and Murray Shanahan. 2022.  Faithful reasoning using large language models.
  * (10) Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su.  Beyond iid: three levels of generalization for question answering on knowledge bases.  In _Proceedings of the Web Conference 2021_ , pages 3477–3488. ACM.
  * Guo et al. (2023) Jiayan Guo, Lun Du, and Hengyu Liu. 2023.  Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking.  _arXiv preprint arXiv:2305.15066_.
  * Huang and Chang (2023) Jie Huang and Kevin Chen-Chuan Chang. 2023.  Towards reasoning in large language models: A survey.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 1049–1065, Toronto, Canada. Association for Computational Linguistics.
  * 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, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023.  Mistral 7b.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with GPUs.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  In _Advances in Neural Information Processing Systems_.
  * Kumar et al. (2019) Vishwajeet Kumar, Yuncheng Hua, Ganesh Ramakrishnan, Guilin Qi, Lianli Gao, and Yuan-Fang Li. 2019.  Difficulty-controllable multi-hop question generation from knowledge graphs.  In _International Workshop on the Semantic Web_.
  * Lan et al. (2021) Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. 2021.  A survey on complex knowledge base question answering: Methods, challenges and solutions.  In _IJCAI_ , pages 4483–4491.
  * Li et al. (2023) Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2023.  Making language models better reasoners with step-aware verifier.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5315–5333.
  * Liu et al. (2021) Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannaneh Hajishirzi. 2021.  Generated knowledge prompting for commonsense reasoning.  _arXiv preprint arXiv:2110.08387_.
  * Liu et al. (2023) Yang Liu, Yuanshun Yao, Jean-Francois Ton, Xiaoying Zhang, Ruocheng Guo Hao Cheng, Yegor Klochkov, Muhammad Faaiz Taufiq, and Hang Li. 2023.  Trustworthy llms: a survey and guideline for evaluating large language models’ alignment.  _arXiv preprint arXiv:2308.05374_.
  * Luo et al. (2023a) Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2023a.  Reasoning on graphs: Faithful and interpretable large language model reasoning.  _arXiv preprint arxiv:2310.01061_.
  * Luo et al. (2023b) Linhao Luo, Trang Vu, Dinh Phung, and Reza Haffari. 2023b.  Systematic assessment of factual knowledge in large language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 13272–13286, Singapore. Association for Computational Linguistics.
  * Lyu et al. (2023) Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Callison-Burch. 2023.  Faithful chain-of-thought reasoning.  _arXiv preprint arXiv:2301.13379_.
  * Madaan et al. (2023) Aman Madaan, Katherine Hermann, and Amir Yazdanbakhsh. 2023.  What makes chain-of-thought prompting effective? a counterfactual study.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 1448–1535, Singapore. Association for Computational Linguistics.
  * Needleman and Wunsch (1970) Saul B Needleman and Christian D Wunsch. 1970.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _Journal of molecular biology_ , 48(3):443–453.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.
  * Qiao et al. (2022) Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen. 2022.  Reasoning with language model prompting: A survey.  _arXiv preprint arXiv:2212.09597_.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Talmor and Berant (2018) Alon Talmor and Jonathan Berant. 2018.  The web as a knowledge-base for answering complex questions.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_. Association for Computational Linguistics.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Tyen et al. (2023) Gladys Tyen, Hassan Mansoor, Peter Chen, Tony Mak, and Victor Cărbune. 2023.  Llms cannot find reasoning errors, but can correct them!
  * Wang et al. (2023a) Boshi Wang, Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun. 2023a.  Towards understanding chain-of-thought prompting: An empirical study of what matters.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2717–2739, Toronto, Canada. Association for Computational Linguistics.
  * Wang et al. (2023b) Jianing Wang, Qiushi Sun, Nuo Chen, Xiang Li, and Ming Gao. 2023b.  Boosting language models reasoning with chain-of-knowledge prompting.
  * Wang et al. (2023c) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023c.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations_.
  * Wang et al. (2021) Zhiguo Wang, Patrick Ng, Ramesh Nallapati, and Bing Xiang. 2021.  Retrieval, re-ranking and multi-task learning for knowledge-base question answering.  In _EACL_ , pages 347–357.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * Wiegreffe et al. (2022) Sarah Wiegreffe, Jack Hessel, Swabha Swayamdipta, Mark Riedl, and Yejin Choi. 2022.  Reframing human-AI collaboration for generating free-text explanations.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 632–658, Seattle, United States. Association for Computational Linguistics.
  * Yao et al. (2023) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. 2023.  Tree of thoughts: Deliberate problem solving with large language models.  _arXiv preprint arXiv:2305.10601_.
  * Ye et al. (2023) Mengyu Ye, Tatsuki Kuribayashi, Jun Suzuki, Goro Kobayashi, and Hiroaki Funayama. 2023.  Assessing step-by-step reasoning against lexical negation: A case study on syllogism.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 14753–14773, Singapore. Association for Computational Linguistics.
  * Ye and Durrett (2022) Xi Ye and Greg Durrett. 2022.  The unreliability of explanations in few-shot prompting for textual reasoning.  In _Advances in Neural Information Processing Systems_.

##  Appendix A Ground-truth Reasoning Path Construction

To obtain graph and ground truth reasoning paths for each question, we utilize
SPARQL query, topic entities, answer entities provided in datasets to
construct subgraphs, then find paths from topic entities to answer entities as
the ground-truth reasoning paths. In particular,

  * •

We replace SELECT query in each SPARQL query into a CONSTRUCT query to return
the corresponding graph. An example CONSTRUCT query and its returned graph
from the CWQ dataset is shown in example 2.

  * •

In the returned graph, we use NetworkX444https://networkx.org/ library to find
the paths starting at one of the topic entities and ending at one of the
answer entities provided in original dataset. As a result, we obtain a list of
ground-truth reasoning paths used for both discriminative and generative
evaluation.

######  Example 2.

An example CONSTRUCT query and the corresponding returned graph.

CONSTRUCT query
PREFIX ns: <http://rdf.freebase.com/ns/>
CONSTRUCT WHERE { FILTER (?x != ?c)
FILTER (!isLiteral(?x) OR lang(?x) = ” OR langMatches(lang(?x), ’en’))
?c ns:location.country.administrative_divisions ns:m.02g__4 .
?c ns:location.country.languages_spoken ?x .
}  Corresponding returned graph
m.03gyl location.country.administrative_divisions m.02g__4 .
m.03gyl location.country.languages_spoken m.02dhwl .
m.03gyl location.country.languages_spoken m.064_8sq .

##  Appendix B Generative Evaluation

The details of triple retrieval, reasoning path evaluation, and fine-grained
path evaluation are shown in the Algorithms 1, 2 and 3, respectively.

Input: Step $s$; Top-$K$; embedding model $E$; knowledge graph $\mathcal{G}$.

Output: Triple $T$

1 $h_{s}\leftarrow E(s)$

2

3$[T_{i},\tau_{i}]_{i=1}^{K}\leftarrow\mathcal{G}.\text{search}(h_{s},k)$

4 $\mathcal{C}=[]$

5 for  _$i\leftarrow 1$ to $K$_ do

6 $\epsilon_{h},\epsilon_{t}\leftarrow\text{Fuzzy-match}(T_{i},s)$

7 $\tilde{\tau_{i}}\leftarrow\frac{\tau_{i}+\epsilon_{h}+\epsilon_{t}}{3}$

8 $\mathcal{C}.\text{append}((\tilde{\tau_{i}},T_{i}))$

9 end for

10$T=\underset{T_{i}\in\mathcal{C}}{\arg\max}~{}\tilde{\tau_{i}}$

Algorithm 1 Triple Retrieval Algorithm

Input: Reasoning path $\hat{P}$; threshold $\sigma$; knowledge graph
$\mathcal{G}$; ground answer entity $\mathcal{A}$.

Output: Validity $v$.

1 $\text{factual\\_error}\leftarrow False$

2

3$order\\_error\leftarrow False$

4$answer\\_error\leftarrow answer_{\hat{P}}!=\mathcal{A}$

5for  _$T_{i}\in\hat{P}$_ do

6

7 if  _$\tau_{i} <\sigma$ _ then

8 $\text{factual\\_error}\leftarrow True$

9

10 else

11 continue

12 if  _$head_{T_{i}}!=tail_{T_{i}-1}$_ then

13 $order\\_error\leftarrow True$

14 end if

15

16 end if

17

18 end for

19$coherent\\_error\leftarrow\neg factual\\_error\wedge order\\_error$

20 $answer\\_error\leftarrow\neg coherent\\_error\wedge answer\\_error$

21if  _$factual\\_error\vee coherent\\_error\vee answer\\_error$_ then

22 $v\leftarrow False$

23

24else

25

26 $v\leftarrow True$

27 end if

28

29return _$v$_

Algorithm 2 Reasoning Path Evaluation

Input: Reasoning path $\hat{P}$; Ground-truth paths $\mathcal{P}^{*}$

Output: Edit distance $u$

1 $m\leftarrow 0$

2 $u\leftarrow 0$

3

4for  _$P^{*}\in\mathcal{P}^{*}$_ do

5

6 $u^{\prime}\leftarrow\text{NeedlemanWunsch}(\hat{P},P^{*})$

7

8 if  _$u^{\prime} <u$_ then

9 $u\leftarrow u^{\prime}$ $\triangleright$ Get minimum edit distance.

10

11 end if

12

13 end for

14

return _$u$_

Algorithm 3 Fine-grained Path Evaluation

##  Appendix C Experiment Settings

###  C.1 Datasets

We adopt two benchmark KGQA datasets: Complex WebQuestions
(CWQ)555https://www.tau-nlp.sites.tau.ac.il/compwebqTalmor and Berant (2018)
and GrailQA666https://huggingface.co/datasets/grail_qaGu et al.  in this work,
especially we use the test split of CWQ, and validation split of GrailQA. We
only keep questions requiring more than 2-hop reasoning. The number of
questions is shown in Table 1. Both CWQ and GrailQA can be reasoned based on
Freebase KGs777https://github.com/microsoft/FastRDFStoreBollacker et al.
(2008). To reduce the KG size, we combine the subgraphs obtained from SPARQL
queries as the final KG. The detail of subgraphs extraction is shown in
Appendix A.

###  C.2 Large Language Models

The LLMs used in experiments are shown in Table 5. We utilize available
checkpoints from HuggingFace888https://huggingface.co/.

LLM | Model Implementation
---|---
Mistral 7B | mistralai/Mistral-7B-Instruct-v0.1
QWen 7B | Qwen/Qwen-7B-Chat
QWen 14B | Qwen/Qwen-14B-Chat
Vicuna 33B | lmsys/vicuna-33b-v1.3
LlaMA2 70B | meta-llama/Llama-2-70b-chat
ChatGPT | GPT-3.5-turbo

Table 5: Details of used LLMs.

###  C.3 Evaluation Metrics

##### Faithful Reasoning Score.

To enable robust and truthful reasoning, many LLMs adopt the guardrail
techniques to abstain from providing answers when they are uncertain Liu et
al. (2023); Luo et al. (2023b). Also, LLMs exhibit different instruction-
following capabilities, which may result in the CoT response in unstructured
format. Thus, we need to consider both the abstained and unstructured
responses in the evaluation. We define the precision and recall as,

(3) (4)

The F1 score is then the harmonic average of the precision and recall. The
details of abstained and unstructured response detection are in Sections C.4
and C.5.

##### Answer Accuracy

The answers generated by LLM can have a different length than the ground-
truth, so we utilize fuzzy matching to check the correctness of answer. It
checks whether the generated answer appears in the ground-truth answers, and
vice versa.

##### Edit Distance

We further look into the fine-grained evaluation of the reasoning path by
calculating the edit distance Needleman and Wunsch (1970): The minimum number
of edits (add/remove the reasoning steps) required to convert the CoT path to
the ground-truth path.

###  C.4 Abstained Answer Detection

We detect abstained answers through following specific keywords in LLMs’
responses:

List of Abstention keywords not have knowledge more information need more
unknown cannot sorry impossible not possible unable unclear

###  C.5 Unstructured Answer Detection

As the instruction shown in prompts 11 and 12, a structured CoT should follow
the following format:

A structured answer 1\. <step1> 2\. <step2> … (T|t)he answer( to the
question)? is ? $?(.*?)$?.?

Therefore, the CoT responses that do not match the pattern are identified as
unstructured.

##  Appendix D Additional Results

###  D.1 Detailed Results of Discriminative Evaluation

LLMs | Size | Valid Reasoning Path | Factual Errors Reasoning Path
---|---|---|---
Zero-shot | Zero-shot-Cot | Few-shot | Few-shot CoT | Zero-shot | Zero-shot-Cot | Few-shot | Few-shot CoT
Mistral | 7B | 79.01 | 72.32 | 98.78 | 74.54 | 98.68 | 99.46 | 74.72 | 90.67
Qwen | 7B | 94.92 | 91.84 | 85.05 | 58.60 | 94.71 | 94.45 | 95.25 | 92.10
Qwen | 14B | 62.41 | 61.97 | 75.74 | 21.69 | 100.00 | 99.96 | 99.78 | 99.31
Vicuna | 33B | 83.54 | 79.32 | 91.80 | 19.02 | 99.37 | 99.77 | 98.96 | 98.40
LLaMA2 | 70B | 18.79 | 27.84 | 92.50 | 57.52 | 99.54 | 99.50 | 59.44 | 72.48
ChatGPT | 175B | 70.27 | 74.57 | 86.56 | 71.45 | 99.72 | 99.72 | 99.70 | 95.86
LLMs | Size | Incoherent Reasoning Path | Misguided Reasoning Path
Zero-shot | Zero-shot-Cot | Few-shot | Few-shot CoT | Zero-shot | Zero-shot-Cot | Few-shot | Few-shot CoT
Mistral | 7B | 90.11 | 92.10 | 39.92 | 53.08 | 82.55 | 95.62 | 14.20 | 61.61
Qwen | 7B | 61.37 | 61.82 | 73.06 | 66.37 | 48.02 | 56.40 | 65.18 | 75.85
Qwen | 14B | 93.56 | 94.91 | 88.56 | 85.49 | 98.38 | 98.61 | 91.14 | 97.00
Vicuna | 33B | 90.21 | 93.62 | 65.65 | 56.56 | 98.04 | 98.82 | 83.21 | 94.23
LLaMA2 | 70B | 95.92 | 97.43 | 44.41 | 18.27 | 97.58 | 98.05 | 31.60 | 42.78
ChatGPT | 175B | 93.36 | 90.57 | 76.76 | 59.01 | 96.07 | 95.82 | 85.34 | 94.28

Table 6: Discriminative evaluation results of different LLMs on CWQ dataset.
We use the binary accuracy as metric.

We illustrate the discriminative evaluation results of different types of
reasoning paths in Table 6. For each error types, LLMs reach the best
performance under factual errors and misguided reasoning path. However, the
performance under incoherent paths is lower, which could due to the limits of
LLMs in understanding structural context. Besides, the performance of valid
reasoning path is slightly lower than invalid reasoning path. Because it
requires both three properties (i.e., factual errors, incoherence,
misguidance) satisfied at the same time.

###  D.2 Detailed Results of Precision

|
---|---

Figure 4: The precision of LLMs using few-shot CoT prompt.

|
---|---

Figure 5: The precision of LLMs using few-shot CoT - Plan prompt.

|
---|---

Figure 6: The precision of LLMs using few-shot CoT - SC prompt.

Based on the definition in eq. 3, precision ignores the abstained and
unstructured responses. The detailed precision results as well as the
abstained and unstructured ratio are shown in Figures 4, 5 and 6.

The precision of the answer gradually improves with the size of the model.
However, Mistral 7B and Qwen 14B are competitive in terms of reasoning
performance compared to models with ten times more parameters. While Vicuna
33B has an intermediate model size, its performance is low. It is also worth
noting that Qwen variants exhibit a high rate of abstention. This leads to
abstaining from answering uncertain questions and achieving higher precision,
but at the cost of reduced recall for correct answers and reasoning.

###  D.3 Detailed Results of Recall

LLMs | Size | CWQ | GrailQA
---|---|---|---
Answer | Reasoning | Answer | Reasoning
|  | Fewshot CoT
Mistral | 7B | 35.67 | 24.64 | 15.93 | 2.07
Qwen | 7B | 28.36 | 16.9 | 11.48 | 1.4
Qwen | 14B | 36.37 | 24.65 | 16.55 | 1.87
Vicuna | 33B | 42.3 | 15.13 | 17.17 | 0.89
LLaMA2 | 70B | 49.29 | 33.63 | 21.6 | 2.82
ChatGPT | 175B | 48.17 | 35.88 | 21.55 | 3.8
|  | Fewshot CoT - Plan
Mistral | 7B | 36.18 | 25.02 | 16.67 | 3.24
Qwen | 7B | 34.13 | 20.78 | 12.16 | 1.82
Qwen | 14B | 36.35 | 24.88 | 16.14 | 2.11
Vicuna | 33B | 47.6 | 19.74 | 19.33 | 1.94
LLaMA2 | 70B | 49.94 | 36.84 | 21.76 | 3.2
ChatGPT | 175B | 51.11 | 38.13 | 23.4 | 4.18
|  | Fewshot CoT - SC
Mistral | 7B | 40.57 | 30.17 | 16.52 | 2.57
Qwen | 7B | 37.2 | 22.37 | 12.45 | 2.07
Qwen | 14B | 38.68 | 27.6 | 18.88 | 2.91
Vicuna | 33B | 46.29 | 21.14 | 18.65 | 1.86
LLaMA2 | 70B | 50.16 | 36.81 | 21.76 | 3.2
ChatGPT | 175B | 50.71 | 39.92 | 23.78 | 4.63

Table 7:  The recall of LLMs on CWQ and GrailQA datasets.

The recall is calculated on all types of responses. Thus, we directly report
the recall in Table 7.

###  D.4 Case Studies

We present the detailed cases of different error types in Table 8.

Correct Answer & Correct Reasoning |  | Question:
---
People from the country that contains Corfu speak what language?
Groundtruth:
[["Corfu","location.country.administrative_divisions","Greece"],
["Greece","location.country.languages_spoken","Greek Language"]]
LLM CoT Answer:
1\. Corfu is an island located in Greece.
2\. Greece is a country that contains Corfu.
3\. The primary language spoken in Greece is Greek.
So the answer is (Greek).
Reasoning path from our framework:
1\. [["Corfu","location.country.administrative_divisions","Greece"]
2\. "Greece","location.country.languages_spoken","Greek Language"]]
Correct Answer & Incorrect Reasoning |  | Question:
---
What is the currency in the country where the Brazilian cruzado is also used?
Groundtruth:
[["Brazilian cruzado","location.country.currency_formerly_used","Brazil"],
["Brazil","location.country.currency_used","Brazilian real"]]
LLM CoT Answer:
1\. The Brazilian cruzado was the currency of Brazil from 1986 to 1989.
2\. Brazil is the country where the Brazilian cruzado was used.
So the answer is (Brazilian real).
Reasoning path from our framework:
1\. ["Brazilian cruzado","location.country.currency_formerly_used","Brazil"]
2\. ["Brazilian cruzado","location.country.currency_formerly_used","Brazil"]
Incorrect Answer & Correct Reasoning |  | Question:
---
Where was the main artist featured in the Rihanna: Live in Concert Tour
raised?
Groundtruth:
[["Rihanna: Live in Concert Tour","music.artist.concert_tours","Rihanna"],
["Rihanna","people.person.place_of_birth","Saint Michael Parish"]]
LLM CoT Answer:
1\. The main artist featured in the Rihanna: Live in Concert Tour is Rihanna.
2\. Rihanna was raised in Barbados.
So the answer is (Barbados).
Reasoning path from our framework:
1\. ["Rihanna: Live in Concert Tour","music.artist.concert_tours","Rihanna"]
2\. ["Rihanna","people.person.nationality","Barbados"]
Incorrect Answer & Incorrect Reasoning |  | Question:
---
Where did the author who published "The Story of My Life" die?
Groundtruth:
[["The story of my life","book.author.book_editions_published","Helen
Keller"],
["Helen Keller","people.deceased_person.place_of_death","Easton"]]
LLM CoT Answer:
1\. "The Story of My Life" is a book written by Helen Keller.
2\. Helen Keller died in Connecticut, USA.
So the answer is (Connecticut, USA).
Reasoning path from our framework:
1\. ["The story of my life","book.author.book_editions_published","Helen
Keller"],
2\. ["Helen Keller","people.deceased_person.place_of_death","Easton"],p=0.57

Table 8:  Examples of answer and reasoning accuracy of generative evaluation
framework.

##  Appendix E Prompts

###  E.1 Discriminative Evaluation Prompts

Zero-shot Discriminative Evaluation Prompt A reasoning path is a sequence of
triples that can be used to derive the answer of given question. A valid
reasoning path should follow these rules: 1\. No factual errors: Each triple
in the reasoning path should adhere to real-world factual knowledge. 2\.
Coherence: The tail entity of the previous triple should be the head entity of
the next triple. 3\. Correctness: The reasoning path should lead to the
correct answer at the last tail entity. Given this reasoning path, do you
think this is a valid path to derive the answer of given question? If yes
please answer "YES", otherwise please answer "NO". Question: <Question>
Answer: <Answer> Reasoning path: <Reasoning Path>

Figure 7: The zero-shot prompt used for discriminative evaluation

Zero-shot CoT Discriminative Evaluation Prompt A reasoning path is a sequence
of triples that can be used to derive the answer of given question. A valid
reasoning path should follow these rules: 1\. No factual errors: Each triple
in the reasoning path should adhere to real-world factual knowledge. 2\.
Coherence: The tail entity of the previous triple should be the head entity of
the next triple. 3\. Correctness: The reasoning path should lead to the
correct answer at the last tail entity. Given this reasoning path, do you
think this is a valid path to answer the question? If yes please answer "YES",
otherwise please answer "NO". Let’s think it step by step. Question:
<Question> Answer: <Answer> Reasoning path: <Reasoning Path>

Figure 8: The zero-shot CoT prompt used for discriminative evaluation.

Few-shot Discriminative Evaluation Prompt A reasoning path is a sequence of
triples that can be used to derive the answer of given question. A valid
reasoning path should follow these rules: 1\. No factual errors: Each triple
in the reasoning path should adhere to real-world factual knowledge. 2\.
Coherence: The tail entity of the previous triple should be the head entity of
the next triple. 3\. Correctness: The reasoning path should lead to the
correct answer at the last tail entity. Given this reasoning path, do you
think this is a valid path to answer the question? If yes please answer "YES",
otherwise please answer "NO". Here are some examples: ## Input: Question: What
type of government is used in the country with Northern District? Answer:
Parliamentary system Reasoning Paths: Step 1: Northern District ->
location.administrative_division.first_level_division_of -> Israel Step 2:
Israel -> government.form_of_government.countries -> Parliamentary system ##
Output: YES ## Input: Question: Where is the home stadium of the team who won
the 1946 World Series championship? Answer: Busch Stadium Reasoning Paths:
Step 1: 1946 World Series -> sports.sports_team.championships -> St. Louis
Cardinals Step 2: St. Louis Cardinals -> sports.sports_team.arena_stadium ->
Roger Dean Stadium ## Output: NO ## Input: Question: In which American
Southern City did the ""Downs"" composer die? Answer: New Orleans Reasoning
Paths: Step 1: Alex Chilton -> people.deceased_person.place_of_death -> New
Orleans Step 2: Downs -> music.composer.compositions -> Alex Chilton ##
Output: NO ## Input: Question: Where was the main artist featured in the
Rihanna: Live in Concert Tour raised? Answer: Saint Michael Parish Reasoning
Paths: Step 1: Rihanna: Live in Concert Tour -> music.concert_tour.artist ->
Rihanna Step 2: Rihanna -> music.track_contribution.role -> Vocals ## Output:
NO ## Input: Question: <Question> Answer: <Answer> Reasoning path: <Reasoning
Path> ## Output:

Figure 9: The few-shot prompt used for discriminative evaluation.

Few-shot CoT Discriminative Evaluation Prompt A reasoning path is a sequence
of triples that can be used to derive the answer of given question. A valid
reasoning path should follow these rules: 1\. No factual errors: Each triple
in the reasoning path should adhere to real-world factual knowledge. 2\.
Coherence: The tail entity of the previous triple should be the head entity of
the next triple. 3\. Correctness: The reasoning path should lead to the
correct answer at the last tail entity. Given this reasoning path, do you
think this is a valid path to answer the question? If yes please answer "YES",
otherwise please answer "NO". Here are some examples: ## Input: Question: What
type of government is used in the country with Northern District? Answer:
Parliamentary system Reasoning Paths: Step 1: Northern District ->
location.administrative_division.first_level_division_of -> Israel Step 2:
Israel -> government.form_of_government.countries -> Parliamentary system ##
Output: This reasoning path indicates that: 1\. "Northern District" is a
location within some country. 2\. The reasoning path mentions "Northern
District -> location.administrative_division.first_level_division_of ->
Israel," indicating that the Northern District is part of Israel. 3\. It
further states "Israel -> government.form_of_government.countries," suggesting
that Israel’s form of government is being discussed. 4\. The last part of the
reasoning path indicates that Israel has a "Parliamentary system." Based on
the provided reasoning paths, it can be concluded that the type of government
used in the country with the Northern District (Israel) is a Parliamentary
system. Therefore, the path adheres to the definition of valid reasoning path.
The answer is "YES" ## Input: Question: Where is the home stadium of the team
who won the 1946 World Series championship? Answer: Busch Stadium Reasoning
Paths: Step 1: 1946 World Series -> sports.sports_team.championships -> St.
Louis Cardinals Step 2: St. Louis Cardinals ->
sports.sports_team.arena_stadium -> Roger Dean Stadium ## Output: This
reasoning path indicates that: 1\. St. Louis Cardinals as the team that won
the 1946 World Series 2\. Roger Dean Stadium is the stadium associated with
the St. Louis Cardinals. However, the home stadium of St. Louis Cardinals is
Busch Stadium, not Roger Dean Stadium. Therefore, this path contains factual
errors. The answer is "NO". ## Input: Question: In which American Southern
City did the ""Downs"" composer die? Answer: New Orleans Reasoning Paths: Step
1: Alex Chilton -> people.deceased_person.place_of_death -> New Orleans Step
2: Downs -> music.composer.compositions -> Alex Chilton ## Output: This
reasoning path indicates that: 1\. Alex Chilton was dead in New Orleans 2\.
The composition of Downs is Alex Chilton Even through the first step of
reasoning path leads to the correct answer, which is New Orleans, the
reasoning path is not coherent. To answer the question, we need to first the
composition of Downs which is Alex Chilton, then we find the death place of
Alex Chilton which is New Orleans. Therefore, the answer is "NO". ## Input:
Question: Where was the main artist featured in the Rihanna: Live in Concert
Tour raised? Answer: Saint Michael Parish Reasoning Paths: Step 1: Rihanna:
Live in Concert Tour -> music.concert_tour.artist -> Rihanna Step 2: Rihanna
-> music.track_contribution.role -> Vocals ## Output: This reasoning path
indicates that: 1\. The artist of Rihanna: Live in Concert Tour is Rihanna 2\.
Rihanna is a vocal artist Even through there are no factual erros and the
reasoning path is coherent, the reasoning path does not lead to the correct
answer. The question asks for the birth place of the main artist, not the role
of the artist. Therefore, the answer is "NO". ## Input: Question: <Question>
Answer: <Answer> Reasoning path: <Reasoning Path> ## Output:

Figure 10: The few-shot CoT prompt used for discriminative evaluation.

We present the zero-shot, zero-shot CoT, few-shot, and few-shot CoT prompts in
Figures 7, 8, 9 and 10.

###  E.2 Generative Evaluation Prompts

We present the few-shot, few-shot plan prompts in Figures 11 and 12.

Few-shot CoT prompt for Generative Evaluation 1\. <step1> 2\. <step2> … So the
answer is (<answer>). Make sure that the answer uses the above format and
answers the question step by step. Q: when Lou Seal is the mascot for the team
that last won the World Series? A: Let’s work this out in a step by step way
to be sure we have the right answer. 1\. Lou Seal is the mascot for the San
Francisco Giants. 2\. The San Francisco Giants are associated with the sports
championship event, the 2014 World Series. So the answer is (2014 World
Series). Q: What nation has an army or more than 713480 people and borders the
country of Bolivia? A: Let’s work this out in a step by step way to be sure we
have the right answer. 1\. Bolivia is a landlocked country located in South
America. 2\. Bolivia shares its borders with several countries, including
Argentina, Brazil, Chile, Paraguay, and Peru. So the answer is (Brazil). Q:
What movie was displayed at the 2012 Refugee Film Festival and had Angelia
Jolie directing it? A: Let’s work this out in a step by step way to be sure we
have the right answer. 1\. Angelia Jolie whose first major film as a director
which named “In the Land of Blood and Honey”. 2\. “In the Land of Blood and
Honey” was shown at the 2012 Refugee Film Festival. So the answer is (In the
Land of Blood and Honey). Q: How many Mary Mary sisters? A: Let’s work this
out in a step by step way to be sure we have the right answer. 1\. Mary Mary
is a group which has a member named Tina Campbell 2\. Mary Mary is a group
which has a member named Erica Campbell So the answer is (Erica Campbell, Tina
Campbell). Q: Which languages are used in the location that the breed Egyptian
Mau started in? A: Let’s work this out in a step by step way to be sure we
have the right answer. 1\. The Egyptian Mau is a breed of domestic cat that is
believed to have originated in Egypt. 2\. In Egypt, the primary language
spoken is Arabic, besides Domari or Nobiin. So the answer is (Arabic, Domari,
Nobiin). Q: {Question}
A: Let’s work this out in a step by step way to be sure we have the right
answer.

Figure 11: The few-shot CoT prompt used for generative evaluation.

Few-shot CoT - Plan prompt used for Generative Evaluation Relation path is a
sequence relation that describes each step of the reasoning process. You first
give a relation path as a HINT, then reason the answer step-by-step based on
it. HINT: 1\. <step1> 2\. <step2> … So the answer is (<answer>). Make sure
that the answer uses the above format and answers the question step by step.
Q: when Lou Seal is the mascot for the team that last won the World Series? A:
Let’s work this out in a step by step way to be sure we have the right answer.
HINT: sports.sports_team.team_mascot -> sports.sports_team.championships 1\.
Lou Seal is the mascot for the San Francisco Giants. 2\. The San Francisco
Giants are associated with the sports championship event, the 2014 World
Series. So the answer is (2014 World Series). Q: What nation has an army or
more than 713480 people and borders the country of Bolivia? A: Let’s work this
out in a step by step way to be sure we have the right answer. HINT:
geography.river.basin_countries -> location.location.partially_contains 1\.
Bolivia is a landlocked country located in South America. 2\. Bolivia shares
its borders with several countries, including Argentina, Brazil, Chile,
Paraguay, and Peru. So the answer is (Brazil). Q: What movie was displayed at
the 2012 Refugee Film Festival and had Angelia Jolie directing it? A: Let’s
work this out in a step by step way to be sure we have the right answer. HINT:
film.director.film ->
film.film_regional_release_date.film_regional_debut_venue 1\. Angelia Jolie
whose first major film as a director which named “In the Land of Blood and
Honey”. 2\. “In the Land of Blood and Honey” was shown at the 2012 Refugee
Film Festival. So the answer is (In the Land of Blood and Honey). Q: How many
Mary Mary sisters? A: Let’s work this out in a step by step way to be sure we
have the right answer. HINT: music.group_membership.member ->
music.group_membership.member 1\. Mary Mary is a group which has a member
named Tina Campbell 2\. Mary Mary is a group which has a member named Erica
Campbell So the answer is (Erica Campbell, Tina Campbell). Q: Which languages
are used in the location that the breed Egyptian Mau started in? A: Let’s work
this out in a step by step way to be sure we have the right answer. HINT:
biology.breed_origin.breeds_originating_here ->
location.country.languages_spoken 1\. The Egyptian Mau is a breed of domestic
cat that is believed to have originated in Egypt. 2\. In Egypt, the primary
language spoken is Arabic, besides Domari or Nobiin. So the answer is (Arabic,
Domari, Nobiin). Q: {Question}
A: Let’s work this out in a step by step way to be sure we have the right
answer.

Figure 12: The few-shot CoT - Plan prompt used for generative evaluation.