1. Overview

Product Quantization (PQ) is a nearest neighbor search technique that splits a high-dimensional vector into several subvectors and quantizes each subspace with a small codebook, compressing a single vector into a short code. The key idea is to approximate distance computation directly on the compressed codes, reducing the memory bottleneck of large-scale search without loading all the original vectors into RAM.

Large-scale vector search is a recurring problem in recommendation systems, image retrieval, and semantic document search. Where NSW and HNSW approach the problem by making graph traversal fast, PQ approaches it by compressing the vectors themselves into short codes and approximating distance computation on those compressed codes. The Product Quantization for Nearest Neighbor Search paper (Jégou, Douze, Schmid, 2011) is the landmark paper that systematically applied this approach to ANN search.

The core questions are as follows.

• The basic principles of vector quantization and Product Quantization
• The strengths of Hamming embedding methods and their limitation of too few distinct distances
• How Product Quantization sidesteps the memory limits of a single quantizer
• How IVFADC, which combines an inverted file structure, implements non-exhaustive search

2. Essential Concepts

2.1. Quantization

Quantization is the process of mapping a continuous value to one of a predetermined, finite set of representative values. The most familiar example is a digital photo. A camera sensor receives the amount of light as a continuous real number, but stores it as an integer in 0–255. Mapping 16 million possible colors to the nearest color in GIF's 256-color palette is the same principle.

입력: 무한한 가능성 (연속적인 값)
       ↓ quantizer
출력: 유한한 k개 대표값 중 하나

Here, the function that performs quantization is called the quantizer, the set of representative values the codebook, and each element of the codebook a codeword. In the end, what a quantizer does splits into two steps.

1. Take an input and determine the index of the nearest codeword
2. Reconstruct the codeword value from that index

Storing only the index instead of the original drastically reduces memory. With 256 codewords, 1 byte is enough for the index. The reason this compression is lossy is that the exact original value is replaced by a representative point called a codeword.

Quantizers are categorized by the data they handle.

In the vector quantization that PQ (Product Quantization) deals with, a codeword is a point in the vector space, and since it serves as the center of a data cluster, it is called a centroid. The quality of a quantizer is measured by the MSE (Mean Squared Error) — the average squared distance between the original and its codeword.

2.2. SIFT and GIST Descriptors

These are the two kinds of image descriptors the PQ paper uses in its experiments. They have different data distribution characteristics, which also affects PQ's dimension grouping strategy. (See 3.7)

Explanation of SIFT and GIST descriptors

SIFT (Scale-Invariant Feature Transform) is a local descriptor. It detects keypoints (distinctive spots such as corners and edges) in an image, and builds a 128-dimensional vector by collecting gradient histograms around each keypoint. A single image produces hundreds to thousands of vectors. It is robust to rotation and scale changes, but the number of vectors explodes. In the paper's experiments, SIFT's natural order already groups spatially adjacent cells, making it insensitive to grouping, whereas GIST's natural order is somewhat arbitrary, so which dimensions get grouped together strongly determines performance.

Both descriptors are built by concatenating orientation histograms, but they differ in how well the natural order (slicing sequentially from the front) groups semantic units together. SIFT's natural order already groups spatially adjacent cells, making it insensitive to grouping, whereas GIST's natural order is somewhat arbitrary, so which dimensions get grouped together strongly determines performance.

2.3. Hamming Embedding

Hamming embedding is a technique that maps a high-dimensional real vector to a short binary code.

The distance in the original space is approximated by the Hamming distance (number of differing bits) between the two mapped codes. Spectral Hashing(SH) and Hamming Embedding(HE) are representative learning methods.

The advantages are that the codes are small (typically 8 bytes) and distance computation finishes with 8 table lookups. The fundamental limitation, however, is that a b-bit code has only b+1 distinct distances. A 64-bit signature can only express distances as 65 integers from 0 to 64, so countless vector pairs receive the same distance, degrading ranking accuracy.

Number of representable Hamming distances

The major benchmark comparison baselines are Hamming-family algorithms. Product Quantization keeps the Hamming family's advantages — short codes + fast lookups — while compensating for their lack of distance accuracy.

2.4. Inverted File Structure

