LUT-NN: Empower Efficient Neural Network Inference with Centroid
  Learning and Table Lookup
On-device Deep Neural Network (DNN) inference consumes significant computing
resources and development efforts. To alleviate that, we propose LUT-NN, the
first system to empower inference by table lookup, to reduce inference cost.
LUT-NN learns the typical features for each operator, named centroid, and
precompute the results for these centroids to save in lookup tables. During
inference, the results of the closest centroids with the inputs can be read
directly from the table, as the approximated outputs without computations.
LUT-NN integrates two major novel techniques: (1) differentiable centroid
learning through backpropagation, which adapts three levels of approximation to
minimize the accuracy impact by centroids; (2) table lookup inference
execution, which comprehensively considers different levels of parallelism,
memory access reduction, and dedicated hardware units for optimal performance.
LUT-NN is evaluated on multiple real tasks, covering image and speech
recognition, and nature language processing. Compared to related work, LUT-NN
improves accuracy by 66% to 92%, achieving similar level with the original
models. LUT-NN reduces the cost at all dimensions, including FLOPs ($\leq$
16x), model size ($\leq$ 7x), latency ($\leq$ 6.8x), memory ($\leq$ 6.5x), and
power ($\leq$ 41.7%).
Xiaohu Tang, Yang Wang, Ting Cao, Li Lyna Zhang, Qi Chen, Deng Cai, Yunxin Liu, Mao Yang
# LUT-NN: Towards Unified Neural Network Inference by Table Lookup

###### 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.

+
Footnote †: Contribution during internship at Microsoft Research

+
Footnote †: 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, BERT\({}_{\textit{LARGE}}\)[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 cen
troids 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.

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.

Figure 1: LUT-NN transforms model linear-computation layers to table lookup for inference.
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.

### 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.

\[\operatorname*{arg\,min}_{P}\sum_{c}\sum_{i}\left\|\hat{A}^{c}_{i}-P^{c}_{k} \right\|^{2} \tag{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})=\operatorname*{arg\,min}_{k}\left\|a^{c}-P^{c}_{k}\right\|^{2} \tag{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 has 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.

### 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.

\[h^{c}(b^{c})=[P^{c}_{0}\!\cdot\!b^{c},P^{c}_{1}\!\cdot\!b^{c},\cdots,P^{c}_{K- 1}\!\cdot\!b^{c}] \tag{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})=\sum_{i=1}^{n}g^{c}(a^{c})\). The matrix multiplication is then computed as \(g^{c}(a^{c})=\sum_{i=1}^{n}g^{c}(a^{c})\).

Figure 2: Product Quantization for AMM. Each color marks a sub-vector dataset.
\[\begin{split} onehot(\operatorname*{arg\,min}_{k}\big{\|}a^{c}-P_{k}^{c} \big{\|}^{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} )\end{split} \tag{4}\]

### 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. 2(a) uses vanilla PQ with \(k\)-means for encoding, while Fig. 2(b) 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.

**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 back-propagation 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).

### 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})\).

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).
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})=\text{softmax}(-\left\|a^{c}-P_{k}^{c}\right\|^{2}/\,t) \tag{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_{k}^{c}\) 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_{k}^{c}\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})-\text{sg}(\tilde{g}^{c}(a^{c })\cdot h^{c}(b^{c})-g^{c}(a^{c})\cdot h^{c}(b^{c})) \tag{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.

### Learned temperature

The temperature hyperparameter \(t\) of softmax[20] controls the approximation error of softmax to argmax. Shown in Fig. 4(a), 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\to 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. 4(b) 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.

### 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{\max(\text{valuel})}{2^{n-1}-1}\).

Figure 4: Soft PQ learns centroids by backpropagation. The forward pass uses argmin as the encoding function, and backward uses softmax. Each color marks a sub-vector dataset using one codebook. \(P_{k}^{c}\) is the \(k^{th}\) centroid for sub-vector \(a^{c}\).
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.

### 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 size\({}^{2}\), 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.

### 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. 2(b)).

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

\begin{table}
\begin{tabular}{|l|c|} \hline \(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}\) \\ \hline  & **Ours** & **MM** \\ \hline
**FLOPs** & \(N\cdot D\cdot K+N\cdot M\cdot D/V\) & \(N\cdot D\cdot M\) \\ \hline
**Size** & \(D\cdot M\cdot K/V\) & \(4\cdot D\cdot M\) \\ \hline \end{tabular}
\end{table}
Table 1: FLOPs and disk size of a LUT-NN AMM compared to MM (FP32).

\begin{table}
\begin{tabular}{|c|c c c|} \hline \multirow{2}{*}{Model} & \multicolumn{3}{c|}{GFLOPs} \\ \cline{2-4}  & original & (8, 9) & (16, 9) & (DT, 9) \\ \hline 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 \\ \hline  & original & (16, 32) & (16, 16) & (DT, 32) \\ \hline BERT & 2.759 & 0.169 & 0.254 & 0.127 \\ \hline \multirow{2}{*}{Model} & \multicolumn{3}{c|}{Disk Size (MB)} \\ \cline{2-4}  & original & (8, 9) & (16, 9) \\ \hline 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 \\ \hline  & original & (16, 32) & (16, 16) \\ \hline BERT & 162.26 & 23.05 & 43.30 \\ \hline \end{tabular}
\end{table}
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.

