IVFPQ

IVFPQ operates as a composite index with two distinct stages. The first level uses an Inverted File Index (IVF) to partition the vector space into Voronoi cells via a coarse quantizer. The second level applies Product Quantization (PQ) to compress the residual vectors—the difference between the original vector and its assigned coarse centroid. This two-level design restricts expensive distance computations to only the most promising partitions while storing vectors in a highly compressed form.

Rather than quantizing raw vectors directly, IVFPQ compresses residual vectors—the offset from each vector to its cluster centroid. This approach is more efficient because residuals typically have lower variance and energy than the original vectors, allowing the PQ codebook to represent them with less distortion. The process:

• Compute the coarse centroid for each vector's assigned partition
• Subtract the centroid to obtain the residual
• Apply product quantization to the residual
• Store only the compact PQ codes

IVFPQ employs Asymmetric Distance Computation (ADC) during search to maximize accuracy. The query vector remains in full precision while database vectors are stored as compressed PQ codes. Distance tables are precomputed between the query subvectors and each PQ codebook, enabling fast lookup-based distance approximation. This asymmetry yields significantly higher recall than symmetric approaches where both query and database vectors are quantized.

IVFPQ offers fine-grained control over the memory-accuracy tradeoff through two primary parameters:

• nprobe: The number of IVF cells to search during query time. Higher values increase recall but add latency
• PQ subvector count (M): More subvectors mean finer quantization and higher accuracy, but larger codes

A typical configuration compresses 128-dimensional float32 vectors from 512 bytes down to just 8-64 bytes, achieving 90%+ recall@10 while reducing memory by 8-64x.

Building an IVFPQ index involves a multi-stage training process:

• Stage 1: Train the coarse quantizer (typically k-means) on a representative sample to partition the space into cells
• Stage 2: Assign all training vectors to their nearest coarse centroids and compute residuals
• Stage 3: Train the product quantizer on the pooled residuals to learn subvector codebooks
• Stage 4: Encode all database vectors as (coarse ID, PQ code) pairs

This training overhead makes IVFPQ best suited for static or slowly-changing datasets where the index is built once and queried many times.

The coarse quantizer that forms the first stage of IVFPQ. IVF partitions the vector space into Voronoi cells using k-means clustering. During a search, the query vector is first assigned to its nearest centroids, and the subsequent fine-grained search is restricted to only those high-probability partitions. This drastically reduces the number of distance computations by ignoring irrelevant regions of the space.

• Role in IVFPQ: Provides the non-exhaustive, partition-based candidate generation.
• Key Parameter: nprobe controls how many cells are visited, directly trading off speed for recall.

The compression engine that forms the second stage of IVFPQ. PQ decomposes a high-dimensional vector into smaller subvectors, then quantizes each independently using a distinct codebook. This turns a full-precision vector into a short code, dramatically reducing memory consumption.

• Role in IVFPQ: Compresses the residual vectors (the difference between the original vector and its assigned IVF centroid).
• Distance Computation: Uses Asymmetric Distance Computation (ADC) where the query is not compressed, yielding higher accuracy.

The critical bridge between IVF and PQ. A residual vector is calculated by subtracting the coarse centroid (from IVF) from the original vector: r = v - c.

This residual encodes only the local, fine-grained deviation from the cluster center. Because residuals have a much smaller variance than the original vectors, they can be compressed far more effectively by Product Quantization with minimal information loss. This two-level encoding is the core insight behind IVFPQ's efficiency.

The standard distance approximation method used during IVFPQ search. The query vector q remains in full precision, while database vectors are represented by their PQ codes.

The distance between q and a database vector is approximated using pre-computed distance look-up tables between q's subvectors and the PQ codebooks. ADC is preferred over Symmetric Distance Computation (SDC) because it introduces less quantization error, providing a superior recall-speed tradeoff.