# On Perfectness of Annihilating-Ideal Graph of $\mathbb{Z}_{n}$

Manideepa Saha<EMAIL_ADDRESS>Sucharita Biswas
<EMAIL_ADDRESS>Angsuman Das<EMAIL_ADDRESS>Department of Mathematics, Presidency University, Kolkata, India

###### Abstract

The annihilating-ideal graph of a commutative ring $R$ with unity is defined
as the graph $\mathbb{AG}(R)$ with the vertex set is the set of all non-zero
ideals with non-zero annihilators and two distinct vertices $I$ and $J$ are
adjacent if and only if $IJ=0$. Nikandish et.al. proved that
$\mathbb{AG}(\mathbb{Z}_{n})$ is weakly perfect. In this short paper, we
characterize $n$ for which $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect.

###### keywords:

annihilator , perfect graph , ideals

###### MSC:

[2008] 05C25, 05C17

††journal:

##  1 Introduction

Over the last two decades, various graphs defined on rings has become an
interesting topic of research. Various graphs like
[1],[3],[4],[5],[6],[7],[8],[9] have been constructed to study the interplay
between the graph theoretic and ring-theoretic properties. Interested readers
are referred to the following surveys [2],[11] on graphs defined on rings. One
such graph is the annihilating-ideal graph $\mathbb{AG}(R)$ of a commutative
ring $R$, introduced by [7].

######  Definition 1.1.

[7] Let $R$ be a commutative ring with unity. The annihilating-ideal graph of
$R$ is defined as the graph $\mathbb{AG}(R)$ with the vertex set is the set of
all non-zero ideals with non-zero annihilators and two distinct vertices $I$
and $J$ are adjacent if and only if $IJ=0$.

In [12], the authors proved that $\mathbb{AG}(\mathbb{Z}_{n})$ is weakly
perfect, i.e., its clique number $\omega$ is equal to its chromatic number
$\chi$.

A graph $G$ is said to be perfect if $\omega(H)=\chi(H)$ holds for all induced
subgraphs $H$ of $G$. Perfect graphs play an important role in graph theory,
as many hard graph problems in general like graph coloring, finding maximum
clique and independent set, etc. can be solved in polynomial-time in case of
perfect graphs. Thus characterizing perfect graphs in different families [10],
[13] is an important issue. In this short paper, we characterize $n$ for which
$\mathbb{AG}(\mathbb{Z}_{n})$ is perfect. The following theorem is the main
result of the paper:

######  Theorem 1.1.

$\mathbb{AG}(\mathbb{Z}_{n})$ is perfect if and only if $n$ is one of the form
$p^{\alpha_{1}}_{1},~{}p^{\alpha_{1}}_{1}p^{\alpha_{2}}_{2},~{}p^{\alpha_{1}}_{1}p_{2}p_{3}$
or $p_{1}p_{2}p_{3}p_{4}$, where $p_{i}$’s are distinct primes and
$\alpha_{i}\in\mathbb{N}$.

In the next section, we prove Theorem 1.1. Before that we state an observation
and an important result which will be crucial in our proof.

######  Proposition 1.1.

The vertex set of $\mathbb{AG}(\mathbb{Z}_{n})$ is $\\{\langle m\rangle:m\mid
n,1<m<n\\}$ and two vertices $\langle m_{1}\rangle$ and $\langle m_{2}\rangle$
are adjacent if and only if $n\mid m_{1}m_{2}$.

######  Theorem 1.2.

(Strong Perfect Graph Theorem) A graph $G$ is perfect if and only if neither
$G$ nor $G^{c}$ has an induced odd-cycle of length greater or equal to $5$.

##  2 Proof of Theorem 1.1

We split the proof of Theorem 1.1 into different cases (lemmas) depending upon
the number of distinct prime factors of $n$.

First, we deal with the case when $n$ has more than $4$ distinct prime factors
and show that in this case $\mathbb{AG}(\mathbb{Z}_{n})$ is not perfect.

######  Lemma 2.1.

If $n={p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}\cdots{p_{k}}^{\alpha_{k}}$ and
$k\geq 5$, then $\mathbb{AG}(\mathbb{Z}_{n})$ is not perfect.

###### Proof.

Let
$m=n/({p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}\cdots{p_{5}}^{\alpha_{5}})$.
Then the following five vertices, taken in order,

$\langle{p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}{p_{4}}^{\alpha_{4}}m\rangle,\langle{p_{3}}^{\alpha_{3}}{p_{4}}^{\alpha_{4}}{p_{5}}^{\alpha_{5}}m\rangle,\langle{p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}m\rangle,\langle{p_{2}}^{\alpha_{2}}{p_{4}}^{\alpha_{4}}{p_{5}}^{\alpha_{5}}m\rangle,\langle{p_{1}}^{\alpha_{1}}{p_{3}}^{\alpha_{3}}{p_{5}}^{\alpha_{5}}m\rangle$

form an induced $5$-cycle in $\mathbb{AG}(\mathbb{Z}_{n})$. The adjacency and
non-adjacency follows from Proposition 1.1. Hence, by strong perfect graph
theorem, the lemma follows. ∎

Next we focus on the case when $n$ has exactly $4$ distinct prime factors. We
characterize the condition when $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect.

######  Lemma 2.2.

If
$n={p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}{p_{4}}^{\alpha_{4}}$,
then $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect if and only if $\alpha_{i}=1$
for all $i$.

###### Proof.

Let at least one $\alpha_{i}>1$, say $\alpha_{1}>1$. Then the following five
vertices, taken in order,

$\langle{p_{1}}^{\alpha_{1}}{p_{4}}^{\alpha_{4}}\rangle,\langle{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}{p_{4}}^{\alpha_{4}}\rangle,\langle{p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}\rangle,\langle
p_{1}{p_{3}}^{\alpha_{3}}{p_{4}}^{\alpha_{4}}\rangle,\langle{p_{1}}^{\alpha_{1}-1}{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}\rangle$

form an induced $5$-cycle in $\mathbb{AG}(\mathbb{Z}_{n})$. As earlier, the
adjacency and non-adjacency follows from Proposition 1.1. Hence, by strong
perfect graph theorem, $\mathbb{AG}(\mathbb{Z}_{n})$ is not perfect.

Now, we assume that $n=p_{1}p_{2}p_{3}p_{4}$. Then
$\mathbb{AG}(\mathbb{Z}_{n})$ has $14$ vertices:

$\begin{array}[]{llc}\mbox{1st type:}&\langle p_{1}\rangle,\langle
p_{2}\rangle,\langle p_{3}\rangle,\langle p_{4}\rangle&4\mbox{ vertices of
degree }1\\\ \mbox{2nd type:}&\langle p_{1}p_{2}\rangle,\langle
p_{2}p_{3}\rangle,\ldots,\langle p_{3}p_{4}\rangle&6\mbox{ vertices of degree
}3\\\ \mbox{3rd type:}&\langle p_{1}p_{2}p_{3}\rangle,\langle
p_{2}p_{3}p_{4}\rangle,\langle p_{1}p_{3}p_{4}\rangle,\langle
p_{1}p_{2}p_{4}\rangle&4\mbox{ vertices of degree }7\\\ \end{array}$

If possible, let $\mathbb{AG}(\mathbb{Z}_{n})$ has an induced odd cycle $C$ of
length $t\geq 5$. Thus $C$ must have a vertex of second type. Without loss of
generality, let $\langle p_{1}p_{2}\rangle$ be a vertex in $C$. As $\langle
p_{1}p_{2}\rangle$ is adjacent to three vertices, namely $\langle
p_{3}p_{4}\rangle,\langle p_{1}p_{3}p_{4}\rangle,\langle
p_{2}p_{3}p_{4}\rangle$, at least two of them, must lie on $C$.

Case 1: $\langle p_{1}p_{3}p_{4}\rangle\sim\langle
p_{1}p_{2}\rangle\sim\langle p_{3}p_{4}\rangle$ be a part of $C$. Let $\langle
x\rangle$ be the next vertex on $C$, i.e., $\langle
p_{1}p_{3}p_{4}\rangle\sim\langle p_{1}p_{2}\rangle\sim\langle
p_{3}p_{4}\rangle\sim\langle x\rangle$. Then by the adjacency condition of the
last two vertices, we get $p_{1}p_{2}\mid x$. But this imply that $\langle
x\rangle\sim\langle p_{1}p_{3}p_{4}\rangle$, i.e., we get a chord in $C$, a
contradiction.

Case 2: $\langle p_{2}p_{3}p_{4}\rangle\sim\langle
p_{1}p_{2}\rangle\sim\langle p_{3}p_{4}\rangle$ be a part of $C$. In this case
also, proceeding similalrly, we get a contradiction.

Case 3: $\langle p_{1}p_{3}p_{4}\rangle\sim\langle
p_{1}p_{2}\rangle\sim\langle p_{2}p_{3}p_{4}\rangle$ be a part of $C$.
However, in this case, we get a chord of the form $\langle
p_{1}p_{3}p_{4}\rangle\sim\langle p_{2}p_{3}p_{4}\rangle$ in $C$, a
contradiction.

Thus $\mathbb{AG}(\mathbb{Z}_{n})$ has no induced odd cycle $C$ of length
$t\geq 5$.

Now, we consider the complement graph of $\mathbb{AG}(\mathbb{Z}_{n})$. If
possible, let $C^{\prime}:\langle x_{1}\rangle\sim\langle
x_{2}\rangle\sim\cdots\sim\langle x_{t}\rangle\sim\langle x_{1}\rangle$ be an
induced odd cycle $C$ of length $t\geq 5$ in
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$. As $C^{\prime}$ consists of $t\geq 5$
vertices, at least one of the vertices must be of 1st or 2nd type.

Case 1: $\langle x_{1}\rangle$ is a vertex of 1st type, i.e., without loss of
generality, let $x_{1}=p_{1}$. Now, as $\langle p_{1}\rangle$ is a pendant
vertex in $\mathbb{AG}(\mathbb{Z}_{n})$, $\langle p_{1}\rangle$ is not
adjacent to exactly one vertex in $\mathbb{AG}^{c}(\mathbb{Z}_{n})$. Thus
$C^{\prime}$ always contain a chord, a contradiction.

Case 2: $\langle x_{1}\rangle$ is a vertex of 2nd type, i.e., without loss of
generality, let $x_{1}=p_{1}p_{2}$. As degree of $\langle p_{1}p_{2}\rangle$
in $\mathbb{AG}(\mathbb{Z}_{n})$ is $3$, the number of vertices which are not
adjacent to $\langle p_{1}p_{2}\rangle$ in $\mathbb{AG}^{c}(\mathbb{Z}_{n})$
is $3$. Thus, as $C^{\prime}$ is chordless, it must be an induced $5$-cycle,
i.e.,

$C^{\prime}:\langle p_{1}p_{2}\rangle\sim\langle x_{2}\rangle\sim\langle
x_{3}\rangle\sim\langle x_{4}\rangle\sim\langle x_{5}\rangle\sim\langle
p_{1}p_{2}\rangle$

As $\langle x_{3}\rangle,\langle x_{4}\rangle$ are adjacent to $\langle
p_{1}p_{2}\rangle$ in $\mathbb{AG}(\mathbb{Z}_{n})$, we must have
$x_{3},x_{4}\in\\{p_{3}p_{4},p_{1}p_{3}p_{4},p_{2}p_{3}p_{4}\\}$. If
$\\{x_{3},x_{4}\\}=\\{p_{1}p_{3}p_{4},p_{2}p_{3}p_{4}\\}$, then $\langle
x_{3}\rangle\sim\langle x_{4}\rangle$ in $\mathbb{AG}(\mathbb{Z}_{n})$. Thus,
without loss of generality, we can assume $x_{3}=p_{3}p_{4}$ and
$x_{4}=p_{1}p_{3}p_{4}$, i.e.,

$C^{\prime}:\langle p_{1}p_{2}\rangle\sim\langle x_{2}\rangle\sim\langle
p_{3}p_{4}\rangle\sim\langle p_{1}p_{3}p_{4}\rangle\sim\langle
x_{5}\rangle\sim\langle p_{1}p_{2}\rangle$

As $\langle x_{5}\rangle\not\sim\langle p_{3}p_{4}\rangle$ in
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$, we have $p_{1}p_{2}\mid x_{5}$. Thus
$x_{5}=p_{1}p_{2}p_{3}$ or $p_{1}p_{2}p_{4}$. However, in any case, $\langle
x_{5}\rangle\sim\langle p_{1}p_{3}p_{4}\rangle$ in
$\mathbb{AG}(\mathbb{Z}_{n})$, a contradiction.

Thus $\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has no induced odd cycle $C$ of length
$t\geq 5$. Hence, by strong perfect graph theorem, the lemma follows. ∎

Now, we turn towards the case when $n$ has exactly three distinct prime
factors and characterize the perfect graphs among this subfamily.

######  Lemma 2.3.

If $n={p_{1}}^{\alpha_{1}}{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}$ and
$\alpha_{i}>1$ for at least two $i$’s, then $\mathbb{AG}(\mathbb{Z}_{n})$ is
not perfect.

###### Proof.

