Double Viterbi: Weight Encoding for High Compression Ratio and Fast On-Chip Reconstruction for Deep Neural Network

Daehyun Ahn, Dongsoo Lee, Taesu Kim, Jae-Joon KimICLR 2019 · OpenReview

Deep Neural Networks (DNNs) are notoriously memory-hungry, making their deployment on resource-constrained edge devices a significant challenge. While weight pruning—removing unnecessary connections—is a standard solution, it introduces a new headache: index overhead. To know which weights were kept, the system must store their coordinates. Traditional formats like Compressed Sparse Row (CSR) often spend more memory on these indices than on the weights themselves.

Furthermore, these sparse formats are difficult to process in parallel. Standard hardware thrives on dense, predictable data; jumping around a sparse matrix to find non-zero values creates a sequential bottleneck that slows down inference. To address both the high-ratio compression and fast, parallel on-chip reconstruction, researchers have introduced the Double Viterbi compression framework.

The Double Viterbi Pipeline

The "Double Viterbi" approach uses the Viterbi algorithm to encode both the locations (indices) and the values of weights in a neural network. The framework operates through a three-stage pipeline:

The Double Viterbi compression pipeline.
  1. Viterbi-based Pruning: Instead of simply cutting the smallest weights, the system uses a Viterbi decompressor (VD) to generate a structural mask. The Viterbi algorithm selects the "best" mask from a set of hardware-generatable options to minimize accuracy loss.
  2. Multi-bit Quantization: The remaining non-zero weights are quantized into multiple binary codes (e.g., 3 bits per weight) using an alternating quantization method.
  3. Viterbi Weight Encoding: This is the "Double" part of the framework. The authors use a second Viterbi process to encode the quantized weight bits.

Crucially, the weights that were pruned in the first step are treated as "Don't Care" terms. When the Viterbi encoder tries to match a target bitstream, it can pick any value for the pruned slots. This mathematical flexibility significantly increases the probability of finding a compressed bitstream that perfectly (or near-perfectly) matches the important, unpruned weights.

Hardware Reconstruction and Parallelism

Because Viterbi decoding is based on a simple state machine, it is easy to implement multiple decoders on a single chip. This allows the hardware to reconstruct the dense weight matrix in parallel, bypassing the sequential bottleneck of traditional sparse formats.

Parallel reconstruction of the dense weight matrix using multiple Viterbi Decompressors.

On the hardware side, the compressed data is sent to the chip, where multiple Viterbi Decompressors work in parallel to "expand" the bitstream back into a dense matrix of weights just-in-time for computation. The authors found that "alternating quantization" produces a distribution of -1 and +1 bits that is roughly 50/50. This perfectly matches the behavior of Viterbi decompressors, which naturally act like random number generators with a 50% probability for each bit.

Key Results

The authors evaluated their method across several domains, including Language Modeling (PTB and WikiText-2 using LSTMs), Image Classification (CIFAR-10 using VGG-9), and Machine Translation (WMT En→De and De→En using GNMT). The results demonstrate significant improvements in both storage and speed:

  • Massive Compression: For state-of-the-art LSTM models on PTB and WikiText-2, the parameter storage was compressed by 19× compared to the uncompressed baseline—a nearly 95% reduction in memory footprint.
  • Hardware Acceleration: Using a cycle-level simulator, the authors showed that their reconstruction scheme can feed parameters to processing elements 20% to 106% faster than reading uncompressed dense values directly from DRAM.
  • Accuracy Preservation: Despite heavy compression, the models maintained their performance. On the GNMT translation task, the BLEU score degradation was negligible (less than 1 point) while achieving 16× compression.
  • Superiority over Prior Art: Compared to the original Viterbi pruning (which only compressed indices), Double Viterbi reduced the total model size by an additional 78% to 90%.

Limitations and Future Work

While highly effective, the Double Viterbi framework does come with trade-offs. The method requires a multi-stage retraining process (prune, quantize, encode, and fine-tune) to recover accuracy, making the training pipeline more complex and time-consuming.

Additionally, the speed benefits are only realized on hardware equipped with custom Viterbi Decompressor (VD) units. While these units are relatively simple (flip-flops and XOR gates), they are not present in standard off-the-shelf CPUs or GPUs. Finally, while the "Don't Care" terms help, some weight bits might still be encoded incorrectly. The authors handle this by storing a small number of "flip-bit" locations to correct errors on-chip, adding a minor layer of complexity to the reconstruction logic.

Summary updated

Abstract

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 19x 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.
BibTeX
@inproceedings{ahn2019double,
  author = {Daehyun Ahn and Dongsoo Lee and Taesu Kim and Jae-Joon Kim},
  title = {{Double Viterbi: Weight Encoding for High Compression Ratio and Fast On-Chip Reconstruction for Deep Neural Network}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=BbSMwo6jVzZ},
}
Figure