Succinct Compression: Lossless Compression for Fast and Memory-Efficient Deep Neural Network Inference
Authors: Yicun Duan
Xiangjun Peng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Succinct Data Structures
Deep Neural Networks
Efficient Inference

Abstract: This paper introduces ``Succinct Compression”, a method to provide lossless compression of Deep Neural Network (DNN) models for fast and memory-efficient inference. The key insight of our method leverages the concept of \textit{Succinct Data Structures}, which supports fast queries without decompressing the compressed representations. Our method consists of three new insights. First, we introduce two basic building blocks to formulate DNN models, and how they can be extended to be synergistic with compressed models (e.g. pruned or quantized models). Then, we propose a scheme to enable mixed-formulation inference for different layers, to better extract its benefits. Finally, our method exploits a specialized execution pipeline to incorporate different model formulations for fast inference. We quantitatively demonstrate that: our method can (1) enable faster and more memory-efficient inference on uncompressed models; (2) be synergistic with a variety of structure-altered/unaltered compression schemes with better speedup and compression ratio, while preserving the accuracy; and (3) can outperform all other state-of-the-art Model Coding approaches.


Under review as a conference paper at ICLR 2023
SUCCINCT COMPRESSION: LOSSLESS COMPRESSION FOR FAST AND MEMORY-EFFICIENT DEEP NEURAL NETWORK INFERENCE
Anonymous authors Paper under double-bling blind review
ABSTRACT
This paper introduces "Succinet Compression", method to provide lossless com- pression of Deep Neural Network (DNN) models for fast and memory-effciiet inference. The key insight of our method leverages the concept of Suceinct Data Structures, which supports fast queries without decompressing the compressed representations. Our method consists of three new insights. First, we introduce two basic building blocks to formulate DNN models, and how they can be ex- tended to be synergistic with compressed models (e.g. pruned quantized mod- els). Then, we propose a scheme to enable mixxed-formulttion inference for differ- ent layers, better extract its benefits. Finally, our method exploits a specialized execution pipeline to incorporate different model formulations for fast inference. We quantitatively demonstrate that: our method can (1) enable faster and more inference on uncompressed models; (2) be synergistic with a variety of structure mnncture-altered/naaeeeee and compression ratio, while preserving the accuracy; and (3) can outperform all other state-of-the-ar Model Coding approaches.
compression schemes with better speedup
INTRODUCTION
Recent efforts on Pareto improvements of compressed Deep Neural Network (DNN) models, on inference time, space consumption and the accuracy, have recently bloomed due to the great success of DNNS in practice. Prior works either aggressively simplifyloptimize the structure DNN models (e.g. Pruning and Neural Architecture Search) retrench the representation of model parameters (e.g. Quantization and Model Coding), with a major focus on the compression ratio and the accuracy. Given variety of methodologies for efficient compression, there still lacks general method to further optimize the inference performance and compression ratio, without affecting the accuracy of both uncompressed and compressed models.
This paper introduces "Succinct Compression", a method to provide lossless compression of Deep Neural Network (DNN) models for fast and memory-efficient inference. The emphasis of method is to enhance the inference performance and compression ratio without affecting the ac- curacy at the same time, for variety classes of uncompressed and compressed models. The unique characteristic of our method is to exploit Succinct Data Structures, which enables fast queries with- out decompressing the compressed representations.
We consolidate three new insights to better incorporate Succinct Data Structures. we propose two semi-strrcturred formulations to represent DNN models element- or block-wise manners, and provide simple extensions to allow them for the combinations of other compression techniques. we enable mixed formulations of different layers in the model, to better extract the potential of Succinct Data Structures. different formulations, by carefully engineering the inner operators of Succinct Data Structures.
design specialized execution pipeline perform the inference
Our evaluation shows that our method can be very effective for the inference efficiency, and gen- erally applicable for uncompressed and compressed models (including for ResNet-50, ResNet- VGG-16, MobileNet-V V2 and DeiT-B). For uncompressed models, 1.07 speedup and 1.17x compression ratio at the same time, without affecting the accuracy. We then show that method can bring significantly more benefits by combining other compression
method achieves most

---