Let $\alpha_{i}\geq 2$ for at least two $i$’s, say $\alpha_{1},\alpha_{2}\geq
2$. Then the following five vertices, taken in order,

$\langle{p_{2}}^{\alpha_{2}}{p_{3}}^{\alpha_{3}}\rangle,\langle{p_{1}}^{\alpha_{1}}{p_{2}}\rangle,\langle{p_{1}}{p_{2}}^{\alpha_{2}-1}{p_{3}}^{\alpha_{3}}\rangle,\langle{p_{1}}^{\alpha_{1}-1}{p_{2}}^{\alpha_{2}}\rangle,\langle{p_{1}}^{\alpha_{1}}{p_{3}}^{\alpha_{3}}\rangle$

form an induced $5$-cycle in $\mathbb{AG}(\mathbb{Z}_{n})$. As earlier, the
adjacency and non-adjacency follows from Proposition 1.1. Hence, by strong
perfect graph theorem, $\mathbb{AG}(\mathbb{Z}_{n})$ is not perfect. ∎

So, now we assume that $n={p_{1}}^{\alpha_{1}}{p_{2}}{p_{3}}$.

######  Lemma 2.4.

If $n={p}^{\alpha}{q}r$, then $\mathbb{AG}(\mathbb{Z}_{n})$ has no induced odd
cycle of length greater than $3$.

###### Proof.

If possible, let $\mathbb{AG}(\mathbb{Z}_{n})$ has an induced odd cycle
$C:\langle x_{1}\rangle\sim\langle x_{2}\rangle\sim\cdots\sim\langle
x_{t}\rangle\sim\langle x_{1}\rangle$, where
$x_{i}=p^{\alpha_{i}}q^{\beta_{i}}r^{\gamma_{i}}$ for $i=1,2,\ldots,t$.

Claim 1: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 0$.

Proof of Claim 1: If possible let $\alpha_{i}\leq\alpha/2$ and
$\beta_{i}=\gamma_{i}=0$. Now $\langle x_{i}\rangle\sim\langle x_{i+1}\rangle$
and $\langle x_{i}\rangle\sim\langle x_{i-1}\rangle$ imply
$\alpha_{i+1},\alpha_{i-1}\geq\alpha/2$ and
$\beta_{i+1}=\beta_{i-1}=1=\gamma_{i+1}=\gamma_{i-1}$. Hence we have $\langle
x_{i+1}\rangle\sim\langle x_{i-1}\rangle$, which is a contradiction.

Claim 2: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}<\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 1$.

Proof of Claim 2: If possible let $\alpha_{i}\geq\alpha/2$ and
$\beta_{i}=\gamma_{i}=1$. Now $\langle x_{i}\rangle\nsim\langle
x_{i+2}\rangle$ and $\langle x_{i}\rangle\nsim\langle x_{i+3}\rangle$ imply
$\alpha_{i+2},\alpha_{i+3}<\alpha/2$, hence
$\alpha_{i+2}+\alpha_{i+3}<\alpha$, which is a contradiction as $\langle
x_{i+2}\rangle\sim\langle x_{i+3}\rangle$.

Claim 3: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 1$.

Proof of Claim 3: Without loss of generality let $\alpha_{1}\leq\alpha/2$ and
$\beta_{1}=\gamma_{1}=1$. Now $\langle x_{1}\rangle\sim\langle x_{2}\rangle$
and $\langle x_{1}\rangle\sim\langle x_{t}\rangle$ imply
$\alpha_{2},\alpha_{t}\geq\alpha/2$. As $\langle x_{2}\rangle\nsim\langle
x_{t}\rangle$ then either $\beta_{2}+\beta_{t}=0$ or $\gamma_{2}+\gamma_{t}=0$
or both. Again without loss of generality we can take $\beta_{2}+\beta_{t}=0$,
i.e., $\beta_{2}=\beta_{t}=0$ and hence $\langle x_{2}\rangle\sim\langle
x_{3}\rangle$ and $\langle x_{t}\rangle\sim\langle x_{t-1}\rangle$ imply
$\beta_{3}=1=\beta_{t-1}$. Now $\langle x_{1}\rangle\sim\langle x_{t}\rangle$
and $\langle x_{1}\rangle\nsim\langle x_{4}\rangle$ imply
$\alpha_{1}+\alpha_{t}\geq\alpha$ and $\alpha_{1}+\alpha_{4}<\alpha$. From
these two equations we have $\alpha_{t}>\alpha_{4}$. Therefore
$\alpha_{3}+\alpha_{4}\geq\alpha$ imply $\alpha_{3}+\alpha_{t}>\alpha$. So
$\langle x_{t}\rangle\nsim\langle x_{3}\rangle$ and $\beta_{3}=1$ imply
$\gamma_{t}+\gamma_{3}=0$, i.e., $\gamma_{3}=\gamma_{t}=0$. Therefore
$\gamma_{t-1}=1$. As $\langle x_{2}\rangle\nsim\langle x_{t-1}\rangle$ and
$\beta_{t-1}=\gamma_{t-1}=1$ hence $\alpha_{2}+\alpha_{t-1}<\alpha$ and we
know $\alpha_{1}+\alpha_{2}\geq\alpha$. From these two equations we have
$\alpha_{1}>\alpha_{t-1}$. So $\alpha_{t-1}+\alpha_{t-2}\geq\alpha$ imply
$\alpha_{1}+\alpha_{t-2}>\alpha$ and $\beta_{1}=\gamma_{1}=1$, so we have
$\langle x_{1}\rangle\sim\langle x_{t-2}\rangle$, which is a contradiction.

From Claim 2 and Claim 3 we see that for any $i$, both $\alpha_{i}$ and
$\beta_{i}$ can not be $1$ and hence both can not be $0$.

Claim 4: For all $i\in\\{1,2,\ldots,t\\}$, $\alpha_{i}>\alpha/2$ .

Proof of Claim 4: Without loss of generality let $\alpha_{1}\leq\alpha/2$ and
$\beta_{1}=1,\gamma_{1}=0$. Now $\langle x_{1}\rangle\sim\langle x_{2}\rangle$
and $\langle x_{1}\rangle\sim\langle x_{t}\rangle$ imply
$\alpha_{2},\alpha_{t}\geq\alpha/2$ and $\gamma_{2}=\gamma_{t}=1$. As $\langle
x_{2}\rangle\nsim\langle x_{t}\rangle$, $\alpha_{2}+\alpha_{t}\geq\alpha$ and
$\gamma_{2}+\gamma_{t}=2$, we have $\beta_{2}+\beta_{t}=0$, i.e.,
$\beta_{2}=\beta_{t}=0$. Hence $\beta_{3}=\beta_{t-1}=1$. Now $\langle
x_{3}\rangle\nsim\langle x_{t}\rangle$ and $\beta_{3}=1=\gamma_{t}$ imply
$\alpha_{3}+\alpha_{t}<\alpha$ and $\alpha_{2}+\alpha_{3}\geq\alpha$, hence
$\alpha_{2}>\alpha_{t}$. Therefore $\alpha_{t}+\alpha_{t-1}\geq\alpha$ implies
$\alpha_{2}+\alpha_{t-1}>\alpha$. So $\beta_{t-1}=\gamma_{2}=1$ imply $\langle
x_{2}\rangle\sim\langle x_{t-1}\rangle$, which is impossible and hence the
Claim holds.

So from the Claim 1 and Claim 4 we can consider $\alpha_{1}>\alpha/2$,
$\beta_{1}=1$ and $\gamma_{1}=0$. From Claim 4 we have
$\alpha_{3},\alpha_{4}>\alpha/2$. So $\langle x_{1}\rangle\nsim\langle
x_{3}\rangle$, $\alpha_{1}+\alpha_{3}>\alpha$ and $\beta_{1}=1$ imply
$\gamma_{1}+\gamma_{3}=0$, i.e., $\gamma_{3}=0$, i.e., $\gamma_{4}=1$.
Therefore $\alpha_{1}+\alpha_{4}>\alpha$ and $\beta_{1}=\gamma_{4}=1$ imply
$\langle x_{1}\rangle\sim\langle x_{4}\rangle$, which is a contradiction. This
completes the proof. ∎

######  Lemma 2.5.

If $n={p}^{\alpha}{q}r$, then $\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has no induced
odd cycle of length greater than $3$.

###### Proof.

We start by noting that $\langle a\rangle\sim\langle b\rangle$ in
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ if and only if $n\nmid ab$. If possible, let
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has an induced odd cycle $C:\langle
x_{1}\rangle\sim\langle x_{2}\rangle\sim\cdots\sim\langle
x_{t}\rangle\sim\langle x_{1}\rangle$, where
$x_{i}=p^{\alpha_{i}}q^{\beta_{i}}r^{\gamma_{i}}$ for $i=1,2,\ldots,t$.

Claim 1: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 0$.

Proof of Claim 1: If possible let $\alpha_{i}\leq\alpha/2$ and
$\beta_{i}=\gamma_{i}=0$. Now $\langle x_{i+2}\rangle$, $\langle
x_{i+3}\rangle\nsim\langle x_{i}\rangle$ imply
$\alpha_{i+2},\alpha_{i+3}\geq\alpha/2$,
$\beta_{i+2}=\beta_{i+3}=1=\gamma_{i+2}=\gamma_{i+3}$. Therefore from this we
have $\langle x_{i+2}\rangle\nsim\langle x_{i+3}\rangle$, which is a
contradiction.

Claim 2: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}<\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 1$.

Proof of Claim 2: If possible let $\alpha_{i}\geq\alpha/2$ and
$\beta_{i}=\gamma_{i}=1$. As $\langle x_{i-1}\rangle$ and $\langle
x_{i+1}\rangle\sim\langle x_{i}\rangle$, hence
$\alpha_{i-1},\alpha_{i+1}<\alpha/2$, i.e., $\alpha_{i-1}+\alpha_{i+1}<\alpha$
and hence $\langle x_{i-1}\rangle\sim\langle x_{i+1}\rangle$, which is a
contradiction.

Claim 3: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or one
of $\beta_{i},\gamma_{i}\neq 1$.

Proof of Claim 3: Without loss of generality let $\alpha_{1}\leq\alpha/2$ and
$\beta_{1}=\gamma_{1}=1$. As $\langle x_{3}\rangle$, $\langle
x_{4}\rangle\nsim\langle x_{1}\rangle$ hence
$\alpha_{3},\alpha_{4}\geq\alpha/2$, i.e., $\alpha_{3}+\alpha_{4}\geq\alpha$.
Now $\langle x_{3}\rangle\sim\langle x_{4}\rangle$ implies either
$\beta_{3}+\beta_{4}=0$ or $\gamma_{3}+\gamma_{4}=0$ or both. Without loss of
generality we can assume $\beta_{3}+\beta_{4}=0$, i.e.,
$\beta_{3}=0=\beta_{4}$. Now $\langle x_{2}\rangle\nsim\langle x_{4}\rangle$,
$\beta_{4}=0$ imply $\beta_{2}=1$ and $\langle x_{3}\rangle\nsim\langle
x_{t}\rangle$, $\beta_{3}=0$ imply $\beta_{t}=1$. Again $\langle
x_{1}\rangle\sim\langle x_{2}\rangle$ and $\beta_{1}=1=\gamma_{1}$ imply
$\alpha_{1}+\alpha_{2}<\alpha$. Therefore $\alpha_{2}+\alpha_{t}\geq\alpha$
implies $\alpha_{t}>\alpha_{1}$. So $\alpha_{1}+\alpha_{t-1}\geq\alpha$ imply
$\alpha_{t}+\alpha_{t-1}>\alpha$. Now $\langle x_{t}\rangle\sim\langle
x_{t-1}\rangle$ and $\beta_{t}=1$ imply $\gamma_{t}+\gamma_{t-1}=0$, i.e.,
$\gamma_{t}=0$. Again $\langle x_{1}\rangle\sim\langle x_{t}\rangle$ and
$\beta_{1}=1=\gamma_{1}$ imply $\alpha_{1}+\alpha_{t}<\alpha$. So
$\alpha_{2}+\alpha_{t}\geq\alpha$ imply $\alpha_{2}>\alpha_{1}$. So
$\alpha_{1}+\alpha_{3}\geq\alpha$ imply $\alpha_{2}+\alpha_{3}>\alpha$. Now
$\langle x_{2}\rangle\sim\langle x_{3}\rangle$ and $\beta_{2}=1$ imply
$\gamma_{2}+\gamma_{3}=0$, i.e., $\gamma_{2}=0$. Therefore
$\gamma_{2}=0=\gamma_{t}$ implies $\langle x_{2}\rangle\sim\langle
x_{t}\rangle$, which is impossible.

From Claim 2 and Claim 3 we see that for any $i$, both $\alpha_{i}$ and
$\beta_{i}$ can not be $1$ and hence both can not be $0$.

Claim 4: For all $i\in\\{1,2,\ldots,t\\}$, $\alpha_{i}>\alpha/2$ .

