What optimizations do libraries like FAISS implement to maintain high throughput for vector search on CPUs, and how do these differ when utilizing GPU acceleration?

FAISS (Facebook AI Similarity Search) optimizes vector search on CPUs through efficient indexing structures, memory management, and parallel computation. One key technique is the use of product quantization (PQ) to compress high-dimensional vectors into smaller codes, reducing memory footprint and speeding up distance calculations. For example, PQ divides vectors into subvectors, each quantized into a small set of centroids, allowing approximate distance computations with lookup tables. FAISS also employs inverted file indexes (IVF), which partition the dataset into clusters and restrict searches to the most relevant clusters, drastically reducing the number of distance computations. Additionally, FAISS leverages SIMD (Single Instruction, Multiple Data) instructions like AVX2 to parallelize operations on CPU cores, enabling bulk processing of vector comparisons. Batch processing of queries further optimizes cache usage, minimizing memory latency. These methods prioritize reducing computational overhead while maintaining acceptable accuracy, making them suitable for latency-sensitive applications on commodity hardware.

When using GPU acceleration, FAISS shifts strategies to exploit the massively parallel architecture of GPUs. Unlike CPUs, which rely on hierarchical cache optimization and SIMD, GPUs handle thousands of concurrent threads, making brute-force exact search more feasible. For instance, FAISS on GPU can compute distances between all query and database vectors in parallel using CUDA kernels, bypassing the need for IVF clustering in some cases. Memory bandwidth becomes a critical factor: GPUs like NVIDIA A100 offer over 1.5 TB/s bandwidth, allowing rapid data transfer for large batches. FAISS also uses specialized data structures like GpuIndexIVFPQ, which combines IVF and PQ but stores quantized vectors in GPU memory to avoid CPU-GPU data transfer bottlenecks. However, GPU memory constraints require careful management—indexes may need to be sharded across multiple GPUs or combined with CPU memory for larger datasets. These optimizations prioritize throughput over latency, making GPUs ideal for batch processing scenarios with high query volumes.

The primary differences lie in parallelism granularity and memory handling. CPU optimizations focus on algorithmic shortcuts (like IVF) and lightweight parallelism (SIMD) to compensate for limited core counts, while GPUs exploit brute-force parallelism and high memory bandwidth. For example, a CPU might use IVF to reduce a 1M-vector search to 10k comparisons per query, whereas a GPU could compute all 1M distances in parallel but require more memory. Additionally, CPU implementations often trade exact results for speed via quantization, whereas GPUs can afford more exhaustive searches. Practical considerations include cost and scale: CPUs are simpler to deploy for smaller datasets or low-latency single queries, while GPUs excel in throughput-oriented tasks like real-time recommendation systems processing thousands of queries per second. FAISS’s hybrid CPU/GPU support allows developers to choose based on their infrastructure and workload requirements.