Coarse Quantizer

The coarse quantizer divides the high-dimensional vector space into non-overlapping regions called Voronoi cells. Each cell is defined by a centroid, and every vector in the space belongs to the cell of its nearest centroid. This geometric partitioning is the foundation of the inverted index structure, ensuring that similar vectors are grouped together logically.

The most common implementation uses k-means clustering to learn the coarse centroids. The algorithm iteratively refines centroid positions to minimize the sum of squared distances within each cluster. The number of centroids, nlist, is a critical hyperparameter that directly controls the trade-off between search speed and recall.

Once a vector is assigned to a coarse centroid, the quantizer enables the calculation of a residual vector: r = v - c. This residual encodes the fine-grained, local offset from the centroid. It is this residual, not the raw vector, that is typically compressed and stored using a second-level technique like Product Quantization (PQ).

During a query, the coarse quantizer computes the distance from the query vector to all coarse centroids. It selects the nprobe nearest centroids for detailed search. This parameter dynamically controls the accuracy-speed tradeoff at query time: a higher nprobe searches more partitions, increasing recall but also latency.

The coarse quantizer itself has a minimal memory footprint, storing only the centroid vectors. For an index with nlist partitions and d dimensions, the storage cost is nlist * d floating-point numbers. This lightweight structure is crucial for scaling to billion-scale datasets where the primary memory bottleneck is the compressed vector data within the partitions.

A query vector near the edge of a Voronoi cell may have its true nearest neighbor in an adjacent cell. The coarse quantizer addresses this edge effect by probing multiple nearby cells (nprobe > 1). Without this multi-probe strategy, the partition boundary would act as a hard cutoff, causing a significant loss in recall.

The parent indexing structure that relies on a coarse quantizer to partition the vector space. The coarse quantizer maps vectors to Voronoi cells, creating an inverted list for each centroid. At query time, only the probe nearest cells are searched, drastically reducing the number of distance computations required.

The standard fine quantizer paired with a coarse quantizer in the IVFPQ composite index. After the coarse quantizer assigns a query to a partition, PQ compresses the residual vectors within that cell. This two-stage approach decouples partitioning from compression, optimizing both speed and memory.

The vector computed by subtracting the coarse centroid from the original data vector. This residual encodes only the local offset within a partition. The fine quantizer (e.g., PQ) compresses this residual, which has a much smaller variance than the original vector, leading to significantly lower quantization error.

The region of space defining a partition in an IVF index. A coarse quantizer assigns every database vector to the cell of its nearest centroid. The shape and size of these cells, determined by the k-means clustering used to train the quantizer, directly impact the recall-speed tradeoff by defining the search boundary.

The preferred distance approximation method for IVFPQ. The query vector is kept in full precision, while only the database vectors are compressed by the coarse and fine quantizers. This avoids compounding quantization errors from the query side, yielding higher accuracy than symmetric computation for the same compression ratio.