Under review as a conference paper at ICLR 2023
schemes, where all models pre- pre-processed via other compression methods. For instance, by combining structure-altered compression (such as pruming), our method enables the at most 8.8x acceleration of inference ResNet- 101, with 3 compression ratio meanwhile. Similarly, the speedup can he further enhanced to reach 9.3x by incorporating structure-unaltered method (such quantization). We also compare method with variety of the state-of-the-art Model Coding schemes, and show that our method outperforms all of them.
2 RELATED WORKS
large body of relevant works on compressing DNN models consists of two categories, based on the orientation of their methodology: structure-altered and -unaltered methodologies. We outline key directions each category, briefly describe their features and justify the novelty of our method.
2.1 STRUCTURE-ALTERES METHODS FOR COMPRESSION
Structure-alteeed Methods refer to those compression methods by simplifying/optimizingg the DNN model architectures, and representative methods in this direction include Pruning, Low-Rank Factorization, Neural Architecture Search (NAS) and Knowledge Distillation (KD). We describe each of them in brief as follow.
Pruning removes the redundant connections within DNN models without incurring consider- able degradation of the accuracy. There are two categories of Pruning. One is Unstructured Prun- ing (Dong et al. (2017): Lee al. (2019); XIAO et al. (2019); Park al. (2020), which aggres- sively removes neurons with small relevance whenever it's possible. Though such an approach can deliver decent compression ratio with only a marginal degradation of the accuracy, the inference overheads suffers from the inefficient usage of the memory, due to the frequent operations on sparse matrices (Gale et al. (2019): Blalock et al. (2020)). The other Structured Pruning (Huang & Wang 2 [in et al. (2018): Yu et al. (2018); ; He et al. (2019); Zhao et al. (2019); Yu et al. (2021). which only removes irrelevant units of DNN models at a granularity of the elementary structures (e.g. weights, filters and layers). Though these methods can benefit the performance/compressioo ratio due to the reduction of the total computational costs, the accuracy is usually not as expected.
@ Low-Rank Factorization (Mamalet & Garcia 2012);; Sainath et al. (2013): Zhao et al. (2017)::
et al. 2018) uncovers the latent compact structure of the network through low-rank matrix factor- ization of weight layers. Though these approaches may only incur a marginal degradation in terms of the accuracy. they requires extra computational costs and the benefits in memory efficiency may not be consistent in different models.
NAS (Mellor et al. (2021): : Zhao et al. (2021) automatically output neural network architectures using specific search strategies applied to a large search space. Therefore, huge amount of extra computational costs are required and such methods need to be performed before the deployments of the selected models.
4 KD (Feng et al. (2021) Wang 2021 Zhu et al. (2021) ) is to train a large model and then use it as teacher train a more compact model. Similarly, KD also demands a huge amount of extra computational costs for training different models, therefore they are usually performed off-line.
In this work, we consider Pruning as the representative method in this direction, to justify the com- patibility of our method with Structure-altered methods (as described in Section 7.2
2.2 STRUCTURE-UNALTERR METHODS FOR COMPRESSION
Structure-unaltered Methodologies refer to those compression methods by compressing DNN models without altering the model architecture, and there are two representative methods in this direction, which are Quantization and Model Coding. We describe each of them brief as follow.
Quantization reduces the bitwidth of parameters within DNN models, and such an approach can be achieved via quantization aware training (Bengio et al. (2013); Allizadeh et al. (2020) or post- training quantization (Banner al. (2019); Cai et al. (2020)). Note that it's also feasible to perform extreme quantization (e.g. binarization) for this purpose (Cai et al. (2017): Bulat et al. (20TT) but usually suffers from significant degradation of the accuracy.
2

---

Under review as a conference paper at ICLR 2023
Model Coding represents DNN models via extra bit sequence. Several well-studied coding strategies like Huffman Coding (van Leeuwen (1976), Tunstall Coding (Tunstall 1967)) and Arith- metic Coding (Witten et al. (1987)) have been attempted for compressing DNN models (Han et al. (2066)): Reagen et al. (2017); | The et al. (201)). ) More recently, there are a growing interests in customized coding strategies in the context of DNN models (Louizos al. (2017); Havasi et al. (2018); Oktay et al. (2020b)). However, these approaches suffers from costly pre-processing to con- vert model parameters encoded values, and the overheads of decoding are significant during the inference runtime.
Our work considers Quantization as the representative method in this direction, to justify the synergy of our method with Structureuunattered methods (as described in Section (.3)) Also, we compare our method against a variety of Model Coding methods to show that our method can outperform all other state-of-the aftt---------tttte methods (as described in Section 7.4
2.3 NOVELTY OF OUR METHOD
The novelty of our method is three-folded. O We are the first to introduce Succinct Data Structures the context of DNN models, which allow fast queries on compressed representations. we design specific formulations to make DNN models more compatible with Succinct Data Structures, which reduces the overheads for both pre-processing and decoding during the inference runtime. @ our method is generally applicable to available DNN models, and achieve Pareto improvements in both inference time and memory efficiency, without affecting the accuracy.
3 FORMULATING DNN MODELS
The first part of our method is to formulate DNN models appropriately, so that Succinct Data Struc- tures can take advantage of. Succinct Data Structures exploits the delimiters within a long string, to perform fast queries directly on the compressed representations. To this end, we propose the model formulation called Muntime-Accessibe ing a minimal amount of delimiters to construct hierarchical information (e.g. layers). Our proposed RAS consists of two basic building blocks, including (1) Element-wise RAS, which uses delimiters to separate different elementary operands within DNN models; and (2) Block-wise RAS, which applies delimiters to separate different sets of data operands within DNN models, based on the computation kernels. Based on the above Element- wise and Block-wise RAS, we provide simple extensions of RAS, to make them synergistic with other compression methods.
Sequence (RAS), which refers semi-structured format us-
A. Outer dellmiter
1.01, 2.09, 3.01, 4.53, 0.77 3.01. 0.55
Inner deliritee
block
[1.03, 2.11, 2.09, 2.05], 0l, 4.35, 0.77) 1S.01... 0.33]
Delimiter for blocks
... [1. 1.11) 2.77% (14, 0.11) (3, 0.111 (20, 1.55) | ...
Distance between and its left neighbor
D.
One block
# I [[t, (B,), 2777, 0.:11] [[B, 0.11), (20, 1.55i] 1...
Figure 1: A comparison of different kinds of
Sequence (RAS).
3

---

Under review as a conference paper at ICLR 2023
3.1 ELEMENT-WISE RUNTIME- ACCEESSILE SEQUENCE
One formulation in our method is Element-wise Runtime Accessible Sequence (denoted as Element- wise RAS). Element-wise RAS utilizes delimiters separate elementary data operands. In the context of DNN models, the pre-defined delimiters (e.g. vertical bar and number sign) are used at the boundaries of different elementary data operands from DNN models, and these delimiters are used to query for clementary data operands accordingly.
Figure (A) shows an example Element-wise RAS; there are two vertical bars encompassing several elementary operands. This methodology forms the Element-wiss RAS, and the number sign used to represent the border of this union. To properly formulate the whole network into Element- wise RAS, we concatenate such unions by using separate delimiter (e.g. #*).
3.2 BLOCK-WISS WISE RUNTIME-ACCESSIRR SEQUENCE
The limitation of Element-wise RAS is that frequent queries are required for every single data operand, before the computation for model inference. Therefore, to improve the efficiency of operand query, we suggest the other formulation DNN models: Block-wise Sequence (denoted as Block-wise RAS). Different from Element-wise RAS, Block-wise RAS forms basic building blocks for query and access based on the computation kernels, namely denoted as block. Such block stores a consecutive number of elementary data operands, which are used for computation kernel. Between different blocks, Block-wise RAS exploits delimiters for separation, so that they can be efficiently queried.
Figure (B) shows an example of Block-wise RAS: the Block wise RAS aggregates five operands with two square brackets, as one individual block. This transformation of elementary operands, by synthesizing multiple operands and using a distinct delimiters, can provide faster queries by extracting them one time over Element-wise RAS.
3.3 EXTENDING BOTH RAS FOR COMPRESSED MODELS
Since compressed models, supported by other compression schemes, usually maintain high extent of the sparsity current designs of Element/Block wise RAS may not be capable to extract the maximum potentials of Succinct Data Structures on compressed models. To resolve this issue, we provide simple extensions to RAS so that they can be synergistic with other compression schemes. The key insight to form elementary data operand in a similar manner as inverted indexes, by forming tuple consisting of the exact values and the relative positions.
Figure [CC)DD shows examples of these optimized RAS formulated in Element- or Block-wise manner. The difference hereby is that, refine the elementary operands tuples. In such tuple, the first element refers to the relative distance between this and its left neighbor (a number a delimiter); and the second element stores the value of the corresponding data operand. This approach is synergistic with sparse models because for unstructured pruning, the relative distance, contained in the reshaped tuple, effectively exploit the sparse model structures.
4 CONVERTING RAS TO Succinct Data Structures
The second part of our method is about how to covert RAS into Succinct Data Structure for efficient inference. We first provide a selection scheme to embrace the heterogeneity of different layers within DNN models, to maximize the benefits of our method. Then, we describe the rationale of our selected Succinci Data Structure Wavelet Tree.
4.1 MAYER-WISE SELECTION OF THE RAS TYPE
In practice, socly using Element-wise or Block-wise RAS for one model cannot fully unleash the potentials, since the sparsity and access frequency vary across the whole model. Therefore, it's
Note that Quantization and Model Coding can be viewed to exploit bit-level sparsity, so that the redundancy of data representation within DNN models he reduced.
4

---

Under review as a conference paper at ICLR 2023
demanded to perform the selection of RAS at certain granularity of model structure. We consider layer-level in this work, by connecting the size of elementary operands with the following criterion.
Access Frequency of elementary data operands is used to determine which RAS to be used for the overall efficiency. More specifically, we define whether a particular layer is computationally intensive or based on the ratio of FLOPs #Parameters (namely ILLOPs-Parameter-ratioo FPr). As long as above FPr, our method uses Block-wise RAS. Otherwise, Element-wise RAS used.
How RAS Types are Distributed? We confirm that, from our experimental studies, all convolution layers and the weight matrices, inside the multi-head attention layers Transformers, exploit Block- wise RAS, due to the intensively usage of stored data; And Element-wise RAS is applied to less- frequently-acceseed layers (FC layers, our experimental studies).
4.2 Succinct Data Structures AND WAVELET TREE
Succinct Data Structures were first pionecred by Jacobson (1988), which refers set of data structures using the and still provide fast query and access operations directly on these compressed representations. In general, Succinct Data Structures have the following representative inner operators.
cerffrmmationthhoorette bound space to store the compressed representation,
Given a string S whose length and alphabet are and o, there are three operations directly on the compression (shown below).
Rank, (x)) returns the number of symbol g appearing in So.r where g E a and x < L.
Select, (I:) returns the position of z-th occurrence of symbol q in S.
(ccess(x) returns the symbol the position of S.
Though there are a number of Succinct Data Structures available for real-world applications, we choose Wavelet Tree (Grossi et al. (2003)) the core of our method. We choose Wavelet Tree (WT) because there are already a number of evident successes in applying WT for large-scale, data- intensive applications, such as Data Store (Agarwal et al.) (2015): Khandelwal et al.) (2016)) Graph Processing (Khandelwal et al. (2017). and it presents outstanding merits of runtime fast queries without losing memory efficiency: allows Rank, Select and Access to only take (logo) time while maintaining space consumption within n log(o) + O(n) bits (where input is of length with a distinct symbols). Therefore, our method deploys WT as the compression technique during the inference runtime.
5 MODEL INFERENCE IN Succinct Data Structures
The third part of our method is perform model inference via Succinci Data Structures. There three steps: O Identify the RAS flag to guide the subsequent steps; @ Execute different retrieval strategies for either Element- or Block-wise RAS: and O Perform the inference.
Identify the RAS Flag, Our method first identifies the RAS flag to obtain which type of RAS being used for the current layer. The flag tagged at the beginning of all RAS for different layers. Therefore, identifying and parsing the flag is necessary for the subsequent steps.
Execute Different Retrieval Strategies based on the Flag. Our method then retrieves all the operands within this layer. For a given type of RAS, the retrieval strategy is structurally organized similarly: for both Element-wise and Block-wise RAS: we use two Select operators locate the corresponding values for current layer within the compressed representation, while the access of these data differs. The differences between two strategics for different types of RAS are: since Block-wise RAS retrieves series of operands at time, additional operations for extracting them are necessary.
0 Inference the extracted operands. Our method finally performs the inference for the current layer. Note that, for inference on compressed models, the inference may require additional decoding, if the combined methods introduce more levels of indexes.
5

---

Under review as a conference paper at ICLR 2023
EXPERIMENTAL METHODOLOGY
Platform and Baseline: All experiments are done via the latest version of PyTorch (Paszke et al.
(019b)); on a platform equipped with Intel Core i9- 1900KF9 and NVIDIA RTX 3090. We consider five mainstream models, including ResNet-50, ResNet- 101 (He al. (2015)) ). VGG-16 (Simonyan & Zisserman 2015)), MobileNet-V V2 (Sandler et al. (019)) and DeiT-B (Touvron et al. (021]).
Methodology: For all uncompressed and compressed models, measure (1) the end-to-end la- tency to examine the performance benefits; (2) the overall memory usage to examine the memory efficiency; and (3) the accuracy. To implement the execution pipeline of our method, the inference pipeline requires less-than-byte packing and unpacking. This can be done directly using Bit Manip- ulation Instructions extensions (e.g. IVVIDIA (a)), due to the fact that
processing granularity of modern SIMD architectures (including CPU SIMD and GPU) is at byte-level. We use PyTorch Bindings with Fortran, to exploit these hardware intrinsic functions for the implementations (i.e. Alexeev).
Model Setups: All these models are trained on the ImageNet dataset (Deng et al. (009)), which used as uncompressed models (used in Section 7.II. To examine the benefits of method over compressed models, we apply representative Pruning (described in Section (7.2 and Quantization methods (described in Section 7.3) on the trained models, and them as the compressed models. Furthermore, we compare our method with other Model Coding methods to show the benefits.
7
EXPERIMENTAL RESULTS
7.1 IMPACTS ON UNCOMPRESSED MODELS
We first examine the impacts of our method uncompressed models. Figure 2 the model size and speedup of our method over the uncompressed models. We draw two observations. First, method provides considerable improvement for uncompressed models on both speedup and compression. For instance, MobileNet-V V2 achieves 1.07 x speedup and 1.17x compression ratio the same time, and ResNet- 101 achieves 1.04x speedup and 1.11x compression ratio at the same time. Second, we note that the improvements on VGG-16 are relatively worse than others. This is because the FC layers within VGG-16 incur significant overheads for the acceleration and compression.
1.50
96.3
1.00
1.02
Reslltt 50
Peoter 331
Oef
Figure 2: Results on uncompressed models for Model Size (left); CR and Speedup (right)
7.2 IMPACTS ON PRUNED MODELS
We then examine the impacts of our method on Pruned models. Table [ reports the results on selected models after using three representative state-of-the-art pruning methods (i.e. layer-level pruning: DBP (Wang et al. 2019)) filter-level pruning: HRank (Lin et al. (2020)); and unstructured pruning: SNIP (Lee et al, (2020)). We first quantitatively demonstrate the outstanding impacts from our method on all models, then we claborate the key observation.
Our method yields significantly better improvements when all models pruned in advance, in terms of both speedup and compression ratio. The results show that our method achieves the speedup of 4.7 x/8.8 x3..8 and the compression ratio 39.48 483999.900 x3x../9xx33.77... /3.77 x/3.81 x, without affect- ing the accuracy, for ResNet-50/ResNet 101//GG- 16G--1//eii-BB Our results suggest that our method synergistic with the state-of-the-art pruning methods.

---

Under review as a conference paper at ICLR 2023
We make the key observation that: method yields better benefits from fiter-levee/unstruuttree pruning, compared with layer-level pruning. As shown Table I the speedup from our method can be up to 1.91 x/8.07x for fller-leve//unstruutturd pruned models, but the improvement for layer- level pruned models (DBP) is limited to just 1.28x. This because the filter-leellunstructurre pruning decreases the "pirtt"/pprammtees of each layer, and there result in less Access operations for extracting data operands, since these layers are formulated in Block-wise RAS based on our methodology.
Table 1: Succinet Compression on Pruned Models: Target sparsity refers to the expected sparsity within the networks after conducting pruning, and can tolerate the error within +-4%. The en- tries "xx/yy" under the Size, CR (Compression Ratio) and Speedup columns show the comparison between only using pruning (left) and applying our method on the top of pruned models (right). UP-ViT Yu & Wu 202T)) is the pruning method specialized for transformers.
Target
Accuracy (Top-1)
CR
Speedup Improved (x)
Size (MB)
CR
Speedup (x)
NN
M
Sparsity
Improved (x)
(x)
(%)
(%)
0
75.5
102
40
75.1
60.8/52.9
1.68/1.93
1.15
1.4/1.6
1.14
DBP
50
74.8
50.2/43.6
2.03/2.34
1.15
1.7/1.8
1.06
60
73.5
41.0/35.3
2.49/2.89
1.16
2.3/2.6
1.13
ResNet- 50
70
72.3
33.2/28.6
3.07/3.56
1.16
3.0/3.4
1.13
40
74.4
61.0/53.1
1.67/1.22
1.15
1,3/1.9
1.46
HRank
50
72.5
49.9/43.2
2.04/2.36
1.15
1,4/2.6
1.86
60
69.9
41.2/35.5
2.48/2.87
1.16
2.1/2.7
1.23
70
68.1
31.0/26.7
3.29/3.83
1.16
2.7/4.5
1.67
90
74.8
10.3/8.7
9.90/11.69
1.18
1.12/2.8
2.50
SNIP
95
74.7
5.2/4.4
19.6/23.34
1.19
1.14/3.5
3.07
97
74.7
3.1/2.6
32.9/39.48
1.20
1.15/4.7
4.09
76.4
171
40
76.2
103/91.2
1,66/1.88
1.13
1,2/1.5
1.25
DBP
50
76.2
87/76.3
1.97/2.24
1.14
1.6/2.0
1.25
60
75.3
70/61.2
2.44/2.79
1.14
1.9/2.4
1.26
ResNet- 101
70
74.9
50.7/44.1
3.37/3.88
1.15
2.5/3.2
1.28
40
76.3
102/90.3
1,68/1.89
1.13
1.172.1
1.91
HRank
50
76.1
85/74.7
2.01/2.29
1.14
1,4/2.6
1.86
60
75.0
71/62.3
2,41/2.75
1.14
1.8/2.9
1.61
70
74.3
50/43.4
3.42/3.94
1.15
2.3/4.4
1.91
90
76.0
17.1/14.6
10.0/11.7
1.17
1.08/5.3
4.91
SNIP
95
75.9
8.6/7.3
19.9/23.56
1.19
1.09/6.4
5.87
97
75.9
5.1/4.3
33.5/39.90
1.19
1.09/8.8
8.07
0
71.3
533
40
71.3
320/290.4
1.67/1.84
1.10
1.7/1.9
I.12
DBP
50
71.3
262/236.0
2,03/2.26
1.11
2.3/2.4
1.04
60
71.1
210/189.2
2.54/2.82
1.11
2.7/2.9
1.07
VGG-16
70
70.2
158/141.1
3.37/3.78
1.12
3.8/3.9
1.03
40
71.3
323/292.8
1.65/1.82
1.10
1.5/1.7
1.13
HRank
50
70.8
254/228.6
2.10/2.33
1.11
1.7/1.8
1.06
60
70.5
214/192.1
2,49/2.77
1.11
1.8/2.1
1.17
70
69.8
160/142.9
3.33/3.73
1.12
2.0/2.4
1.20
90
71.0
53/46.1
10.06/11.57
1.15
1.08/I.3
1.20
SNIP
95
69.9
26.7/22.9
19.96/23.26
1.17
1.08/1.4
1.30
97
69.9
16/13.6
33.31/39.08
1.17
1.1/1.7
1.55
0
81.8
347
DeiT-B
UP-ViT
40
81.7
210/189.2
1.65/1.83
1.11
1.5/1.9
1.27
50
81.7
170/152.6
2,04/2.27
1.11
2.3/2.9
1.26
60
81.6
141/125.8
2.46/2.76
1.12
2.6/3.3
1.27
70
81.5
103/91.2
3.37/3.81
1.13
2.9/3.8
1.31

---

Under review as a conference paper at ICLR 2023
7.3 IMPACTS ON QUANTIZED MODELS
Next we examine the impacts of our method on quantized models, we use first quantize all models at different levels with different bit precision (2/4/8 bits). To quantize our selected models, use the state-of- fotte-of-hhearr quantization methods, including LSQ (Esser et al. (2020) for CNNs and PQT (Liu et al. (202T)) for transformer. After quantization, we apply our method upon these quantized models. We first report our quantitative results in terms of the speedup and compression ratio. Then, we elaborate the key observation.
Table 2: Succinet Compression on Quantized Models: The entries "xx/yy" under the Size, CR (Compression Ratio) and Speedup columns show the comparison between only using quantization (left) and applying our method on the top quantized models (right). For the quantization of DeîT- B. we modify the framework PQT output fixed-bits-enngth results and handcraft DeiT-B model comprised of 2-bits parameters (marked with **), since PQT is incapable for the 2-bit precision. Speedup Improved (x)
Accuracy
CR
Precision
Size
CR
Speedup (x)
NN
M
(Top-1)
Improved (x)
(bits)
(MB)
(x)
(%)
ResNet-50 50
32
75.5
102
1
8
75.4
25.5/21.6
4.00/4.72
1.18
3.5/3.8
1.09
LSQ
75.3
12.8/10.7
7.97/9.56
1.20
3.4/6.6
1.94
72.5
6.4/5.1
15.94/19.92
1.25
2.9/7.0
2.41
ResNet- 101
32
76.4
171
1
76.3
42.8/36.6
4.00/4.67
1.17
3.2/3.9
1.22
LSQ
76.3
21.4/18.0
7.99/9.51
1.19
3.1/7.2
2.32
74.2
10.7/8.8
15.98/19.50
1.22
2.5/9.3
3.72
32
71.3
533
VGG-16
71.3
134/117.5
3.98/4.53
1.14
3.4/3.2
0.94
LSQ
71.5
66.6/56.9
8.00/9.36
1.17
3.1/3.4
1.10
2
69.5
33.3/28.0
16.01/19.05
1.19
2.6/3.8
1.46
81.8
347
DeîT-B
PQT
81.3
86.8/75.5
4.00/4.60
1.15
2.6/3.3
1.27
75.9
43.6/36.9
7.96/9.39
1.18
2.4/5.2
2.17
67.2
21.7/18.1
15.99/19.19
1.20
1.8/6.7
3.72
After quantization, method achieve the maximum level of speedup across all experiments, and still maintain a considerable amount of the reduction in terms of the memory footprint. On ResNet-101 quantized 2-bit precision, the speedup can be achieved by 9.3x. For other quantized models at 2-bit granularity, As for the compress ratio, combining quantization and our method can further compress the models to certain extent. For all four models selected for our experiments, our method can realize more than 19x compression ratio.
SaaNett50/VGG-16/Dee
the speedup can reach to 7.0x/3.8 (0xx3.8x/6.7 8 (6.7x
We make the key observations that: similar to our methods on Pruning, our method on quantized models also bring more benefits on CONV-dominated models, rather than FC-dominated models. For VGG-16 with large FC layers, the improvement of speedup is restricted to 1.10x most. This similar with the results when our method applied on pruned models. We also report results by applying method DeiT-B. Though this model is distinctively different from CNNs, method can still provide a considerable amount of space reduction and inference acceleration, by up 19. x compression and 6.7x speedup.
7.4 COMPARISON AGAINST OTHER MODEL CODING METHODS
Finally, we compare method with the state-of-the-an Model Coding methods, including Rate- distortion Optimized Coding (ROC) (Zhe et al. (202I)). Entropy Penalized Reparameterization (EPR) (Otta et al. (2020a)), DeepCABAC (Wiedemann al. (2019)), Minimal Random Code
8

---

Under review as a conference paper at ICLR 2023
Table 3: A comparison between Succinet Compression and other Model Coding Methods: for fair comparison, we only consider the best results from baseline methods. ('- means the speedup is not capable be validated, since they are not reported in the original paper.)
Error (Top-1)
Size (MB)
CR
Speedup (x)
Neural Network Models
Method
(x)
(%)
Uncompressed
102
1
1
24.5
OPQ
2.68
38.0
1.3
24.5
Deep Compression
6.41
15.91
0.8
25.7
ResNet-50
DeepCABAC
6.06
16.8
25.9
(PR(DF
5.49
18.6
26.0
ROC (Tunstall)
5.10
20.0
4.3
24.9
Our Method
2.10
48.56
9.2
24.5
Uncompressed
13.2
1
29.0
OPQ 0.57
23.2
1.2
29.3
MobileNet-V2
Deep Compression
0.97
13.62
1.1
30.5
ROC (Tunstall)
1.2
11.0
1.7
29.8
Our Method
0.44
30.11
5.6
29.3
Uncompressed
60
1
1
6.6
OPQ
0.13
461.5
1.5
7.0
Deep Compression
1,64
36.57
1.2
7.2
Small VGG-16
DeepCABAC
0.95
63.2
9.0
MIRACLE
0.16
375.0
10.0
EPR (DFT)
0.10
600.0
10.0
Our Method
0.09
641.5
4.7
7.0
Learning (MIRACLE) (Havasi al. (2018) Deep Compression (Han et al. (2016b)). Our experi-
ments aim to examine the tradeoffs of our method on compression ratio, inference time and accuracy loss. In order have fair comparison, the input models for our method
pre pre-processed using OPQ method for Pruning and Quantization (Hu et al. (20II), since other approaches also apply Pruning and Quantization methods (or other methods) before applying their methods.
Table reports the results of this experiment. Our results show that our method can significantly outperform the state-of-the-ard Model Coding methods both compression ratio and speedup by a large magnitude, with the lowest loss of the accuracy. On ResNet-50, MobileNet- V2 and Small VGG-16, our method demonstrates the compression ratio up 48. 48.56x/30.11 1xx433 x with con- spicuous 9.2 9/.6 x/..7 speedup, with the minimum accuracy loss.
We make the key observation that: incorporating Pruning and Quantization with method am- plifies the benefits significantly to achieve the best outcome throughput the whole paper. compared with solely utilizing either Pruning or Quantization. On ResNet-50, our method outperforms the best results reported in Section 7.2 (i.e. 39.48x compression ratio, 4.7x speedup, 25.3% top-1 error), with 48.56 compression ratio, 9.2x speedup and only 24.5% top-1 error. Second, our method can enable lossless compression and acceleration at the same time. As shown in Table 3 there is no accuracy degradation models by using our method.
8 CONCLUSIONS
We present "Succinct Compression".. method to provide lossless compression of Deep Neural Net- work (DNN) models for fast and memory-effcient inference. Our method exploits Succinct Data Structures with three novel insights, which can be generally applicable to a variety of models (i.e. CNNs and Transformers). Our method also synergistic with both structure-allered/--aalteee compress schemes (such as Pruning and Quantization). Our results justify the above benefits. On uncompressed models, our method provides at most 1.07 speedup with 1.17x compression ratio. The benefits from method be further amplified. By incorporating Pruning (and/or Quanti- zation), we can achieve the maximum speedup/compression ratio at 9.3x/641.57 We extensively examine and show that method significantly outperform six other Model Coding methods.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rachit Agarwal, Anurag Khandelwal, and lon Stoica. Succinct: Enabling queries on com- pressed data. In 12th USENIX Symposium Networked Systems Design and Implementa-
tion, NSDI 15, Oakland, CA. USA, May 4-6, 2015, pp. 337-350. USENIX Association, 2015. URL https: wwtp://wwwwwwwwwiw.....
presentation/aggant
Dmitry Alexeev. Fortran Bindings in Py PyTorch. URL. https:// htw.:tuuub.ccm/leeeeeeeee
Entorch-fortzan
Milad Alizadeh, Arash Behboodi, Mart van Baalen, Christos Louizos, Tijmen Blankevoort, and Max Welling. Gradient & regularization for quantization robustness, 2020.
Ron Banner, Yury Nahshan, Elad Hoffer, and Daniel Soudry. Post-training 4-bit quantization of convolution networks for repid-deployment, 2019.
Gilad Baruch, Shmuel T. Klein, and Dana Shapira. Accelerated partial decoding in
wavelet trees. Discrete Applied Mathematics, 274:2-10, 2020. ISSN 0166-218X.
doil/tpss//doo.rr//101001/// http://woooppp.ooooooo..mmmm.a.. 201..0mm..0..011166.. URL https:/ / /www.
rect.
8303974 Stringology Algorithms.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag, What is the state of neural network pruning?, 2020.
Adrian Bulat, Brais Martinez, and Georgios Trimiropoulos. High-capacity expert binary networks, 2021.
Yaohui Cai, Zhewei Yao, Zhen Dong. Amir Gholami, Michael W. Mahoney, and Kurt Keutzer. Zeroq: novel zero shot quantization framework. 2020.
Zhaowei Cai, Xiaodong He, Jian Sun, and Nuno Vasconcelos. Deep learning with low precision by
half-wave gaussian quantization, 2017.
Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez. The wavelet matrix: An efficient
wavelet tree for large alphabets. Information Systems, 47:15-32, 2015. ISSN 0306-4379. http::/s//booooo///.0001011/.11. aeciencc/arrrtcee///////00330000
URL htthtt:p/// //ttt::://ww.... www.:essiiecceccieeeeeee com/
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 JEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi 10. |0. WWW.CCVR..200.2000000
Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer- wise optimal brain surgeon, 2017.
Steven K. Esser, Jeffrey L. McKinstry, Deepika Bablani, Rathinakumar Appuswamy, and Dharmen- dra S. Modha. Learned step size quantization, 2020.
Haozhe Feng, Zhaoyang You, Minghao Chen, Tianye Zhang, Minfeng Zhu, Fei Wu, Chao Wu, and Wei Chen. KD3A: unsupervised multi-source decentralized domain adaptation via knowl- edge distillation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Interna- tional Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pp. 3274-3283, PMLR, 2021. URL http::/proceedingg .ml.iiggssmmm.r............. wwt.pppeessseeeeeeeeeee www.g//3eeegg..ffne html
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks, 2019.
Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text in- dexes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmms, SODA '03, pp. 841-850, USA, 2003. Society for Industrial and Applied Mathematics. ISBN 0898715385.
10

---

Under review as a conference paper at ICLR 2023
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016a. URL http:://axxiv.o/ abs/ / 151 O. 00149
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning. trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016b. URL httt::/aarxiv.or/ abs 1510. 00149
Marton Havasi, Robert Peharz, and José Miguel Herúnndez-Lobato. Minimal random code learning: Getting bits back from compressed model parameters, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition, 2015.
Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. Ame: Automl for model
compression and acceleration on mobile devices, 2019.
Peng Hu, Xi Peng, Hongyuan Zhu, Mohamed M. Sabry Aly. and Jie Lin. OPQ: compressing deep neural networks with one-shot gruning-quantizatin In Thirty-Fifth AAAI Conference on Arti- ficial Intelligence, AAAI 2021, Thirty-Third Conference
Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelli- gence, EAAI 2021, Virtual Event, Febrwary 2-9, 2021, pp. 7780-7788. AAAI Press, 2021. URL attps://ojs aaai. org/ index.ni... http:/nnnexx...eeeeeeeeepp httpp///A.//atttle////e/////////
Zehao Huang and Naiyan Wang. Data-driven sparse structure selection for deep neural networks, 2018.
J. lan Munro, Yakov Nekrich, and Jeffrey S. Vitter. Fast construction of wavelet
trees. Theoretical Computer Science, 638:91-97 2016.
ISSN 0304-3975.
boi/https://oi.org/// http:///do..rr/11.0001/////11/1/ 10tp:/..00111/...2151......0 coom/ sci /ot.://///arrtteee/////////33111 Structures and Compression.
URL https:// https//wwww.cienne.......
sciencedirect
Pattern Matching, Text Data
Guy Joseph Jacobson. Succinct Static Data Structures. PhD thesis, USA, 1988. AA18918056.
Anurag Khandelwal, Rachit Agarwal, and Ion Stoica. Blowfish: Dynamic sorfaceperformance tradeoff in data stores. In Katerina J. Argyraki and Rebecca Isaacs (eds.), 13th USENIX Sym- posium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara. CA, USA, March 16- 18, 2016, pp. 485-500. USENIX Association, 2016. htthttss::///// //wp::::://www////////pp//s usenix. wa
org/conferencce /ndinice//nddii nsdi mnndii16e 1oadi166/tecch.. ca sessi
Anurag Khandelwal, Zongheng Yang. Evan Ye, Rachit Agarwal, and Ion Stoica. Zipg: A memory-effiiient graph store for interactive queries. In Proceedings of the 2017 ACM Inter- national Conference on Management of Data, SIGMOD Conference 2017, Chicago, II, USA, May 14-19, 20/7, pp. 1149-1164. ACM, 2017. 00110001447003351188030666 3064012
URL https:
7/doi 1tt.://01/1.111//3333333333331
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: Single-shot network pruning based on connection sensitivity, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. A signal propaga- tion perspective for pruning neural networks at initialization, 2020.
Chao Li, Zhun Sun, Jinshi Yu, Ming Hou, and Qibin Zhao. Low-rank embedding of kernels in convolutional neural networks under random shuffling. 2018
Mingbao Lin, Rongrong Ji, Yan Wang. Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao. Hrank: Filter pruning using high-rank feature map, 2020.
11

---

Under review as a conference paper at ICLR 2023
Shaohui Lin, Rongrong Ji, Yuchao Li, Yongjian Wu, Feiyue Huang, and Baochang Zhang. Accelerating convolutional networks via global dynamic filter pruning. In Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI-18, pp- 2425 2432. International Joint Conferences on Artificial Intelligence Organization, 7 2018. 1oi1100296//icca2222133333
Utl.tttps://do..rrgg 1ttp//00222633/jaa...... 2t1p////aaaa111//33333 2018/336
Zhenhua Liu, Yunhe Wang, Kai Han, Siwei Ma, and Wen Gao. Post-training quantization for vision transformer, 2021.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning, 2017.
Yifan Lu, Lu Yang. Virendrakumar C. Bhavsar, and Neetesh Kumar. Tree structured data processing on gpus. In 2017 7th International Conference on Cloud Computing, Data Science Engineering -Confluence, pp. 498-505, 2017. doi 10.1 100010990NNPUUUEE222177.0.000000
Franck Mamalet and Christophe Garcia. Simplifying convnets for fast learning. 09 2012. ISBN 0000000077778---44--332222
978-3-642-33265-4
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley. Neural architecture search without training. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Interna- tional Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pp. 7588-7598. PMLR, 2021. URL html
mlr. www.s/pesssss..... 1ee11/9mmeeeee
Gonzalo Navarro. Wavelet trees for all. Journal of Discrete Algorithms, 25:2-20 20, 2014. ISSN 1570- 8667. doi htto:/tss///0..orr/0000011../.
Utthttps:: /www. scí enced rect.]
com/ sc aacc/artte /nnc://arrlleee/////577776673373
23rd Annual Symposium on Com-
binatorial Pattern Matching.
NVIDIA. Bit Manipulation Functions (Table 6) in CUDA FORTRAN Program-
ming Guide,
URL bttps://docs.nvione www.iiiiii..... com/ httppsppcccoppeeeeeeeeeepp/eeeee
cuda fortran-trrrrae poail-prooooo-- quiiii
NVIDIA.
NVIDIA: How
to
access global
memory
efficiently in
CUDA C/C++
kernels.
www.lppprr.iiiiiiaae.....o. nvidia com/blog/
now-access, -eerrgggooolllmm---e--eeee------ antaaaoaaaaafiiiiiillllllyooooo
b. Accessed:
2022-08-26.
Deniz Oktay, Johannes Ballé, Saurabh Singh, and Abhinav Shrivastava. Scalable model compression by entropy penalized reparameterization, 2020a.
Deniz Oktay, Johannes Ballé, Saurabh Singh, and Abhinav Shrivastava. Scalable model compression by entropy penalized reparameterization, 2020b.
Sejun Park*, Jacho Lec*, Sangwoo Mo, and Jinwoo Shin. Lookahead: far-sighted alternative of magnitude-based pruning. In International Conference Learning Representations, 2020. URL
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bur Buc, Emily Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cexsing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024-8035, 2019a. htt.https:///prrrot bdbca288feee 220.EEEEEE.722EEEEEE22222222000.
neur ips. cc pptppppp/////1/aah/ Abst .tmaaattttmmmmmmmmmmmmm...mm...t
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance
12

---

Under review as a conference paper at ICLR 2023
deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Bol Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32. pp. 8024 8035. Curran Associates, Inc., 2019b. 901 5 wass-pyytrchhhaeee settorch-ar-ii imptorrata-mmmpeaattaa ie ve http://rrrra.eeeeeeeeeegnnoorrrr
ibbary.
pdf
Brandon Reagen, Udit Gupta, Robert Adolf, Michael M. Mitzenmacher, Alexander M. Rush, Gu- Yeon Wei, and David Brooks. Weightless: Lossy weight encoding for deep neural network com- pression, 2017.
Tara N. Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran. Low- rank matrix factorization for deep neural network training with high nigh-dimensional output targets. In 2013 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 6655-
6659, 2013.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chigh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceed- ings, 2015. URL httt:://aaxxv.rrrppp//
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou. Training data-efficient image transformers amp; distillation through attention. In International Conference Machine Learning, volume 139, pp. 10347-10357, July 2021.
B. Tunstall. Synthesis of noiseless compression codes. 1967.
Jan van Leeuwen. On the construction of huffman trees. In S. Michaelson and Robin Milner (eds.), Third International Colloquium on Automata, Languages and Programming, University of Edinburgh, UK, July 20-23, 1976, pp. 382-410. Edinburgh University Press, 1976.
Wenxiao Wang, Shuai Zhao, Minghao Chen, Jinming Hu, Deng Cai, and Haifeng Liu. Dbp: Dis- crimination based block-level pruning for deep model acceleration, 2019.
Zi Wang. Zero-shot knowledge distillation from decision-based black-box model. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 10675-10685. PMLR, 2021. URL http: http::///pccceeing...om mllr. (tess/v139/wang21a. html
Simon Wiedemann, Heiner Kirchhoffer, Stefan Matlage, Paul Haase, Arturo Marban, Talmaj Mar- inc, David Neumann, Ahmed Osman, Detlev Marpe, Heiko Schwarz, Thomas Wiegand, and Wojciech Samek. Deepcabac: Context-adaptive binary arithmetic coding for deep neural network compression, 2019.
Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Commun. ACM, 520))500-- jun 1987. ISSN 0001-0782. doi/10.1145/1147222211 URL
21477
XIA XIAO, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network pruning by regularizing auxiliary parameters. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol-
ume 32. Curran Associates, Inc., 2019. URL https:: http::::/ http::////ccceeeececeeeoo nww.ips.cccpoooo
Hao Yu and Jianxin Wu. A unified pruning framework for vision transformers, 2021. 2021.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I. Morariu, Xintong Han, Mingfei Gao, Ching Yung Lin, and Laryy S. Davis. Nisp: Pruning networks using neuron importance score propagation, 2018.
13

---

Under review as a conference paper at ICLR 2023
Shixing Yu, Zhewei Yao, Amir Gholami, Zhen Dong, Schoon Kim, Michael W Mahoney, and Kurt Keutzer. Hessian-aware pruning and optimal neural implant, 2021.
Chenglong Zhao, Bingbing Ni, Jian Zhang, Qiwei Zhao, Wenjun Zhang, and Qi Tian. Variational convolutional neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 2780-2789, 2019.
Qibin Zhao, Masashi Sugiyama, and Andrzej Cichocki. Learning efficient tensor representations with ring structure networks, 2017.
Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo. Few-shot neural architecture search. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12707-12718. PMLR, 2021. URL http:// proceedings ngs mlm press/ zw..ldd..olldccooooo html
Wang Zhe, Jie Lin, Mohamed Sabry Aly, Sean Young, Vijay Chandrasekhar, and Bernd Girod. Rate- distortion optimized coding for efficient cmn compression. In 202/ Data Compression Conference (DCC), pp. 253,262,22 2021. 000/001.1000DCC50052222000000000
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogeneous federated learning. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International
Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12878-12888 PMLR, 2021. URL http:// proceedings mlr. www.pppwwss.eeeeee....... htw39///hu2ll html
14

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL DETAILS OF THE EXPERIMENTS
We disclose additional experimental details to make our work reproducible by others. More specif- ically, we focus on the detailed configurations of RAS types for different layers in the Deep Neural Network models, which is the most influential factor on the inference performance.
To this end, provide additional details how decide the usage of different RAS and the quantitative supports, based on the requirement described in Section 3.3 Since our selection criteria based on FPr MALLOP--Prrameter-ratto we also provide relevant details for each layer.
Table A demonstrates the detailed results of this method on ResNet-50, As explained in our paper, the CONV layers demand Block-wiss RAS for coarse- gaase-grained accesses, since accesses these layers are relatively frequent; and the FC layers can be used via Element-wise RAS, since accesses these layers are less frequent.
Table
ResNet-50 MACs and RAS Type Parameerss
Layers
#Parameters
MACs
RAS Type
conv1
9.41k
118.01M
12541
Block-wise
layerI.conv
215.8Ik
680.39M
3153
Block-wise
layer2.conv
1.22M
1.04G
852
Block-wise
layer3.comy
7.1M
1.47G
207
Block-wise
layer4.comy
14.96M
811.02M
54213
Block-wise
fc
2.05M
2.05M
Element-
Total
25.6M
4121.47M
161
The same trend of the RAS distribution can also be found on VGG-16, where FC layers accounts for around 90% of all model parameters. Such overwhelming proportion directly results in the fact that: the inference performance of our method on VGG-16 is significantly weakened, compared to the results other models (where FC layers occupy less space).
Table 5: VGG-16 MACs and RAS Type
Layers
#Parameters
MACs
MACy/
RAS Type
convl
1.79k
89.92M
50179
Block-wise
conv2
36.93k
1,85G
50095
Block-wise
conv3
73.86k
926.45M
12543
Block-wise
conv4
147.58k
1.85G
12536
Block-wise
conv5
295.17k
925.65M
3136
Block-wise
conv6
590.08k
1,85G
3135
Block-wise
conv7
590.08k
1.85G
3135
Block-wise
conv8
1.I8M
925.25M
784
Block-wise
conv9
2.36M
1,85G
783898
Block-wise
conv 10
2.36M
1,85G
783898
Block-wise
conv 11
2.36M
462.52M
196
Block-wise
conv 12
2.36M
462.52M
196
Block-wise
conv
2.36M
462.52M
196
Block-wise
fel
102.76M
102.76M
Element-wise
fc2
16.78M
16.78M
Element-wiss
Tc3
4.1M
4.1M
Element-wing
Total
138.355M
15478M
112
15

---

Under review as a conference paper at ICLR 2023
B INFERENCE ENGINE
Since the inference of our method requires extra supports to access more hardware-detailed func- tions, extend PyTorch Paszke et al. 2019a) for our design. As shown in Figure 3 there are two parts in our extended version. First, we build extensions to support the harmonic transition from the tensor interface to our formalization. Second, build module support runtime query, access and computation over Wavelet Tree Grossi et al. 2003).
PyTorch
B
O N
B
F
Input
N
N
N
N
V
v
Tensor
Storage
Slicing Access
Point to
Tensor Interface
Req
Resp
Request Queries
Wavelet Matrix
Query Execution
Wavelet Inference Engine
Figure 3: Wavelet Inference Engine
B. TENSOR INTERFACE
We extend override of the PoTorch tensor interface, for new set of mechanisms including the storage, slice and data accesses. This guarantees the ease of usage from our method, since no extra efforts needed. The rationles behind our extensions are follows. First, the data storage format of PyTorch's 's tensor becomes inefficient when managing Succinet Data Structures: PyTorch separates the calculation logic and data storage for the tensor, and the storage is managed by special module under the assumption that all the data can be stored as a whole block of continuons memory. So that the interpretation of these data (e.g., slice and view) is easy to be offloaded to tensor's ss implementation. Hereby, we describe how we can connect Succinct Data Structures with the tensor interface.
Slicing is an indispensable function of tensor manipulation, and we extend this function by replacing the original offset-based slicing with Wavelet Tree's select primitive. On our RAS formulation, se- lect operation is natively equivalent to slicing. By leveraging the delimiters in RAS, select can locate any sub-parts under small time consumption. For instance, there slicing request [2 on 4-dimension tensor T' whose size is (128, 3, 224, 224). To response this request, select operations in order to get the required range, which are selecta1 (5), select (3), select (2) and select.zx (3) (where d1, d2 and d3 are the delimiters for dimension- 1/2/3, respectively). Consid- ering the equivalence between select and slicing, we substitute classic slicing with select operations in Succinet Data Structures.
can execute
Address-basee access, which is another rudimentary operation supported by the tensor interface, more difficult to be used for Wavelet Tree. Therefore, override the original access function
16

---

Under review as a conference paper at ICLR 2023
with access operations in Succinct Data Structures. Unlike tensors (whose data arranged tinuously), data (in Wavelet Trees) are stored a tree-like structure, with positions specifically identified by delimiters (e.g., [an Munro et al. (216)). To query data in Wavelet Tree. the di- rect approach is to recursively conduct rankin queries on each level of the bitmap Navarro (2014). However, as the size of bitmap grows (e.g., to IMB), the query process becomes inefficient due to the pointer-chasing issues. We provide additional supports for this, by utilizing a combination of Wavelet Matrix (Claude et al. (2015) and Accelerated Decoding Baruch et al. (2020) accelerate access query on GPU (Described in the next section).
B.2 WAVELET TREE QUERYING MODULE
As mentioned in Section B.1 in Succinet Data Structures, the query mechanism and data arrange- ment format are highly associated. Therefore, it's necessary co-design them for the better perfor- mance. For data storage, rather than storing a tree-like structure which the standard formulation of Wavelet Tree, rearrange the Wavelet Tree to be formed in SIMD friendly format, 2D array- Compared to commonly-used linear data structure like 2D array, pointer-traced tree structures incur additional challenges in data transfer and runtime access Lu al. (2017); NVIDIA (b). Therefore, the conventional approach for Wavelet Tree can't t be directly accelerated on GPU platform. To ad- dress this issue, leverage Wavelet Matrix Claude al. (015)). an equivalent of Wavelet tree but expressed as 2D array, for our implementation on GPU. As shown in Figure 4 our implementation of Wavelet Tree now becomes matrix with bitmaps, which, under the hood, can be stored in a array of bytes. This linear data structure allows our method to exploit GPUs more effectively.
1), (3,
Lo
0), (5,
1
1
1
4
[4, 4), (5, 4)
0
0
0
1
1
Lz
[3, 1),
L3
ranky Cache
Array
Wavelet Matrix
Figure 4: Wavelet Tree Query Module
To improve the performance of rank and select, follow the methodology (descrihed in Baruch et al. (2020)) to improve the performance. Our early characterization reveals that: ranki function accounts for more than 90% computation time and is usually overlapped with other ranko calcula- tions, if the system accesses on adjacent elements. Baruch et al. (2020) proposes solution for this issue (though not addressed DNN inference). by keeping the previous ranky result in a specific register. Our extensions allocate block of cache for each layer, to facilitate with the reuse of previ- ous results. We give out an pictorial example of this in Figure 4 the previous calculation results are stored as tuples in per layer cache; and, when the system invoke new ranko function, the execution can directly start from the nearest recording. For a formal description of our algorithm, we provide the pseudo-codes in Algorithm
Franky is performed each layer's bitmaps count the number of certain range.
17

---

Under review as a conference paper at ICLR 2023
Algorithm Access(x)
Require: 0x
x < the length of bilmap
Ensure: symbhol where symboo is the Feh element of original string 1
r- len(o)
is the alphabet
level +-0 0
B < WM[[evel
WM is the Wavelet Matrix comprised of bitmaps
while r do
(y.pre/tesul) + GelN GelNeares - ranku v. + prefesult Rtcrrdecco
b ranko counts the zeros between and
if B = 0 then
x + 4
(r11/2
else
x Z[level] + (x q) + (--1))))
Z(level] is the number of zeros in current level
end if
level + level +
B +- W MM (level)
end while
symbol + a[!]
18


Reviews:
[{"review_id": "o_aAf86T52i", "reviewer": "Reviewer_BLqS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel method for lossless compression of DNNs which enables faster and memory-efficient inference. Specifically, it applies the succinct data structure to do the compression of DNNs. The main benefit of succinct data structure is that it supports queries without decompressing the compressed representations, thus being faster than previous model coding approaches. Experiments show better speedup ratio on both pruned models and quantized models with several different DNN architectures.", "summary_of_the_review": "Overall the proposed method is novel and the experiments do support the speedup claim. Some details need more explanations.", "strength_and_weaknesses": "## Strength\n1. The proposed method can enable faster inference without influencing the model's performance.\n2. It can be applied together with existing methods on model pruning and quantization.\n3. The use of succinct data structure is well motivated. \n4. Experiments are extensive and the speedup improvements are consistent.\n\n## Weaknesses\n1. The description of how to apply the succinct data structure is not very clear. Having an algorithm or pseudo code would be better.\n2. It seems that certain software library is utilized for better performance of the proposed method on the hardware. This needs more detailed explanation. Are the reported baseline methods results also based on comparable libraries for performance/speed optimization?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "m_NaYy7Jgc", "reviewer": "Reviewer_MXqh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose succinct data structures and a new formulate, Runtime-Accessible Sequence, to efficiently utilize new data structures. RAS is provided with two versions (element-wise and block-wise) with synergistic effects with pruning and quantization. The authors provide experimental results to support the claims with improved compression ratio and speedup.", "summary_of_the_review": "- More background and related work need to be included.\n- This reviewer is not sure whether ICLR is the right venue for this manuscript.\n- Both mathematical and practical analysis need to be presented.\n- What about other tasks, such as NLP? Is the proposed method specific to vision tasks?\n- Overall, it is difficult for this reviewer to see how the proposed method can lead to \"faster and more memory-efficient\" inference.", "strength_and_weaknesses": "*Strength\n- It is interesting to apply new data structures to enable practical approaches of widely adopted model compression techniques, such as pruning and quantization.\n- Compression ratio and inference speed can be improved by more than 1.2X and 4-9X, respectively, for ResNet-50, ResNet-100, and VGG DeiT-B.\n\n*Weakness\n- Detailed (mathematical) analysis on succinct data structures is missing while exploring (and comparing) other data structures needs to be included.\n- Ablation study for Table 3 needs to be included. Since OPQ has been already applied as a pre-processing, it is difficult to estimate whether the overall improvement on CR or speedup is due to OPQ or RAS.\n- What are the inherent advantages of RAS? How can RAS enhance memory saving?\n- What is \"specialized execution pipeline\"? If it is based on NVIDIA CUDA Fortran, at least some introduction of such engines need to be introduced.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MeDr5iMVmTd", "reviewer": "Reviewer_PvEU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a new data structure to support lossless compression of neural networks and show the effectiveness and efficiency of inference workflows in computer vision tasks.   \n", "summary_of_the_review": "The novelty of this paper is limited; the presentation of the technical section should be further polished; Although it shows a performance boost over computer vision tasks, they are inappropriate benchmarks to show the efficiency of model compression for inference based on the platform where the experiments have been conducted. ", "strength_and_weaknesses": "Strengthes:\n\n+ Lossless compression method can be widely adopted in various inference workflows without considering the drawbacks of performance.\n\n+ The combination with other lossy compression method is flexible. \n\nWeaknesses:\n\n- The presentation of the technique part is difficult to track. It is casual in terms of lack of enough formulation. It is also not-intuitive that those design decisions are presented with enough justification.\n\n- The experimental section is limited to computer vision tasks, where the most memory intensive workflow is NLP models such as Bert and GPT in language modeling. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "06MmHrPReU6", "reviewer": "Reviewer_DFkG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In  this paper,  the succinct data structures, which supports fast queries without decompressing the compressed representations, is utilized to do deep neural network inference. Also they propose a scheme to enable mixed-formulation inference for different layers.  The experimental results show that the proposed method not only can achieve better speedup and memory efficiency on both uncompressed and compressed models while preserving the accuracy, but also outperform the sota model coding approaches.\n", "summary_of_the_review": "This paper proposed a good idea to apply the succinct data structure to the neural network inference. By combining with using the mixed schemas for different layers, it shows significant benefits on both time and memory requirements on different types of neural networks.  It would be better to provide more comparisons for the theoretical time/memory comparison instead of the experimental findings to justify when it will be suitable.\n", "strength_and_weaknesses": "Strengths:\n1. the paper combine a new data structure with the neural network inference and get good results.\n2. the paper propose a flexible schema on where the data structures is used for neural network to further optimize the memory and time.\n3. The benefits are verified on different types of popular neural networks including resnet and transformer.\nWeaknesses:\n1. Lack some descriptions on how this data structure is applied to neural networks? Are both the neural network weights and activations represented by the succinct data structure?\n2. Can you provide more details on how to use pytorch with the succinct data structure? do you rewrite the pytorch kernels to directly use the succinct data structure, or there still need to convert to tensor representation before feeding into pytorch kernel?\n3. The paper gives time/memory complexity of the succinct data structure, it will be better to compare this to the corresponding nn complexities for each kind of neural network(layer).\n4. the speedup improvement on the uncompressed model is not significant compared to the compressed model?  Is there any formal explanation on this? such as vocabulary size change and so on?\n5. It’s not very clear where the speedup comes from, like more efficient kernel, cache, data communication or anything else? Can you provide a theoretical analysis on why this new data structure runs faster compared to common nn libraries like pytorch if this is the first one to use it for nn? This might be related to issue 2.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject