Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Indexing and ANN Search

Product Quantization and Vector Compression

Shrink vector indexes 4x to 64x with scalar, binary and product quantization. Build each in NumPy, measure recall, and learn when rescoring recovers accuracy.

Embeddings are expensive to store: a 1536-dimension float32 vector takes 6 KB, so a hundred million chunks need 600 GB of RAM before any index overhead. Quantization shrinks vectors by storing coarser numbers, trading a little accuracy for a lot of memory (and often speed, because less data moves through the CPU).

There are three levels of aggressiveness. This lesson builds each one, measures what it costs in recall, and shows the habit that makes aggressive compression safe: search with the compressed vectors, then re-score the best candidates with the full-precision ones.

The experiment setup

We use clustered 64-dimension data, exact search as ground truth, and recall@10 as the metric (recall).

Level 1: scalar quantization (float32 to int8)

Map each coordinate from a float to one of 256 integer levels. Memory drops 4 times (4 bytes to 1 byte per number), and recall barely changes, because 256 levels are plenty for most embedding dimensions.

Level 2: binary quantization (1 bit per dimension)

Keep only the sign of each coordinate: positive becomes 1, negative becomes 0. A 1536-dimension vector becomes 1536 bits = 192 bytes, a 32 times reduction. Distance becomes Hamming distance (count of differing bits), which CPUs compute extremely fast with XOR and popcount. Recall drops more, but rescoring recovers most of it.

Python Scalar and binary quantization with rescoring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Scalar quantization cut memory 4 times for a recall of 0.976. Binary alone lost most accuracy here (recall 0.23: it keeps only 1 bit of 32 per number, and 64 dimensions give very few bits to work with), but fetching 10 times more candidates and re-ranking them with the original vectors brought recall back to 0.84. Models with 1024 or more dimensions fare much better. The rescoring step needs the full-precision vectors, which many databases keep on disk or in cheaper storage while the compact codes stay in RAM.

Level 3: product quantization (PQ)

PQ compresses harder than scalar quantization while keeping more information than one bit per dimension. The method:

  1. Split each vector into m equal sub-vectors (for example 64 dimensions into 8 pieces of 8).
  2. For each piece, run k-means on that sub-space to learn a small codebook of, say, 256 representative sub-vectors.
  3. Encode a vector by replacing each piece with the index of its nearest codebook entry. 8 pieces times 1 byte = 8 bytes per vector instead of 256.
  4. At query time, build a small lookup table of distances from each query piece to every codebook entry; the distance to any stored vector is then just m table lookups and additions (asymmetric distance computation, ADC: the query stays exact, only the data is compressed).
flowchart LR
    V["64-dim vector"] --> S["Split into 8 pieces of 8 dims"]
    S --> C["Replace each piece by its nearest codebook id"]
    C --> B["8 bytes: [17, 203, 5, 88, 140, 9, 61, 254]"]

A product-quantized code: one small integer per piece.

Python Product quantization in NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the pattern: more pieces m means longer codes and better recall. m = 4 gives 64 times smaller vectors but recall of only 0.07 from the codes alone; m = 16 (16 times smaller) reaches 0.41. Rescoring the best 100 candidates with the original vectors lifts these to 0.59, 0.86 and 0.99. Note that this toy uses only 64 centroids per piece and 64 dimensions, so the raw PQ numbers are lower than a real system with 256 centroids and larger vectors would show, but the lesson holds: PQ finds candidates, rescoring finishes the job.

Comparing the options

Method Bytes for 1536 dims Reduction Recall impact Notes
float32 6,144 1x none baseline
float16 3,072 2x negligible easy win
int8 (scalar) 1,536 4x tiny widely supported
binary 192 32x moderate, fixed by rescoring needs models that tolerate it
PQ (m=96, 1 byte each) 96 64x moderate, fixed by rescoring needs training

Binary quantization works best on high-dimension models (1024 and up) that were tested for it; on 384-dimension vectors it loses a lot more. Always check a model's documentation.

Using quantization in practice

  • Rescore: oversample (fetch 3 to 10 times k candidates from the compressed index) and re-rank with full vectors. This is a one-line setting in most databases.
  • Train on representative data: PQ codebooks are learned. Train on a sample that looks like production, and retrain if your data changes a lot.
  • Combine with an index: HNSW with scalar quantization, or IVF-PQ, are standard recipes.
  • Measure: run your evaluation questions (retrieval metrics) before and after. A recall number against exact search is not the same as answer quality; check both.
  • Mind the budget: compare the saving with the dimension choice itself (embedding dimensions). Sometimes a smaller model beats a compressed bigger one.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Scalar quantization from float32 to int8 reduces vector memory by about:

    Each number shrinks from 4 bytes to 1 byte, a 4x reduction.
  2. 2. How does binary quantization store a 1536-dimension vector?

    One bit per dimension is 1536 bits, i.e. 192 bytes, a 32x reduction. Comparisons use Hamming distance.
  3. 3. What does the rescoring step do?

    Compressed search finds a candidate pool quickly; exact scores on a few hundred candidates restore most accuracy.
  4. 4. In product quantization, what is stored for each vector?

    The vector is split into m pieces, each replaced by the id of its nearest codebook entry.
  5. 5. What does 'asymmetric' mean in asymmetric distance computation?

    Only the database vectors are quantised; the query's exact pieces are compared to codebook entries via a lookup table.

Summary

  • Quantization trades accuracy for memory: int8 (4x), binary (32x), product quantization (often 16x to 64x).
  • Scalar int8 costs almost no recall; binary and PQ cost more but are repaired by oversampling and rescoring.
  • PQ splits vectors into pieces, learns a codebook per piece with k-means and stores one small id per piece.
  • Always evaluate before and after, and train PQ on representative data.

Next: Locality-Sensitive Hashing