# Repair of Reed-Solomon Codes in the Presence of Erroneous Nodes

Stanislav Kruglik1, Gaojun Luo1, Wilton Kim1, Shubhransh Singhvi2, Han Mao
Kiah1, San Ling1, Huaxiong Wang1 {stanislav.kruglik, gaojun.luo,
<EMAIL_ADDRESS><EMAIL_ADDRESS>{hmkiah,
lingsan<EMAIL_ADDRESS>1 School of Physical and Mathematical Sciences,
Nanyang Technological University, Singapore  2 Signal Processing &
Communications Research Center, International Institute of Information
Technology, Hyderabad, India

###### Abstract

We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code
and ask: can we correctly repair a failed node in the presence of erroneous
nodes? Equivalently, we consider the collection of downloaded traces as a code
and investigate its code-distance properties. We propose three lower bounds on
its minimum distance and study methods to efficiently correct errors close to
these bounds.

##  I Introduction

Distributed storage becomes more popular as data volume increases
exponentially in all industries. The data can be represented as
$x\in\mathbb{F}^{k}$ for some finite field $\mathbb{F}$. To protect against
erasures, the data is encoded into $c=(c_{1},\ldots,c_{n})$ and each $c_{i}$
is kept in the server $i$. One important performance metric of distributed
storage is the total amount of information to download to perform the
recovery, called the repair bandwidth, which was introduced in [1]. Reed-
Solomon code [2, 3] is widely used as it allows one to recover $x$ by
utilizing $k$ available servers. However, this approach is not optimal for the
case of repairing a single erasure as we need to download $k$ codesymbols to
recover one codesymbol.

Many studies have been conducted to improve the repair bandwidth [4, 5]. The
pioneering work of Guruswami and Wootters [6] revisits the widely used Reed-
Solomon codes and shows that it is possible to decrease the repair bandwidth
of single erasure dramatically when more than $k$ nodes are available. Roughly
speaking, in this scheme, instead of downloading $k$ symbols in $\mathbb{F}$,
we download $(n-1)$ sub-symbols in a base field $\mathbb{B}$ called traces.
Then using certain parity-check equations (see Section II-A for details), we
then recover the failed node.

Later, the Guruswami-Wooters repair scheme, or the trace repair framework, was
extended to different scenarios in a number of works [7, 8, 9, 10, 11, 12, 13,
14]. All of these studies, however, assume that all available nodes give
correct information.

In this paper, we consider the case where nodes can provide wrong information
and we attempt to answer the following question: is it possible to correctly
repair a node with low bandwidth in the presence of erroneous nodes?
Previously, the problem of erroneous trace correction in Reed-Solomon repair
was solved for the case of the high sub-packetization regime [15]. Our
approach, on the other hand, is applicable to any sub-packetization level.
Furthermore, applications extend beyond coding for distributed storage. In the
case of secret sharing schemes based on Reed-Solomon codes (i.e., Shamir’s
secret sharing scheme [16]), our methods allow shareholders to successfully
obtain a secret in the presence of malicious shareholders.

###  I-A Motivating Example

Let $\mathbb{F}=GF(16)$. Set $n=16$ and $k=2$, and we consider a
$[16,2,15]-$RS code. So, we can correct five errors and four erasures. Hence,
in the classical approach, when there are at most five erroneous nodes, we
download $(16-4)=12$ symbols from any twelve available nodes to repair a
failed node. In other words, the repair bandwidth in this case is $12(4)=48$
bits.

On the other hand, we consider $\mathbb{F}$ as an extension field of
$\mathbb{B}=GF(4)$. Then Guruswami-Wooters repair scheme [6] allow us to
repair a failed node by downloading 15 traces (see Theorem 2). Later, we show
that the traces form a $\mathbb{B}$-linear code with minimum distance 11 (see
Theorem 3). Therefore, using these 15 traces, we are able to correct five
errors. Here, our repair bandwidth is $15(2)=30$ bits only.

###  I-B Our Contributions

In the spirit of Guruswami and Wootters, our primary objective is to simply
understand what can be done for Reed-Solomon codes. Specifically, we focus on
the Guruswami-Wootters repair scheme (which we review in Section II-A) and
ask: can we correctly repair a failed node in the presence of erroneous nodes?
Equivalently, we consider the collection of traces as a $\mathbb{B}$-linear
code $\mathcal{T}$ and ask what is the minimum distance of this code. In
Section III, we first show this code is in fact a subcode of a generalized
Reed-Solomon code. Hence, we are able to apply efficent decoding algorithms
like Berlekamp-Welch to correct errors. This gives us a lower bound when $k$
is small. For larger values of $k$, we construct additional parity check
equations in $\mathbb{F}$ and use lifted decoding to correct errors (see
Section III-A). Finally, we use the character sums to provide another lower
bound. We remark that similar techniques were used in [17, 18, 19, 20, 21,
22], but most of these works focus on polynomial trace codes, while we
consider more general rational trace codes. To efficiently correct errors
close to these bounds, we modify the famous Guruswami-Sudan list-decoding
algorithm in Section IV. Finally, in Section V, we compare the various bounds
obtained in the paper.

##  II Preliminaries

Let $[n]$ denote the set of integers $\\{1,\ldots,n\\}$. Let $\mathbb{B}$ be
the finite field with $p^{m}$ elements and $\mathbb{F}$ be the extension of
degree $t\geq 1$. So, $|\mathbb{F}|=p^{mt}$ and $|\mathbb{B}|=p^{m}$. We refer
to the elements of $\mathbb{F}$ as symbols and to the elements of $\mathbb{B}$
as sub-symbols. We use $\mathbb{F}[x]$ to denote a ring of polynomials over
finite field $\mathbb{F}$.

An $\mathbb{F}$-linear $[n,k]$ code $\mathcal{C}$ is $k$-dimensional subspace
of $\mathbb{F}^{n}$. We denote the dual of code $\mathcal{C}$ by
$\mathcal{C}^{\perp}$ and so, for each
$\mathbfsl{c}=(c_{1},\ldots,c_{n})\in\mathcal{C}$ and
$\mathbfsl{c}^{\perp}=(c_{1}^{\perp},\ldots,c_{n}^{\perp})\in\mathcal{C}^{\perp}$,
it holds that $\sum_{i=1}^{n}c_{i}c_{i}^{\perp}=0$. We denote the minimum
distance of $\mathcal{C}$ with $d(\mathcal{C})$ and the Singleton bound states
that $d(\mathcal{C})\leq n-k+1$ (see for example [17]). Codes that attain this
bound are called maximum-distance separable (MDS) codes and in this work, we
focus on the following class of MDS codes.

######  Definition 1.

Let $\mathcal{A}\subseteq\mathbb{F}$. The Reed-Solomon code ${\rm
RS}(\mathcal{A},k)$ of dimension $k$ with evaluation points $\mathcal{A}$ is
defined as:

${\rm
RS}(\mathcal{A},k)\triangleq\\{(f(\alpha))_{\alpha\in\mathcal{A}}:f\in\mathbb{F}[x],\deg(f(X))\leq
k-1\\}\,,$

while the generalized Reed-Solomon code ${\rm RS}(\mathcal{A},k)$ of dimension
$k$ with evaluation points $\mathcal{A}\subseteq\mathbb{F}$ and multiplier
vector ${\boldsymbol{\lambda}}\in\mathbb{F}^{n}\setminus\\{\mathbf{0}\\}$ is
defined as:

${\rm
GRS}(\mathcal{A},k,{\boldsymbol{\lambda}})\triangleq\\{(\lambda_{\alpha}f(\alpha))_{\alpha\in\mathcal{A}}:f\in\mathbb{F}[x],\deg(f(X))\leq
k-1\\}\,.$

Clearly, the generalized Reed-Solomon code with multiplier vector
${\boldsymbol{\lambda}}=(1,\ldots,1)$ is a Reed-Solomon code of the same
length and dimension. It is well known (see [17]) that dual of ${\rm
RS}(\mathcal{A},k)$ is ${\rm
GRS}(\mathcal{A},|\mathcal{A}|-k,{\boldsymbol{\lambda}})$ for
${\boldsymbol{\lambda}}=(\lambda_{\alpha})_{\alpha\in\mathcal{A}}$ where

$\lambda_{j}=\frac{1}{\prod_{\alpha_{i}\in\mathcal{A}\setminus\\{\alpha_{j}\\}}(\alpha_{j}-\alpha_{i})}.$
(1)

Note that when $\mathcal{A}=\mathbb{F}$, we have $\lambda_{\alpha}=1$ for all
$\alpha\in\mathcal{A}$. If it is clear from the context, we use $f(x)$ to
denote the polynomial of degree at most $k-1$ corresponding to ${\rm
RS}(\mathcal{A},k)$ and $r(x)$ to denote the polynomial of degree at most
$|\mathcal{A}|-k-1$ corresponding to the dual codeword in
$\mathcal{C}^{\perp}$.

###  II-A Trace Repair Framework

In this section, we discuss about trace repair framework to recover a single
erased node. The main idea of trace repair framework is that we want to
recover a symbol in $\mathbb{F}$ by using sub-symbols in $\mathbb{B}$. Without
loss of generality, let us assume that $f(0)$ is erased. Let
$\mathcal{A}\subseteq\mathbb{F}\setminus\\{0\\}$ be the set of evaluation
points.

We consider trace function ${\rm Tr}:\mathbb{F}\to\mathbb{B}$ defined as

$\displaystyle{\rm
Tr}(x)=\sum_{i=0}^{t-1}{x^{|\mathbb{B}|}}^{i},\quad\text{for all
}x\in\mathbb{F}.$ (2)

Clearly, ${\rm Tr}(x)$ is a polynomial in $x$ with degree $p^{mt-m}$. Next, we
discuss how this trace function helps us in the recovery. We regard
$\mathbb{F}$ as a $\mathbb{B}$-linear vector space of dimension $t$ and let
$\\{u_{1},\ldots,u_{t}\\}$ be a basis of $\mathbb{F}$ over $\mathbb{B}$.
Furthermore, there exists a trace-dual basis
$\\{\widetilde{u}_{1},\ldots,\widetilde{u}_{t}\\}$ for $\mathbb{F}$ such that
${\rm Tr}(u_{i}\widetilde{u}_{j})=1$ if $i=j$, and ${\rm
Tr}(u_{i}\widetilde{u}_{j})=0$, otherwise. The following result plays a
crucial role in our evaluation framework.

######  Proposition 1 ([23, Ch. 2]).

Let $\\{u_{1},\ldots,u_{t}\\}$ be a $\mathbb{B}$-basis of $\mathbb{F}$. Then
there exists a trace-dual basis
$\\{\widetilde{u}_{1},\ldots,\widetilde{u}_{t}\\}$ and we can write each
element $x\in\mathbb{F}$ as

$x=\sum_{i=1}^{t}{\rm Tr}(u_{i}x)\widetilde{u}_{i}.$

This means, in order to recover $f(0)$, we need to determine ${\rm
Tr}(u_{i}\lambda_{0}f(0))$ for all $i=1,\ldots,t$ by downloading certain
information from the remaining nodes. To do so, we consider

$p_{i}(x)=\frac{{\rm Tr}(u_{i}x)}{x},\quad\text{for all }i=1,\ldots,t.$ (3)

We can check that $p_{i}$ is a polynomial of degree $p^{mt-m}-1$ and
$p_{i}(0)=u_{i}$. If $p^{mt-m}-1\leq|\mathcal{A}|-k$, then the following
parity check equations hold

$\displaystyle
u_{i}\lambda_{0}f(0)=\sum_{\alpha\in\mathcal{A}}p_{i}(\alpha)\lambda_{\alpha}f(\alpha).$
(4)

Applying trace function both sides of (4), we obtain

$\displaystyle{\rm Tr}(u_{i}\lambda_{0}f(0))$
$\displaystyle=\sum_{\alpha\in\mathcal{A}}{\rm
Tr}(p_{i}(\alpha)\lambda_{\alpha}f(\alpha))$
$\displaystyle=\sum_{\alpha\in\mathcal{A}}{\rm Tr}(u_{i}\alpha){\rm
Tr}\left(\frac{\lambda_{\alpha}f(\alpha)}{\alpha}\right).$ (5)

Therefore, it suffices to download ${\rm
Tr}(\lambda_{\alpha}f(\alpha)/\alpha)$ from node $\alpha$. This motivates us
to study the following code.

######  Definition 2.

The repair-trace code with evaluation points
$\mathcal{A}\subseteq\mathbb{F}\setminus\\{0\\}$ is defined as:

$\displaystyle\mathcal{T}(\mathcal{A},k)$ $\displaystyle\triangleq\\{({\rm
Tr}(\lambda_{\alpha}f(\alpha)/\alpha))_{\alpha\in\mathcal{A}}:f\in\mathbb{F}[x],$
$\displaystyle\hskip 85.35826pt\deg(f(X))\leq k-1\\}\,.$ (6)

######  Remark 3.

It is possible that $|\mathcal{T}(\mathcal{A},k)|<|\mathbb{F}|^{k}$. That is,
in the definition of $\mathcal{T}$, it is possible for two distinct
polynomials $f$ and $g$ (with degrees at most $k-1$) to correspond to the same
codeword. In other words, ${\rm Tr}(\lambda_{\alpha}f(\alpha)/\alpha)={\rm
Tr}(\lambda_{\alpha}g(\alpha)/\alpha)$ for $\alpha\in\mathcal{A}$.
Nevertheless, $\mathcal{T}(\mathcal{A},k)$ is a $\mathbb{B}$-linear code.

The above technique is summarised into the theorem below.

######  Theorem 2 ([6, Guruswami-Wootters]).

If $|\mathcal{A}|\geq p^{mt-m}-1+k$ and given
$\mathbfsl{c}\in\mathcal{T}(\mathcal{A},k)$, we can efficiently compute
$f(0)$.

Our main task is to determine the minimum distance of
$\mathcal{T}(\mathcal{A},k)$. If the distance is $d$, then we are able to
correct ${\left\lfloor(d-1)/2\right\rfloor}$ errors. In addition, we also
investigate algorithms that are able to correct the number of errors
efficiently.

###  II-B Main Results

In this conference paper, to simplify our exposition, we focus on the case
where the data is stored on a full-length Reed-Solomon code of length
$n=p^{mt}$, dimension $k$ and code rate $R$. Hence, $\lambda_{\alpha}=1$ for
all $\alpha$. Then the repair-trace code is simply
$\mathcal{T}(\mathcal{A},k)=\\{({\rm
Tr}(f(\alpha)/\alpha))_{\alpha\in\mathcal{A}}:\deg(f(X))\leq k-1\\}$ and we
summarize our results in the following theorem.

######  Theorem 3.

Consider the full-length Reed-Solomon code and let $0$ be the failed node
$f(0)$. Let $d$ be the minimum distance of corresponding repair-trace code
$\mathcal{T}(\mathcal{A},k)$ with $\mathcal{A}=\mathbb{F}\setminus\\{0\\}$.
The following bounds on $d$ hold:

  1. (i)

(Degree Bound). If $k\leq p^{m}$, then $d\geq p^{mt}-1-\Delta\triangleq
d_{1}$, where

$\Delta\triangleq\begin{cases}(k-1)p^{mt-m},&\text{ when }k\geq 2,\\\
p^{mt-m}-1,&\text{ when }k=1.\end{cases}$ (7)

  2. (ii)

(Lifted Decoding). If $k\leq p^{mt}-p^{mt-m}$, then
$d\geq\lfloor\frac{p^{mt}-k}{p^{mt-m}}\rfloor\triangleq d_{2}$.

  3. (iii)

(Character Sum Bound). If $k<1+\frac{p^{mt}-1}{\sqrt{p^{mt}}}$,then $d\geq
d_{3}$, where

$\footnotesize
d_{3}\triangleq\begin{cases}\frac{p^{m}-p}{p^{m}}\left(p^{mt}-1-(k-1)\sqrt{p^{mt}}\right),&\text{
when }m\geq 2,\\\ \frac{p-1}{p}\left(p^{t}-1-(k-1)\sqrt{p^{t}}\right),&\text{
when }m=1.\end{cases}$ (8)

We can efficiently correct up to the distances promised by Theorem 3(i) and
(ii). For Theorem 3(iii), we modify the famous Guruswami-Sudan algorithm to
correct errors close to the character sum bound. We do note that results from
Theorem 3(i) and (ii) can be generalized for non-full-length Reed-Solomon
codes.

##  III Lower Bounds for Minimum Distance

In this section, we prove Theorem 3. Recall that $\mathcal{A}$ is a set of
nonzero elements in $\mathbb{F}$. First, we consider the code
$\mathcal{T}_{1}\triangleq\left\\{\left(\alpha^{p^{mt-m}}c_{\alpha}\right)_{\alpha\in\mathcal{A}}:\mathbfsl{c}\in\mathcal{T}(A,k)\right\\}$
and show that it is a subcode of some generalized Reed-Solomon code.

######  Proposition 4.

Let $\Delta$ be defined in (7). If $\Delta<|\mathcal{A}|$, then
$\mathcal{T}_{1}\subseteq{\rm
GRS}(\mathcal{A},\Delta+1,{\boldsymbol{\mu}}_{1})$ for some
${\boldsymbol{\mu}}_{1}$

###### Proof.

We note that $\mathbfsl{c}^{*}\in\mathcal{T}_{1}$ can be represented as

$\displaystyle(F(\alpha))_{\alpha\in\mathcal{A}}$
$\displaystyle=\left(\alpha^{p^{mt-m}}{\rm
Tr}(\frac{f(\alpha)}{\alpha})\right)_{\alpha\in\mathcal{A}}$
$\displaystyle=\left(\alpha^{p^{mt-m}}\sum_{i=0}^{t-1}\left(\frac{f(\alpha)}{\alpha}\right)^{p^{mi}}\right)_{\alpha\in\mathcal{A}}$
$\displaystyle=\left(\alpha^{p^{mt-m-1}}f(\alpha)+\cdots+f(\alpha)^{p^{mt-m}}\right)_{\alpha\in\mathcal{A}},$

where $F(x)$ is a polynomial of degree
$\max(k+p^{mt-m}-2,\ldots,(k-1)p^{mt-m})$. This fact finishes the proof. ∎

Since $\mathcal{T}_{1}$ is equivalent to the repair-trace code
$\mathcal{T}(\mathcal{A},k)$ (since $\alpha\neq 0$ for all
$\alpha\in\mathcal{A}$), the minimum distance of $\mathcal{T}(\mathcal{A},k)$
is at least $|\mathcal{A}|-\Delta$ and we obtain Theorem 3(i). We note that we
can efficiently correct up to the promised distance using any Reed-Solomon
code bounded-distance decoder (see [17]).

###  III-A Lifted Decoding

Proposition 4 applies only when $k$ is at most $\sqrt{n}$. In this section, we
study the other extreme and look for bounds that apply when $k$ is large. In
fact, we demonstrate that $\mathcal{T}(\mathcal{A},k)$ is a subcode of a
generalized Reed-Solomon code with a different set of parameters and sub-
constant minimum distance at least $p^{m}(1-R)$. To this end, we form the
following set of parity-check equations similar to (5).

######  Lemma 5.

For $2\leq\ell\leq{\left\lfloor\frac{p^{mt}-k}{p^{mt-m}}\right\rfloor}$, we
have that

$\sum_{\alpha\in\mathcal{A}}\alpha^{\ell}{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)=0.$

###### Proof.

Let $\\{u_{1},\ldots,u_{t}\\}$ be the basis of $\mathbb{F}$ over $\mathbb{B}$
and $\\{\eta_{1},\ldots,\eta_{t}\\}$ be its trace-dual basis. We have the
following codewords of the dual of ${\rm RS}(\mathcal{A}\cup\\{0\\},k)$:

$r_{i}^{(\ell)}(x)\triangleq\frac{\textrm{Tr}\left(u_{i}x^{\ell}\right)}{x},$
(9)

for all $i=1,\ldots,t$ and
$\ell=2,\ldots,\lfloor\frac{p^{mt}-k}{p^{mt-m}}\rfloor$.

It is clear that $r_{i}^{(\ell)}(0)=0$ and the polynomial $r_{i}{(\ell)}(x)$
is of degree at most $\ell p^{mt-m}-1\leq p^{mt}-k-1$ for all $i$ and $\ell$.
Then we have the following parity-check equations for code ${\rm
RS}(\mathcal{A}\cup\\{0\\},k)$.

$r_{i}^{(\ell)}(0)f(0)+\sum_{\alpha\in\mathcal{A}}r_{i}^{(\ell)}(\alpha)f(\alpha)=0.$

Following the definition of $r_{i}^{(\ell)}(x)$, we have

$\sum_{\alpha\in\mathcal{A}}f(\alpha)\frac{{\rm
Tr}(u_{i}\alpha^{\ell})}{\alpha}=0.$ (10)

Applying the trace function to both sides of (10) and employing the fact that
${\rm Tr}(a{\rm Tr}(b))={\rm Tr}(b{\rm Tr}(a))={\rm Tr}(a){\rm Tr}(b)$ we have

$\sum_{\alpha\in\mathcal{A}}{\rm Tr}\left(u_{i}\alpha^{\ell}{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)\right)=0.$

Utilizing the linearity of trace function, we have

${\rm Tr}\left(\sum_{\alpha\in\mathcal{A}}u_{i}\alpha^{l}{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)\right)={\rm
Tr}\left(u_{i}\sum_{\alpha\in\mathcal{A}}\alpha^{\ell}{\rm
Tr}\left(\frac{f(\alpha}{\alpha}\right)\right)=0\,.$

Consequently,

$\sum_{i=1}^{t}\eta_{i}{\rm
Tr}\left(u_{i}\sum_{\alpha\in\mathcal{A}}\alpha^{\ell}{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)\right)=\sum_{\alpha\in\mathcal{A}}\alpha^{\ell}{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)=0.$

∎

Then the following proposition is immediate from Lemma 5.

######  Proposition 6.

$\mathcal{T}(\mathcal{A},k)\subseteq{\rm
GRS}(\mathcal{A},p^{mt}-\lfloor\frac{p^{mt}-k}{p^{mt-m}}\rfloor,{\boldsymbol{\mu}}_{2})$
for some multiplier ${\boldsymbol{\mu}}_{2}$.

###### Proof.

From Lemma 5, it is clear that parity-check matrix of code $\mathcal{T}$ has
the following rows

$\mathbfsl{H}=\begin{bmatrix}\alpha_{1}^{2}&\alpha_{2}^{2}&\cdots&\alpha_{n}^{2}\\\
\alpha_{1}^{3}&\alpha_{2}^{3}&\cdots&\alpha_{n}^{3}\\\
\vdots&\vdots&&\vdots\\\
\alpha_{1}^{\ell}&\alpha_{2}^{\ell}&\cdots&\alpha_{n}^{\ell}\\\
\end{bmatrix}\,.$

for $\ell=\lfloor\frac{p^{mt}-k}{p^{mt-m}}\rfloor$ and
$\mathcal{A}=\\{\alpha_{1},\ldots,\alpha_{n}\\}$. It is clear that the dual of
the code generated by $\mathbfsl{H}$ is a ${\rm
GRS}(\mathcal{A},|\mathcal{A}|-\ell+1,{\boldsymbol{\mu}}_{2})$ for some
multiplier ${\boldsymbol{\mu}}_{2}$. Therefore $\mathcal{T}(\mathcal{A},k)$ is
a subcode of the latter and we obtain the proposition. ∎

Therefore, every nonzero codeword in $\mathcal{T}(\mathcal{A},k)$ has weight
at least $\lfloor\frac{p^{mt}-k}{p^{mt-m}}\rfloor$ and statement of Theorem
3(ii) follows.

###  III-B Character Sum Bound

In this subsection, we prove the Theorem 3(iii) by modifying the proof of [17,
Theorem 5.4] for two cases, $m=1$ and $m>1$. Before we proceed further, let us
provide a short overview of character sums and refer the reader to [23, 24]
for more details. Assume that $\omega=e^{\frac{2i\pi}{p}}$ is a primitive
$p$-th root of complex unity. It is well known that for any $x\in\mathbb{B}$
it holds that

$\sum_{a\in\mathbb{B}\setminus\\{0\\}}\omega^{ax}=\begin{cases}p-1&\text{if
$x=0$}\\\ -1&\text{otherwise}.\end{cases}$ (11)

For any element $a$ from $\mathbb{F}$, we can define an additive character as
function $\chi_{a}(x)=\omega^{{\rm Abs}{\rm Tr}(ax)}$, where $x\in\mathbb{F}$
and ${\rm Abs}{\rm Tr}(\cdot)$ is the trace function from $\mathbb{F}$ to the
finite filed with $p$ element. Character defined by $\chi_{0}(x)=x$ is called
trivial, while all other characters are called non-trivial. The additive
character $\chi_{1}(x)$ is said to be canonical. It is well known that all
additive characters of $\mathbb{F}$ form a group of order $p^{m}$ isomorhic to
the additive group of $\mathbb{F}$ and the following property holds

$\chi_{a+b}(x)=\chi_{a}(x)\chi_{b}(x).$ (12)

The orthogonality relation of additive characters is given by

$\sum_{x\in\mathbb{F}}\chi_{a}(x)=\begin{cases}0,&\mbox{if $a\neq 0$}\\\
p^{mt},&\mbox{if $a=0$}\end{cases}$ (13)

By the same way, for any element $a$ from multiplicative group of $\mathbb{F}$
we can define a multiplicative character as a function
$\Psi_{a}(g^{k})=e^{\frac{2i\pi ak}{p^{mt}-1}}$, where $g$ is a fixed
primitive element of $\mathbb{F}$. Character defined by $\Psi_{0}(x)=1$ is
called trivial, while all other characters are called non-trivial. It is well
known that all multiplicative characters of $\mathbb{F}$ form a group of order
$p^{mt}-1$ isomorphic to the multiplicative group of $\mathbb{F}$ and the
following property holds

$\Psi_{ab}(x)=\Psi_{a}(x)\Psi_{b}(x).$ (14)

Our further derivations rely on the upper bound for absolute value of the
following non-degenerate sum

$S(\chi_{a},\Psi_{b};\phi,\varphi)=\sum_{x\in\mathbb{F}\setminus\mathcal{S}}\chi_{a}(\phi(x))\Psi_{b}(\varphi(x)),$
(15)

where $\mathcal{S}$ denotes the set of poles of functions
$\phi(x)\in\mathbb{F}[x]$ and $\varphi(x)\in\mathbb{F}[x]$. Non-degenerate
property means that $a\phi(x)\neq h(x)^{p}-h(x)+c$ and $\varphi\neq
ch(x)^{p^{mt}-1}$ for any $h(x)\in\mathbb{F}[x]$ and $c\in\mathbb{F}$. It is
clear that $a\phi(x)=h(x)^{p}-h(x)+c$ and $\varphi(x)=ch(x)^{p^{mt}-1}$ imply
that $\chi_{a}(\phi(x))$ and $\Psi_{b}(\varphi(x))$ are respective constant
numbers for each $x\in\mathbb{F}\setminus\mathcal{S}$. Essentially, we have
the following generalization of Weil estimate proved by Castro and Moreno to
the case of rational functions $\phi(x)$ and $\varphi(x)$ in [25] in notations
of [26] and [27].

######  Proposition 7 ([27, Lemma 2.1]).

Let $\phi(x)$, $\varphi(x)$ be rational functions in $\mathbb{F}$, $\chi_{a}$
be non-trivial additive character on $\mathbb{F}$ and $\Psi_{b}$ be non-
trivial multiplicative character on $\mathbb{F}$. Let $\mathcal{S}$ be the set
of poles of functions $\phi$ and $\varphi$ in $\mathbb{F}$. Further, let $l$
be the number of distinct zeros and non-infinite poles of $\phi$. Let $l_{1}$
be the number of all poles of $\varphi$ and $l_{0}$ be the sum of their
multiplicities. Let $l_{2}$ be the number of non-infinite poles of $\varphi$
which are zeros or poles of $\phi$. Then

$\displaystyle|S(\chi_{a},\Psi_{b};\phi,\varphi)|=|\sum_{x\in\mathbb{F}\setminus\mathcal{S}}\chi_{a}(\phi)\Psi_{b}(\varphi)|$
$\displaystyle\leq(l+l_{0}+l_{1}-l_{2}-2)\sqrt{p^{mt}}$ (16)

By setting $\varphi(x)=1$ and $\phi(x)=\frac{f(x)}{x}$ so that $a\phi(x)\neq
h(x)^{p}-h(x)+c$ for any $h(x)\in\mathbb{F}[x]$ and $c\in\mathbb{F}$, we
receive the following estimate:

$\displaystyle\left|\sum_{x\in\mathbb{F}\setminus\\{0\\}}\chi_{a}\left(\frac{f(x)}{x}\right)\right|\leq(k-1)\sqrt{p^{mt}}.$
(17)

######  Proposition 8.

If $\mathcal{A}=\mathbb{F}\setminus\\{0\\}$ and $m=1$, then every nonzero word
in $\mathcal{T}(\mathcal{A},k)$ has weight at least

$\frac{p-1}{p}\left(|\mathcal{A}|-(k-1)\sqrt{p^{t}}\right)$ (18)

###### Proof.

We distinguish between two cases.

Case 1. $f(x)=x(h(x))^{p}-xh(x)+xb$ for some $h\in\mathbb{F}[x]$ and
$b\in\mathbb{F}$. In this case,

$\displaystyle c_{j}$ $\displaystyle={\rm
Tr}\left(\frac{f(\alpha_{j})}{\alpha_{j}}\right)={\rm
Tr}\left(h(\alpha_{j})^{p}\right)-{\rm Tr}(h(\alpha_{j}))+{\rm Tr}(b)$
$\displaystyle={\rm Tr}\left(h(\alpha_{j})\right)^{p}-{\rm
Tr}(h(\alpha_{j}))+{\rm Tr}(b)={\rm Tr}(b),$

In other words, $\mathbfsl{c}$ is a multiple of the all-ones vector.

Case 2. $f(x)\neq x(h(x))^{p}-xh(x)+xb$ for any $h\in\mathbb{F}[x]$ and
$b\in\mathbb{F}$. In this case we can form the non-degenerate sum and apply an
estimate (7). For $p$-th root of complex unity we can write down that

$\displaystyle\sum_{j=1}^{p^{t}-1}\left(\sum_{a\in\mathbb{B}\setminus\\{0\\}}\omega^{ac_{j}}\right)$
$\displaystyle=(p-1)(p^{t}-1-w(\mathbfsl{c}))-w(\mathbfsl{c})$
$\displaystyle=(p-1)(p^{t}-1)-pw(\mathbfsl{c}),$ (19)

where $w(\mathbfsl{c})$ is the Hamming weight of the codeword $\mathbf{c}$.

Utilizing the fact that $\omega^{a\textrm{Tr}(\frac{f(x)}{x})}$ for
$a\in\mathbb{B}\setminus\\{0\\}$ is non-trivial additive character
$\chi_{a}(\frac{f(x)}{x})$ we have

$\displaystyle\left|\sum_{a\in\mathbb{B}\setminus\\{0\\}}\sum_{j=1}^{p^{t}-1}w^{ac_{j}}\right|$
$\displaystyle=\left|\sum_{a\in\mathbb{B}\setminus\\{0\\}}\sum_{x\in\mathbb{F}\setminus\\{0\\}}\chi_{a}(\frac{f(x)}{x})\right|$
$\displaystyle\leq\sum_{a\in\mathbb{B}\setminus\\{0\\}}\left|\sum_{x\in\mathbb{F}\setminus\\{0\\}}\chi_{a}(\frac{f(x)}{x})\right|.$
(20)

Applying the estimate (7) we have

$\left|(p-1)(p^{t}-1)-pw(\mathbfsl{c})\right|\leq(p-1)(k-1)\sqrt{p^{t}}.$ (21)

Combining two cases, we get the proposition statement. ∎

######  Proposition 9.

If $\mathcal{A}=\mathbb{F}\setminus\\{0\\}$ and $m>1$, then every nonzero word
in $\mathcal{T}(\mathcal{A},k)$ has weight at least

$\frac{p^{m}-p}{p^{m}}\left(|\mathcal{A}|-(k-1)\sqrt{p^{mt}}\right)$ (22)

###### Proof.

Let $\mathbfsl{c}=\left({\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)\right)_{\alpha\in\mathcal{A}}$ be a
codeword of $\mathcal{T}(\mathcal{A},k)$. Let $\lambda_{1}$ be the canonical
additive character of $\mathbb{B}$. By the orthogonality relation of additive
characters, we deduce that

$\displaystyle w(\mathbfsl{c})$
$\displaystyle=p^{mt}-1-\\#\left\\{\alpha\in\mathcal{A}:{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)=0\right\\}$
$\displaystyle=p^{mt}-1-\frac{1}{p^{m}}\sum_{\alpha\in\mathcal{A}}\sum_{a\in\mathbb{B}}\lambda_{1}\left(a{\rm
Tr}\left(\frac{f(\alpha)}{\alpha}\right)\right)$
$\displaystyle=p^{mt}-1-\frac{1}{p^{m}}\sum_{a\in\mathbb{B}}\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)$
$\displaystyle=\frac{(p^{mt}-1)(p^{m}-1)}{p^{m}}-\frac{1}{p^{m}}\sum_{a\in\mathbb{B}\setminus\\{0\\}}\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)$

From the above equation, we have

$\sum_{a\in\mathbb{B}\setminus\\{0\\}}\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)=(p^{mt}-1)(p^{m}-1)-p^{m}w(\mathbfsl{c})$
(23)

