Succinct Compression: Near-Optimal and Lossless Compression of Deep Neural Networks during Inference Runtime
Authors: Yicun Duan
Xiangjun Peng
Venue: ICLR 2022 Submitted (2022)

Abstract: Recent advances in Deep Neural Networks (DNN) compression (e.g. pruning, quantization and etc.) significantly reduces the amount of space consumption for storage, making them easier to deploy in low-cost devices. However, those techniques do not keep the compressed representation during inference runtime, which incurs significant overheads in terms of both performance and space consumption. We introduce ``Succinct Compression”, a three-stage framework to enable DNN inference with near-optimal compression and much better performance during inference runtime. The key insight of our method leverages the concept of \textit{Succinct Data Structures}, which supports fast queries directly on compressed representation without decompression. Our method first transforms DNN models as our proposed formulations in either Element-wise or Block-wise manner, so that \textit{Succinct Data Structures} can take advantage of. Then, our method compresses transformed DNN models using \textit{Succinct Data Structures}. Finally, our method exploits our specialized execution pipelines for different model formulations, to retrieve relevant data for DNN inference. Our experimental results show that, our method keeps near-optimal compression, and achieves at least 8.7X/11.5X speedup on AlexNet/VGG-16 inference, compared with Huffman Coding. We also experimentally show that our method is quite synergistic with Pruning and Quantization.  


Under review as a conference paper at ICLR 2022
SUCCINCT COMPRESSION: NEAR-OPTIMAL AND LOSSLESS COMPRESSION OF DEEP NEURAL NET- WORKS DURING INFERENCE RUNTIME
Anonymous authors Paper under double-bling review
ABSTRACT
Recent advances in Deep Neural Networks (DNN) compression (e.g. pruning, quantization and etc.) significantly reduces the amount of space consumption for storage, making them easier to deploy in low-cost devices. However, those tech- niques do not keep the compressed representation during inference runtime, which incurs significant overheads in terms of both performance and space consump- tion. We introduce "Succinct Compression", a three-stage framework to enable DNN inference with near-optimal compression and much better performance dur- ing inference runtime. The key insight of our method leverages the concept of Succinct Data Structures, which supports fast queries directly on compressed rep- resentation without decompression. Our method first transforms DNN models as our proposed formulations in either Element- wise or Block-wise manner, so that Succinct Data Structures can take advantage of. Then, our method compresses transformed DNN models using Succinci Data Structures. Finally, our method exploits our specialized execution pipelines for different model formulations. retrieve relevant data for DNN inference. Our experimental results show that, method keeps nparmoptimal compression, and achieves at least 8.7X/11.5X speedup on AlexNe/VVGG-It 16 inference, compared with Huffman Coding. We also experimentally show that method is quite synergistic with Pruning and Quantization.
INTRODUCTION
Deep neural networks (DNNs) demand an increasing number of parameters as the required complex- ity of tasks, which substantially make DNN models become larger Bengio al. (202T). Therefore, DNNs incurs significant amount of memory footprints during inference runtime, and thus affects both the overall performance and the space consumption. Recent efforts compress DNN models in both loss (e.g. pruning, quantization and etc.) and lossless manners (c.g. Huffman Coding). However, the emphasis the prior works focus on compressing DNN models for efficient storage, rather than providing space-efficient representations during the inference runtime. Thus, prior ap- proaches require to decompress compressed model first and perform the inference, which consumes huge amount of memory space. An alternative is to query the compressed models, decode the query results and perform the inference. However, this method suffers from significant performance overheads during the inference runtime.
Our goal is to improve the inference performance, while keeping the model compressed near- optimally. We introduce "Succinct Compression". a three-stage framework enable much faster DNN inference with near-optimal and lossless compression simultancously. The unique charac- teristic of our method is the fast-queryable yet rear-opiimally-coppesee data structures called Succinct Data Structures. By engineering the inner operators, Succinct Data Structures allow fast lookup within the compressed representations directly, without decompressing them first. To exploit this unique set of data structures, we introduce two additional stages to make them and DNN models more synergistic: (1) before compressing DNN models into Succinct Data Structures, we propose two semi-structured formulations to represent DNN models in element-wise block- wise manners; and (2) after maintaining DNN models in Succinet Data Structures, we specialize two pipelines for different formulations, by carefully engineering the inner operators of Succinct Data Structures.

---

