Facebook AI Similarity Search (FAISS)

For datasets up to a few million vectors, FAISS offers the fastest exact search via highly optimized GPU kernels. It leverages SIMD instructions and massive parallelism to compute Euclidean Distance or Maximum Inner Product Search (MIPS) against every database vector simultaneously. This guarantees perfect Recall@K without the approximation trade-offs of indexing, making it ideal for benchmarking ground truth and latency-sensitive applications with smaller indexes.

FAISS is not a single algorithm but a composable framework. It implements all major ANN families:

• Inverted File Index (IVF): Partitions space into Voronoi Cells using a Coarse Quantizer.
• Hierarchical Navigable Small World (HNSW): Builds a multi-layer proximity graph for logarithmic scaling.
• Product Quantization (PQ): Compresses vectors into short codes using distinct Codebooks for subvectors.
• IVFPQ: Combines IVF coarse partitioning with PQ compression of Residual Vectors for memory efficiency.

To maximize accuracy under compression, FAISS defaults to Asymmetric Distance Computation. Database vectors are compressed via Product Quantization, but the query vector remains in full precision. Distances are approximated by looking up pre-computed distances between the query subvectors and the PQ codebook entries. This yields significantly higher search accuracy than symmetric computation (where both query and database vectors are quantized) at minimal extra cost.

FAISS abstracts memory hierarchy complexity. It provides seamless functions to move indices between CPU RAM and GPU VRAM. A common pattern involves performing the expensive Index Build Time phase on GPU for speed, then transferring the compressed index to CPU for low-cost, high-throughput inference. This hybrid execution model allows serving billion-scale indices on machines with limited GPU memory by storing the compressed vectors in system RAM.

FAISS is designed for high-throughput serving. Its C++ backend supports batched query execution, processing thousands of vectors in a single API call to saturate GPU utilization. Internal prefetching mechanisms overlap data movement with computation, ensuring that the next batch of compressed vectors is streaming from RAM while the current batch is being scored. This pipelining is critical for achieving sub-10ms latency in production retrieval systems.

FAISS supports Filtered ANN via the IDSelector callback interface. This allows users to define arbitrary boolean predicates (e.g., metadata filters) that are evaluated during the search traversal. While FAISS primarily uses a pre-filtering strategy, the tight C++ integration ensures minimal overhead. The selector is invoked during graph traversal or cell scanning to skip invalid vectors, enabling constrained semantic search without post-processing the entire candidate set.

A vector compression technique central to FAISS's memory efficiency. High-dimensional vectors are split into subvectors, each quantized independently using a distinct codebook. This reduces storage by representing vectors as short codes. FAISS implements IVFPQ to combine coarse partitioning with PQ compression, enabling billion-scale search in RAM. The primary tradeoff is quantization error—the distortion introduced by mapping continuous vectors to discrete centroids.

A clustering-based partitioning strategy used by FAISS to avoid exhaustive search. The vector space is divided into Voronoi cells using a coarse quantizer trained via k-means. At query time, only the most promising partitions are searched. FAISS computes residual vectors—the difference between the original vector and its assigned centroid—to encode fine-grained local information, often compressing these residuals with PQ for maximum efficiency.

A graph-based ANN algorithm natively supported in FAISS. It constructs a multi-layered proximity graph where sparse upper layers enable long-range jumps and dense lower layers refine results. Key hyperparameters include graph degree (edges per node) and efSearch (search-time exploration factor). HNSW delivers state-of-the-art recall-speed tradeoffs without requiring a training phase, though it consumes more memory than compressed indices.

FAISS provides highly optimized brute-force search on GPU, computing exact distances for every database vector in parallel. While linear in complexity, GPU parallelism makes this viable for moderate-scale datasets requiring perfect Recall@K. FAISS leverages SIMD instructions and efficient matrix multiplication kernels to maximize throughput. This serves as the ground-truth baseline against which approximate indices are evaluated.

An efficiency technique used in FAISS when searching compressed indices. Only the database vectors are stored in quantized form; the query vector remains in full precision. Distances are approximated by computing the distance between the uncompressed query and the pre-computed codebook entries. ADC yields significantly higher accuracy than symmetric computation (where both query and database are compressed) at minimal additional search-time cost.

FAISS supports filtered ANN via IDSelector objects, enabling constrained search where results must satisfy metadata predicates. The library implements both pre-filtering (applying filters before distance computation) and post-filtering (scoring then discarding). FAISS also provides SearchParameters to control recall-speed tradeoffs per query, including the max_codes parameter for IVF indices that limits the number of scanned partitions.