Vector Compression

Maps continuous floating-point vector values to a smaller set of discrete integers, typically converting 32-bit floats to 8-bit integers. This achieves a 4x memory reduction with minimal precision loss.

• Uniform quantization: divides the value range into equal intervals
• Non-uniform quantization: allocates more intervals to high-density regions
• Widely used as a first-pass compression before applying product quantization
• Supported natively in FAISS and most vector databases

Decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently using separate codebooks. A 768-dimensional vector might be split into 96 sub-vectors of 8 dimensions each.

• Each sub-vector is mapped to the nearest centroid in its codebook
• Distances are computed using pre-calculated lookup tables for speed
• Achieves compression ratios of 16x to 32x while maintaining reasonable recall
• The number of sub-vectors and codebook size control the accuracy-memory tradeoff

Combines coarse quantization for candidate pruning with product quantization for compressed storage. An inverted file index first partitions the vector space using k-means clustering, then applies PQ to residuals within each partition.

• Coarse quantizer narrows search to the nearest 1-10% of partitions
• PQ compresses the residual vectors after subtracting cluster centroids
• Enables sub-millisecond search over billion-scale datasets
• The dominant indexing strategy in production vector search systems

Pre-processes vectors with a learned rotation matrix before applying product quantization. This rotation decorrelates dimensions and balances the variance across sub-vectors, making the subsequent PQ step significantly more accurate.

• Finds an optimal orthogonal transformation to minimize quantization distortion
• Particularly effective for high-dimensional embeddings with correlated dimensions
• Improves recall by 10-20% over standard PQ at the same compression rate
• The rotation matrix is learned once on a representative sample and applied to all vectors

The most aggressive compression technique, reducing each vector dimension to a single bit based on its sign relative to a threshold. A 768-dimensional float32 vector becomes just 96 bytes.

• Each dimension is encoded as 0 or 1, achieving 32x compression
• Distance computation reduces to fast Hamming distance or popcount operations
• Works surprisingly well for high-dimensional embeddings where sign carries significant information
• Often used as a rapid pre-filter before more precise re-ranking stages

Trains embeddings so that the first few dimensions alone provide a coarse but useful representation, with additional dimensions adding progressively finer detail. Named after nested Russian dolls.

• A single embedding supports multiple granularities without re-encoding
• Truncating to 1/8th of dimensions retains 90%+ of full-dimensional accuracy
• Enables adaptive retrieval: fast coarse search followed by precise re-ranking
• Eliminates the need to store multiple copies of embeddings at different resolutions

The foundational compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently using distinct codebooks. Instead of storing a full 768-dimensional float32 vector (3 KB), PQ might split it into 96 sub-vectors of 8 dimensions each, quantizing each to a codebook index.

• Memory reduction: A 768-dim vector compressed from 3072 bytes to ~96 bytes (32x reduction)
• Asymmetric distance computation: Query vectors remain uncompressed while database vectors are quantized, preserving accuracy
• Trade-off: Compression ratio vs. recall quality controlled by the number of sub-vectors (M parameter)

A simpler compression method that maps continuous floating-point values to discrete integer bins. Unlike PQ, SQ operates on individual dimensions rather than sub-vectors.

• 8-bit quantization: Converts float32 values to int8, reducing memory by 4x with minimal accuracy loss
• 4-bit quantization: Further compression to int4 for aggressive memory savings
• Calibration: Requires computing per-dimension min/max ranges from a sample of the dataset to set quantization boundaries
• Often used as a first-stage compression before applying PQ for additional gains

A partitioning strategy that clusters the vector space into Voronoi cells using k-means. At query time, only the nearest partitions are searched rather than the entire dataset.

• Coarse quantizer: The clustering step that assigns each vector to its nearest centroid
• nprobe parameter: Controls how many cells to search — higher values increase recall at the cost of speed
• IVF+PQ combination: The industry-standard approach where IVF provides the index structure and PQ compresses the vectors within each cell
• Enables sub-linear search time by pruning 90-99% of the dataset per query

A graph-based indexing algorithm that builds a multi-layered proximity graph where each layer contains increasingly dense connections. Search navigates from sparse upper layers to dense lower layers.

• No training phase: Unlike IVF, HNSW builds incrementally without a separate clustering step
• Logarithmic scaling: Search complexity scales as O(log N) with dataset size
• Memory overhead: Stores full-precision vectors plus graph edges, making compression essential for large-scale deployment
• Often paired with PQ or SQ to compress the stored vectors while preserving the graph structure for navigation

The core similarity metric that measures the cosine of the angle between query and document vectors, ranging from -1 (opposite) to 1 (identical). Compression techniques must preserve the relative ordering of these similarity scores.

• Normalization invariant: Only cares about direction, not magnitude — vectors are typically L2-normalized before compression
• Inner product equivalence: For normalized vectors, cosine similarity equals the dot product, enabling efficient MIPS
• Quantization-aware training: Modern embedding models are trained to produce vectors that remain discriminative after compression
• Compression quality is measured by how well the ranked order of cosine similarities is preserved post-quantization