Shrinking Models by Sharing Weights — K-Means-based Quantization

Do we really need all 32 bits per number?

In the previous post, while taking data types apart, we noticed something: a neural network’s weights are usually clustered densely near zero with long tails. That invites a natural question.

With so many weights holding similar values, do we really have to store each one as its own 32-bit float?

What if we group similar values into one bucket and replace them with a single representative value? For example, 2.09, 2.12, 1.92, 1.87 are all “roughly 2.0”. We can replace all four with a single 2.00, and at each position just record an index saying “which representative to use”.

This is the core idea of K-Means-based weight quantization. The 2016 Deep Compression paper¹ proposed it and shrank models by tens of times with almost no accuracy loss.

---

The idea: sharing weights via clustering

There are three steps.

1. Cluster — group all weights into $k$ clusters with K-Means.
2. Codebook — store each cluster’s centroid as a representative value. This list of representatives is the codebook.
3. Index — at each weight position, instead of a 32-bit float, store only a small integer index pointing to “which cluster it belongs to”.

With $k=4$ clusters, a 2-bit index ($\log_2 4$) is enough. The original 32-bit numbers shrink to 2-bit indices + a small codebook.

Try it yourself in the widget below. There’s a 4×4 weight matrix; press run and with each K-Means iteration the centroids (codebook) converge, and each cell is colored by the cluster it belongs to. Changing bits changes the number of clusters, and the quantization error (MSE), storage, and compression ratio below update in real time.

In the default state (2-bit), running run to the end converges the codebook to roughly -1.00, 0.00, 1.50, 2.00. Each weight is now reconstructed as one of these four values. The difference between the original and the reconstruction is the quantization error.

• Raise bits to 3 → clusters grow to 8, error drops, but the indices get bigger so storage grows.
• Lower bits to 1 → everything is lumped into 2 representatives, so error grows.

The trade-off between precision (error) and size (storage) becomes tangible.

---

How much does it shrink?

Let’s follow the numbers from the widget. 4×4 = 16 weights, 2-bit quantization:

• Original: $16 \times 32\text{bit} = 512\text{bit} = 64\text{B}$
• Compressed: indices $16 \times 2\text{bit} = 32\text{bit} = 4\text{B}$  +  codebook $4 \times 32\text{bit} = 128\text{bit} = 16\text{B}$  =  $20\text{B}$
• $64 / 20 = \textbf{3.2×}$ smaller.

This example has only 16 parameters, so the codebook (16B) looks relatively large. But a real network has $M$ = millions to billions of parameters, so $M \gg 2^N$ and the codebook cost becomes negligible. Generalizing:

$$\text{original} = 32M \text{ bit}, \qquad \text{compressed} = \underbrace{N \cdot M}_{\text{indices}} + \underbrace{32 \cdot 2^N}_{\text{codebook}} \text{ bit}$$

When $M \gg 2^N$, the codebook term vanishes and the compression ratio converges to $32M / NM = \mathbf{32/N}$. So 2 bits gives about 16×, 4 bits about 8×. In the calculator below, move the parameter count $M$ and bit width $N$ to see when the codebook becomes negligible.

---

What about accuracy? — retrain the codebook

Lumping weights into representatives obviously creates error. Left alone, accuracy drops. The clever part of Deep Compression is that it fine-tunes the quantized codebook itself.

Here’s how. After backprop computes each weight’s gradient:

1. gather the gradients of weights in the same cluster (group by index),
2. sum them (reduce),
3. multiply by the learning rate and update that cluster’s centroid.

So you train just a handful of representatives, not the individual weights. This recovers much of the error introduced by quantization.

It’s intuitive from the weight distribution. Before quantization it’s a continuous bell shape; it turns into a few discrete spikes, and retraining nudges those spikes to fit the data. The “positions” of the representatives shift in the direction that reduces the loss.

As a result, the answer to how few bits still preserve accuracy is quite striking. In the Deep Compression experiments, for AlexNet:

• Convolutional (Conv) layers: no accuracy loss down to 4 bits
• Fully-connected (FC) layers: no accuracy loss down to 2 bits

So each layer needs a different bit width, and FC layers — with many parameters — can be cut more aggressively.

---

The final squeeze: Huffman coding

After quantization, each weight becomes one of a few indices (e.g. 0–3 for 2-bit). But these indices don’t appear uniformly. Since weights cluster near zero, the index for zero shows up very often while the extreme indices are rare. Plot the index histogram of a real network and it’s heavily skewed to one side.

Here we can squeeze out one more round of lossless compression. Huffman coding assigns different bit lengths based on symbol frequency.

• frequent value → short code
• rare value → long code

Instead of spending the same 2 bits on every index, dividing code length by frequency reduces the average bit count. For example, when the distribution is skewed:

Representative	Frequency	Fixed 2-bit	Huffman code
0.00	50%	01	0 (1 bit)
−1.00	25%	00	10 (2 bits)
1.50	15%	10	110 (3 bits)
2.00	10%	11	111 (3 bits)

The average bit count here is $0.5\times1 + 0.25\times2 + 0.15\times3 + 0.1\times3 = 1.75$ bits, shorter than a fixed 2 bits. Information-theoretically the optimal code length approaches the entropy of the distribution, so the more skewed the distribution, the bigger the gain.

The key point is that it’s lossless. It changes no value at all; it merely strips away wasted representation. In Deep Compression this stage sits at the very end of the pipeline and pushes the compression ratio one step further (27–31× after quantization → 35–49× after Huffman).

---

The crucial limitation: this only reduces “storage”

Here’s something we must not miss. What K-Means quantization reduces is only the model size stored on disk/in memory.

What happens at inference time? What’s stored is integer indices + a float codebook. To actually do the multiplications and additions, you have to decode the indices through the codebook back into the original float weights. That is:

• Storage: integer indices (small) ✓
• Compute: still floating-point arithmetic on the reconstructed 32-bit floats ✗

We saved memory bandwidth, but the computation itself got no faster at all. The multiply-accumulate (MAC) units still run floats.

To actually make inference itself fast with integer arithmetic, we need a different approach — Linear Quantization, which stores weights as integers and performs the multiplications in integer arithmetic. That’s the story of the next post.

---

Summary

• Idea: group similar weights with K-Means to share representatives (a codebook), and store only a small index at each position.
• Compression: 32-bit → $N$-bit index. When $M \gg 2^N$, about $32/N$× smaller.
• Accuracy: retrain the codebook (centroids) to recover the error. Lossless down to 4 bits (Conv) / 2 bits (FC).
• Extra compression: since the index distribution is skewed, Huffman coding squeezes out one more round of lossless compression.
• Limitation: it only reduces storage; inference compute is still float. This is the middle piece of the Deep Compression pipeline (Pruning → Quantization → Huffman), and to accelerate integer compute you need Linear Quantization.

For reference, the original Deep Compression added pruning on top for a 3-stage pipeline (pruning → quantization → Huffman), shrinking AlexNet by 35× and VGG by 49× (with accuracy preserved). Applied to SqueezeNet it reached 0.47MB, a 510× compression. Pruning is a topic for another post.