The inverted file structure is a data structure borrowed from information retrieval that pre-partitions the dataset and stores a list of the items belonging to each partition. It is the same structure as a book index that maps word → list of pages. At search time, you scan only a few lists rather than the whole dataset.

In vector search, a separate quantizer called the coarse quantizer $q_c$ is used to create the partitions. $q_c$ is trained with plain k-means, and the number of centroids $k'$ is typically $10^3\sim 10^6$. Each centroid produced by $q_c$ corresponds to one inverted list.

On the left, coarse centroids (★) partition the space into Voronoi cells; on the right, the vectors of each cell are stored as inverted lists. The query scans only the list of its nearest centroid

In this paper, the inverted file solves the limitation that a product quantizer alone must scan all the data every time. IVFADC is a two-level hierarchy where the coarse quantizer determines which region (upper bits) and the product quantizer compresses the residual within it (lower bits).

3. PQ Paper Walkthrough

3.1. Paper Overview

At the time the paper appeared, the ANN search field had the following currents.

1. Tree-based search: KD-tree and its variants — fast in low dimensions, but in high dimensions their worst-case complexity is no better than brute force. FLANN is the auto-tuning library of this family. The fundamental memory constraint is that the original vectors must be kept in memory for the re-ranking step.

2. LSH family: E2LSH (Euclidean Locality-Sensitive Hashing) is the representative; it offers theoretical guarantees on search quality, but re-ranking requires keeping the original vectors in memory as-is, so memory usage can end up even larger than the originals.

3. Hamming embedding: the binary-code family covered in Section 2 above. Memory and speed are good, but the small number of distinct distances limits ranking accuracy.

3.1.1. Why Memory Becomes the First Constraint

The reason the paper puts "memory" forward as its core motivation is the recognition that the evaluation criteria for ANN search are a trade-off not merely of (search quality, search speed) but of (search quality, search speed, memory). Once the dataset grows to billions of vectors, the following become natural requirements.

• The full original vectors no longer fit in RAM → disk I/O dominates search speed → the vectors must be compressed to fit in RAM
• Approaches that keep the originals for re-ranking, like LSH or FLANN, collapse at this point
• Replacing the vectors themselves with short codes and estimating distances on the codes is the only solution

The question the paper solves is therefore made concrete as follows.

Can we compress vectors into short codes while securing both distance-computation accuracy and a rich set of distinct distances? And is that possible under the constraint that not just the codes but the codebook, too, must fit in memory?

Training $k = 2^{64}$ centroids with a single k-means means the codebook itself is $k \cdot D$ floats and won't fit in RAM. PQ's core idea takes direct aim at exactly this codebook memory problem.

3.1.2. Why PQ and Not Another Quantizer

Even before PQ, there were attempts to increase the number of centroids.

All three alternatives fail to solve the three problems (training data / time / memory) at once. PQ solves all three and occupies an entirely new position.

3.1.3. PQ's Position: a "semi-structured" Quantizer

Quantizers can be divided into three classes by their degree of structure.

PQ has a partial structure that trains the full space freely with k-means while forcing that space to be a product of m subspaces. It gets both k-means' adaptivity and a lattice's efficiency.

"To our knowledge, such a semi-structured quantizer has never been considered in any nearest neighbor search method."

The product quantizer itself is an old technique from information theory, but the paper states that applying it to ANN search is a first.

3.1.4. Two Advantages of Product Quantization

Advantage 1 — Diversity of distinct distances: whereas a $b$-bit Hamming code can express distances only as $b+1$ integers, PQ-ADC stores real-valued distances in the LUT (Look-Up Table), producing practically continuous distance values. With the same code length, much more accurate ranking becomes possible.

Advantage 2 — Expected squared distance estimation: PQ provides an estimate of the actual distance value. It tells you not just the rank but also how close things are. This matters in two applications.

• ε-radius search: "find all vectors within distance ε" → requires actual distance values
• Lowe's distance ratio criterion: the standard technique in SIFT matching that judges match reliability by the ratio of 1st-nearest distance / 2nd-nearest distance → requires the distance values themselves

Hamming embedding gives only the rank and cannot provide such distance values. PQ provides distance values at no extra cost.

