IDKM: Memory Efficient Neural Network Quantization via Implicit, Differentiable k-Means

Sean Jaffe, Ambuj K. Singh, Francesco BulloarXiv 2023 · DOI · arXiv

Abstract

Differentiable $k$-Means (DKM) is a powerful technique for quantization-aware training, yet it is severely limited by a "memory wall" caused by storing intermediate clustering states for backpropagation. We introduce Implicit Differentiable $k$-Means (IDKM), which reformulates soft $k$-means clustering as a fixed-point problem. By applying implicit differentiation, IDKM achieves constant memory complexity relative to clustering iterations. This allows for full convergence during training and enables the quantization of large-scale models like ResNet18 on standard hardware. Our results demonstrate that IDKM maintains or improves accuracy while significantly reducing training time and memory overhead.

Introduction

Deploying deep neural networks on edge devices requires aggressive compression. Quantization—limiting weights to a small set of unique values (a codebook)—is a primary solution. Differentiable $k$-Means (DKM) recently emerged as a state-of-the-art approach by integrating soft $k$-means clustering into the training loop. However, DKM requires storing the results of every clustering iteration to compute gradients, leading to an explosion in memory usage. This constraint often forces practitioners to use fewer iterations, sacrificing convergence, or limits the method to small models.

Methods: Implicit Differentiable $k$-Means

IDKM addresses the memory bottleneck by framing soft $k$-means as a fixed-point problem: $C^* = F(C^*, W)$, where $C^*$ represents the converged cluster centers and $W$ the weights. Instead of backpropagating through the entire unrolled loop of the clustering algorithm, IDKM employs implicit differentiation.

This mathematical shift allows the gradient of the converged centers to be calculated using only the final state, decoupling memory complexity from the number of iterations ($t$). The memory requirement drops from $O(t \cdot m \cdot 2^b)$ to $O(m \cdot 2^b)$.

Furthermore, the authors propose IDKM-JFB, which utilizes Jacobian-Free Backpropagation. By using a zeroth-order approximation to avoid the expensive matrix inversion typically required by implicit differentiation, IDKM-JFB significantly accelerates the backward pass.

Experimental Results

The authors evaluated IDKM on MNIST (using a small CNN) and CIFAR-10 (using ResNet18).

Efficiency and Speed

On the MNIST benchmark, IDKM demonstrated substantial improvements in training efficiency. IDKM-JFB, in particular, proved to be the fastest method, consistently outperforming DKM across various compression regimes.

Training time comparison on MNIST. IDKM-JFB shows significant speedups over DKM.

Scalability to Large Models

The primary advantage of IDKM is its scalability. In experiments with ResNet18 on CIFAR-10, DKM was unable to complete training on the available hardware, running out of memory after only 5 iterations—insufficient for effective learning. In contrast, IDKM and IDKM-JFB successfully quantized the 11.1-million-parameter model to high accuracy by running clustering to full convergence.

Top-1 accuracy on ResNet18 (CIFAR-10). IDKM and IDKM-JFB scale to large models where DKM exceeds memory limits.

Conclusion and Future Work

IDKM overcomes the "memory wall" of differentiable clustering, making high-quality quantization accessible for modern architectures. By decoupling the forward clustering iterations from backward gradient memory, it enables better convergence and faster training. Future work may explore more complex temperature annealing schemes and investigate the stability of implicit differentiation in diverse architectural settings.

Summary updated

Abstract

Compressing large neural networks with minimal performance loss is crucial to enabling their deployment on edge devices. (Cho et al., 2022) proposed a weight quantization method that uses an attention-based clustering algorithm called differentiable $k$-means (DKM). Despite achieving state-of-the-art results, DKM's performance is constrained by its heavy memory dependency. We propose an implicit, differentiable $k$-means algorithm (IDKM), which eliminates the major memory restriction of DKM. Let $t$ be the number of $k$-means iterations, $m$ be the number of weight-vectors, and $b$ be the number of bits per cluster address. IDKM reduces the overall memory complexity of a single $k$-means layer from $\mathcal{O}(t \cdot m \cdot 2^b)$ to $\mathcal{O}( m \cdot 2^b)$. We also introduce a variant, IDKM with Jacobian-Free-Backpropagation (IDKM-JFB), for which the time complexity of the gradient calculation is independent of $t$ as well. We provide a proof of concept of our methods by showing that, under the same settings, IDKM achieves comparable performance to DKM with less compute time and less memory. We also use IDKM and IDKM-JFB to quantize a large neural network, Resnet18, on hardware where DKM cannot train at all.
BibTeX
@misc{jaffe2023idkm,
  author = {Sean Jaffe and Ambuj K. Singh and Francesco Bullo},
  title = {{IDKM: Memory Efficient Neural Network Quantization via Implicit, Differentiable k-Means}},
  year = {2023},
  eprint = {2312.07759},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.07759},
}
Figure