Billion-Scale Similarity Search with GPUs

The Problem

As neural networks became standard for generating dense embeddings for images, text, and users, platforms needed a way to find the "k-nearest neighbors" (k-NN) to a query vector among billions of stored vectors. Exact search (computing distance to every vector) is O(N) and impossible at this scale. Existing Approximate Nearest Neighbor (ANN) algorithms were designed for CPUs, couldn't scale to billions of vectors while remaining in memory, and failed to exploit the massive parallelism of GPUs.

The Idea

The Facebook AI Research (FAIR) team developed a highly optimized GPU-based library (FAISS) for similarity search. They solved the scale problem by combining two techniques: Inverted File (IVF) indexing to avoid searching the whole dataset, and Product Quantization (PQ) to heavily compress the vectors so they fit in GPU memory. They designed custom GPU kernels that could execute these operations at unprecedented speeds.

How It Works

The system relies on an inverted index with quantization:

1. Coarse Quantization (IVF): The vector space is partitioned into thousands of clusters using k-means (Voronoi cells). When a query arrives, the system only searches the vectors residing in the closest few cells, ignoring the vast majority of the dataset.
2. Product Quantization (PQ): To fit a billion vectors in RAM, each vector is chopped into sub-vectors. Each sub-vector is replaced by the ID of its closest centroid from a small, pre-computed codebook. A 4096-byte vector can be compressed to just a few bytes, allowing distance approximations via lookups.
3. GPU Optimization: The authors wrote highly parallelized CUDA kernels specifically designed to keep the GPU's execution units fed and memory bandwidth saturated, utilizing registers and shared memory effectively.

Why It Mattered

This paper and the open-source FAISS library made modern neural search production-ready. It proved that you could perform nearest-neighbor searches on a billion vectors in milliseconds on a single server with a GPU. It unlocked the transition from sparse keyword search to dense semantic search across the industry.

What Came After

FAISS became the gold standard for dense retrieval and remains widely used. While HNSW (navigable graphs) later became preferred for pure speed-accuracy tradeoffs when memory isn't a bottleneck, FAISS's IVF-PQ remains the default choice when you need to index datasets too large to fit uncompressed in RAM. It paved the way for modern vector databases like Pinecone, Milvus, and Weaviate.