IVF and product quantisation
How vector search scales to billions: search only the nearest clusters, and shrink every vector to a few bytes.
Read first:EmbeddingsHNSW vector search
Step 1 of 6· Illustrative 2-D points; the k-means cells, residuals, product codes and table distances are computed live, and the memory maths is real
With hundreds of millions of vectors, even storing them gets expensive, let alone comparing a query with each one. IVF with product quantisation tackles both problems. First, the vectors are sorted into clusters, each with a centre point, and a query is compared only with the members of its few nearest clusters. Second, each vector is squeezed into a short code: it is cut into pieces, and each piece is replaced by the number of the closest entry in a small learned codebook. A 512-byte vector can shrink to 8 bytes, and distances can be estimated straight from the codes with a few table lookups.
Why it matters for your product
At large scale, simply holding the vectors in memory becomes the problem. One billion 128-number vectors take 512 GB as 32-bit floats but 8 GB as 8-byte codes. The price is accuracy: coarser codes and fewer probed cells miss more true neighbours, so tune nprobe and code size against measured recall, and consider re-ranking a shortlist with fuller vectors. The Faiss authors suggest graph indexes such as HNSW for up to about 10 million vectors that fit comfortably in memory, and IVF indexes, compressed to the memory budget, beyond that.
For engineersShow the maths
distances per query ≈ nlist + nprobe × N ÷ nlist
Compare the query with every centroid, then scan the probed lists, assuming the lists are equal in size. The total is smallest when nlist = √(nprobe × N), which is why nlist is usually set in proportion to √N.
Worked example: N = 1,000,000 and nprobe = 16: with nlist = 4,000, the query makes 4,000 + 16 × 250 = 8,000 distance computations, 125 times fewer than brute force.
code = m × log₂(k*) bits; possible reproductions = k*ᵐ
Each of the m pieces stores one index into its own k*-entry codebook. The small codebooks together stand for k* to the power m different vectors, far more than could ever be stored as one codebook.
Worked example: D = 128, m = 8, k* = 256: 8 × 8 = 64 bits, 8 bytes per vector instead of 512, with 256⁸ ≈ 1.8 × 10¹⁹ possible reproductions.
d(x, y)² ≈ Σⱼ table_j[ code_j(y) ], table_j[i] = ‖u_j(x − c) − c_{j,i}‖²
Split the query's residual against the cell centre c into the same pieces, fill one table per piece with its squared distance to every codebook entry, then score each stored vector by adding m entries.
Worked example: With m = 8 and k* = 256 the query fills 8 × 256 = 2,048 table entries per probed cell; after that each candidate in the cell costs just 8 lookups and additions.
Distances from codes are estimates, and heavy compression loses a lot: with 8-byte codes on a billion SIFT vectors, searched in 17.7 µs per query on one GPU, Johnson et al. found the true nearest neighbour in the top 10 for 37.6% of queries. Centroids and codebooks are learned from a training sample, and uneven cell sizes make some queries slower than the formula suggests.
The words you will hear
Coarse quantiser
Primary sources
- 01Product Quantization for Nearest Neighbor SearchJégou et al. · 2011
- 02Billion-scale similarity search with GPUsJohnson et al. · 2017
- 03The Faiss libraryDouze et al. · 2024
Connected ideas
Retrieval and search
HNSW vector search
How a stack of sparse-to-dense graphs finds the nearest vectors without checking them all.
ExploreSpeed and cost
Quantisation
Storing a model's numbers with fewer bits, and keeping the answers nearly the same.
ExploreRetrieval and search
Retrieval-augmented generation (RAG)
How a model answers from your documents, and shows you exactly where each claim came from.
ExploreRetrieval and search
Hybrid search and reranking
Search by exact words and by meaning at once, merge the two lists, then let a slower model reread the best few.
ExploreWant this working on your data?
We design and build the systems these ideas power: retrieval, agents, voice and the models behind them. Start with a free discovery call.