Doping: A technique for Extreme Compression of LSTM Models using Sparse Structured Additive Matrices

Urmish Thakker, Paul N. Whatmough, Zhi Gang Liu, Matthew Mattina, Jesse G. BeuMLSys 2021 · OpenReview

Introduction

The proliferation of Large Language Models (LLMs) and Long Short-Term Memory (LSTM) networks has revolutionized natural language processing. However, the massive parameter counts of these models pose significant challenges for deployment on resource-constrained edge devices such as smartphones and IoT hardware. While various compression techniques exist, they often face a trade-off between hardware efficiency and model accuracy.

Standard approaches like random pruning create sparse matrices that are difficult to accelerate on commodity hardware because they do not align with standard linear algebra libraries. Conversely, structured matrices, such as Kronecker Products, offer extreme memory efficiency but act as a "mathematical straightjacket," forcing parameters into rigid relationships that often degrade accuracy on complex tasks.

The Doping Framework

To address these limitations, researchers have introduced "Doping," a technique that represents a weight matrix $W$ as the sum of a rigid structured matrix and a highly sparse additive matrix.

Comparison between conventional Kronecker products and the proposed Doped Kronecker Product (DKP).

The core formulation is $W = W_k + W_s$, where:

  • $W_k$ is a Kronecker Product, generated from two much smaller matrices. This component provides the bulk of the compression.
  • $W_s$ is a "doped" sparse matrix. It begins as a dense matrix during training and is gradually pruned until only 1–5% of its values remain.

This sparse component acts as an "escape valve," allowing a small subset of parameters to diverge from the strict Kronecker structure to capture nuanced patterns that the rigid matrix would otherwise miss.

Overcoming Training Challenges: CMA and CMR

Integrating these two types of matrices presents a unique optimization challenge known as Co-Matrix Adaptation (CMA). During early training, the model tends to become "lazy," relying disproportionately on the flexible, dense $W_s$ because it is easier to optimize than the rigid $W_k$. Consequently, when $W_s$ is pruned later in the training cycle, the model's performance often collapses because $W_k$ never learned the necessary underlying logic.

To solve this, the authors developed Co-Matrix Dropout Regularization (CMR). This scheme involves randomly dropping entire rows from either $W_k$ or $W_s$ during training. By occasionally "hiding the calculator" (the sparse matrix), CMR forces the structured matrix $W_k$ to learn independently, ensuring the model remains robust even after the doped parameters are pruned to their final sparse state.

Experimental Evaluation

The Doped Kronecker Product (DKP) method was evaluated across several benchmarks, including the Penn Treebank (PTB) for language modeling, English-Vietnamese translation, and ImageNet for CNN generalization.

Key Results:

  • Compression and Accuracy: On the Medium LSTM benchmark, DKP achieved 25× compression with a perplexity of 83.2, nearly matching the uncompressed baseline of 82.1. It outperformed standard pruning and low-rank methods by over 8% in accuracy at equivalent compression levels.
  • Hardware Performance: Unlike random pruning, DKP is hardware-friendly. On a Raspberry Pi 4, DKP models delivered an inference speedup of 2.5× to 5.5× compared to uncompressed baselines by leveraging optimized BLAS (Basic Linear Algebra Subprograms) libraries.
  • Generalization: The technique successfully improved a quantized AlexNet's top-1 accuracy by 3.1% with only 1% doping, demonstrating its utility beyond LSTMs.

Conclusion

Doping provides a powerful middle ground between the rigidity of structured matrices and the inefficiency of random pruning. By allowing a small amount of "rebellion" in the parameter space, DKP enables high-performance deep learning on the edge. Future work will focus on optimizing training overhead—currently 2–3× slower due to initial matrix density—and scaling the technique to modern Transformer architectures.

Summary updated

BibTeX
@inproceedings{thakker2021doping,
  author = {Urmish Thakker and Paul N. Whatmough and Zhi Gang Liu and Matthew Mattina and Jesse G. Beu},
  title = {{Doping: A technique for Extreme Compression of LSTM Models using Sparse Structured Additive Matrices}},
  booktitle = {MLSys},
  year = {2021},
  url = {https://openreview.net/forum?id=KkRd28xbBx},
}
Figure