We distinguish between two cases

Case 1 $\frac{af(x)}{x}=(h(x))^{p}-h(x)+b$ for some
$a\in\mathbb{B}\setminus\\{0\\}$, $h(x)\in\mathbb{F}[x]$ and $b\in\mathbb{F}$.
In this case, the number of such $a$ is at most $p-1$ and let $\mathfrak{B}$
be the collection of such $a$. In fact, if for $a_{1}$ from $\mathfrak{B}$ it
holds that $\frac{a_{1}f(x)}{x}=(h(x))^{p}-h(x)+b$, then for $a_{2}$ from the
same set it holds that
$\frac{a_{2}f(x)}{x}=a_{2}a_{1}^{-1}((h(x))^{p}-h(x)+b)$. Hence,
$\chi_{a_{2}}\left(\frac{f(x)}{x}\right)$ is a constant number for each
$x\in\mathcal{A}$ when $a_{2}a_{1}^{-1}$ belongs to the finite field with $p$
elements. Utilizing the estimate (17), we have

$\displaystyle\left|\sum_{a\in\mathbb{B}\setminus\\{0\\}}\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)\right|$
$\displaystyle\leq\sum_{a\in\mathbb{B}\setminus\\{0\\}}\left|\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)\right|$
$\displaystyle\leq(p-1)\\#\mathcal{A}+\sum_{a\in\mathbb{B}\setminus(\\{0\\}\cup\mathfrak{B})}\left|\sum_{\alpha\in\mathcal{A}}\chi_{a}\left(\frac{f(\alpha)}{\alpha}\right)\right|$
$\displaystyle\leq(p-1)(p^{mt}-1)+(p^{m}-p)(k-1)\sqrt{p^{mt}}.$

