Optimized Product Quantization (OPQ)
Optimized Product Quantization (OPQ) extends product quantization (PQ) by learning a linear transformation (rotation) of the vector space before splitting into subvectors. This reduces the distortion caused by splitting correlated dimensions across different codebooks and often improves recall at the same compression ratio.
Summary
- Learn rotation matrix R; apply x → R·x (or R·x then split). Subvectors become more “independent,” so per-subspace quantization loses less. Same code size as PQ; better approximation. Often used in IVFPQ.
Why rotation helps
In plain PQ, dimensions are split into contiguous blocks. If the data has strong correlation across those blocks, each subvector carries redundant information and the codebook wastes capacity. OPQ learns an orthogonal (or general linear) rotation so that after rotation, the subspaces are more independent—variance is better distributed across subvectors—and quantization error drops. The rotation is applied at encode and query time; the code structure (m subvectors, k centroids each) is unchanged, so memory and lookup cost match PQ.
Training and use
Training alternates between (1) fixing the rotation and learning codebooks (e.g. K-means per subspace on rotated subvectors), and (2) fixing the codebooks and updating the rotation to minimize reconstruction error. OPQ is often used with IVFPQ for large-scale ANN: IVF reduces the search set, OPQ+PQ compresses vectors with better fidelity than plain PQ.
Practical tip: use OPQ when PQ recall is insufficient and you can afford the extra training; product quantization (PQ) explained and the concept of codebooks in PQ describe the base mechanism. Trade-off between compression ratio and accuracy and accuracy vs. speed in quantization apply to OPQ as well.
Frequently Asked Questions
Does OPQ change code size?
No. Same m codes, same bits per code as PQ. Only the pre-processing (rotation) and codebook learning differ.
Is the rotation orthogonal?
Often yes (orthogonal or unitary), so it preserves norms and distances approximately; some variants use a general matrix.
When is OPQ worth the extra training?
When PQ recall is not enough and you can afford the build-time cost. High-dimensional or correlated data often benefits most.
How do I apply OPQ at query time?
Rotate the query with the same R, then compute PQ distances (e.g. lookup tables) against the rotated codebooks. One matrix-vector multiply per query.