# LUT-NN: Towards Unified Neural Network Inference by Table Lookup

Xiaohu Tang  Microsoft Research  Zhejiang University  Yang Wang  Microsoft
Research  Ting Cao  Microsoft Research  Li Lyna Zhang  Microsoft Research  Qi
Chen  Microsoft Research  Deng Cai  Zhejiang University  Yunxin Liu  Institute
for AI Industry Research (AIR), Tsinghua University  Mao Yang  Microsoft
Research

###### Abstract

DNN inference requires huge effort of system development and resource cost.
This drives us to propose LUT-NN, the first trial towards empowering deep
neural network (DNN) inference by table lookup, to eliminate the diverse
computation kernels as well as save running cost. Based on the feature
similarity of each layer, LUT-NN can learn the typical features, named
centroids, of each layer from the training data, precompute them with model
weights, and save the results in tables. For future input, the results of the
closest centroids with the input features can be directly read from the table,
as the approximation of layer output.

We propose the novel centroid learning technique for DNN, which enables
centroid learning through backpropagation, and adapts three levels of
approximation to minimize the model loss. By this technique, LUT-NN achieves
comparable accuracy (<5% difference) with original models on real complex
dataset, including CIFAR, ImageNet, and GLUE. LUT-NN simplifies the computing
operators to only two: closest centroid search and table lookup. We implement
them for Intel and ARM CPUs. The model size is reduced by up to $3.5\times$
for CNN models and $7\times$ for BERT. Latency-wise, the real speedup of LUT-
NN is up to $7\times$ for BERT and $2\times$ for ResNet, much lower than
theoretical results because of the current unfriendly hardware design for
table lookup. We expect first-class table lookup support in the future to
unleash the potential of LUT-NN.

††* Corresponding author††** Contribution during internship at Microsoft
Research

##  1 Introduction

Current DNN inference faces two critical issues. Firstly, the development of
inference software (e.g., ONNX Runtime [35], TensorFlow [14], and TVM [6]) and
hardware (e.g., Google TPU [26], Alibaba HanGuang [25], and Intel Spring Hill
[41]) takes huge efforts and often lags behind DNN innovation. Computing
operators are optimized for different operator sizes, types, algorithms, and
backends. To take convolution as an example, an inference system normally has
to support direct, Winograd, im2col, depthwise, and group convolution for CPU,
CUDA, OpenCL, WebAssembly, etc. Hardware wise, inference accelerators tend to
be customized for different computing operators. For example, the ones
designed for convolution, such as HanGuang, cannot well support a NLP model.
Secondly, inference consumes more and more computation and storage resources,
as models get larger (e.g. ResNet-50 [18] 98 M, BERTLARGE [11] 340 M, GPT-2
[37] 1.5 B).

These issues drive us to ask is it possible to eliminate these computing
operators for inference. If so, the development of inference systems can be
much simplified, accelerated, and decoupled with the rapid DNN algorithm
evolution. A new model could be directly deployed after training. Besides,
computation resources can be saved.

To explore the possibility, we rethink the essence of DNN inference. The
computation of each DNN layer is to output another level of features given the
input features. For example, the front layers of a CNN model output low-level
features (e.g., edges and lines), and subsequent layers output high-level
features (e.g., faces and objects). Though the input images for a model are
diverse, the input features for each layer have semantic similarity, and
result in similar outputs. A vivid example is that though cats and horses are
different inputs for a model, the output of the ear feature could be similar
for the layer that extracts it. Same for language tasks, similar words of
different sentences should have similar embeddings and output results.

Because of the similarity, the research question of this work is that whether
the typical features among clusters of similar features can be learned for
each layer, so that the computation output of these typical features can
approximate the output of diverse input features, and achieve similar model
accuracy.

Towards answering this question, we propose LUT-NN. The system learns the
typical features, named _centroid_ , for each layer, and precompute the
results for these features to save in lookup tables. During inference, the
results of the closest centroids with the input features can be read directly
from the table as the output of this layer. Fig. 1 shows an overview of LUT-NN
using real data samples of a model. LUT-NN is the first to empower end-to-end
DNN inference by table lookup. It achieves comparable accuracy with the
original models on real and complex datasets and tasks, including CIFAR [29]
and ImageNet [10] for image tasks, and GLUE [39] for language tasks.

The major challenges for LUT-NN is how to learn the centroids for minimum
accuracy loss. MADDNESS [4] initiates the works towards learning centroids for
matrix multiplication (MM), leveraging the technique of Product Quantization
(PQ). PQ is an effective vector quantization algorithm widely used for dataset
compression [24, 16]. It clusters the vectors in the dataset, and learns the
centroids to represent vectors in each cluster. By using PQ, MADDNESS learns
the centroids from the training dataset, and precomputes the MM results for
the centroids, as the approximation for future input matrices.

However, as we will show in the paper, directly applying MADDNESS to the
computation layers of a DNN model results in poor accuracy (80% accuracy drops
for CIFAR-10). A similar conclusion is also from McCarter et al. [33].

Inspired by this, we first analyze and expose the key factor for DNN centroid
learning compared to a MM. We find the main reason for the poor result of
MADDNESS for DNN is that the different optimization goal of centroid learning
for PQ and DNN. The goal of PQ is to learn the centroids that can minimize the
total error/distance between centroids and vectors, while the goal of DNN is
to minimize the final loss function. Without considering the loss function,
errors introduced by centroids in MADDNESS are accumulated layer by layer,
resulting in poor accuracy.

Figure 1: LUT-NN transforms model linear-computation layers to table lookup
for inference.

Therefore, the key for DNN centroid learning is to pass the model loss to each
layer through backpropagation and iteratively adjust the centroids by the
gradients to minimize the loss. However, it is not possible for PQ since the
function to encode a vector to the closest centroid e.g., `argmin` or hashing
in MADDNESS, is not differentiable.

To solve this, we propose the novel LUT-NN centroid learning technique for
DNN. It adapts three levels of approximation by three methods through
backpropagation, to minimize the model loss. First, to adapt the approximation
introduced by centroids, LUT-NN uses _soft-PQ_ method. It uses the continuous
approximation of `argmax`, i.e., `softmax`, for backward pass, to enable
gradient calculation and centroid update. The forward pass still uses `argmin`
for model loss calculation, since `argmin` will be used for inference. Second,
to adapt the approximation introduced by `softmax`, LUT-NN uses _learned
temperature_ method, to learn the hyperparameter `temperature` of `softmax`
for each layer during backpropagation, as the tradeoff of model loss reduction
and learning convergence. Third, to reduce memory cost, LUT-NN reduces the
size of lookup tables by scalar quantization. To adapt the approximation
introduced by this quantization, LUT-NN uses _quantization-aware training_ ,
which uses quantized tables in the forward pass and real-value tables in the
backward pass.

Empowered by this centroid learning technique, LUT-NN can reduce DNN
computations to table lookup, and unify the diverse computation kernels to
only two, i.e., _closest centroid search_ and _table lookup_. It can greatly
simplify the inference software and hardware design.

LUT-NN is best fit for the system taking table lookup as the first class, but
current systems are all designed for complex computations. Even though, we
still implement the two kernels of LUT-NN by a tensor compiler, on commodity
Intel and ARM CPUs. Our design carefully aligns the number of centroids and
feature length with the width of SIMD instructions. We properly order the loop
to improve cache locality of dist calculation and fuse it with `argmin` to
reduce memory accesses. Even with all these optimizations, the implementation
is still hard to unleash the potential of LUT-NN. For example, the `argmin`
has to be mostly sequentially executed. The configurations of centroids are
limited by SIMD width. Hashing cannot accelerate centroid search compared with
distance calculation.

