Walk through how Product Quantization compresses a 1024-dim float32 vector down to 32 bytes, step by step.

Short answer·Medium·4.0 · 0·~3 min·Asked atMphasis Zilliz·Relevant atMicrosoft NVIDIA

Attempt it

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.

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.

Memory aid

Easy to grasp

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.

Key concepts

Vector databases Embeddings

Concept explanation~2 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Product Quantization is the workhorse compression scheme behind billion-scale ANN. The interview question is testing whether the candidate can cleanly separate the offline codebook-training phase from the per vector encoding phase, and whether they understand the byte-alignment trick that makes 256 centroids the canonical choice.

The Cartesian product trick

A naive vector quantizer for R^1024 would need an enormous codebook to cover the space (something like 256^32 entries to match PQ's effective resolution). PQ sidesteps that by factoring the 1024-dim space into a product of 32 lower-dim subspaces and quantizing each independently. Each subspace gets its own small codebook of 256 entries; the joint quantizer is the Cartesian product of the 32 per-subspace quantizers, with effective resolution 256^32 representable vectors at storage cost 32 * 256 entries.

The implicit assumption is that the data distribution factorizes (approximately) across the subspaces. For raw float vectors that assumption is often violated because embedding dims are correlated; OPQ learns a rotation to make the assumption hold better.

Why 256 centroids and 1 byte per subspace

Where the recall cost comes from

Situations where this technique stops working.

2–4 min · Everything important, quickly.

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 products, models, and research that use this idea.

Faiss IndexPQ and IndexIVFPQ both implement this exactly; pq_m is the constructor argument M and nbits defaults to 8.
Milvus IVF_PQ index type exposes m (subspaces) and nbits as tuning knobs; OPQ rotation is included in the OPQ_PQ variant.

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy exactly 256 centroids? Why not 1024 or 64?

256 = 2^8 fits in exactly one byte. Going higher (e.g. 65536 = 2^16, 2 bytes per subspace) doubles storage; going lower (e.g. 16 = 2^4, half a byte) requires bit-packing and loses recall. 256 is the sweet spot for byte-aligned storage.

2 more follow-ups an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases 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.

60 second bullets to scan on the way to the call.

Two phases: offline codebook training (once) and per vector encoding (every insert)
pq_m = number of subspaces; subspace size = total_dim / pq_m

Primary sources. Browse if you want the original framing.