FAISS (Facebook AI Similarity Search)

The foundational algorithmic class FAISS implements. ANN algorithms trade a small, controllable amount of recall for massive gains in query speed, making sub-millisecond search feasible on billion-scale datasets. Unlike exact K-Nearest Neighbors (KNN) which scales linearly, ANN uses indexing structures to achieve logarithmic or constant time complexity.

• Core trade-off: Speed vs. accuracy, tuned via search-time parameters like nprobe or efSearch.
• FAISS implementation: Provides multiple ANN algorithms including IVF, HNSW, and graph-based methods.
• When exact search fails: Exact search on 1B 128-dimensional vectors requires scanning 128GB of data; ANN reduces this to accessing < 1% of the index.

A lossy compression technique central to FAISS's ability to store massive indexes in RAM. PQ decomposes the original high-dimensional vector space into M independent lower-dimensional subspaces, then clusters each subspace independently using k-means. A vector is encoded not by its original floating-point values but by the IDs of the nearest centroids in each subspace.

• Compression ratio: A 1024-dim float32 vector (4096 bytes) can be compressed to 64 bytes using M=64 sub-quantizers with 256 centroids each.
• Distance computation: FAISS uses asymmetric distance computation (ADC) — the query vector is not compressed, only the database vectors are.
• Memory impact: Enables storing 1 billion 128-dim vectors in ~64GB RAM instead of 512GB.

A graph-based ANN algorithm available in FAISS that constructs a multi-layered navigable graph. The top layers contain long-range edges for rapid coarse navigation, while bottom layers contain short-range edges for fine-grained search. Search begins at the top layer and descends greedily, achieving logarithmic scaling with dataset size.

• Key parameter: M controls the number of outgoing edges per node, directly trading memory for recall.
• Advantage over IVF: No separate training step required; the graph is built incrementally during insertion.
• FAISS integration: Available via IndexHNSWFlat for exact storage or IndexHNSWPQ for compressed storage.
• Memory overhead: Higher than IVF due to storing the graph structure alongside vectors.

FAISS's most widely-used indexing strategy. IVF partitions the vector space into Voronoi cells using k-means clustering. At query time, only the nprobe nearest cells to the query vector are searched, dramatically reducing the candidate set. The inverted file structure maps each cluster centroid to a posting list of vectors assigned to that cell.

• Training required: k-means clustering must run on a representative sample before indexing.
• Coarse quantizer: The centroid assignment step itself uses a smaller index for speed.
• Combined with PQ: IndexIVFPQ is FAISS's flagship index, pairing IVF partitioning with PQ compression for billion-scale search.
• Tuning nprobe: Higher values increase recall at the cost of linear slowdown; typical values range from 1 to 256.

FAISS provides first-class GPU support, enabling brute-force exact search on GPUs that outperforms CPU ANN for moderate dataset sizes. GPU indexes leverage massive parallelism: a single NVIDIA A100 can compute 10+ billion distance comparisons per second for 128-dim vectors.

• GpuIndexFlatL2: Exact brute-force L2 search on GPU, ideal for < 10M vectors where speed trumps compression.
• GpuIndexIVFPQ: GPU-accelerated IVF with PQ, combining partitioning and compression with parallel distance computation.
• Multi-GPU sharding: FAISS can distribute an index across multiple GPUs using IndexProxy or IndexShards, enabling linear scaling.
• Batch processing: GPU indexes achieve peak throughput when queries are batched, amortizing kernel launch overhead.