By (23), we obtain that
$w(\mathbf{c})\geq\frac{(p^{m}-p)\left((p^{mt}-1)-(k-1)\sqrt{p^{mt}}\right)}{p^{m}}$.

Case 2 $f(x)\neq x(h(x))^{p}-xh(x)+xb$ for any
$a\in\mathbb{B}\setminus\\{0\\}$, $h(x)\in\mathbb{F}[x]$ and $b\in\mathbb{F}$.
Using a method analogous to Case 1, we deduce that

$\displaystyle
w(\mathbfsl{c})\geq\frac{(p^{m}-1)\left((p^{mt}-1)-(k-1)\sqrt{p^{mt}}\right)}{p^{m}}$
(24)

Taking the minimum over two cases, we get the proposition statement. ∎

Combining Proposition 8 and Proposition 9 together, we get Theorem 3(iii).

##  IV Modified Guruswami-Sudan Algorithm

In this section, we study efficient bounded-distance decoders for
$\mathcal{T}(\mathcal{A},k)$. Formally, we fix integer $e$, a codeword
$\mathbfsl{c}\in\mathcal{T}(\mathcal{A},k)$ and output
$\mathbfsl{y}\in\mathbb{F}_{p}^{|\mathcal{A}|}$ such that $\mathbfsl{c}$ and
$\mathbfsl{y}$ differ in at most $e$ positions. The input to the bounded-
distance decoder is $\mathbfsl{y}$ and our task is to find $\mathbfsl{c}$ in
polynomial time. Note that for the bounded-distance decoder to succeed, it is
necessary that $2e+1$ is at most the minimum distance for
$\mathcal{T}(\mathcal{A},k)$.

