Vector Quantization

The core of VQ is the codebook—a finite set of centroid vectors that represent the entire vector space. During training, algorithms like k-means clustering partition the embedding space into Voronoi cells, where each original vector is assigned to its nearest centroid. The codebook size K determines the compression ratio: a codebook of 256 centroids requires only 8 bits per vector component.

• Lloyd's algorithm iteratively refines centroids by minimizing within-cluster variance
• Codebook quality directly impacts distortion—the quantization error between original and reconstructed vectors
• Typical codebook sizes range from 256 to 4096 centroids per subspace

Product Quantization decomposes high-dimensional vectors into M orthogonal subspaces and quantizes each independently. Instead of quantizing a 768-dimensional vector as one unit, PQ splits it into 8 sub-vectors of 96 dimensions each, with separate codebooks per subspace. This Cartesian product structure exponentially expands representational capacity: 8 sub-codebooks of 256 centroids each yield 256^8 possible combinations.

• Memory reduction: a 768-dim float32 vector (3 KB) compresses to 8 bytes with M=8, K=256
• Asymmetric distance computation (ADC) accelerates search by precomputing query-to-centroid distances
• PQ is the foundation of FAISS IndexPQ and ScaNN anisotropic quantization

Residual Vector Quantization applies multiple stages of quantization sequentially, where each stage quantizes the residual error from the previous stage. The first codebook captures coarse structure; subsequent codebooks refine the approximation iteratively. This hierarchical approach achieves lower distortion than single-stage PQ at equivalent bitrates.

• Stage 1: r_0 = x - c_1(x) captures the dominant signal
• Stage 2: r_1 = r_0 - c_2(r_0) refines the residual
• Final reconstruction: x̂ = c_1 + c_2 + ... + c_n
• Used in SoundStream, EnCodec, and neural audio codecs for high-fidelity compression

VQ-VAE integrates vector quantization into the latent bottleneck of an autoencoder, forcing the continuous encoder output to map to discrete codebook entries. This discretization prevents the posterior collapse common in standard VAEs and learns a structured latent space where each codebook vector corresponds to a meaningful semantic primitive.

• The straight-through estimator bypasses the non-differentiable argmin operation during backpropagation
• Commitment loss encourages encoder outputs to stay close to chosen codebook vectors
• VQ-VAE-2 generates high-resolution images hierarchically using multi-scale latent maps
• Discrete latents enable autoregressive prior models like PixelCNN for generative sampling

Simpler quantization variants trade precision for extreme speed. Binary quantization reduces each vector dimension to a single bit based on sign: x_i > 0 → 1, else 0. This yields 32x compression for float32 vectors and enables Hamming distance computation via XOR and popcount CPU instructions. Scalar quantization maps each dimension independently to 8-bit or 4-bit integers using learned min-max ranges.

• Binary: 32x compression, sub-millisecond search over millions of vectors
• Scalar (int8): 4x compression with minimal recall degradation (< 0.5%)
• RaBitQ achieves state-of-the-art binary quantization with randomized orthogonal transforms
• Ideal for edge deployment and memory-constrained environments

Quantization-Aware Training simulates quantization effects during model training rather than applying it post-hoc. Forward passes use fake quantization nodes that round activations and weights to lower precision, while backward passes use full-precision gradients. This allows the model to adapt its parameters to compensate for quantization error, yielding significantly higher accuracy than post-training quantization (PTQ).

• Simulates int8 or int4 arithmetic during training with straight-through estimator gradients
• Critical for deploying LLMs on edge hardware with minimal perplexity degradation
• Used in QLoRA for 4-bit fine-tuning of large language models
• Typically recovers 95-99% of full-precision model quality

The most widely adopted VQ variant that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently.

• Reduces memory from N × D × 4 bytes to N × M × log2(K) bits
• Enables billion-scale ANN search on commodity hardware
• Used in FAISS IVF-PQ indexes for sub-millisecond latency
• Trade-off: higher compression ratios increase recall degradation

The process of learning the discrete centroid set that maps continuous vectors to their nearest prototype.

• Typically trained via k-means clustering on a representative sample
• Codebook size K determines the bitrate: log2(K) bits per sub-vector
• Residual vectors (encoding errors) are often recursively quantized for higher fidelity
• Poor codebook initialization leads to dead centroids and degraded recall

A multi-stage quantization technique that iteratively encodes the reconstruction error from the previous stage.

• First stage: coarse approximation of the original vector
• Subsequent stages: quantize the residual r_i = x - Q_i(x)
• Enables hierarchical refinement without exponential codebook growth
• Used in Google's SCANN and modern audio codecs like SoundStream

The simplest VQ baseline that maps each dimension to a b-bit integer using a learned range.

• INT8 quantization: maps 32-bit floats to 8-bit integers
• Binary quantization: extreme 1-bit per dimension using sign thresholding
• Preserves vector dimensionality unlike PQ subspace decomposition
• Often used as a fast pre-filter before expensive rescoring with full-precision vectors

A recent technique that projects vectors onto a random orthonormal matrix before binary quantization to minimize information loss.

• Achieves near-lossless recall at 32× compression ratios
• Outperforms naive binary quantization by decorrelating dimensions
• Compatible with Hamming distance for ultra-fast hardware-accelerated search
• Published in SIGMOD 2024 as a state-of-the-art quantization method