FAISS

FAISS implements a comprehensive taxonomy of index structures that trade off between speed, memory usage, and accuracy. The library provides flat indexes for exact search and compressed-domain indexes for approximate search.

• IndexFlatL2 / IndexFlatIP: Exact brute-force search with L2 distance or inner product
• IndexIVFFlat: Inverted file with exact post-verification for fast coarse quantization
• IndexIVFPQ: Inverted file with Product Quantization for compressed storage
• IndexHNSW: Hierarchical Navigable Small World graphs for high-recall graph-based search
• Composite indexes combining IVF coarse quantizers with HNSW or PQ fine quantizers

FAISS provides a native C++ implementation with full Python bindings via SWIG, enabling both high-performance production deployment and rapid experimentation. The API supports index serialization, GPU resource management, and batch operations.

• Index factory strings for declarative index construction (e.g., 'IVF4096,PQ64')
• write_index / read_index for persistent serialization to disk
• IndexIDMap wrapper for arbitrary external IDs alongside vectors
• Range search returning all neighbors within a distance threshold
• merge_from for combining indices without full rebuilds

The foundational problem that FAISS solves. ANN trades a small, controllable amount of accuracy for massive gains in speed and memory efficiency when searching billion-scale vector datasets. Unlike exact search, which scales linearly, ANN uses indexing structures to achieve sub-linear query times.

• Core trade-off: Accuracy vs. speed, tuned via index parameters
• Common indices: IVF, HNSW, PQ-based methods
• Use case: Finding the top-k most similar embeddings to a query vector in under 10ms

A lossy compression technique central to FAISS's ability to handle billion-scale datasets in RAM. PQ decomposes the original high-dimensional vector space into a Cartesian product of lower-dimensional subspaces and quantizes each independently.

• Memory reduction: 32-bit floats → 8-bit codes (4x compression)
• Trade-off: Introduces quantization error, reducing recall slightly
• Variants: Optimized Product Quantization (OPQ) applies a rotation to minimize distortion
• Example: A 128-dim float vector (512 bytes) can be stored in 64 bytes with PQ

A partitioning strategy that avoids exhaustive search by clustering the dataset and searching only the most promising clusters. FAISS uses k-means to partition vectors into Voronoi cells, then searches only the nprobe nearest cells to the query.

• Training required: Must run k-means on a representative sample before indexing
• Key parameter: nprobe controls the speed-accuracy trade-off
• Combined approach: IVF+PQ (IVFPQ) is FAISS's workhorse for billion-scale search
• Performance: Reduces search scope from billions to millions of vectors per query

A graph-based indexing algorithm that builds a multi-layered proximity graph. Search navigates from the top layer (long-range edges) down to the bottom layer (local neighbors) using a greedy best-first traversal. FAISS implements HNSW as an alternative to IVF-based indices.

• No training phase: Index is built incrementally by inserting vectors
• Excellent recall-speed trade-off: Often outperforms IVF for moderate dataset sizes
• Memory overhead: Stores graph edges in addition to vectors, increasing RAM usage
• FAISS integration: Available via IndexHNSWFlat and IndexHNSWPQ

FAISS provides first-class GPU support via CUDA, enabling brute-force exact search on GPU to be faster than approximate search on CPU for moderate dataset sizes. GPU indices store vectors in VRAM and leverage massive parallelism for distance computations.

• Speedup: 5-10x faster than CPU for brute-force search
• Batch processing: GPU excels at high-throughput, multi-query scenarios
• Limitations: VRAM capacity bounds dataset size; CPU remains necessary for trillion-scale
• Hybrid approach: Combine GPU brute-force for small indices with CPU PQ for large ones