FAISS (Facebook AI Similarity Search)

FAISS is engineered from the ground up for GPU parallelism, enabling brute-force and approximate nearest neighbor search to run orders of magnitude faster than CPU-only implementations. It leverages CUDA kernels to batch distance computations across thousands of queries simultaneously, making sub-millisecond latency achievable even on datasets containing hundreds of millions of vectors. The library supports multiple GPU configurations, including single-GPU, multi-GPU sharding, and hybrid CPU-GPU workflows where the CPU manages the index structure and GPUs handle the distance calculations.

FAISS implements several inverted file and graph-based indexing structures specifically designed to handle datasets that exceed available RAM. Key indexing strategies include:

• IVF (Inverted File): Partitions the vector space using k-means clustering, restricting search to the nearest centroids.
• HNSW (Hierarchical Navigable Small World): Builds a multi-layered graph that enables logarithmic-time traversal.
• PQ (Product Quantization): Compresses vectors by decomposing them into sub-vectors and quantizing each subspace independently, reducing memory footprint by up to 16x. These can be combined into composite indices like IVFPQ for maximum compression and speed.

FAISS natively supports a range of distance functions to accommodate different embedding types and similarity definitions:

• L2 (Euclidean) Distance: Standard straight-line distance between two points.
• Inner Product: Equivalent to cosine similarity when vectors are L2-normalized, commonly used for neural network embeddings.
• Cosine Similarity: Directly supported via normalization pre-processing.
• L1 (Manhattan) Distance and Linf (Chebyshev) Distance: Available for specific use cases.
• Hamming Distance: For binary codes and compact hash-based representations. The choice of metric is specified at index creation time and cannot be changed without rebuilding the index.

FAISS is optimized for high-throughput batch querying rather than single-query latency. It processes queries in batches to maximize GPU utilization and amortize kernel launch overhead. The library also supports concurrent read access to a single index from multiple threads, enabling production deployments where many application servers query a shared in-memory index. For write operations, FAISS provides explicit synchronization primitives, though index modification is typically performed in a separate process to avoid blocking search operations.

To fit billion-scale datasets into GPU or CPU memory, FAISS employs aggressive yet tunable compression techniques:

• Scalar Quantization (SQ): Converts 32-bit floating-point dimensions to 8-bit or 4-bit integers.
• Product Quantization (PQ): Achieves compression ratios of 16x–32x by encoding sub-vectors against learned codebooks.
• Additive Quantization: A refinement of PQ that represents vectors as sums of multiple codewords for higher accuracy.
• PCA Dimensionality Reduction: Pre-processes vectors to reduce dimensions before indexing, often combined with quantization for compound savings. These methods introduce a trade-off between memory usage and recall accuracy, controllable via parameters like the number of PQ sub-quantizers.

FAISS supports direct serialization of trained indices to disk or memory buffers, enabling offline index construction followed by deployment to production servers without re-training. Indices can be saved as binary files and loaded back into memory with a single function call. The library also supports index merging—combining multiple independently built indices into a single unified index—which is critical for distributed index construction pipelines. For very large indices that exceed single-machine memory, FAISS provides distributed index sharding across multiple machines with client-side query aggregation.

The foundational search paradigm FAISS implements. Exact nearest neighbor search scales linearly with dataset size, becoming infeasible at billions of vectors. ANN algorithms trade a small, tunable amount of recall for sub-linear or logarithmic query time. FAISS provides multiple ANN index types—including IVF, HNSW, and PQ-based indices—each optimized for different memory, speed, and accuracy trade-offs. The core insight: in high-dimensional spaces, a slightly imperfect result returned in microseconds is far more valuable than a perfect result returned in seconds.

A vector compression technique central to FAISS's ability to scale to billion-scale datasets in RAM. PQ decomposes a high-dimensional vector into multiple sub-vectors, then independently quantizes each subspace using a learned codebook of centroids. A 1024-dimensional float32 vector requiring 4KB can be compressed to just 64 bytes using PQ with 8 sub-quantizers and 256 codes each. FAISS implements optimized PQ kernels that compute distances directly in the compressed domain using precomputed lookup tables, avoiding decompression overhead during search.

FAISS's primary indexing structure for clustering-based search. An IVF index first partitions the vector space into Voronoi cells using k-means clustering. At query time, only the nearest nprobe cells are searched, reducing the candidate set from billions to thousands. FAISS implements IVFPQ, which combines IVF partitioning with PQ compression: the coarse quantizer maps queries to relevant cells, while the product quantizer encodes residuals within each cell. This two-level structure is the default choice for GPU-accelerated billion-scale retrieval.

A graph-based ANN algorithm available in FAISS as an alternative to IVF-based indices. HNSW builds a multi-layered proximity graph where long-range edges at higher layers enable logarithmic-time navigation, while dense local connections at the base layer ensure high recall. Unlike IVF, HNSW requires no training phase—the graph is built incrementally during insertion. FAISS's HNSW implementation supports incremental insertion and deletion, making it suitable for dynamic datasets. The trade-off: HNSW consumes more memory than compressed IVF indices due to storing the full graph structure.

FAISS's IndexFlatL2 and IndexFlatIP on GPU represent the exact search baseline. While brute-force comparison against every vector in the database is O(N), FAISS leverages NVIDIA's cuBLAS library to parallelize matrix-matrix multiplication across thousands of CUDA cores. For datasets up to ~10 million vectors, GPU brute force can outperform approximate CPU indices in wall-clock time. This is the reference implementation for measuring ANN recall: any approximate index's results are compared against GPU brute-force ground truth. FAISS also supports multi-GPU sharding for larger exact-search workloads.

The mathematical foundation that gives FAISS indices their purpose. Cosine similarity measures the angle between two embedding vectors, ignoring magnitude differences that often reflect document length rather than semantic content. FAISS natively supports inner product (IP) and L2 distance metrics. To use cosine similarity, vectors must be L2-normalized before indexing—inner product on normalized vectors is equivalent to cosine similarity. FAISS provides IndexFlatIP for exact inner product search and all approximate indices support IP as a distance metric.