Proof of Claim 4: Without loss of generality let $\alpha_{1}\leq\alpha/2$ and
$\beta_{1}=1,\gamma_{1}=0$. Therefore $\langle x_{3}\rangle$, $\langle
x_{4}\rangle\nsim\langle x_{1}\rangle$ imply
$\alpha_{3},\alpha_{4}\geq\alpha/2$ and $\gamma_{3}=1=\gamma_{4}$. So $\langle
x_{3}\rangle\sim\langle x_{4}\rangle$ imply $\beta_{3}+\beta_{4}=0$, i.e.,
$\beta_{3}=0=\beta_{4}$. Now $\beta_{4}=0$ and $\langle
x_{4}\rangle\nsim\langle x_{2}\rangle$ imply $\beta_{2}=1$. Now $\langle
x_{2}\rangle\sim\langle x_{3}\rangle$ and $\beta_{2}=1=\gamma_{3}$ imply
$\alpha_{2}+\alpha_{3}<\alpha$. So $\alpha_{1}+\alpha_{3}\geq\alpha$ imply
$\alpha_{1}>\alpha_{2}$. Also $\alpha_{2}+\alpha_{t}\geq\alpha$ imply
$\alpha_{1}+\alpha_{t}>\alpha$. So $\langle x_{1}\rangle\nsim\langle
x_{t}\rangle$ and $\beta_{1}=1$ imply $\gamma_{1}+\gamma_{t}=0$, i.e.,
$\gamma_{t}=0$, i.e., $\gamma_{2}=1$.Hence we have $\beta_{2}=1=\gamma_{2}$,
which is not possible by Claim 2 and Claim 3.

So from the Claim 1 and Claim 4 we can consider $\alpha_{1}>\alpha/2$,
$\beta_{1}=1$ and $\gamma_{1}=0$. So $\langle x_{3}\rangle,\langle
x_{4}\rangle\nsim\langle x_{1}\rangle$ imply $\gamma_{3}=1=\gamma_{4}$. From
Claim 4 we have $\alpha_{3},\alpha_{4}>\alpha/2$. So $\langle
x_{3}\rangle\sim\langle x_{4}\rangle$ implies $\beta_{3}+\beta_{4}=0$, i.e.,
$\beta_{3}=0=\beta_{4}$. Now $\langle x_{2}\rangle\sim\langle x_{3}\rangle$,
$\gamma_{3}=1$ and $\alpha_{2},\alpha_{3}>\alpha/2$ imply
$\beta_{2}+\beta_{3}=0$, i.e., $\beta_{2}=0$. Therefore
$\beta_{2}=0=\beta_{4}$ imply $\langle x_{2}\rangle\sim\langle x_{4}\rangle$,
which is a contradiction and this completes the proof. ∎

Thus, it follows from strong perfect graph theorem and Lemma 2.4 and Lemma
2.5, that if $n=p^{\alpha}qr$, then $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect.

Thus, the case when $n$ has three distinct prime factors is complete. Now, we
focus on the case, when $n$ has two distinct prime factors.

######  Lemma 2.6.

If $n={p}^{\alpha}{q}^{\beta}$, then $\mathbb{AG}(\mathbb{Z}_{n})$ has no
induced odd cycle of length greater than $3$.

###### Proof.

If possible, let $\mathbb{AG}(\mathbb{Z}_{n})$ has an induced odd cycle
$C:\langle x_{1}\rangle\sim\langle x_{2}\rangle\sim\cdots\sim\langle
x_{t}\rangle\sim\langle x_{1}\rangle$, where
$x_{i}=p^{\alpha_{i}}q^{\beta_{i}}$ for $i=1,2,\ldots,t$.

Claim 1: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or
$\beta_{i}>\beta/2$.

Proof of Claim 1: If $\alpha_{i}\leq\alpha/2$ and $\beta_{i}\leq\beta/2$ for
some $i$, then as $\langle x_{i}\rangle\sim\langle x_{i+1}\rangle$, we have
$\alpha_{i+1}\geq\alpha/2$ and $\beta_{i+1}\geq\beta/2$. Similarly, as
$\langle x_{i}\rangle\sim\langle x_{i-1}\rangle$, we have
$\alpha_{i-1}\geq\alpha/2$ and $\beta_{i-1}\geq\beta/2$. But this implies
$\alpha_{i+1}+\alpha_{i-1}\geq\alpha$ and $\beta_{i+1}+\beta_{i-1}\geq\beta$,
i.e., $\langle x_{i-1}\rangle\sim\langle x_{i+1}\rangle$, a contradiction.
Thus the claim holds.

In Claim 1, we show that for any $i$, either $\alpha_{i}$ or $\beta_{i}$ is
greater than $\alpha/2$ or $\beta/2$ respectively. In the next claim, we show
that both of them can not be greater or equal to $\alpha/2$ and $\beta/2$
simultaneously.

Claim 2: For any $i$, both $\alpha_{i}\geq\alpha/2$ and $\beta_{i}\geq\beta/2$
can not hold.

Proof of Claim 2: Without loss of generality, suppose $\alpha_{1}\geq\alpha/2$
and $\beta_{1}\geq\beta/2$. As $\langle x_{1}\rangle\not\sim\langle
x_{3}\rangle$, we have either $\alpha_{1}+\alpha_{3}<\alpha$ or
$\beta_{1}+\beta_{3}<\beta$, i.e., $\alpha_{3}<\alpha/2$ or
$\beta_{3}<\beta/2$. Again, without loss of generality, we assume that
$\alpha_{3}<\alpha/2$. So, by Claim 1, we get $\beta_{3}>\beta/2$. As $\langle
x_{3}\rangle$ is adjacent to both $\langle x_{2}\rangle$ and $\langle
x_{4}\rangle$, we have $\alpha_{2},\alpha_{4}>\alpha/2$. As $\langle
x_{1}\rangle\not\sim\langle x_{4}\rangle$ and
$\alpha_{1},\alpha_{4}\geq\alpha/2$ and $\beta_{1}\geq\beta/2$, we have
$\beta_{4}<\beta/2$. Again as $\langle x_{4}\rangle\sim\langle x_{5}\rangle$,
we have $\beta_{5}>\beta/2$.

Here $C$ is a $t$-cycle with $t$ odd and $t\geq 5$. We show, by strong
induction, that for any odd value of $t\geq 5$, we get a contradiction.

We start with $t=5$, i.e., $\langle x_{1}\rangle\sim\langle x_{5}\rangle$. As
$\langle x_{1}\rangle\not\sim\langle x_{4}\rangle$ and
$\alpha_{1},\alpha_{4}\geq\alpha/2$, we have $\beta_{1}+\beta_{4}<\beta$.
Again as $\langle x_{4}\rangle\sim\langle x_{5}\rangle$, we have
$\beta_{4}+\beta_{5}\geq\beta$. Thus, we get $\beta_{5}>\beta_{1}$. As
$\langle x_{1}\rangle\sim\langle x_{2}\rangle$, we have
$\beta_{1}+\beta_{2}\geq\beta$, i.e., $\beta_{2}+\beta_{5}>\beta$. Thus as
$\langle x_{2}\rangle\not\sim\langle x_{5}\rangle$, we must have
$\alpha_{2}+\alpha_{5}<\alpha$. Also, as $\langle x_{1}\rangle\sim\langle
x_{5}\rangle$, we have $\alpha_{1}+\alpha_{5}\geq\alpha$. Thus we must have
$\alpha_{1}>\alpha_{2}$. Similarly, $\langle x_{2}\rangle\sim\langle
x_{3}\rangle$ implies $\alpha_{2}+\alpha_{3}\geq\alpha$, i.e.,
$\alpha_{1}+\alpha_{3}>\alpha$. On the other hand, as
$\beta_{1},\beta_{3}\geq\beta/2$, we have $\beta_{1}+\beta_{3}\geq\beta$. Thus
we have $\langle x_{1}\rangle\sim\langle x_{3}\rangle$. Hence we get a
contradiction for $t=5$.

For $t>5$, as $\langle x_{1}\rangle\not\sim\langle x_{5}\rangle$ and
$\beta_{1},\beta_{5}\geq\beta/2$ and $\alpha_{1}\geq\alpha/2$, we have
$\alpha_{5}<\alpha/2$. Thus the induction hypothesis is: For all odd $k$
satisfying $1<k<t-2$,

$\begin{array}[]{ccc}\alpha_{i}<\alpha/2,~{}1<i\leq k,~{}i\mbox{ is
odd}&\mbox{and }&\beta_{i}\geq\beta/2,~{}1\leq i\leq k,~{}i\mbox{ is odd}\\\
\alpha_{j}\geq\alpha/2,~{}2<j\leq k-1,~{}j\mbox{ is even}&\mbox{and
}&\beta_{j}<\beta/2,~{}2<j\leq k-1,~{}j\mbox{ is even}\\\ \end{array}$

Now $\langle x_{k+1}\rangle\sim\langle x_{k}\rangle$ and $\alpha_{k}<\alpha/2$
imply $\alpha_{k+1}>\alpha/2$. Similarly, $\langle x_{1}\rangle\not\sim\langle
x_{k+1}\rangle$ and $\beta_{1}\geq\beta/2$ implies $\beta_{k+1}<\beta/2$ and
$\langle x_{k+1}\rangle\sim\langle x_{k+2}\rangle$ implies
$\beta_{k+2}>\beta/2$. As $k+2\leq t-2$, we have $\langle
x_{1}\rangle\not\sim\langle x_{k+2}\rangle$ and
$\beta_{1},\beta_{k+2}>\beta/2$, which implies $\alpha_{k+2}<\alpha/2$. Thus,
by induction, we have

$\begin{array}[]{c}\mbox{For odd }i\mbox{ with
}1<i<t,\alpha_{i}<\alpha/2\mbox{ and, for odd }i\mbox{ with }1\leq i\leq
t,\beta_{i}\geq\beta/2\\\ \mbox{For even }j\mbox{ with
}j>2,\alpha_{j}\geq\alpha/2\mbox{ and }\beta_{j}<\beta/2.\end{array}$

Now, $\langle x_{2}\rangle\not\sim\langle x_{t}\rangle$ implies either
$\beta_{2}+\beta_{t}<\beta$ or $\alpha_{2}+\alpha_{t}<\alpha$ or both. As $t$
is odd, $t-1$ is even and hence $\alpha_{1},\alpha_{t-1}\geq\alpha/2$ and
$\beta_{1}>\beta/2$. Thus $\langle x_{1}\rangle\not\sim\langle x_{t-1}\rangle$
implies $\beta_{1}+\beta_{t-1}<\beta$ and $\langle x_{t}\rangle\sim\langle
x_{t-1}\rangle$ implies $\beta_{t}+\beta_{t-1}\geq\beta$. Therefore
$\beta_{t}>\beta_{1}$.

Again $\langle x_{1}\rangle\sim\langle x_{2}\rangle$ implies
$\beta_{1}+\beta_{2}\geq\beta$, i.e., $\beta_{t}+\beta_{2}>\beta$. Now, as
$\langle x_{2}\rangle\not\sim\langle x_{t}\rangle$, we must have
$\alpha_{2}+\alpha_{t}<\alpha$.

Also $\langle x_{1}\rangle\sim\langle x_{t}\rangle$ implies
$\alpha_{1}+\alpha_{t}\geq\alpha$. Therefore $\alpha_{1}>\alpha_{2}$.
Similarly $\langle x_{2}\rangle\sim\langle x_{3}\rangle$ implies
$\alpha_{2}+\alpha_{3}\geq\alpha$. Thus $\alpha_{1}+\alpha_{3}>\alpha$. Again,
as $\beta_{1},\beta_{3}>\beta/2$, we have $\langle x_{1}\rangle\sim\langle
x_{3}\rangle$, a contradiction. Hence Claim 2 holds good.

From Claim 1 and 2, we see that for any $i$, both $\alpha_{i},\beta_{i}$ can
not be simultaneously ‘greater or equal’ or ‘lesser or equal’ to $\alpha/2$
and $\beta/2$ respectively. So for any $i$, either
$\alpha_{i}<\alpha/2,\beta_{i}>\beta/2$ or
$\alpha_{i}>\alpha/2,\beta_{i}<\beta/2$ holds. Without loss of generality, let
$\alpha_{1}<\alpha/2,\beta_{1}>\beta/2$.

Now, as $\langle x_{1}\rangle\sim\langle x_{2}\rangle$, we have
$\alpha_{1}+\alpha_{2}\geq\alpha$, which implies $\alpha_{2}>\alpha/2$, i.e.,
$\beta_{2}<\beta/2$ (by Claim 2). Similarly $\langle x_{2}\rangle\sim\langle
x_{3}\rangle$ implies $\beta_{3}>\beta/2$, i.e., $\alpha_{3}<\alpha/2$ (by
Claim 2). Proceeding this way, we get

$\begin{array}[]{c}\mbox{If }i\mbox{ is odd, }\alpha_{i}<\alpha/2\mbox{ and
}\beta_{i}>\beta/2\\\ \mbox{If }i\mbox{ is even, }\alpha_{i}>\alpha/2\mbox{
and }\beta_{i}<\beta/2\end{array}$

As $t$ is odd, we have $\alpha_{t}<\alpha/2$. Also, as $\langle
x_{1}\rangle\sim\langle x_{t}\rangle$, we have
$\alpha_{1}+\alpha_{t}\geq\alpha$. However as
$\alpha_{1},\alpha_{t}<\alpha/2$, we get a contradiction. Thus
$\mathbb{AG}(\mathbb{Z}_{n})$ has no induced odd cycle of length greater than
$3$. ∎

######  Lemma 2.7.

If $n={p}^{\alpha}{q}^{\beta}$, then $\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has no
induced odd cycle of length greater than $3$.

###### Proof.

We start by noting that $\langle a\rangle\sim\langle b\rangle$ in
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ if and only if $n\nmid ab$. If possible, let
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has an induced odd cycle $C:\langle
x_{1}\rangle\sim\langle x_{2}\rangle\sim\cdots\sim\langle
x_{t}\rangle\sim\langle x_{1}\rangle$, where
$x_{i}=p^{\alpha_{i}}q^{\beta_{i}}$ for $i=1,2,\ldots,t$.

Claim 1: For all $i\in\\{1,2,\ldots,t\\}$, either $\alpha_{i}>\alpha/2$ or
$\beta_{i}>\beta/2$.

Proof of Claim 1: If $\alpha_{i}\leq\alpha/2$ and $\beta_{i}\leq\beta/2$ for
some $i$, then as $\langle x_{i}\rangle\not\sim\langle x_{i+2}\rangle$ and
$\langle x_{i}\rangle\not\sim\langle x_{i+3}\rangle$, we have
$\alpha_{i+2},\alpha_{i+3}\geq\alpha/2$ and
$\beta_{i+2},\beta_{i+3}\geq\beta/2$. But this imply that $\langle
x_{i+2}\rangle\not\sim\langle x_{i+3}\rangle$ in
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$, a contradiction. Hence Claim 1 holds. In
Claim 1, we show that for any $i$, either $\alpha_{i}$ or $\beta_{i}$ is
greater than $\alpha/2$ or $\beta/2$ respectively. In the next claim, we show
that both of them can not be greater or equal to $\alpha/2$ and $\beta/2$
simulatneously.

Claim 2: For any $i$, both $\alpha_{i}\geq\alpha/2$ and $\beta_{i}\geq\beta/2$
can not hold.

Proof of Claim 2: Without loss of generality, suppose $\alpha_{1}\geq\alpha/2$
and $\beta_{1}\geq\beta/2$. $\langle x_{1}\rangle\sim\langle x_{2}\rangle$
implies either $\alpha_{1}+\alpha_{2}<\alpha$ or $\beta_{1}+\beta_{2}<\beta$
or both. Again, without loss of generality, we assume that
$\alpha_{1}+\alpha_{2}<\alpha$, i.e., $\alpha_{2}<\alpha/2$. Now $\langle
x_{2}\rangle\nsim\langle x_{t}\rangle$ implies
$\alpha_{2}+\alpha_{t}\geq\alpha$, i.e., $\alpha_{t}>\alpha/2$.

At first we assume that $t=5$. Therefore $\langle x_{1}\rangle\sim\langle
x_{5}\rangle$ and $\alpha_{1},\alpha_{5}\geq\alpha/2$ imply
$\beta_{1}+\beta_{5}<\beta$. Now $\langle x_{1}\rangle\nsim\langle
x_{3}\rangle$ imply $\alpha_{1}+\alpha_{3}\geq\alpha$, so
$\alpha_{1}+\alpha_{2}<\alpha$ implies $\alpha_{3}>\alpha_{2}$. Again $\langle
x_{3}\rangle\sim\langle x_{4}\rangle$ imply either
$\alpha_{3}+\alpha_{4}<\alpha$ or $\beta_{3}+\beta_{4}<\beta$ or both. Now
$\langle x_{2}\rangle\nsim\langle x_{4}\rangle$ imply
$\alpha_{2}+\alpha_{4}\geq\alpha$. If $\alpha_{3}+\alpha_{4}<\alpha$, then we
have $\alpha_{2}>\alpha_{3}$, which is a contradiction as we already have
$\alpha_{3}>\alpha_{2}$. Now $\langle x_{1}\rangle\nsim\langle x_{4}\rangle$
implies $\beta_{1}+\beta_{4}\geq\beta$. If $\beta_{3}+\beta_{4}<\beta$, then
we have $\beta_{1}>\beta_{3}$. Now $\langle x_{3}\rangle\nsim\langle
x_{5}\rangle$ implies $\beta_{3}+\beta_{5}\geq\beta$, therefore
$\beta_{1}+\beta_{5}>\beta$, which contradicts the condition
$\beta_{1}+\beta_{5}<\beta$. So for $t=5$ the Claim 2 is true.

Now assume that $t>5$. As $\alpha_{1},\alpha_{t}\geq\alpha/2$ and $\langle
x_{1}\rangle\sim\langle x_{t}\rangle$, we have $\beta_{1}+\beta_{t}<\beta$,
i.e., $\beta_{t}<\beta/2$ as $\beta_{1}\geq\beta/2$. Now $\alpha_{2}<\alpha/2$
and $\langle x_{4}\rangle,\langle x_{5}\rangle\nsim\langle x_{2}\rangle$ imply
$\alpha_{4},\alpha_{5}>\alpha/2$, hence $\alpha_{4}+\alpha_{5}>\alpha$. Again
$\beta_{t}<\beta/2$ and $\langle x_{4}\rangle,\langle x_{5}\rangle\nsim\langle
x_{t}\rangle$ imply $\beta_{4},\beta_{5}>\beta/2$, hence
$\beta_{4}+\beta_{5}>\beta$, which is a contradiction as $\langle
x_{4}\rangle\sim\langle x_{5}\rangle$. Hence Claim 2 holds for all odd $t\geq
5$.

From Claim 1 and 2, we see that for any $i$, both $\alpha_{i},\beta_{i}$ can
not be simultaneously ‘greater or equal’ or ‘lesser or equal’ to $\alpha/2$
and $\beta/2$ respectively. So for any $i$, either
$\alpha_{i}<\alpha/2,\beta_{i}>\beta/2$ or
$\alpha_{i}>\alpha/2,\beta_{i}<\beta/2$ holds. Without loss of generality, let
$\alpha_{1}<\alpha/2,\beta_{1}>\beta/2$.

Now $\langle x_{3}\rangle,\langle x_{4}\rangle\nsim\langle x_{1}\rangle$ imply
$\alpha_{3},\alpha_{4}>\alpha/2$ and hence by Claim 2 we have
$\beta_{3},\beta_{4}<\beta/2$. As $\langle x_{2}\rangle\nsim\langle
x_{4}\rangle$, so $\beta_{2}>\beta/2$ and by Claim 2 we have
$\alpha_{2}<\alpha/2$. Now $\langle x_{2}\rangle\nsim\langle x_{5}\rangle$
implies $\alpha_{5}>\alpha/2$. Then by Claim 2 we have $\beta_{5}<\beta/2$,
but $\beta_{3}<\beta/2$ imply $\beta_{3}+\beta_{5}<\beta$, which is a
contradiction as $\langle x_{3}\rangle\nsim\langle x_{5}\rangle$. Thus
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ has no induced odd cycle of length greater
than $3$. ∎

Thus from Lemma 2.6 and Lemma 2.7, we have if $n={p}^{\alpha}{q}^{\beta}$,
then $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect.

Now, we deal with the last case when $n$ is a prime power.

######  Lemma 2.8.

If $n={p}^{\alpha}$, then $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect.

###### Proof.

In this case, the vertices are $\langle p\rangle,\langle
p^{2}\rangle,\ldots,\langle{p}^{\alpha-1}\rangle$ and two vertices
$\langle{p}^{k}\rangle$ and $\langle{p}^{l}\rangle$ are adjacent if and only
if $k+l\geq\alpha$.

If possible, let
$C:\langle{p}^{k_{1}}\rangle\sim\langle{p}^{k_{2}}\rangle\sim\cdots\sim\langle{p}^{k_{t}}\rangle\sim\langle{p}^{k_{1}}\rangle$
be an induced odd cycle of length $t\geq 5$. Then from adjacency and non-
adjacency conditions, we have the following two sets of relations. Adding
them, we get a contradiction:

$\begin{array}[]{ccc}k_{1}+k_{2}\geq\alpha&{}{}{}{}{}{}{}{}{}{}{}{}\hfil&k_{1}+k_{3}<\alpha\\\
k_{2}+k_{3}\geq\alpha&&k_{2}+k_{4}<\alpha\\\ \vdots&&\vdots\\\
k_{t-1}+k_{t}\geq\alpha&&k_{t-1}+k_{1}<\alpha\\\
k_{t}+k_{1}\geq\alpha&&k_{t}+k_{2}<\alpha\\\ &&\\\ \hline\cr&&\\\
2(k_{1}+k_{2}+\cdots+k_{t})\geq
t\alpha&&2(k_{1}+k_{2}+\cdots+k_{t})<t\alpha\end{array}$

Thus $\mathbb{AG}(\mathbb{Z}_{n})$ has no induced odd cycle $C$ of length
$t\geq 5$. Proceeding similarly, it can be shown that
$\mathbb{AG}^{c}(\mathbb{Z}_{n})$ also has no induced odd cycle of length
$t\geq 5$. Hence $\mathbb{AG}(\mathbb{Z}_{n})$ is perfect. ∎

Combining all the results in this section, we get the proof of Theorem 1.1.

## Acknowledgement

The first and third authors acknowledge the funding of DST-SERB-SRG Sanction
no. $SRG/2019/000475$ and $SRG/2019/000684$, Govt. of India. The second author
is supported by the PhD fellowship of CSIR (File no. 08/155(0086)/2020-EMR-I),
Govt. of India.

## References

  * [1] C. Abdioglu, E.Y. Celikel and A. Das, The Armendariz Graph of a Ring, Discussiones Mathematicae - General Algebra and Applications, Volume 38, Issue 2, pp. 189-196, 2018.
  * [2] D.F. Anderson, M.C. Axtell, J.A. Stickles, Jr., Zero-divisor graphs in commutative rings, Commutative Algebra: Noetherian and Non-Noetherian Perspectives, Springer (2011) 23–45.
  * [3] D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217 (1999) 434–447.
  * [4] A. Badawi, On the Dot Product Graph of a Commutative Ring, Comm. Algebra, 43(1) (2015) 43–50.
  * [5] A. Badawi, On the Annihilator Graph of a Commutative Ring, Comm. Algebra, 42(1) (2014) 108–121.
  * [6] D.F. Anderseon, A. Badawi, The total graph of a commutative ring, J. Algebra 320(7) (2008) 2706–2719.
  * [7] M. Behboodi and Z. Rakeei, The annihilating-ideal graph of commutative rings I, Journal of Algebra and its Applications, Vol. 10(4), pp.727-739, 2011.
  * [8] B. Bose and A. Das, Graph Theoretic Representation of Rings of Continuous Functions, Filomat, Volume 34, Issue 10, pp. 3417-3428, 2020.
  * [9] I. Chakrabarty, S. Ghosh, T. K. Mukherjee and M. K. Sen, Intersection graphs of ideals of rings, Discrete Mathematics 309(17) (2009) 5381-5392.
  * [10] M. Ebrahimi, The character graph of a finite group is perfect, Bulletin of the Australian Mathematical Society, Volume 104, Issue 1, pp. 127-131, 2021.
  * [11] H.R. Maimani, M.R. Pournaki, A. Tehranian, S. Yassemi, Graphs Attached to Rings Revisited, Arab J Sci Eng 36 (2011) 997–1011.
  * [12] R, Nikandish, H.R. Maimani and H. Izanloo, The annihilating-ideal graph of $\mathbb{Z}_{n}$ is weakly perfect, Contributions to Discrete Mathematics, Vol. 11(1), pp. 16-21, 2016.
  * [13] A. Das, On Perfectness of Intersection Graph of Ideals of $\mathbb{Z}_{n}$, Discussiones Mathematicae - General Algebra and Applications, Vol 37(2), pp. 119-126, 2017.


# Hidden Technical Debts for Fair Machine Learning in Financial Services

Chong Huang
FICO AI Research
San Jose, CA 95110
<EMAIL_ADDRESS>
Arash Nourian11footnotemark: 1
FICO AI Research
San Rafael, CA 94903
<EMAIL_ADDRESS>
Kevin Griest
FICO AI Research
San Rafael, CA 94903
<EMAIL_ADDRESS>
Equal contribution

###### Abstract

The recent advancements in machine learning (ML) have demonstrated the
potential for providing a powerful solution to build complex prediction
systems in a short time. However, in highly regulated industries, such as the
financial technology (Fintech), people have raised concerns about the risk of
ML systems discriminating against specific protected groups or individuals. To
address these concerns, researchers have introduced various mathematical
fairness metrics and bias mitigation algorithms. This paper discusses hidden
technical debts and challenges of building fair ML systems in a production
environment for Fintech. We explore various stages that require attention for
fairness in the ML system development and deployment life cycle. To identify
hidden technical debts that exist in building fair ML system for Fintech, we
focus on key pipeline stages including data preparation, model development,
system monitoring and integration in production. Our analysis shows that
enforcing fairness for production-ready ML systems in Fintech requires
specific engineering commitments at different stages of ML system life cycle.
We also propose several initial starting points to mitigate these technical
debts for deploying fair ML systems in production.