Recall the values of $d_{1}$ and $d_{2}$ in Theorem 3(i) and (ii). In both
proofs (that is, Propositions 4 and 6), we demonstrated that
$\mathcal{T}(\mathcal{A},k)$ (or its equivalent code) is a subcode of some GRS
code. Hence, we can apply any bounded-distance decoder for Reed-Solomon codes,
like the Berlekamp-Welch algorithm, and correct any $e$ errors, where $e$ is
at most $(\max\\{d_{1},d_{2}\\}-1)/2$.

Therefore, it remains to find an efficient bounded-distance decoder that
corrects $(d^{\prime}-1)/2$ errors, where $d^{\prime}$ is a lower bound on the
minimum distance of $\mathcal{T}(\mathcal{A},k)$. One such lower bound is the
value $d_{3}$ given in Theorem 3(iii). To this end, we modify the famous
Guruswami-Sudan algorithm for list decoding to perform this task.
Unfortunately, we are unable to guarantee that we can correct up to
$(d_{3}-1)/2$ errors. Nevertheless, we find some numerical examples where we
are close to these values (see Table I and II).

First, we recall the following restatement of Guruswami-Sudan algorithm due to
Koetter and Vardy [28, Theorem 2].

######  Theorem 10 (Guruswami-Sudan [29]).

Fix $\Delta\leq n$ and $\mu$. Set $\delta$ to be the smallest integer such
that
$N_{1,\Delta}\triangleq{\left\lceil\frac{\delta+1}{\Delta}\right\rceil}\left(\delta-\frac{\Delta}{2}{\left\lfloor\frac{\delta}{\Delta}\right\rfloor}+1\right)>\frac{n\mu(\mu+1)}{2}$.
Next, set $e=n-{\left\lfloor\delta/\mu\right\rfloor}$. Given
$\mathbfsl{y}\in\mathbb{F}^{n}$, we can find all polynomials $F(X)$ of degree
at most $\Delta$ such that $F(\alpha_{i})\neq y_{i}$ in at most $e$ positions.
Let $\mathcal{F}$ be the set of these polynomials. Furthermore, we can find
all $F(X)$’s in polynomial time (in $n$, $\mu$ and $|\mathcal{F}|$).

Next, we described a simple procedure that allows us to correct errors for
$\mathcal{T}(\mathcal{A},k)$.

Modified Guruswami-Sudan Decoder.

Input: Integer $e$ as defined in Theorem 10 (note that $e$ is defined by some
integer $\mu$) and $\mathbfsl{y}\in\mathbb{F}_{p}^{n}$.
Output: $\mathcal{L}\subseteq\mathcal{T}(\mathcal{A},k)$ such that
$\mathbfsl{c}$ and $\mathbfsl{y}$ differs in at most $e$ positions.

  1. (Step 1)

We apply Guruswami-Sudan algorithm with field $\mathbb{F}_{q}$ and $\Delta$ as
defined in (7). Hence, after this step, we have a set of polynomials
$\mathcal{F}$.

  2. (Step 2)

For each $F(X)\in\mathcal{F}$, we determine whether the word
$\mathbfsl{c}\triangleq(F(\alpha_{i})/\alpha_{i}^{p^{t-1}})_{i\in[n]}$ belongs
to $\mathcal{T}(\mathcal{A},k)$. We add $\mathbfsl{c}$ to $\mathcal{L}$ if and
only if it belongs to $\mathcal{T}(\mathcal{A},k)$.

######  Proposition 11.

Let $e$ be as defined earlier. Suppose $\mathcal{T}(\mathcal{A},k)$ has
minimum distance at least $d^{\prime}$. If $e\leq(d^{\prime}-1)/2$, the set
$\mathcal{L}$ returned by the modified Guruswami-Sudan decoder has size at
most one. Furthermore, the set $\mathcal{L}$ has size at most one.

###### Proof.

The fact that $|\mathcal{L}|$ is at most one follows directly from usual
coding arguments. Suppose otherwise that $\mathcal{L}$ comprises two words
$\mathbfsl{c}_{1}$ and $\mathbfsl{c}_{2}$ that differ from $\mathbfsl{y}$ in
at most $e$ positions. Then the Hamming distance of $\mathbfsl{c}_{1}$ and
$\mathbfsl{c}_{2}$ is at most $2e$, contradicting the distance property of
$\mathcal{T}(\mathcal{A},k)$.

Thus, it remains to show that Step 2 can be performed efficiently. Since
$\mathcal{T}(\mathcal{A},k)$ is a $\mathbb{F}_{p}$-linear code and so, there
exists check matrix $\mathbfsl{H}$ over $\mathbb{F}_{p}$. Therefore,
determining whether $\mathbfsl{c}$ belongs to $\mathcal{T}(\mathcal{A},k)$ is
equivalent to checking at $\mathbfsl{c}\mathbfsl{H}^{T}=\mathbf{0}$. This
completes the proof. ∎

##  V Numerical results

In this section, we provide a comparison of the number of correctable errors
corresponding to the different lower bounds on minimum distance given in
Theorem 3. In Tables I and II, we set $(p,m,t)=(5,1,2)$ and $(p,m,t)=(2,4,3)$,
respectively, and vary the parameter $k$. In addition, we also determine the
number of correctable errors that the modified Guruswami-Sudan algorithm
according to Proposition 11. We see that for moderate values of $k$, the
modified Guruswami-Sudan algorithm is able to correct up beyond the bounds
promised by the degree and lifted decoding bounds. Unfortunately, in most
cases, we fall short of the character sum bound and it is interesting if we
are able to efficiently decode close to the latter bound. For completeness, in
Table I, we compute the exact the minimum distance of repair-trace code.

$k$ |  Exact |  Degree |  Lifted |  Character | Modified
---|---|---|---|---|---
|  |  decoding |  sum | Guruswami-Sudan
|  bound |  bound |  bound |  $e$ |  $\mu$
$1$ |  $9$ |  $9$ |  $1$ |  $9$ |  $9$ |  $1$
$2$ |  $9$ |  $9$ |  $1$ |  $7$ |  $9$ |  $1$
$3$ |  $6$ |  $6$ |  $1$ |  $5$ |  $6$ |  $1$
$4$ |  $5$ |  $4$ |  $1$ |  $3$ |  $4$ |  $1$
$5$ |  $4$ |  $1$ |  $1$ |  $1$ |  $1$ |  $1$
$6$ |  $4$ |  $-$ |  $1$ |  $-$ |  $-$ |  $-$
$7$ |  $4$ |  $-$ |  $1$ |  $-$ |  $-$ |  $-$
$8$ |  $4$ |  $-$ |  $1$ |  $-$ |  $-$ |  $-$
$9$ |  $1$ |  $-$ |  $1$ |  $-$ |  $-$ |  $-$
TABLE I: Exact and lower bounds for the number of correctable errors of the repair-trace code $\mathcal{T}(\mathcal{A},k)$. Here, $\mathbb{B}=\textrm{GF}(5)$ and $\mathbb{F}=\textrm{GF}(25)$, and lower bounds are obtained from Theorem 3. $k$ |  Degree |  Lifted |  Character | Modified
---|---|---|---|---
|  decoding |  sum | Guruswami-Sudan
bound |  bound |  bound |  $e$ |  $\mu$
$1$ |  $1919$ |  $7$ |  $1791$ |  $1919$ |  $1$
$2$ |  $1919$ |  $7$ |  $1763$ |  $1919$ |  $1$
$3$ |  $1791$ |  $7$ |  $1735$ |  $1791$ |  $1$
$4$ |  $1663$ |  $7$ |  $1707$ |  $1707$ |  $1$
$5$ |  $1535$ |  $7$ |  $1679$ |  $1679$ |  $1$
$6$ |  $1407$ |  $7$ |  $1651$ |  $1651$ |  $3$
$7$ |  $1279$ |  $7$ |  $1623$ |  $1587$ |  $473$
$8$ |  $1151$ |  $7$ |  $1595$ |  $1386$ |  $424$
$9$ |  $1023$ |  $7$ |  $1567$ |  $1199$ |  $406$
$10$ |  $895$ |  $7$ |  $1539$ |  $1023$ |  $279$
$11$ |  $767$ |  $7$ |  $1511$ |  $857$ |  $277$
$12$ |  $639$ |  $7$ |  $1483$ |  $699$ |  $243$
$13$ |  $511$ |  $7$ |  $1455$ |  $548$ |  $198$
$14$ |  $383$ |  $7$ |  $1427$ |  $404$ |  $496$
$15$ |  $255$ |  $7$ |  $1399$ |  $264$ |  $120$
$16$ |  $127$ |  $7$ |  $1371$ |  $130$ |  $106$
$17$ |  $-$ |  $7$ |  $1343$ |  $-$ |  $-$
TABLE II: Exact and lower bounds for the number of correctable errors of the
repair-trace code $\mathcal{T}(\mathcal{A},k)$. Here,
$\mathbb{B}=\textrm{GF}(16)$ and $\mathbb{F}=\textrm{GF}(16^{3})$, and lower
bounds are obtained from Theorem 3.

Finally, to further justify our approach, we compare the repair bandwidth of
our approach with the repair bandwidth of the classical approach.
Specifically, we consider an ${\rm RS}(\mathcal{A},k)$ with distance $n-k+1$
that corrects $e$ errors and $s$ erasures whenever $2e+s\leq n-k$. Therefore,
in the classical approach, in the presence of $e$ erroneous helper nodes, we
need to download at least $n-(n-k-2e)=k+2e$ symbols to repair any failed
nodes. In other words, the bandwidth is
$(k+2e)\left\lceil\log_{2}p^{mt}\right\rceil$ bits.

On the other hand, suppose that $\mathcal{T}(\mathcal{A},k)$ has minimum
distance $d_{*}$. Again, we have that $\mathcal{T}(\mathcal{A},k)$ corrects
$e$ errors and $s$ erasures whenever $2e+s\leq d_{*}-1$. Then repeating the
same computation as before, we obtain the bandwidth
$(n-d_{*}+2e)\left\lceil\log_{2}p^{m}\right\rceil$ bits. In Fig. 1, we
consider the case $p=5$, $m=1$, $t=2$ and $n=25$. We then vary the number of
number of erroneous helper nodes and determine the corresponding bandwidth
(according to our estimates of the minimum distance). We see that when the
number of erroneous helper nodes is moderate, our approach has savings for
repair bandwidth.

Figure 1: Repair bandwidth of the various schemes. Here, we consider ${\rm
RS}(\mathbb{F},2)$ with $\mathbb{F}=\textrm{GF}(25)$,
$\mathbb{B}=\textrm{GF}(5)$.

##  VI Conclusion

We investigate the Reed-Solomon repair problem in the presence of erroneous
information from helper nodes under Guruswami-Wootters scheme. We consider the
collection of downloaded traces as code and investigate its code-distance
properties. Three lower bounds on its minimum distance and modification of the
famous Guruswami-Sudan algorithm to efficiently correct errors close to these
bounds are proposed. However, this is just the tip of the iceberg, and we
point out several open questions: is it possible to generalize this approach
to repair schemes based on subspace polynomials [8, 10, 13]? Do all of our
results hold for non-full-length Reed-Solomon codes? How do these results
compare to the parameters of existing polynomial trace codes?

## Acknowledgements.

