FAISS

FAISS provides a comprehensive taxonomy of index types that trade off between accuracy, speed, and memory. The IndexFlat performs exact brute-force search, serving as the ground-truth baseline. IndexIVF uses k-means clustering to partition the vector space, searching only the nearest centroids. IndexHNSW builds a hierarchical navigable small world graph for rapid traversal. These can be composed into complex pipelines:

• IndexIVFPQ: Combines inverted files with product quantization for extreme compression
• IndexRefine: Applies a re-ranking step using exact distance computation on top-K candidates
• IndexIDMap: Wraps any index to support arbitrary external IDs alongside vectors

FAISS is designed for high-throughput batch operations rather than single-query serving. The index_factory function provides a declarative string-based API to construct complex indices. For example, IVF4096,PQ64 creates an inverted file with 4096 centroids and 64-byte product quantization. Batch methods include:

• add_with_ids: Populates an index with vectors and custom identifiers in bulk
• search: Executes batched k-nearest neighbor queries against the entire index
• range_search: Returns all vectors within a specified distance radius
• merge_index: Combines multiple trained indices for distributed index construction

FAISS serves as the de facto indexing backend for dense passage retrieval (DPR) and retrieval-augmented generation (RAG) systems. After a bi-encoder produces passage embeddings, FAISS indexes them for low-latency semantic search. Common integration patterns include:

• Haystack and LangChain: Both frameworks provide native FAISS document store wrappers
• Incremental indexing: New embeddings can be added to IVF indices without full retraining
• Serialization: Indices can be saved to disk and memory-mapped for zero-copy loading
• ID mapping: External document IDs are preserved through the IndexIDMap wrapper, enabling direct lookup of original text passages after vector search

The foundational algorithmic class that FAISS implements. ANN algorithms trade a small, controlled amount of accuracy for orders-of-magnitude speedups in finding similar vectors. Without ANN, exact search over billions of embeddings would be computationally prohibitive for real-time applications.

• Exact vs. Approximate: Exact search scales linearly O(N), while ANN achieves sub-linear or logarithmic complexity
• Recall trade-off: FAISS allows tuning the accuracy-speed balance via parameters like nprobe and efSearch
• Common use case: Retrieving the top-100 most similar passages from a 10M-document index in under 10ms

A graph-based ANN algorithm available in FAISS that constructs a multi-layered navigable structure. Each layer is a proximity graph where nodes connect to their nearest neighbors. Search begins at the top layer with long-range edges and descends through increasingly dense layers, achieving logarithmic complexity.

• Index factory string: HNSW64 or HNSW64,Flat in FAISS
• Key parameters: M (number of connections per node) and efConstruction (search width during building)
• Memory trade-off: HNSW provides excellent recall but stores the full graph structure, increasing memory usage compared to IVF-based indices

A partitioning-based indexing technique that FAISS uses to cluster the embedding space using k-means. At query time, only the clusters (Voronoi cells) closest to the query vector are searched, dramatically reducing the number of distance computations.

• Index factory string: IVF4096,Flat for 4096 centroids with exact storage
• nprobe parameter: Controls how many clusters to search—higher values increase recall at the cost of speed
• Training requirement: IVF indices require a training phase to learn cluster centroids from a representative sample of vectors

A vector compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently. This reduces memory footprint by 4-16x, enabling billion-scale indices to fit in RAM.

• Mechanism: A 768-dimensional vector is split into 96 sub-vectors of 8 dimensions each, each quantized to 256 centroids
• Index factory string: IVF4096,PQ96 combines IVF partitioning with PQ compression
• Trade-off: PQ introduces quantization error that slightly reduces recall; compensated by using more coarse quantization or re-ranking with exact distances

FAISS provides native GPU support via CUDA, enabling brute-force exact search over millions of vectors in sub-millisecond time. GPU indices are drop-in replacements for CPU indices with identical APIs.

• GpuIndexFlatL2: GPU-accelerated exact L2 distance search
• Batch processing: GPU indices achieve maximum throughput when processing multiple queries simultaneously
• Multi-GPU: FAISS supports sharding indices across multiple GPUs for trillion-scale retrieval
• Limitation: GPU memory is typically smaller than system RAM, so PQ compression is often combined with GPU acceleration for large indices

FAISS's declarative API for constructing complex indices from a string-based specification. The factory pattern composes preprocessing, partitioning, and encoding components into a single index without manual configuration.

• Example: "PCA128,IVF4096,PQ96" applies PCA dimensionality reduction to 128 dimensions, partitions into 4096 clusters, and compresses with 96-byte PQ codes
• Common patterns: "OPQ64,IVF65536,PQ64" for optimized product quantization with IVF
• Preprocessing options: PCA, OPQ (Optimized Product Quantization), PCAR (PCA with random rotation)
• Encoding options: Flat (exact), PQ, SQ (Scalar Quantization), RQ (Residual Quantization)