Explain the internal working of product quantization (PQ) in vector indexing?

Product Quantization compresses a high-dimensional vector by splitting it into several smaller sub-vectors and separately approximating each sub-vector using a small, shared codebook, dramatically reducing the storage and computation cost of comparing vectors at the price of some precision loss.

During index build, the original vector (say, 512 dimensions) is split into M sub-vectors (say, 8 sub-vectors of 64 dimensions each), and a separate small codebook of centroids is trained for each of those M positions via k-means; each sub-vector is then replaced by just the ID of its nearest centroid in that position's codebook, shrinking a 512 32-bit floats vector down to just 8 small integer codes.

At query time, instead of decompressing stored vectors back to full precision, LanceDB precomputes the distance from the query's own sub-vectors to every centroid in each codebook, then estimates a candidate's total distance to the query via fast table lookups summed across its M codes — avoiding expensive full-precision distance computation while still producing a reasonably accurate distance ranking.