Every vector search is a nearest-neighbor problem: given a query vector, find the closest stored vectors. The naive way — compare against all of them — is exact but doesn't scale. So vector databases use approximate nearest neighbor (ANN) indexes that trade a little accuracy for a lot of speed. The three you'll actually encounter are flat, IVF, and HNSW, and the choice between them is a concrete trade-off across four dimensions: speed, accuracy (recall), memory, and build time. Understanding what each does lets you pick deliberately instead of accepting whatever default your database ships.
Flat: exact, simple, doesn't scale
A flat index does no approximation — it compares the query against every stored vector (brute force). That makes it perfectly accurate: it always returns the true nearest neighbors. No index to build, no accuracy loss, no parameters to tune.
The catch is cost: search time grows linearly with the number of vectors. At ten thousand vectors, flat is instant and you should probably just use it. At ten million, it's too slow for interactive search. Flat is the right choice for small collections and as a ground-truth baseline — you can measure another index's recall against flat's exact results.
IVF: divide the space into cells
IVF (inverted file index) clusters the vectors into cells during a training step. At query time, it finds the few cells nearest the query and searches only within those, skipping the rest. This turns "compare against everything" into "compare against a fraction," which is much faster.
- The knob: how many cells to probe (
nprobe). Probe more cells → higher recall, slower. Probe fewer → faster, lower recall. This is a direct, tunable speed/accuracy dial. - The trade: IVF needs a training step to learn the clusters, and its quality depends on the data distribution. It's generally memory-efficient and builds reasonably fast, which makes it attractive for very large datasets where memory matters. The risk is that the right answer sits just outside the probed cells and gets missed — the classic IVF recall failure.
HNSW: navigate a layered graph
HNSW (hierarchical navigable small world) builds a multi-layer graph. Upper layers are sparse (long-range links for fast navigation); lower layers are dense (fine-grained local links). A search starts at the top, greedily hops toward the query through progressively finer layers, and converges on the nearest neighbors quickly.
HNSW is the default in many vector databases (including pgvector) because it hits an excellent speed/accuracy point: very fast queries with high recall. The costs:
- Memory. The graph structure is memory-hungry — HNSW typically uses more RAM than IVF for the same data.
- Build time and parameters. Building the graph is slower, and it has tuning knobs (
Mfor connections per node,ef_constructionfor build quality,ef_searchfor query-time accuracy/speed) that trade memory and build time against recall.
Picking for your situation
| Flat | IVF | HNSW | |
|---|---|---|---|
| Accuracy | Exact | Tunable (nprobe) | High, tunable (ef) |
| Query speed | Slow at scale | Fast | Very fast |
| Memory | Low | Efficient | Higher |
| Build time | None | Moderate (training) | Slower |
| Best for | Small collections, ground truth | Very large, memory-constrained | The general default |
A practical rule of thumb:
- Small dataset (thousands to low tens of thousands): use flat. It's exact and fast enough; an ANN index is premature optimization.
- General case (up to many millions), want great speed and recall: use HNSW. It's the default for a reason and covers most workloads well. Tune
ef_searchif you need to trade a little recall for latency or vice versa. - Very large, memory is the binding constraint: consider IVF (or IVF combined with quantization). It trades some recall and tuning effort for lower memory footprint at massive scale.
The key mental model
There's no free lunch — every ANN index trades exactness for speed, and each does it differently. Flat spends compute to stay exact. IVF spends recall (via cell probing) to save memory and time. HNSW spends memory and build time to get the best speed/recall balance. For most teams the honest answer is "use HNSW, tune it if you must, and don't think about it further" — but knowing why means that when your dataset gets huge and memory bites, you'll recognize IVF as the tool for that specific corner rather than fighting HNSW's RAM appetite. Match the index to your actual constraint, and validate recall against a flat baseline so you know what accuracy your approximation is actually giving up.