Based on current implementation, LUT-NN achieves comparable accuracy, i.e.,
within 5% difference, for CIFAR, ImageNet, and GLUE, with reduced model size
(in FP32) by $2.3$~$3.5\times$ for CNN ResNet models, and $7\times$ for BERT,
since it only needs to save centroid results. We also count the theoretical
FLOPs of LUT-NN by using distance calculation compared to MM. The FLOPs for
CNN can be reduced by $2$~$4\times$, and $16\times$ for BERT. The real speedup
is less than this, due to the issues above. The speedup for BERT is up-to
$5.4\times$ compared to current inference systems. The speedup for larger
ResNet, e.g., ResNet-18 for ImageNet, can achieve $2\times$. However, for
smaller ones, e.g., ResNet-20 for CIFAR, LUT-NN can even be slower than the
baseline.

We will discuss the hardware implications of LUT-NN in the paper. With first-
class table lookup and hashing support, LUT-NN is expected to approach even
higher theoretical speedup.

To sum up, the key contributions of this paper are as follows.

  * •

LUT-NN is the first to empower DNN inference by table lookup to simplify
inference systems and save cost.

  * •

It can achieve comparable model accuracy by the novel centroid learning
technique for DNN, which can adjust approximation through backpropagation to
reduce model loss.

  * •

It automatically generates kernels for table lookups to enable this new
inference paradigm on commodity CPUs.

  * •

We implement the whole learning and inference pipelines. Results show up-to
$5.4\times$ speedup and $7\times$ model size reduction for BERT, and $2\times$
speedup and $3.5\times$ model size reduction for ResNet.

##  2 Background and Motivation

Each data sample in the training set can be assumed as a vector. This section
will first introduce the concept of vector quantization and its efficient
solution, PQ, and then show the poor results of directly applying PQ to DNN
inference.

###  2.1 Product Quantization

Quantization has been well studied in information theory [15]. It reduces the
cardinality of a dataset by using _centroids_ to represent the data samples.
The set of centroids is called a _codebook_. For vector quantization, the
dataset is composed of $D$-dimension vectors. The vector quantizer can encode
each vector to a centroid in the codebook. However, the complexity of learning
and storing the centroids increases exponentially with the vector dimension.

As a result, PQ is proposed to address this complexity issue. The essence of
it is to decompose the high-dimensional vector space into the Cartesian
product of sub-vector spaces and then quantize these sub-vector spaces
separately. As shown in Fig. 2(a), it splits the $D$-dimension vector into $C$
distinct $V$-dimension sub-vectors ($D=C\cdot V$). The sub-vectors are
quantized separately using $C$ codebooks. The quantization result of the
vector is the concatenation of the $C$ centroids. By PQ, the complexity of
learning and storing the centroids increases linearly with the vector
dimension.

Centroid learning We now formulize the PQ process. To quantize a $D$-dimension
vector $a\in\mathbb{R}^{D}$, PQ needs to learn the centroids from a training
dataset $\hat{A}\in\mathbb{R}^{\hat{N}\times D}$ composed of vectors with the
same distribution as $a$. PQ first decomposes the vectors in the dataset into
$C$ distinct $V$-dimension sub-vectors, notated as
$\hat{A}^{c}\in\mathbb{R}^{\hat{N}\times V}$ (marked in different colors in
Fig. 2). To make optimal quantization, the centroid learning process is to
find the $K$ centroids $P^{c}$ (i.e., the $c^{th}$ codebook) for $\hat{A}^{c}$
by $k$-means [30], which can minimize the distance sum of each sub-vector
$\hat{A}^{c}_{i}$ and its nearest centroid $P^{c}_{k}$, as shown in Eq. 1.

$\underset{P}{\mathrm{arg\
min}}\sum_{c}\sum_{i}\left\|\hat{A}^{c}_{i}-P^{c}_{k}\right\|^{2}$ (1)

Sub-vector encoding With the learned centroids $P$, for an input vector $a$,
PQ can encode it as the concatenation of the nearest centroids for each sub-
vector. The encoding function for a sub-vector is shown in Eq. 2. By this
vector decomposition method, the centroids can represent $K^{C}$ different
vectors by only $K\times C$ memory cost.

$g^{c}(a^{c})=\underset{k}{\mathrm{arg\
min}}\left\|a^{c}-P^{c}_{k}\right\|^{2}$ (2)

Hashing for encoding acceleration Learning centroids is a NP-hard problem.
Vanilla PQ uses $k$-means to learn centroids and encode sub-vectors. $k$-means
satisfies Lloyd optimality conditions [30, 24] and can get locally optimal
quantization error. However, the $k$-means encoding costs high to compute the
Euclidean distance for each sub-vector with each centroid, as shown in Eq. 2.

To reduce the encoding cost, some works propose hashing methods to encode sub-
vectors [4, 17], but at the cost of higher quantization error. Hashing hashes
a sub-vector to one of the $K$ buckets. For example, MADDNESS selects a
4-level balanced binary regression tree of the hashing function family, with
each leaf as a hash bucket. A sub-vector is encoded by traversing the tree
from the root, and moving to left or right child if the value of certain
indices is above or below a threshold.

This paper will evaluate both distance-based encoding and hashing-based
encoding methods.

Figure 2: Product Quantization for AMM. Each color marks a sub-vector dataset.

###  2.2 PQ for AMM

PQ can be used for AMM (approximated matrix multiplication) [4]. The essence
is to approximate the matrix multiplication by the centroids’ multiplication.

To formulize it, for matrix multiplication $A\times B^{T}$, $a$ and $b$ are
the rows of $A$ and $B$ respectively. The centroid codebooks for $A$ is $P$.
For a layer of DNN, $A$ can be the input feature maps, and $B$ can be the
weights (note that convolution can be computed as matrix multiplication too).
Since $B$ is constant, the multiplication of all the centroids and $B$ can be
precomputed to construct a lookup table, as shown in Fig. 2(b). The table
construction function for $b^{c}$ is shown in Eq. 3.

$\begin{split}h^{c}(b^{c})=[P_{0}^{c}\cdot b^{c},P_{1}^{c}\cdot
b^{c},\cdots,P_{K-1}^{c}\cdot b^{c}]\end{split}$ (3)

The matrix multiplication can then be approximated by looking up and
aggregating the results of the nearest centroids in the precompute table,
formulated in Eq. 4. Here considers the $g^{c}(a^{c})$ function with $onehot$
representation for $argmin$, i.e., the nearest centroid is marked as 1 and
others as 0, $g^{c}(a^{c})=onehot(\underset{k}{\mathrm{arg\
min}}\left\|a^{c}-P^{c}_{k}\right\|^{2})=(0,...,0,1,0,...,0)$.

$a\cdot b=\sum_{c}{a^{c}}b^{c}\approx\sum_{c}{g^{c}(a^{c})}\cdot h^{c}(b^{c})$
(4)

###  2.3 Poor results of PQ for DNN

Since DNN models are composed of MM, a direct thought is that can we replace
MM in a DNN model by the PQ-based AMM. However, results show that directly
applying it to a DNN model leads to poor accuracy.

Fig. 3 shows the accuracy of using PQ-based AMM for ResNet-20 on CIFAR-10, as
well as the Mean Square Error (MSE) of the replaced model and the original
model. We replace the MM from the last to the first layer by PQ-based AMM.
Fig. 3a uses vanilla PQ with $k$-means for encoding, while Fig. 3b uses
MADDNESS with hashing for encoding.

Results show the accuracy keeps dropping while more layers are replaced by
AMM, because the error of the AMMs is accumulated. As expected, vanilla PQ
shows better results than MADDNESS, since $k$-means introduces smaller
quantization error than hashing. MADDNESS can maintain accuracy when only the
last layer is replaced. This is consistent with the MADDNESS paper, which only
replaces the last layer, i.e., fully-connect, by AMM. However, if we replace
the last two layers, the accuracy sharply drops by 30%, and finally ends in
10% accuracy. Vanilla PQ drops by 30% when the last six layers are replaced,
and also ends in 10% accuracy.

(a)

(b)

Figure 3:  Model accuracy keeps decreasing because MSE keeps increasing, while
each MM (from the last to the first) is replaced by PQ-based AMM, for ResNet20
on CIFAR-10. Encoding uses (a) $k$-means from vanilla PQ and (b) hashing from
MADDNESS. MSE is computed as MSE(replaced model, original model).

Reason for poor accuracy We expose the key reason for the poor model accuracy
of using PQ-based AMM is that _the optimization goal of PQ and DNN learning is
different_. As shown in Eq. 1, the goal of PQ is to minimize quantization
error, i.e., learn the centroids to minimize the distance of each sub-vector
and its nearest centroid. On the other hand, the learning goal of DNN is to
minimize the final loss function, through backpropagation to iteratively
adjust the model parameters of each layer. Without considering the loss
function, when more layers use AMM, the approximation error gets accumulated,
as shown in Fig. 3. To get better accuracy, it is necessary to learn the
centroids by the DNN training process.

However, the challenge is that PQ centroid learning and encoding functions
shown in Eqs. 1 and 2 are not differentiable, and cannot use backpropagation
to calculate gradient. This paper thus proposes the soft-PQ technique, which
empowers the centroid learning for a DNN by backpropagation and gradient
descent.

##  3 Differentiable Centroid Learning for DNN

It is essential to learn the centroids of each layer through backpropagation
to minimize the model loss. However, the `argmin` function in vanilla PQ is
not differentiable. Our key technique is to leverage the continuous and
differentiable approximation to `argmax` function, `softmax`, for
backpropagation [23], which approximates the $onehot$ centroid result as the
weighted sum of all centroid results (Sec. 3.1). There is work before using
`softmax` for differentiable PQ, but again only for the input embedding
compression [7].

The challenge for approximating `argmin` by `softmax` for every layer of a
model is again the accumulated approximation error and reduced model accuracy.
Since the hyperparameter of `softmax`, `temperature`, adjusts the
approximation error with `argmin`, we propose learnable temperature to learn
the temperature of each layer’s `softmax` through backpropagation (Sec. 3.2).

To reduce the memory and table lookup cost, we propose scalar-quantized lookup
tables. However, this again introduces a level of approximation. Similarly, we
quantize the lookup tables during centroid learning (Sec. 3.3).

The two major factors of LUT-NN are the number of centroids and the length of
sub-vectors, which are a tradeoff between cost and accuracy. We theoretically
analyze the FLOPs and disk cost of LUT-NN with the two factors (Sec. 3.4).
Since hashing can speed up encoding but at the cost of higher quantization
error, we also explore the potential of hashing for LUT-NN (Sec. 3.5).

Figure 4:  Soft PQ learns centroids by backpropagation. The forward pass uses
$\mathrm{argmin}$ as the encoding function, and backward uses
$\mathrm{softmax}$. Each color marks a sub-vector dataset using one codebook.
$P^{c}_{k}$ is the $k^{th}$ centroid for sub-vector $a^{c}$.

###  3.1 Backpropagation through soft-PQ

As introduced in Sec. 2.1, vanilla PQ uses $k$-means to learn centroids from
the dataset, and the encoding function $g^{c}(a^{c})$ uses `argmin` to encode
a sub-vector as the nearest centroid, e.g., the `onehot` representation
$(0,...,1,...,0)$ shown in Fig. 4. The sub-vector AMM result can then be read
directly from the lookup table by $g^{c}(a^{c})\cdot h^{c}(a^{c})$.

However, to apply PQ to the whole DNN model and minimize the model loss, the
centroids for each layer are required to be learned from backpropagation and
gradient descent. We therefore use the smooth `argmax` function, `softmax`, as
the encoding function for backpropagation, shown in Eq. 5. $t$ is the
`temperature` hyperparameter, which will be discussed in Sec. 3.2.

$\tilde{g}^{c}(a^{c})=\mathrm{softmax}(-\left\|a^{c}-P^{c}_{k}\right\|^{2}/\
t)$ (5)

For the $K$ centroids in a codebook, `softmax` takes a vector of $K$ distance
results between sub-vector $a^{c}$ and each centroid $P^{c}_{k}$ as the input,
and normalizes the input to the probability distribution adding up to 1.
According to the definition of `softmax`, each probability is proportional to
the exponent of the distance, i.e.,
$exp({-\left\|a^{c}-P^{c}_{k}\right\|^{2}}/{t})$. The nearer the centroid is,
the higher the probability is. The encoding for a sub-vector is then changed
from a deterministic `onehot` vector into the probability vector. Illustrated
in Fig. 4 for example, the `softmax` encoding function output is
$(0.12,...,0.64,...)$, and 0.64 is the probability of the nearest centroid.
The sub-vector AMM result is now the dot product of the probability vector and
the table entries of the lookup table.

Soft-PQ centroid learning By using `softmax`, the centroid learning process of
our soft-PQ for the whole model is shown in Fig. 4. In the forward pass,
onehot `argmin` is the encoding function to calculate the model output and
loss, since the model inference will also use `argmin` for execution
simplicity. The backward pass uses `softmax` as the encoding function to
calculate gradients, adjust centroids by gradient descent, and rebuild lookup
tables with the adjusted centroids for the next training iteration. Based on
Eq. 4, the sub-vector AMM in soft-PQ is formulated as Eq. 6.

$a^{c}b^{c}=\tilde{g}^{c}(a^{c})\cdot
h^{c}(b^{c})-\mathrm{sg}(\tilde{g}^{c}(a^{c})\cdot
h^{c}(b^{c})-g^{c}(a^{c})\cdot h^{c}(b^{c}))$ (6)

Here $sg$ is the _stop gradient_ operator. It is an identity function in the
forward pass, to enable $g^{c}(a^{c})$ encoding in `argmin`. It drops gradient
inside it in the backward pass, to enable $\tilde{g}^{c}(a^{c})$ to generate
gradients by `softmax`.

As the initial value is critical for learning convergence and accuracy, we use
the $k$-means learned centroids from vanilla PQ to initialize centroids and
lookup tables.

###  3.2 Learned temperature

The `temperature` hyperparameter $t$ of `softmax` [20] controls the
approximation error of `softmax` to `argmax`. Shown in Fig. 5a, as
$softmax(x)_{i}=\frac{exp(x_{i}/t)}{\sum_{k=1}^{K}exp(x_{k}/t)}$, when
$t\rightarrow\infty$, $softmax(x)_{i}\rightarrow\frac{1}{K}$, i.e., the output
probability distribution approaches uniform distribution. When $t\rightarrow
0$, $softmax(x)\rightarrow onehot(argmax(x))$, i.e., the probability of the
largest $x$ approaches 1 and others are 0.