This research/project is supported by the National Research Foundation,
Singapore under its Strategic Capability Research Centres Funding Initiative,
Singapore Ministry of Education Academic Research Fund Tier 2 Grants
MOE2019-T2-2-083 and MOE-T2EP20121-0007, and Nanyang Technological University
Research Grant No. 04INS000047C230GRT01. Any opinions, findings and
conclusions or recommendations expressed in this material are those of the
author(s) and do not reflect the views of National Research Foundation,
Singapore.

## References

  * [1] Alexandros G. Dimakis et al.  “Network Coding for Distributed Storage Systems”  In _IEEE Transactions on Information Theory_ 56.9, 2010, pp. 4539–4551
  * [2] I.. Reed and G. Solomon  “Polynomial Codes Over Certain Finite Fields”  In _Journal of the Society for Industrial and Applied Mathematics_ 8.2, 1960, pp. 300–304
  * [3] Thi Xinh Dinh et al.  “Practical Considerations in Repairing Reed-Solomon Codes”  In _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 2607–2612
  * [4] S.. Balaji et al.  “Erasure coding for distributed storage: an overview”  In _Science China Information Sciences_ 61.10, 2018, pp. 100301
  * [5] Shiqiu Liu and Frédérique Oggier  “An Overview of Coding for Distributed Storage Systems”  In _Network Coding and Subspace Designs_ Cham: Springer International Publishing, 2018, pp. 363–383
  * [6] Venkatesan Guruswami and Mary Wootters  “Repairing Reed-Solomon Codes”  In _IEEE Transactions on Information Theory_ 63.9, 2017, pp. 5684–5698
  * [7] Iwan Duursma and Hoang Dau  “Low bandwidth repair of the RS(10,4) Reed-Solomon code”  In _2017 Information Theory and Applications Workshop (ITA)_ , 2017, pp. 1–10
  * [8] Hoang Dau and Olgica Milenkovic  “Optimal repair schemes for some families of full-length Reed-Solomon codes”  In _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 346–350
  * [9] Hoang Dau, Iwan M. Duursma, Han Mao Kiah and Olgica Milenkovic  “Repairing Reed-Solomon Codes With Multiple Erasures”  In _IEEE Transactions on Information Theory_ 64.10, 2018, pp. 6567–6582
  * [10] Son Hoang Dau et al.  “Repairing Reed-Solomon Codes via Subspace Polynomials”  In _IEEE Transactions on Information Theory_ 67.10, 2021, pp. 6395–6407
  * [11] Noah Shutty and Mary Wootters  “Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data”  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ 215, Leibniz International Proceedings in Informatics (LIPIcs), 2022, pp. 117:1–117:19
  * [12] Roni Con and Itzhak Tamo  “Nonlinear Repair of Reed-Solomon Codes”  In _IEEE Transactions on Information Theory_ 68.8, 2022, pp. 5165–5177
  * [13] Amit Berman et al.  “Repairing Reed–Solomon Codes Evaluated on Subspaces”  In _IEEE Transactions on Information Theory_ 68.10, 2022, pp. 6505–6515
  * [14] Han Mao Kiah et al.  “Explicit Low-Bandwidth Evaluation Schemes for Weighted Sums of Reed-Solomon-Coded Symbols”  In _2023 IEEE International Symposium on Information Theory (ISIT)_ , 2023
  * [15] Zitan Chen, Min Ye and Alexander Barg  “Repair of RS codes with optimal access and error correction”  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 589–594
  * [16] Adi Shamir  “How to Share a Secret”  In _Commun. ACM_ 22.11 New York, NY, USA: Association for Computing Machinery, 1979, pp. 612–613
  * [17] Ron M. Roth  “Introduction to coding theory”  Cambridge University Press, 2006
  * [18] Chengju Li, Qin Yue and Fengwei Li  “Hamming Weights of the Duals of Cyclic Codes With Two Zeros”  In _IEEE Transactions on Information Theory_ 60.7, 2014, pp. 3895–3902
  * [19] Kelan Ding and Cunsheng Ding  “A Class of Two-Weight and Three-Weight Codes and Their Applications in Secret Sharing”  In _IEEE Transactions on Information Theory_ 61.11, 2015, pp. 5835–5842
  * [20] Chunming Tang et al.  “Linear Codes With Two or Three Weights From Weakly Regular Bent Functions”  In _IEEE Transactions on Information Theory_ 62.3, 2016, pp. 1166–1176
  * [21] Gaojun Luo and Xiwang Cao  “Constructions of Optimal Binary Locally Recoverable Codes via a General Construction of Linear Codes”  In _IEEE Transactions on Communications_ 69.8, 2021, pp. 4987–4997
  * [22] Gaojun Luo and San Ling  “Application of Optimal P-Ary Linear Codes to Alphabet-Optimal Locally Repairable Codes”  In _Des. Codes Cryptography_ 90.5 USA: Kluwer Academic Publishers, 2022, pp. 1271–1287
  * [23] Rudolf Lidl and Harald Niederreiter  “Finite Fields”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 1996
  * [24] “Character Sums and Polynomials”  Berlin, Boston: De Gruyter, 2013
  * [25] Francis N. Castro and Carlos J. Moreno  “Mixed Exponential Sums Over Finite Fields”  In _Proceedings of the American Mathematical Society_ 128.9 American Mathematical Society, 2000, pp. 2529–2537
  * [26] Todd Cochrane and Christopher Pinner  “Using Stepanov’s method for exponential sums involving rational functions”  In _Journal of Number Theory_ 116.2, 2006, pp. 270–292
  * [27] Andrew R. Booker, Stephen D. Cohen, Nicol Leong and Tim Trudgian  “Primitive elements with prescribed traces”  In _Finite Fields and Their Applications_ 84, 2022, pp. 102094
  * [28] R. Koetter and A. Vardy  “Algebraic soft-decision decoding of Reed-Solomon codes”  In _IEEE Transactions on Information Theory_ 49.11, 2003, pp. 2809–2825
  * [29] V. Guruswami and M. Sudan  “Improved decoding of Reed-Solomon and algebraic-geometric codes”  In _Proceedings 39th Annual Symposium on Foundations of Computer Science_ , 1998, pp. 28–37


# KnowledgeMath: Knowledge-Intensive Math Word Problem Solving
in Finance Domains

Yilun Zhao 1 Hongjun Liu${}^{*~{}2,3}$ Yitao Long3
Rui Zhang4 Chen Zhao3 Arman Cohan1,5
1Yale University 2Zhejiang University 3NYU Shanghai
4Penn State University 5Allen Institute for AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>Equal Contribution

###### Abstract

We introduce KnowledgeMath, a novel benchmark designed to evaluate LLMs’
capabilities in applying financial knowledge to solve complex math word
problems. Compared to prior works, this study features three core
advancements. First, KnowledgeMath includes 1,259 problems with a hybrid of
textual and tabular content and require college-level knowledge in the finance
domain for effective resolution. Second, we provide expert-annotated, detailed
solution references in Python program format, ensuring a high-quality
benchmark for LLM assessment. Finally, we evaluate a wide spectrum of 14 LLMs
with different prompting strategies like Chain-of-Thoughts and Program-of-
Thoughts. The current best-performing system (i.e., GPT-4 with Program-of-
Thoughts) achieves only 45.4% accuracy, leaving substantial room for
improvement. While knowledge-augmented LLMs can improve the performance (e.g.,
from 23.9% to 32.0% for GPT-3.5) , it is still significantly lower the
estimated human expert performance of 94%. We believe that KnowledgeMath can
facilitate future research on domain-specific knowledge retrieval and
augmentation into the math word problem-solving process. We will release the
benchmark and code at https://github.com/yale-nlp/KnowledgeMath.

KnowledgeMath: Knowledge-Intensive Math Word Problem Solving
in Finance Domains

Yilun Zhao††thanks:  Equal Contribution 1 Hongjun Liu${}^{*~{}2,3}$ Yitao
Long3 Rui Zhang4 Chen Zhao3 Arman Cohan1,5 1Yale University 2Zhejiang
University 3NYU Shanghai 4Penn State University 5Allen Institute for AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>

Figure 1: An example of KnowledgeMath. To answer the given question, LLMs are
required to comprehend specialized financial terms, such as “passive equity
ownership interest” and “proportionate consolidation method”. Additionally,
they must interpret tabular data within the question and accurately identify
question-relevant data points in the table.

Dataset | Domain | Level | Source | # Problems | Table | Knowledge- | Solution Format
---|---|---|---|---|---|---|---
Reasoning? | Intensive?
MAWPS Koncel-Kedziorski et al. (2016) | Math | Elem. School | Generated | 3,320 | ✗ | ✗ | Text
ASDiv Miao et al. (2020) | Math | Elem. School | Internet | 2,305 | ✗ | ✗ | Math Equation
SVAMP Patel et al. (2021) | Math | Elem. School | ASDiv | 1,000 | ✗ | ✗ | Math Equation
Math23K Wang et al. (2017) | Math | Elem. School | Internet | 23,162 | ✗ | ✗ | Math Equation
GSM8K Cobbe et al. (2021) | Math | Middle School | Annotated | 8,500 | ✗ | ✗ | Text
MATH Hendrycks et al. (2021) | Math | High School | Competition | 12,500 | ✗ | ✗ | Text
AQuA Ling et al. (2017) | Math | College | GMAT, GRE | 100,000 | ✗ | ✗ | Text
MathQA Amini et al. (2019) | Math | College | AQuA | 100,000 | ✗ | ✗ | Math Equation
MathQA-Python Austin et al. (2021) | Math | College | AQuA | 23,914 | ✗ | ✗ | Python Program
TabMWP Lu et al. (2023) | Math | Middle School | Textbooks | 38,431 | ✓ | ✗ | Text
FinQA Chen et al. (2021) | Finance | College | CrowdSource | 8,281 | ✓ | ✗ | Math Program
TAT-QA Zhu et al. (2021a) | Finance | College | CrowdSource | 16, 552 | ✓ | ✗ | Text
MultiHierttZhao et al. (2022) | Finance | College | CrowdSource | 10,440 | ✓ | ✗ | Math Equation
TheoremQAChen et al. (2023b) | STEM | College | Internet+Expert | 800 | ✗ | ✓ | Text
KnowledgeMath (ours) | Finance | College | Internet+Expert | 1,259 | ✓ | ✓ | Python Program

Table 1: Comparison between KnowledgeMath and existing MWP datasets.
KnowledgeMath is distinguished by three unique characteristics: (1)
_Knowledge-Intensive_ : Problems necessitate domain-specific knowledge,
complemented by a financial knowledge bank for research facilitation; (2)
_Table Reasoning_ : 39.0% of problems incorporate table information, requiring
models to understand table structure as well as interpret and reason over
tabular data; (3) _Expert Annotation_ : Each problem is accompanied by a
detailed, expert-annotated Python-formatted solution. Such solution annotation
combines the explicitness of code execution with the descriptive power of
annotated comments, offering a more effective and adaptable solution
representation for complex MWPs in KnowledgeMath.

##  1 Introduction

Large language models (LLMs) have been increasingly recognized for their
potential for complex problem-solving in real-world scenarios OpenAI (2023);
Touvron et al. (2023). Solving math word problems (MWPs) has emerged as a key
method for assessing LLMs’ capabilities Amini et al. (2019); Cobbe et al.
(2021); Hendrycks et al. (2021); Cobbe et al. (2021); Lu et al. (2023); Chen
et al. (2023b), as it demands both understanding contextual information and
reasoning over complex logics.

Recent advancements in LLMs have led to remarkable progress in solving
fundamental math problems Wei et al. (2022); Chen et al. (2023a); Wang et al.
(2023); Luo et al. (2023a); Azerbayev et al. (2023). However, as illustrated
in Table KnowledgeMath: Knowledge-Intensive Math Word Problem Solving  in
Finance Domains, existing MWP benchmarks typically do not require specialized
domain knowledge. This becomes a notable shortcoming when considering
practical applications of LLMs. Measuring progress in specialized areas such
as finance and healthcare typically involves addressing _domain-specific_ and
_knowledge-intensive_ problems, which goes beyond the scope of general
mathematical reasoning.