Under review as a conference paper at ICLR 2022
The contributions of this paper are as follows.
(i) To improve the inference performance while keeping DNN model compressed, we introduce "Succinct Compression": a three-stage framework to exploit Succinct Data Structures to enable faster DNN inference with near-optimal compression at the same time.
(ii) We suggest two semi-structured formulations store DNN models, which Succinet Data Struc- tures can exploit them more efficiently. One formulates the DNN models in Element-wii manner, while the other one formulates the models in Block-wise manner.
(ii) We provide two approaches for the inference of compressed DNN models, maintained Suc- einct Data Structures, using its inner operators. One serves for the inference pipeline in Element- wise manner, while the other serves for the inference pipeline in Block-wise manner.
(iv) We experimentally demonstrate that method achieve significant speedup with near-optimal compression, compared with the state-of-the-art approach (i.e. Huffman Coding). In addition. our experiments also justify that our method is well-synergistic with other compression schemes (i.e. Pruning and Quantization).
2 RELATED WORKS
The architectures of DNN models grow much larger due to its incredible effects for resolving non- linear tasks. However, the rapidly growing size of DNN models incurs significant overheads in terms of storage. We first classify and elaborate modern compression mechanisms for DNN models into three parts: Pruning, Quantization and Model Encoding. Then we identify the novelty of our method, by comparing it with the above ofate-of-the-art approaches.
Pruning refers to those techniques enabling the removal of irrelevant units (weights, neurons or convolutional filters) (LeCun al. (1989)). Relevance of weights is often determined by the ab- solute value ("magnitude based pruning" (Han et al. (2016) 2017); Guo et al.] (2016)), but more sophisticated methods have been known for decades, e.g., based on second-order derivatives (Opti- mal Brain Damage (LeCun et al. (1989) and Optimal Brain Surgeon (Hassibi & Stork (1992)) or ARD (automatic relevance determination, Bayesian framework for determining the relevance of weights, (Neal [996); Mackay & David (1995); Karaletsos & Rätsch (2015)).
Quantization refers to those techniques aimming for the reduction of the bit-precision of weights, activations or even gradients, which is highly demanded for hardware accelerator designs (Sze et al. (017 ) Methods range from fixed bit-width computation (e.g.. 12-bit fixed point) aggressive quantization such as binarization of weights and activations (Courbariaux et al. (2016): Rastegari ctt al. (2016); Zhou et al. (0116); Hubara et al. (017))) Few-bit quantization (2 to bits) is of- ten performed by k-means clustering of trained weights with subsequent fine-tuning of the cluster centers (Han et al. (2016)). Pruning and quantization methods have been shown to work well in conjunction (Han et al. (2066). In so-called "ternary" networks, weights can have possible values (negative, zero or positive) which also allows for simultaneous pruning and few-bit quantization (Li & Liu 2016); Zhu et al. (2017)).
of three
Model Encoding refers to exploiting existing compression techniques to improve the space effi- ciency of model storage. These techniques are usually lossless, and compress DNN models via extra encoding. Han et al. (2015) leverages Huffman Encoding to reduce the storage of pruned and quantized DNN models by tens of magnitude. It uses variable-length codewords to encode source symbols. The table is derived from the occurrence probability for each symbol. More com- mon symbols are represented with fewer bits. Huffman Coding the optimal scheme for lossless compression, and Han et al. (2015) shows that it's synergistic with pruning and quantization. Our method aims to provide a more efficient mechanism over Huffman Coding, to optimize the inference performance while keeping DNN models compressed.
Novelty our method comes from the following three aspects, compared with the above three methods. First, prior works from Model Encoding focuses offline storage of DNN models, but our method targets to keep the compression and accelerate the inference during runtime; second, prior works, such as Pruning and Quantization, may cause loss of information, but method is lossless and near optimall, and third, prior works from Pruning and Quantization are not contradictory with method, instead show and demonstrate that they are synergistic with our method.
2

---

Under review as a conference paper at ICLR 2022
3 FORMULATING DNN MODELS
The first stage of our method is to form DNN models appropriately, so that Succinct Data Structures can take advantage of. Succinct Data Structures exploits the delimiters within a long string, to per- form fast queries directly the compressed string. Hence, our method first formulates DNN mod- els as Runtime-Accessible Sequence (RAS), which refers to semi-structured format using a minimal amount of delimiters to construct hierarchical information (e.g. layers). To exploit Succinct Data Structures effectively, we propose two semi-structured formulations to store model details. First, we introduce Element-wise RAS by using delimiters separate different elementary operands within DNN models; and second, we introduce Block-wise RAS by applying delimiters to separate differ- ent sets of data operands within DNN models, based on the related computation kernels. Based on the above Element- wiis and Block wise RAS, we provide specializations to make them synergistic with Pruning and Quantization, which can further improves both the performance and compression rate during inference runtime.
Further
Gemprees
Standard
Pruning QuantizaiQanniiiii
Manner
Outer delimbrr
srrey
Element wise
(t. 1.01 (8, 2.77, 0:13) (8, 0.11), 1.8)
A.
C.
Diszance betweenit and neightor
Block wise
One black
B.
D.
One bleck
240, (2.0)
[R.01,
161), Is, 2770 1D4, e [[8, 0.11, (28, 1.3
Dellnher for blocks
Figure I: A comparison of different kinds of Rumtime-Accessibl Sequence (RAS).
3.1 ELEMENT-WISH RUNTIME-ACCESSIN SEQUENCE
One type of formulation, suggested by our method, is Element-wise Runtime Accessible Sequence (denoted as Element-wise RAS). Element- wise RAS utilizes delimiters to separate elementary data operands. 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 elementary data operands accordingly.
Figure (A) shows an example of Element-wise RAS; there are two vertical bars encompass several elementary operands. This methodology forms the Element-wise RAS, and the number sign used to represent the border of this union. To properly formulate the whole network into Element-wise RAS, concatenate such unions by using a separate delimiter (e.g. ##).
3.2 BLOCK- FLOCK-WISE RUNTIME-ACCESSIBE SEQUENCE
One limitation of Element-wise RAS 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.
Accessibbe
Figure (B) shows an example of Block-wise RAS: the Block- 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, compared with Element-wise RAS.
3

---

Under review as a conference paper at ICLR 2022
3.3 BHUNING-QUANTIZTTUN RAS
The designs of Element/Block-win RAS are still without the consideration of Pruning and Quan- tization. As revealed by prior works, the impacts of these compression schemes can substantially incur huge amount of sparsity within the model storage. Therefore, the designs of RAS need to account for this feature when the models are pruned and/or quantized. We provide generic optimiza- tion to make RAS synergistic with Pruning and Quantization, regardless of Element- or Block-wise. The key insight is 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((D shows examples of the optimized Element-/Block-wiss RAS for Pruning and Quantization.
RAS for Element-wise and Block- wise. The difference hereby is that, we refine the elementary operands as tuples. such a tuple, the first element refers to the relative distance between this and its left neighbor (a number or delim- iter); and the second element stores the value of the corresponding data operand. This approach is synergistic with Pruning and Quantization because: (1) for Pruning, the relative distance, contained in the reshaped tuple, can effectively exploit the pruned model structures; and (2) for Quantization, the values, contained in the reshaped tuple, can enhance the space benefits from quantization.
Figure [TC and (D) shows examples of Truning-Quantizan
4 Succinct Data Structures
After formulating DNN models into RAS, the second stage of our method stores them in Succinet Data Structures during runtime. Succinct Data Structures were first pioneered by Jacobson (1888), which refers to a set of data structures using the nearinffrrattion-teerreee bound space to store the compressed representation, and still provide fast query and access operations directly on these compressed representations. In general, Succinct Data Structures have the following representative inner operators.
Given a string S whose length and alphabet are and a, there are three operations directly on the compression (shown below).
Rank, (x) returns the number of symbol g appearing in So.. where g E a and x < L.
Select, (z) returns the position of z-th occurrence of symbol q in S.
(ccess(z) returns the symbol at the position x S.
Though there are number of Succinct Data Structures available for real-world applications, choose Wavelet Tree (Grossi et al.] (2003) as 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. (2013); Khandelwal et al. (2016). ) Graph Processing (Khandelwal et al. (2177) and etc. Therefore, method deploys WT as the compression technique during the inference runtime.
4.1 WAVELET TREE
Wavelet Tree, a kind of Succinct Data Structures introduced by Grossi et al. (2003), was originally used in compressed suflix arrays. Since its initial use, a myriad of applications has been found. For instance, the wavelet tree could be used representations of sequence, reordering of elements and grid of points (Navarro (2014)). We elaborate the details of WT as follows. Figure 2 gives an example of WT, where the alphabets/subsets are partitioned into pairs of subsets recursively, until the bit-vector can be distinguished by "0" and "1".
As lossless compression method, WT near-optimal. Assume string S (length n) composed of a different symbols: if we use wavelet tree to represent this string, the space consumption is n log(a) + O(n) bits, which is near-optimal to the ixformation-theoreete lower bound. Moreover, WT yields significant potentials for runtime performance. WT allows Rank, Select and Access operators to only take logarithmic time complexity. Following the above assumption: these oper- ations are supported in O(log σ)) time, where is the size of the alphabet for the sequence. Note that the time complexity of these operators are independent to the string length, which can bring significant benefits to the computation without full decompression.
4

---

Under review as a conference paper at ICLR 2022
Original string
abcdddcaabccddcba 0011110000111100
Alphabot a,b,c,d
Bit-vector
Subtett
Subset cd
6,b
abbaabba
cddccddc
01100110
01100110
Subset
Subset
Subset
b
aaaa
bbbb
CCCC
dddd
Figure 2: An example of Wavelet Tree (WT): This is an illustration of WT for the string "abed- dcbaabeddeba". The bitvector for its first layer (i.e. 001111000011 1100) is derived based on the alphabet partition: characters "a" and "b", located in the left subset of the alphabet, are encoded with the bit "O", and the other two characters "c" and "d" are encoded with the bit "1". For two subsets in the next layer, they are recursively divides into smaller subsets, which are "a" "b", "c" and "d".. Then the encoding is continued correspondingly. As a result, all characters can be distinguished by an unique sequence of bits.
MODEL INFERENCE IN Succinct Data Structures
The third stage of our method is to perform model inference via Succinet Data Structures. This stage trivial first retrieve all relevant operands via queries, then decode these operands, and finally perform the computation for model inference. Our methods can yield significant performance ben- efits because the queries on compressed models don't require any decompression. This is because carefully engineering Rank. Select and Access operators allow the queries directly on compres- sion. We restrict each set of decompressed data for one convolution filter at a time. To extract these operands from Succinct Data Structures, we use two Select operators to locate the corresponding values within the compressed representation; and then we use one Access operator to retrieve the values from the range, restricted by the Select operators. In practice, the inference process for wise method slightly differs from that of Block-wise method: Element-wise method can perform the inference by extracting elementary operands individually from WT, and Block-wise method can only perform the inference by extracting aggregated sets of operands. This is because a block the smallest unit for indexes in Block-wise method.
6 EXPERIMENTAL STUDY
We compare Succinct Compression with Huffmman Coding(?), as suggested by Deep Compression (Han et al. (2016)). for four networks: AlexNet (Krizhevsky et al. (212)). Pruned-Quantized AlexNet, VGG-16 Simonyan & Zisserman (201)) and Pruned-Quantizer VGG-16 on ImageNet dataset (Dng et al. (2009)). For Pruning and Quantization, perform the same method suggested by Deep Compression (Han et (2016). Since Succinct Compression is lossless, we find that all models achieve the same level of accuracy, compared with model inference without Succinct Com- pression. We form an extension of Succinct Compression, by replacing Succinct Data Structures with Huffman Encoding as our baseline. All experiments were performed using PyTorch (Paszke)
et al. (2019)) on the Intel Core i7 5930K.
6.1 NEAR-OPTIMAL COMPRESSION DURING INFERENCE RUNTIME
We first examine the impacts of Succinct Compression with AlexNet and VGG-16 (w/out pruning and quantization). Table I and Table 2 show the comparison regarding the statistics of the original model and different compression schemes. We make two observations. First, our method achieves optr-oltimal compression rate among all models. Our methods has the best compression rate of 19.80% for AlexNet and 18.72 88.72% for VGG-16. This is credited to the proper applications of our method using Succinct Data Structures. Second, method achieves significant reduction of layers
5

---

Under review as a conference paper at ICLR 2022
in terms of runtime space. Our method reduces AlexNet from 232.56 MB to 46.04 MB, and VGG-16 from 527.8 MB to 98.82 MB.
Table Compression statistics for AlexNet (No PQ). CR: Compression Rate, HF: Huffman Coding, WT-E: Wavelet Tree via Element- Wise, WT-B: Wavelet Tree via Block-wise.
Layer
Size
Size
Size
Size
CR
CR
CR
(Origin)
(HF)
(WT-E)
(WT-B)
(HF)
(WT-E)
(WT-B)
conv1
0.1333
0.0359
0.0417
0.1239
26.89%
31.32%
92.92%
conv2
1.1729
0.2424
0.3310
0,4118
20.67%
28.22%
35.11%
conv3
3,3765
0.6443
0.9112
0.8559
19.08%
26.99%
25.35%
conv4
2.5327
0,4950
0.6827
0.6629
19.54%
26.96%
26.17%
conv5
1.6885
0.3339
0.4673
0.4741
19.77%
27.68%
28.08%
fc6
144.02
19.99
35.97
27.87
13.88%
24.98%
19.35%
fc7
64.02
9.649
17.99
12.47
15.07%
28.10%
19.48%
fc8
15.63
2.682
4.300
3.177
17.16%
27.51%
20.33%
conv .tttl
8,904
1.751
2,434
2.529
19.67%
27.34%
28.40%
fc_total
223.7
32.327
58.26
43.52
14.45%
26.05%
19.46%
total
232.56
34.07
60.69
46.04
14.65%
26.10%
19.80%
Table 2: Compression statistics for VGG-16 (No PQ). CR: Compression Rate, HF: Huffman Coding, WT-E: Wavelet Tree via Element- Wise, WT-B: Wavelet Tree via Block-wise
Layer
Size
Size (HF)
Size
Size
CR
CR
CR
(Origin)
(WT-E)
(WT-B)
(HF)
(WT-E)
(WT-B)
conv | I_1
0.006834
0.00582
0.00499
0.007865
85.08%
72.92%
115.05%
conv 1 22
0.1409
0.0345
0.04046
0.1159
24.48%
28.72%
82.25%
conv2.1
0.2817
0.0631
0.08107
0.1592
22.38%
28.78%
56.49%
conv2.2
0.5630
0.1160
0.1539
0.2271
20.61%
27.33%
40.34%
conv3.
1.126
0.2153
0.3019
0.3335
19.12%
26.81%
29.62%
conv3_2
2.251
0.3991
0.5959
0.5380
17.72%
26.47%
23.90%
conv3_3
2.251
0.4001
0,5887
0,5404
17.77%
26.15%
24.01% %
conv4_1
4.502
0.7578
1.155
0.9893
16.83%
25.65%
21.97%
conv4
9.002
1,411
2.202
1.843
15.68%
24.46%
20.47%
conv4
9.002
1.423
2.290
1.860
15.80%
25.44%
20.66%
conv5
9.002
1,466
2.437
1.877
16.29%
27.08%
20.85%
conv5
9.002
1.476
2.489
1.851
16.40%
27.65%
20.56%
conv5_3
9.002
1.458
2.501
1.841
16.19%
27.78%
20.45%
fe6 392.0
42.63
121.5
71.75
10.87%
30.98%
18.30%
fc7 64.02
8.642
19.41
11.89
13.50%
30.33%
18.58%
fc8 15.63
2.517
4.526
2.995
16.10%
28.96%
19.16%
conv_tota total
56.13
9.226
14.84
12.18
16.44%
26.44%
21.70%
fc_total 471.7
53.78
145.4
86.64
11.40%
30.83%
18.37%
all_total 527.8
63.01
160.2
98.82
11.94%
30.36%
18.72%
Interestingly, also notice that Block-wise method outperforms Element-wise method in most cases. We find that, Block-wise method saves more space than Element-wise method for FC layers of AlexNet and all layers of VGG-16 in total. This is because Block-wise method can effectively reduce the overall size of the compressed representation, which refers to the required length for bit-encoding to distinguish different values, by using individual bits to represent more operands. However, we also observe that Flement- method saves more space than Block-wise method requires for CONV layers of AlexNet. This is because CONV layers AlexNet are relatively small, where the redundancy of Block-wise Method plays significant role in space consumption.
We then examine the impacts of Pruning and Quantization on Succinct Compression. Table 3 and Table show the comparison regarding the statistics of the pruned and quantized model and dif- ferent compression schemes. We make two observations. First, we find that our method very synergistic with Pruning and Quantization. For Pruned-Quantizee AlexNet/VGG-16, achieves the compression rate with only 1% difference. compared with the optimal solution. Sec- ond, find that Flement-wise method achieves better space savings for both CONV and FC layers.
method

---

Under review as a conference paper at ICLR 2022
For CONV/FC layers, Element-wise method reduces runtime space consumption by 8%/0.5% average, compared with Block-wise method.
Table Compression statisties for AlexNet (w/ PQ). CR: Compression Rate, HF: Huffman Coding, WT-E: Wavelet Tree via Element- Wise, WT-B: Wavelet Tree via Block-wise.
Layer
Size
Size
Size
Size
CR
CR
CR
(Origin)
(HF)
(WT-E)
(WT-B)
(HF)
(WT-E)
(WT-B)
conv1
0.05589
0.0333
0.0371
0.04352
25.08%
27.94%
32.74%
conv2
0.2231
0.1576
0.1856
0.2116
13.44%
15.84%
18.06%
conv3
0.5912
0.4081
0.5473
0.8420
12.09%
16.22%
24.95%
conv4
0.4681
0.3230
0,4304
0.6408
12.76%
17.00%
25.31%
conv5
0.3119
0.2180
0.2888
0.4268
12.92%
17.11%
25.29%
fc6
8.325
4.002
4.685
5.494
2.779%
3.253%
3.815%
fc7
3.697
1.778
2.083
2.448
2.777%
3.255%
3.825%
fc8
1.972
1.011
1.113
1.121
6.473%
7.122%
7.176%
conv total
1.650
1.140
1.489
2.165
12.80%
16.73%
24.31%
fc tott 13.99
6.791
7.881
9.063
3.04%
3.52%
4.05%
all_total
15.64
7.931
9.370
11.23
3.41%
4.03%
4.83%
Table 4: Compression statisties for VGG-16 (w/ PQ). CR: Compression Rate, HF: Huffman Coding, WT-E: Wavelet Tree via Element-Wiss WT-B: Wavelet Tree via Block-wise.
Layer
Size
Size (HF)
Size
Size
CR
CR
CR
(Origin)
(WT-E)
(WT-B)
(HF)
(WT-E)
(WT-B)
convl __
0.001977
0.002652
0,003235
0.002836
40.23%
49.08%
43.02%
conv 1_2
0.01528
0.01983
0.02061
0.02423
14.10%
14.66%
17.23%
conv2_1
0,04790
0,04081
0,04824
0,06328
14.51%
17.15%
22.50%
conv2.2
0.1006
0.07720
0.09635
0.1342
13.73%
17.13%
23.85%
conv3_1
0.2974
0.1920
0.2510
0.3496
17.07%
22.31%
31.07%
conv3.2 _2
0.2700
0.2090
0.2810
0.4303
9.290%
12.49%
19.13%
conv3.3
0.4725
0.3177
0.4210
0.6171
14.12%
18.71%
27.43%
conv4_1
0.7186
0.5048
0.6829
1.0641
11.22%
15.18%
23.65%
conv4_2
1.214
0.8676
1.234
1.959
9.640%
13.72%
21.77%
conv4 3
1,528
1.046
1.454
2.266
11.62%
16.16%
25.17%
conv5
1.576
1.071
1.485
2.306
11.90%
16.49%
25.62%
conv5_2
1.306
0.9176
1.266
2.050
10.20%
14.06%
22.78%
conv5_3
1.622
1.095
1.485
2.350
12.17%
16.50%
26.11%
fc6
10.75
5.430
6.726
7.817
1.385%
1.716%
1.994%
fc7
1.755
0.8897
1.100
1.283
1.390%
1.719%
2.004%
fc8
1.795
0.9485
1.128
1.125
6.071% %
7.219%
7.199%
conv total
9.171
6.361
8,728
13.62
11.33%
15.55%
24.26%
fc total
14.30
7,268
8.954
10.22
1.54%
1.90%
2.17%
all_total 23.47
13.63
17.68
23.84
2.58%
3.35%
4.52%
Note that observation is slightly different from the results from models without PQ. where the results suggest that Block-wise saves more space for FC layers. This is because Pruning and Quan- tization significantly reduces the number of parameters in FC layers, which made the redundancy of Block-wise method becomes the major limiter for compression.
6.2 SPEEDUP-COMPRESSIE RATE TRADEOFF
Rate Tradeoff in Figure for all models. also break down the results all layers, CONV layers and FC layers separately. We find that our method achieves at least 8.65X speedup for the inference of all layers. And for CONV/FC layers, our method achieves speedup 10.47X/1.6X at least, except for the FC layers in VGG-16 without Pruning and Quanti- zation. The exception is because blsck-wise method incurs significant redundancy, since both the alphabet of WT and the amount of parameters huge and grow significantly.
We report the

---

Under review as a conference paper at ICLR 2022
180%
1.N,3320
2015 1180
LUME
122.5
2.5L 1448
10.2000
Huffmann Encoding
Wavelet Tree via Element-wise
Wavelet Tree via Block-wise
(i) All Layers
(ii) CONY Layers
(iii) FC Layers
(A) AlexNet (w/out Pruning Quantization)
68
1521 20-4
5.800
Huffmann Encoding
Wavelet Tree Element-wise
Wavelet Tree Block-wise
(i) All Layers
(ii) CONV Layers
(iii) FC Layers
(B) VGG-16 (w/out Pruning Quantization)
12.0 1200
1.34X
Huffmann Encoding
Wavelet Tree via Element-wise
Wavelet Tree Block-wise
(i) All Layers
(ii) CONV Layers
(iii) FC Layers
(C) AlexNet (w/ Pruning Quantization)
2006
Speeka
Huffmann Encuding
Wavelet Tree via Element-wise
Wavelet Tree via Block-wise
(i) All Layers
(ii) CONV Layers
(iii) FC Layers
(D) VGG-16 (w/ Pruning Quantization)
Rate Tradeoff of Huffman Coding, our Element-wise method, and our Block-wise method among (A) AlexNet (w/out PQ): (B) VGG-16 (w/out PQ): (C) AlexNet (w/ PQ); and (D) VGG-16 (w/ PQ). For each sub-figure, results for (i) all layers; (ii) CONV layers; (iii) FC layers. The y-axis refers to Compression Rate (lower is better), and the x-axis refers to Speedup (higher better).
Figure 3: Opeedup-Comppeedd
Interestingly, for FC layers, we observe variations across compression schemes and models. We make two observations. First, Element-wise method achieves better speedup with worse compres- sion rate for FC layers of models w/out PQ. This is because Element-wise formulation suits better for the structure of FC layers, but also suffers from a huge amount parameters. Second, Element- wise method achieves both better speedup and compression rate for FC layers of models w/ PQ.
8

---

Under review as a conference paper at ICLR 2022
This is because PQ significantly reduces the amount of parameters, which make Element- method more suitable.
6.3 SPEEDUP-LAYER SIZE TRADEOFF
We finally examine the tradeoff between the speedup and layer size among different methods. Note that, after PQ. the permutation of layers from AlexNet remain consistent, but VGG-16 changes slightly CONV layers. We draw two observations. First, the benefits of Element-wise method exhibits more robust trends in CONV layers in most cases, with increasing speedup with the grow- ing layer size, compared with Block-wise method. This is because, compared with Element-wise method, Block-wise method is much more sensitive to both layer size and the layer structure. Sec- ond, PQ significantly varies the tradeoffs between speedup and layer size. This because PQ exploits the structure information to reduce the layer size well as the layer complexity. Therefore, it's expected that the speedup may vary significantly due to PQ.
Speokk
Spodo
sutthan Ercoding vije Wive Comarroittus Waveled Macontte
stubnaa Enarding -iln BemanoWWe Wawser Trea dedolitte
(A) AlexNet (w/out Pruning Quantization)
(B) VGG16 (w/out Pruning Quantization)
Layers
Doooding Alvelir Cormert Winelee
Grooding
Weveles
(C) AlexNet (w/ Pruning Quantization)
(D) VGG16 (w/ Pruning + Quantization)
Figure 4: Speedup-Layer Size tradeoffs among (A) AlexNet (w/out PQ): (B) VGG-16 (w/out PQ);
(C) AlexNet (w/ PQ); and (D) VGG-16 (w/ PQ).
DISCUSSIONS
Though we demonstrate the synergy between our method and Pruning Quantization from Han et al. 2016), different Pruning and Quantization methods are expected to be synergistic well. This is because our method doesn't affect any optimization in terms of model structures and value encoding. as Pruning and Quantization achieves. In addition, our element-wise and block-wise methods can be combined for a single model inference, since can be constructed in a layer-wise manner. As suggested by our results, the layer heterogeneity breeds the needs to combine different formulations to obtain the best tradcoff's between performance and space consumption.
CONCLUSIONS
We present "Succinet Compression" that improves inference performance with compressed neu- ral networks during inference runtime. Our method operates by proper combinations of newly- introduced formulations, Succinct Data Structures and carefully-engineeree inference. our method achieves near-optimal compression results, compared with Huffman Coding. In addi- tion, we reveals that our method achieves significant speedup over Huffman Coding, by exploiting the characteristics of queries directly compression in Succinct Data Structures. We also show that our method is synergistic with Pruning and Quantization, which brings significant performance benefits and space saving at the same time.
show

---

Under review as a conference paper at ICLR 2022
REFERENCES
Rachit Agarwal, Anurag Khandelwal, and Ion Stoica. Succinct: Enabling queries com- pressed data. In 12th USENIX Symposium on Networked Systems Design and Implementa- fion, NSDI 15, Oakland, CA, USA, May 4-6, 2015, pp. 337-350. USENIX Association, 2015. URL https: uswnix..seeee..ooo. http://www..a....oooo..o.eeee/aa presentation/aggee
Yoshua Bengio, Yann LeCun, and Geoffrey E. Hinton. Deep learning for Al. Commun, ACM, 64 (7):58-65, 2021. doi: 10.1 14.44444444250 URL/ittss//bo..org/10..11
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- Ylniv,,,, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to or 11, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pp. 248-255 IEEE Computer Society, 2009. doi: (0009//VVP.2009.52000000
//oii//ooi/ http:///oo..org//// /10
11C9/CVPR. 2009. 5206848
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 Algorithms, SODA '03, pp. 841-850, USA, 2003. Society for Industrial and Applied Mathematics. ISBN 0898715385.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp-
1379-1387, 2016. URL httpppps//ppcccceiiggg....o///s/ neuriiss........................ wttpp/ppee//////aaae..ee
2B2314191102ceelaaec3333333 6ddd Abstract html
Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural networks. arXiv preprint arXiv: (506 2015.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained guantization 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. 2016. 151 00149
Song Han, Jeff Pool, Sharan Narang, Huizi Mao, Enhao Gong, Shijian Tang, Erich Elsen, Peter Va- jda, Manohar Paluri, John Tran, Bryan Catanzaro, and William J. Dally. DSD: seseee-paase-ddee training for deep neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. httpt:
net www.eeeoooiddaaeeeeeeeeeee
9x1
Babak Hassibi and David G. Stork. Second order derivatives for network prun- ing: Optimal brain surgeon. In Stephen Jose Hanson, Jack D. Cowan, and C. Lee Giles (eds.), Advances in Neural Information Processing Systems 5. [NIPS Con- ference, Denver, Colorado, USA, November 30 December 3, 1992], pp. 164- Morgan Kaufmann, 1992.
171.
URL http::/ nips wttpppppepccpppe///pepppppppcc.c
647-
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. J. Mach.
Learn. Res., 18:187:1-187:30, 2017. URL http: fmlr wttppppprs//u111111-52553
html
Guy Joseph Jacobson. Succinct Static Data Structures. PhD thesis, USA, 1988. LAT8918056.
10

---

Under review as a conference paper at ICLR 2022
Theofanis Karaletsos and Gunnar Rätsch. Automatic relevance determination for deep generative models, 2015.
Anurag Khandelwal, Rachit Agarwal, and Ion Stoica. Blowfish: Dynamic storage-performance tradeoff in data stores. Katerina J. Argyraki and Rebecca Isaacs (eds.). 13th USENIX Syn-
posium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara. CA, USA,
March 18, 2016, pp. 485-500. USENIX Association, 2016. URL httpttss: //ww www. usenix.
org/confereece//nne http://///nnn//////ceeecec 1 - onn possssons//reseettaaiiiooo wwwandd//aaaeeeeee wa
Anurag Khandelwal, Zongheng Yang, Evan Ye, Rachit Agarwal, and lon Stoica. Zipg: A memory-efficient graph store for interactive queries. In Proceedings of the 2017 ACM Inter- national Conference on Management of Data, SIGMOD Conference 2017, Chicago, H. USA, May 14-19, 2017, pp. 1149-1164. ACM, 2017. doi: 10. 00.114//335918830640000 URL https: 7/doi. 10. 11A.111355911111 3064012
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep con- volutional neural networks. In Peter L. Bartlett, Fernando C. N. Percira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger (eds.), Advances Neural Information Pro- cessing Systems 25: 26th Annual Conference Neural Information Processing Systems 2012. Proceedings of meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pp. 1116-1114, 2012. URL htttps::/prrcceeete Abstract. Ats .tml
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In David S. Touretzky (ed.), Advances Neural Information Processing Systems 2, (NIPS Conference, Denver, Colorado, USA, November 27-30, 1989], pp. 598-605. Morgan Kaufmann, 1989. BtRp:tt:://ppeent nips. www.cc/ppppppaeeeee 250 ipptimal brain damage
Fengfu Li and Bin Liu. Ternary weight networks. CoRR, abs/1605.04411, 2016. URL http:
Mackay and J. C. David. Probable networks and plausible predictions - review of practical
bayesian methods for supervised neural networks. Network Computation in Neural Systems, 6(3), 1995.
Gonzalo Navarro. Wavelet trees for all. Journal of Discrete Algorithms, 25:2-20, 2014. ISSN 1570-8667. doi: http:///e.....eeeeeaa///////611. sciencedirect. www./cccenee Symposium on Combinatorial Pattern Matching.
004. URL https://ww/ 23rd Annual
R. M. Neal. Bayesian learning for neural networks. Lecture Notes in Statistics, 1996.
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 Veti,o, 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' A'Ach-BBuc, Emily Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8035, 2019, URL bdbca288fee (EwE77E292EEEEE22222222222 -btett0--bbbrttttceee html
neurips.. cc pttppppppp///aaaaeeeeee
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling (eds.). Computer Vision - ECCV 2016 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV, volume 9908 of Lecture Notes in Computer Science, pp. 525-542, Springer. 2016. doi: 10. 11100007777--19994444 46493-01, 32, URI. hhtpps://dot .rgg 100 C. 1007 3-0---33-999-9-----111
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning
11

---

Under review as a conference paper at ICLR 2022
Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015. URL http: /ttp//aaxvvvv...///.//.....a.av. org abs 1409. 1556
Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S. Emer. Efficient processing of deep neural networks: A tutorial and survey. Proc. IEEE, 105(12):295-2329) 2017. doi: 10.1 10.1/09/PRRC. 2017.2761740, URL https: org/ 1109/ JPROC. 2017 27777774)7
Shuchang Zhou, Zekun Ni, Xinyu Zhou, He Wen, Yuxin Wu, and Yuheng Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. CoRR, abs/1606.06160,
2016. URLtttt::/aaxxi wwtpxiii.orggaao. 1606.666600 C6160
Chenzhuo Zhu, Song Han, Huizi Mao, and William J. Dally. Trained ternary quantization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.nntt 2017. URLhttps: hatps:///ppeneee //tp///eeeeeee.eeee/eee
net her/forum? 1d= 1aatruumdd__1_pAUu_
12


Reviews:
[{"review_id": "fIF7EWWlO_r", "reviewer": "Reviewer_eHWE", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The idea of enabling inference directly on the compressed model without decompression is quite interesting. However, I could not verify if the proposed method indeed shows any improvement in runtime speedup or compression rate, or accuracy by looking at the experimental results. It is also not very straightforward to me that there must be a speedup without any empirical support because all the weights need to be queried for inference and I do not see how this is different from decompression. Here are my main concerns and questions:  \n\n- The paper is not very easy to follow and needs significant improvement in writing. There are repeating sentences, many typos, and the general flow is not very fluent. I especially recommend making Section 3 more clear since it is the most important section of the paper and some concepts need to be better explained by providing some background information.\n\n- I believe the related work section misses many references, especially in the model encoding part, which is the most related direction to this paper. For example, [1], [2], [3], and [4] would be good candidates for the related work section since they also propose new methods to encode neural network models. \n\n- The authors compare their work with Huffman coding in Deep Compression paper [5]. However, there are more recent methods such as [1], [2], [3], and [4] that are directly comparable. A comparison with these papers would strengthen the paper.\n\n- The authors claim that their method is near-optimal but they do not provide any reason as to why this is the case. In Section 4.1, they mention that the space consumption is $n \\log(\\sigma) + O(n)$ bits and claim that this is near-optimal to the information-theoretic lower bound. A $n \\log(\\sigma)$ space consumption is actually an upper bound, which is exact only when the weights are uniformly distributed. There are several empirical results that show that weights are not uniformly distributed, e.g., [2] shows that trained weights look Laplacian. Therefore, the proposed method has a space consumption close to the worst-case estimate of the entropy, which is not close to the optimal model compression since we know that weights are not uniform. \n\n- $\\sigma$ is used for both the alphabet and the alphabet size in different places. It would be nice to fix this to avoid confusion.\n\n- There are some missing citations. For example Huffman Coding(?) in page 5. \n\n- Maybe most importantly, the authors claim in Section 6.1 that the proposed method has the best compression rate of $19.8$% for AlexNet and $18.72$% for VGG-16.  However, by looking at Tables 1 and 2, the only baseline (Huffman Coding) has a better compression rate of $14.65$% and $11.94$%, respectively. It means that the text and the results in the tables are not consistent, and the proposed method underperforms Huffman Coding. \n\n- I find the following sentence from the paper very confusing: \"For Pruned-Quantized AlexNet/VGG-16, our method\nachieves the compression rate with only $1 \\%$ difference, compared with the optimal solution.\". Can the authors explain what the optimal solution here is? \n\n\n[1] Wiedemann, Simon, et al. \"Deepcabac: Context-adaptive binary arithmetic coding for deep neural network compression.\" arXiv preprint arXiv:1905.08318 (2019).\n\n[2] **v1 of** Isik, Berivan, Albert No, and Tsachy Weissman. \"Rate-Distortion Theoretic Model Compression: Successive Refinement for Pruning.\" arXiv preprint arXiv:2102.08329 (2021).\n\n[3] Havasi, Marton, Robert Peharz, and José Miguel Hernández-Lobato. \"Minimal random code learning: Getting bits back from compressed model parameters.\" arXiv preprint arXiv:1810.00440 (2018).\n\n[4] Oktay, Deniz, et al. \"Scalable model compression by entropy penalized reparameterization.\" arXiv preprint arXiv:1906.06624 (2019).\n\n[5] Han, Song, Huizi Mao, and William J. Dally. \"Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.\" arXiv preprint arXiv:1510.00149 (2015).", "summary_of_the_paper": "This paper aims to improve the runtime of NN inference via a novel DNN compression idea. Specifically, the authors propose an approach that allows fast queries at inference directly on the compressed model without decompressing the model back. They show comparisons to prior work on AlexNet andVGG16 architectures.", "summary_of_the_review": "Overall, I think the paper is not ready for publication due to the reasons I listed in the previous section. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "avWBm2Mp74J", "reviewer": "Reviewer_R8Un", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Paper strengths:\n\n+ The idea of proposing a different data structure to store a neural network is novel for accelerating inference.\n\n+ The paper shows good performance in the experimental part compared to the Huffman encoding.\n\n\nPaper weaknesses: \n\n- Claim on decompress compressed model requirement: There is a plethora of prior work that does not require the model to be decompressed during inference. For instance, distillation approaches, as well as factorization and pruning methods. The paper is motivated by a claim, which does not hold based on the prior work. This is also reflected in the experimental section which prior works from the aforementioned categories are completely ignored in the comparisons with the prior work. The claims of the work are a major limitation.\n\n- The proposed data structure for the neural network is method agnostic. It would help the paper to perform experiments based on several quantizations and pruning approaches. This experiment would add a significant value to the work.\n\n- The main contribution is how to formulate the compressed neural network (in terms of data structure) to accelerate the inference. This idea is not quite clear after reading the paper. Overall, the writing part needs some improvement to improve the clarity of the work.\n\n- Related work on lossless compression: It is important to extensively discuss the related work on lossless compression and memory-efficient deployment. A few useful references:\n\t- Lossless Compression of Structured Convolutional Models via Lifting (2021).\n\t- Lossless Compression of Deep Neural Networks (2020).\n\t- Universal deep neural network compression (2020).\n\t- Hardware-Based Real-Time Deep Neural Network Lossless Weights Compression (2020)\n\t- Compact and Computationally Efficient Representation of Deep Neural Networks (2019).\n\n- Prior work comparisons: There is only one comparison with the Huffman encoding. It would be helpful to include more approaches (see above). \n\n- It would be helpful to include a ResNet-like architecture since it is the standard to be used nowadays. \n\n\nImprovements:\n\n- The claims in the introduction could be supported by references.\n\n- \"As revealed by prior works, the impacts of these compression schemes..\" references are missing.\n\n- The quality of the figures, e.g. Fig 1/2/3, is poor. Rendering on a better resolution is recommended. ", "summary_of_the_paper": "It is presented an approach to store a compressed deep neural network in a form that allows fast inference. The deep neural network is defined as an element- and block-wise Runtime Accessible Sequence (RAS). Moreover, the RAS elementary operands are defined as tuples to account for parameter quantization and pruning. Given the neural network RAS formulation, succinct data structures, i.e. wavelet tree, are used to store the network during inference.  The approach is evaluated on AlexNet and VGG-16 architectures which are quantized and pruned. The results are promising compared to the Huffman encoding. ", "summary_of_the_review": "Overall, the paper presents an interesting idea. It is relatively easy to follow it, but the clarity of the paper needs improvement. The experimental part needs additional work, as already discussed. There are major claims which might need to be reformulated. There are also missing references at different points. Overall, the work is not ready for publication yet.", "strength_and_weaknesses": "", "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": "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": "DkygIf4f9Wq", "reviewer": "Reviewer_QdUC", "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": "The paper discusses an interesting and important problem and proposes what appears to be a novel approach. There are two main issues for me at the moment 1) it is difficult to understand the precise scheme that has been proposed, and 2) the evaluation seems very limited and somewhat unclear.\n\n1. To confirm, pruning and quantization was performed but only to the point that the model accuracy did not change? \n2. What were the results of quantization? \n3. When pruning/quantization is applied, wouldn't it be clearer to use 15.64MB as the new baseline and report CR compared to this. Claiming \"only 1% difference\" hides the fact that the HF model size = 6.8 and with WT-B it is 9.063. Obviously, the overall CR is low if you compare to the original model size of 232MB.\n4. Again, results for the performance of the quantized and quantized/pruned models would be of interest, but I don't think are presented? (i.e. without your compression scheme). There are many simple data formats suitable for stored sparse data of course (e.g. using sparsity maps or Z-RLC, CSC/CSR perhaps). Would these be faster but use slightly larger models?\n5. You don't compare to other simple compression schemes, e.g. Dynamic Prediction Reduction (DPRed) perhaps? \n6. Are there variations of the Wavelet-tree scheme that could have been evaluated?\n7. I don't think you can say Huffman encoding is strictly optimal? \n8. Speedups are achieved through the reduction of memory traffic I assume, what is the overhead of accessing these compressed formats? e.g. if applied to a small model that fitted in the cache? I assume the architecture of the target processor has a big impact here too and the overhead will perhaps be smallest on the desktop style processor you target. How would the results differ on embedded cores for instance?\n\nLow-rank approximation would be another technique to discuss or compare to perhaps.\n\nI found some parts of the paper to be difficult to follow unfortunately, e.g. page 3. I suspect this is quite simple, but I struggled. Perhaps better diagrams or an example would help.\n\nThe bitmap Figures are also very difficult to see (e.g. Figure 1 and Figure 3 - the y-axis could perhaps cover a smaller range, avoding bitmaps would help too.\n\nI understand the technique is lossless, but it would perhaps still be useful to confirm the model accuracy. \n\nminor:\n* \"aimming\"\n* missing reference for Huffman \"(?)\"\n", "summary_of_the_paper": "The paper explores the compression of weights in a DNN. The compression technique presented permits the uncompressed values to be easily recovered without first decompressing the data. The approach appears to take advantage of Wavelet Trees after the data has been structured in some way. \n\nResults are presented showing compression rates (vs. Huffman encoding) and speedups on a CPU. ", "summary_of_the_review": "I feel that the description of the work needs to be improved. The evaluation also needs improvement. For these reasons I am recommending the paper is rejected.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0Zeo8Oj0i0u", "reviewer": "Reviewer_G6tm", "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": "Strengths:\n\n- The paper explores an interesting idea to perform lossless compression for efficient DNN inference.\n- The proposed method seems to be able to achieve a better compression rate than Huffman Coding, a compression technique used in DeepCompression from Han et al. 2015.\n\nWeaknesses:\n- The missing discussion of related work makes the significance of the contribution questionable. \n- The comparison with existing work is weak.\n- The paper lacks details on how speedups are measured, which is important for model inferencing. \n- Writing needs to be improved. \n", "summary_of_the_paper": "The paper introduces a method to compress DNN networks with succinct data structures for efficient inference. The paper claims that DNN inference suffers from a storage bottleneck and proposes a lossless compression scheme using wavelet trees to reduce the size of DNN models. The paper performs an evaluation of the proposed method on AlexNet/VGG-16 and shows that the method outperforms existing methods for compressing models using Huffman Coding. ", "summary_of_the_review": "The paper explores an interesting idea for compressing DNN networks, e.g., through lossless compression. This could be potentially quite impactable but the current state of the paper raises several concerns:\n\n1. There have been significant missing discussions related to model compression. In particular, if we look that the related work section, it is very weird that most of the cited papers in Section 2 are work done prior to 2017, whereas there have been vast advancements for model compression in the past several years that the paper seems to choose to ignore, such as [1-3]. Of course, many existing compression techniques are not lossless in theory, but they often achieve comparable performance as the original model, e.g., quantization, that cannot be dismissed completely. \n\n2. The evaluation section is weak. The comparison is made primarily with the Huffman coding method used in Deep Compression [4], which was done six years ago and no longer represents the state-of-the-art. Furthermore, the evaluation was also done on AlexNet and VGG, both of which have been heavily studied. To be more convincing, the paper should compare at least with some lossy compression techniques such as integer quantization and one more advanced model architecture such as ResNet and Transformers. \n\n3. The paper lacks descriptions of implementations and how speedups are calculated. Is the speedup measured through proxies or measured execution time? Is Succinct Data structure GPU hardware friendly? How does it perform on GPU in comparison with models served via cuDNN?  What are the implementations used for the baseline? \n\n4. The paper would benefit from thorough proofreading.\n\nTypos:\n1. Missing references, e.g. Huffman Coding (?), in the first paragraph of Section 6. \n\n[1] Dong et al. HAWQ: Hessian AWare Quantization of Neural Networks with Mixed-Precision, https://arxiv.org/abs/1905.03696, 2019\n\n[2] Choudhary et al. A comprehensive survey on model compression and acceleration, 2020\n\n[3] Deng et al. A comprehensive survey on model compression and acceleration, 2020\n\n[4] Cho et al. On the Efficacy of Knowledge Distillation, 2019\n\n[5] Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding, Han et al., 2015, https://arxiv.org/abs/1510.00149", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Summary

The paper proposes a technique that enables inference directly on a compressed model without decompressing the model.

### Discussion

- Strengths
  - An important problem as well as a compelling direction, namely inference without decompression.
 
- Weaknesses: 
  - The reviewers provided a number of both broad and specific criticisms of the work. 
  The most salient point is the lack of comparison to modern baselines.  Notably, the primary comparison is to a 2015 technique that, while seminal, has since been followed by significant related work (e.g, that identified by Reviewer eHWE, R8Un, and G6tm). In concert, the evaluation should consider at least one more contemporary network in the domain, such as a ResNet.

### Recommendation

I recommend Reject.  At current, this work is the first step in a strong, compelling direction. However, the work needs to be contextualized within a more modern context of contemporary results
Decision: Reject