Therefore, there is a tradeoff between small and large temperature. For small
temperature, `softmax` is close to `onehot` `argmax`, but the training is
difficult since the variance of gradients is large. For larger temperature,
the approximation error is increased, but the variance of gradients is
smaller.

Works before normally set $t$ as a fixed value (mostly 1), or anneal it from a
large number to a small one during training [20, 23], but never analyze how to
set it reasonably. This is because currently for a DNN model, `softmax` is
only used by the output layer to produce class probability, or used by the
input layer to produce symbol embedding. The approximation error barely
impacts the DNN model accuracy. However, our soft-PQ for DNN employs `softmax`
in every layer. The accumulated error can obviously decrease accuracy without
proper $t$ settings.

We thus propose to learn the temperature for each layer, also during
backpropagation while centroid learning. Fig. 5b shows the learned $t$ for
each layer for ResNet18. The value for each layer is different, and thus not
practical to tune by hand. According to the CIFAR10 accuracy experiments,
training with the learned temperature technique only spends $\frac{1}{10}$
iterations of training with temperature setting to 1 to achieve 85% accuracy.
Detailed results will show in Sec. 6.

(a)

(b)

Figure 5:  (a) The output probability distribution of
$\mathrm{softmax}(\frac{x}{t})$ at different temperature, for four centroids
as an example. $t\rightarrow\infty$ approaches uniform distribution, and
$t\rightarrow 0$ approaches $\mathrm{argmax}$. (b) The learned $t$ for each
layer of ResNet18.

###  3.3 Scalar quantized lookup table

Lookup tables are the main disk and memory cost. We reduce the table size by
scalar quantization (e.g., FP32 to INT8). We leverage the classic range-based
linear quantization. The formula is $r=s(q-z)$ [21], in which $r$ is the real
value, $s$ is the scaling factor, $q$ is the quantized value, and $z$ is the
zero point. We use symmetric quantization, so $z$ is forced to be 0, and the
quantized range is $[-2^{n-1},2^{n-1}-1]$. The scaling factor $s$ is
calculated as the max absolute value in the table divided by half of the
range, i.e., $s=\frac{\text{max(|value|)}}{2^{n-1}-1}$.

Quantized lookup tables introduce another level of approximation. Similar to
`temperature`, we thus quantize the tables during centroid learning, to
minimize the loss function. Inspired by Jacob et al. [21], the backpropagation
uses lookup tables in real values, so that they can be adjusted in small
amounts. The forward pass uses quantized lookup tables as in the inference to
calculate the loss. Results show that by this learning method, the quantized
lookup table has little impact on the model accuracy. We have also tried to
quantize the centroids, which reduces the accuracy more significantly.
Therefore, we do not quantize centroids in this paper.

###  3.4 Cost analysis of LUT-NN

According to the output formula Eq. 4 of a PQ-based AMM in LUT-NN, the main
cost is from the encoding function $g^{c}(a^{c})$, which calculates the
Euclidean distance of the sub-vector with each centroid. After that, the cost
is from table lookup with the encoding result (i.e., index of the closest
centroid), and the result aggregation of sub-vectors. For file size, the major
cost is from the lookup tables, which saves the dot product result of each
centroid and the according sub-vectors in the weight matrix. The size of
codebooks is relatively small, since the sub-vectors on the same column share
one codebook.

Therefore, we analyze the FLOPs of encoding, table lookup and aggregation, as
well as the size of lookup tables as the cost of a LUT-NN AMM, to compare it
with normal MM in Table 1. Since convolution can be transformed to MM by
im2col, its cost also follows these formulas. For a convolution, $M$ is the
number of output channels, $D$ is the number of input channels $\times$ filter
size2, and $N$ is height $\times$ width.

The number of centroids $K$ and the sub-vector length $V$ are two
hyperparameters of LUT-NN. They are tradeoffs between accuracy and cost (refer
to Sec. 6.3). The more centroids $K$ and shorter sub-vector $V$ may lead to
higher accuracy, but will increase the cost of LUT-NN. Table 2 shows the
calculated GFLOPs and model size by the formulas in Table 1 for different
models, using typical $(K,V)$ settings in LUT-NN. These typical settings can
achieve comparable accuracy with the original model, and also align with the
SIMD width for high performance. Similar to other hyperparameters in DNN
training, $K$ and $V$ can be set by grid search, evolutionary search, or other
popular methods considering the cost budget.

It is clear that LUT-NN can achieve both computation and model size saving.
The FLOPs saving is because $K$ is normally smaller than $M$. For example, the
number of output channels i.e., $M$, for ResNet50 is normally 128, 256, or
512, so the FLOPs can be reduced by $4\times$ when $K=8$. For ResNet20, the
number of output channel is 16, 32, and 64, so the FLOPs is reduced by
$2\times$ when $K=8$. We will discuss the hashing cost in next section.

$A\in\mathbb{R}^{N\times D}$: input matrix
---
$B\in\mathbb{R}^{D\times M}$: weight matrix
$V$: the length of a sub-vector $a^{c}$
$K$: the number of centroids in a codebook for $a^{c}$
| Ours | MM
FLOPs | $N\cdot D\cdot K+N\cdot M\cdot D/V$ | $N\cdot D\cdot M$
Size | $D\cdot M\cdot K/\,V$ | $4\cdot D\cdot M$
Table 1: FLOPs and disk size of a LUT-NN AMM compared to MM (FP32).

Model | GFLOPs
---|---
original | (8, 9) | (16, 9) | (DT, 9)
ResNet20 | 0.041 | 0.017 | 0.029 | 0.006
ResNet32 | 0.069 | 0.028 | 0.048 | 0.011
ResNet18 | 1.814 | 0.412 | 0.515 | 0.208
ResNet50 | 4.089 | 1.015 | 1.175 | 0.775
| original | (16, 32) | (16, 16) | (DT, 32)
BERT | 2.759 | 0.169 | 0.254 | 0.127

Model | Disk Size (MB)
---|---
original | (8, 9) | (16, 9)
ResNet20 | 1.02 | 0.40 | 0.80
ResNet32 | 1.76 | 0.69 | 1.37
ResNet18 | 44.55 | 12.57 | 23.16
ResNet50 | 97.29 | 42.18 | 76.52
| original | (16, 32) | (16, 16)
BERT | 162.26 | 23.05 | 43.30

Table 2:  Theoretical GFLOPs and model size of typical ($K$, $V$) for
different models, calculated by formulas in Table 1. “DT” stands for hashing
by decision tree to encode sub-vectors. Hashing does not change disk size.

###  3.5 Hashing for faster encoding

As introduced in Sec. 2.1, hashing is to avoid the Euclidean distance
calculation of $k$-means encoding, but at the cost of higher quantization
error (refer to Fig. 3b).

We also evaluate the potential of hashing for DNN inference. Since hashing is
not differentiable, LUT-NN uses hashing after the centroids are learned. Our
current results show that to achieve similar model accuracy as Euclidean
distance for encoding, we have to use a 12-level decision tree for hashing.
Table 2 lists the theoretical FLOPs reduction by using this 12-layer decision
tree. Compared to distance calculation, it can further reduce FLOPs by 30% to
$3\times$. As the encoding cost is reduced, the table lookup and aggregation
FLOPs become the bottleneck.

