TracksStudyAbout
Sign in
Start studying
Module 8 · Embeddings & Search Module contents
Module 8  ·  Card 16 / 17advanced

Vector Quantization

A million vectors of a thousand dimensions in full precision is four gigabytes before any index.

Quantization shrinks each vector by storing an approximation instead of the exact numbers.

Product quantization splits a vector into chunks and replaces each with a codebook entry.

Binary quantization goes further, keeping one bit per dimension and comparing with fast bit operations.

Accuracy drops, so the usual pattern is a compressed first pass rescored on the exact vectors.

Back Next
Learn in depth ↓
Module 08 · Embeddings & Search · 17 concepts
In depth  /  15 lines

Vector Quantization, in more detail

Embeddings are large, and it is the storage rather than the arithmetic that usually hurts first.

A thousand-dimension vector at four bytes per number is four kilobytes on its own.

Ten million of those is forty gigabytes, before the index structure that makes them searchable.

Vector quantization reduces that by storing an approximation of each vector rather than the vector.

Scalar quantization is the simplest form, mapping each dimension from a float to a single byte.

That is a fourfold reduction and typically costs very little recall, which makes it a safe default.

Product quantization is the classic method and compresses far harder.

The vector is cut into chunks, and k-means over each chunk position produces a codebook of centroids.

Each chunk is then stored as the identifier of its nearest centroid, often a single byte.

A thousand-dimension vector can end up in sixty-four bytes, a compression of over sixty times.

Distances are computed against the codebook using precomputed tables, so the search is also faster.

Binary quantization is the most aggressive, keeping only the sign of each dimension.

Comparison then becomes a Hamming distance, which modern processors compute extremely quickly.

All of these lose information, so the standard pattern is a two-stage search.

The compressed index proposes a few hundred candidates and those are rescored on the exact vectors.

Want the full technical article? Wikipedia ↗
Deep dive

What is underneath Vector Quantization

Replacing a vector with the address of a similar one

x≈μc(x),c(x)∈{1,…,K}\mathbf{x} \approx \boldsymbol{\mu}_{c(\mathbf{x})}, \qquad c(\mathbf{x}) \in \{1, \dots, K\}

Cluster the vectors, keep the centroids in a codebook, and store only which centroid each vector is nearest to.

log⁡2K bits per vector\log_2 K \text{ bits per vector}

With 256 centroids that is one byte, replacing 3,072 bytes of float32. The compression is enormous and the error is fatal, because 256 points cannot describe a 768-dimensional space.

Product quantisation

x=[ x1,  x2,  …,  xm ]\mathbf{x} = [\, \mathbf{x}^{1}, \; \mathbf{x}^{2}, \; \dots, \; \mathbf{x}^{m} \,]

Split the vector into mm sub-vectors and quantise each one separately with its own codebook of KK centroids.

Km effective centroids, mlog⁡2K bitsK^{m} \text{ effective centroids, } m \log_2 K \text{ bits}

With m=96m = 96 and K=256K = 256, the representable set is 25696256^{96} vectors while the storage is 96 bytes, down from 3,072.

That exponential is the whole idea: the codebooks combine multiplicatively and the storage adds.

3072→96 bytes,32× smaller3072 \to 96 \text{ bytes}, \quad 32\times \text{ smaller}

Distances without decompressing

d(q,x)2≈∑j=1md(qj,  μcj(x)j)2d(\mathbf{q}, \mathbf{x})^2 \approx \sum_{j=1}^{m} d\big(\mathbf{q}^{j}, \; \boldsymbol{\mu}^{j}_{c_j(\mathbf{x})}\big)^2

The squared distance decomposes across the sub-vectors, so it can be summed from per-segment distances rather than reconstructed.

m×K table, computed once per querym \times K \text{ table, computed once per query}

Precompute the distance from each query segment to each of that segment's centroids. Scoring a stored vector is then mm table lookups and mm additions, with no multiplication at all.

That is why a quantised scan is not merely smaller but several times faster per vector than a float scan.

One index, in order

  1. Train the codebooks by running k-means on each segment of a sample.
  2. Encode every corpus vector to its mm centroid ids.
  3. At query time, build the lookup table from the query.
  4. Scan the codes, summing table entries to get approximate distances.
  5. Rescore the top candidates against the original vectors, if they are kept.

Step five is what keeps the ranking honest. Quantisation decides who the candidates are, and full precision decides their order.

The binary extreme

bi=1[xi>0]b_i = \mathbf{1}[x_i > 0]

Binary quantisation keeps only the sign of each dimension, giving one bit per dimension and a 32-fold reduction.

dH(a,b)=popcount(a⊕b)d_H(\mathbf{a}, \mathbf{b}) = \mathrm{popcount}(\mathbf{a} \oplus \mathbf{b})

Comparison becomes an exclusive-or and a bit count, which a CPU does on 512 bits per instruction.

It loses more than product quantisation and it is astonishingly fast, so it is used as a first filter with exact rescoring behind it.

What it costs

Recall drops a few points at 32 times compression.

The loss is real and it is usually acceptable, because retrieval feeds a reranker that fixes the ordering of whatever it is handed.

Codebooks are trained on a sample, so a corpus whose distribution shifts over time slowly degrades until they are retrained.

Quantisation error is also not uniform. Dimensions with high variance suffer most, which is why rotating the space first, as OPQ does, measurably improves the result for no extra storage.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1
Why is a quantized search usually followed by rescoring on the exact vectors?
Concepts these five lines lean on
PrecisionAccuracyK-MeansVectors · Data ScienceRecall
Embeddings & Search

17 concepts in this module, then a graded test with every answer explained.

Study this module →
↑↓ move↵ openesc close