Recognizing this gap in existing benchmarks, we focus on the finance domain.
We chose this domain because, as illustrated in Figure 1, it often involves
scenarios requiring not only basic mathematical skills but also a deep
understanding of financial concepts Yang et al. (2023); Xie et al. (2023a); Wu
et al. (2023). Additionally, the finance domain frequently employs tables to
represent data Zhu et al. (2021b); Chen et al. (2021); Zhao et al. (2022); Li
et al. (2022), which adds another layer of complexity to the knowledge-
intensive problem-solving.

We introduce KnowledgeMath, the first benchmark tailored for evaluating LLMs
in the context of _knowledge-intensive_ MWP solving in the finance domain. The
dataset contains 1,259 problems that cover a broad range of finance subareas
(e.g., investment analysis, risk assessment, and financial forecasting), with
39.0% of the problems necessitating data interpretation over tabular data.
Each problem is accompanied by detailed, expert-annotated solutions and
explanations, providing a comprehensive reference for evaluating the LLMs’
performance. Additionally, we collect and release a comprehensive knowledge
bank, which includes detailed definitions and explanations for 1,760 financial
terms and concepts, facilitating future research on improving knowledge-
intensive problem-solving through knowledge retrieval.

We evaluate a wide spectrum of open-source and proprietary LLMs, specifically,
14 models from 13 organizations. Notably, this includes code-based LLMs Xu et
al. (2023); Luo et al. (2023b); Tunstall et al. (2023) for enhanced reasoning
and programming abilities and LLMs specialized for the finance domain Xie et
al. (2023b). Two prompting methods, Chain-of-Thoughts (CoT) Wei et al. (2022)
and Program-of-Thoughts (PoT) Chen et al. (2023a), are adopted for
experiments. Our experimental results indicate that all evaluated _open-
source_ LLMs scored below 20% in accuracy using various prompting methods,
including CoT and PoT prompting. Proprietary models perform better, with GPT-4
significantly outperforms other LLMs, achieving an accuracy of 45.4% when
applying PoT prompting. However, it still lags far behind human expert
performance in the open-book setting, which stands at 94%. This significant
gap between LLMs and human experts demonstrates the challenges of
KnowledgeMath, highlighting the need for further advancements in LLMs for
knowledge-intensive problem-solving capabilities.

Next, we investigate how to integrate domain-specific knowledge to enhance the
problem-solving capabilities of LLMs under three knowledge-augmented settings:
oracle, external knowledge retrieval, and LLM as the knowledge base. We reveal
that including question-relevant knowledge into the prompt can improve LLMs’
performance, providing insights for future work to develop more advanced
knowledge-augmented strategies to realize higher performance gains.

Our contributions are summarized below:

  * •

We propose KnowledgeMath, the first knowledge-intensive MWP benchmark in the
finance domain, aimed at evaluating LLMs’ capabilities to integrate domain
knowledge for complex problem-solving.

  * •

We conduct comprehensive evaluations using a diverse array of LLMs, uncovering
a substantial performance gap between the best-performing LLM (i.e., GPT-4)
and human experts.

  * •

Our detailed analysis on augmenting LLMs with knowledge integration further
demonstrates the effectiveness of retrieving and including question-relevant
domain knowledge in the LLM input context.

##  2 KnowledgeMath

In this section, we describe the dataset construction process for
KnowledgeMath. We begin by constructing a knowledge bank that includes well-
formulated definitions of 1,760 financial terms. We then instruct expert111We
hire 8 graduate students (5 females and 3 males) majoring in finance-relevant
disciplines who have passed our quality exams in Python and finance. Before
starting the official annotation process, each annotator is given a two-hour
training session to understand the annotation requirements and learns how to
use the annotation interface. annotators to create knowledge-intensive
questions based on the constructed knowledge bank, followed by annotating
detailed Python solutions.

###  2.1 Knowledge Bank Construction

We construct a knowledge bank that covers a wide range of topics in the
finance domain. It simplifies the creation of knowledge-intensive questions by
annotators and enables the exploration of various perspectives within domain
knowledge. The knowledge bank includes finance-domain-specific terms (e.g.,
“price index” and “net present value”), along with their corresponding
definitions and, where applicable, relevant formulas. It is worth noting that
this knowledge bank is versatile and can be applied to a variety of finance-
relevant tasks.

Figure 2: An example of knowledge terms in the constructed knowledge bank.

#### Knowledge Collection and Deduplication

To construct a knowledge bank, we first collect knowledge relevant to the
finance domain from Wikipedia using “finance” and “economics” as key search
terms. After collecting the raw financial data, we adopt comprehensive
heuristics methods (e.g., embedding-based similarity) to remove duplicates.
This procedure ensures the uniqueness of each knowledge term in our bank.

#### Automatic Knowledge Formulation

To enhance the adaptability and usability of the knowledge bank, we
incorporate a two-step automatic knowledge formulation process, making each
piece of collected knowledge standardized and distilled into a clear, concise
format. The primary motivation for using _automatic_ knowledge formulation is
cost efficiency and effectiveness. We have observed that GPT-* models are
adept at handling this straightforward task with minimal bias, as this process
does not involve the addition of extraneous knowledge. We first prompt GPT-3.5
to reformulate the gathered information for each financial term into a
concise, paragraph-long textual definition. Since some financial terms come
with mathematical definitions, we address the issue of varied formula formats
in the original sources (e.g., LaTeX and HTML). We instruct GPT-4 to transform
these formulas into a unified python program format. Figure 2 illustrates an
example collected in the knowledge bank.

#### Knowledge Bank Update and Maintenance

After formulating knowledge using LLMs, During the dataset annotation stage
(Section 2.2), we dynamically update and maintain the constructed knowledge
bank, incorporating new knowledge that, although not initially covered, is
essential for answering the annotated questions. Additionally, we remove any
duplicate entries identified by the annotators. We eventually collect 1,760
pieces of financial knowledge in the knowledge bank, with 52% of the terms
including Python-formatted mathematical definitions.

###  2.2 KnowledgeMath Question Annotation

For each financial term in the knowledge bank, we instruct annotators to
create a corresponding math word question, if applicable. The answer to the
composed question should be a numeric value. The annotators are required to
adhere to the following guidelines for a successful question annotation:

#### Mitigating Data Contamination Issue

If the annotators choose to adapt questions from textbooks or the Internet
instead of devising their own, they are asked to not only modify the surface-
level description of the question but also change the associated numeric
values. This approach helps prevent the inclusion of questions that may
already be part of the pretraining dataset for LLMs. To further tackle the
issues of _data contamination_ , we direct the annotators to conduct a Google
search for each annotated question, ensuring that no similar question appears
on the first page of the search results.

#### Identifying Question-relevant Knowledge

After a question is annotated, annotators must identify 1-3 key financial
concepts for answering this question. They then search for each term in our
constructed knowledge bank. If the term is included, they verify its context
and details for relevance. If a term is absent or with low-quality definition,
annotators receive a bonus for documenting the term, providing a brief
explanation or definition and outlining its relevance to the problem. These
identified terms are subsequently added or updated in the knowledge bank,
resulting in a total of 346 new inclusions and 83 revisions.

#### Processing Tabular Data

We recognize that many financial problems involve knowledge and information
from tables. Therefore, we encourage annotators to include tables that are
relevant and accurately represent the data pertinent to their questions. We
use Excel for recording each table, as it enables annotators to modify the
content of tables with hierarchical structures (e.g., combined columns and
rows). Subsequently, we export these tables in HTML format.

Property | Value
---|---
Question Length (Median/Avg) | 49.0 / 55.7
% Questions with Table | 39.0
# Rows per Table (Median/Avg) | 3.0 / 3.2
# Columns per Table (Median/Avg) | 6.0 / 6.9
# Knowledge Terms per Example (Median/Avg) | 2.5 / 2.4
# Math Operations in Python Solution (Median/Avg) | 5.0 / 5.3
# Code Lines in Python Solution (Median/Avg) | 5.0 / 6.1
# Comment Lines in Python Solution (Median/Avg) | 3.0 / 3.5
Dataset Size | 1,259

Table 2: Basic statistics of KnowledgeMath dataset.

Figure 3: Topic distribution of KnowledgeMath.

###  2.3 KnowledgeMath Solution Annotation

As illustrated in KnowledgeMath: Knowledge-Intensive Math Word Problem Solving
in Finance Domains, existing math word problem (MWP) datasets typically
represent solutions using text or mathematical equations. However, solutions
in text format often lack the precision and unambiguous nature required for
computational problem-solving. Solutions in mathematical equations are
explicit, but less descriptive, as the semantic meaning associated with each
numeric value in the equations can be ambiguous. Moreover, these two formats
are less adaptable for use in automated systems due to variations in language
and difficulties in semantic parsing and execution.

To overcome these limitations, we use Python programs, starting with “def
solution():”, to represent solutions. Such Python program combines the
explicitness of code execution with the descriptive power of annotated
comments, offering a more effective and adaptable solution representation for
complex MWPs. Specifically, in the solution annotation stage, annotators are
required to first define variables at the beginning of the Python function.
These variables correspond to the key elements or quantities mentioned in the
word problem, and annotators assign meaningful names that clearly represent
each element. The annotators then proceed to write a sequence of Python
statements that logically solve the problem, step by step. Additionally,
annotators are awarded a bonus for writing detailed comments, making the code
more readable and understandable. To ensure the accuracy and functionality of
the Python-format solutions, our annotation interface automatically executes
the Python function. This execution checks that the return type of the answer
is either a float or an int and verifies that there are no execution errors.

###  2.4 Dataset Statistics

subsection 2.2 describes the basic statistics of KnowledgeMath. Finally, we
collected a total of 1,259 questions, with 39.0% of them requiring data
interpretation over tables. The topic-type distribution of KnowledgeMath is
shown in Figure 3.

###  2.5 Human-level Performance

To assess the human performance of non-experts and experts on KnowledgeMath,
we enroll two evaluators with different backgrounds.222The first evaluator is
a third-year undergraduate student majoring in computer science and has
limited experience in the finance domain. The second evaluator is a
professional with a master’s degree in business management and holds the
Chartered Financial Analyst (CFA) license. Each evaluator is tasked with
completing 50 questions randomly sampled from the KnowledgeMath dataset. To
encourage the evaluators to finish the questions carefully and thoroughly, we
award a bonus for each correctly answered question, thus incentivizing
detailed attention and comprehensive understanding in their responses.

#### Human Performance in Closed-book Setting

We first evaluate their performance in a _closed-book_ setting, where the
evaluators do not have access to the internet or textbooks and are required to
finish the 50 questions within three hours. The non-expert evaluator achieves
an accuracy of 54% (27 out of 50), and the expert evaluator achieves an
accuracy of 76% (38 out of 50).

#### Human Performance in Open-book Setting

We then transition to an _open-book_ setting, where the evaluators are asked
to use the internet and textbooks to correct their initial errors. This
setting is designed to assess how external knowledge resources could enhance
human problem-solving abilities and accuracy. The non-expert evaluator
corrects 16 of the error cases, resulting in an accuracy of 86%. Similarly,
the expert evaluator improves the accuracy from 76% to 94%.

##  3 Method

###  3.1 Prompting Approach

Figure 4: Examples of CoT and PoT Prompts we used.

We evaluate two established prompting strategies, with examples illustrated in
Figure 4.

#### Chain-of-Thought (CoT)

The CoT method Wei et al. (2022), instructs the LLMs to articulate a step-by-
step reasoning process. This leads to a detailed explanation that culminates
in the final answer.

#### Program-of-Thought (PoT)

Different from CoT, the PoT method Chen et al. (2023a) disentangles
computation from the reasoning process by prompting the LLMs to generate a
structured program to represent the reasoning process. The final answer is
then derived by executing the generated program with an external calculator.

###  3.2 Knowledge-Augmented Prompting approaches

We develop and evaluate three knowledge-augmented approaches. In both
settings, we include the definition of question-relevant knowledge terms
within the CoT prompts. An examples is illustrated in Figure 5 in Appendix.

#### Oracle

To investigate the headroom in knowledge augmentation, we use an oracle
setting, where the _ground-truth_ knowledge terms associated with the question
are included.