##  1 Introduction

Machine learning (ML) systems play an increasingly important role in making
various decisions in financial industry ranging from customer on-boarding for
a loan to detecting fraudulent transactions. These systems utilize a massive
amount of historical data to build complex prediction systems that provide
valuable insights for decision making, thus improve efficiency and reduce
costs. Despite many advantages that ML systems can potentially provide, the
financial technology (Fintech) industry is one of the few industries that has
not fully utilized the latest advancements in this space. One major challenge
for adopting ML systems in Fintech is that it is highly regulated and often
requires careful scrutiny of models used to make high stake decisions. The
lack of explainability in most black-box ML systems brings the potential risk
that the ML based systems may identify patterns that exist because of
inadvertent discrimination and/or exclusionary behavior. Indeed, these
unintended but harmful discriminatory behaviors have been observed in many
such systems (Vigdor, 2019; Bowyer et al., 2020; Dastin, 2018). Recent
advancements in explainable AI and more transparent/self-explaining ML models
have put ML based systems on the forefront of transforming financial industry
(Hagras, 2020). These new advancements have also highlighted challenges around
how to evaluate fairness in the ML systems and mitigate potential unfair
treatments specially in a fast changing production setting – a real concern
for Fintech companies considering whether to put advanced ML systems into
production.

The notion of technical debt is introduced in (Cunningham, 1992) as a metaphor
to describe the costly long-term issues emerged by choosing an expedient
solution in the short-term and has been used to capture potential risk factors
in ML system design (Sculley et al., 2015). In this paper, we argue that there
exists a variety of hidden technical debts and challenges for ML practitioners
to consider when building a production ready fair ML system for Fintech. These
systems not only have all of the traditional issues with respect to mitigating
fairness challenges in ML models but also suffer from Fintech-specific
fairness issues specially in production environment that are often ignored.
These debts may be difficult to detect since they exist at the system level
across the whole life cycle of ML system when pushed in production. Hidden
technical debt is a real concern for ML systems in production because it
accumulates silently and can become extremely expensive to payoff. Our
analysis reveals that typical methods for addressing fairness in ML models may
not be sufficient to solve the challenges at the system level because ML model
is just a small component of the system in production (Figure 1).

Figure 1: Simplified example of ML system in production

ML systems’ discriminatory behavior may be due to a variety of reasons. For
example, some ML systems may give privileges to certain subgroups of the data
due to the characteristics associated with the dataset used for training the
ML system (e.g., too few data samples for a certain subgroup, or biases that
are embedded in the data because of historical policies and decisions). Other
ML systems might have fairness issues due to biases inherited from the
learning algorithm, human intervention during the model development, and
interactions with other components in the deployment process. As a result,
ensuring fairness end-to-end in ML systems is challenging in many aspects.
Discriminatory behavior can creep in not only from ML models but also from
other components in the system such as data collection, data augmentation,
post-model deployment and monitoring etc (Figure 1). All of these components
can contribute to accumulating technical debts that make building fair ML
systems in production costly. Although some of the technical debts can be paid
off by adopting what we introduce as fairness by design which puts fairness at
the core of building ML systems when refactoring code, designing components
for a decision flow, and providing fairness specific tests for production
environments. These techniques may not be applicable to other debts at the ML
system level. Therefore, designing a fair ML system without careful
consideration of the hidden technical debts upfront will bring issues that
accumulate and become costly to address in the long run.

###  1.1 Contributions

The scope of this paper is not focused on offering novel solutions to the fair
ML problem. Instead, we seek to highlight the hidden technical debts for
developing and deploying fair ML systems with fairness by design paradigm in
production and increase the community’s attention to the difficult challenges
that should be considered in large scale production environment over the long-
term. The main contributions of this paper are: 1) identifying hidden
technical debts in building fair ML system at different stages of the life
cycle of ML in production; 2) highlighting challenges for enforcing fair ML
systems in production environment; and 3) proposing fairness by design with
starting points to address the challenges for enforcing fairness in ML systems
used in Fintech industry.

##  2 Data Related Technical Debts

As ML systems rely on data to learn, the input data can influence their
behavior in many ways. A detailed survey of potential biases in data can be
found in (Mehrabi et al., 2019). In this section we mainly focus on technical
challenges and debts related to the data used to build fair ML systems in
Fintech industry.

###  2.1 Mitigate sampling bias

Due to social and historical biases in the related use cases, it is possible
that there exists sampling biases in the datasets collected to train the ML
systems. The sampling bias may impact the ML system in an unpredictable manner
which can result in biased outcome. For example, (Harney, 2018) shows that
loan applications of black applicants are denied at a higher rate in history.
If historical loan application data is used to train the ML system for risk
analysis, the information about whether or not black applicants would have
defaulted had their application been approved may be heavily underrepresented
in the dataset since less black applicants are approved compared to the other
races. Using a dataset which has potential sampling bias to train the ML
system could lead to biased or even sub-optimal decision-making strategies.
Therefore, sampling bias mitigation methods should be designed carefully to
avoid adding technical debt to the system which makes building fair ML systems
more costly. Addressing sampling biases become even more critical when
multiple datasets are used or merged to train the ML system. In the case of a
merged dataset, it is important that the information associated with all the
original datasets used in merging are passed as a metadata in the merged
dataset for further consideration of potential sampling bias.

An ideal but naive approach to mitigating sampling bias is to actively accept
more of the underrepresented population until we have a balanced dataset for
development. However, this is both time-intensive and brings a significant
financial burden to the lender so is infeasible in production. Upsampling can
help balance the number of samples but the diversity of the data is limited.
Reject inference (Banasik and Crook, 2007) is a common technique to address
this issue. Traditional reject inference requires building models on the
dataset to augment the training data by inferring the performance of rejected
samples. While this approach reduces the under-represented bias by modeling
the “through-the-door” population, it can also magnify other biases that are
encoded in the known population’s label. For example, if the accepted black
applicants are more likely to default due to biased decisions such as
predatory loan pricing, an inference model without fairness constraint may
generate estimations that are even less favorable to the black applicant who
has been rejected. Therefore, the inference process should be designed
carefully to eliminate extra biases introduced into the ML system.

###  2.2 Isolate proxy variable

Given the variety of features used for building ML system, it is challenging
to establish that a biased decision outcome is solely driven by “non-
protected” features rather than protected features. In (Ross et al., 2008),
the authors found that minority borrowers were more often encouraged to apply
FHA loans, which are considered to be more expensive to finance. In this
scenario, the loan type information can be considered as a proxy for race and
can carry biased information if not treated properly. These proxy variables
are quite common in real datasets. For example, in the widely used German
Credit dataset (Dua and Graff, 2017), both “Risk” and “Sex” are positively
correlated with the “Housing” feature. If the correlation is strong, “Housing”
becomes a proxy variable for the protected “Sex” feature. Other studies have
raised concerns that income level (Weinberg, 2007) and zip code (Datta et al.,
2017) can be proxy features for gender and race. Unfortunately, it is very
difficult (in some cases almost impossible) to separate the proxy variables’
influence on the target variable with their correlation with protected
features. Including these proxy variables in the dataset to train ML systems
may result in biased decisions, even if the protected features are excluded
explicitly. Therefore it is crucial to investigate the dataset for potential
proxy variables as well as leaking such variables through feedback loops in a
possible retraining process. Including proxy variables without careful
studying of their influence on ML system fairness is a technical debt, which
may be difficult to identify for the ML system in production specially when
the ML system is run as a micro-service interacting with other services or
applications.

Figure 2: Pearson correlation between features for German Credit dataset

###  2.3 Handle missing data

In many real-world application settings, missing data is a common challenge to
tackle for data mining and ML model development (Lin and Tsai, 2020). In
Fintech industry, missing data can be present in a variety of applications
such as credit scoring and fraud detection. In some cases, discarding data
with missing value seems to be a simple solution but may lead to sampling bias
that could violate fairness constraints of the ML system. In many other cases,
missing value imputation (Lin and Tsai, 2020) is used to estimate missing
data. However, many imputation methods are trained based on the dataset and
may introduce extra unpredictable biases to the dataset. For example, using
mean value imputation could potentially shift the distribution of the minority
group closer to the majority group of the dataset. Furthermore, after the
model has been deployed in production, evaluating fairness metrics on data
samples with missing protected feature information (e.g., gender or sex) could
also be challenging for many group fairness metrics (e.g., demographic parity
and equalized odds (Hardt et al., 2016)) which require access to the protected
feature label.

##  3 Fairness Metrics Related Technical Debts

Another area where technical debt can accumulate is the configuration of
metrics for evaluating fairness of ML systems. To investigate whether there
exists discrimination in the output of ML models, numerous fairness metrics
have been introduced to capture fairness via mathematical formulation, such as
equalized odds and equal opportunity (Hardt et al., 2016), positive predictive
value (Chouldechova, 2017), counterfactual fairness (Kusner et al., 2017),
earthmover distance (Dwork et al., 2012), and generalized entropy index
fairness (Speicher et al., 2018). On one hand, these metrics provide a set of
measurements that investigates fairness from different perspectives. On the
other hand, the variety of fairness metrics has introduced new challenges in
determining which metric is the most relevant for different use cases in
Fintech industry.

###  3.1 Lack of consensus among metrics

Interpreting the impact of different fairness metrics is a difficult task
given that many of them are not mathematically compatible for the fairness
definition (Corbett-Davies and Goel, 2018). In the heavily regulated Fintech
industry, it would be challenging to pick the right fairness metrics for the
task at hand and justify the preference of one metric over the others
specially when the production environment could change over time. Furthermore,
due to the various requirements from regulatory bodies, the ML systems are
subject to constant auditing. For regulators and auditors, it is important to
understand the fairness metrics used both in evaluating models and in the
production as well as the relationship between measurements and the compliance
with fair decision regulations. In such scenarios, intuitive and effective
metrics are preferred over complex mathematical formulation. Due to the
complexity of the integrated ML systems in a production setting and the
backward compatibility requirements, changing fairness metrics in production
is expensive. Selecting the most suitable metrics and being able to justify
the metrics and the outcome of the ML system to regulators is another
important step to avoid accumulating technical debt for building fair ML
system. It is also crucial to provide evidence to show that for a specific use
case, no other fairness metric performs better at capturing discrimination of
the ML system without harming the business use case. Furthermore, given the
fact that there exists significant disagreement in people’s perception of
“unfair” treatment, coming up with a consensus metric to capture the
heterogeneity in people’s understanding of discrimination in various use cases
would also be a challenge in enforcing fair ML in production. Therefore,
having consensus on justification of fairness metrics for the specific tasks
by utilizing domain expertise is an important hidden debt that needs to be
considered upfront when designing ML systems.

###  3.2 Fairness-performance trade-off

Strictly enforcing a fairness constraint, which only focuses on the risk of
discrimination for the protected group without considering potential benefits
of the ML systems, may also hurt the overall utility of the ML system. For
example, enforcing complete demographic parity fairness constraint on a ML
model may often cripple the utility of the model Hardt et al. (2016). Given
the dynamic nature of environment change in ML systems pushed in production,
it is very difficult or almost impossible for some cases to completely
eliminate biases while guaranteeing good utility for a decision maker.
However, it is possible to engineer a production friendly ML system that is
reasonably fair and performs well on other objectives for decision making. It
is important to document and acknowledge the potential edge cases such
engineered systems can not handle for auditing purposes.

In reality, a decision maker might have several competing objectives to
consider. Therefore, rather than enforcing fairness as a strict “hard”
constraint (e.g., enforcing demographic parity), it would be beneficial for
the decision maker to view fairness as a “soft” constraint (e.g., setting up a
tolerable threshold for the fairness metrics) and thus shifting the focus from
completely removing bias based on quantified fairness metrics to designing a
ML system that offers the best trade-off between competing objectives. With
such blueprints for measuring fairness in production grade ML systems, setting
up a threshold for specific fairness metrics to determine whether the bias in
the ML system meets the requirements could be a potential widely adopted
solution. However, determining the right metrics and thresholds to answer the
question of “how fair is fair enough?” for different use cases and contexts
will be a difficult task and the choices will have strong influences on the
system behavior in the long term. The accumulated influence of fairness
metrics can create technical debts that are increasingly difficult to address
later in the production environment.

###  3.3 Identifying counterfactual

With the potential biases inherited from data collection, historical
discrimination and human intervention (e.g., manual overrides of decision), it
is not sufficient to evaluate fairness only based on statistical metrics, such
as parity in selection or error rates. It would be beneficial to have a
counterfactual setting to drill down to the root cause of discrimination and
disentangle the correlation between proxy variables for both target and
protected features by modeling the causes and effects via directed acyclic
graph Kusner et al. (2017). Given the complexity of discovering causal
relationship for modern ML models, it would be challenging to implement this
in real-world ML decision systems. Such relationships could constantly change
the causes in an environment with many potential sudden shifts.

###  3.4 Metrics precision vs. cost

