IVF, PQ, and ScaNN — Partition, Quantize, Re-rank
IVF partitions space with k-means and scans only the nprobe cells nearest the query. PQ compresses each vector into a few bytes of codebook ids and scores them with table lookups. Together, with an exact re-rank, that is the classic recipe from hundreds of millions to billions of vectors. ScaNN spends its quantization error where inner-product rank actually moves.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What do nlist and nprobe trade?
Answer
nlist is the number of cells, often around sqrt(N) to 4 times sqrt(N). nprobe is how many of the closest cells you scan. Cost is about nlist centroid distances plus N times nprobe over nlist vector distances.
L2
How does ADC score a coded vector?
Answer
Once per query, build a table of distances from each query sub-vector to every centroid in that subspace. A database distance is then m table lookups. The query stays full precision. The database does not.
L3
Why is a re-rank mandatory for PQ?
Answer
Close vectors collide on the same code, and near-ties get reordered. PQ alone often lands at recall 0.3 to 0.7. Re-ranking the top 100 to 1000 with full vectors recovers 0.9 and up.
L4
Memory for 1 billion vectors, d = 768, IVF-PQ with m = 64?
Answer
Codes are 64 GB. Ids are about 8 GB. Centroids are noise next to that. About 72 GB versus about 3 TB of fp32. Full vectors for the re-rank live on SSD or object storage.
L5
int8 or PQ?
Answer
int8 if you can afford 25 percent of fp32: a small recall hit, and it composes with HNSW. PQ when you need 30 times compression or more, and you accept training plus a re-rank.
L6
What does ScaNN change?
Answer
Standard PQ minimizes reconstruction error in every direction. For inner product, error parallel to the vector moves the score more than orthogonal error. ScaNN penalizes the parallel component, then re-orders with exact dots.
L7
Why does IVF recall drop over months with no deploy?
Answer
Data drift. New content lands in a few cells, lists grow unevenly, and the centroids no longer match the corpus. Retrain on a fresh sample, rebuild, and alert on list-size skew and on a frozen query set.
Failure modes
Boundary miss
The true neighbor sits just across a cell wall. nprobe = 1 recall in the sandbox is about 0.55. Raising nprobe buys it back.
List skew
k-means cells are not balanced. Hot cells dominate p99. Centroids trained on old data make it worse.
PQ without a re-rank
Codes that collide cannot be ordered. No nprobe setting fixes a tie the code erased.
Quantizing the query too
SDC is cheaper and less accurate. ADC keeps the query exact. Use ADC unless you have measured otherwise.
Misconceptions
More nprobe always means you built a better index.
nprobe is the query dial. If recall plateaus early, nlist, the training sample, or the code size is the problem.
PQ reconstructs the vector well enough to skip the original.
The code is for scanning. The original, or a higher-precision copy, still has to re-rank.
Binary quantization is a drop-in for fp32.
One bit per dimension loses a lot alone. It works with oversampling, about 3 to 10 times k, and a higher-precision re-score, especially in high dimensions.
Interviewer traps
Describing HNSW layers when the question was IVF-PQ bytes.
Give the code size, the id size, and where the full vectors live. Mention HNSW only as the RAM-resident alternative.
Calling ScaNN a different architecture.
It is still partition, quantize, re-rank. The loss function is what changed.
Design scenario
Same prompt for every reader.
Requirements
Recall at 10 at least 0.9 after re-rank, and a retrain plan when the corpus drifts.
Traffic / scale
1 billion vectors, online queries, batch inserts between centroid rebuilds.
Latency
The scan is table lookups over nprobe lists. The re-rank fetches a few hundred full vectors.
Consistency
Codes and centroids come from one training snapshot. Mixing a new model's vectors into old codes is a different failure, owned by the production page.
Availability
One large node can hold the codes. The SSD re-rank path has to survive a cold cache.
Failure assumptions
- A true neighbor lies on a cell boundary.
- A few lists grow to many times the median.
- Someone turns off the re-rank to save a disk read.
Constraints
- State bytes before QPS.
- Name nlist, nprobe, m, and the re-rank depth as separate knobs.
Prompt
Fit 1 billion 768-d vectors into RAM for CPU search, with a re-rank path to full vectors on SSD.
API
What does a query return before the re-rank, and what does it return after?
Data
What is stored in RAM, and what stays on SSD?
Architecture
When do you retrain centroids, and what metric tells you it is time?
Where the bytes go
Prefer
Partition, quantize, then re-rank
Cut the candidate set with centroids, score codes with table lookups, then rescore a short list with full vectors.
- IVF-PQ at m = 96 is about 100 bytes in RAM plus full vectors elsewhere.
- A re-rank of a few hundred hits is what turns PQ recall from weak to usable.
- ScaNN keeps the same shape and changes the loss so inner-product order survives.
Alternative
Full vectors in RAM
Flat and HNSW fp32 keep about 3 KB per 768-d vector. That is the right bill when N fits and you want the recall curve of a graph.
- int8 HNSW is the modern compromise, about a quarter of the vector bytes.
- PQ without a re-rank looks cheap and returns the wrong neighbors.
- GPU batch search likes IVF-Flat because the vectors are still plain.
One IVF-PQ query
Training happens once. The query path is centroids, codes, then a short exact list.
- 1
Score the coarse centroids
Compare the query to all nlist centroids and keep the nprobe closest lists. - 2
Build ADC tables
For each probed list, distances from the query's sub-vectors to the codebook centroids. The database vectors stay as bytes. - 3
Scan codes
Approximate distance is m lookups and adds. Keep a few hundred winners. - 4
Re-rank with full vectors
Fetch the original vectors from RAM, SSD, or object storage and return the true top k.
Overview
Graphs are not the only way to make vector search sub-linear. IVF (inverted file) partitions space with k-means and scans only the nprobe cells nearest the query. PQ (product quantization) compresses each vector into a few bytes of codebook ids and computes approximate distances with table lookups. Together, IVF-PQ is the classic recipe for hundreds of millions to billions of vectors.
ScaNN refines the recipe. Anisotropic quantization spends precision where it matters for inner-product ranking, and an exact re-scoring stage puts the top of the list back in order. The universal pattern is partition, quantize, re-rank.
How those vectors were trained is Embeddings & Similarity — Dense Vectors, Metrics & Chunking Basics. Which engine you run them in, when the choice is OpenSearch versus Elasticsearch versus Postgres full text, stays on Ecosystem — OpenSearch vs Elasticsearch vs Solr (and when not to use a search engine).
IVF: partition the space
Flow
- 1
1. Sample vectors
- next2. k-means, nlist centroids
- 2
2. k-means, nlist centroids
- next3. Assign each vector
- 3
3. Assign each vector
- next4. Inverted lists
- 4
4. Inverted lists
- next5. Query vector
- next8. Scan those lists
- 5
5. Query vector
- next6. Score all centroids
- 6
6. Score all centroids
- next7. Pick nprobe lists
- 7
7. Pick nprobe lists
- next8. Scan those lists
- 8
8. Scan those lists
- next9. Return top k
- 9
9. Return top k
Lesson map
IVF, PQ, and ScaNN — Partition, Quantize, Re-rank
IVF partitions space with k-means and scans only the nprobe cells nearest the query. PQ compresses each vector into a few bytes of codebook ids and scores them with table lookups. Together, with an exact re-rank, that is the classic recipe from hundreds of millions to billions of vectors. ScaNN spends its quantization error where inner-product rank actually moves.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB sample["1. Sample vectors"] km["2. k-means, nlist centroids"] assign["3. Assign each vector"] lists["4. Inverted lists"] sample -->|1. Sample vectors| km km -->|2. k-means, nlist centroids| assign assign -->|3. Assign each vector| lists
- nlist, the number of cells. A rule of thumb is about sqrt(N) to 4 times sqrt(N). Faiss guidance uses a few thousand to tens of thousands of lists from 1 million to 1 billion vectors.
- nprobe is the recall dial. Cost is about nlist centroid distances plus N times nprobe / nlist vector distances.
- Boundary misses. A true neighbor sitting just across a cell wall is invisible unless that cell is probed. The sandbox shows recall about 0.55 at nprobe 1, about 0.95 at 4, and about 0.99 at 8.
- Skew. k-means cells are not balanced. Hot cells make some queries much slower, and centroids trained on old data drift as the corpus changes. Monitor the list-size distribution and retrain.
- Strength. The build is a k-means on a sample. An insert is an O(nlist) assignment. It maps well to GPUs, and it composes with compression.
PQ: compress the vectors
Split a d-dimensional vector into m sub-vectors of d/m dimensions. For each subspace, train a codebook of ks centroids, usually 256, so one byte per sub-vector. A vector becomes m bytes of codebook ids.
| Setting | fp32 bytes | PQ bytes | Ratio |
|---|---|---|---|
| d = 768, m = 96, ks = 256 | 3072 | 96 | 32 times |
| d = 768, m = 48, ks = 256 | 3072 | 48 | 64 times |
| d = 128, m = 16, ks = 256 | 512 | 16 | 32 times |
ADC
- For the query, compute a table: for each subspace and each centroid, the distance from the query's sub-vector to that centroid. That is m times ks small distances, once per query.
- The approximate distance to any database vector is the sum of m table lookups using its codes.
- No floats from the database vector are touched, so the scan is cache-friendly. Faiss fast-scan variants pack 4-bit codes into registers.
ADC (asymmetric) keeps the query exact. SDC (symmetric) also quantizes the query and is less accurate. Practically everyone uses ADC.
Why PQ needs a re-rank
Quantization error means close vectors can share a code, and near-ties get reordered. PQ alone often lands at recall 0.3 to 0.7. Re-ranking the top 100 to 1000 approximate hits with full vectors, from RAM, SSD, or a separate store, recovers 0.9 and above. The sandbox shows 8-byte codes going from about 0.44 alone to 1.00 with a re-rank of 200.
Two refinements sit on top of plain PQ:
- Residuals. IVF-PQ encodes the vector minus its cell centroid. Residuals have smaller spread and quantize better.
- OPQ. A learned rotation spreads information evenly across subspaces before PQ.
Scalar and binary quantization
| Method | Bytes per dim | Memory versus fp32 | Typical recall impact | Notes |
|---|---|---|---|---|
| fp16 / bf16 | 2 | 50 percent | Negligible | Easy win. pgvector halfvec |
| int8 scalar | 1 | 25 percent | Small, often under 1 to 2 points | Lucene, Elasticsearch, OpenSearch, Qdrant, Faiss |
| int4 scalar | 0.5 | 12.5 percent | Noticeable. Re-rank advised | An Elasticsearch option |
| Binary, 1 bit per dim | 0.125 | about 3 percent | Large alone. Good with oversampling and re-score | Elasticsearch BBQ, Qdrant binary quantization. Best on high-d models |
| PQ | m / d | about 1 to 6 percent | Large alone. Re-rank needed | Faiss, Milvus, the in-memory part of DiskANN |
ScaNN
Standard PQ minimizes reconstruction error equally in all directions. For maximum inner product search, error parallel to the data vector changes scores much more than error orthogonal to it. ScaNN's anisotropic quantization penalizes the parallel component, so the top results keep their order.
The pipeline is still a partition (a tree of k-means leaves), a score with quantized codes, then an exact dot product on the top candidates. On ANN-Benchmarks style sets it posts excellent recall per QPS on CPU. Use it when you are inner-product heavy, CPU bound, and on a stack that already ships it, or when you are comfortable integrating the library.
Same budget, different index
| Index | Memory per vector, d = 768 | Build | Recall at modest compute | Best fit |
|---|---|---|---|---|
| Flat | 3 KB | none | 1.0 | Small or filtered |
| IVF-Flat | 3 KB | k-means | 0.95 and up with enough nprobe | GPU, batch, simple ops |
| IVF-PQ, m = 96, plus re-rank | about 100 bytes in RAM, full vectors elsewhere | k-means plus PQ | 0.9 and up | 100 million to 1 billion and beyond |
| HNSW fp32 | about 3.2 KB | slow | 0.95 to 0.99 | Low-latency, RAM-resident |
| HNSW int8 | about 0.9 KB | slow | 0.95 and up | Default modern compromise |
| ScaNN | compressed plus a re-order buffer | training | very high per CPU | Maximum inner product on CPU |
Sandbox: flat versus IVF, then PQ
Flat scans everything. IVF stores each vector on the list of its nearest centroid and scans nprobe lists. Misses happen across a cell wall. PQ replaces sub-vectors with codebook ids. Distances come from lookup tables. A short exact re-rank restores most of the lost recall.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Seeded reading: list sizes run from empty to a fat max, which is normal. nprobe 1 recalls about 0.55. nprobe 4 recalls about 0.95 while scanning about 12 percent of N. At 100 million vectors and 16k lists that scanned fraction is far smaller. PQ at 4 bytes per vector (here 32 times smaller than fp32) is weak alone. At 8 bytes, a re-rank of 200 restores recall 1.00 on this toy. Pick code size and re-rank depth together.
Sandbox: ADC, SDC, int8, and a collision
PQ stores a short code. ADC keeps the query exact. SDC quantizes the query too. Scalar int8 rounds each dimension and compresses far less, with far less error. Two vectors that share a code cannot be ordered until a re-rank sees the originals.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Vectors 0 and 2 share code 1,1. ADC reports 0.40 for both. Exact distances are about 0.10 and 0.63. No amount of nprobe can order them. Only a re-rank with the original vectors can. The memory line for 100 million by 768 is about 307 GB fp32, 154 GB fp16, 77 GB int8, and 9.6 GB for either PQ at m = 96 or 1-bit binary.
Interview Q&A
Walk through IVF-PQ search.
Answer
Score the query against nlist coarse centroids, pick nprobe lists, compute residual ADC tables for each probed list, scan PQ codes with table lookups, keep the top few hundred, then re-rank those with full vectors and return the top k.
Memory for 1 billion vectors, d = 768, IVF-PQ with m = 64?
Answer
Codes: 1 billion times 64 bytes is 64 GB. Ids at 8 bytes are 8 GB. Centroids are negligible. About 72 GB, so one large node holds the codes, versus about 3 TB for fp32. The full vectors for re-ranking live on SSD or object storage and are fetched for the top few hundred per query.
Why does IVF recall drop over time with no code change?
Answer
Data drift. New content lands in a few cells, lists grow unevenly, and the centroids no longer reflect the distribution. Retrain on a fresh sample and rebuild. Alert on list-size skew and on recall against a fixed query set.
Scalar int8 or PQ?
Answer
int8 if you can afford 25 percent of fp32. The recall loss is small, the math is simple, and it works with HNSW. PQ when you need 30 times compression or more to fit at all, accepting a re-rank stage and a training job.
What is binary quantization, and when does it work?
Answer
One bit per dimension, the sign. Hamming distance via popcount, 32 times smaller than fp32. It loses a lot alone. It works with oversampling, fetching about 3 to 10 times k, and re-scoring with higher-precision vectors, especially for high-dimensional models.
What does ScaNN do differently from Faiss IVF-PQ?
Answer
It uses anisotropic quantization that minimizes error in the direction that changes inner-product rankings, plus a tree partition and exact re-ordering. Same partition, quantize, re-rank shape, with a loss aligned to ranking.
How do you pick nlist?
Answer
Start near sqrt(N) to 4 times sqrt(N). Make sure each list holds at least a few hundred vectors. Train on about 30 to 256 times nlist samples, then sweep nprobe for the recall target. Too few lists means big scans. Too many means more centroid scoring and more boundary misses.
ADC or SDC?
Answer
ADC. The query stays full precision and the database is coded, so the error is only on one side. SDC quantizes the query too. The tables can be precomputed, and the distances get worse. Use SDC only if you have measured that the cheaper tables still hit the recall target.
Pitfalls
Write bytes for fp32, int8, and IVF-PQ at m = 64, including 8-byte ids. Say where the re-rank reads from. Then name the alert that fires when one list is ten times the median.
Go Deeper
- Product Quantization for Nearest Neighbor Search
- Faiss wiki — The index factory
- Billion-scale similarity search with GPUs
- Anisotropic vector quantization (ScaNN)
- Pinecone — Product quantization
- Faiss wiki — Guidelines to choose an index
- Next: Filtered and Hybrid Search — Metadata, BM25, and Broken Recall