Model | Portfolio | Market | Management | Derivatives | Quantitative | Issuance | Accounting | ALL
---|---|---|---|---|---|---|---|---
Chain of Thoughts (CoT)
GPT-4 | 37.6 | 47.5 | 41.9 | 47.0 | 43.6 | 39.1 | 31.3 | 42.9
GPT-3.5 | 17.2 | 27.0 | 28.4 | 17.9 | 34.8 | 30.4 | 34.7 | 26.9
WizardMath (70B) | 11.8 | 16.8 | 13.5 | 10.8 | 17.2 | 8.7 | 18.3 | 14.5
WizardLM* (70B) | 12.9 | 13.9 | 14.9 | 10.3 | 21.1 | 10.9 | 13.0 | 13.9
Llama-2 (70B) | 3.2 | 16.1 | 8.1 | 11.8 | 15.6 | 10.9 | 16.8 | 13.2
Lemur (70B) | 8.6 | 13.1 | 8.1 | 9.0 | 15.2 | 13.0 | 13.0 | 11.6
Llama-2 (7B) | 3.2 | 10.2 | 8.1 | 6.2 | 7.0 | 4.3 | 6.9 | 6.8
WizardCoder-Python (34B) | 4.3 | 8.8 | 5.4 | 4.4 | 7.4 | 2.2 | 8.4 | 6.3
Mistral (7B) | 4.3 | 3.6 | 2.7 | 4.1 | 9.4 | 4.3 | 7.6 | 5.8
MPT* (30B) | 1.1 | 11.7 | 4.1 | 4.6 | 6.3 | 2.2 | 4.6 | 5.3
StarChat (16B) | 3.2 | 8.0 | 0.0 | 4.1 | 2.7 | 0.0 | 3.8 | 3.7
Vicuna* (33B) | 1.1 | 4.4 | 2.7 | 3.3 | 4.3 | 2.2 | 4.6 | 3.7
Qwen* (14B) | 1.1 | 4.4 | 5.4 | 4.4 | 1.2 | 2.2 | 3.1 | 3.2
PiXiu* (30B) | 2.2 | 0.7 | 0.0 | 1.3 | 1.6 | 0.0 | 1.9 | 1.4
Program of Thoughts (PoT)
GPT4 | 64.5 | 40.1 | 39.2 | 47.2 | 60.3 | 50.0 | 25.2 | 45.4
GPT-3.5 | 36.6 | 26.3 | 28.4 | 24.4 | 47.5 | 26.1 | 16.8 | 28.9
Lemur (70B) | 21.5 | 15.3 | 23.0 | 9.7 | 27.2 | 15.2 | 9.2 | 15.6
Llama-2 (70B) | 21.5 | 15.3 | 23.0 | 9.7 | 27.2 | 15.2 | 9.2 | 7.4
WizardCoder-Python (34B) | 7.5 | 4.4 | 9.5 | 1.3 | 8.9 | 4.3 | 2.7 | 4.5
Mistral (7B) | 2.2 | 1.5 | 4.1 | 1.5 | 8.2 | 8.7 | 5.0 | 4.1
WizardMath (70B) | 2.2 | 3.6 | 9.5 | 3.8 | 5.1 | 6.5 | 1.9 | 4.0
Llama-2 (7B) | 4.3 | 4.4 | 4.1 | 1.8 | 3.9 | 0.0 | 1.5 | 2.7
StarChat | 2.2 | 1.5 | 0.0 | 0.8 | 1.2 | 2.2 | 1.9 | 1.3

Table 3: Results for CoT and PoT prompting on KnowledgeMath. We report the
accuracy over different fine-grained question types. Models marked with ∗ are
found challenging to instruct for generating _executable Python solutions_
using PoT prompting; therefore, we only report their performance with CoT
prompting approach.

#### External Knowledge Retrieval

In this setting, we use the question as the retrieval query. We apply a
retriever, as described in Section 4.1, to retrieve the top-$n$ knowledge
terms with the highest similarities from our constructed knowledge bank.

#### LLM as Knowledge Base

Recent work Petroni et al. (2019); Kang et al. (2023) demonstrates that LLMs
themselves can effectively serve as knowledge bases. Therefore, in this
setting, we prompt LLMs to first identify the financial terms required to
answer the question. Subsequently, they generate definitions of each
identified knowledge term using their inherent data memorization capabilities.
These generated knowledge definitions are then used for knowledge augmented
prompting.

##  4 Experiments

###  4.1 Baselines

#### Evaluated LLMs

We evaluate following instruction-tuned general and code-based LLMs: (1)
General LLMs: GPT-3.5&4 Brown et al. (2020); OpenAI (2022, 2023), Llama-2
Touvron et al. (2023), Mistral Jiang et al. (2023), MPT Team (2023), WizardLM
Luo et al. (2023b), Qwen Bai et al. (2023), (2) Code-based LLMs: StarCoder Li
et al. (2023), StarChat Tunstall et al. (2023), CodeLlama Rozière et al.
(2023), WizardCoder Luo et al. (2023b), WizardMath Luo et al. (2023a), and
Lemur Xu et al. (2023). We used chat or instruct versions for each type of
LLMs, when available, otherwise, we used their base version. All the model
weights of evaluated LLMs can be found at HuggingFace Model
Hub333https://huggingface.co/models.

#### Retriever

We implement OpenAI Ada Embedding444platform.openai.com/docs/guides/embeddings
as the dense retriever, alongside BM25 Robertson et al. (1995) as the sparse
retriever. These retrievers are employed to extract the top-$n$ most related
pieces of knowledge. As detailed in Section 4.1, the retrieved knowledge is
then provided as the context to answer the question.

###  4.2 Implementation Details

#### LLM Experiment

The experiments for open-sourced LLMs were conducted using vLLM framework Kwon
et al. (2023). For all the experiments, we set temperature as 1.0, Top P as
1.0, and maximum output length as 512. For questions involving tabular data,
we converted the tables into Markdown format for model input.

#### Final Answer Extraction

For LLM with CoT prompting, we adopt the answer extraction pipeline from Chen
et al. (2023b) to identify the final answer from the model’s output. For LLM
with PoT prompting, we first develop a heuristic method to extract the
generated python solution from the model’s output. If this python solution is
executable, we execute it to obtain the final answer. Once we obtain the final
answer from model’s output, we compare it with the ground-truth answer for
accuracy measurement.

###  4.3 Results and Analysis

#### GPT-* significantly outperforms other open-source LLMs

Proprietary models demonstrate the best performance on KnowledgeMath. Notably,
as illustrated in Table 3, GPT-4 significantly outperforms other LLMs,
achieving an accuracy of 42.9% on KnowledgeMath with CoT. In contrast, open-
source LLMs significantly lag behind. Furthermore, our case study in Table 5
shows that while GPT-* models are capable of performing complex mathematical
calculations, other LLMs often fail to understand financial terms, leading to
incorrect mathematical expressions. This highlights a critical need for future
development efforts to close the performance gap.

#### Substantial Discrepancy in Performance Between Human Experts and LLMs

Even the best-performing LLM, GPT-4, performs much worse than human experts.
For instance, GPT-4’s accuracy on our dataset using the PoT method stands at
45.4%, falling well short of the 94% accuracy achieved by expert evaluators in
the open-book setting. This gap highlights the critical need for further
advancements in LLMs, especially in tackling complex problem-solving tasks
within specialized domains that are knowledge-intensive.

#### Effectiveness of Tuning LLMs in Specialized Field

Among open-source LLMs with CoT prompting, WizardMath achieves the best
performance as it is further instruction-tuned to learn mathematical
reasoning. Moreover, among open-source LLMs with PoT prompting methods, Lemur
achieves the best performance with PoT prompting methods, demonstrating the
effectiveness of tuning LLMs on code-based tasks for enhanced reasoning
capabilities. PiXiu, although a specialized LLM in the finance domain,
achieves low performance on KnowledgeMath. Our findings indicate the needs for
future research on exploring the development of LLMs in expert domains.

Model | Setting | Acc
---|---|---
Llama-2-70B | Baseline (_wo._ knowledge aug.) | 11.4
2-3 | LLM as Knowledge Base | 10.9 (- 0.5)
2-3 | Retrieval _w._ BM25 | 11.8 (+0.4)
| Retrieval _w._ Ada Embedding | 13.2 (+1.8)
2-3 | Oracle | 16.9 (+5.5)
GPT-3.5 | Baseline (_wo._ knowledge aug.) | 23.9
2-3 | LLM as Knowledge Base | 24.7 (+0.8)
2-3 | Retrieval _w._ BM25 | 23.8 (- 0.1)
| Retrieval _w._ Ada Embedding | 26.9 (+3.0)
2-3 | Oracle | 32.0 (+8.1)

Table 4: Results of CoT prompting approach under different knowledge
augmentation settings. There is a correlation between model improvement and
the quality of knowledge incorporated into the input context.

#### Analysis of Knowledge Retrieval and Augmentation

We conduct an analysis to understand the performance of LLMs and the quality
of knowledge incorporated into the input context, aiming to provide insights
for future work on knowledge augmentation in LLMs to solve knowledge-intensive
tasks. As illustrated in subsection 4.3, improving the question-relevance of
incorporated knowledge can consistently improve the LLMs’ performance.
Specifically, LLMs equipped with retrieved knowledge from Ada Embedding
outperform those using retrieved knowledge from BM25, owing to the more
advanced capabilities of the Ada Embedding-based retriever. Nevertheless, it
is worth noting that even when incorporated with the ground-truth knowledge
(i.e., the oracle setting), GPT-3.5 still performs much worse than human
experts. This demonstrates the need for future work on developing more
advanced domain-specific knowledge integration methods.

##  5 Related Work

In past studies, researchers have proposed a wide spectrum of challenging
datasets, aiming at exploring the potential and capability to solve
mathematical problems from different perspectives. As one of the most popular
datasets, GSM8K dataset Cobbe et al. (2021) proposes to test the model’s
multi-step mathematical reasoning performance. Considering the university-
level theorems included in datasets referred to in TheoremQA Chen et al.
(2023b), AQuA Ling et al. (2017), MathQA Amini et al. (2019) and MathQA-Python
Austin et al. (2021) focus on university-level Math problems; FinQA Chen et
al. (2021), TAT-QA Zhu et al. (2021a), and MultiHiertt Zhao et al. (2022) are
more concentrating on finance knowledge. More recently, Callanan et al. (2023)
investigates the LLMs’ performance on mock CFA exams. To further investigate
the LLMs’ capabilities in solving knowledge-intensive MWPs, we propose
KnowledgeMath.

##  6 Conclusion

This paper introduces KnowledgeMath, which focuses on assessing LLMs in
solving college-level MWPs requiring both mathematical and financial
knowledge. Our comprehensive evaluations of 17 LLMs, using both CoT and PoT
prompting methods, identify significant areas where LLMs need to enhance their
specialized knowledge for complex problem-solving in expert domains.
Additionally, our experiments with knowledge augmentation in LLMs indicate
that integrating domain-specific knowledge can improve LLMs’ problem-solving
abilities. We believe this research provides insights for future work in
advancing LLMs in complex problem-solving within expert domains.