On current commodity hardware without direct hashing support, hashing is
higher than Euclidean distance calculation, since the tree traversing is
sequential without SIMD support. Therefore, we still use Euclidean distance
for encoding in LUT-NN and will discuss the potential hardware design for
hashing in Sec. 5.

##  4 Model Inference Design and Optimization

In this section, we present the design and optimization of the inference
system to support LUT-NN. LUT-NN unifies neural network operators to table
lookups, and each operator can be represented by closest centroid search and
table lookup. We design the LUT-NN model inference architecture in Fig. 6,
which includes the Closest Centroid Search Operator and the Table Lookup
Operator.

###  4.1 Closest Centroid Search Operator

The centroid search is the most computation-intensive operation in LUT-NN, and
high-performance centroid search empowers performance efficiency compared to
conventional computational methods. The Closest Centroid Search Operator first
computes the distance between input tensors and centroids, which can be
denoted as matrix multiplications of input tensors and centroid matrices.
Then, it searches centroids with the shortest distance for each input sub-
vector.

However, it is challenging to implement the centroid search in LUT-NN. First,
LUT-NN distance computation is irregular-shaped (tall-and-skinny) and is
difficult to be optimized by BLAS libraries. The height of the input tensor
($N$) is usually much larger than the length of sub-vector ($N\gg V$) and the
number of centroids ($N\gg K$) on each codebook. Thus, the operation intensity
of the distance calculation can be approximated by
$\frac{2NVK}{NV+KV+NK}\approx\frac{2}{1/K+1/V}\text{FLOP/Byte}$. Since the
length of the sub-vector and the number of centroids are small in LUT-NN, the
operation intensity $\frac{2}{1/K+1/V}$ is also small. The distance
computation becomes a memory-intensive matrix multiplication.

Therefore, we focus primarily on optimizing memory access for centroid
distance computations (❶ in Fig. 6). To reduce memory access overhead, we keep
frequently accessed data in registers and caches as much as possible. Since
centroids matrices have small sizes, we design a centroid-stationary
computation scheme to reside centroid matrices in registers and reorder
centroid matrix load in the inner loop to keep them in cache as long as
possible. The centroid-stationary computation keeps $K\cdot V$ centroid
elements in cache for each codebook, which only requires to read these
centroids once from DRAM. Consequently, it also only requires to read an
$N\cdot V$ input tensor and $V\cdot M$ centroids from DRAM once, which
alleviates memory bandwidth costs and improves performance.

Second, after computing the centroid distance, the Closest Centroid Search
Operator needs to find the centroid with the shortest distance for each input
sub-vector and produce the centroid index (❷ in Fig. 6). It can be represented
by an `argmin` function, which finds an index with the shortest distance.
However, optimization of the search for the closest centroid is still
challenging. First, searching for the nearest centroid for each input sub-
vector is a data-dependent operation. To find the closest one, we must compare
each distance sequentially, which is RAW (Read After Write) dependent and hard
to be parallelized on CPUs. Then, each input tensor has to leverage the
distance computation stage and the closest distance search stage to obtain the
result’s centroid index. And there are data-dependent memory reads and writes
between these two stages.

We propose intra-codebook parallelism to optimize the Closest Centroid Search
Operators. Intra-codebook parallelism searches the nearest centroid for the
input sub-vector on a codebook in parallel. We slice a codebook into multiple
sub-codebooks and compare each distance between sub-vector and centroids in
each sub-codebook. We merge the compared distances by reduction and find the
index corresponding to the closest centroid. It leverages instruction-level
parallelism to improve hardware utilization and performance.

###  4.2 Table Lookup Operator

LUT-NN obtains the indices of the nearest centroids for the input sub-vectors
after closest centroid search, and it leverages Table Lookup Operator to
compute the final results. Table Lookup Operator first reads the pre-computed
results from the corresponding lookup table through indices (❸ in Fig. 6) and
completes the computation by accumulation operation (❹ in Fig. 6). For
example, convolution operators directly read out filter’s outputs from lookup
tables and accumulate each input channel’s result for output channels.

However, table lookup and accumulation introduce additional overhead in model
inference. First, table lookup is difficult to be parallelized and introduces
additional indirect memory accesses, which exaggerate the memory overhead on
lookup tables. Since we have quantized lookup table into INT8 in Sec. 3.3, we
leverage widely supported SIMD shuffle instructions (x86: `pshfb` and ARM:
`tbl`) to achieve parallel and efficient table lookup. We demonstrate the
implementation of table lookup using shuffle instructions in Fig. 6. The
shuffle instruction [5] permutes each byte of a vector based on an index
vector and stores the shuffled bytes in the result vector register in each
clock cycle. On 128-bit wide SIMD, a vectorized table lookup instruction
handles 16 sub-vector lookups ($128/8=16$) on $16$ results ($128/8=16$)
simultaneously, greatly simplifying table lookup and reducing overheads.

Second, the accumulation still has comparable computation costs to the entire
process. For example, when a codebook handles $N$ index lookups on a $K\cdot
M$ lookup table, it costs $N\cdot M$ table lookups ($K=16$) and $N\cdot M$
accumulation adds. Therefore, the vectorized lookup table leaves accumulation
operations as the performance bottleneck of table lookups. Since a higher
number of lanes leads to higher throughput on the same width of SIMD
instruction (e.g., the vectorized INT16 add instruction has twice the
operations of INT8 on a 128-bit SIMD), we maximize accumulation throughput by
mixed precision accumulation. It first accumulates results in INT16 to utilize
more SIMD lanes and then gathers INT16 to INT32 to avoid overflow.

Figure 6: Model inference design and optimization in LUT-NN.

##  5 Gaps of LUT-NN

As the first trial towards unified DNN by table lookup, LUT-NN has several
gaps to be improved.

Hardware implication  Potentially, LUT-NN can greatly reduce FLOPs, e.g.,
$16\times$ for BERT. However, as we will show in Sec. 6.2, the real speedup of
LUT-NN is only $5.4\times$ compared to BERT. For small models, e.g., ResNet20
with $2\times$ FLOPs reduction, LUT-NN may be even slower. The reason is the
unfriendly hardware support. LUT-NN has to run `argmin` partially sequentially
to return the index of the nearest centroid, and then lookup in the table
followed by aggregation. Compared to the direct Multiply-Add support for MM in
hardware, the execution of LUT-NN is very inefficient. Besides, the SIMD width
limits the number of centroids.

To this end, an accelerator or function unit supporting the first-class
parallel table-lookup pipeline could approach the theoretical speedup of LUT-
NN, with no limitation on the number of centroids. What is more, hardware can
also integrate hashing units for further speedup.

Layers sensitive to LUT-NN For CNNs, we find replacing the first layer by
table-lookup can lead to obvious accuracy drop. For example, replacing the
first layer of ResNet20 results in a ~$7\%$ accuracy drop on CIFAR-10. As
explained by Zhou et al. [44], the layer interacted with the model input can
cause more accuracy drop. This issue is even more serious for BERT. Replacing
the first two layers results in 80% accuracy loss (refer to Fig. 11).
Therefore, we do not replace these layers by table lookup. The solutions need
to be further explored.

Operators not replaced by LUT-NN Currently LUT-NN only replaces linear
computation operators with weights, including MM, convolution, and fully
connected. The scaled dot-product attention ($<2\%$ of total latency) in
attention layers have no weights, and we do not replace it by lookup table in
this work. Even with no weights, it could be possible to replace it by lookup
tables with the production of centroids. The non-linear operators, such as the
activation functions, are not replaced by LUT-NN right now. The possibility of
replacing non-linear operators will be future work.