Figure 5: (a) The output probability distribution of \(\operatorname{softmax}(\frac{x}{t})\) at different temperature, for four centroids as an example. \(t\rightarrow\infty\) approaches uniform distribution, and \(t\to 0\) approaches argmax. (b) The learned \(t\) for each layer of ResNet18.
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.

### 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}\)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.

### 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.

## 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.

## 6 Evaluation

### 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 50\(K\) training images and 10\(K\) validation images in 10 classes. ImageNet dataset consists of 1.28\(M\) for training and 50\(K\) 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

Figure 6: Model inference design and optimization in LUT-NN.
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.

### 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 \(\sim\)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 (\(\sim\)10% on CIFAR-10 and \(\sim\)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. 6(a) and 6(d), 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. 6(c) and Fig. 6(f)). 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\(\sim\)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\)).

### 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.

**Learned Temperature** In Sec. 3.2, we use gradient descent to learn the temperature. To evaluate the effectiveness of our

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|} \hline Task & \multicolumn{2}{c|}{CIFAR-10 (\%)} & \multicolumn{2}{c|}{ImageNet (\%)} \\ \hline Model & ResNet20 & ResNet32 & ResNet18 & ResNet50 \\ \hline Original & 91.73 & 92.63 & 69.76 & 76.13 \\ \hline BNN & 84.87 & 86.74 & 51.20 & 55.80 \\ \hline MADDNESS & 10.85 & 10 & 0.1 & 0.1 \\ \hline LUT-NN & 89.94 & 90.60 & 67.38 & 71.58 \\ \hline \end{tabular}
\end{table}
Table 4: LUT-NN achieves comparable accuracy on CIFAR-10 and ImageNet with the original models, much higher than BNN and MADDNESS.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline Dataset & Model & \begin{tabular}{c} Centroid \\ learning rate \\ \end{tabular} & \begin{tabular}{c} Temperature \\ learning rate \\ \end{tabular} & \begin{tabular}{c} Weight \\ decay \\ \end{tabular} & \begin{tabular}{c} Batch \\ size \\ \end{tabular} & \begin{tabular}{c} Number of \\ epochs \\ \end{tabular} & Optimizer & \begin{tabular}{c} Learning rate \\ scheduler \\ \end{tabular} \\ \hline \multirow{2}{*}{CIFAR-10} & ResNet20 & \multirow{2}{*}{1e-3} & \multirow{2}{*}{0} & \multirow{2}{*}{256} & \multirow{2}{*}{400} & \multirow{2}{*}{Adam} & \multirow{2}{*}{\begin{tabular}{c} Cosine \\ annealing \\ \end{tabular} } \\ \cline{2-2} \cline{6-8}  & ResNet32 & & & & & & & \\ \hline \multirow{2}{*}{ImageNet} & ResNet18 & \multirow{2}{*}{1e-1} & \multirow{2}{*}{0} & \multirow{2}{*}{256} & \multirow{2}{*}{150} & \multirow{2}{*}{Adam} & \multirow{2}{*}{\begin{tabular}{c} Cosine \\ annealing \\ \end{tabular} } \\ \cline{2-2} \cline{6-8}  & ResNet50 & & & & & & & \\ \hline \multirow{2}{*}{GLUE} & BERT & \{
\begin{tabular}{c} \{5e-5, 4e-5, \\ 3e-5, 2e-5\} \\ \end{tabular} & \multirow{2}{*}{1e-2} & \multirow{2}{*}{32} & \multirow{2}{*}{3} & \multirow{2}{*}{AdamW} & \multirow{2}{*}{Constant} \\ \hline \end{tabular}
\end{table}
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].
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. (a)a and (b)b 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

Figure 8: Normalized end-to-end throughput of LUT-NN (higher is better).

Figure 7: LUT-NN layerwise kernel speedup over ONNX Runtime (ORT) and TVM.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline \multirow{2}{*}{Dataset Task} & \multicolumn{2}{c|}{Single-Sentence} & \multicolumn{3}{c|}{Similarity and Paraphrase} & \multicolumn{3}{c|}{Natural Language Inference} & \multicolumn{1}{c|}{} \\ \cline{2-10}  & CoLA & SST-2 & MRPC & STS-B & QQP & MNLI-m & MNLI-m & QNLI & RTE & Average \\ \hline Training Dataset Size & 8.5k & 67k & 3.7k & 7k & 364k & 393k & 105k & 2.5k & \\ \hline Test Dataset Size & 1k & 1.8k & 1.7k & 1.4k & 391k & 20k & 5.4k & 3k & \\ \hline BERT base (\%) & 52.1 & 93.5 & 88.9 & 85.8 & 71.2 & 84.6 & 83.4 & 90.5 & 66.4 & 79.6 \\ \hline BERT half (\%) & 32.9 & 91.3 & 85.5 & 80.8 & 69.2 & 81.0 & 80.3 & 87.4 & 65.2 & 74.8 \\ \hline LUT-NN (\%) & 43.5 & 92.4 & 85.1 & 83.2 & 69.6 & 81.3 & 79.9 & 87.4 & 64.7 & 76.3 \\ \hline \end{tabular}
\end{table}
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.
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.

**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.

## 7 Related Work

### 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.

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.

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

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.
### 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.

### 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.
