FAISS

The fundamental search paradigm that FAISS implements. ANN algorithms trade a small, controlled amount of accuracy for orders-of-magnitude speed improvements when finding the closest vectors in high-dimensional spaces. Unlike exact k-NN search, which scales linearly with dataset size, ANN techniques use indexing structures to achieve sub-linear or logarithmic query time. FAISS implements multiple ANN algorithms including IVF, HNSW, and PQ-based methods, allowing practitioners to tune the accuracy-speed tradeoff for their specific use case.

A vector compression technique that FAISS uses extensively to enable billion-scale search in memory-constrained environments. PQ works by:

• Decomposing high-dimensional vectors into smaller sub-vectors
• Quantizing each sub-vector independently using k-means clustering
• Representing each original vector as a compact code of cluster indices

This reduces memory footprint from 4 bytes per float to just a few bits per dimension, enabling FAISS to store and search billions of vectors entirely in RAM. FAISS implements PQ, OPQ (Optimized Product Quantization), and IVF-PQ variants.

A graph-based indexing algorithm natively supported in FAISS that constructs a multi-layered proximity graph for logarithmic-time similarity search. HNSW builds a hierarchy where:

• Upper layers contain long-range edges for rapid coarse navigation
• Lower layers contain dense local connections for fine-grained search
• Search starts at the top layer and descends greedily toward the query's neighborhood

FAISS's HNSW implementation delivers state-of-the-art query speed for in-memory datasets and supports incremental insertion without full index rebuilds, making it ideal for dynamic vector collections.

FAISS's foundational partition-based indexing structure that clusters the vector space into regions for efficient pruning. The IVF workflow:

• Training phase: K-means clustering partitions vectors into Voronoi cells
• Indexing phase: Each vector is assigned to its nearest centroid
• Query phase: Only the nprobe closest cells to the query are searched

This reduces search scope from the entire dataset to a small fraction of cells. FAISS combines IVF with PQ (IVF-PQ) and scalar quantization (IVF-SQ) to achieve billion-scale search with sub-100ms latency on commodity hardware.

FAISS provides native CUDA implementations of its core algorithms, enabling massive parallelism for both index construction and query execution. Key GPU capabilities include:

• Brute-force search on GPU achieving throughput of millions of queries per second
• GPU-accelerated k-means for rapid IVF and PQ training
• Multi-GPU sharding that distributes indices across devices for linear scaling
• Half-precision (float16) computation for 2x throughput with minimal accuracy loss

This GPU support allows FAISS to handle trillion-scale similarity search when combined with efficient index structures, making it the standard for production semantic search at Meta and beyond.

An alternative ANN technique available in FAISS that uses random projection functions to hash similar vectors into the same buckets with high probability. Unlike graph-based or partition-based methods, LSH provides probabilistic guarantees on search accuracy. FAISS implements LSH for binary codes and cosine similarity, making it useful when:

• Theoretical guarantees on recall are required
• Vectors are extremely sparse or binary
• A simple, parameter-free baseline is needed

While generally outperformed by HNSW and IVF-PQ on dense vectors, LSH remains valuable for specific data distributions and as a theoretically grounded reference implementation.