IndexIVFPQ

IndexIVFPQ is a data structure for scalable approximate nearest neighbor search that combines an inverted file (IVF) with Product Quantization (PQ). It is designed for high-dimensional vector collections and is commonly used in libraries such as FAISS. The index first partitions the vector space into a fixed number of coarse clusters (nlist) using a coarse quantizer. Each database vector is assigned to one coarse cell, and its residual vector (the difference between the vector and the cell centroid) is then compressed with PQ. The resulting PQ codes are stored in the corresponding inverted lists.

In operation, a query is first compared against the coarse centroids to identify the most relevant cells. A parameter called nprobe controls how many inverted lists are inspected. Within each selected cell, the PQ encoding allows fast distance estimation between the query and database vectors using precomputed lookup tables for the query and the PQ codebooks. This yields an approximate distance rather than a exact Euclidean distance, enabling rapid ranking of candidates.

Key parameters include nlist (the number of coarse clusters), nprobe (the number of cells examined during search), M (the number of PQ subquantizers), and the dimension d of the vectors (which must be compatible with M, typically satisfying d mod M = 0). Training involves learning the coarse centroids and the PQ codebooks, usually from the dataset. IndexIVFPQ balances memory usage and query speed, offering strong performance for large-scale, high-dimensional data, with tradeoffs in accuracy depending on parameter choices.