Faiss

The Inverted File Index (IVF) is a fundamental indexing method in Faiss that partitions the vector space into Voronoi cells using k-means clustering. During search, the query is compared only to the centroids of these cells, and the search is restricted to vectors within the most promising cells (a process called coarse quantization). This dramatically reduces the number of distance computations required.

• Key Parameter: nlist defines the number of Voronoi cells (clusters).
• Trade-off: Higher nlist increases search accuracy but also increases the time to compute distances to centroids.
• Common Usage: Often combined with Product Quantization (PQ) for further compression in the IVF-PQ index, enabling billion-scale searches.

Product Quantization (PQ) is a compression technique that reduces memory footprint by splitting each high-dimensional vector into subvectors and quantizing each sub-space independently. Instead of storing full-precision vectors, Faiss stores short codes representing the quantized values.

• Mechanism: A 128-dimensional vector might be split into 8 subvectors of 16 dimensions each. Each subvector is mapped to one of 256 centroids (an 8-bit code). The full vector is represented by eight 8-bit codes.
• Distance Approximation: Distances are computed using pre-computed lookup tables, making them extremely fast.
• Primary Benefit: Enables fitting billion-scale datasets in RAM by reducing storage by 4x to 32x.

Faiss includes a highly optimized implementation of the Hierarchical Navigable Small World (HNSW) graph algorithm. HNSW constructs a multi-layered graph where the bottom layer contains all data points, and higher layers are exponentially sparser subsets, enabling fast, greedy traversal.

• Search Process: Starts at a random node in the top layer, navigates to the nearest neighbor, moves down a layer, and repeats until the bottom layer is traversed.
• Performance: Offers excellent query speed and high recall, often with lower build time than IVF but higher memory usage as it stores the graph structure.
• Key Parameters: efConstruction (graph quality) and efSearch (search depth).

Faiss provides transparent GPU acceleration for many of its indexes, leveraging CUDA kernels to parallelize brute-force computations, k-means clustering, and nearest neighbor searches across thousands of threads.

• Supported Operations: Exact search (Flat index), IVF coarse quantizer training and search, and PQ distance computations.
• Memory Model: GPU-resident indexes store vectors in GPU memory. The library also supports pinned memory for faster CPU-GPU transfers.
• Multi-GPU Support: Indexes can be sharded across multiple GPUs using IndexShards or IndexProxy, enabling scaling to handle massive datasets.

Faiss supports both exact and approximate search paradigms, allowing engineers to choose the optimal trade-off between precision, speed, and memory.

• Exact Search (IndexFlat): Performs a brute-force comparison of the query against all vectors in the dataset. Guarantees perfect recall but has O(N) complexity. Used as a baseline for accuracy.
• Approximate Search (IVF, HNSW, PQ): Returns potentially approximate results with sub-linear O(log N) search time, crucial for large-scale applications.
• Hybrid Indexes: Faiss excels at combining techniques (e.g., IVF + PQ, IVF + HNSW) to create highly tunable indexes that balance these factors.

Faiss indexes are highly composable. Core components like quantizers, pre-processing steps, and search methods can be combined like building blocks. It also supports multiple distance metrics.

• Index Composition: An IndexIVFPQ is composed of a coarse_quantizer (often IndexFlatL2), a ProductQuantizer, and the IVF structure. Custom pipelines can be built.
• Supported Metrics: L2 (Euclidean) distance and inner product are natively supported. Cosine similarity is achieved by normalizing vectors to unit length and using inner product.
• Pre-Processing: Includes optional steps like PCA (Principal Component Analysis) reduction and random rotation, which can improve quantization efficiency.