3.1.5. The Hamming Camp's Speed Advantage Is Matched Too

Hamming embedding was popular because of its very fast distance computation using table lookups. But PQ-ADC computes distances with the same number of table lookups (8 lookups + 7 additions).

Same speed, far better accuracy — this was the decisive reason PQ could rapidly displace the Hamming camp.

3.2. Vector Quantization

The paper begins by formally defining vector quantization.

A quantizer $q$ is a function that maps a $D$-dimensional real vector to an element of the codebook.

• $c_i$ : centroid (in the paper's terminology, the reproduction value)
• $\mathcal{C}$ : the codebook of size $k$
• $\mathcal{I}$ : the index set

The set of vectors mapped to the same index is called a Voronoi cell.

The $k$ cells form a partition of $\mathbb{R}^D$, and every vector in the same cell is reconstructed to the same centroid $c_i$.

The quality of a quantizer is measured by the average squared distance between the original and its reconstruction.

3.2.1. Lloyd's optimality conditions

The paper spells out the two conditions an optimal quantizer must satisfy.

1. Nearest Neighbor Condition: $q(x) = \arg\min_{c_i \in \mathcal{C}} d(x, c_i)$ — map to the nearest centroid
2. Centroid Condition: $c_i = \mathbb{E}[X \mid X \in \mathcal{V}_i]$ — the centroid is the mean of its cell

The PQ paper uses k-means as its training tool because k-means satisfies both conditions (near-optimally).

3.2.2. Cell distortion

Per-cell distortion is also defined — the mean squared error restricted to cell $\mathcal{V}_i$.

The overall MSE is expressed as the probability-weighted average of the per-cell distortions.

3.2.3. Memory Cost

Finally, the cost of storing one index value is $\lceil \log_2 k \rceil$ bits. So choosing $k$ as a power of two is efficient for byte alignment, which is why PQ uses $k^* = 256$ as the standard (exactly 1 byte).

3.3. Product Quantization

Each subquantizer $q_j$ has its own codebook $\mathcal{C}_j$ dedicated to its subspace, and the full PQ codebook is defined as the Cartesian product.

The principle of the Cartesian product in Product Quantization

If each subquantizer has $k^* = 256$ centroids, the number of distinct centroids the full product quantizer can express is as follows.

The same $2^{64}$ centroids, yet the training and storage costs are completely different.

With $m=8, k^*=256$, the PQ codebook is only $8 \times 256 \times 16 \times 4 = 128\text{KB}$. This is how $2^{64}$ centroids are represented implicitly.

3.3.1. Data Storage Cost

Not just the codebook — how each vector is represented also has a big impact on memory. Suppose we store 100 million 128-dimensional SIFT vectors.

LSH and FLANN must keep the originals for re-ranking, so they fall in the first row. PQ estimates distances directly on the codes, so the second row is enough. This 64x difference is the decisive gap that made it possible to index billions of vectors on a single machine.

Instead of "one big codebook," the same expressive power is obtained with exponentially fewer resources through a "product of several small codebooks", and the vectors themselves are compressed into short codes and loaded into RAM.

Since $k^*$ is small, each subquantizer can be trained perfectly well with plain Lloyd's algorithm. And each vector is represented as a short code that collects the $m$ indexes from the subquantizers. With $m=8, k^=256$, one vector is compressed to 8 bytes.

Train_PQ(training_set, m, k*)
1   // training_set: n개의 D차원 벡터
2   for j = 1 to m:
3       // subspace j 학습 데이터: 모든 n개 벡터의 j번째 subvector
4       sub_data_j ← { u_j(y) : y ∈ training_set }
5       C_j ← k-means(sub_data_j, k*)   // k*개 centroid 학습
6
7   return (C_1, C_2, ..., C_m)

The training of each subspace is mutually independent, so the m of them can be processed in parallel.

Once training is done, the codebook $(C_1, \ldots, C_m)$ is produced, and we can define the encoding function $q_p$ that holds it as internal state.

Encode_PQ(y: D차원 벡터, codebooks=(C_1, ..., C_m))   // 곧 q_p(y)
1   code ← empty array of length m
2   for j = 1 to m:
3       // u_j(y): y의 j번째 subvector (D/m차원)
4       // C_j에서 *가장 가까운 centroid의 인덱스* 찾기
5       code[j] ← argmin_{i=0..k*-1} ||u_j(y) - c_{j,i}||²
6
7   return code                          // m개 인덱스, 총 m byte

The paper's notation $q_p(y)$ refers to the result of calling this Encode_PQ function — the m byte code. That is:

• Train_PQ: the training function; the result is the codebook (centroid coordinates, built once)
• $q_p$ = Encode_PQ: the encoding function; reads the codebook to convert vector → code (called for every data point)

Diagram of the PQ code encoding algorithm

3.3.2. Two Assumptions of Product Quantization

1. Each subvector carries similar energy. Since the same $k^*=256$ centroids are allocated equally to every subspace, if variance is heavily skewed to one side, some subspaces suffer insufficient resolution. The remedy is to multiply by a random orthogonal matrix before quantization, but the paper does not recommend it because preserving the correlation of adjacent dimensions takes priority.
2. Subspaces are mutually orthogonal. If subvectors are made by slicing the vector sequentially from the front, this is a split along the standard coordinate axes and is automatically guaranteed. Thanks to this assumption, the equation $\text{MSE}(q) = \sum_j \text{MSE}(q_j)$ lets us decompose the MSE.

3.4. Distance Computation: SDC vs ADC

How do we compute distances with short codes? The PQ paper presents two methods.

SDC and ADC. SDC quantizes the query too, while ADC leaves the query as-is and quantizes only the database vectors

Symmetric Distance Computation (SDC): quantize both the query $x$ and the database vector $y$, then approximate by the distance between the two centroids.

Asymmetric Distance Computation (ADC): do not quantize the query; quantize only the database vectors.

At first glance SDC seems more natural because it is symmetric, but ADC is almost always more accurate. The reason is simple: with ADC, there is no quantization error on the query side.

Another advantage of ADC is that the LUT (Look-Up Table) needs to be precomputed only once per query. When a query arrives, the following table is precomputed for each subquantizer $j$.

After that, computing the distance to one database vector takes only $m$ table lookups and $m-1$ additions, using that vector's code $(i_1, i_2, ..., i_m)$.

It is only slightly heavier than a Hamming distance computation, yet can express far richer distinct distances.

ADC_Distance(x: query, codes: database codes, codebooks)
1   // Step 1: query 쪽 LUT 미리 계산 (한 번만)
2   for j = 1 to m:
3       for i = 1 to k*:
4           LUT[j][i] ← d(u_j(x), c_{j,i})^2
5
6   // Step 2: 각 database 벡터 거리 계산 (n번 반복)
7   for each y_code in codes:
8       dist² ← 0
9       for j = 1 to m:
10          dist² ← dist² + LUT[j][y_code[j]]
11      record dist²
12
13  return top-k smallest distances

Diagram of the ADC distance computation algorithm using the LUT

Since the total cost is nearly identical, ADC is recommended unless you are in the special case of needing to reduce query-side memory.

3.5. Statistical Guarantees for Distance Estimation

There is a result showing that PQ is not a mere heuristic but a principled approximation: ADC's distance estimation error is statistically bounded by the quantizer's MSE.

Here $\text{MSDE}$ (Mean Squared Distance Error) is the mean of the squared error between the estimated distance and the true distance, and $\text{MSE}$ is the quantizer's own mean squared error.

3.5.1. Proof Steps

The key tool is the triangle inequality. For any three points $x, y, q(y)$:

This is one form of the triangle inequality; intuitively, it says "when you nudge one point, the distance to another point can change by at most the amount you moved it." Since ADC is defined as $\tilde{d}(x, y) = d(x, q(y))$, the left-hand side is the distance estimation error we want to know.

The triangle inequality for the three points x, y, q(y). The ADC estimation error (black edge minus blue dashed line) is bounded above by y's quantization error (red solid line).

Squaring both sides:

Substituting $(1)$ into the definition of $\text{MSDE}$ and simplifying the integral over $x$:

For SDC, since both the query and the database vector are quantized, the triangle inequality must be applied twice, and the result becomes $\text{MSDE}_{\text{SDC}}(q) \leq 2 \cdot \text{MSE}(q)$. The mathematical reason ADC is inherently more accurate than SDC lies in this difference of bounds.

• Training the quantizer with k-means (Lloyd's algorithm) makes the MSE small (the optimality conditions of Section 3.2)
• If MSE is small, MSDE is small too (the proof above)
• If MSDE is small, the ranking of NN search stays close to the true distances

3.6. ADC's Bias Analysis and Correction

In Section 3.5 the $MSDE$ bound dealt with the $MSE$, but the ADC estimated distance, on average, underestimates the true distance.

A typical search result using one SIFT vector as the query against a set of 1000 vectors

3.6.1. Deriving the Correction Formula

To correct this bias exactly, we directly compute the expected squared distance conditioned on y being in cell $\mathcal{V}_i$.

The paper decomposes $x - y$ into a form that passes through $c_i$.

When the three terms are integrated, the cross term becomes exactly 0 — thanks to Lloyd's second optimality condition.

The condition that the centroid is the mean of its cell is what makes the cross term exactly 0 and keeps the correction formula clean. The two remaining terms are:

Applied to PQ, it decomposes into the sum of the cell distortions of each subspace.

Each $\xi_j(y)$ can be precomputed at training time and stored in the LUT (Look-Up Table), so the extra cost at search time is just $m$ additions.

But in practice it isn't used

It is a mathematically valid correction, yet the paper recommends using ADC without the correction for NN search. The reason is the bias-variance trade-off.

Corrected ADC brings the bias to nearly 0, but the variance grows (variance: 0.00146 → 0.00155). For the ranking accuracy of NN search, plain ADC is more favorable.

• Plain ADC: bias = -0.044 (underestimate), variance = 0.00146
• Corrected ADC: bias = +0.002 (nearly 0), variance = 0.00155 (increased)

The bias shrank, but the variance grew. And in NN search, the correction term $\xi_j$ frequently exceeds the original estimate. This effectively penalizes vectors of rarely assigned indexes (= cells with large distortion $\xi$), causing genuinely close vectors to be missed.

3.7. The Impact of Dimension Grouping

The simplest implementation of PQ makes subvectors by slicing the vector sequentially from the front. Yet this grouping choice has a surprisingly large impact on performance.

The results the paper confirmed on SIFT and GIST are as follows.

(based on $recall@100$, $k^*=256$)

On the GIST descriptor, merely switching from natural order to structured order doubles recall@100 from 0.338 to 0.652. The same algorithm ran with the same code length, yet performance changed dramatically depending on how the dimensions were grouped.

Descriptors like SIFT and GIST are built by concatenating orientation histograms. Slicing in natural order can scatter the bins of one histogram across multiple subvectors, and random order is worse. Structured order groups dimensions with the same meaning (e.g., bins representing the same orientation) into one subvector. The more semantically related dimensions sit within one subvector, the better a small codebook can represent them.

4. Non-Exhaustive Search : IVFADC

The ADC of Section 3.4 is an exhaustive search. It must scan all n vectors every time, which is burdensome in environments where hundreds to thousands of SIFT descriptors are extracted per image and billions of descriptors must be indexed.

The paper proposes IVFADC, which combines an inverted file with ADC. The coarse quantizer partitions the data into Voronoi cells so that only a small part of the index is accessed quickly, and within it the residual is encoded with PQ, which even nudges accuracy upward.

IVFADC indexing system. Top: indexing flow; bottom: query flow

4.1. Coarse Quantizer and Residual Encoding

The coarse quantizer $q_c$ is an ordinary vector quantizer trained with k-means. For SIFT, the number of centroids $k'$ is typically in the 1,000 – 1,000,000 range, smaller than the $2^{64}$ of the product quantizer seen in Section 3.

The key point is that the vector $y$ is not encoded by PQ directly; the residual is encoded instead.

The residual corresponds to the offset within the Voronoi cell. It carries much less energy than the original vector, so a more accurate approximation is possible with the same code length. The vector is approximated as follows.

The stored representation is the tuple $(q_c(y), q_p(r(y)))$. By analogy with binary representation, the coarse quantizer handles the upper bits (MSB) and the product quantizer the lower bits (LSB).

The distance estimate is computed as the distance between the query $x$ and $\ddot{y}$.

To compute this efficiently, the subquantizer decomposition is used.

As with ADC, for each subquantizer $q_{p_j}$ the distances between the partial residual $u_j(x - q_c(y))$ and the centroids $c_{j,i}$ are precomputed and stored in the LUT.

The product quantizer trains one unique PQ on the set of residuals of the training data. Even though the training vectors belong to different coarse cells, it is trained on the result of marginalizing the residual distribution over all Voronoi cells.

Keeping a separate PQ per cell would make the codebook memory $k' \times d \times k^*$ floating point values — impractical.

Training algorithm

Train_IVFADC(training_set, k', m, k*)
1   // Step 1: coarse codebook 학습 (원본 벡터로 k-means)
2   coarse_codebook ← k-means(training_set, k')
3   //  → k'개의 coarse centroid c_1, ..., c_k'
4   //  → 이걸로 q_c 함수가 정의됨 (벡터 → 가장 가까운 c_i의 인덱스)
5
6   // Step 2: 학습 데이터의 residual 계산
7   residuals ← { y - q_c(y) : y ∈ training_set }
8
9   // Step 3: residual로 단일 product quantizer 학습 (3.3절 Train_PQ)
10  pq_codebooks ← Train_PQ(residuals, m, k*)
11  //  → m개 subspace codebook (C_1, ..., C_m)
12  //  → 이걸로 q_p 함수가 정의됨 (벡터 → m개 인덱스 = code)
13
14  return (coarse_codebook, pq_codebooks)

4.2. Indexing Data Structure

The inverted file is implemented as an array of lists $L_1, \ldots, L_{k'}$. For a dataset $Y$, the list corresponding to centroid $c_i$ is:

A list entry consists of two fields: an identifier and a code.

The identifier is the overhead incurred by the inverted file structure. Depending on the kind of vectors, it may not even need to be unique. Example: when an image is represented by local descriptors, an image identifier can substitute for the vector identifier — every vector of the same image shares the same identifier. For a dataset of one million images, 20 bits suffice.

Indexing procedure (for a single vector $y$):

1. Quantize y to $q_c(y)$
2. Compute the residual $r(y) = y - q_c(y)$
3. Quantize $r(y)$ to $q_p(r(y))$; from the product quantizer's viewpoint this is the same as assigning each $u_j(y)$ to $q_j(u_j(y))$ ($j = 1, \ldots, m$).
4. Append the identifier + PQ code as an entry to the inverted list corresponding to $q_c(y)$.

Index_IVFADC(database: [(id_1, y_1), ..., (id_n, y_n)], coarse_codebook, pq_codebooks)
1   // k'개 빈 list 초기화
2   L_1, ..., L_k' ← empty
3
4   for each (id, y) in database:
5       // Step 1: coarse quantize → 어느 list?
6       i ← argmin_{1..k'} ||y - c_i||²        // c_i는 coarse_codebook[i]
7
8       // Step 2: residual 계산
9       r ← y - c_i
10
11      // Step 3: residual을 PQ로 인코딩 → code
12      code ← Encode_PQ(r, pq_codebooks)      // 곧 q_p(r), m byte 반환
13
14      // Step 4: list L_i에 (id, code) entry 추가
15      L_i.append((id, code))
16
17  return (L_1, ..., L_k')

4.3. Search Algorithm

The heart of the search is that, thanks to the inverted file, distance estimation happens only on a small subset of Y — only the list $L_i$ corresponding to the query $x$'s $q_c(x)$ is scanned.

However, the NN closest to $x$ may not be quantized to the same centroid and can belong to a neighboring centroid. To solve this problem, a multiple assignment strategy is used. The query $x$ is assigned to w indexes (the w-NN of $x$ in the coarse codebook), and all the corresponding inverted lists are scanned. Multiple assignment is not applied to database vectors — memory would grow w-fold outright.

Search procedure (query $x$):

1. Quantize $x$ to the w-NN of codebook $q_c$. The following steps are applied to all w assignments (for convenience, the residual is collectively denoted $r(x)$).
2. For each subquantizer $j$ and each centroid $c_{j,i}$, compute the squared distance $d(u_j(r(x)), c_{j,i})^2$. Fill the LUT.
3. For every indexed vector in the inverted list, compute the squared distance to $r(x)$. Using the subvector-to-centroid distances computed in step 2, sum the m looked-up values (Eq. 2).
4. Select the K-NN based on the estimated distances. Implemented efficiently with a fixed-capacity Maxheap — keep the K smallest values seen so far, and add an entry only when a newly computed distance is smaller than the Maxheap's maximum distance.

IVFADC_Search(x: query, w, K, coarse_codebook, pq_codebooks, lists)
1   // Step 1: query를 모든 coarse centroid와 비교 → 가까운 w개 list 선택
2   for i = 1 to k':
3       coarse_dist[i] ← ||x - c_i||²              // c_i는 coarse_codebook[i]
4   top_w_indices ← argsort(coarse_dist)[:w]
5
6   H ← Maxheap(capacity=K)
7
8   for each i in top_w_indices:
9       r_x ← x - c_i                              // query residual
10
11      // Step 2: LUT 채우기 (m × k* 엔트리)
12      //         pq_codebooks의 centroid 좌표를 *읽어서* 거리 미리 계산
13      for j = 1 to m:
14          for n = 0 to k*-1:
15              LUT[j][n] ← ||u_j(r_x) - c_{j,n}||²   // c_{j,n}은 pq_codebooks[j][n]
16
17      // Step 3: list L_i 스캔, code의 인덱스로 LUT lookup
18      for each (id, code) in L_i:
19          d² ← 0
20          for j = 1 to m:
21              d² ← d² + LUT[j][code[j]]          // j번째 subspace 거리 lookup
22          if d² < H.max():
23              H.push((d², id))
24
25  // Step 4: Maxheap에서 K개 추출
26  return sorted(H)[:K]

4.4. What the Parameters Mean

Here is a summary of how IVFADC's parameters affect search performance.

The paper's recommended settings are $k^* = 256, m = 8$ (i.e., 64-bit codes) and, for SIFT, $k' \in [1024, 8192]$.

Diagram of the IVF-ADC index and search algorithm

5. Experimental Results

The paper ran its validation on two datasets: SIFT (128 dimensions) and GIST (960 dimensions).

The experimental environment is a single core, with separate sets for training, database, and queries.

5.1. Code length vs Accuracy trade-off

SDC's recall@100 vs code length

ADC's recall@100 vs code length

At the same code length, a small number of large subquantizers performs better than a large number of small subquantizers. For example, when building a 64-bit code, $(m=8, k^*=256)$ is more accurate than $(m=16, k^*=16)$.

ADC was consistently superior to SDC. ADC with $k^*=64$ achieved roughly the same accuracy as SDC with $k^*=256$.

5.2. Comparison with the State of the Art

The PQ paper carries out two kinds of comparisons separately.

• Accuracy comparison against memory-saving algorithms at the same code length
• Speed-accuracy trade-off against tree-based search that keeps the original vectors (FLANN)

1) recall@R comparison (vs SH, HE)

recall@R comparison on SIFT 64-bit codes (Parameters: m=8 and k^∗=256 for SDC/ADC, k’ =1024 for HE and IVFADC)

recall@R comparison on GIST 64-bit codes (Parameters: m=8 and k^∗=256 for SDC/ADC, k’ =1024 for HE and IVFADC)

$recall@R$ is the fraction of all queries for which the true nearest neighbor appears within the $top-R$.

At 64-bit codes, the comparison was against two baselines from the same memory-saving camp.

• Spectral Hashing(SH) [Weiss et al. 2008]
• Hamming Embedding(HE) [Jégou et al. 2008]

The whole PQ family (SDC/ADC/IVFADC) beat spectral hashing by a wide margin. To reach the same recall, ADC needed to verify an order of magnitude fewer results than spectral hashing.

The best performance came from IVFADC, because it pushed accuracy even higher while avoiding exhaustive search.

2) search time vs accuracy comparison (vs FLANN)

Trade-off between search quality (1−recall@1) and search time

FLANN is not a short-code algorithm but a library that accelerates search with trees, so comparing on the same recall@R curve is meaningless; it is more natural to compare the trade-off between actual search time and Top-1 accuracy ($1-recall@1$).

IVFADC was faster at comparable accuracy, or more accurate at comparable time, and the more important difference was memory. IVFADC's index is under 25MB; FLANN's is over 250MB. This is because FLANN must keep the original vectors in RAM for re-ranking.

5.3. Complexity vs Speed trade-off

Search time and recall@100 of each method on the GIST dataset (500 queries, 64-bit codes). IVFADC measured while varying k’ and w

• The exhaustive camp (SDC/ADC/SH) takes similar time (16–23ms), but ADC has 5x the recall of SH — the LUT's real-valued distances carry richer information than Hamming's integer distances.
• IVFADC (w=1) reduces code comparisons from 1 million to about 2 thousand — a several-hundred-fold reduction — and is 10x faster as well. Recall drops, though.
• Increasing w recovers recall: at w=8 there exists an operating point that is both faster and more accurate than exhaustive ADC.
• Choosing $k'$: for small datasets a small $k'$ (1K–8K) is favorable; the larger the dataset, the larger the $k'$ (tens of thousands to 1 million). However, once $k'⋅D>n/k'*$, the coarse quantizer itself becomes the bottleneck.

IVFADC can trace the speed-accuracy trade-off with the two parameters $k', w$. In practice, you pick the point where recall is maximal within the allowed time budget.

5.4. Large-Scale Experiment: 2 Billion Vectors

Search time as a function of dataset size (HE vs IVFADC)

The large-scale experiment indexed about 2 billion SIFT descriptors extracted from a million images. IVFADC and HE were compared under the same 20,000-word coarse codebook and 64-bit signature conditions.

On small datasets, IVFADC is slightly slower because of the extra quantization step. But as the dataset grows, the distance computations inside the inverted lists become dominant, and the two methods' per-vector processing times become nearly identical.

HE computes the Hamming distance with 8 table lookups, and IVFADC likewise computes the PQ distance with 8 table lookups. Floating-point operations becoming as fast as binary operations — that is PQ's core efficiency.

6. Limitations of PQ

6.1. Limitation: Sensitivity to Dimension Grouping

As seen in Section 3.7, PQ's performance varies greatly depending on which dimensions are grouped into the same subvector.

For descriptors with clear semantic groups, like SIFT and GIST, a structured order can yield good results, but PQ is hard to apply directly to generic vectors whose semantics are unknown (e.g., word embeddings, learned features).

6.2. Limitation: Performance Variance Across Data Distributions

PQ works best when each subvector carries similar energy and the subspaces are mutually orthogonal (the assumptions of Section 3.3).

On datasets other than SIFT/GIST, the effectiveness can differ. Learned embeddings that appeared later (word2vec, BERT, CLIP, etc.) often have highly uneven per-dimension variance and adjacent dimensions that are semantically unrelated, so applying PQ as-is causes a large drop in accuracy.

6.3. Limitation: Differences in Residual Distributions

IVFADC uses one identical product quantizer across all cells.

This rests on the assumption that the residual distributions of all cells are similar, but in reality the residual distribution differs quite a bit from cell to cell. Training a separate PQ per cell improves accuracy, but all $k'$ codebooks must be stored, making memory usage impractical

7. Closing

PQ is an algorithm that solved ANN search from the perspective of compression.

Where graph-based algorithms focused on how to traverse quickly, PQ focused on how to represent compactly. And so that the compression would not wreck distance computation, it found a way to gain large expressive power through a product of several small codebooks by decomposing the space into a product of subspaces.

IVFADC, which combines this with an inverted file structure, merged two effects into one system: compression cuts memory, and partitioning cuts time. This combination, which made it possible to index 2 billion vectors on a single machine, still holds its place today as the standard baseline for large-scale vector search.

8. References

• Product Quantization for Nearest Neighbor Searchdoi.org
• Spectral Hashingproceedings.neurips.cc
• Hamming Embedding and Weak Geometric Consistency for Large Scale Image Searchinria.hal.science
• Fast Approximate Nearest Neighbors with Automatic Algorithm Configurationcs.ubc.ca