Learning for hashing  We have explored applying hashing after centroids are
learned. It could be possible to also integrate it into the backpropagation to
learn the hashing functions. This could reduce the depth of the tree for
hashing and further reduce the encoding cost.

Dataset | Model | Centroid | Temperature | Weight | Batch | Number of | Optimizer | Learning rate
---|---|---|---|---|---|---|---|---
learning rate | learning rate | decay | size | epochs | scheduler
CIFAR-10 | ResNet20 | 1e-3 | 1e-1 | 0 | 256 | 400 | Adam |
ResNet32 | Cosine
ImageNet | ResNet18 | 256 | 150 | annealing
ResNet50 | 1e-4 |
GLUE | BERT | {5e-5, 4e-5, | 1e-2 | 32 | 3 | AdamW | Constant
3e-5, 2e-5} |
Table 3:  Soft-PQ training settings for centroid and temperature learning. We choose the best fine-tune learning rate among {5e-5, 4e-5, 3e-5, 2e-5} based on the accuracy of validation set for BERT, following [11].  Task | CIFAR-10 (%) | ImageNet (%)
---|---|---
Model | ResNet20 | ResNet32 | ResNet18 | ResNet50
Original | 91.73 | 92.63 | 69.76 | 76.13
BNN | 84.87 | 86.74 | 51.20 | 55.80
MADDNESS | 10.85 | 10 | 0.1 | 0.1
LUT-NN | 89.94 | 90.60 | 67.38 | 71.58
Table 4: LUT-NN achieves comparable accuracy on CIFAR-10 and ImageNet with the original models, much higher than BNN and MADDNESS. Dataset Task | Single-Sentence | Similarity and Paraphrase | Natural Language Inference |
---|---|---|---|---
CoLA | SST-2 | MRPC | STS-B | QQP | MNLI-m | MNLI-mm | QNLI | RTE | Average
Training Dataset Size | 8.5k | 67k | 3.7k | 7k | 364k | 393k | 105k | 2.5k |
Test Dataset Size | 1k | 1.8k | 1.7k | 1.4k | 391k | 20k | 5.4k | 3k |
BERT base (%) | 52.1 | 93.5 | 88.9 | 85.8 | 71.2 | 84.6 | 83.4 | 90.5 | 66.4 | 79.6
BERT half (%) | 32.9 | 91.3 | 85.5 | 80.8 | 69.2 | 81.0 | 80.3 | 87.4 | 65.2 | 74.8
LUT-NN (%) | 43.5 | 92.4 | 85.1 | 83.2 | 69.6 | 81.3 | 79.9 | 87.4 | 64.7 | 76.3
Table 5:  LUT-NN achieves comparable accuracy on GLUE with BERT-base on all
tasks. F1 scores are reported for QQP and MRPC, Spearman correlations are
reported for STS-B, and accuracy scores are reported for the other tasks.

##  6 Evaluation

###  6.1 Experiment methodologies and settings

Dataset and Models In our experiment, we evaluate LUT-NN on both vision and
NLP tasks to demonstrate its effectiveness. Specifically, we evaluate ResNet
family on CIFAR-10 [29] and a large-scale ImageNet [10] dataset. CIFAR-10
dataset consists of $50K$ training images and $10K$ validation images in $10$
classes. ImageNet dataset consists of $1.28M$ for training and $50K$ images
for validation. For NLP tasks, we evaluate the popular BERT model on the GLUE
[39] benchmark dataset.

Baselines We compare CNN model accuracy with two baselines: (1) MADDNESS [4]
and (2) BNN (binary neural network) [44], where weights and activation are
stored in 1-bit and 2-bit, respectively. BNN is a highly optimized model for
traditional model compression methods to avoid computation.

For NLP tasks, the baselines are the BERT-base with 12 layers, and another
6-layer BERT, marked as BERT-half. BERT-half is initialized with the weights
of the first 6 layers from BERT-base and trained with the same settings as
BERT-base. Its precision is illustrated in Table 5.

Soft-PQ training Table 3 lists the detailed training hyperparameter settings.
Except for the initial learning rate, all other training receipts follow the
standard practices [19, 11]. Since the learned temperature requires a larger
learning rate to converge quickly to the optimum value, we use different
learning rates for centroid and temperature learning. Before soft-PQ training,
we initialize centroids by $k$-means clustering. Specifically, we forward the
original model on a randomly sampled sub-dataset (i.e., 1024 training samples)
and collect each layer’s inputs. Each layer’s inputs are clustered by the
$k$-means algorithm to get the initial centroids.

LUT-NN settings To trade off accuracy and cost, we can specify: the layers to
be replaced by lookup table, the number of centroids in a codebook $K$, and
the length of the sub-vector $V$ (Table 1). The default setting in the paper
is to align with both the feature size and the length of SIMD instructions. We
set $(K,V)=(16,9)$ for $3\times 3$ convolution, $(K,V)=(16,4)$ for $1\times 1$
convolution, and $(K,V)=(16,32)$ for BERT. We evaluate different settings in
Sec. 6.3.

As explained in Sec. 5, for CNNs, we replace all the convolution layers except
the first layer. For BERT, we replace the fully-connected operators of the
last 6 layers to compare with BERT-half. We will also evaluate the accuracy
with different number of replaced layers in Sec. 6.3.

Evaluation platforms LUT-NN are implemented on ARM Neon and Intel SIMD
instructions in a single thread and batch size $1$. We evaluate LUT-NN on an
ARM CPU, Cortex-X1 at $2.80$ GHz of Google Pixel 6, and an Intel server CPU,
Xeon Silver 4210 at $2.20$ GHz. We compare LUT-NN with other high-performance
inference systems, including TVM v0.9.0 [6] and ONNX Runtime v1.12.1 [35]. We
tune TVM baselines per kernel using AutoScheduler and AutoTVM in $1500$
iterations.

###  6.2 Accuracy and latency evaluation

Accuracy Table 4 and 5 summarize the accuracy achieved by different methods.
Remarkably, LUT-NN achieves comparable accuracy with the original models with
only $2.03\%$ accuracy drop on CIFAR-10, $<5\%$ drop on the ImageNet, and
~$3.3\%$ drops on GLUE, suggesting that LUT-NN empowers the possibility of
unifying DNN inference by table lookups. In contrast, BNN and MADDNESS
experience a significant accuracy drop. Specifically, BNN has $20\%$ accuracy
drop on ImageNet, and MADDNESS only performs random prediction (~$10\%$ on
CIFAR-10 and ~$0.1\%$ on ImageNet).

Kernel speedup According to Table 1, the FLOPs of our proposed LUT-NN is
$ND(K+M/V)$, and the FLOPs of a normal MM is $NDM$. The FLOPs reduction can be
denoted as $M/(K+M/V)$. We can observe that the LUT-NN kernel achieves lower
computation costs when $M\gg K$ and $V\gg 1$. As shown in Fig. 7a and 7d, the
kernel speedup gradually improves as the layer index increases. The reason is
that the number of output channels increases from $64$ to $128$, $256$, and
$512$ as the layer index increases. The increased number of output channels
$M$ contributes to the speedup in these layers.

