DOUBLE VITERBI: WEIGHT ENCODING FOR HIGH COMPRESSION RATIO AND FAST ON-CHIP RECON- STRUCTION FOR DEEP NEURAL NETWORK
Weight pruning has been introduced as an efficient model compression technique. Even though pruning removes significant amount of weights in a network, memory requirement reduction was limited since conventional sparse matrix formats require significant amount of memory to store index-related information. Moreover, computations associated with such sparse matrix formats are slow because sequential sparse matrix decoding process does not utilize highly parallel computing systems efficiently. As an attempt to compress index information while keeping the decoding process parallelizable, Viterbi-based pruning was suggested. Decoding non-zero weights, however, is still sequential in Viterbi-based pruning. In this paper, we propose a new sparse matrix format in order to enable a highly parallel decoding process of the entire sparse matrix. The proposed sparse matrix is constructed by combining pruning and weight quantization. For the latest RNN models on PTB and WikiText-2 corpus, LSTM parameter storage requirement is compressed 19× using the proposed sparse matrix format compared to the baseline model. Compressed weight and indices can be reconstructed into a dense matrix fast using Viterbi encoders. Simulation results show that the proposed scheme can feed parameters to processing elements 20 % to 106 % faster than the case where the dense matrix values directly come from DRAM.
Summary:
This paper addresses the computational aspects of Viterbi-based encoding for neural networks. 
In usual Viterbi codes, input messages are encoded via a convolution with a codeword, and then decoded using a trellis. Now consider a codebook with n convolutional codes, of rate 1/k. Then a vector of length n is represented by inputing a message of length k and receiving n encoded bits. Then the memory footprint (in terms of messages) is reduced by rate k/n. This is the format that will be used to encode the row indices in a matrix, with n columns.  (The value of each nonzero is stored separately.)  However, it is clear that not all messages are possible, only those in the "range space" of my codes. (This part is previous work Lee 2018.) 
The "Double Viterbi" (new contribution) refers to the storage of the nonzero values themselves. A weakness of CSR and CSC (carried over to the previous work) is that since each row may have a different number of nonzeros, then finding the value of any particular nonzero requires going through the list to find the right corresponding nonzero, a sequential task. Instead, m new Viterbi decompressers are included, where each row becomes (s_1*codeword_1 + s_2*codeword2 + ...) cdot mask, and the new scalar are the results of the linear combinations of the codewords. 
Pros:
 - I think the work addressed here is important, and though the details are hard to parse and the new contributions seemingly small, it is important enough for practical performance. 
 - The idea is theoretically sound and interesting.
Cons: 
 - My biggest issue is that there is no clear evaluation of the runtime benefit of the second Viterbi decompressor. Compressability is evaluated, but that was already present in the previous work. Therefore the novel contribution of this paper over Lee 2018 is not clearly outlined.
 - It is extremely hard to follow what exactly is going on; I believe a few illustrative examples would help make the paper much clearer; in fact the idea is not that abstract. 
 - Minor grammatical mistakes (missing "a" or "the" in front of some terms, suggest proofread.)