Vector Quantization

One line: store numbers with fewer bits (fp32 → int8 / 1 bit / short code). Lose a little precision, gain a lot of memory and speed.

Two places it shows up in GenAI systems:

• Model weights: fp16 → int8/int4. 70B model 140 GB → 35 GB → fewer GPUs, faster decode. See [[GenAI Capacity Math]].
• Embedding vectors: this page.

---

Why vectors need it

Vector search is a memory problem. HNSW-style indexes want every vector in RAM; RAM is expensive.

100M chunks × 1024 dims × 4 B (fp32) = 410 GB RAM   ← many nodes, $$$

Quantization shrinks that 4–32×:

1. Memory/cost: fits on fewer machines, or one.
2. Speed: smaller vectors → better CPU cache use, less memory bandwidth. Integer/bit math (SIMD, popcount) beats float math.
3. Scale: billion-vector indexes become feasible.
4. Small recall loss: search only needs the ranking roughly right, not exact distances.

---

The 3 main types

---

Product Quantization (PQ) — in detail

Idea: a single k-means codebook over the full 1024-dim space would need billions of centroids to be accurate. PQ instead splits the vector into m independent sub-spaces and quantizes each one separately. Combining sub-codes gives 256^m possible reconstructions from only m × 256 stored centroids. That "product" of small codebooks is the name.

Running example: N = 100M vectors, d = 1024, m = 64 sub-vectors, nbits = 8 (256 centroids per sub-space). Sub-vector dim = 1024 / 64 = 16.

Step 1 — Train (offline, once)

take a representative sample (e.g. 1–5M vectors)
for j in 1..64:
    run k-means (k = 256) on dims [16j .. 16j+15] of the sample
    → codebook_j: 256 centroids × 16 dims
total codebooks = 64 × 256 × 16 floats × 4 B ≈ 1 MB

Step 2 — Encode (every vector, at insert)

x (1024 floats) → split into x_1 .. x_64 (16 dims each)
code_j = index of nearest centroid to x_j in codebook_j   (0–255 → 1 byte)
stored code = [code_1 .. code_64] = 64 bytes   (was 4096 B → 64× smaller)

flowchart LR
  V[1024-dim fp32 vector<br/>4096 B] --> S[Split into<br/>64 × 16-dim chunks]
  S --> K[Each chunk → nearest<br/>of 256 centroids]
  K --> C[64 centroid IDs<br/>64 B]

Step 3 — Search with Asymmetric Distance Computation (ADC)

The query is not quantized (only database vectors are). That is the "asymmetric" part, and it's more accurate than quantizing both sides (SDC).

1. split query q into q_1 .. q_64
2. build lookup table T[j][k] = ||q_j − codebook_j[k]||²
   size 64 × 256 = 16,384 floats; cost ≈ 64 × 256 × 16 ≈ 262k FLOPs (once per query)
3. for every stored code c:
       dist(q, x) ≈ Σ_j T[j][c_j]        ← 64 table lookups + 64 adds, no float vector math
4. keep top-k smallest

The approximation: x is replaced by its reconstruction (concatenated centroids), so the distance error equals the quantization error of x.

PQ knobs

Limitation of PQ alone

Brute-force ADC over 100M codes = 6.4 billion lookups per query → still ~seconds. We need to avoid scanning everything → IVF.

---

IVF-PQ — in detail

IVF = Inverted File index. Same idea as a search engine's inverted index, but the "terms" are cluster centroids. Partition the space with k-means; each vector lives in the list of its nearest centroid; at query time only scan the few closest lists.

IVF-PQ = IVF for which vectors to look at + PQ for how to store and compare them cheaply. The standard billion-scale index (FAISS IndexIVFPQ, Milvus IVF_PQ). FAISS factory string: "IVF65536,PQ64".

Build

1. Coarse quantizer: k-means on sample with nlist centroids (e.g. 65,536)
2. For each vector x:
     list_id  = nearest coarse centroid c
     residual r = x − c                       ← encode the residual, not x
     code     = PQ.encode(r)                  (64 B)
     append (vector_id, code) to inverted_list[list_id]
3. PQ codebooks are trained on residuals of the sample

Why residuals? After subtracting the cluster centroid, vectors are centred near zero with much smaller spread → the same 256 centroids per sub-space describe them far more precisely → better recall for the same 64 bytes.

flowchart TB
  X[Vector x] --> CQ[Coarse quantizer<br/>nearest of nlist centroids]
  CQ --> R[Residual r = x − c]
  R --> PQ[PQ encode residual<br/>64 B]
  PQ --> L[(Inverted list for c<br/>id + code)]

Search

1. compare q to all nlist coarse centroids → pick nprobe nearest (e.g. 32)
   (65,536 × 1024 dims ≈ 67M FLOPs; or put an HNSW index over the centroids)
