Drag each answer to line up with its matching prompt
HNSW
Graph based; excellent recall, higher memory
IVF (Inverted File)
Compresses vectors; massive memory savings, some recall loss
Flat (brute force)
Exact search; only viable up to ~100k vectors
PQ (Product Quantization)
Partition based; trades recall for speed via probes
HNSW is a graph index, IVF partitions with k-means, Flat is exact brute force, and PQ is a compression layer that composes with IVF or HNSW.
Imagine four ways to organize a giant library so you can find similar books fast. **HNSW** is a friendship web: each book points to a few of its closest friends, and you walk friend to friend until you find what you want. **IVF** sorts every book into one of a few hundred labeled boxes; you only open the boxes most likely to contain matches. **Flat** is simply walking past every shelf in order. It is honest and exact but unbearably slow once the library grows. **PQ** is a trick that shrinks each book into a tiny summary card so the whole library fits in a smaller room; you lose a little detail but save enormous space. PQ is usually used with IVF or HNSW, not alone.
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.
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.
Vector search literature throws a lot of names around (HNSW, IVF, Flat, PQ, OPQ, ScaNN, DiskANN) and it is easy to come away believing they are all peer algorithms competing on the same axis. They are not. The four names in this question land on three different axes of design.
This question is interview shorthand for 'do you understand the taxonomy?' The match pairs format is testing that you can correctly classify each name as an index family, a baseline, or a compression scheme. A clear taxonomy is what lets you reason about which combination fits your workload.
HNSW: the graph family
HNSW stands for Hierarchical Navigable Small World. The index is a multi-layer graph. The bottom layer contains every vector; each higher layer is a sparser sample with longer range links. Each node stores M neighbors (typically 16 to 64).
Search starts at the top layer and greedily moves toward the query along edges. When no neighbor is closer than the current node, the search drops to the next layer down and continues. The hierarchy gives logarithmic average search depth, which translates to sub millisecond latency in practice.
Strengths. Highest recall per unit latency among ANN methods on corpora up to about 100M vectors. The graph adapts to data distribution naturally.
Weaknesses. The full vectors must be RAM resident because every distance computation during graph traversal uses the original vector. Memory cost scales with corpus size and embedding dimension; a 100M index in 1024 dimensions lands around 400GB.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Method | Type | Memory | Recall | Sweet spot |
|---|---|---|---|---|
| HNSW | Graph index | High (2-4x raw) | 0.99+ achievable | 1M to 100M vectors |
| IVF | Partition index | Low | 0.85-0.95 typical | 100M+, often with PQ |
| Flat | Brute force | Just the vectors | 1.0 (exact) | Under 100k vectors |
| PQ | Compression layer | 10-50x savings | Lower (quantization error) | Composed with IVF or HNSW |
Real products, models, and research that use this idea.
- Pinecone's managed service defaults to HNSW for indexes under 50M vectors and switches to compressed variants at higher scale.
- Milvus and Faiss both ship IVF-PQ as the canonical billion scale recipe, used inside LinkedIn, Salesforce, and many in house search stacks.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow would you decide nlist for an IVF index?
Rule of thumb is around sqrt(N) for the partition count, then tune nprobe against a held out recall target.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Treating PQ as a peer of HNSW and IVF. It is a compression scheme that composes with one of them, not a standalone index family.
60 second bullets to scan on the way to the call.
Why PQ is a compression scheme, not an index family
When Flat brute force is the correct choice
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.