Product quantisation (PQ) compresses each vector by cutting it into pieces and replacing every piece with the ID of its closest "prototype" piece from a small learned dictionary of 256, so each piece costs one byte.

Introduction

It is like describing a colour by the name of the nearest paint swatch instead of its exact RGB values: much shorter, slightly less precise.

  • example: a 768 number vector is cut into 64 pieces of 12 numbers, and stored as 64 bytes instead of 3072 bytes
  • the dictionaries are learned with k-means inside each piece
  • distances are estimated from small pre-computed tables, so search stays fast
  • PQ is usually combined with Inverted File Index (IVF) as "IVF-PQ", where clusters cut the search and codes cut the memory

Worked example: memory budget

10 million passages with 768 dimensional float32 embeddings (4 bytes per number), and PQ with pieces and 256 prototypes per piece.

PQ shrinks 30.72 GB to 0.64 GB, a factor of 48, so 10 million vectors fit on one ordinary server instead of a cluster. The price is approximate distances, so systems re-check the top few results with full precision vectors.

Code

def pq_memory(n_vectors, dim, m, bits=8, bytes_per_float=4):
    """Memory in bytes for raw float vectors vs product-quantised codes."""
    raw = n_vectors * dim * bytes_per_float    # every number stored as a 4 byte float
    codes = n_vectors * m * bits // 8          # m pieces per vector, 1 byte each when bits is 8
    return raw, codes
 
raw, codes = pq_memory(10_000_000, 768, m=64)
print(f"raw vectors : {raw / 1e9:.2f} GB")     # 30.72 GB
print(f"PQ codes    : {codes / 1e9:.2f} GB")   # 0.64 GB
print(f"compression : {raw / codes:.0f}x")     # 48x

The same idea as an index in faiss:

import faiss
 
d, m = 768, 64                                  # d must be divisible by m (768 / 64 = 12 numbers per piece)
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, 4096, m, 8)   # 4096 clusters, m pieces, 8 bits per piece
index.train(xb)
index.add(xb)
index.nprobe = 16

Another way to find neighbours quickly is to walk through a graph, see Hierarchical Navigable Small World (HNSW).