vector-index-hnsw-ivf-pq
verified2c82a383-f9f6-4348-b762-a4d249da505b
Design and tune approximate nearest neighbor (ANN) indexes — HNSW vs IVF vs product quantization, M/ef params, recall-cost tradeoffs, and warm-up.
Metadata
Skill file
# Vector Indexes: HNSW, IVF, and Product Quantization
Use when your semantic search / RAG retrieves from thousands to billions of
embeddings and a brute-force scan of all vectors is too slow — you need an
**approximate nearest neighbor (ANN)** index, and you must pick the right one and
tune it so recall stays high at acceptable latency and memory.
## The core tradeoff: recall vs cost
Every ANN method trades exactness for speed/memory. You almost never want exact
(brute-force) at scale. The decision is which approximate method and how much
recall you're willing to give up.
| method | memory | build time | query speed | recall | best for |
|--------|--------|-----------|-------------|--------|----------|
| flat / brute-force | full vectors | none | slow at scale | 1.0 (exact) | small sets, tuning baselines |
| IVF (inverted file) | full vectors + centroids | fast | fast | good (targetable) | moderate recall, lower mem, large corpus |
| HNSW (graph) | full vectors + graph edges | slow | fastest | highest | top recall, in-memory, single-node |
| + PQ (product quant.) | compressed vectors | medium | very fast | reduced | shrinking memory / disk at scale |
## HNSW — the high-recall default
HNSW builds a multi-layer proximity graph; searches walk it from the top layer
down. It has the best recall/speed for in-memory indexes but uses more memory
(graph edges) than IVF.
Parameters (names vary slightly by engine — Faiss, Milvus, Qdrant, pgvector…):
- **`M`** (max neighbors/edges per node): higher → better recall, more memory and
slower build/search. Recommended range ~[5, 100]; common default 16–30. Raise for
high dimensionality or when recall is critical; lower when memory/latency matter.
- **`efConstruction`** (build-time search width): how many candidates considered
when linking a new vector. Higher → higher-quality graph, slower build.
Set *before* adding vectors. Typical 100–400.
- **`efSearch`** (query-time search width): higher → higher recall per query, slower
query. *Can be raised at query time* — this is your live recall/latency dial.
Typical 50–500. Increase only if recall is low.
Faiss example:
```python
import faiss
index = faiss.IndexHNSWFlat(d, M=32) # d = embedding dim
index.hnsw.efConstruction = 200 # set before add()
index.add(vectors)
index.hnsw.efSearch = 100 # can change before each search
D, I = index.search(queries, k=10)
```
Milvus/Qdrant expose the same three concepts (`M`, `efConstruction`, `ef_search`).
## IVF — the memory-friendlier choice
IVF clusters the corpus into `nlist` centroids (Voronoi cells) and stores vectors in
each cell. A query probes the nearest `nprobe` cells.
- **`nlist`**: number of cells. More cells → faster build, but a vector's nearest
neighbor may be split across cells → lower recall unless you probe more.
- **`nprobe`**: number of cells searched per query. Higher → better recall,
slower query. This is the main recall dial.
- Tune `nprobe` up until recall targets are met, then stop — beyond that you pay
latency for no gain.
## Product Quantization (PQ) — shrinking vectors
PQ compresses each vector into a short code by splitting it into sub-vectors and
quantizing each (a codebook). Huge memory/disk savings (10–30×+), much faster scans,
but quantization noise **reduces recall**. Often combined as **IVF-PQ** or used as
a first-pass filter followed by exact re-score of top candidates. Use when memory
dominates the budget and you can afford a small recall hit (or re-scoring).
## Distance metric consistency
- **Cosine** needs L2-normalized vectors (or use inner-product on normalized).
- Don't mix: index with one metric and query with another → silently wrong rankings.
- Normalize once at ingest and again on the query vector.
## Tuning procedure (do this, don't guess)
1. Build a **labeled eval set**: queries each with known-relevant neighbors.
2. Start from engine defaults; measure **recall@k** and **p99 latency**.
3. If recall is low: raise `efSearch`/`nprobe` first (cheap, query-only).
4. If still low: raise `M`/`efConstruction` (rebuild) or `nlist`.
5. Stop at the lowest-cost combination meeting your recall floor — don't over-build.
6. Re-run evals after any index/embedding change.
## Pitfalls
- **Cold index**: freshly built / sparsely seeded indexes give poor recall; warm up
with real data and re-VACUUM/ANALYZE after bulk loads.
- **Forgetting score back**: always return similarity scores so callers can
threshold; top-k alone hides bad matches.
- **`efConstruction` set after building** → no effect. In Faiss it must be before
`add()`.
- **Embedding/model change** invalidates an index — must rebuild, not append.
- **PQ recall overconfidence**: an eval that used uncompressed vectors won't reflect
the compressed deployment. Re-eval with the real index.
- **Tuning on train set only**: the hold-out determines real recall; tuning to the
train set over-fits the index.
## Verify
- Recall@k on a held-out labeled set meets your target (e.g. ≥0.9) at your latency
budget.
- Memory footprint (full vs PQ) matches your hosting constraint.
- Queries with a real void of relevant results return low scores (thresholdable).
- After scale-up (many more vectors), re-measure — ANN recall changes with corpus
size and distribution.