FAISS

FAISS provides highly optimized CUDA kernels that offload the computational bottleneck of similarity search to NVIDIA GPUs. This allows for sub-millisecond query latency even against indexes containing hundreds of millions of vectors. The library supports both single-GPU and multi-GPU configurations through sharding and replication, enabling linear scaling of queries per second (QPS) by distributing shards across available devices. Key GPU algorithms include a brute-force GpuIndexFlat for exact search and GpuIndexIVFFlat for compressed-domain approximate search.

Product Quantization is FAISS's core lossy compression technique for storing vectors in a fraction of their original memory footprint. The high-dimensional input vector is split into distinct sub-vectors, and each sub-vector is independently quantized to the nearest centroid in a pre-trained codebook. This allows a 1024-dimensional float32 vector (4KB) to be stored using just 64 bytes. Search is performed using Asymmetric Distance Computation (ADC), where the query vector is not compressed, preserving accuracy while scanning compressed database codes.

The IVF index is a partitioning strategy that avoids exhaustive search by clustering the vector space using k-means. At query time, only the nprobe nearest partitions to the query vector are visited. This reduces the search scope from the entire dataset to a small fraction of it. FAISS combines IVF with PQ (IVFPQ) to achieve both memory efficiency and fast search. The nprobe parameter provides a direct trade-off dial between search accuracy and speed, making it suitable for latency-critical production systems.

FAISS implements the Hierarchical Navigable Small World (HNSW) algorithm, a graph-based index structure that builds a multi-layered proximity graph. The top layers contain long-range edges for fast traversal across the vector space, while bottom layers contain short-range edges for precise local search. HNSW achieves logarithmic time complexity O(log N) and often outperforms IVF-based indexes in recall at the cost of higher memory usage, as the raw vectors and the graph structure must be stored in RAM.

FAISS exposes an index factory string syntax that allows complex indexes to be constructed declaratively. For example, IVF4096,PQ64 builds an inverted file index with 4096 centroids and 64-byte product quantization. Indexes can be composed using pre-transformations like OPQ (Optimized Product Quantization) to rotate the vector space for better compression, or PCA for dimensionality reduction. This composability allows engineers to rapidly prototype and benchmark different index configurations without writing custom construction code.

Beyond single-vector k-NN queries, FAISS natively supports batch vector search where thousands of query vectors are processed simultaneously, maximizing GPU utilization. It also provides range search, which returns all vectors within a specified distance radius rather than a fixed top-k. This is critical for applications like deduplication, clustering, and density estimation. The library's C++ core with Python bindings ensures that these operations are memory-efficient and avoid the overhead of Python-level loops.

The class of algorithms FAISS implements to trade a small, controlled amount of accuracy for massive speed gains. Instead of an exact, brute-force O(n) scan of every vector, ANN algorithms use quantization, graph traversal, or locality-sensitive hashing to find the most similar vectors in sub-linear time. This trade-off is essential for scaling semantic search to billion-scale corpora where an exact search would take seconds or minutes per query.

A core compression technique within FAISS that decomposes the original high-dimensional vector space into a Cartesian product of lower-dimensional subspaces. Each subspace is independently quantized using a distinct codebook. This drastically reduces the memory footprint of the index—enabling billion-scale datasets to fit in RAM—at the cost of a small, bounded increase in search error. FAISS offers multiple PQ variants, including IVFPQ and OPQ.

A partitioning strategy that serves as a coarse quantizer to avoid exhaustive search. During indexing, vectors are clustered using k-means; each cluster centroid defines a Voronoi cell. At query time, only the cells closest to the query vector are searched. The key parameter nprobe controls how many cells to visit, directly trading off speed against recall. IVF is the foundational pre-filter for IVFFlat and IVFPQ indexes.

A graph-based ANN algorithm available in FAISS that constructs a multi-layered navigable graph. Each layer is a proximity graph where nodes represent vectors and edges connect near neighbors. Search begins at the top (sparsest) layer and descends greedily, using long-range edges to skip across the space before refining at the bottom (densest) layer. HNSW offers state-of-the-art query speed without a separate training phase, but consumes more memory than PQ-based indexes.

FAISS's defining architectural advantage is its deep optimization for NVIDIA GPUs. It provides custom CUDA kernels for both index construction and query execution, enabling brute-force kNN on billion-scale datasets in milliseconds. Key GPU features include:

• GpuIndexFlatL2: Exact search on GPU
• GpuIndexIVFFlat: GPU-accelerated IVF
• Multi-GPU sharding for indices that exceed single-GPU memory This makes FAISS the standard choice for applications where query latency must be measured in single-digit milliseconds at extreme scale.