FAISS (Facebook AI Similarity Search)

FAISS leverages GPU computation to perform similarity search orders of magnitude faster than CPU-only solutions. It supports single and multi-GPU configurations, enabling billion-scale nearest neighbor search in milliseconds. The library implements efficient k-selection algorithms on GPU, allowing for brute-force, IVF, and HNSW indexing methods to run directly on CUDA-enabled hardware without data transfer bottlenecks.

FAISS provides a comprehensive suite of indexing structures optimized for different accuracy-speed tradeoffs:

• IndexFlatL2: Exact brute-force search with Euclidean distance
• IndexIVFFlat: Inverted file index with coarse quantization for fast approximate search
• IndexHNSW: Hierarchical Navigable Small World graphs for high-recall navigation
• IndexPQ: Product Quantization for extreme memory compression, reducing vector storage by up to 30x
• IndexBinary: Hamming distance search on binary codes for ultra-fast filtering

Product Quantization (PQ) is FAISS's core technique for compressing high-dimensional vectors into compact codes. The original vector space is split into M subspaces, and each subvector is quantized independently using a k-means codebook. This enables storing vectors using only a few bytes each while retaining the ability to compute approximate distances via lookup tables. PQ is essential for fitting billion-scale embedding indices into main memory.

FAISS serves as the standard retrieval index for Bi-Encoder entity linking architectures. After a mention encoder and entity encoder independently produce dense vectors, FAISS indexes all entity embeddings. At inference, the mention vector is used to query the index, retrieving the top-k candidate entities via maximum inner product search (MIPS). This decoupling of encoding and retrieval enables sub-linear search time relative to the knowledge base size.

FAISS supports index sharding across multiple GPUs and machines using an IndexProxy and IndexShards architecture. Queries are distributed across shards, and results are merged via a reduce operation. Combined with batch query processing, this enables throughput-optimized retrieval for production entity linking pipelines handling thousands of mentions per second across knowledge bases containing tens of millions of entities.

FAISS provides a native C++ implementation with full Python bindings. Vectors are passed as NumPy float32 arrays, enabling seamless integration with PyTorch, TensorFlow, and Hugging Face embedding pipelines. The API supports index serialization to disk, incremental index building, and direct memory access for zero-copy operations. This design makes FAISS the default choice for research prototyping and production deployment alike.

The fundamental problem FAISS solves. Instead of an exact, brute-force O(N) comparison against every vector in the database, ANN algorithms trade a small, controlled loss in recall for massive speed gains. FAISS implements multiple ANN strategies, including Inverted File Index (IVF) and Hierarchical Navigable Small World (HNSW) graphs, reducing search latency from seconds to sub-millisecond for billion-scale datasets. This is the core mechanism enabling real-time entity linking against large knowledge bases.

A lossy compression technique critical to FAISS's memory efficiency. PQ decomposes the original high-dimensional vector space into M lower-dimensional subspaces and independently quantizes each. Instead of storing full-precision floats, FAISS stores compact 8-bit codes, achieving memory reductions of 10-30x. This allows billion-scale vector indices to reside entirely in RAM. During search, distances are estimated via precomputed lookup tables, trading negligible accuracy loss for massive storage savings.

FAISS's primary coarse quantizer for partitioning the vector space. During training, k-means clustering groups vectors into nlist Voronoi cells. At query time, the search is restricted to only the nprobe cells closest to the query vector, ignoring the vast majority of the database. This acts as a dynamic pruning mechanism. The key tuning tradeoff is between nprobe (higher increases recall but slows search) and nlist (more partitions speeds up search but requires probing more cells for equivalent recall).

A graph-based indexing algorithm available in FAISS that constructs a multi-layered navigable structure. The bottom layer contains all data points connected by short-range links, while higher layers have exponentially fewer points with long-range links. Search begins at the top layer's entry point and greedily descends, making large jumps before refining locally. HNSW offers state-of-the-art logarithmic search complexity and high recall without a separate training phase, making it ideal for dynamic indices with frequent insertions.

For datasets up to tens of millions of vectors where exact results are mandatory, FAISS provides a highly optimized GPU brute-force index (IndexFlatIP). By leveraging thousands of CUDA cores and efficient matrix multiplication kernels, FAISS computes exact dot products or L2 distances against the entire database in parallel. This is often used as a ground truth baseline for benchmarking ANN recall and for applications like Cross-Encoder re-ranking where the candidate set is small but precision is paramount.

FAISS uses a declarative string syntax to construct complex, multi-stage indices. For example, IVF4096,PQ64 creates an inverted file with 4096 centroids followed by 64-byte product quantization. This composability allows engineers to combine a coarse quantizer (IVF, HNSW) for candidate pruning with a fine quantizer (PQ, SQ) for memory compression. The factory pattern enables rapid experimentation with different index configurations without rewriting code.