We observe that some kernels have smaller speedups in these two figures, and
all of these layers are $1\times 1$ convolutions. Compared with $3\times 3$
convolutions ($V=9$), currently we use shorter sub-vectors ($V=4$) for
$1\times 1$ convolutions. It limits the speedup of these layers.The similar
results can be also observed in ResNet20 (Fig. 7c and Fig. 7f). The first six
kernels of ResNet20 are even slower than the baselines. The reason is $M=16$
for these layers, so LUT-NN has more FLOPs than the original kernels. BERT
kernels achieve higher speedups due to larger $M=768$ or $3072$, and longer
sub-vector $V=32$. The best speedup on BERT kernels are $12.5\times$ (ARM CPU)
and $10.3\times$ (x86 CPU).

Model speedup Fig. 8 shows the normalized end-to-end model throughput. LUT-NN
achieves $1.37$~$2.3\times$ end-to-end speedup on ResNet18 and ResNet50
compared to TVM and ONNX Runtime. The best speedup is $2.3\times$ in ResNet18
on ARM CPU over ONNX Runtime. However, since ResNet20 and ResNet32 have fewer
output channels $M$, these models achieve $1.04$~$1.51\times$ speedups. And
these two have not achieved speedup compared with TVM. The BERT model has
higher throughput, and the speedups are $5.4\times$ and $3.8\times$ on the ARM
CPU and the x86 CPU, respectively. Compared to CNN models ($M\leq 512$), the
BERT model has a larger input tensor ($M=768,3072$) to acquire better
performance gains. It also has a longer sub-vector length ($V=32$) compared to
CNN models ($V\leq 9$).

(a)

(b)

(c)

(d)

(e)

(f)

Figure 7:  LUT-NN layerwise kernel speedup over ONNX Runtime (ORT) and TVM.
Figure 8:  Normalized end-to-end throughput of LUT-NN (higher is better).

###  6.3 Ablation Study

We evaluate the effectiveness of the learned temperature and hyperparameters
in the ablation study. The hyperparameters include the number of centroids,
the length of sub-vector, and the number of replaced layers.

Figure 9:  Learning curves of LUT-NN-based ResNet20 on the CIFAR10 dataset
with temperature tuning methods. “Annealing Temperature” (Orange) refers to
manually annealing temperature from 1 to 1e-1. Our proposed learned
temperature technique reaches a higher 89.94% accuracy than the annealing
temperature’s 89.01% accuracy and setting temperature as 1’s 86.85% accuracy.

Learned Temperature In Sec. 3.2, we use gradient descent to learn the
temperature. To evaluate the effectiveness of our method, we compare three
temperature tuning strategies together: learned temperature, statically
setting the temperature as $1$, and annealing temperature from $1$ to $0.1$.
We compare the training curves in Fig. 9. The figure suggests that our
proposed learned temperature reaches the highest accuracy ($89.94\%$) and
outperforms the statically setting ($86.85\%$) and the annealing temperature
($89.01\%$). In addition, the learned temperature has a faster convergence
speed.

Impact of centroids number and sub-vector length The centroids number and sub-
vector length do affect not only the inference throughput but also the model
accuracy. We present the ablation study for the impact of these two
hyperparameters. We follow the same experiment setting as Sec. 6.1 on ResNet20
and BERT.

Figs. 10a and 10b collect accuracy and FLOPs for the variant of centroid
numbers and sub-vector lengths in ResNet20 and BERT. For ResNet20, the sub-
vector length significantly affects the model accuracy and worsens as the sub-
vector length increases. Each codebook has to handle higher dimensions as the
sub-vector length grows, which cannot be accurately classified and harms the
model accuracy.

The centroid number also affects accuracy and performance. As the centroid
number increases, each codebook can classify sub-vector in more fine-grained
granularity, and it improves the accuracy of ResNet20. To balance the model
accuracy with performance, we prefer to set $K=16$ and $V=9$ to achieve better
accuracy and fewer GFLOPs than ResNet20. However, the accuracy of LUT-NN on
BERT model rises and then falls as the sub-vector length and centroid number
increase. It indicates that the relationship between latency and accuracy is
affected by hyperparameters, model structures and datasets. For BERT model, we
set centroid numbers $K=16$ and sub-vector length $V=32$, which obtains the
highest accuracy and lower costs.

(a) ResNet20

(b) BERT

Figure 10: The scaling of centroids number and sub-vector length on ResNet20
and BERT for accuracy and FLOPs.

The number of replaced layers As LUT-NN introduces quantization errors, the
number of replaced layers of a model also affects its accuracy. To investigate
this effect, we gradually replace more layers of BERT model on the Semantic
Textual Similarity Benchmark (STS-B) task. Since quantization errors are
passed through forward propagation, we gradually replace each layer of BERT
with LUT-NN from the last layer to the front, and see accuracy gradually drops
in Fig. 11, particularly for the last three layers. The experiment shows that
the number of replaced layers is an essential hyperparameter for improving
model accuracy.

Figure 11:  The accuracy of LUT-NN based BERT with respect to the number of
layers to replace. Replacing 7 layers brings a negligible decrease in
accuracy.

##  7 Related Work

###  7.1 Approximated Matrix Multiplication

Traditional approximated matrix multiplication works focus on minimizing the
difference between the ground truth and the approximated output. [31] used the
random projection technique to project two matrices to a lower dimensional
subspace before multiplying. [36] treated matrix multiplication as the sum of
outer products and calculate it with Fast Fourier Transformation. SVD [28] can
be used for accelerating matrix multiplication too. With SVD, one input matrix
is decomposed into a form that is more efficient to compute. SVD is applicable
when one input matrix is known in the initialization stage and can be
decomposed in advance. [1, 12] approximated matrix multiplication with the
Column-Row-Sampling method: they first sample $k$ columns from the left
operand and respective $k$ rows from the right operand. Then the $k$ columns
and $k$ rows are multiplied to get the approximated result. [4] used product
quantization to compress one input matrix and precompute the compressed
centroids with the other input matrix to form a lookup table. The matrix
multiplication is then transformed into a lookup operation in the lookup
table. To conclude, traditional methods will suffer from severe accuracy loss
when embedded in the neural network inference if the approximation is too
harsh. Our method can avoid this defect by integrating itself into the end-to-
end training process of the neural network.

###  7.2 Product Quantization for DNN

Product Quantization [32] is a popular and successful method for large-scale
approximated nearest neighbor search [24]. In recent years, some work
integrates product quantization into neural networks for different purposes.
For example, [42, 43, 22, 27] incorporated product quantization as a layer of
a convolutional neural network to obtain a compact and discriminative image
representation. [7] utilized Product Quantization as a tool to compress the
embedding layer in NLP models. [38, 13, 8] compress the weight matrix for
neural networks with Product Quantization. However, our method differs from
the above methods in that our purpose is end-to-end neural network inference
acceleration. We use differentiable product quantization to replace all layers
of the neural network rather than a single layer. Also, we compress the input
and output feature maps of operators rather than the weight matrices to
achieve acceleration.

###  7.3 Scalar Quantization

Scalar quantization methods aim to reduce scalar bits in neural networks,
e.g., from float representation to INT8 representation. They can both compress
the neural network bits and accelerate the inference. [21] proposed an INT8
quantization method with both the training scheme and an efficient kernel
implementation. [9, 45, 2, 3, 34] further proved that 1/2/4-bit quantization
suffices for image classification. Recently, [40] proposed a quantization
method that reduces the weight to less than one bit. However, extremely low-
bit quantization methods, such as 1/2/4 bit or even less than one bit, usually
require specially designed hardware like the Tensor Core. Our work designed a
less than one-bit quantization method that only depends on SIMD instructions
available on the common Intel and ARM CPU platforms.