For an ML system in production, it is often costly to evaluate various
fairness metrics on large datasets due to computation complexity of the
metrics and the amount of data samples needed for evaluating such metrics. Due
to limited resources in practice, the ML practitioners may have to make a
trade-off between precise fairness evaluation (typically costly evaluation
processes) versus alternative approximations. These approximations are often
not carefully evaluated/tested and could potentially cause serious issues that
could go undetected for a long time. Therefore, simple and yet effective
metrics and evaluation process is of paramount importance for fairness
evaluation on large datasets in production environment. Otherwise, less
precise metrics may be used in production due to cost constraints and they may
not be sufficient to discover discriminatory behaviors completely.
Furthermore, in a production environment, costs associated with fairness
evaluation on inference is also a concern if the metrics used need to be
evaluated on large sample size. Thus, balancing the trade-off between
precision of fairness evaluation and the cost of evaluation can help reducing
hidden technical debt for building fair ML systems in production.

##  4 Production Monitoring Related Technical Debts

Deployed ML systems for decision making often interact directly with the
external world or other applications (e.g., taking a stream of loan
applicants’ data and providing the predicted probability of default). With a
constant changing environment where applications are spawned by various up-
stream/down-stream services or different users, this creates several
challenges and potential technical debts for monitoring fairness guarantees of
the ML system for decision making in production.

###  4.1 Issues related to dynamic nature of production environment

Decision making often requires a decision threshold to predict the applicant
will default or not, to detect whether the voice is from a fraudster, and to
offer or not offer a credit line increase. The canonical approach is to pick a
threshold based on system performance on certain metrics, such as accuracy or
precision. However, the thresholds are often set manually to optimize the
metrics. If a model updates on new data or the distribution of incoming data
in production is different from the data used for model development, the
manually set threshold may not enforce the desired fairness constraint for the
new input. Manually checking and updating the thresholds in the production may
be time consuming and prone to errors. One possible mitigation strategy for
this problem is to use ML techniques such as Reinforcement Learning to adjust
thresholds that achieve a trade-off between fairness and performance metrics
in a dynamic environment. Thus, building the fair ML system without taking the
dynamic environment of the ML system into consideration is another technical
debt that needs special attention.

###  4.2 Monitoring fairness metrics in production

Constant and comprehensive monitoring of ML systems in real-time production
environment is critical for long-term system reliability. One important
question for monitoring fair ML systems is the degree of the monitoring in
production. Unlike ML model development process where test datasets are often
used, test datasets strictly used for fairness evaluations are not always
readily available given that many ML systems in production evolve over time.
Furthermore, the changes in the input data bring extra challenges (e.g.,
evolving consumer behavior may affect ML systems fairness). How to monitor
fairness for dynamically evolving ML systems in production remains a
challenging task but needs to be baked into fair ML system design to avoid
technical debts. We propose the following aspects as starting points and the
key pieces of fairness by design for ML systems:

  * •

Monitoring ML system output bias: the first level of monitoring involves a set
of fairness metrics tests that each model needs to pass based on a holdout
test data and random simulated data. This is by no means a comprehensive test
but it is a useful initial evaluation process to detect unfair systems. Also,
changes in fairness metrics may indicate issues that require attention.
Investigating the disparity of various performances and fairness metrics can
also help detect discriminatory behavior of the system.

  * •

Limiting certain decisions/actions: for an ML system that makes decisions in a
live production environment, such as loan origination, it can be useful to set
and enforce limits on the decisions made on the protected group as a sanity
check. For example, one could limit the rejection rate for the protected
group. If the system hits a limit for the rejection rate threshold set by a
domain expert, automated alert is triggered and the responsible parties
receive a notification for presence of potential bias in the system that needs
further investigation.

  * •

Monitoring changes for input data and data processors: data is often pre-
processed before it is fed to a ML model, it is also useful to monitor the
input features for biases, to make sure that the distribution of values is
relatively stable. It would be beneficial to raise alert if the input
features, various transformations, or data augmentation were to vary
significantly, as this would cause unwanted changed behavior for the ML
system. Also, the data processors used at every step of a ML pipline should be
thoroughly monitored, tested and audited to check for potential biases
introduced for the down-stream ML systems.

##  5 Debiasing Related Technical Debts

To ensure the output of a ML model is fair, a variety of algorithms have been
proposed to mitigate biases in ML systems based on mathematical fairness
metrics. These algorithms enforce fairness constraints at different stages of
ML model development including pre-processing (Zemel et al., 2013; Madras et
al., 2018; Lahoti et al., 2019; Feldman et al., 2015), post-processing (Hardt
et al., 2016), and learning fair model (Zhang et al., 2018; Agarwal et al.,
2018). The diversity of bias mitigation algorithms provides a wide range of
choices for users to mitigate biases in ML systems but also brings several
hidden technical debts for building fair ML system.

###  5.1 Consensus and guideline on bias mitigation algorithms

Given the large pool of bias mitigation algorithms, it is difficult to
determine which algorithm works best for different use cases in production and
justify why one mitigation algorithm is preferred over another without
establishing coherent guidelines to use in the production environment.
Furthermore, for compliance and regulation purposes, explaining the deployed
debiasing techniques to regulators is another important technical debt to
consider when choosing bias mitigation algorithms. As ML system in production
is very costly to modify, it is also crucial to ensure that the bias
mitigation algorithm is compliance friendly and generates required real-time
auditory reports without harming the business use. Introducing a general
guideline for the pros and cons of each bias mitigation algorithm and the
applicable use cases would be a starting point for tackling this issue.

###  5.2 Configuration of bias mitigation algorithms

Another area that may accumulate technical debts is the configuration of the
bias mitigation methods. Each bias mitigation algorithm may have different
configuration options, including which features to use, how data is processed,
and various algorithm specific configuration parameters. It is challenging to
optimize, reason, verify and test the set of configuration variables in a live
system. Moreover, in a production environment, the combination of
configurations of other components and the bias mitigation modules can be very
large and may have accumulated effects on the outcomes while incurring huge
computational cost if not engineered properly. The error prone nature of
manual configuration can be costly and hard to identify, leading to a
significant cost in production environment.

###  5.3 Accounting for adversarial scenarios

Due to the potential disparity in treating different subgroups, malicious
users may take advantage of such disparity in the system to increase the
likelihood of obtaining their favorable outcome (Miller, 2018). Thus, the
correction of biased behavior, either through pre-processing, post-porcessing
or learning fair models, should not incentivize malicious users to game the
system. For instance, if the debiasing algorithm has a higher probability of
offering favorable outcome to a protected group, the process for debiasing
should also prevent the users from extracting potential vulnerabilities to
their benefits. Such debiasing scanning can result in adversarial actions such
as users hiding their actual protected feature (e.g., sex) in exchange for a
favorable outcome. The cost of successfully gaming the system is extremely
expensive and may lead to significant issues in production environment.

###  5.4 Consistent debaising behavior

For ML systems in production, consistency and stability of the system are
important requirements. Thus, for any debiasing algorithm deployed in
production, the output of the ML system after debiasing is expected to perform
consistently over time. Given the randomness and unstable behavior of some of
the bias mitigation algorithms (Lee and Floridi, 2020) and the close
interaction with other components, it might be challenging to obtain strictly
consistent debiased outcome in a dynamic production environment. This may
create various problems for regulatory parties to audit the system and justify
the proper use of these bias mitigation algorithms.

##  6 CI/CD Related Technical Debts

In a production environment, one ML system (i.e., an entire pipeline) could be
a small part of a large ecosystem of pipelines that collaborates together in
delivering a precision decision. The ML system has to be integrated tightly
with other components in the production environment. For example, ML systems
may be connected with up-stream data provider which generates real-time data
streams for prediction and a down-stream rule based decision execution engine
for making the decisions. The close interactions between different subsystems
in the production environment makes the continuous integration and deployment
of fair ML systems an area that hidden technical debt can accumulate.

###  6.1 Integration of multiple fairness evaluation methods in production

Since ML systems in production are not living organisms in isolation and are
typically chained with other components, these systems can be affected by the
behavior of other interacting components. Integrating different components in
the production environment requires supporting code and attached schema to get
data in and out of each component. It is costly in the long run to simply
“glue” different components together (Sculley et al., 2015). Furthermore, in
the production environment, the “glued” components make identifying causes of
biased behavior difficult. Running unit tests works for individual components
but fails to capture the aggregated effects in a heavily integrated system.
Thus, investigating the influence of other components’ on the fairness
properties of ML systems for fairness evaluation is a challenging but required
task. Creating a standard procedure to assess the influence of the changes in
other components on fairness in production as well as designing integration
tests that proactively embed fairness can help reduce technical debt in the
long run.

###  6.2 Integration of bias mitigation in production

For a ML system in production environment, integrating the bias mitigation
algorithms should also take the influence of other integrated components into
consideration. Once the discriminatory behavior has been identified, it is
important to single out the components that contribute to the biased outcomes
and correct their behavior. Multiple reconfiguration, retraining or rebuilding
a model in production is costly, challenging, and may change the behavior of
other components. Modifying the system due to fairness concerns in an
integrated production environment should be carefully investigated to avoid
causing problems for up-stream and down-stream applications.

In a production environment, the bias mitigation module along with other
components in the production environment should be stored in a repository from
which the developed fair ML systems could be restored quickly and seamlessly
in production. Managing, trouble shooting, and recovering these systems are
difficult and costly. Moreover, these accumulated versions of different
components can create more debt due to increasing difficulties to maintain
backward compatibility. Also, testing the system integration often requires
extensive unit tests and expensive end-to-end integration tests.

##  7 Reducing Hidden Technical Debt via Fairness by Design

To reduce potential technical debts for fair ML systems, we propose using
fairness by design paradigm for building production ML systems. At its core,
fairness by design means integrating fairness evaluation and bias mitigation
into the system design, development and deployment life cycle. It shouldn’t be
a simple isolated model fairness analysis or add-on to the existing procedure.
We resort to the following strategies as starting points:

  * •

Build ML systems with fairness baked into the design, development, and
production deployment.

  * •

Carefully monitor and logging data input, such as potential proxy variable as
well as the corresponding meta data.

  * •

Consolidate the metrics, evaluation process, as well as the bias mitigation
algorithm that are appropriate for different use cases and regulations.

  * •

Constantly monitor and alert potential biased behavior of the ML system in a
dynamic production environment.

  * •

Create standard procedures to assess the influence of changes in other
components on fairness in production and design unit/integration tests that
proactively embed fairness.

##  8 Conclusion

In this paper, we highlighted some of the technical debts for building and
deploying fair ML systems in production from the perspective of data, fairness
metrics, debiasing methods, integrating and monitoring such systems in
production. Guaranteeing end-to-end preservation of a fair metric is not a
simple task and requires specific commitments in different stages of ML system
life cycle. Our analysis shows a need for fairness by design approach when
developing and deploying ML with fairness properties in production.

We hope that this paper may serve as an initial endeavor to encourage broader
discussions between academia and industry with respect to developing and
deploying fair ML systems for decision making in Fintech. Developing
theoretical frameworks considering real-world problems has several challenges
such as continuous integration, monitoring and testing discrimination of ML
systems in production. More comprehensive guidelines for choosing fairness
metrics and bias mitigation algorithms are essential for successful deployment
of fair ML systems. Properly treating these technical debts and challenges can
assist Fintech industry to utilize fair ML systems more broadly in real-world
problems.

