ANN Indexes

The intuition

Exact nearest-neighbor search is honest: compare the query to every stored vector, keep the best k. That linear scan works until the corpus is millions of vectors and the budget is a few milliseconds.

Approximate Nearest Neighbor (ANN) indexes organize vectors so search skips almost everything and still usually finds the true neighbors. The price is recall — the fraction of the true top-k you get back. You buy speed and lower cost; some true neighbors will be missed.

One picture carries the rest of the page. Think of a city map. HNSW is a multi-layer road network: hop far on sparse upper layers, then refine on dense local streets. IVF is zoning: only search neighborhoods near the query. Quantization packs lighter suitcases so more of the city fits in RAM — then double-checks the shortlist with full luggage when accuracy matters.

Why it exists

Exact search is O(N·d) per query. With SIMD that is often fine up to roughly a million vectors. Product corpora and multi-tenant stores blow past that.

Four constraints force the trade:

1. Latency budgets are milliseconds. A RAG or search request cannot scan tens of millions of high-dimensional vectors on the hot path.
2. RAM is finite. Float32 alone is dims × 4 × N bytes before graph overhead; replicas multiply it.
3. Perfect recall is rarely the product metric. Users need a good-enough shortlist into a reranker or LLM. 95–99% recall@10 at a few milliseconds usually beats 100% at hundreds of milliseconds.
4. Indexes encode one metric. Neighborhoods are built for cosine, L2, or inner product. Build and query with the geometry the embedding model expects.

Always brute force fails the latency curve. Quantization without rescoring can collapse recall. Vendor defaults are starting points — unmeasured, they leave free recall or free latency on the table.

The core idea

Three ideas dominate, and they compose.

HNSW (Hierarchical Navigable Small World) is a layered proximity graph and the usual online default. Sparse upper layers have long-range links; layer 0 holds every vector. Search greedily hops in the upper layers, then refines with a candidate beam at the bottom — roughly O(log N), often 95–99% recall at single-digit milliseconds over millions of vectors. The bill is memory: graph plus vectors in RAM.

IVF (inverted file) runs k-means into nlist clusters and stores each vector in its nearest list. Queries scan only the nprobe closest lists. Simpler and cheaper to build than HNSW, natural with compression, but recall drops when the true neighbor sits in an unprobed cluster, and the partition needs training on representative data.

Quantization compresses vectors (float32 → int8, product codes, or bits) by 4–32×+. Alone it hurts ranking; with rescoring — over-fetch on compressed codes, re-rank with full-precision vectors — most recall returns while the RAM win stays.

The rest of the page is how these three move you around the triangle, and what breaks when you tune one corner alone.

How it actually works

HNSW search as a layered greedy walk:

Flat search (FAISS IndexFlat and cousins) is brute force: recall = 100%. Use it below ~1M vectors when latency allows, and always as ground truth when measuring ANN recall. Production may never serve flat; the lab still needs it.

HNSW. Skip-list layering (long hops on top) plus navigable small-world graphs (greedy routing with short and long links). On insert, each vector draws its top layer from an exponential distribution — most nodes exist only at layer 0 — then connects to M best neighbors among efConstruction candidates (layer 0 often allows 2·M links). On search, greedy-descend from the entry point; at layer 0 keep a beam of size efSearch and return top-k. If the true neighbor never enters the beam, recall drops (the red path above).

efSearch is the live dial — no rebuild. Illustratively, 100 → 400 can move recall ~90% → ~98% at ~2× latency; measure on your data. Memory ≈ d × 4 bytes (vectors) + ~2·M × 4 bytes/node (graph). Example: M=16 → ~128 B graph overhead/vector; 1M × 768-d float32 ≈ 3 GB vectors + ~0.15 GB graph.

IVF. Train k-means → nlist centroids; each vector joins its nearest posting list. Query: scan the nprobe nearest lists (~nprobe/nlist of the data). FAISS guidance: nlist roughly 4·√N to 16·√N. nprobe is the recall/latency dial (typical 8–128; nprobe = nlist ≡ brute force). Classic failure: edge-of-cell queries whose true neighbor sits just across a boundary. After a model swap or heavy drift, stale centroids route into the wrong lists until you retrain.

Quantization.

Rescoring: search compressed for top-100, re-rank with float32, return top-10. Compression buys speed/memory; rescore restores accuracy.

Composites. IVF-PQ scans compressed codes inside probed clusters — classic FAISS at large N. Managed DBs often run HNSW + int8/binary. DiskANN-style graphs keep codes in RAM and full vectors + graph on NVMe for roughly 10–100× cheaper capacity at higher latency when pure HNSW no longer fits.

