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 walking past every shelf in order. It is exact, but far too slow once the library grows. PQ shrinks each book into a tiny summary card so the whole library fits in a smaller room. You lose a little detail but save a lot of 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 uses a lot of names (HNSW, IVF, Flat, PQ, OPQ, ScaNN, DiskANN). It is easy to come away believing they are all peer algorithms competing on the same axis. They are not. HNSW, IVF, Flat and PQ lie on three different axes of design.
Each name is an index family, a baseline, or a compression scheme. A clear taxonomy 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 up to M neighbors per upper layer and up to 2M on the base layer (M is 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 426GB.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Method | Type | Memory | Recall | Sweet spot |
|---|---|---|---|---|
| HNSW | Graph index | High (full vectors in RAM) | 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 serverless manages indexing internally, so users do not choose an ANN algorithm.
- 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.