Product Quantization

Compressing vectors to a few bytes each and computing distances from the compressed codes. Vector quantization and its error, the product quantizer of Jégou, Douze and Schmid with one small k-means codebook per sub-vector, the memory arithmetic, asymmetric and symmetric distance computation with lookup tables derived, the proofs that the error of the estimated distance is bounded by the quantization error and that the squared estimate falls short of the squared distance by exactly that error on average, a full example on eight vectors worked by hand, measurements on 399,000 GloVe vectors, the optimized rotation (OPQ) with its Procrustes step proved, and the inverted file with compressed lists. Worked problems on encoding, lookup tables, memory and eigenvalue allocation.

The 399,000 GloVe word vectors of this unit have 100 dimensions each, stored as 32-bit floating-point numbers: 400 bytes per vector and 159.6 megabytes in all. A product quantizer stores each of them in 10 bytes, 3.99 megabytes in all, and still answers nearest neighbor queries. For the query word neighborhood, a scan of the 10-byte codes places five of its ten true neighbors among its ten best, and all ten among its thirty best. How can 80 bits stand in for 3,200, how is a distance computed from a code without rebuilding the vector, and how large is the error?

Product quantization splits each vector into $M$ sub-vectors, replaces each sub-vector by the number of the nearest entry in a small codebook learned for that position, and stores the $M$ numbers. The distance from a query to a stored vector is then estimated by adding $M$ numbers read from tables that are computed once per query. The method is due to Jégou, Douze and Schmid (2011), and this article follows their paper.

Here is the route. First we define a quantizer and its error, and see why a single codebook cannot reach a useful size. Then we build the product quantizer, prove its two structural properties, and work a complete example on eight vectors by hand. Next we derive the two ways of computing distances from codes, and prove how wrong the estimates can be. Then we measure all of it on the GloVe vectors. Finally we describe the rotation that prepares vectors for quantization (OPQ) and the combination with an inverted file. The article assumes the k-means algorithm, whose objective is the quantization error used here, and inverted file indexes for vectors. Recall@$k$ and the dataset are those of nearest neighbor search in high dimensions. The numbers are computed by tools/experiments/vectors/product-quantization.py with the implementation in pq.py beside it.

Quantization: a codebook and its error

To quantize a vector is to replace it by one of a finite list of vectors. The list is the codebook $\mathcal{C} = \{\vec c_1, \dots, \vec c_k\}$, its entries are centroids (also called codewords or reproduction values), and the quantizer is the function $Q$ that sends each vector $\vec x \in \mathbb{R}^m$ to a centroid $Q(\vec x) \in \mathcal{C}$. Only the number of the centroid is stored, which takes $\log_2 k$ bits. The set of vectors sent to the same centroid is a cell.

Quantization loses information, and the standard measure of the loss is the mean squared error between the vectors and their centroids (Jégou, Douze, and Schmid, 2011, equation 3). For the $N$ base vectors $\vec x_1, \dots, \vec x_N$ it is

$$\mathrm{MSE}(Q) = \frac{1}{N} \sum_{n=1}^{N} \lvert \vec x_n - Q(\vec x_n) \rvert^2 .$$

This is the residual sum of squares of the k-means article divided by $N$, with the cells as the clusters. So the codebook of $k$ centroids with the smallest error is the best k-means clustering into $k$ clusters, and Lloyd's algorithm is the standard way to look for it. Its two steps are the two conditions an optimal quantizer must meet, which the quantization literature calls the Lloyd conditions (Jégou, Douze, and Schmid, 2011, equations 4 and 5; for the field they refer to the survey of Gray and Neuhoff, 1998):

  • each vector is sent to its nearest centroid (the assignment step);
  • each centroid is the mean of the vectors sent to it (the update step).

The k-means article proves that each step lowers the error and that the algorithm stops at a local minimum, not necessarily the best codebook. The second condition is used twice below, and it is worth stating what it gives: in every cell, the errors $\vec x - Q(\vec x)$ of the cell's vectors add up to the zero vector.

How many centroids does a useful code need? The error falls as $k$ grows, and a code of 80 bits can name $k = 2^{80}$ centroids. That codebook cannot be built. It would hold $2^{80} \approx 1.2 \times 10^{24}$ centroids of 100 numbers each, about $4.8 \times 10^{26}$ bytes, and k-means would need several training vectors per centroid to learn it. Jégou, Douze and Schmid make the same count for 64-bit codes and conclude that neither the learning nor the storage is possible. The authors of the Faiss library put the practical limit of a plain k-means codebook at roughly three-byte codes, about 16 million centroids (Douze et al., 2026, section 4.1 of the arXiv version, 2401.08281v4, which is the version read). The product quantizer is a way to get $2^{80}$ centroids without storing or learning them one by one.

The product quantizer

Here is the idea in one sentence: cut every vector into $M$ pieces, learn a small codebook for each piece position, and let the centroids of the whole vector be all the ways of gluing one small centroid from each codebook end to end.

The formal version. Let $M$ divide the dimension $m$. Write a vector as the concatenation of $M$ sub-vectors of $m/M$ coordinates each,

$$\vec x = \big(\vec x^{(1)}, \vec x^{(2)}, \dots, \vec x^{(M)}\big), \qquad \vec x^{(j)} \in \mathbb{R}^{m/M},$$

so that $\vec x^{(1)}$ holds coordinates 1 to $m/M$, $\vec x^{(2)}$ the next $m/M$, and so on. For each position $j$ there is a sub-quantizer $Q_j$ with its own sub-codebook $\mathcal{C}_j = \{\vec c_{j,1}, \dots, \vec c_{j,k^*}\}$ of $k^*$ centroids in $\mathbb{R}^{m/M}$, learned by k-means on the $j$th sub-vectors of a training set. The product quantizer applies them side by side (Jégou, Douze, and Schmid, 2011, equation 8):

$$Q(\vec x) = \big(Q_1(\vec x^{(1)}), \dots, Q_M(\vec x^{(M)})\big).$$

The code of $\vec x$ is the list of the $M$ centroid numbers, $(i_1, \dots, i_M)$ with $Q_j(\vec x^{(j)}) = \vec c_{j, i_j}$. It takes $M \log_2 k^*$ bits. The symbol $k^*$ is the paper's; $k$ without a star is kept in this unit for the number of neighbors wanted.

The codebook of $Q$ is the Cartesian product $\mathcal{C} = \mathcal{C}_1 \times \dots \times \mathcal{C}_M$: every concatenation of one centroid from each sub-codebook. It has $(k^*)^M$ centroids, and it is never written out. What is stored is the $M$ sub-codebooks, $M \cdot k^* \cdot (m/M) = k^* m$ numbers. With $M = 10$ and $k^* = 256$ on 100-dimensional vectors, the product codebook has $256^{10} = 2^{80}$ centroids and is defined by $256 \times 100 = 25{,}600$ numbers, 102,400 bytes. Jégou, Douze and Schmid (2011, Table I) set this against k-means, whose codebook and assignment both cost $k\,m$ for $k$ centroids, where the product quantizer's cost is $k^{1/M} m$.

Two properties make the construction work. Both follow from one fact: a squared Euclidean distance is a sum over coordinates, so it splits into a sum over the $M$ blocks of coordinates,

$$\lvert \vec x - \vec y \rvert^2 = \sum_{j=1}^{M} \lvert \vec x^{(j)} - \vec y^{(j)} \rvert^2 \qquad \text{for all } \vec x, \vec y \in \mathbb{R}^m. \tag{1}$$

Property 1 (encoding is done piece by piece). Concatenating a nearest centroid of each sub-codebook to the corresponding sub-vector gives a centroid of the product codebook nearest to $\vec x$, and every nearest centroid of the product codebook arises in this way. Proof. A centroid of $\mathcal{C}$ is $\vec c = (\vec c^{(1)}, \dots, \vec c^{(M)})$ with each $\vec c^{(j)}$ chosen freely from $\mathcal{C}_j$. By (1), $\lvert \vec x - \vec c \rvert^2 = \sum_j \lvert \vec x^{(j)} - \vec c^{(j)} \rvert^2$. The $j$th term depends only on the choice of $\vec c^{(j)}$, so the sum is smallest exactly when every term is smallest, that is, when each $\vec c^{(j)}$ is a centroid of $\mathcal{C}_j$ nearest to $\vec x^{(j)}$. Where a sub-vector is equally near two centroids there are several nearest product centroids, and a fixed rule, here the lower number, chooses among them. So $Q$ as defined above sends each vector to a nearest centroid among all $(k^*)^M$, at the cost of $M k^*$ distance computations in $m/M$ dimensions, which is the arithmetic of $k^*$ distances in $m$ dimensions. Ge, He, Ke and Sun (2013, section 2.2) make the same observation and conclude that minimizing the error of a product codebook splits into $M$ separate k-means problems.

Property 2 (the error adds over the pieces). $\mathrm{MSE}(Q) = \sum_{j=1}^{M} \mathrm{MSE}(Q_j)$, where $\mathrm{MSE}(Q_j)$ is the mean squared error of the $j$th sub-quantizer on the $j$th sub-vectors. Proof. Apply (1) to $\vec x_n$ and $Q(\vec x_n)$, whose $j$th sub-vector is $Q_j(\vec x_n^{(j)})$, and average over $n$:

$$\frac{1}{N}\sum_n \lvert \vec x_n - Q(\vec x_n) \rvert^2 = \frac{1}{N}\sum_n \sum_j \lvert \vec x_n^{(j)} - Q_j(\vec x_n^{(j)}) \rvert^2 = \sum_j \mathrm{MSE}(Q_j).$$

This is equation 11 of the paper.

The product codebook is large but not free in shape: its centroids form a grid, every combination of the sub-centroids, whether or not any data lie near that combination. A k-means codebook of the same size would put its centroids where the data are. That is the price of the construction, and it is why the order and grouping of the coordinates matters, a point the section on OPQ returns to.

Memory

The saving is plain arithmetic. An uncompressed vector takes $32m$ bits. Its code takes $M \log_2 k^*$ bits.

Per vector The 399,000 GloVe vectors ($m = 100$)
32-bit floating point $32 \times 100 = 3{,}200$ bits $= 400$ bytes 159,600,000 bytes
Code, $M = 10$, $k^* = 256$ $10 \times 8 = 80$ bits $= 10$ bytes 3,990,000 bytes
Sub-codebooks $10 \times 256 \times 10 \times 4 = 102{,}400$ bytes

The codes are 40 times smaller than the vectors. The choice $k^* = 256$ makes each centroid number exactly one byte, and it is the value the paper uses throughout its comparisons, with $M = 8$ for its 128-dimensional vectors.

A worked example on eight vectors

Eight vectors in four dimensions are quantized with $M = 2$ sub-vectors of two coordinates and $k^* = 2$ centroids per sub-codebook. A code is then two bits, against $4 \times 32 = 128$ bits for the vector. Every number can be checked by hand, and the script does so in exact arithmetic.

Vector First half $\vec x^{(1)}$ Second half $\vec x^{(2)}$
$\vec x_1$ (0, 0) (1, 6)
$\vec x_2$ (1, 2) (5, 1)
$\vec x_3$ (3, 1) (2, 8)
$\vec x_4$ (0, 1) (6, 3)
$\vec x_5$ (6, 5) (3, 5)
$\vec x_6$ (8, 4) (8, 0)
$\vec x_7$ (7, 7) (2, 5)
$\vec x_8$ (7, 4) (5, 0)

Learning the first sub-codebook. Run k-means with two centroids on the eight first halves, seeded with those of $\vec x_1$ and $\vec x_5$, $(0, 0)$ and $(6, 5)$. The first halves of $\vec x_1$ to $\vec x_4$ are nearer $(0, 0)$ and those of $\vec x_5$ to $\vec x_8$ nearer $(6, 5)$. For example $(3, 1)$ is at squared distance $9 + 1 = 10$ from the first seed and $9 + 16 = 25$ from the second. The means of the two groups are

$$\vec c_{1,1} = \tfrac{1}{4}\big((0,0) + (1,2) + (3,1) + (0,1)\big) = (1, 1), \qquad \vec c_{1,2} = \tfrac{1}{4}\big((6,5) + (8,4) + (7,7) + (7,4)\big) = (7, 5).$$

No vector changes group with these centroids, so the algorithm has stopped.

Learning the second sub-codebook. The same on the second halves, seeded with those of $\vec x_1$ and $\vec x_2$, $(1, 6)$ and $(5, 1)$, groups the vectors with odd numbers against those with even numbers, and gives

$$\vec c_{2,1} = \tfrac{1}{4}\big((1,6) + (2,8) + (3,5) + (2,5)\big) = (2, 6), \qquad \vec c_{2,2} = \tfrac{1}{4}\big((5,1) + (6,3) + (8,0) + (5,0)\big) = (6, 1).$$

Both sub-codebooks are the best possible ones: the script tries all 127 ways of splitting eight points into two nonempty groups, in each half, and none has a smaller error. They are also what k-means reaches from a poor start. Seeded with the second halves of $\vec x_1$ and $\vec x_3$, which belong to the same group, it reaches the same two centroids in three assignment steps.

Codes and errors. Each vector's code is the pair of centroid numbers of its two halves. The squared error of each half is its squared distance to its centroid.

Vector Code Reconstruction $Q(\vec x)$ Squared error, first half Second half Whole vector
$\vec x_1$ (1, 1) (1, 1, 2, 6) 2 1 3
$\vec x_2$ (1, 2) (1, 1, 6, 1) 1 1 2
$\vec x_3$ (1, 1) (1, 1, 2, 6) 4 4 8
$\vec x_4$ (1, 2) (1, 1, 6, 1) 1 4 5
$\vec x_5$ (2, 1) (7, 5, 2, 6) 1 2 3
$\vec x_6$ (2, 2) (7, 5, 6, 1) 2 5 7
$\vec x_7$ (2, 1) (7, 5, 2, 6) 4 1 5
$\vec x_8$ (2, 2) (7, 5, 6, 1) 1 2 3
Sum 16 20 36

The sub-quantizers have errors $\mathrm{MSE}(Q_1) = 16/8 = 2$ and $\mathrm{MSE}(Q_2) = 20/8 = 2.5$, and the product quantizer has $\mathrm{MSE}(Q) = 36/8 = 4.5 = 2 + 2.5$, as Property 2 requires. The product codebook has $2^2 = 4$ centroids, the four reconstructions in the table, defined by four stored sub-centroids. Property 1 can be checked directly: for each of the eight vectors, and for every point of the integer grid from $-1$ to 9 in all four coordinates, the product centroid named by the two nearest sub-centroids is at the least distance among the four.

The example continues below with a query.

Distances from codes

A search needs the distance from the query $\vec q$ to every base vector $\vec x$, and only the codes are stored. The paper gives two estimates (Jégou, Douze, and Schmid, 2011, section III.A).

Asymmetric distance computation

The first estimate replaces the base vector by its reconstruction and leaves the query as it is:

$$\tilde d(\vec q, \vec x) = \lvert \vec q - Q(\vec x) \rvert .$$

It is called asymmetric distance computation (ADC) because only one of the two vectors is quantized. Here is the idea of its computation in one sentence: by (1) the squared estimate is a sum of $M$ terms, the $j$th term depends on $\vec x$ only through the $j$th number of its code, and that number takes only $k^*$ values, so all possible terms can be computed before any code is read.

The derivation. Let the code of $\vec x$ be $(i_1, \dots, i_M)$, so that the $j$th sub-vector of $Q(\vec x)$ is $\vec c_{j, i_j}$. Apply (1) to $\vec q$ and $Q(\vec x)$:

$$\tilde d(\vec q, \vec x)^2 = \sum_{j=1}^{M} \big\lvert \vec q^{(j)} - \vec c_{j, i_j} \big\rvert^2 = \sum_{j=1}^{M} T_j[i_j], \qquad \text{where } T_j[i] = \big\lvert \vec q^{(j)} - \vec c_{j,i} \big\rvert^2 . \tag{2}$$

This is equation 13 of the paper. The numbers $T_j[i]$, for $j = 1, \dots, M$ and $i = 1, \dots, k^*$, form $M$ lookup tables of $k^*$ entries each. They depend on the query and the codebooks and not on any base vector. A search therefore has two phases:

  1. compute the $M k^*$ table entries: $M k^*$ squared distances in $m/M$ dimensions, the arithmetic of $k^*$ distances in $m$ dimensions;
  2. for each of the $N$ codes, read one entry from each table and add the $M$ numbers.

No square root is needed, since the order of the squared estimates is the order of the estimates. The paper's Table II gives the same count: $k^* m$ operations to prepare a query, whatever the size of the collection, and $N M$ to scan it. An exact scan costs $N m$ multiplications. With $M = 10$ and $m = 100$ the scan reads and adds ten numbers per vector where the exact scan multiplies and adds a hundred, and it reads 10 bytes of memory per vector where the exact scan reads 400.

On the eight vectors. Let the query be $\vec q = (2, 2, 4, 4)$, with halves $(2, 2)$ and $(4, 4)$. The tables are

Centroid 1 Centroid 2
$T_1$ (first half) $\lvert (2,2) - (1,1) \rvert^2 = 2$ $\lvert (2,2) - (7,5) \rvert^2 = 34$
$T_2$ (second half) $\lvert (4,4) - (2,6) \rvert^2 = 8$ $\lvert (4,4) - (6,1) \rvert^2 = 13$

and each estimate is one entry of $T_1$ plus one entry of $T_2$:

Vector Code $\tilde d^2 = T_1[i_1] + T_2[i_2]$ True $\lvert \vec q - \vec x \rvert^2$ Rank by estimate True rank
$\vec x_1$ (1, 1) $2 + 8 = 10$ 21 1 3
$\vec x_2$ (1, 2) $2 + 13 = 15$ 11 3 2
$\vec x_3$ (1, 1) $2 + 8 = 10$ 22 1 4
$\vec x_4$ (1, 2) $2 + 13 = 15$ 10 3 1
$\vec x_5$ (2, 1) $34 + 8 = 42$ 27 5 5
$\vec x_6$ (2, 2) $34 + 13 = 47$ 72 7 8
$\vec x_7$ (2, 1) $34 + 8 = 42$ 55 5 7
$\vec x_8$ (2, 2) $34 + 13 = 47$ 46 7 6

Three things show in this small table, and all three hold at full scale.

  • The estimate is the distance to the reconstruction. For $\vec x_1$, $\lvert (2,2,4,4) - (1,1,2,6) \rvert^2 = 1 + 1 + 4 + 4 = 10$, the value the tables gave without forming the reconstruction.
  • Vectors with the same code are indistinguishable. There are four codes, so there are four distinct estimates, and each pair of vectors sharing a code is tied. In general the estimates for one query take at most $(k^*)^M$ values.
  • The ranking is approximately right, not exactly. The estimate puts $\vec x_1$ and $\vec x_3$ first. The true nearest vectors are $\vec x_4$ and $\vec x_2$. With two neighbors wanted, the two best by estimate contain neither of the true two, a recall@2 of 0. The four best by estimate, $\vec x_1, \vec x_3, \vec x_2, \vec x_4$, do contain both.

The third point is how compressed codes are used in practice when the original vectors can still be reached: take a short-list of the $R$ best by estimated distance, compute the exact distance to those $R$ only, and return the best $k$ of them. The paper adds such a verification stage for its comparison with an index that keeps the vectors (section V.D), and this unit calls it re-ranking. Here, re-ranking the four best by estimate with exact distances returns $\vec x_4$ and $\vec x_2$, the right answer, after four exact distance computations in place of eight.

Symmetric distance computation

The second estimate quantizes the query as well:

$$\hat d(\vec q, \vec x) = \lvert Q(\vec q) - Q(\vec x) \rvert, \qquad \hat d(\vec q, \vec x)^2 = \sum_{j=1}^{M} \big\lvert \vec c_{j, i_j(\vec q)} - \vec c_{j, i_j(\vec x)} \big\rvert^2 ,$$

where $i_j(\cdot)$ is the $j$th number of a vector's code. This is symmetric distance computation (SDC), equation 12 of the paper. Each term is now a distance between two centroids of the same sub-codebook, so the tables do not depend on the query at all: for each $j$, a $k^* \times k^*$ table of squared distances between centroids is computed once and kept. A query is encoded, which costs the same $k^* m$ operations as building the asymmetric tables, and the scan again adds $M$ numbers per code.

On the eight vectors, the query's halves $(2,2)$ and $(4,4)$ are nearest $\vec c_{1,1}$ and $\vec c_{2,1}$ (the smaller entries of the tables above), so its code is (1, 1). The two centroid tables hold $\lvert \vec c_{1,1} - \vec c_{1,2} \rvert^2 = 36 + 16 = 52$ and $\lvert \vec c_{2,1} - \vec c_{2,2} \rvert^2 = 16 + 25 = 41$, and zeros on their diagonals. The symmetric estimates are 0 for the code (1, 1), 41 for (1, 2), 52 for (2, 1) and 93 for (2, 2). Every vector that shares the query's code gets the estimate 0, however far away it is.

The two methods cost the same per query. The asymmetric one is the more accurate in the paper's experiments and in the measurements below. The next section proves bounds on both errors, and the bound for the symmetric estimate is the larger. The paper's advice is to quantize the base vectors and not the query whenever the query is available as a vector, and it names one case for the symmetric form: when the queries themselves must be stored as codes.

How wrong the estimates are

The estimates are wrong by an amount that the quantization error controls. The results of this section make that precise. The first is the bound the paper gives (its section III.B, equations 14 to 18). The paper derives it from the triangle inequality for each pair of a query and a base vector (its equations 15 and 16), integrates, and states the result as an expectation over the distributions of both. The same inequality gives the result for every single query, with the average taken over the base vectors, and that is the form proved here.

Theorem 1 (the asymmetric bound). For any quantizer $Q$, any query $\vec q$ and any vector $\vec x$,

$$\big\lvert\, \lvert \vec q - \vec x \rvert - \tilde d(\vec q, \vec x) \,\big\rvert \le \lvert \vec x - Q(\vec x) \rvert .$$

Consequently, for every query, the mean over the base vectors of the squared error of the estimated distance is at most the quantization error:

$$\frac{1}{N} \sum_{n=1}^{N} \big( \lvert \vec q - \vec x_n \rvert - \tilde d(\vec q, \vec x_n) \big)^2 \le \mathrm{MSE}(Q).$$

Proof. The triangle inequality for the three points $\vec q$, $\vec x$ and $Q(\vec x)$ says $\lvert \vec q - \vec x \rvert \le \lvert \vec q - Q(\vec x) \rvert + \lvert Q(\vec x) - \vec x \rvert$, and also $\lvert \vec q - Q(\vec x) \rvert \le \lvert \vec q - \vec x \rvert + \lvert \vec x - Q(\vec x) \rvert$. The first gives $\lvert \vec q - \vec x \rvert - \tilde d \le \lvert \vec x - Q(\vec x) \rvert$ and the second gives $\tilde d - \lvert \vec q - \vec x \rvert \le \lvert \vec x - Q(\vec x) \rvert$. Together they are the first claim. Squaring it and averaging over the base vectors gives the second, since the right side averages to $\mathrm{MSE}(Q)$ by definition. Nothing was assumed about $Q$: the result holds for a product quantizer, for k-means, and for a quantizer that satisfies neither Lloyd condition.

The geometric content is simple. The estimate measures the distance to the wrong point, and the wrong point is within $\lvert \vec x - Q(\vec x) \rvert$ of the right one, so the two distances cannot differ by more than that.

Theorem 2 (the symmetric bound). For any quantizer $Q$, the mean, over all $N^2$ ordered pairs of base vectors, of the squared error of the symmetric estimate is at most twice the quantization error:

$$\frac{1}{N^2} \sum_{a=1}^{N} \sum_{b=1}^{N} \big( \lvert \vec x_a - \vec x_b \rvert - \hat d(\vec x_a, \vec x_b) \big)^2 \le 2\, \mathrm{MSE}(Q).$$

The paper states this bound, saying that a derivation similar to the asymmetric one gives it. The proof below is ours, and it shows where the factor of two comes from: both vectors of the pair carry a quantization error.

Proof. Write $\vec e_a = \vec x_a - Q(\vec x_a)$ for the error vector of $\vec x_a$. Then $Q(\vec x_a) - Q(\vec x_b) = (\vec x_a - \vec x_b) - (\vec e_a - \vec e_b)$. The triangle inequality, used in both directions as in Theorem 1, gives

$$\big\lvert\, \lvert \vec x_a - \vec x_b \rvert - \lvert Q(\vec x_a) - Q(\vec x_b) \rvert \,\big\rvert \le \lvert \vec e_a - \vec e_b \rvert .$$

Square and average over all pairs. The right side becomes

$$\frac{1}{N^2} \sum_{a} \sum_{b} \lvert \vec e_a - \vec e_b \rvert^2 = \frac{1}{N^2} \sum_a \sum_b \big( \lvert \vec e_a \rvert^2 + \lvert \vec e_b \rvert^2 - 2\, \vec e_a \cdot \vec e_b \big) = 2\, \mathrm{MSE}(Q) - 2\, \Big\lvert \frac{1}{N} \sum_a \vec e_a \Big\rvert^2 .$$

The last term is the squared length of the mean error vector, which is never negative, so the average is at most $2\,\mathrm{MSE}(Q)$. That proves the theorem. Under the second Lloyd condition the bound on the pairwise errors is exactly $2\,\mathrm{MSE}(Q)$: the errors add to zero within every cell, so they add to zero over the whole base, and the last term vanishes. For a product quantizer it is enough that each sub-quantizer meets the condition, since the $j$th block of the mean error vector is the mean error of $Q_j$.

Theorem 2 is about pairs of base vectors. A search uses the symmetric estimate between a query, which need not resemble the base, and the base vectors. The same argument covers that case.

Theorem 2, for a query. For any quantizer $Q$ and any query $\vec q$, with $\vec e_q = \vec q - Q(\vec q)$ and $\bar{\vec e}$ the mean error vector of the base,

$$\frac{1}{N} \sum_{n=1}^{N} \big( \lvert \vec q - \vec x_n \rvert - \hat d(\vec q, \vec x_n) \big)^2 \le \lvert \vec e_q \rvert^2 - 2\, \vec e_q \cdot \bar{\vec e} + \mathrm{MSE}(Q) \le \big( \lvert \vec e_q \rvert + \sqrt{\mathrm{MSE}(Q)} \big)^2 .$$

If every centroid (for a product quantizer, every sub-centroid) is the mean of the base vectors (sub-vectors) it encodes, the middle expression is $\lvert \vec q - Q(\vec q) \rvert^2 + \mathrm{MSE}(Q)$.

Proof. As before, $Q(\vec q) - Q(\vec x_n) = (\vec q - \vec x_n) - (\vec e_q - \vec e_n)$, so the triangle inequality gives $\big\lvert\, \lvert \vec q - \vec x_n \rvert - \hat d(\vec q, \vec x_n) \,\big\rvert \le \lvert \vec e_q - \vec e_n \rvert$. Square, expand $\lvert \vec e_q - \vec e_n \rvert^2 = \lvert \vec e_q \rvert^2 - 2\, \vec e_q \cdot \vec e_n + \lvert \vec e_n \rvert^2$, and average over $n$: the three terms become $\lvert \vec e_q \rvert^2$, $-2\, \vec e_q \cdot \bar{\vec e}$ and $\mathrm{MSE}(Q)$. That is the first inequality. For the second, $\lvert \bar{\vec e} \rvert^2 \le \frac{1}{N}\sum_n \lvert \vec e_n \rvert^2 = \mathrm{MSE}(Q)$, because the squared length of a mean is at most the mean of the squared lengths, so by the Cauchy-Schwarz inequality $-2\, \vec e_q \cdot \bar{\vec e} \le 2 \lvert \vec e_q \rvert \sqrt{\mathrm{MSE}(Q)}$, and the three terms are at most a perfect square. Under the second Lloyd condition $\bar{\vec e} = \vec 0$ and the middle term vanishes.

The asymmetric bound of Theorem 1 is $\mathrm{MSE}(Q)$ for every query. The symmetric bound adds the query's own quantization error, $\lvert \vec q - Q(\vec q) \rvert^2$. For a query drawn like the base vectors that error is $\mathrm{MSE}(Q)$ on average, which gives the paper's $2\,\mathrm{MSE}(Q)$. These are two upper bounds, and comparing them proves nothing about which estimate has the smaller error. The measurements do that, on the eight vectors below and on real vectors in the next section.

Theorem 3 (the squared estimate is too small on average, by exactly the quantization error). Let $Q$ be a product quantizer whose sub-codebooks satisfy the second Lloyd condition on the base vectors. Then for every query $\vec q$,

$$\frac{1}{N} \sum_{n=1}^{N} \lvert \vec q - \vec x_n \rvert^2 = \frac{1}{N} \sum_{n=1}^{N} \tilde d(\vec q, \vec x_n)^2 + \mathrm{MSE}(Q).$$

Proof. Fix a position $j$ and a centroid number $i$, and let $S$ be the set of base vectors whose $j$th code number is $i$. For $\vec x \in S$, write $\vec q^{(j)} - \vec x^{(j)} = (\vec q^{(j)} - \vec c_{j,i}) + (\vec c_{j,i} - \vec x^{(j)})$ and expand the square:

$$\lvert \vec q^{(j)} - \vec x^{(j)} \rvert^2 = \lvert \vec q^{(j)} - \vec c_{j,i} \rvert^2 + 2\, (\vec q^{(j)} - \vec c_{j,i}) \cdot (\vec c_{j,i} - \vec x^{(j)}) + \lvert \vec c_{j,i} - \vec x^{(j)} \rvert^2 .$$

Sum over $\vec x \in S$. The first factor of the middle term is the same for all of them, and $\sum_{\vec x \in S} (\vec c_{j,i} - \vec x^{(j)}) = \vec 0$ because $\vec c_{j,i}$ is the mean of the $j$th sub-vectors of $S$. So the middle term vanishes, and

$$\sum_{\vec x \in S} \lvert \vec q^{(j)} - \vec x^{(j)} \rvert^2 = \sum_{\vec x \in S} T_j[i] + \sum_{\vec x \in S} \lvert \vec x^{(j)} - \vec c_{j,i} \rvert^2 .$$

Now add these equations over the $k^*$ values of $i$, which covers every base vector once, and then over $j$. By (1) the left sides add up to $\sum_n \lvert \vec q - \vec x_n \rvert^2$. By (2) the first terms on the right add up to $\sum_n \tilde d(\vec q, \vec x_n)^2$. The last terms add up to $N \sum_j \mathrm{MSE}(Q_j) = N\, \mathrm{MSE}(Q)$ by Property 2. Dividing by $N$ gives the claim.

This is the source of a remark in the paper, that the estimates "underestimate, on average, the distance" (section III.C). The paper proposes a corrected estimate of the squared distance, its equation 25: add to $\tilde d^2$ the mean squared error of the cells the code names, $\sum_j \xi_j$, where $\xi_j$ is the mean of $\lvert \vec x^{(j)} - \vec c_{j,i_j} \rvert^2$ over the vectors whose $j$th code number is $i_j$. The proof above shows exactly what that correction is an average over. For each position $j$ separately, among the vectors that share the $j$th code number, the mean of $\lvert \vec q^{(j)} - \vec x^{(j)} \rvert^2$ is $T_j[i] + \xi_j$. It does not follow that the vectors sharing a whole code have mean squared distance $\tilde d^2 + \sum_j \xi_j$, because a centroid of the product codebook need not be the mean of the vectors that share its code. The eight vectors show the difference below. The paper reports that on its data the correction removes the bias (from $-0.044$ to $0.002$ in the measurement of its Figure 4) but raises the variance of the error, that search results with it were worse on average, and it recommends the uncorrected estimate for nearest neighbor search.

The three results on the eight vectors. For the query $\vec q = (2, 2, 4, 4)$:

  • Theorem 1. The distances and their estimates, unsquared, are $\sqrt{21} = 4.583$ against $\sqrt{10} = 3.162$ for $\vec x_1$, and so on down the table. The eight squared differences have mean 1.294, which is below $\mathrm{MSE}(Q) = 4.5$. Vector by vector, $\vec x_1$ has a difference of 1.420 (from the unrounded values), which is below its own error $\sqrt{3} = 1.732$.
  • Theorem 2. Over the 64 ordered pairs of the eight vectors, the mean squared error of the symmetric estimate is 2.746, below $2 \times 4.5 = 9$. The error vectors of the eight do add to zero, and the mean of $\lvert \vec e_a - \vec e_b \rvert^2$ over the pairs is exactly 9. For the query itself, $Q(\vec q) = (1, 1, 2, 6)$ and $\lvert \vec q - Q(\vec q) \rvert^2 = 1 + 1 + 4 + 4 = 10$, so the query form of the theorem bounds the mean squared error of its eight symmetric estimates by $10 + 4.5 = 14.5$. The mean is 9.58, against 1.294 for the asymmetric estimates of the same query.
  • Theorem 3. The true squared distances add to $21 + 11 + 22 + 10 + 27 + 72 + 55 + 46 = 264$, a mean of 33. The squared estimates add to $2 \times (10 + 15 + 42 + 47) = 228$, a mean of 28.5. The difference is $4.5 = \mathrm{MSE}(Q)$.

Example (a correction that is right on average and wrong for one code). The vectors $\vec x_1$ and $\vec x_3$ share the code (1, 1) and the estimate 10. The first sub-centroid of that code has $\xi_1 = (2 + 1 + 4 + 1)/4 = 2$, the mean squared error of the four first halves it encodes, and the second has $\xi_2 = (1 + 4 + 2 + 1)/4 = 2$. The corrected estimate is $10 + 2 + 2 = 14$. The mean squared distance of $\vec x_1$ and $\vec x_3$ from the query is $(21 + 22)/2 = 21.5$. The correction is exact where the proof says it is: the four vectors whose first code number is 1 have first halves at mean squared distance $(8 + 1 + 2 + 5)/4 = 4$ from $(2, 2)$, and $T_1[1] + \xi_1 = 2 + 2 = 4$.

Product quantization on GloVe

The eight vectors show the mechanism. What it is worth on real vectors has to be measured. The experiment uses the unit's dataset: 399,000 GloVe word vectors of 100 dimensions, scaled to unit length, 1,000 queries, and the exact ten nearest neighbors of each as the truth (nearest neighbor search in high dimensions describes it). The quantizer has $M = 10$ sub-vectors of ten coordinates and $k^* = 256$ centroids each, so a code is 10 bytes. Each sub-codebook is learned by 20 iterations of k-means on a sample of 50,000 base vectors, and all 399,000 are then encoded. The sample and the k-means seeds change with the random seed. There are 30 seeds, and each figure is the median over them, with the first and third quartiles in parentheses.

The error. The quantization error on the base vectors is $\mathrm{MSE}(Q) = 0.3310$ (0.3309 to 0.3310). These are unit vectors, so the squared length of every vector is 1, and the mean squared error is a third of that: the typical distance between a vector and its reconstruction is $\sqrt{0.331} = 0.575$. The ten sub-quantizers share the error almost equally, between 0.032 and 0.035 each at the median. By comparison the nearest neighbor of a typical query is at distance 0.737 and its tenth at about 0.85. The code moves a vector by nearly as much as the distance that separates a query from its neighbors. Eighty bits are few for a hundred coordinates that have no structure to exploit, and the search results show it.

The search. A query is compared with all 399,000 codes by the asymmetric estimate, and the base vectors are ranked by it. The counts below were not produced by reading tables. They use the fact shown on the eight vectors, that the estimate is the distance to the reconstruction, and compute all estimates of a batch of queries with one matrix product. For the first 100 queries the script also runs the table lookups: the two routes differ by less than $10^{-6}$ in any squared estimate and put the same 429 true neighbors in the ten best.

Short-list size $R$ Share of the ten true neighbors among the $R$ best by estimate
10 0.277 (0.275 to 0.280)
20 0.392 (0.389 to 0.394)
50 0.553 (0.552 to 0.558)
100 0.675 (0.673 to 0.677)
200 0.782 (0.780 to 0.784)
500 0.890 (0.887 to 0.891)
1,000 0.942 (0.941 to 0.944)

The first row is the recall@10 of the codes used alone: 0.277. The ten best by estimate hold fewer than three of the ten true neighbors on average. The other rows are what re-ranking buys. If the $R$ best by estimate are compared exactly with the query, every true neighbor among them is returned, by the argument that a true neighbor cannot be pushed out of the best ten by exact distances (Proposition 1 of the previous article gives it for the candidates of an inverted file, and it holds for any set of candidates). So the share in the table is the recall@10 after re-ranking $R$ candidates. Re-ranking 100 candidates gives 0.675, and 1,000 candidates, a quarter of a percent of the base, gives 0.942. The true nearest neighbor alone is ranked first by the estimate for 23.4 percent of the queries (22.4 to 23.9), and is among the best 100 for 84.5 percent.

The codes, then, do not replace the vectors on this data. They are a cheap first pass that reduces 399,000 candidates to a few hundred, and the vectors are still needed for the second pass. Where the vectors cannot be kept, the recall of the first row is what remains. On the paper's image descriptors the first pass alone did much better: with 64-bit codes ($M = 8$, $k^* = 256$) on one million vectors of 128 dimensions, its Table IV gives the nearest neighbor ranked among the first 100 for 92.1 percent of the queries, where the corresponding figure here is 84.5 percent with 80-bit codes. Those descriptors are histograms whose neighboring coordinates are correlated, which is the structure a sub-codebook can exploit.

Back to neighborhood. With the quantizer of seed 0, the ten best by estimate are suburban, neighbourhood, suburb, campus, neighborhoods, mall, upscale, suburbs, residential and adjacent. Five of them are true neighbors. The other five true neighbors are ranked 12th (apartment), 16th (downtown), 18th (city), 28th (town) and 30th (area) by the estimate, so re-ranking 30 candidates recovers all ten for this query. The estimates are not close to the distances one by one. The true nearest neighbor, neighborhoods, is at distance 0.582, and its estimate is 0.823. The estimate of suburban is 0.760 against a true 0.773. What the ranking needs is only that the errors be smaller than the gap between neighbors and the rest, and here they are comparable to it.

Nine of the ten true neighbors have an estimate larger than their distance, although Theorem 3 says that squared estimates are too small on average. Both are true, and one identity shows why. With $\vec e = \vec x - Q(\vec x)$, the estimate is $\lvert \vec q - Q(\vec x) \rvert = \lvert (\vec q - \vec x) + \vec e \rvert$, so

$$\tilde d(\vec q, \vec x)^2 = \lvert \vec q - \vec x \rvert^2 + 2\, (\vec q - \vec x) \cdot \vec e + \lvert \vec e \rvert^2 .$$

The middle term is $2\, \vec q \cdot \vec e - 2\, \vec x \cdot \vec e$. Over the base the first part averages $2\, \vec q \cdot \bar{\vec e}$, which is 0 under the condition of Theorem 3, since then the errors add to zero. The second part averages $-2\,\mathrm{MSE}(Q)$ under the same condition: $\vec x \cdot \vec e = \lvert \vec e \rvert^2 + Q(\vec x) \cdot \vec e$, and the last term adds to zero over the vectors of each cell, block by block, because the centroid is fixed there and the errors of the cell add to zero. So each error has, on average, a component of length $\lvert \vec e \rvert^2$ along its own vector, and the middle term averages $-2\,\mathrm{MSE}(Q)$, which turns the surplus of $\mathrm{MSE}(Q)$ into the deficit the theorem states. For a vector far from the query, $\vec q \cdot \vec e$ has no reason to be large, and the middle term is about $-2\lvert \vec e \rvert^2$ whatever the distance. For a vector close to the query the two parts nearly cancel, since $\vec q \cdot \vec e$ is then close to $\vec x \cdot \vec e$, and the squared estimate exceeds the squared distance by about $\lvert \vec e \rvert^2$. What matters is not that $\vec q - \vec x$ is short beside the error (for neighborhoods it has length 0.582, the same size as the typical error of 0.575) but that $\vec q$ points nearly the way $\vec x$ does, and so shares the component of the error along $\vec x$. For neighborhoods, $0.582^2 + 0.331 = 0.670$, whose square root is 0.818, close to the 0.823 observed (0.331 is the average error, not this word's own). For this query 98.9 percent of the base vectors have an estimate below their distance. The estimate pulls far vectors in and pushes the nearest ones out, both of which make neighbors harder to tell from the rest.

Asymmetric estimate against true distance for the query word "neighborhood" and the quantizer of seed 0: 4,000 base vectors drawn at random (dots), the ten true neighbors (circles) and the ten best by estimate (crosses). On the solid diagonal the estimate would equal the distance. The dotted lines are the diagonal plus and minus 0.575, the typical length of a quantization error, which is the size of error Theorem 1 allows. Notice that the cloud of far vectors lies just below the diagonal, as Theorem 3 predicts, that nine of the ten true neighbors lie above it, and that the whole cloud stays far inside the dotted lines. Every sampled point is drawn; the farthest is at a true distance of 1.72.
Asymmetric estimate against true distance for the query word "neighborhood" and the quantizer of seed 0: 4,000 base vectors drawn at random (dots), the ten true neighbors (circles) and the ten best by estimate (crosses). On the solid diagonal the estimate would equal the distance. The dotted lines are the diagonal plus and minus 0.575, the typical length of a quantization error, which is the size of error Theorem 1 allows. Notice that the cloud of far vectors lies just below the diagonal, as Theorem 3 predicts, that nine of the ten true neighbors lie above it, and that the whole cloud stays far inside the dotted lines. Every sampled point is drawn; the farthest is at a true distance of 1.72.

The theorems, measured. For the quantizer of seed 0 and the first 100 queries, the script computes the true distance and the estimate for every base vector. The queries keep the order of the GloVe file, which lists words by frequency, so these 100 are the most frequent of the query words: all of them are among the 46,000 most frequent words of the file. That matters for one of the measurements below, which is therefore also given over all 1,000 queries.

  • Theorem 1. The pointwise bound $\lvert d - \tilde d \rvert \le \lvert \vec x - Q(\vec x) \rvert$ holds for all 39.9 million pairs, as it must. The mean squared error of the estimated distance is 0.016 per query on average and at most 0.017, against the bound $\mathrm{MSE}(Q) = 0.331$. The bound is true and loose by a factor of twenty. It is attained only when the quantization error of a vector points straight at the query or straight away from it, and the errors do not point that way. Over these queries the squared cosine of the angle between a vector's error and the direction from its reconstruction to the query has a mean of 0.0075, weighted by the squared length of the error, below even the $1/100$ that two independent random directions in 100 dimensions give on average (cosine similarity proves it). The error of the estimate splits into two parts of different order. Write $\vec u$ for the unit vector from $Q(\vec x)$ to $\vec q$. Since $\lvert \vec q - \vec x \rvert^2 = \tilde d^2 - 2 \tilde d\, (\vec u \cdot \vec e) + \lvert \vec e \rvert^2$, expanding the square root in powers of $\vec e$ gives $\lvert \vec q - \vec x \rvert - \tilde d \approx -\,\vec u \cdot \vec e + \lvert \vec e_\perp \rvert^2 / (2 \tilde d)$, where $\vec e_\perp$ is the part of the error at right angles to $\vec u$. The first part is the component of the error along the direction to the query; the second is the lengthening that an error at right angles produces, which is second order in $\lvert \vec e \rvert$ (here $\lvert \vec e_\perp \rvert^2$ is nearly all of $\lvert \vec e \rvert^2$, by the small cosine just measured). The script computes both over every base vector and these queries. The mean of $(\vec u \cdot \vec e)^2$ is 0.0025, and the mean of $(\lvert \vec e \rvert^2 / (2 \tilde d))^2$ is 0.017. The measured 0.016 is their sum plus $-0.0035$, the cross term between the two parts together with the terms of higher order. So the error of the estimate is mostly the second-order lengthening, not the first-order component along the direction to the query, and that is why it is so far below $\lvert \vec e \rvert^2$.
  • Theorem 3. The mean over the base of the true squared distance exceeds the mean squared estimate by 0.317 per query (between 0.316 and 0.318 over the 100 queries), where the quantization error is 0.331. The theorem's condition is not met exactly here. The centroids are the means of the 50,000 training sub-vectors assigned to them, not of all the base sub-vectors they encode. When a centroid $\vec c_{j,i}$ differs from the mean $\vec m_{j,i}$ of the $n_{j,i}$ base sub-vectors it encodes, the middle term in the proof no longer vanishes, and the identity gains the term $\frac{2}{N} \sum_{j,i} n_{j,i}\, (\vec q^{(j)} - \vec c_{j,i}) \cdot (\vec c_{j,i} - \vec m_{j,i})$. The script computes it: it averages $-0.014$ over the 100 queries, and for each query the surplus equals the quantization error plus this term to nine decimal places. On the eight vectors, where the condition holds, the identity was exact.
  • Ties. The 399,000 base vectors have 397,505 distinct codes, only 1,495 fewer than there are vectors, so ties between estimates are rare at 80 bits. They were the rule at two bits.
  • Theorem 2, for a query. With the same quantizer and the first 100 queries, the mean squared error of the symmetric estimate is 0.102 per query on average (at most 0.149 for any of the 1,000 queries), 6.3 times the error of the asymmetric estimate for these queries. The bound proved above, $\lvert \vec e_q \rvert^2 - 2\, \vec e_q \cdot \bar{\vec e} + \mathrm{MSE}(Q)$, averages 0.744 for them. The centroids are not exactly the means of the base sub-vectors they encode (the item on Theorem 3 above says why), so this is not exactly the Lloyd form $\lvert \vec q - Q(\vec q) \rvert^2 + \mathrm{MSE}(Q)$; but the mean error vector of the base has length only 0.0023, and the two differ by less than 0.001 for every one of the 1,000 queries. The bound is large for these 100 queries because they are quantized worse than the base as a whole: $\lvert \vec q - Q(\vec q) \rvert^2$ averages 0.414 for them, against $\mathrm{MSE}(Q) = 0.331$. That is a property of frequent words, not of queries. Frequent words are quantized worse whether they are queries or base vectors: the squared error of the 10,000 most frequent base vectors averages 0.407, that of the next 90,000 0.405, and that of the remaining 299,000 0.306. Over all 1,000 queries $\lvert \vec q - Q(\vec q) \rvert^2$ averages 0.332, about the base's 0.331 (0.323 for the 900 queries after the first 100). Over all 1,000 queries the symmetric estimate's mean squared error averages 0.078, 4.0 times the asymmetric estimate's 0.019, and the bound averages 0.663. Over the first 100 and over all 1,000 alike, the symmetric estimate reaches at most 21 percent of its bound. So on these vectors the measured errors differ by far more than the factor of two between the two bounds.

More or fewer sub-vectors, and symmetric against asymmetric. The remaining comparisons were run on a smaller base, the 50,000 most frequent words, with each quantizer trained on 20,000 of them, again with 30 seeds. The neighbors are those among the 50,000, so these figures are comparable with each other and not with the table above.

$M$ $k^*$ Bits per vector $\mathrm{MSE}(Q)$ Recall@10 from the codes After re-ranking 100
5 256 40 0.519 0.166 (0.156 to 0.174) 0.508 (0.499 to 0.513)
10 256 80 0.352 0.339 (0.333 to 0.344) 0.759 (0.755 to 0.763)
20 256 160 0.143 0.551 (0.548 to 0.555) 0.955 (0.953 to 0.956)
20 16 80 0.401 0.315 (0.312 to 0.319) 0.724 (0.719 to 0.728)
10, symmetric 256 80 0.352 0.165 (0.159 to 0.170) 0.454 (0.444 to 0.459)
  • More sub-vectors, less error. Doubling $M$ at a fixed $k^*$ doubles the code and gives each sub-quantizer half as many coordinates to describe. The error falls from 0.519 to 0.352 to 0.143, and the recall of the codes alone rises from 0.166 to 0.339 to 0.551. At 160 bits, 5 percent of the size of the vector, re-ranking 100 candidates recovers 0.955 of the neighbors.
  • At equal size, fewer and larger codebooks did better. Eighty bits can be spent as ten sub-vectors with 256 centroids or as twenty with 16. The first has the lower error, 0.352 against 0.401, and the higher recall, 0.339 against 0.315. This agrees with what Jégou, Douze and Schmid (2011, sections II.B and V.B) observed on their descriptors: for a fixed number of bits, a small number of sub-quantizers with many centroids beats many sub-quantizers with few. The price is in the tables. Ten tables of 256 entries take 2,560 distance computations in ten dimensions to fill, and twenty tables of 16 take 320 in five.
  • Quantizing the query costs half the recall. The symmetric estimate, with the same codes and the query encoded as well, has a recall of 0.165 where the asymmetric one has 0.339. That is the recall of the asymmetric estimate with codes half as long, the first row of the table. The measurement on the full set found its mean squared error to be 4.0 times that of the asymmetric estimate over all 1,000 queries, and here the price of using it is about the same as halving the code. The paper found the same relation on its own data in a milder form: its symmetric estimate with 256 centroids per sub-vector matched its asymmetric estimate with 64.

Rotating the space first: optimized product quantization

A product quantizer treats the $M$ blocks of coordinates separately. It therefore wastes nothing only if the blocks are independent of each other, and it spends its bits evenly only if the blocks carry similar shares of the variance. Nothing makes a set of vectors arrive that way. Jégou, Douze and Schmid (2011, Table IV) found the grouping of coordinates to matter a great deal on their image descriptors: at eight sub-vectors, their recall@100 on one set was 0.921 with the descriptor's natural order of coordinates and 0.859 with a random order, and on the other set a grouping designed from the descriptor's structure nearly doubled the recall of the natural order, from 0.338 to 0.652.

Ge, He, Ke and Sun (2013) turned the grouping into part of the optimization. Their optimized product quantization (OPQ) applies an orthogonal matrix $R$ to every vector before the product quantizer and chooses $R$ together with the sub-codebooks to minimize the quantization error. An orthogonal matrix is a rotation, possibly combined with a reflection. It changes no distance, so nearest neighbors are the same before and after, and a query is simply rotated by the same $R$ before its tables are built. Any reordering of the coordinates is an orthogonal matrix, so the search includes every grouping, and much more.

The paper gives two ways to find $R$.

The non-parametric method

The first alternates between two steps, each of which solves half of the problem exactly, in the manner of k-means itself (Ge et al., 2013, section 3.1 and Algorithm 1).

  1. With $R$ fixed, rotate the training vectors and improve the sub-codebooks by k-means in each block. The paper runs a single k-means iteration here: move each centroid to the mean of its sub-vectors, then reassign.
  2. With the codes fixed, choose the orthogonal $R$ that brings the rotated vectors closest to their current reconstructions. If $\vec y_n$ is the reconstruction of $R\vec x_n$, this asks for the orthogonal $R$ minimizing $\sum_n \lvert R \vec x_n - \vec y_n \rvert^2$.

Step 2 is a classical problem with a closed solution, the orthogonal Procrustes problem (Schönemann, 1966, whom Ge et al. cite for it). The paper states the solution; here is the proof.

Proposition (orthogonal Procrustes). Let $S = \sum_n \vec x_n \vec y_n^{\mathsf T}$, an $m \times m$ matrix, with singular value decomposition $S = U \Sigma V^{\mathsf T}$. Then $R = V U^{\mathsf T}$ minimizes $\sum_n \lvert R \vec x_n - \vec y_n \rvert^2$ over all orthogonal matrices $R$.

Proof. An orthogonal matrix preserves lengths, so $\lvert R\vec x_n \rvert = \lvert \vec x_n \rvert$ and

$$\sum_n \lvert R \vec x_n - \vec y_n \rvert^2 = \sum_n \lvert \vec x_n \rvert^2 + \sum_n \lvert \vec y_n \rvert^2 - 2 \sum_n \vec y_n \cdot R \vec x_n .$$

Only the last sum depends on $R$, and minimizing the whole is maximizing it. Writing the dot product as a trace, $\vec y_n \cdot R\vec x_n = \operatorname{tr}(R\, \vec x_n \vec y_n^{\mathsf T})$, the sum is $\operatorname{tr}(R S) = \operatorname{tr}(R\, U \Sigma V^{\mathsf T}) = \operatorname{tr}(V^{\mathsf T} R\, U\, \Sigma)$, since a trace is unchanged when a factor is moved from the back to the front. The matrix $Z = V^{\mathsf T} R\, U$ is a product of orthogonal matrices and so is orthogonal, and $\Sigma$ is diagonal with the singular values $\sigma_1, \dots, \sigma_m \ge 0$. Hence $\operatorname{tr}(Z\Sigma) = \sum_i z_{ii} \sigma_i$. Every entry of an orthogonal matrix lies between $-1$ and 1, because each of its rows has length 1. So $\sum_i z_{ii}\sigma_i \le \sum_i \sigma_i$, with equality when $Z$ is the identity, that is, when $R = V U^{\mathsf T}$.

Neither step can raise the quantization error, so the error falls or stays at every round. Like k-means, the method stops at a local optimum that depends on where it starts, as the authors say. The script checks the proposition numerically: on random data, $V U^{\mathsf T}$ gives a smaller sum than each of 2,000 random orthogonal matrices, and it recovers a rotation exactly when the $\vec y_n$ are an exact rotation of the $\vec x_n$.

The parametric method

The second method needs no iteration, and it explains what a good rotation does (Ge et al., 2013, section 3.2). Suppose the vectors follow a Gaussian distribution with covariance matrix $\Sigma$. Rate-distortion theory gives a lower bound on the error of any quantizer with $k$ centroids, which the authors take as an approximation of what k-means achieves. Applied to each block of a product quantizer, it bounds the total error from below by a constant times

$$\sum_{j=1}^{M} \big\lvert \hat\Sigma_{jj} \big\rvert^{M/m},$$

where $\hat\Sigma = R\, \Sigma\, R^{\mathsf T}$ is the covariance after rotation, $\hat\Sigma_{jj}$ its diagonal block for the $j$th sub-vector, and $\lvert \cdot \rvert$ of a matrix is its determinant (their equations 11 and 12). The bound itself is cited here, not proved. Minimizing a lower bound is a heuristic: it rests on the authors' observation that k-means comes within about 5 percent of the bound on Gaussian data (the table in their section 3.2.1). What the authors do with the expression is elementary. By the inequality between the arithmetic and geometric means, a sum of $M$ positive numbers is at least $M$ times the $M$th root of their product:

$$\sum_{j=1}^{M} \big\lvert \hat\Sigma_{jj} \big\rvert^{M/m} \ge M \prod_{j=1}^{M} \big\lvert \hat\Sigma_{jj} \big\rvert^{1/m},$$

with equality when all the determinants are equal. And by Fischer's inequality, which they cite, the product of the determinants of the diagonal blocks is at least the determinant of the whole matrix, $\prod_j \lvert \hat\Sigma_{jj} \rvert \ge \lvert \hat\Sigma \rvert = \lvert \Sigma \rvert$, with equality when the blocks are uncorrelated with one another. Together (their equation 15):

$$\sum_{j=1}^{M} \big\lvert \hat\Sigma_{jj} \big\rvert^{M/m} \ge M\, \lvert \Sigma \rvert^{1/m} .$$

The right side does not depend on $R$. A rotation reaches it when it makes the blocks uncorrelated and gives them equal determinants. The first is achieved by rotating to the principal axes of the data, where the covariance is diagonal and each block's determinant is the product of the eigenvalues assigned to it. The second is then a matter of dealing the eigenvalues into $M$ groups of $m/M$ with equal products. The authors do this greedily and call it eigenvalue allocation: take the eigenvalues from largest to smallest, and give each to the group whose product so far is smallest, among the groups that are not yet full. Worked problem 4 does it by hand. One detail is our reading and not the paper's. The paper says to give each eigenvalue to "the bucket having the minimum product of the eigenvalues in it (unless the bucket is full)", and it does not say what the product of an empty bucket is or how eigenvalues below 1 are to be treated. They are below 1 for unit vectors, and a product of such numbers shrinks as a group fills, so the rule read literally would keep adding to the fullest group. The script divides all eigenvalues by the smallest before forming the products, so that every factor is at least 1 and an empty group has the smallest product. This choice has one property worth having: the allocation it produces does not change when all the vectors are multiplied by a constant, just as the objective and its lower bound change only by a constant factor. Another normalization would give another greedy path. On the data below the reading does its job, and the allocation reaches the lower bound.

Measured on GloVe

Both methods were run on the 50,000-vector base of the previous section, with $M = 10$ and $k^* = 256$, the rotation and the codebooks learned on the same 20,000 training vectors, and 30 seeds. A random rotation is included for comparison. The non-parametric method starts from the parametric rotation, as the authors recommend, and runs 20 rounds. The authors report that about 100 rounds are enough in practice. With 20 the error was still falling, so the figures for this method are, if anything, an underestimate of it.

Rotation $\mathrm{MSE}(Q)$ Recall@10 from the codes After re-ranking 100
None (the coordinates as given) 0.3516 (0.3515 to 0.3517) 0.339 0.759
Random 0.3535 (0.3533 to 0.3538) 0.341 0.762
Parametric (eigenvalue allocation) 0.3141 (0.3140 to 0.3142) 0.345 0.771
Non-parametric, 20 rounds 0.3102 (0.3101 to 0.3105) 0.349 0.778
  • The rotations do what they are built to do. The parametric rotation lowers the quantization error by 11 percent and the non-parametric rounds lower it a little further, 12 percent below the unrotated quantizer. For the seed-0 training sample, the objective of the parametric method is 0.0946 with the coordinates as given and 0.0816 after the allocation, which equals the lower bound $M \lvert \Sigma \rvert^{1/m}$ to three significant figures. The eigenvalues of that sample range from 0.048 down to 0.0009, a factor of 50, so there was something to balance. During the 20 non-parametric rounds the error on the training vectors fell at every round, from 0.2971 to 0.2920, as the argument above requires.
  • A random rotation does nothing here. Its error is slightly higher than that of the unrotated coordinates. A GloVe vector's coordinates have no order that means anything, so the coordinates as given are already an arbitrary grouping, and a second arbitrary grouping is no better. On the image descriptors of Jégou, Douze and Schmid, where the given order follows the layout of the descriptor, a random order made matters clearly worse, and in the experiments of Ge, He, Ke and Sun a random rotation fell well short of the optimized one.
  • The gain in recall is small. The error falls by an eighth, and the recall of the codes alone rises from 0.339 to 0.349. After re-ranking 100 candidates it rises from 0.759 to 0.778. The gain is consistent: the non-parametric quantizer has the higher recall@10 in 26 of the 30 seeds, compared seed by seed with the unrotated one, and in 28 of the 30 after re-ranking. But it is modest beside what one more byte per vector would buy. Ge, He, Ke and Sun report that both methods substantially outperform product quantization with a random order or a random rotation on their two sets of image descriptors and on a set of digit images. On these word vectors the effect is smaller, and the experiment does not isolate why.

With an inverted file: IVFADC

Scanning every code is still a scan. Jégou, Douze and Schmid (2011, section IV) combine the product quantizer with the inverted file of the previous article, and call the result IVFADC. Three things change.

  • The lists hold codes. Each inverted list stores, for every vector assigned to it, an identifier and a product-quantizer code.
  • The code is of the residual. What is encoded is not the vector but its offset from the centroid of its cell, the residual $\vec r(\vec x) = \vec x - \vec c_{i(\vec x)}$, where $\vec c_{i(\vec x)}$ is the centroid of the cell of $\vec x$ (their equation 28). The vector is approximated by $\vec c_{i(\vec x)} + Q_p(\vec r(\vec x))$, with $Q_p$ a product quantizer learned on the residuals of a training set. One product quantizer serves all cells. The residuals are shorter than the vectors, so the same number of bits describes them more finely. The authors put it as an analogy with the digits of a number: the cell gives the most significant bits and the code the least significant.
  • The tables are built per probed cell. For a query $\vec q$ and a probed cell with centroid $\vec c$, the estimate is $\lvert (\vec q - \vec c) - Q_p(\vec r(\vec x)) \rvert$, the asymmetric estimate (2) applied to the query's own residual $\vec q - \vec c$ (their equation 31). So the $M$ tables are computed once for each of the $w$ probed cells, and each list is scanned with its own tables.

The cost of a search is then $K$ distances to the centroids, $w k^*$ distance computations' worth of table building, and $M$ table reads for each code on the probed lists, with re-ranking of a short-list on top if the vectors are kept. Johnson, Douze and Jégou (2021, section 5.2 of the arXiv version, 1702.08734) show how to avoid most of the table building. They expand the squared estimate into three terms, of which one does not depend on the query and can be stored, one is the distance to the centroid that the first step has already computed, and one does not depend on the cell and is computed once per query.

The memory is the sum of the parts: the centroids, an identifier and $M \log_2 k^*$ bits per vector, and the sub-codebooks. The paper reports the scale this reaches: its largest experiment indexes two billion image descriptors. Benchmarking vector indexes measures IVFADC beside the other indexes of the unit, and finds on this unit's data that the table building makes it expensive when the lists are short.

What is proved here, what is cited, what the experiment shows

Proved on this page. Properties 1 and 2: the nearest product centroid is found block by block, and the error is the sum of the blocks' errors. Identity (2) for the asymmetric estimate, and the operation counts of both estimates. Theorem 1, the bound on the error of the asymmetric estimate, for any quantizer and every query. The identity that explains why the nearest vectors are overestimated while the average is underestimated. Theorem 2, the bound for the symmetric estimate, for pairs of base vectors and for a query. Theorem 3, that the mean squared estimate falls short of the mean squared distance by exactly the quantization error when the centroids are means. The orthogonal Procrustes solution. The step from the cited Gaussian bound to the two criteria of the parametric method, given Fischer's inequality.

Cited. That Lloyd's algorithm never increases the error and stops after finitely many steps at a clustering that neither of its steps changes, from the k-means article. The rate-distortion bound for Gaussian data and Fischer's inequality, from Ge, He, Ke and Sun (2013), who cite them in turn. Every measurement on image descriptors, from the two papers.

Measured. The error and recall of product quantizers on the GloVe vectors, over 30 seeds, and the effect of the two rotations. These describe one set of word vectors whose coordinates have no particular order. The papers' image descriptors, built from histograms laid side by side, behaved differently in the ways noted above.

Worked problems

These problems are posed on the eight vectors of the worked example and on the sizes of this unit's datasets. The script recomputes every number.

Problem 1 (encoding a new vector). With the sub-codebooks of the worked example, encode $\vec z = (5, 3, 4, 2)$, reconstruct it, and find the squared error.

By Property 1 each half is encoded separately. The first half $(5, 3)$ is at squared distance $16 + 4 = 20$ from $\vec c_{1,1} = (1, 1)$ and $4 + 4 = 8$ from $\vec c_{1,2} = (7, 5)$, so its code number is 2. The second half $(4, 2)$ is at squared distance $4 + 16 = 20$ from $\vec c_{2,1} = (2, 6)$ and $4 + 1 = 5$ from $\vec c_{2,2} = (6, 1)$, so its code number is 2. The code is (2, 2), the reconstruction is $(7, 5, 6, 1)$, and the squared error is $8 + 5 = 13$. The two bits of the code replace 128 bits. The error is larger than that of any of the eight vectors the codebooks were learned on, whose largest is 8, which is the ordinary situation for a vector outside the training set.

Problem 2 (a second query). For the query $\vec q\,' = (6, 6, 3, 6)$, build the tables, estimate the eight distances, and compare the two nearest by estimate with the two true nearest.

The halves are $(6, 6)$ and $(3, 6)$. The tables are $T_1 = [\,25 + 25,\ 1 + 1\,] = [50, 2]$ and $T_2 = [\,1 + 0,\ 9 + 25\,] = [1, 34]$. The four possible estimates are $50 + 1 = 51$ for the code (1, 1), $50 + 34 = 84$ for (1, 2), $2 + 1 = 3$ for (2, 1) and $2 + 34 = 36$ for (2, 2).

Vector Code $\tilde d^2$ True squared distance
$\vec x_1$ (1, 1) 51 76
$\vec x_2$ (1, 2) 84 70
$\vec x_3$ (1, 1) 51 39
$\vec x_4$ (1, 2) 84 79
$\vec x_5$ (2, 1) 3 2
$\vec x_6$ (2, 2) 36 69
$\vec x_7$ (2, 1) 3 4
$\vec x_8$ (2, 2) 36 45

The two nearest by estimate are $\vec x_5$ and $\vec x_7$, tied at 3, and they are the two true nearest, at squared distances 2 and 4. The recall@2 is 1, where for the query of the worked example it was 0. The difference is in where the queries lie. This query is close to the product centroid $(7, 5, 2, 6)$ and to both vectors that share it, so the quantization error of 3 and 5 on those vectors is small beside the distances that separate them from everything else. The earlier query sat between two product centroids, where the errors were as large as the differences being compared. Theorem 3 holds here as it must: the true squared distances have mean $384/8 = 48$, the estimates have mean $348/8 = 43.5$, and the difference is 4.5.

Problem 3 (memory for this site's passages). This site's own search is lexical and stores no vectors. In the dense-retrieval experiments of the previous unit, the site's passages at one commit were encoded as 11,264 vectors of 384 dimensions. How much memory do they take as 32-bit floating-point numbers, and as product-quantizer codes with $M = 48$ and $k^* = 256$? What does the same quantizer save on a million such vectors?

Uncompressed, a vector takes $384 \times 4 = 1{,}536$ bytes, and the collection $11{,}264 \times 1{,}536 = 17{,}301{,}504$ bytes, 17.3 megabytes. A code takes 48 bytes, so the codes take $11{,}264 \times 48 = 540{,}672$ bytes. The sub-codebooks hold $k^* m = 256 \times 384 = 98{,}304$ numbers, 393,216 bytes. The total is 933,888 bytes, a factor of 18.5 below the vectors, where the codes alone are 32 times smaller. At this size the codebooks are 42 percent of the compressed index.

For a million vectors the vectors take 1,536 megabytes and the codes 48 megabytes, and the same 393,216 bytes of codebooks no longer matter: the total is 48.4 megabytes, a factor of 31.7. The fixed cost of the codebooks is one reason product quantization is a tool for large collections. The other is that 17.3 megabytes needs no compressing in the first place.

Problem 4 (eigenvalue allocation by hand). A four-dimensional Gaussian has a covariance matrix with eigenvalues 8, 4, 2 and 1. Allocate them to $M = 2$ sub-vectors of two coordinates, and compare the objective of the parametric method with the one obtained by keeping the eigenvalues in order.

Take the eigenvalues from largest to smallest. Both groups start with product 1 (empty). The eigenvalue 8 goes to the first group, whose product becomes 8. The eigenvalue 4 goes to the group with the smaller product, the second, whose product becomes 4. The eigenvalue 2 again goes to the second group, now at product $4 \times 2 = 8$, which fills it. The eigenvalue 1 goes to the only group with room, the first, at product $8 \times 1 = 8$. The groups are $\{8, 1\}$ and $\{4, 2\}$, with equal products.

With $M/m = 2/4$, the objective is the sum of the square roots of the two products. Allocated, it is $\sqrt{8} + \sqrt{8} = 5.657$. In order, the groups $\{8, 4\}$ and $\{2, 1\}$ give $\sqrt{32} + \sqrt{2} = 7.071$. The lower bound $M \lvert \Sigma \rvert^{1/m} = 2 \times (8 \times 4 \times 2 \times 1)^{1/4} = 2 \times 64^{1/4} = 5.657$ is reached by the allocation, as it must be when the products are equal and the principal axes are uncorrelated. The in-order split has the same total variance in the same four directions. It is worse only because it gives one sub-quantizer all the large directions and the other all the small ones, and each has the same $k^*$ centroids to spend.

What we have learned

A product quantizer encodes a vector as $M$ small numbers, one per sub-vector, each naming a centroid of a k-means codebook learned for that position. Its $(k^*)^M$ centroids are never stored. Encoding is done block by block and the error is the sum of the blocks' errors. The distance from a query to a coded vector is estimated by adding $M$ entries of tables built once per query, and the estimate is the exact distance to the vector's reconstruction. For every query the mean squared error of the estimated distance is at most the quantization error, and the squared estimate is too small on average by exactly that error. On eight vectors with two-bit codes the estimates ranked the wrong pair first for one query and the right pair for another, and re-ranking four candidates repaired the first. On 399,000 GloVe vectors, 10-byte codes had a quantization error of 0.331 on vectors of length 1 and returned 0.277 of the true ten neighbors by themselves, 0.675 after re-ranking 100 candidates and 0.942 after re-ranking 1,000, so on this data the codes serve as a first pass and not as a replacement for the vectors. A rotation chosen to make the blocks uncorrelated and balanced lowers the error further, and an inverted file over residuals removes the need to scan every code.

Quantization shrinks the index and partitions prune the search. The next article takes a different road to pruning, with no partition at all: hierarchical navigable small world graphs link each vector to a few near ones and walk the links toward the query.

References

  • Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., and Jégou, H. (2026). The Faiss library. IEEE Transactions on Big Data, 12(2), 346–361. arXiv:2401.08281. record · 4 pages
  • Ge, T., He, K., Ke, Q., and Sun, J. (2013). Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2946–2953. record
  • Gray, R. M., and Neuhoff, D. L. (1998). Quantization. IEEE Transactions on Information Theory, 44(6), 2325–2383. record
  • Jégou, H., Douze, M., and Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117–128. record · 6 pages
  • Johnson, J., Douze, M., and Jégou, H. (2021). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547. record · 3 pages
  • Schönemann, P. H. (1966). A generalized solution of the orthogonal Procrustes problem. Psychometrika, 31(1), 1–10. record