Triangle (indicative, 1M × 768-d): Flat = 100% recall, ~50–200 ms, ~3 GB. HNSW (M=16, ef=100) ≈ 95–99%, 1–5 ms, ~3.2 GB. IVF (nprobe=16) ≈ 90–95%, 5–20 ms. IVF-PQ ≈ 70–90% before rescore, ~0.1–0.3 GB. HNSW + binary + rescore ≈ 95%+ at ~0.2 GB RAM + disk.

The flows

On the governed enterprise platform, online serving is typically HNSW over per-tenant or entitlement-filtered collections. Rebuilds run offline after embedding-model migrations, with recall@k vs flat on a golden sample before cutover.

A worked example

Corpus: 1M × 768-d float32 (~3 GB). Need: p95 vector latency under ~10 ms, recall@10 ≥ 95% into hybrid + rerank.

Start HNSW at M=16, efConstruction=200 (~3.2 GB with graph). Serve efSearch=100, k=50 (over-fetch for the reranker). Ballpark 1–5 ms and mid/high-90s recall@10 — only if you measure.

If recall@10 is 91%, raise efSearch to 200–400. Latency roughly doubles; recall often moves toward 97–99%. If the ceiling stays low, rebuild with higher M/efConstruction. If RAM is the constraint, int8 + rescore top-100 → top-50: ~4× less vector memory, ~1% tax before rescore.

Measure recall. Sample ~1,000 real queries. True top-10 via flat under the same metric. ANN recovery fraction = recall. Plot vs efSearch (or nprobe); pick the SLA knee. Without flat, "looks fine" means nothing.

Scale jump. 100M × 1536-d ≈ 600 GB float32 — pure HNSW in RAM is off the table. Truncate if Matryoshka, quantize with disk-backed rescoring, or IVF-PQ / DiskANN-style NVMe. Always validate vs flat.

Production concerns

Measure on your data. Sample real queries, recall@k vs flat, tune efSearch/nprobe to the curve knee. Defaults are not answers. See evals and testing.

Memory is usually the HNSW bill. RAM ≈ (d × 4 + ~2M × 4) × N × replicas. That forces quantization or disk indexes more often than average latency does. See scaling and operations.

Deletes and churn. Inserts are incremental; deletes are often tombstones until rebuild/compaction. High-churn corpora need scheduled reindexing.

IVF drift. Centroids go stale when data or the embedding model shifts. Retrain after model migrations the same way you re-embed.

Filtered search. Post-filters can return < k; heavy filters also blunt graph shortcuts. Pre-filter, filter-aware indexes, or measured over-fetch — filtering and metadata.

Build time. High efConstruction over large N is hours of CPU — offline blue/green, not hot-path mutation (reliability). Graph latency varies by query difficulty; p99 matters more than mean (latency).

Common drill-downs

When is exact still fine? Below ~1M vectors with SIMD, often single-digit ms — and still your only ground truth for recall@k.

HNSW vs IVF? HNSW: online default, best recall/latency, RAM-hungry, incremental inserts. IVF(-PQ): cheaper memory, fast builds, batch/billion-scale with compression; training + nprobe, fragile at cell edges.

efSearch maxed, recall stuck at 85%? Graph ceiling. Rebuild higher M/efConstruction; check tombstones, quantization without rescore, metric mismatch. More efSearch cannot invent missing edges.

How does PQ compress? Split into m sub-vectors; each → 1-byte centroid ID (256 per sub-space). 768-d float32 (3072 B) → m bytes. Distance ≈ sum of table lookups.

Why binary works? Sign bits + Hamming (XOR+popcount). High-d angular structure is enough for a coarse pass; float rescore often keeps ~95%+ recall at 32× less memory.

Test yourself

Go deeper

• Efficient and robust ANN with HNSW graphs — Malkov & Yashunin — the HNSW paper.
• Hierarchical Navigable Small Worlds — Pinecone — mechanics and parameters with FAISS code.
• Product Quantization — Pinecone — PQ memory/recall tradeoffs.
• Guidelines to choose an index — FAISS wiki — index selection and nlist rules of thumb.
• DiskANN — Microsoft Research — disk-based graph ANN at billion scale.
• HNSW Explained — James Briggs — video: intuition then FAISS code.

Where this connects

• Vector database landscape — which stores expose HNSW/IVF/quantization and their defaults.
• Filtering and metadata — selective filters vs ANN recall.
• Hybrid search — ANN is the dense arm; BM25 is the other.
• Rerankers — ANN maximizes shortlist recall; the cross-encoder buys precision.