## References

  * Agarwal et al. [2018] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach.  A reductions approach to fair classification.  _arXiv preprint arXiv:1803.02453_ , 2018.
  * Banasik and Crook [2007] John Banasik and Jonathan Crook.  Reject inference, augmentation, and sample selection.  _European Journal of Operational Research_ , 183(3):1582–1594, 2007.
  * Bowyer et al. [2020] Kevin W Bowyer, Michael King, and Walter Scheirer.  The criminality from face illusion.  _arXiv preprint arXiv:2006.03895_ , 2020.
  * Chouldechova [2017] Alexandra Chouldechova.  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  _Big data_ , 5(2):153–163, 2017.
  * Corbett-Davies and Goel [2018] Sam Corbett-Davies and Sharad Goel.  The measure and mismeasure of fairness: A critical review of fair machine learning.  _arXiv preprint arXiv:1808.00023_ , 2018.
  * Cunningham [1992] Ward Cunningham.  The wycash portfolio management system.  _ACM SIGPLAN OOPS Messenger_ , 4(2):29–30, 1992\.
  * Dastin [2018] Jeffrey Dastin.  Amazon scraps secret ai recruiting tool that showed bias against women.  Available at https://www.reuters.com/article/us-amazon-com-jobs-automation-insight/amazon-scraps-secret-ai-recruiting-tool-that-showed-bias-against-women-idUSKCN1MK08G (2018/10/10), 2018.
  * Datta et al. [2017] Anupam Datta, Matt Fredrikson, Gihyuk Ko, Piotr Mardziel, and Shayak Sen.  Proxy non-discrimination in data-driven systems.  _arXiv preprint arXiv:1707.08120_ , 2017.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Dwork et al. [2012] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , pages 214–226, 2012.
  * Feldman et al. [2015] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.  Certifying and removing disparate impact.  In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 259–268, 2015.
  * Hagras [2020] Hani Hagras.  Banking is on the cusp of an explainable ai revolution.  Available at https://www.finextra.com/blogposting/19292/banking-is-on-the-cusp-of-an-explainable-ai-revolution (2020/09/09), 2020.
  * Hardt et al. [2016] Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  In _Advances in neural information processing systems_ , pages 3315–3323, 2016.
  * Harney [2018] Kenneth R. Harney.  Large numbers of loan applications get denied. but for blacks, hispanics and asians, the rejection rate is even higher.  Available at https://www.washingtonpost.com/realestate/large-numbers-of-loan-applications-get-denied-but-for-blacks-hispanics-and-asians-the-rejection-rate-is-even-higher/2018/05/22/dac19ffc-5d1b-11e8-9ee3-49d6d4814c4c_story.html (2018/05/23), 2018.
  * Kusner et al. [2017] Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva.  Counterfactual fairness.  In _Advances in neural information processing systems_ , pages 4066–4076, 2017.
  * Lahoti et al. [2019] Preethi Lahoti, Krishna P Gummadi, and Gerhard Weikum.  ifair: Learning individually fair data representations for algorithmic decision making.  In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_ , pages 1334–1345. IEEE, 2019.
  * Lee and Floridi [2020] Michelle Seng Ah Lee and Luciano Floridi.  Algorithmic fairness in mortgage lending: from absolute conditions to relational trade-offs.  _Available at SSRN_ , 2020.
  * Lin and Tsai [2020] Wei-Chao Lin and Chih-Fong Tsai.  Missing value imputation: a review and analysis of the literature (2006–2017).  _Artificial Intelligence Review_ , 53(2):1487–1509, 2020.
  * Madras et al. [2018] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel.  Learning adversarially fair and transferable representations.  _arXiv preprint arXiv:1802.06309_ , 2018.
  * Mehrabi et al. [2019] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  _arXiv preprint arXiv:1908.09635_ , 2019.
  * Miller [2018] Zack Miller.  Gaming the system: Loan applicants are reverse engineering the online lending algorithms.  Available at https://tearsheet.co/data/gaming-the-system-online-loan-applicants-are-reverse-engineering-the-algorithms/ (2018/07/11), 2018.
  * Ross et al. [2008] Stephen L Ross, Margery Austin Turner, Erin Godfrey, and Robin R Smith.  Mortgage lending in chicago and los angeles: A paired testing study of the pre-application process.  _Journal of Urban Economics_ , 63(3):902–919, 2008.
  * Sculley et al. [2015] David Sculley, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-Francois Crespo, and Dan Dennison.  Hidden technical debt in machine learning systems.  In _Advances in neural information processing systems_ , pages 2503–2511, 2015.
  * Speicher et al. [2018] Till Speicher, Hoda Heidari, Nina Grgic-Hlaca, Krishna P Gummadi, Adish Singla, Adrian Weller, and Muhammad Bilal Zafar.  A unified approach to quantifying algorithmic unfairness: Measuring individual &group unfairness via inequality indices.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2239–2248, 2018.
  * Vigdor [2019] Neil Vigdor.  Apple card investigated after gender discrimination complaints.  Available at https://www.nytimes.com/2019/11/10/business/Apple-credit-card-investigation.html (2019/11/10), 2019.
  * Weinberg [2007] Daniel H Weinberg.  Earnings by gender: Evidence from census 2000.  _Monthly Lab. Rev._ , 130:26, 2007.
  * Zemel et al. [2013] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork.  Learning fair representations.  In _International Conference on Machine Learning_ , pages 325–333, 2013.
  * Zhang et al. [2018] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell.  Mitigating unwanted biases with adversarial learning.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 335–340, 2018.


11institutetext: Microsoft Research
11email<EMAIL_ADDRESS>

# Look-Up mAI GeMM: Increasing AI GeMMs Performance by Nearly $2.5\times$ via
msGeMM

Saeed Maleki

###### Abstract

AI models are increasing in size and recent advancement in the community has
shown that unlike HPC applications where double precision datatype are
required, lower-precision datatypes such as fp8 or int4 are sufficient to
bring the same model quality both for training and inference. Following these
trends, GPU vendors such as NVIDIA and AMD have added hardware support for
fp16, fp8 and int8 GeMM operations with an exceptional performance via Tensor
Cores. However, this paper proposes a new algorithm called msGeMM which shows
that AI models with low-precision datatypes can run with $\approx 2.5\times$
fewer multiplication and add instructions. Efficient implementation of this
algorithm requires special CUDA cores with the ability to add elements from a
small look-up table at the rate of Tensor Cores.

###### Keywords:

Artificial Intelligence, Machine Learning, ML System, GPU, Matrix-matrix
multiplication, GeMM, Look-up Table

##  1 Introduction

Artificial Intelligent (AI) recent advancements have shown remarkable results
for Large Language Models (LLM) such as GPT-4 [1] or Llama-2 [2]. However,
such models require very large number of parameters to store the weights.
Luckily, recent works have shown that unlike HPC applications with fp64
datatypes, low-precision datatypes such as fp8 [6] or int4 [7] are as
effective as their wider counterparts. This allows to lower the memory
requirement per parameter and have much faster compute capabilities in GPUs.
As the datatypes are getting extremely narrow, interesting alternative
approaches could be utilized to calculate an output of a model.

General Matrix Multiply (GeMM) is the basic operation for any AI model. Model
weights and activation vectors for different input samples (stacked as a
matrix) make up the two matrices for a GeMM operation. We use the following
formulation to represent a GeMM:

$M\times X=Y$ (1)

where the $M$ is a model weight and $X$ is a matrix with each column as an
activation vector. Usually, the model weight matrix is stored in a low-
precision format such as int4 or fp8 and the activation matrix is stored in a
higher precision format such as fp16 or fp32. When a datatype is as small as
an int4, arithmetic operations such as multiplication may no longer need an
actual functional unit in the processor, instead a simple $2^{4}\times 2^{4}$
multiplication table would be sufficient where each row and column would
correspond to one of the $2^{4}$ possible values of each operand. This paper
applies a similar idea to GeMMs with low-precision $M$ and arbitrary precision
$X$ and $Y$. Specifically, we proposes msGeMM (Microsoft GeMM), a new
technique in computing GeMMs with low-precision model weights using look-up
tables such that the number of required arithmetic operations is $2.5\times$
lower than traditional GeMM computation.

##  2 Background

Transformer model architecture [3] is widely used in industry and worked on in
the research community. At the core, most operations in a transformer layer is
a GeMM operation along with some non-linear operations such as layernorm or
ReLU. The focus of this paper is on the GeMM operations as they take the
majority of the end-to-end time.

A GeMM operation in a transformer layer is usually represented by $M\times
X=Y$ where $M$ is the weight matrix, $X$ is the activation matrix (a batch of
different activation vectors stacked as a matrix), and $Y$ is the output
matrix (a batch of outputs stacked as a matrix). The computation of a GeMM is
represented by $m\times k\times b$ where $m$ is the number of rows of $M$ and
$Y$, $k$ is the number of columns of $M$ and the number of rows of $X$, and
$b$ is the batch size which is the number of columns of $X$ and $Y$. As a
running example in this paper, we will consider a GeMM with a computation size
of $12\times 4\times 1$ and later we will generalize it to any GeMM size.
Figure 1 shows $M\times x=y$ for this example111We will use lower-case $x$ and
$y$ for representing vectors and upper-case $X$ and $Y$ for matrices.. Note
that in this figure, all blue elements of $M$ ($\forall i:M(i,0)$) need to
multiply with the blue element of $x$ ($x(0)$), red with red and so on. Since
there are many blue elements of $M$ multiplied by the same blue element of
$x$, one may wonder if the same multiplication is repeated too many times when
$M$ has a low-precision representation.

Figure 1: Multiplication of an MLP matrix $M$ by an activation vector $x$ with
an output vector $y$.

There are many proposed datatypes and precision for both matrix weights and
activation vector including floating points and integers. The key contribution
of this paper is that if either the matrix weights or activation vector has a
low-precision datatype such as a 4-bit representation, the number of required
operations can be significantly reduced. Therefore, for the rest of this
paper, we will assume that the weight matrix is in 4-bit int (int4) and the
activation vector is in any arbitrary datatype. Note that the exact datatypes
and their arithmetic are irrelevant. We could have 8-bit floating point for
weight matrix and 32-bit floating for activation vector and similar
conclusions could be made.

Consider Figure 1 where $M$ has $12$ rows and the datatypes are in int4. Given
that int4 has only $2^{4}=16$ possible values and half of them are negative,
at least there are two rows on the same column that have the same absolute
values. Therefore, $\forall i:M(i,0)\cdot x(0)$, at least two of them are off
by just a sign. This means that some of the multiplications can be avoided by
looking up previously computed values. However, looking up a single
multiplication is not going to help much as a GeMM operation requires both a
multiplication and an addition. Therefore, the key question is whether we can
also have the addition as a part of the look-up.

For now, we assume a GeMM operation is a matrix-vector multiplication
represented by $M\times x=y$ and we will later generalize it later.

##  3 msGeMM Algorithm

msGeMM algorithm takes advantage of the low-precision datatype of matrices in
AI GeMM operations to reduce down on the number of required arithmetic
operations and it works in two phases: (1) producing a look-up table, (2)
consuming the look-up table. Next we will explain each phase separately:

###  3.1 Producing the Look-Up Table

The algorithm has a parameter denoted by $d$ which corresponds to the depth of
accumulation into the look-up table. As a reminder, $M$ matrix is of size
$m\times k$ and $x$ is of size $k\times 1$. Our look-up table $L$ is of size
$\underbrace{2^{4}\times 2^{4}\times\cdots 2^{4}}_{d}\times\frac{k}{d}$ and
defined as follows222We assume $k$ is divisible by $d$ in this paper.:

$\displaystyle\forall p:0000\leq i_{p}\leq 1111,\forall j:0\leq
j<\frac{k}{d}:L(i_{0},i_{1},\cdots,i_{d-1},j)$ (2)
$\displaystyle=\sum_{r=0}^{d-1}b(i_{r})\cdot x(j\cdot d+r)$ (3)

where $b(i)$ is the $i^{th}$ possible value for the datatype of $M$ which in
our example is int4 and therefore, there are $2^{4}$ possible values. One can
think of $b$ as a function from a 4-bit representation to an int4 value:
$b(0000)=0$, $b(0001)=1$, …, $b(0111)=7$, $b(1000)=-8$, …, $b(1111)=-1$.

#### Example

Suppose that $k=4$ as shown in Figure 1 and $d=2$. $L$ has a size of
$2^{4}\times 2^{4}\times 2$. Let’s focus on a 2D block of $L$ by fixing the
last dimension i.e. $\forall i_{0},i_{1}:L(i_{0},i_{1},0)$. Figure 2 shows
this 2D block for $L$. Each element of this table stores the value of
$b(i_{0})\cdot x(0)+b(i_{1})\cdot x(1)$.

Figure 2: A 2D block of the look-up table $L$ for Figure 1 with $d=2$. Note
that $L$ is actually a 3D table and this is only showing a 2D block of it by
fixing the last dimension.

As it can be implied, the computation of this look-up table is dependent on
the activation vector $x$ and effectively, it constructs all possible linear
combinations of $d$ int4s with $d$ consecutive elements of $x$ vector as
coefficients. Therefore, one can use this table to find pre-computed values
for $M\times x$ instead of computing it, specially when $M$ has many more rows
than the number of elements of the look-up table.

###  3.2 Consumer of Look-Up Table

The second phase of the algorithm consists of consuming the look-up table
built in Section 3.1. Let’s consider Figure 1 again and look-up table $L$ with
$d=2$ already computed as shown in Figure 2. Therefore, for every possible
int4 values that may exist on blue and red columns of matrix $M$, we have
already pre-computed the linear combination of them with $x(0)$ and $x(1)$,
the blue and red rows of $x$. Similarly, all linear combination of $x(2)$ and
$x(3)$ is already pre-computed. Therefore, each element of $y$ is simply a
summation of two elements of the look-up table. For example, if assume that
the first row of $M(0,:)=\\{2,4,3,5\\}$, then
$y(0)=L(0010,0100,0)+L(0011,0101,1)$.

This can be extended to any general GeMM formulation as follows:

$\displaystyle y(i)$ $\displaystyle=\sum_{j=0}^{k-1}M(i,j)\cdot
x(j)=\sum_{j=0}^{\frac{k}{d}-1}\sum_{r=0}^{d-1}M(i,j\cdot d+r)\cdot x(j\cdot
d+r)$ (4)
$\displaystyle=\sum_{j=0}^{\frac{k}{d}-1}L\Big{(}\hat{b}\big{(}M(i,j\cdot
d+0)\big{)},\hat{b}\big{(}M(i,j\cdot d+1)\big{)},$ (5)
$\displaystyle\cdots,\hat{b}\big{(}M(i,j\cdot d+d-1)\big{)},j\Big{)}$ (6)

where $\hat{b}$ is the inverse of $b$ described in Section 3.1 i.e. it gives
the 4-bit representation of a given value. For example, $\hat{b}(-1)=1111$.
Equation 4 is straight forward and it is from the naive way of computing a
GeMM. The inner summation looks similar to Equation 3 where $L$ has the pre-
computed all possible linear combination of int4 values with $\forall r:0\leq
r<d:x(j\cdot d+r)$. Therefore, Equation 5 is a direct application of the look-
up table by finding the 4-bit representation of each element of $M$.

