IVF (inverted file index)
Inverted File index: k-means clusters the vectors into cells; a query scans only the nprobe nearest cells. Cheap to build, easy to shard, pairs with PQ.
IVF sorts vectors into a few thousand buckets using k-means clustering, each bucket represented by its centre. At query time it finds the few bucket centres closest to the query and searches only the vectors inside those buckets. Searching more buckets (a higher nprobe) finds more true neighbours but takes longer.
A warehouse sorted into aisles by product type: to find something like a garden hose, you check the two or three nearest aisles, not the whole building.
Training centroids on a tiny or unrepresentative sample (the first 10k rows ingested, all from one tenant). Cells end up wildly unbalanced, a few lists hold most vectors, and both latency and recall get worse. Train on a uniform random sample of ≥ 30 × nlist vectors.
Training runs k-means on a sample (≥ 30–256 × nlist vectors) to get nlist centroids; each vector is assigned to its nearest centroid's list. A query computes distances to all nlist centroids, then scans nprobe lists. Cost ≈ nlist + nprobe × N/nlist distance computations, minimised around nlist ≈ √N; FAISS guidance is 4√N–16√N for large N (e.g. 65,536 cells at 100M–1B). pgvector IVFFlat recommends lists = rows/1000 up to 1M rows and √rows above, probes ≈ √lists; its default probes is 1, which gives poor recall. IVF's weak spot is the cluster boundary: a neighbour sitting just across a cell edge is missed unless nprobe covers that cell. Because centroids are trained once, distribution Drift (new product lines, a new language) unbalances lists and silently lowers recall until you retrain. Strengths over HNSW: 2–10× faster builds, lower memory, natural fit for Product quantization (PQ) (IVF65536,PQ64) and GPU search.
FAISS: nlist ≈ 4√N–16√N (IVF4096,Flat at 1M, IVF65536,PQ64 at 100M+), train on ≥ 30 × nlist random vectors, nprobe swept to hit recall@10 ≥ 0.95 after rescoring. pgvector IVFFlat: lists = rows/1000 (≤ 1M rows) else √rows, ivfflat.probes ≈ √lists, build only after the table is loaded.
E-commerce image embeddings, 120M × 512-d, FAISS IVF65536,PQ64 on one 256 GB node. nprobe=16: 0.9 ms/query on GPU, recall@10 0.82 (before rescoring). nprobe=128: 4 ms, recall@10 0.93. Rescoring the top 200 PQ candidates with float16 vectors read from SSD lifts recall@10 to 0.97 for +3 ms. Memory: 120M × (64 B code + 8 B id) ≈ 8.6 GB vs 246 GB raw float32.
Say when you'd pick it over HNSW: "IVF when I'm RAM-bound or at 100M+ vectors, usually as IVF-PQ with rescoring; HNSW when it fits in memory and I want the best recall per millisecond." Expect: what happens when the data drifts? Lists unbalance, recall drops at fixed nprobe — monitor list-size skew and retrain centroids on a schedule.
Numbers worth knowing
- Distance computations per query
- nlist + nprobe·N/nlistflat lists; minimised near nlist ≈ √N
- pgvector IVFFlat lists
- rows/1000 (≤1M rows), √rows abovepgvector README guidance; probes ≈ √lists
- Build speed vs HNSW
- 2–10× fastersame vectors, CPU, k-means on a sample
How to decide
| When | Do this |
|---|---|
| RAM-bound or > 100M vectors | IVF-PQ with rescoring of top 100–200. |
| Frequent inserts from a shifting distribution | Prefer HNSW; or schedule centroid retraining and monitor list skew. |
| GPU available and batch queries | FAISS GPU IVF — thousands of queries/s per card. |
Cost maths
120M × 512-d: float32 = 246 GB RAM (4 × 64 GB nodes ≈ $1,240/month at ~$0.43/hr each, illustrative Oct 2026) vs IVF-PQ64 ≈ 8.6 GB (one 16 GB node, ~$80/month) plus SSD for float16 rescoring vectors (123 GB ≈ $10/month of block storage at ~$0.08/GB-month). Price of the saving: ~3 ms rescoring and an offline recall gate.
Operating it
- Largest list > 10× the median list size — retrain centroids
- Recall@10 at fixed nprobe drops > 3 points month-over-month — drift; retrain
- nprobe needed for target recall > 5% of nlist — increase nlist or switch to HNSW
- List-size skew (max/median) — alert above 10
- Per-segment recall@10 vs exact — alert below 0.9 for any category or tenant
- Vector-stage p99 — alert above 15 ms
When it goes wrong
Product search recall on a newly launched furniture category was half that of established categories.
Per-category recall@20 dashboard (exact vs ANN on sampled queries): furniture 0.48, others 0.93.
IVF centroids were trained a year earlier, before furniture existed; all furniture vectors were crammed into a few distant cells and nprobe=32 rarely reached them.
Retrained centroids on a fresh uniform sample, rebuilt behind an Index alias, added monthly retraining and a list-skew alert.
Related terms
Sources
- Product Quantization for Nearest Neighbor Search — Jégou, Douze & Schmid, 2011paper
- Billion-scale similarity search with GPUs — Johnson, Douze & Jégou, 2017paper
- Faiss wiki: The index factory — Meta AI (FAISS), 2026docs
- pgvector: open-source vector similarity search for Postgres — pgvector project, 2026docs
Check yourself
Three questions. Every option is explained once you answer.