2. for each probed list with centroid c:
       q_res = q − c
       build ADC table for q_res              (one table per probed list)
       scan its codes with table lookups
3. merge results → top k' candidates (e.g. 200)
4. optional rescore with full-precision vectors → top 10

flowchart LR
  Q[Query q] --> C1[Find nprobe nearest<br/>coarse centroids]
  C1 --> S1[Scan list 1<br/>ADC on residual codes]
  C1 --> S2[Scan list 2]
  C1 --> S3[... list nprobe]
  S1 --> M[Merge top k']
  S2 --> M
  S3 --> M
  M --> RS[Rescore with fp32<br/>from SSD]
  RS --> T[Top 10]

The numbers (N = 100M, d = 1024)

nlist = 65,536  → avg list size ≈ 100M / 65,536 ≈ 1,500 vectors
nprobe = 32     → scan ≈ 48k codes instead of 100M   (~2,000× less work)
Memory:
  PQ codes      100M × 64 B          = 6.4 GB
  vector IDs    100M × 8 B           = 0.8 GB
  centroids     65,536 × 1024 × 4 B  = 0.27 GB
  total ≈ 7.5 GB   vs 410 GB raw fp32 (≈ 55× smaller)
Latency: single-digit ms per query on CPU

Tuning knobs

IVF-PQ vs HNSW

Operational gotchas

• Training data must be representative. If the data distribution shifts (new doc types, new embedding model), lists become unbalanced and recall drops → retrain and rebuild (blue-green).
• Unbalanced lists: a few huge lists make some queries slow. Monitor list-size distribution.
• Deletes: usually tombstones + periodic compaction.
• Metadata filtering (e.g. ACLs): filter inside the list scan; very selective filters can starve results → raise nprobe or use a filtered/partitioned index.
• Embedding model change = re-encode everything; codebooks are tied to the embedding space.

Minimal FAISS example

import faiss
import numpy as np

d, nlist, m = 1024, 65536, 64
quantizer = faiss.IndexFlatL2(d)                    # coarse quantizer
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8) # 8 bits → 256 centroids/sub-space

index.train(train_sample)        # e.g. 2–5M representative vectors, float32
index.add(all_vectors)           # assigns list + encodes residuals
index.nprobe = 32                # query-time recall/latency dial

D, I = index.search(queries, 200)   # 200 candidates per query
# rescore: load full-precision vectors for I from disk, compute exact distances, keep top 10

HNSW vs IVF-PQ short version also in [[GenAI Vocabulary]].

---

Production pattern: oversample, then rescore

1. Search quantized index → top 200 candidates   (fast, in RAM)
2. Fetch those 200 full-precision vectors          (SSD / disk)
3. Recompute exact distances → return top 10

Recovers most of the lost recall at a small cost. Say this in interviews.

---

Trade-offs to state

• Gain: 4–32× less memory, faster search, cheaper infrastructure.
• Cost: some recall loss. PQ needs a training step (k-means) and must be retrained if the data distribution shifts.
• Decision rule:
  • int8 = safe default: almost free quality-wise, 4× smaller.
  • Binary or PQ + rescoring at hundreds of millions to billions of vectors.
  • Always measure recall@k on your own eval set before and after.
• Related lever: fewer dimensions instead of fewer bits. Matryoshka embeddings let you truncate 1024 → 256 dims. Combine both.

---

Worked example — Enterprise RAG ([[Design Enterprise RAG Q&A]])

200M chunks × 768 dims:
fp32       = 615 GB
int8       = 154 GB   (4×)
PQ m=96    → 96 B/vector = 19 GB   (32×) + rescore from SSD

---

Interview Q&A

Q: Why quantize embeddings? Memory dominates vector search cost; int8 gives 4× smaller with ~1% recall loss, PQ/binary give 16–32× for billion scale. Q: How do you avoid the recall hit? Oversample on the quantized index, rescore top candidates with full-precision vectors. Q: Scalar vs product quantization? Scalar compresses each dimension independently (simple, 4×, no training). PQ compresses groups of dimensions with learned codebooks (16–64×, needs training, more recall loss). Q: Walk me through IVF-PQ search. Compare query to coarse centroids → probe nprobe nearest lists → per list build ADC table on q − centroid → scan residual codes with lookups → merge top k' → rescore with fp32. Q: Why encode residuals instead of raw vectors? Residuals have much smaller spread, so the same codebooks quantize them more precisely → higher recall at the same bytes. Q: Recall dropped after launch — what knob first? Raise nprobe (no rebuild), then rescore depth k'; if data drifted, retrain coarse + PQ codebooks. Q: When would you not quantize? Small corpus that fits in RAM anyway (< ~10M vectors), or recall-critical use cases where the loss is measured and unacceptable.

Related: [[GenAI Vocabulary]] · [[GenAI Capacity Math]] · [[Learning/AI & ML/LLM Fundamentals]] (weight quantization) · [[index|GenAI index]]