Vector Indexes — HNSW, IVF & Product Quantization Tradeoffs
Brute-force top-k dies at millions of vectors. HNSW, IVF, and product quantization trade a measured amount of recall for latency and memory. Pick them the way you pick a B-tree versus a hash index: with a recall curve and a p99.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Ten million chunk vectors, a 50 ms retrieve budget
Prefer
An ANN index with a measured knee
HNSW when RAM is available and latency is the SLO. IVF, with PQ when memory binds. Publish Recall@10 against p99 and pick the knee.
- Build cost is paid up front or on a batch rebuild.
- Query knobs (efSearch, nprobe) move recall and latency together.
- A flat index remains the ground truth for the recall audit.
Alternative
ORDER BY distance, or ask the LLM to rerank the corpus
A full scan is honest and too slow at this size. A cross-encoder cannot score millions of chunks on the user path.
- Exact scan is the audit path, not the online path.
- Rerank is a shortlist tool. The next lesson places it.
- Blog defaults for M and nprobe are not your corpus.
Overview
At small n, brute force is the correct index. It is exact, it is easy to debug, and it is how you score recall for every approximate structure you might ship. At millions of vectors, a full scan misses the latency budget. Approximate nearest neighbor indexes skip most of the corpus on purpose.
You pick them the way you pick a B-tree versus a hash index: name the access pattern, then measure. Here the axes are recall at k, p99 latency, memory, and build cost.
The vectors themselves came from Embeddings & Similarity. This page does not re-teach cosine versus L2.
Index families
| Index | Idea | Latency | Memory | Build cost | Prefer when |
|---|---|---|---|---|---|
| Flat / brute force | Exact scan | Slow at scale | Full vectors | None | Under about 100k vectors, or a recall audit |
| HNSW | Multi-layer proximity graph | Excellent | High (graph plus vectors) | Medium to high | Low-latency online RAG |
| IVF | Cluster, then search nprobe lists | Good | Medium | Medium (k-means) | Large corpora you can tune |
| IVF plus PQ | IVF plus compressed codes | Good | Low | Higher | Memory-bound or huge scale |
| Disk graph (DiskANN-style) | Graph stored on SSD | Good if I/O behaves | RAM-light | High | Billion-scale when RAM will not hold the graph |
“Just SQL ORDER BY distance” fails the latency budget at this scale. “Let the LLM rerank the whole corpus” is not an index.
HNSW and IVF
Decisions
- 1
1. Query vector arrives
- next2. Which ANN family?
- ?
2. Which ANN family?
- graph3. HNSW enters top layer
- lists6. IVF picks nearest centroids
- 3
3. HNSW enters top layer
- next4. Greedy walk to neighbors
- 4
4. Greedy walk to neighbors
- next5. Descend layers for candidates
- 5
5. Descend layers for candidates
- next9. Return top-k
- 6
6. IVF picks nearest centroids
- next7. Scan nprobe inverted lists
- 7
7. Scan nprobe inverted lists
- next8. Score candidates in those lists
- 8
8. Score candidates in those lists
- next9. Return top-k
- 9
9. Return top-k
Lesson map
Vector Indexes — HNSW, IVF & Product Quantization Tradeoffs
Brute-force top-k dies at millions of vectors. HNSW, IVF, and product quantization trade a measured amount of recall for latency and memory. Pick them the way you pick a B-tree versus a hash index: with a recall curve and a p99.
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 q["1. Query vector arrives"] h["2. Which ANN family?"] g["3. HNSW enters top layer"] n["4. Greedy walk to neighbors"] q -->|1. Query vector arrives| h h -->|graph| g g -->|3. HNSW enters top layer| n
HNSW knobs. M is the graph degree. efConstruction is how wide the build search is. efSearch is how wide the query search is. Higher efSearch raises recall and latency. The graph plus the raw vectors sit in memory unless you move to a disk-based graph.
IVF knobs. nlist is the number of clusters. nprobe is how many inverted lists you scan. Raise nprobe for recall. The build is a clustering pass. Query cost tracks nprobe, not the full corpus, as long as the lists are balanced.
Product quantization. Split a vector into subvectors. Replace each subvector with the id of the nearest codebook entry. You store codes, not floats. Distance is approximate (asymmetric distance computation against the codes). Pair it with IVF when memory is the constraint. OPQ rotates the space first so the codebooks fit better. You pay recall, codebook tuning, and a slower path than uncompressed HNSW at small scale.
When not to use PQ. If the corpus is under about 1 to 2 million vectors and RAM is comfortable, uncompressed HNSW usually wins on recall and on engineering time. Reach for PQ when memory or cold storage dominates and you can afford a recall bake-off.
Some APIs offer Matryoshka or short prefixes of a long vector for a cheap first stage. Higher dimensions can help quality and always cost memory bandwidth. Treat a shorter prefix as another point on the same recall curve.
Toy IVF (run this)
Two centroids, four vectors, and a query at the origin. With nprobe 1 you only scan the near list. With nprobe 2 you scan both. This is the shape of the knob, not a k-means build.
ProblemBuild inverted lists from fixed centroids and search with nprobe 1 and 2.
ExpectedBoth probes return a and b. nprobe 2 scans the far list, and those vectors do not outrank the origin cluster.
Edge cases
- nprobe larger than the number of lists scans everything.
- An empty list contributes no candidates.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Candidate cap (run this)
efSearch keeps a wider pool than the k you return. This snippet only shows the cap: sort, keep ef, then keep k. A real HNSW walk fills that pool from the graph, it does not sort the whole corpus.
ProblemShow that the candidate cap is applied before the final top-k.
ExpectedThe best two scores inside a pool of three.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Filters, tenants, and rebuilds
Many vector databases can pre-filter or post-filter on metadata. A very selective pre-filter can starve an HNSW walk: the graph neighbors you would have followed were filtered out, so recall collapses in a way that efSearch only partly repairs. Payload indexes and per-tenant partitions often beat “search the world, then drop rows.” The interview line is: measure selectivity, and partition hot tenants.
Graph indexes dislike heavy delete churn. Tombstones leave holes. A practical pattern is a batch rebuild and an alias swap, not a million random deletes into a live HNSW. Incremental upserts are fine at modest rates. Say which regime you are in.
Flat indexes stay in production as:
- the ground-truth scorer for recall at k
- the online path for a tiny namespace
They are rarely the online path at tens of millions of vectors.
Ingest lag, failed deletes, and “the answer matches the PDF from last week” are failure modes, not index trivia. See RAG Failure Modes.
Operational questions you will actually get
- Recall versus latency. Publish Recall@10 versus p99 on your corpus. Pick the knee, and write down the knob (
efSearchornprobe) that produced it. - Memory versus SSD. HNSW in RAM is the simple online path. Disk-based graphs when the working set will not fit.
- Rebuild versus incremental. Heavy deletes want a batch rebuild and an atomic alias swap.
- Multi-tenant. Separate namespaces beat one giant graph with a desperate filter when QPS and selectivity are both high.
- PQ. Use it when memory binds and you have a recall budget you can measure. Skip it when RAM is fine and the corpus is still small.
Interview Q&A
Why approximate search at all?
Answer
Exact k-NN scans the corpus (or worse, if you are naive about dimensions). ANN gives sub-linear query time with a recall you can tune. Under about 100k vectors, exact scan is often simpler and fast enough.
HNSW versus IVF?
Answer
HNSW usually gives lower latency and higher recall at mid scale, and it spends RAM on the graph. IVF, especially with PQ, scales memory better and tunes recall with nprobe. Pick from a curve on your data, not from a vendor diagram.
What does product quantization buy?
Answer
Compressed codes instead of floats. Memory drops and more of the index stays hot in cache. Distances are approximate, so recall drops until you spend nprobe or a rerank on uncompressed vectors for the shortlist.
How do you set efSearch or nprobe?
Answer
Sweep them on a labeled query set. Plot recall at k against p99 latency. Ship the knee. Do not copy a blog default onto a different corpus and dimensionality.
Can the index go stale?
Answer
Yes. Updates and deletes need tombstones or a rebuild. Measure ingest lag and whether old ids were removed. That operational story is the failure-modes lesson.
What is a flat index for in production?
Answer
Ground-truth recall measurement, and tiny namespaces where the scan is cheap. It is the honest baseline the approximate index has to beat.
What does a selective metadata filter do to HNSW?
Answer
It can remove the neighbors the walk needed, so recall falls even though efSearch looks generous. Measure selectivity. Partition tenants or use a filter-aware index before you only “raise ef.”
When do you skip PQ?
Answer
When the corpus is under about 1 to 2 million vectors and RAM is comfortable. Uncompressed HNSW is simpler and usually recalls better. PQ is a memory decision with a recall bake-off attached.
Rebuild or delete in place?
Answer
Modest upserts can be incremental. Heavy delete churn punches holes in a graph. Batch-rebuild and swap an alias so readers never see a half-deleted graph.
Why not rerank every vector with a cross-encoder?
Answer
A cross-encoder scores a query-document pair with real attention. That is a shortlist tool (tens or hundreds of hits), not a scan of millions. The index exists so the reranker has something small to look at.
Pitfalls
One tenant is 0.2 percent of a shared HNSW index. After you add a pre-filter, Recall@10 on that tenant falls off a cliff while the global average still looks fine. What do you change first: efSearch, a partitioned index, or PQ?