PQ's blind spot: the fixed split
Recall base PQ. A vector x ∈ R^D is split into M contiguous subvectors of dimension D/M; each subvector is quantized against its own k-entry codebook (typically k = 256, so 8 bits per subquantizer), and the code is the concatenation of the M nearest-codeword indices. The reconstruction is q(x) = [c^1, c^2, …, c^M], and training minimizes total quantization error Σ_i ||x_i − q(x_i)||^2 by running k-means independently in each subspace.
The weak point is the word contiguous. PQ takes dimensions 1…D/M as subspace 1, the next block as subspace 2, and so on — an arbitrary, data-blind partition. If the embedding puts 90% of its energy in a handful of directions (as PCA spectra of real features routinely show), those high-variance dimensions crowd into a few subspaces while others get near-constant slices. A codebook spent on a low-variance slice is wasted; a high-variance slice is under-resourced. Correlation across subspace boundaries compounds the loss — PQ’s error is hostage to the coordinate system it was handed.
The key insight: a rotation is free
OPQ’s move rests on one fact: an orthogonal matrix R (with R^T R = I) preserves Euclidean distance. For any two vectors, ||Rx − Ry|| = ||x − y||, since (x−y)^T R^T R (x−y) = (x−y)^T (x−y). Rotating the entire dataset therefore leaves the nearest-neighbor structure — the thing we search — completely intact.
But while distances are invariant, how those distances distribute across the coordinate axes is not. A rotation can take an ellipsoidal cloud whose long axis lies at 45° to the axes and re-orient it so the variance lines up with the coordinates we are about to slice along. So OPQ has a free parameter to exploit: pick the R that makes the post-rotation coordinate split as quantization-friendly as possible. We quantize Rx, store the same compact codes, and rotate the query the same way at search time. Retrieval semantics are unchanged; only the reconstruction error shrinks. That is the whole idea — the rest is how to find a good R.
The OPQ objective
Where base PQ optimizes codebooks alone, OPQ optimizes the rotation and the codebooks jointly. Writing q(·) for the PQ quantizer (concatenate the nearest codeword from each of the M subspaces), the objective is:
minimize Σ_i || R x_i − q(R x_i) ||^2
R, C
subject to R^T R = I (R is D x D, orthogonal)
q(y) = [ c^1(y_1), ..., c^M(y_M) ] (PQ on the rotated y)Two knobs, one loss. The codebooks C = {c^m} are the usual PQ centroids; the new variable is the orthogonal R. Setting R = I recovers ordinary PQ, so OPQ can only do at least as well — the optimum over a larger feasible set cannot be worse. The constraint R^T R = I keeps the transform distance-preserving; drop it and you could collapse dimensions to cheat the loss while destroying the geometry. The difficulty is that R and C are coupled: the best split depends on the codebooks, and the best codebooks depend on the split. OPQ breaks that coupling two ways — a parametric closed form and a non-parametric alternating loop.
Why rotation helps: the distortion math
To see what a good R should achieve, model the rotated data as zero-mean Gaussian with covariance Σ. High-rate quantization theory says the minimum achievable distortion of a d-dimensional subspace, at a fixed bit budget, is proportional to the geometric mean of its variances — equivalently to (∏ λ_j)^(1/d), the d-th root of the product of the eigenvalues assigned to that subspace. Total distortion is the sum over the M subspaces:
D_total ∝ Σ_m ( ∏_{j ∈ subspace m} λ_j )^(1 / (D/M))Minimizing this reveals two design rules. First, decorrelate: R should diagonalize Σ — align the axes with the principal directions so no correlation leaks across slice boundaries. Second, balance the variance: for a fixed total, a sum of geometric means is smallest when the per-subspace products ∏ λ_j are all equal (a consequence of the AM–GM inequality). So the ideal R both removes correlation and spreads variance evenly across the M groups — exactly the two things the contiguous split fails to do.
The parametric (Gaussian) solution
Those two rules give a direct recipe when the data is roughly Gaussian. Step one, decorrelate: take the eigendecomposition of the covariance, Σ = U Λ U^T, and use the eigenvectors as a PCA rotation — this diagonalizes the data. Step two, balance: assign the D eigenvalue-directions to the M subspaces (each of size D/M) so the product of eigenvalues in every subspace is as equal as possible. A greedy pass — sort eigenvalues descending, drop each into the subspace with the currently smallest product — does the job. The final R is the PCA rotation composed with the permutation that realizes this assignment.
Worked example. Say D = 4, M = 2 (two 2-D subspaces), with eigenvalues λ = [100, 50, 2, 1]. The naive contiguous split after PCA pairs the two largest and the two smallest: products 100×50 = 5000 and 2×1 = 2 — wildly imbalanced. The balanced assignment pairs largest-with-smallest: {100, 1} and {50, 2}, giving products 100 and 100 — perfectly equal. Same eigenvalues, same PCA, but the balanced grouping slashes the summed geometric-mean distortion.
The non-parametric solution: alternating optimization
Real embeddings are not exactly Gaussian, so OPQ also offers a data-driven solver that optimizes the actual objective directly by alternating between the two coupled variables, holding one fixed while solving the other. Initialize R from the parametric solution above (a strong warm start), then iterate until the loss stops dropping:
repeat:
(1) fix R -> train codebooks C on the rotated data { R x_i }
= standard PQ: run k-means in each of the M subspaces
(2) fix C -> solve for the best orthogonal R given the current
reconstruction targets y_i = q(R x_i) [Procrustes]Step (1) is just plain PQ applied to Rx: quantize the rotated vectors and update the per-subspace centroids. Step (2) is the new piece. With the codebooks and each point’s codeword assignment frozen, every point has a fixed target y_i = q(R x_i), and we ask which orthogonal rotation best maps the raw x_i onto those targets. Each half-step can only lower (or hold) the shared loss, so the alternation converges monotonically to a local optimum — the same guarantee that underwrites Lloyd’s k-means.