##  8 Conclusion

This paper takes the first step towards unifying DNN inference by table
lookup. A new paradigm potentially brings significant benefits to DNN
inference ecosystem, which simplifies the inference software and hardware
design, and decouples with the DNN algorithm updates. By the centroid learning
technique for DNN, LUT-NN achieves comparable accuracy for complex tasks with
less resource cost. However, LUT-NN still has space to be improved, such as
the learning technique to improve accuracy, and hardware support for table
lookup, which call for future efforts from the community.

## References

  * [1] Menachem Adelman, Kfir Levy, Ido Hakimi, and Mark Silberstein.  Faster neural network training with approximate tensor operations.  Advances in Neural Information Processing Systems, 34:27877–27889, 2021.
  * [2] Hande Alemdar, Vincent Leroy, Adrien Prost-Boucle, and Frédéric Pétrot.  Ternary neural networks for resource-efficient ai applications.  In 2017 international joint conference on neural networks (IJCNN), pages 2547–2554. IEEE, 2017.
  * [3] Ron Banner, Yury Nahshan, and Daniel Soudry.  Post training 4-bit quantization of convolutional networks for rapid-deployment.  Advances in Neural Information Processing Systems, 32, 2019.
  * [4] Davis Blalock and John Guttag.  Multiplying matrices without multiplying.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 992–1004. PMLR, 18–24 Jul 2021.
  * [5] Davis W Blalock and John V Guttag.  Bolt: Accelerated data mining with fast vector compression.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 727–735, 2017.
  * [6] Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, et al.  Tvm: An automated end-to-end optimizing compiler for deep learning.  In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 578–594, 2018.
  * [7] Ting Chen, Lala Li, and Yizhou Sun.  Differentiable product quantization for end-to-end embedding compression.  In International Conference on Machine Learning, pages 1617–1626. PMLR, 2020.
  * [8] Weihan Chen, Peisong Wang, and Jian Cheng.  Towards convolutional neural networks compression via global&progressive product quantization.  In BMVC, 2020.
  * [9] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David.  Binaryconnect: Training deep neural networks with binary weights during propagations.  Advances in neural information processing systems, 28, 2015.
  * [10] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 248–255. IEEE Computer Society, 2009.
  * [11] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [12] Petros Drineas and Ravi Kannan.  Fast monte-carlo algorithms for approximate matrix multiplication.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 452–459. IEEE, 2001.
  * [13] Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev.  Compressing deep convolutional networks using vector quantization.  arXiv preprint arXiv:1412.6115, 2014.
  * [14] Google.  Tensorflow: An end-to-end open source machine learning platform, 2019\.
  * [15] R.M. Gray and D.L. Neuhoff.  Quantization.  IEEE Transactions on Information Theory, 44(6):2325–2383, 1998\.
  * [16] Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha.  Quantization based fast inner product search.  CoRR, abs/1509.01469, 2015.
  * [17] Kaiming He, Fang Wen, and Jian Sun.  K-means hashing: An affinity-preserving quantization method for learning binary compact codes.  In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23-28, 2013, pages 2938–2945. IEEE Computer Society, 2013.
  * [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  * [19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [20] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network, 2015.
  * [21] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2704–2713, 2018.
  * [22] Himalaya Jain, Joaquin Zepeda, Patrick Pérez, and Rémi Gribonval.  Subic: A supervised, structured binary code for image search.  In Proceedings of the IEEE international conference on computer vision, pages 833–842, 2017.
  * [23] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax, 2016.
  * [24] Herve Jegou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  IEEE transactions on pattern analysis and machine intelligence, 33(1):117–128, 2010.
  * [25] Yang Jiao, Liang Han, and Xin Long.  Hanguang 800 NPU - the ultimate AI inference solution for data centers.  In IEEE Hot Chips 32 Symposium, HCS 2020, Palo Alto, CA, USA, August 16-18, 2020, pages 1–29. IEEE, 2020.
  * [26] Norman P. Jouppi, Doe Hyun Yoon, Matthew Ashcraft, Mark Gottscho, Thomas B. Jablin, George Kurian, James Laudon, Sheng Li, Peter Ma, Xiaoyu Ma, Thomas Norrie, Nishant Patil, Sushma Prasad, Cliff Young, Zongwei Zhou, and David Patterson.  Ten lessons from three generations shaped google’s tpuv4i.  ISCA ’21, page 1–14. IEEE Press, 2021.
  * [27] Benjamin Klein and Lior Wolf.  In defense of product quantization.  arXiv preprint arXiv:1711.08589, 2(3):4, 2017.
  * [28] V. Klema and A. Laub.  The singular value decomposition: Its computation and some applications.  IEEE Transactions on Automatic Control, 25(2):164–176, 1980.
  * [29] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * [30] Stuart P. Lloyd.  Least squares quantization in PCM.  IEEE Trans. Inf. Theory, 28(2):129–136, 1982.
  * [31] Avner Magen and Anastasios Zouzias.  Low rank matrix-valued chernoff bounds and approximate matrix multiplication.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1422–1436. SIAM, 2011.
  * [32] Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh.  A survey of product quantization.  ITE Transactions on Media Technology and Applications, 6(1):2–10, 2018.
  * [33] Calvin McCarter and Nicholas Dronen.  Look-ups are not (yet) all you need for deep learning inference, 2022\.
  * [34] Jeffrey L McKinstry, Steven K Esser, Rathinakumar Appuswamy, Deepika Bablani, John V Arthur, Izzet B Yildiz, and Dharmendra S Modha.  Discovering low-precision networks close to full-precision networks for efficient embedded inference.  arXiv preprint arXiv:1809.04191, 2018.
  * [35] Microsoft.  Onnx runtime, 2019.
  * [36] Rasmus Pagh.  Compressed matrix multiplication.  ACM Transactions on Computation Theory (TOCT), 5(3):1–17, 2013\.
  * [37] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  2019\.
  * [38] Pierre Stock, Armand Joulin, Rémi Gribonval, Benjamin Graham, and Hervé Jégou.  And the bit goes down: Revisiting the quantization of neural networks.  In ICLR 2020-Eighth International Conference on Learning Representations, pages 1–11, 2020.
  * [39] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  CoRR, abs/1804.07461, 2018.
  * [40] Yikai Wang, Yi Yang, Fuchun Sun, and Anbang Yao.  Sub-bit neural networks: Learning to compress and accelerate binary neural networks.  In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021 [40], pages 5340–5349.
  * [41] Ofri Wechsler, Michael Behar, and Bharat Daga.  Spring hill (nnp-i 1000) intel’s data center inference chip.  In 2019 IEEE Hot Chips 31 Symposium (HCS), pages 1–12, 2019.
  * [42] Tan Yu, Junsong Yuan, Chen Fang, and Hailin Jin.  Product quantization network for fast image retrieval.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 186–201, 2018.
  * [43] Cao Yue, M Long, J Wang, Zhu Han, and Q Wen.  Deep quantization network for efficient image retrieval.  In Proc. 13th AAAI Conf. Artif. Intell., pages 3457–3463, 2016\.
  * [44] Shuchang Zhou, Zekun Ni, Xinyu Zhou, He Wen, Yuxin Wu, and Yuheng Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  CoRR, abs/1606.06160, 2016.
  * [45] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  arXiv preprint arXiv:1606.06160, 2016.