Explain the Product Quantization compression pipeline that takes a 1024-dim float32 vector (4096 bytes) and produces a 32-byte PQ-encoded representation. Cover the offline training step and the per vector encoding step.
Free · 2 AI evals / day
**Product Quantization (PQ)** is a vector compression technique that turns a high-dimensional float vector into a tiny byte string. Walk it through end to end:
**Step 1: Pick the parameter pq_m.** This is the number of sub-vectors. The target encoding is 32 bytes; each sub-vector becomes 1 byte; so pq_m = 32.
**Step 2: Train codebooks (offline, once per corpus).** Take a training sample of vectors (typically 100k to 1M from the corpus). Split each vector into 32 contiguous sub-vectors of 32 dims each. For sub-vector position 1, gather every training vector's first sub-vector and run k-means with 256 centers; this produces codebook 1, a set of 256 32-dim centroids. Repeat for positions 2 through 32. Final artifact: 32 codebooks, each containing 256 centroids.
**Step 3: Encode any new vector (per-vector, cheap).** Take a 1024-dim float32 vector. Split into 32 sub-vectors. For each sub-vector, find the closest centroid in that subspace's codebook (a 256-way comparison). Store the 1-byte index (0-255) of the winning centroid. Concatenate the 32 indices into a 32-byte string.
**Result.** 4096 bytes (1024 floats x 4 bytes) compressed to 32 bytes. That is a 128x reduction. The cost is information loss: each sub-vector is replaced by its nearest codebook entry, introducing **quantization error**. Recall drops slightly relative to full-precision search, but the memory savings unlock billion-scale ANN on commodity hardware.
**PQ has two distinct phases. Get the phase boundary right or the rest collapses.**
**Offline codebook training (one-time per corpus).**
Select `pq_m = 32` (the number of subspaces) and `nbits = 8` (the bits per code, giving `2^8 = 256` centroids per codebook). The 1024-dim space is split into 32 contiguous chunks of 32 dims each: subspace 1 is dims 1-32, subspace 2 is dims 33-64, and so on.
Draw a training sample of vectors (commonly 100k to 1M from the corpus). For each subspace independently, take the corresponding 32-dim slice of every training vector and run k-means with 256 centroids on that slice. After training, you have 32 codebooks, each holding 256 32-dim centroids. Memory cost of the codebooks: 32 * 256 * 32 * 4 = 1 MB. The codebooks are the fixed compression artifact.
**Per-vector encoding (run on every insert).**
Given a 1024-dim float32 vector, split it into 32 contiguous 32-dim sub-vectors. For each sub-vector, compute its distance to all 256 centroids in the matching codebook and pick the nearest. Store the centroid's index as a single byte (0-255). The 32 byte indices concatenated form the PQ code: 32 bytes total. Encoding cost is 32 * 256 = 8192 distance comparisons per vector, all in 32-dim space; this runs in microseconds per vector with SIMD.
**Compression ratio.** 1024 * 4 = 4096 bytes per uncompressed vector, vs 32 bytes per PQ-encoded vector. 128x compression.
**The trade.** The cost is recall. Each 32-dim sub-vector gets replaced by one of 256 representatives in its subspace, introducing quantization error. Reconstruction loss is bounded by sub-vector to nearest centroid distance; this propagates into approximate distance computation at search time. Recall typically drops 1-5 percentage points compared to full-precision search, depending on data distribution and how well-aligned the subspace partitioning is with the embedding manifold.
Quick reference
TL;DR
Split the 1024-dim vector into 32 sub-vectors of 32 dims. For each subspace, k-means produced 256 centroids during offline training. Encode each sub-vector as the 1-byte index of its nearest centroid.
Imagine your 1024-number vector is a long bookshelf with 1024 books. **The chunked-codebook method** (called PQ) chops the shelf into 32 mini-shelves of 32 books each. For each mini-shelf, a librarian has already prepared a catalogue of 256 typical mini-shelf arrangements (the codebook). To compress your bookshelf, you look at each of your 32 mini-shelves, find the catalogue entry that looks most like it, and write down that catalogue number. Catalogue numbers go from 0 to 255, which fits in one byte. So your entire 1024-book shelf becomes 32 small numbers, one per mini-shelf. The cost is that two different mini-shelf arrangements may round to the same catalogue entry, so some detail is lost; that is the rounding error.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Corpus is small enough to hold full vectors in RAM PQ pays a recall cost; if memory is not the binding constraint, full-precision search wins on quality.
Recall target is very high (>0.98) and no rerank is possible Quantization error caps recall a few points below full-precision; without a rerank pass on full vectors you cannot recover.
Data distribution shifts frequently Codebooks were trained on a snapshot. Significant drift requires retraining, which is more disruptive than just re-indexing HNSW.
Quick scan · 2–4 min
Everything important, quickly.
4 min: phase split (offline codebooks vs per vector encoding) + the 256/byte alignment + compression math + quantization error + OPQ + production composition with IVF or HNSW.
Side-by-side
Aspect
Offline codebook training
Per-vector encoding
When it runs
Once per corpus (re-run on distribution shift)
On every insert
Input
100k-1M training vectors
One float32 vector
Cost per call
Minutes (k-means convergence)
Microseconds (32 * 256 distance ops)
Output
32 codebooks, 1 MB total
32-byte PQ code
Failure mode
Training set unrepresentative -> bad centroids
None at encoding; recall loss is from codebook quality
Real-world examples
Real products, models, and research that use this idea.
1Faiss IndexPQ and IndexIVFPQ both implement this exactly; pq_m is the constructor argument M and nbits defaults to 8.
2Milvus IVF_PQ index type exposes m (subspaces) and nbits as tuning knobs; OPQ rotation is included in the OPQ_PQ variant.
3Qdrant supports PQ as a quantization option for HNSW; the deployment is HNSW-PQ rather than pure PQ.
4Spotify's Annoy uses random projections rather than PQ, but Spotify's recommendation pipeline historically used PQ-encoded vectors for billion-scale similarity search.
5Pinecone's serverless tier uses PQ-style compression internally for cold storage tiers; the API hides the parameters.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy exactly 256 centroids? Why not 1024 or 64?
Sign in or go Pro to see the approach for this follow-up.
QHow does OPQ improve on vanilla PQ?
Sign in or go Pro to see the approach for this follow-up.
QHow is distance actually computed against PQ codes at search time?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Confusing the offline codebook training (run once per corpus, expensive) with per vector encoding (run on every insert, cheap). They are different phases with different costs and different inputs.