## References

  * Amini et al. (2019) Aida Amini, Saadia Gabriel, Peter Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannaneh Hajishirzi. 2019.  Mathqa: Towards interpretable math word problem solving with operation-based formalisms.  _arXiv preprint arXiv:1905.13319_.
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_.
  * Azerbayev et al. (2023) Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen McAleer, Albert Q. Jiang, Jia Deng, Stella Biderman, and Sean Welleck. 2023.  Llemma: An open language model for mathematics.
  * 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_.
  * 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, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Callanan et al. (2023) Ethan Callanan, Amarachi Mbakwe, Antony Papadimitriou, Yulong Pei, Mathieu Sibue, Xiaodan Zhu, Zhiqiang Ma, Xiaomo Liu, and Sameena Shah. 2023.  Can gpt models be financial analysts? an evaluation of chatgpt and gpt-4 on mock cfa exams.
  * Chen et al. (2023a) Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2023a.  Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks.  _Transactions on Machine Learning Research_.
  * Chen et al. (2023b) Wenhu Chen, Ming Yin, Max Ku, Elaine Wan, Xueguang Ma, Jianyu Xu, Tony Xia, Xinyi Wang, and Pan Lu. 2023b.  Theoremqa: A theorem-driven question answering dataset.  _arXiv preprint arXiv:2305.12524_.
  * Chen et al. (2021) Zhiyu Chen, Wenhu Chen, Charese Smiley, Sameena Shah, Iana Borova, Dylan Langdon, Reema Moussa, Matt Beane, Ting-Hao Huang, Bryan Routledge, et al. 2021.  Finqa: A dataset of numerical reasoning over financial data.  _arXiv preprint arXiv:2109.00122_.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. 2021.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021.  Measuring mathematical problem solving with the math dataset.
  * 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. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Kang et al. (2023) Minki Kang, Seanie Lee, Jinheon Baek, Kenji Kawaguchi, and Sung Ju Hwang. 2023.  Knowledge-augmented reasoning distillation for small language models in knowledge-intensive tasks.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Koncel-Kedziorski et al. (2016) Rik Koncel-Kedziorski, Subhro Roy, Aida Amini, Nate Kushman, and Hannaneh Hajishirzi. 2016.  MAWPS: A math word problem repository.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1152–1157, San Diego, California. Association for Computational Linguistics.
  * Kwon et al. (2023) Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023.  Efficient memory management for large language model serving with pagedattention.  In _Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles_.
  * Li et al. (2022) Moxin Li, Fuli Feng, Hanwang Zhang, Xiangnan He, Fengbin Zhu, and Tat-Seng Chua. 2022.  Learning to imagine: Integrating counterfactual thinking in neural discrete reasoning.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 57–69, Dublin, Ireland. Association for Computational Linguistics.
  * Li et al. (2023) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj, Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Yee, Logesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. 2023.  Starcoder: may the source be with you!
  * Ling et al. (2017) Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017.  Program induction by rationale generation: Learning to solve and explain algebraic word problems.  _arXiv preprint arXiv:1705.04146_.
  * Lu et al. (2023) Pan Lu, Liang Qiu, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan. 2023.  Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning.  In _The Eleventh International Conference on Learning Representations_.
  * Luo et al. (2023a) Haipeng Luo, Qingfeng Sun, Can Xu, Pu Zhao, Jianguang Lou, Chongyang Tao, Xiubo Geng, Qingwei Lin, Shifeng Chen, and Dongmei Zhang. 2023a.  Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct.  _arXiv preprint arXiv:2308.09583_.
  * Luo et al. (2023b) Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. 2023b.  Wizardcoder: Empowering code large language models with evol-instruct.  _arXiv preprint arXiv:2306.08568_.
  * Miao et al. (2020) Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su. 2020.  A diverse corpus for evaluating and developing English math word problem solvers.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 975–984, Online. Association for Computational Linguistics.
  * OpenAI (2022) OpenAI. 2022.  Chatgpt: Optimizing language models for dialogue.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774.
  * Patel et al. (2021) Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021.  Are NLP models really able to solve simple math word problems? In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2080–2094, Online. Association for Computational Linguistics.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019.  Language models as knowledge bases? 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)_ , pages 2463–2473, Hong Kong, China. Association for Computational Linguistics.
  * Robertson et al. (1995) Stephen E Robertson, Steve Walker, Susan Jones, Micheline M Hancock-Beaulieu, Mike Gatford, et al. 1995.  Okapi at trec-3.  _Nist Special Publication Sp_ , 109:109.
  * Rozière et al. (2023) Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. 2023.  Code llama: Open foundation models for code.
  * Team (2023) MosaicML NLP Team. 2023.  Introducing mpt-7b: A new standard for open-source, commercially usable llms.  Accessed: 2023-03-28.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony S. Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.
  * Tunstall et al. (2023) Lewis Tunstall, Nathan Lambert, Nazneen Rajani, Edward Beeching, Teven Le Scao, Leandro von Werra, Sheon Han, Philipp Schmid, and Alexander Rush. 2023.  Creating a coding assistant with starcoder.  _Hugging Face Blog_.  Https://huggingface.co/blog/starchat.
  * Wang et al. (2023) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations_.
  * Wang et al. (2017) Yan Wang, Xiaojiang Liu, and Shuming Shi. 2017.  Deep neural solver for math word problems.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 845–854.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Wu et al. (2023) Shijie Wu, Ozan Irsoy, Steven Lu, Vadim Dabravolski, Mark Dredze, Sebastian Gehrmann, Prabhanjan Kambadur, David Rosenberg, and Gideon Mann. 2023.  Bloomberggpt: A large language model for finance.  _ArXiv_ , abs/2303.17564.
  * Xie et al. (2023a) Qianqian Xie, Weiguang Han, Xiao Zhang, Yanzhao Lai, Min Peng, Alejandro Lopez-Lira, and Jimin Huang. 2023a.  Pixiu: A large language model, instruction data and evaluation benchmark for finance.  _ArXiv_ , abs/2306.05443.
  * Xie et al. (2023b) Qianqian Xie, Weiguang Han, Xiao Zhang, Yanzhao Lai, Min Peng, Alejandro Lopez-Lira, and Jimin Huang. 2023b.  Pixiu: A large language model, instruction data and evaluation benchmark for finance.
  * Xu et al. (2023) Yiheng Xu, Hongjin Su, Chen Xing, Boyu Mi, Qian Liu, Weijia Shi, Binyuan Hui, Fan Zhou, Yitao Liu, Tianbao Xie, Zhoujun Cheng, Siheng Zhao, Lingpeng Kong, Bailin Wang, Caiming Xiong, and Tao Yu. 2023.  Lemur: Harmonizing natural language and code for language agents.
  * Yang et al. (2023) Hongyang Yang, Xiao-Yang Liu, and Christina Dan Wang. 2023.  Fingpt: Open-source financial large language models.  _arXiv preprint arXiv:2306.06031_.
  * Zhao et al. (2022) Yilun Zhao, Yunxiang Li, Chenying Li, and Rui Zhang. 2022.  MultiHiertt: Numerical reasoning over multi hierarchical tabular and textual data.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6588–6600, Dublin, Ireland. Association for Computational Linguistics.
  * Zhu et al. (2021a) Fengbin Zhu, Wenqiang Lei, Youcheng Huang, Chao Wang, Shuo Zhang, Jiancheng Lv, Fuli Feng, and Tat-Seng Chua. 2021a.  Tat-qa: A question answering benchmark on a hybrid of tabular and textual content in finance.  _arXiv preprint arXiv:2105.07624_.
  * Zhu et al. (2021b) Fengbin Zhu, Wenqiang Lei, Youcheng Huang, Chao Wang, Shuo Zhang, Jiancheng Lv, Fuli Feng, and Tat-Seng Chua. 2021b.  TAT-QA: A question answering benchmark on a hybrid of tabular and textual content in finance.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3277–3287, Online. Association for Computational Linguistics.

##  Appendix A Appendix

GPT-4 (Explicit and faithful reasoning)
---
Output: Firstly, under the proportionate consolidation method, we consider the
portion of assets, liabilities, revenue, and expenses we proportionately own
in relation to the company we invested in. In the case of PZ, they increased
their stake in T-Internet from 15% to 50% in 2019. Therefore, for 2019, the
proportionate consolidation of liabilities for company PZ would be its own
liabilities plus 50% of T-Internet’s liabilities. From the figures, we have
PZ’s total liabilities for 2019 as 900 and T-Internet’s total liabilities for
2019 as 650. Calculating 50% of T-Internet’s liabilities: 0.50 * 650 = 325
(right formula). To get the total liabilities under the proportionate
consolidation method, we add PZ’s own liabilities to its 50% share of
T-Internet’s liabilities.Doing this, we have: 900 (PZ’s liabilities) + 325
(50% of T-Internet’s liabilities) = 1225 (right formula). Therefore, the
answer is 1225 (right answer).
GPT-3.5 (Explicit and faithful reasoning)
Output: To determine the total liabilities for company PZ under the
proportionate consolidation method for 2019, we need to use the formula: Total
liabilities = PZ liabilities + (T-internet liabilities * ownership ratio) In
2018, PZ had a passive equity ownership interest of 15% in the T-internet
company. So, for 2018, the ownership ratio is 15%. In 2019, PZ increased its
ownership to 50% as of 1st January 2019. So, for 2019, the ownership ratio is
50%. From the given table, we can find the liabilities for PZ in 2018 and
2019: PZ liabilities in 2018 = 1200 PZ liabilities in 2019 = 900 We also have
the liabilities for the T-internet company in 2018 and 2019: T-internet
liabilities in 2018 = 600 T-internet liabilities in 2019 = 650 Using the
formula and the given values, we can calculate the total liabilities for
company PZ under the proportionate consolidation method for 2019: Total
liabilities = 900 + (650 * 50%) (right formula) Therefore, the answer is 1225
(right answer).
Llama-2-70B (Error-prone implicit reasoning)
Output: Therefore, the answer is 1,426,615 (wrong answer). Here’s how we get
to that answer: 1\. First, we need to calculate the total liabilities for
company PZ in 2019 under the proportionate consolidation method. We can do
this by using the formula: Total liabilities = PZ liabilities + (T-internet
liabilities * ownership ratio) We know that PZ liabilities in 2019 were
1,200,000 (from the table). We also know that T-internet liabilities in 2019
were 900,000 (from the table). The ownership ratio is 50%, which means that PZ
owns half of T-internet’s shares. So, we can plug these values into the
formula: Total liabilities = 1,200,000 + (900,000 * 0.5) Total liabilities =
1,200,000 + 450,000 Total liabilities = 1,650,000 (wrong formula) 2\. Next, we
need to add the dividends paid by T-internet in 2019, which were 230,000 (from
the table). We add this to the total liabilities we calculated above: Total
liabilities = 1,650,000 + 230,000 Total liabilities = 1,880,000 3\. Finally,
we need to convert the answer to the proportionate consolidation method, which
means we need to subtract the portion of T-internet’s liabilities that are not
owned by PZ. We can do this by multiplying T-internet’s liabilities by the
ownership ratio and subtracting the result from the total liabilities: Total
liabilities = 1,880,000 - (900,000 * 0.5) Total liabilities = 1,880,000 -
450,000 Total liabilities = 1,430,000 (wrong formula)
WizardMath (Error-prone implicit reasoning)
Output: Step 1: Determine the cost of acquiring the 35% stake in T-internet.
We need to calculate the cost of purchasing the additional 35% (50% - 15%)
equity stake in T-internet. We can do this by multiplying the total book value
of T-internet’s equity by the percentage of the stake acquired. Cost of
acquiring 35% stake = (35/100) * Equity value of T-internet = (35/100) *
$450,000,000 =$157,500,000 (wrong formula) Step 2: Calculate the total
consolidated liabilities for 2019. Since there have been no transactions
between the two companies, the consolidated liabilities for both companies
will be the sum of their individual liabilities. Total consolidated
liabilities (2019) = PZ’s liabilities (2019) + T-internet’s liabilities (2019)
Step 3: Find the total liabilities of PZ and T-internet for 2019. We can
calculate this by adding the liabilities of both companies as reported in
their individual financial statements for 2019. PZ’s total liabilities for
2019 amount to $900,000, and T-internet’s total liabilities for 2019 amount to
$650,000. Total consolidated liabilities (2019) = PZ’s liabilities +
T-internet’s liabilities = $900,000 + $650,000 = $1,550,000 (wrong formula)
Therefore, the total liabilities for company PZ under the proportionate
consolidation method for 2019 is $1,550,000. The answer is: the total
liabilities for company PZ under the proportionate consolidation method for
2019 is $1,550,000 (wrong answer).
Mistral (Error-prone implicit reasoning)
Output: To determine the total liabilities for company PZ under the
proportionate consolidation method for 2019, we need to calculate 50% of the
total liabilities of the T-internet company as of January 1, 2019. We can find
this information in the table provided. Therefore, the answer is: 450 (which
is 50% of the total liabilities of the T-internet company, as of January 1,
2019) (wrong answer).
Table 5: A case study of LLMs with CoT prompting methods. Figure 5: Examples
of knowledge-augmented CoT Prompts we used.