Vector quantization

Every quantization scheme replaces a real-valued vector with a small code (an integer, or a tuple of integers) plus a fixed codebook that maps codes back to approximate vectors. Search then happens on the codes — either by decompressing on the fly or by precomputing distance tables once per query.

The simplest scheme: per dimension, find the min/max across the dataset, then linearly map floats to uint8 (256 levels). You keep the vector layout, just shrink each number from 4 bytes to 1. Recall stays within ~1% of float32 for most embedding models, and distances can be computed directly on the int8 codes with SIMD.

import numpy as np

def fit_sq8(X):
    lo, hi = X.min(0), X.max(0)
    scale = (hi - lo) / 255.0
    return lo, scale

def encode_sq8(X, lo, scale):
    return np.clip(((X - lo) / scale).round(), 0, 255).astype(np.uint8)

def decode_sq8(C, lo, scale):
    return C.astype(np.float32) * scale + lo

PQ splits a D-dimensional vector into m sub-vectors of length D/m and runs k-means independently on each sub-space (typically k = 256 → one byte per sub-vector). A 1024-dim float32 vector with m=64 becomes 64 bytes — a 64× shrink.

At query time the database precomputes a small m × 256 table of distances from the query's sub-vectors to every centroid, then scores each candidate by summing 64 table lookups instead of doing a full dot product. That's why IVFPQ scales to billions on one machine.

import faiss, numpy as np

d, n = 1024, 200_000
xb = np.random.random((n, d)).astype("float32")

quantizer = faiss.IndexFlatL2(d)
# nlist=4096 coarse clusters, m=64 PQ sub-vectors, 8 bits each
index = faiss.IndexIVFPQ(quantizer, d, 4096, 64, 8)
index.train(xb)        # learns coarse centroids + 64 sub-codebooks
index.add(xb)
index.nprobe = 16      # how many coarse cells to scan
D, I = index.search(xb[:5], k=10)

Each float becomes a single bit (sign of the value, optionally after a random rotation). A 1024-dim vector collapses to 128 bytes, and distance is computed as Hamming weight of XOR — one CPU instruction per 64 dimensions. Recall is lower, so it's typically used as a first-stage filter that hands a few hundred candidates to a float re-ranker.

def to_binary(X):
    return np.packbits(X > 0, axis=1)  # (n, d/8) uint8

def hamming(a, b):
    return np.unpackbits(a ^ b, axis=-1).sum(-1)

A common production recipe: store float32 once on disk, hold a quantized copy in RAM for ANN search, and re-rank the top 100 candidates against the float32 originals. You get 8–32× memory savings with recall@10 nearly indistinguishable from exact search.