Vector Quantization

Vector quantization (VQ) is a compression technique that replaces each vector in a dataset with the index of its nearest entry in a small set of representative vectors called a codebook. Encoding stores only the index, decoding looks the index up, and the reconstruction error is the distance between the original vector and its codeword. A codebook of K entries costs log₂(K) bits per vector however many dimensions the vector has, so a 256-entry codebook stores any vector in one byte. VQ comes from signal processing: Stuart Lloyd's 1957 Bell Labs algorithm for designing scalar quantizers, published in 1982, is the algorithm now usually called k-means, and Yoseph Linde, Andrés Buzo, and Robert Gray extended it to vectors in 1980. In deep learning, VQ became the standard way to turn images, audio, and video into discrete tokens for generative AI.

How Vector Quantization Works#

A codebook is usually learned with k-means clustering: assign every training vector to its nearest codeword, move each codeword to the mean of the vectors assigned to it, and repeat, which never increases the average distortion. Color quantization shows the whole cycle on the pixels of a photo, using SciPy's scipy.cluster.vq module:

import numpy as np
from scipy.cluster.vq import kmeans2, vq
from sklearn.datasets import load_sample_image

image = load_sample_image("china.jpg")  # 427 x 640 RGB photo bundled with scikit-learn
pixels = image.reshape(-1, 3).astype(np.float64)  # one 3-D color vector per pixel

# Learn a 16-entry codebook with k-means (Lloyd's algorithm) on a sample of pixels
rng = np.random.default_rng(0)
codebook, _ = kmeans2(rng.choice(pixels, 5000), 16, minit="++", seed=0)

# Encode: replace each pixel with the index of its nearest codeword (4 bits instead of 24)
indices, _ = vq(pixels, codebook)
# Decode: look each index up in the codebook
reconstruction = codebook[indices]

rmse = np.sqrt(((pixels - reconstruction) ** 2).mean())
print(f"{len(pixels):,} pixels, {len(codebook)} codewords, 24 -> 4 bits per pixel")
print(f"Reconstruction RMSE: {rmse:.1f} on the 0-255 scale")

All 273,280 pixels are stored as 4-bit indices into 16 colors, six times less color data than 24-bit RGB, with a root-mean-square error of 11.3 intensity levels out of 255.

Scalar quantization is the one-dimensional case, and model quantization applies it to neural networks. Ultralytics YOLO26 uses it at export: quantize=8 rounds each weight and activation independently to one of 256 integer levels, with activation ranges observed in one calibration pass over the images in data. Quantizing whole vectors jointly exploits correlations between dimensions, and at the same bit rate an optimal vector quantizer never has higher distortion than an optimal scalar quantizer applied to each value.

Product and Residual Quantization#

A single codebook grows exponentially with the bit budget, since 64 bits would need 2⁶⁴ codewords. Product quantization, introduced by Hervé Jégou, Matthijs Douze, and Cordelia Schmid in 2011, splits each vector into m sub-vectors and quantizes each with its own 256-entry codebook. With m = 8, a 128-dimensional float32 embedding shrinks from 512 bytes to 8, and distances to a query come from small lookup tables. Meta's FAISS library pairs it with an inverted file index, a coarse k-means quantizer that limits each query to a few clusters, for billion-scale vector search.

Residual quantization stacks codebooks instead: the second codebook quantizes the error left by the first, the third the error left by the second, and so on. Google's SoundStream (2021) and Meta's EnCodec (2022) neural audio codecs use it to compress speech and music to a few kilobits per second, and visual autoregressive modeling (VAR) applies it across image resolutions.

VQ-VAE and Image Tokens#

Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu of DeepMind introduced the VQ-VAE in Neural Discrete Representation Learning in 2017. An autoencoder's encoder output at each spatial position is replaced by its nearest codeword, and the decoder reconstructs the input from the codewords. The nearest-neighbor lookup has no gradient, so a straight-through estimator copies the decoder's gradient past it during backpropagation, written in PyTorch as z_q = z + (z_q - z).detach(). Two extra loss terms pull codewords toward the encoder outputs and commit the encoder to its chosen codewords, the second weighted by 0.25 in the paper.

The resulting token grids feed a second model, usually a transformer, that learns to generate them. VQGAN (2021) added adversarial and perceptual losses for sharper tokens and became the tokenizer behind many text-to-image models. A common failure is codebook collapse, in which most codewords are never selected and the effective vocabulary shrinks. K-means initialization, moving-average codebook updates, and resetting unused codes counter it, and Google's finite scalar quantization (FSQ, 2023) avoids it by rounding each of a few latent dimensions to a handful of fixed levels, so every code in the implied codebook is reachable.

Vector Quantization vs. Related Terms#

• Vector databases: Store and index embeddings, and often apply product quantization internally to fit them in memory.
• Dimensionality reduction: Maps vectors to fewer continuous dimensions, as PCA does, where VQ maps each vector to one discrete code.
• Tokenization: Splits text into units from a fixed vocabulary; VQ builds the equivalent vocabulary for continuous signals such as image patches and audio frames.