It should be clear how the proposed msGeMM algorithm uses the look-up table
instead of computing each element directly. However, one may wonder if this is
ever cost effective given that we have to pre-compute a large look-up table
which will be discussed next.

###  3.3 Datatypes with Shared Scales

Custom datatypes where a block of elements of $M$ share a scale are common in
AI workloads. For example, MSFP12 [8] for matrix $M$, stores all elements in
int4 as the mantissa of a floating point and several elements in a bounding-
box share an 8-bit exponent so that each element has a 12-bit floating point
representation. As an instance, a bounding-box around elements of a row of $M$
means that $\forall i:y(i)=q(i)\cdot\sum_{j}M(i,j)\cdot x(j)$ where $q$ is an
array of a shared exponents for each row of $M$. One can think of $q(i)$s as
any arbitrary scale in floating point as well. Note that this type of scaling
is directly applicable to msGeMM since we can multiply each $y(i)$ by $q(i)$
after consuming $L$. However, the bounding-box could be arranged in a 2D shape
where only a few elements of each row share a scale.

In general, msGeMM is still applicable if $r$ elements of a row of $M$ share a
scale where $r\geq d$ and preferably $r$ is a multiplication of $d$. This is
because the scale factor can be applied after consuming the look-up table.
However, if the bounding-box was, for example, around each column of $M$,
msGeMM would not be applicable. Regardless of msGeMM, this format of bounding-
box is inefficient for the hardware since computing each $y(i)$ would require
$2\cdot k$ multiplications (one extra multiplication for the scale of elements
of $M$) and $k-1$ addition. Luckily, if the bounding-box has multiple elements
of a row, this extra multiplication can be factored out and implementing it
becomes more efficient in the hardware. This also aligns with msGeMM perfectly
as it only requires $d$ elements of each row to share a scale when there is
one. As we will show in Section 5, $d\leq 4$ for practical cases. Therefore,
msGeMM is applicable for when at least $d$ elements of a row share a scale
which we expect to be the case in most scenarios.

##  4 Complexity

In this section, we will calculate the complexity of each phase of the
algorithm. As before, let’s assume that $M$ is of size $m\times k$. Given that
the depth of $L$ is $d$, it has $\underbrace{2^{4}\times 2^{4}\times\cdots
2^{4}}_{d}\times\frac{k}{d}=2^{4\cdot d}\times\frac{k}{d}$ elements as
explained in Section 3.1. Each element of $L$ is a linear combination of $d$
elements which means it costs $d-1$ additions and $d$ multiplications (the
result of the first multiplication does not need an add). Let’s round that up
to $d$ fused multiplication-add operations. Therefore, the computation
complexity of $L$ is:

$C(L)=2^{4\cdot d}\cdot\frac{k}{d}\cdot d=2^{4\cdot d}\cdot k$ (7)

Number of memory access for $L$ is just the access of vector $x$. The 4 bits
for the linear combination of each element is instead constructed as opposed
to a memory access. Therefore, the amount of memory access for $L$ is:

$M(L)=k$ (8)

The complexity of the second phase of the algorithm can be calculated by
considering Equation 5 which requires adding $\frac{k}{d}$ elements from $L$
table to compute a single element of $y$. Considering that $y$ has $m$ rows,
the computation complexity of $y$ by consuming $L$ is:

$C(y)=(\frac{k}{d}-1)\cdot m$ (9)

Note that there is no cost associated with $\hat{b}$ function from Equation 5.
We assumem that $M$ is stored in a row-major format and $d$ consecutive
elements of $M$ in int4 representation can be thought as $d$ concatenated int4
together to form a int4$d$ which can be used directly to dereference the first
$d$ dimension of $L$. Therefore, there is no computation required to indexing
into $L$.

The memory accesses required for the second phase of computation is simply the
number of elements of $M$ which is $m\times k$. We assume that $L$ computed in
phase 1 is kept in cache. If $L$ is too large to be kept in cache, we can
pipeline phase 1 and 2 by partially computing $L$ and fixing the last
dimension. Therefore, the memory access required for the second phase of
msGeMM is:

$M(y)=m\cdot k$ (10)

The total computation and memory access of msGeMM for both phases are:

$\displaystyle C(msGeMM)$ $\displaystyle=C(L)+C(y)=2^{4\cdot d}\cdot
k+(\frac{k}{d}-1)\cdot m$ (11) $\displaystyle M(msGeMM)$
$\displaystyle=M(L)+M(y)=k+m\cdot k$ (12)

Note that a naive GeMM computation requires $(k-1)\cdot m$ fused
multiplication-add operations and $m$ multiplication (the first multiplication
does not need an addition). Let’s round that up to $k\cdot m$ fuse
multiplication add operations333In most modern processors, addition,
multiplication, and fused multiplication-add cost the same.. The memory access
of a naive GeMM computation is $k+m\cdot k$ for each element of $M$ and $x$.
The number of memory accesses of a naive GeMM and msGeMM are identical. The
computation, however, is quite different. For msGeMM, $C(y)$ is nearly $d$
times smaller than the naive GeMM computation. But, $C(L)$ is the obvious
overhead in this algorithm and we need to consider when this overhead is
manageable. The exponential growth rate of $2^{4\cdot d}$ asks for a small $d$
but note that $C(L)$ is independent of $m$, the number of rows of $M$.
Therefore, as $m$ grows, the overhead of $L$ minimizes. The key question is
whether GeMM operations in modern LLMs have large enough $m$ for msGeMM to be
efficient. We will study this in Section 5.

###  4.1 Optimization

There are many obvious optimizations that can be applied to the computation of
the look-up. The most obvious one is utilizing the linear property of linear
combination of elements of $L$: $\sum_{r}q\cdot b(i_{r})\cdot
x(r)=q\cdot(\sum_{r}b(i_{r})\cdot x(r))$ for any $q$. For example, for $q=-1$,
we can almost calculate $L$ for only the non-negative values of $b(i_{0})$.
But this comes with a lot of caveats. For example, he datatype may not allow
negative values (uint4) or even if they do (int4), the reduction in
computational complexity of $L$ is incredibly complicated. For example, int4
has $8$ negative values, $7$ positive values and a $0$ and computing with only
non-negative values of $b(i_{0})$ is not enough. Other datatypes such as fp8
has special set of bits reserved for inf or nan and etc which would be hard to
capture all of them for optimizing $L$. Therefore, we consider $L$ for general
cases.

###  4.2 Generalization

From the beginning, we assumed that $x$ is an activation vector which
corresponds to a batch size of $1$. In general, GeMM operations in AI
workloads run with larger batch sizes. Luckily, all of the computational
complexity calculated in this section scales linearly with the batch size and
the relative benefit of msGeMM over naive GeMM computation remain unchanged.
For the memory access, both naive GeMM and msGeMM will have $k\cdot b+m\cdot
k$ accesses and they will stay identical. Therefore, for the rest of this
paper, we assume that the cost of the GeMM of size $m\times k\times b$ is

$\displaystyle C(msGeMM)$ $\displaystyle=\Big{(}2^{4\cdot d}\cdot
k+(\frac{k}{d}-1)\cdot m\Big{)}\cdot b$ (13) $\displaystyle C(GeMM)$
$\displaystyle=m\cdot k\cdot b$ (14)

##  5 Theoretical Evaluation

In this section, we will compare the cost of msGeMM against the cost of naive
GeMM computation and evaluate when msGeMM has an advantage for AI GeMM
operations.

The speedup of msGeMM over naive GeMM can be calculate using Equation 14 in
Section 4.2:

$\displaystyle\frac{C(GeMM)}{C(msGeMM)}=\frac{m\cdot k\cdot
b}{\Big{(}2^{4\cdot d}\cdot k+(\frac{k}{d}-1)\cdot m\Big{)}\cdot
b}=\frac{m\cdot k}{2^{4\cdot d}\cdot k+(\frac{k}{d}-1)\cdot m}$ (15)

Now, let’s pick some real-world GeMM operations from AI workloads. GPT-3 [4]
models architecture consists of two GeMM operations from the MLP module of the
transformer layers, $MLP_{1}$ and $MLP_{2}$, which are of size $12288\times
49152\times b$ and $49152\times 12288\times b$. Therefore, the speedup number
for a given $d$ would be:

$\displaystyle speedup(MLP_{1})$ $\displaystyle=\frac{m\cdot k}{2^{4\cdot
d}\cdot k+(\frac{k}{d}-1)\cdot m}$ (16) $\displaystyle=\frac{12288\times
49152}{2^{4\cdot d}\cdot 49152+(\frac{49152}{d}-1)\cdot 12288}$ (17)
$\displaystyle=\frac{49152}{2^{4\cdot d}\cdot 4+(\frac{49152}{d}-1)}$ (18)
$\displaystyle speedup(MLP_{2})$ $\displaystyle=\frac{m\cdot k}{2^{4\cdot
d}\cdot k+(\frac{k}{d}-1)\cdot m}$ (19) $\displaystyle=\frac{49152\times
12288}{2^{4\cdot d}\cdot 12288+(\frac{12288}{d}-1)\cdot 49152}$ (20)
$\displaystyle=\frac{49152}{2^{4\cdot d}+(\frac{12288}{d}-1)\cdot 4}$ (21)

$0$$0.5$$1$$1.5$$2$$2.5$$1$$2$$3$$4$$5$$6$$7$$8$

Speedup

d$MLP_{1}=12K\times 48K\times b$$MLP_{2}=48K\times 12K\times b$Speedup of
2-phase algorithm over normal GeMM calculation Figure 3: Comparing the
performance of the 2-phase algorithm against the naive computation of GeMM.

Figure 3 shows the speedup of the proposed algorithm for varying $d$, the
depth of the look-up table. Because of the exponential cost growth of $L$, $d$
cannot be larger than $4$. However, a value of $3$ shows a sweet-spot of
$\approx 2.5\times$ speedup for msGeMM for both MLP GeMM operations. Another
observation in this plot is that the larger the number of rows ($m$) the
better this algorithm works and that is because the cost the look-up table is
independent of $m$.

##  6 Implementation: Proposal for Next-Gen GPUs

GPUs are the common backend target for running GeMM computation and they have
been heavily optimized for naive GeMM computation by utilizing Tensor Cores
[5]. A100 GPUs have an impressive 312 TFLOPS for fp16 GeMMs with Tensor Cores.
However, the CUDA cores of A100s (normal computational cores) are limited to
19.5 TFLOPS. This means that the naive GeMM computation can run at 312 TFLOPS.
Similarly, the first phase of msGeMM can run at 312 TFLOPs. However, the
second phase of this algorithm requires adding elements of the the look-up
table where Tensor Cores cannot be utilized. Therefore, the second phase
limited to 19.5 TFLOPS. This is a limiting factor of current GPUs which do not
allow msGeMM to be implemented efficiently.

This shortcoming can be addressed by adding special CUDA cores in GPUs which
allow for adding elements of a look-up table with a similar performance of
Tensor Cores.

##  7 Conclusion

This paper proposes msGeMM which utilizes the low-precision property of GeMM
operation in AI workloads to reduce down the total required number of
multiplication and add. We show that by using a look-up table with depth of
$3$, modern AI GeMMs can be heavily optimized by $\approx 2.5\times$. However,
this type of optimization requires special support from the hardware which
current generation of GPUs do not have.

## References

  * [1] GPT-4, https://openai.com/research/gpt-4
  * [2] Introducing Llama 2, https://ai.meta.com/llama/
  * [3] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention Is All You Need,” CoRR, vol. abs/1706.03762, 2017. [Online]. Available: http://arxiv.org/abs/1706.03762
  * [4] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared 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 M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. _Language Models are Few-Shot Learners_. CoRR, abs/2005.14165, 2020. [Online]. Available: https://arxiv.org/abs/2005.14165
  * [5] NVIDIA Tensor Cores, Unprecedented Acceleration for HPC and AI, https://www.nvidia.com/en-us/data-center/tensor-cores/
  * [6] M. van Baalen, A. Kuzmin, S. S. Nair, Y. Ren, E. Mahurin, C. Patel, S. Subramanian, S. Lee, M. Nagel, J. Soriaga, T. Blankevoort, _FP8 versus INT8 for efficient deep learning inference_ , arXiv preprint arXiv:2303.17951, 2023.
  * [7] X. Wu, C. Li, R. Y. Aminabadi, Z. Yao, Y. He, _Understanding INT4 Quantization for Transformer Models: Latency Speedup, Composability, and Failure Cases_ , arXiv preprint arXiv:2301.12017, 2023.
  * [8] Darvish Rouhani, B., Lo, D., Zhao, R., Liu, M., Fowers, J., Ovtcharov, K., … & Burger, D. (2020).  Pushing the Limits of Narrow Precision Inferencing at Cloud Scale with Microsoft Floating Point.  In Advances in Neural Information Processing Systems (Vol. 33, pp. 10271-10281). Curran Associates, Inc.  [Online].