Codebook

A codebook is a set of K representative centroid vectors learned from the data distribution. Each original vector is replaced by the ID of its nearest centroid, reducing storage from D floating-point numbers to a single integer. The codebook itself stores the full-precision centroids for reconstruction. Typical codebook sizes range from 256 (8-bit codes) to 4096 (12-bit codes), balancing compression ratio against quantization error.

Codebooks are typically constructed using the Lloyd's k-means algorithm on a representative training set. The process iteratively:

• Assigns each training vector to the nearest centroid
• Updates centroids to the mean of their assigned vectors
• Repeats until convergence or a maximum iteration count

The resulting centroids minimize the within-cluster sum of squared errors, ensuring the codebook optimally represents the training distribution under Euclidean distance.

In Product Quantization (PQ), a high-dimensional vector is split into M equal-length subvectors, each quantized using its own distinct codebook. For a 128-dimensional vector split into 8 subvectors of 16 dimensions, each with a 256-entry codebook:

• Storage drops from 128 floats (512 bytes) to 8 bytes
• The total number of representable vectors is 256^8, despite storing only 8 × 256 centroids
• This exponential expressiveness with linear storage is the key insight behind PQ's effectiveness

Codebooks enable Asymmetric Distance Computation (ADC) for fast similarity search. When a query arrives:

1. Compute distances between the query subvectors and all centroids in each codebook
2. Build M lookup tables of size K each
3. For any database vector, approximate its distance to the query by summing precomputed table values using its stored codes

This replaces expensive D-dimensional distance calculations with M integer table lookups and additions, yielding 10-50x speedups.

The quantization error — the mean squared distance between original vectors and their codebook reconstructions — decreases as codebook size K increases. However:

• Larger K increases training time and lookup table computation cost
• For PQ with M sub-codebooks of size K, total training complexity is O(M × K × D_sub × iterations)
• Practical sweet spots: K=256 for 8-bit codes, K=65536 for 16-bit codes in high-precision scenarios
• Residual quantization can reduce error by encoding the difference between the original vector and its first-stage approximation

Effective codebooks require a training set representative of the query distribution. Best practices include:

• Using 100K to 1M training vectors per codebook for stable convergence
• Applying k-means++ initialization to avoid poor local minima
• Running multiple restarts and selecting the clustering with lowest distortion
• For dynamic datasets, implementing online codebook updates or periodic retraining to prevent distribution drift

Poorly trained codebooks exhibit high quantization error on production data, directly degrading search recall.