ANN Indexes

The intuition

Looking up the nearest needle in a haystack of vectors by checking every needle is honest — and too slow once the haystack is millions of items tall. Exact search is a linear scan: compare the query to each stored vector, keep the best k.

Approximate Nearest Neighbor (ANN) indexes are clever shortcuts. They organize vectors so the search can skip almost all of them and still usually find the true neighbors. You trade a little recall (fraction of the true top-k you actually get back) for large speed and cost wins.

Think of a city map with highways and side streets. HNSW is a multi-layer road network: hop long distances on sparse upper layers, then refine on dense local streets. IVF is zoning: only search the neighborhoods closest to your query. Quantization is packing lighter suitcases so more of the city fits in memory — then double-checking the shortlist with the full luggage when accuracy matters.

Why it exists

Exact nearest-neighbor search is O(N·d) per query. With SIMD that is often fine up to roughly a million vectors, but product corpora, ticket histories, and multi-tenant document stores blow past that.

Hard constraints:

1. Latency budgets are milliseconds. A chat or RAG request cannot spend hundreds of milliseconds scanning tens of millions of 1536-d vectors on the hot path.
2. RAM and disk are finite. Float32 vectors alone are dims × 4 × N bytes before any graph structure; multi-replica serving multiplies that.
3. Perfect recall is rarely the product metric. Users need good-enough top-k into a reranker or LLM; 95–99% recall@10 at 2 ms often beats 100% at 200 ms.
4. Indexes must match the metric. The structure encodes neighborhoods for cosine, L2, or IP — not an abstract "similarity."

Alternatives lose differently. Always brute force fails the latency and cost curve. Aggressive premature quantization without rescoring saves memory but can collapse recall to unusable levels. One-size vendor defaults are starting points; unmeasured, they leave free recall or free latency on the table.

The core idea

Exact nearest-neighbor search compares the query against every vector — O(N·d) per query. With SIMD that's fine up to roughly a million vectors, but it doesn't scale, so production systems use Approximate Nearest Neighbor (ANN) indexes: data structures that trade a little recall (fraction of the true top-k actually returned) for orders-of-magnitude speedups.

The dominant index is HNSW — Hierarchical Navigable Small World — a layered proximity graph. The top layers contain few nodes with long-range links; each layer down is denser. A query greedily hops toward its target in the sparse upper layers (coarse, fast), then refines in the dense bottom layer that contains every vector. Search is roughly O(log N), and recall in the 95–99% range is typical at single-digit-millisecond latency over millions of vectors. Its cost: the whole graph plus all vectors live in RAM, and memory is its main weakness.

The main alternative is IVF — inverted file index: k-means the corpus into nlist clusters, and at query time scan only the nprobe closest clusters. Simpler, smaller, faster to build, but recall drops when the true neighbor sits in an unprobed cluster.

Orthogonal to both is quantization — compressing vectors (float32 → int8, product codes, or single bits) to cut memory 4–32×+, usually combined with a rescoring pass on full-precision vectors to claw recall back. Every configuration is a point on the recall / latency / memory triangle: you can improve two at the expense of the third, and tuning means choosing where on that surface your product needs to sit.

How it actually works

HNSW search as a layered greedy walk (the dominant online default):

Exact (flat) search. FAISS IndexFlat, brute force. Recall = 100% by definition. Use it (a) below ~1M vectors when latency budget allows, (b) as ground truth for measuring your ANN index's recall. Also the fallback when correctness is non-negotiable.

HNSW mechanics. Two ingredients: skip lists (layered express lanes) and navigable small-world graphs (greedy routing works because of a mix of short and long links).

• Insert: each new vector draws its top layer from an exponentially decaying distribution (most nodes exist only at layer 0). Descending from the entry point, at each of its layers the algorithm collects efConstruction candidates and connects the node to its M best neighbors (layer 0 allows 2·M links).
• Search: start at the top-layer entry point, greedily move to the neighbor closest to the query until no improvement, drop a layer, repeat. At layer 0, maintain a best-candidate list of size efSearch and explore until it stabilizes; return top-k from it.

HNSW parameters and their effects:

efSearch is the runtime knob — the one you tune without rebuilding. Indicatively, pushing efSearch 100 → 400 can move recall ~90% → ~98% at ~2× the latency. Memory: vectors themselves (d × 4 bytes) plus graph links ≈ 2·M × 4 bytes per node at layer 0 (e.g. M=16 → ~128 bytes/vector of graph overhead; 1M × 768-d float32 ≈ 3 GB vectors + ~0.15 GB graph).

IVF mechanics. Train k-means → nlist centroids; each vector is stored in its nearest centroid's posting list. Query: find the nprobe nearest centroids, scan only those lists — scanning nprobe/nlist of the data.

• nlist: more, smaller clusters → less scanned per probe but higher chance the true neighbor is in an unprobed cluster. Rule of thumb: nlist ≈ 4·√N to 16·√N.
• nprobe: the recall/latency dial (1 = fastest, worst recall; nprobe = nlist ≡ brute force). Typical: 8–128.
• IVF requires a training step on representative data; heavy distribution drift (new domain, new embedding model) degrades the partition until retrained. Edge-of-cell queries are the classic recall failure — their true neighbors sit just across a cluster boundary.

Quantization.

Rescoring / refinement is the standard fix: search the compressed index for, say, top-100, then re-rank those with full-precision vectors (kept on disk or fetched lazily) to return top-10. Buys back most recall while keeping the RAM win.

Composites: IVF-PQ (scan compressed codes inside probed clusters — the classic billion-scale FAISS recipe), HNSW + int8/binary (what most managed vector DBs run), and disk-based graphs (DiskANN-style) that keep compressed vectors in RAM and full vectors + graph on NVMe for ~10–100× cheaper capacity at higher latency.

The triangle in one table (indicative, 1M × 768-d):

The flows

On the governed enterprise platform, online serving is typically HNSW (or vendor equivalent) over per-tenant or entitlement-filtered collections; full rebuilds run offline after embedding-model migrations, with recall@k checked against a flat baseline on a golden query sample before cutover.

A worked example

Corpus: 1M chunks × 768-d float32 from an internal wiki (~3 GB raw vectors).
Product need: p95 query latency under ~10 ms for the vector stage, recall@10 ≥ 95% into a hybrid+rerank pipeline.

Measuring recall correctly. Sample 1,000 real queries. For each, compute true top-10 with flat L2/IP (same metric as the index). Run ANN, compute fraction of true neighbors recovered. Plot recall vs efSearch (or nprobe). Pick the knee that meets the SLA.

Scale jump: 100M vectors × 1536-d → 1536 × 4 B × 100M ≈ 600 GB float32. Pure HNSW in RAM is off the table. Realistic sketch from the same playbook: Matryoshka-truncate to 512-d (≈200 GB), int8 (÷4), binary (÷32 → ~19 GB) with disk-backed rescoring, or IVF-PQ / DiskANN-style NVMe — always recall-validated against flat on sampled queries.

Common drill-downs

These are the questions a careful engineer asks one level down when choosing and tuning an index.

Why approximate search at all — when is exact fine? Brute force is O(N·d) per query; below ~1M vectors with SIMD it's often single-digit ms and perfectly fine (and it's your recall ground truth). Beyond that, latency and cost force ANN, which buys 10–1000× speed for a few points of recall.

Explain HNSW in 60 seconds. A multi-layer proximity graph: few nodes and long links on top, everything with short links at the bottom — a skip list crossed with a small-world graph. Search greedily descends: coarse hops in upper layers localize the region in ~log N steps, the bottom layer refines with a candidate beam of size efSearch. High recall at millisecond latency; cost is everything in RAM.

What do M, efConstruction, and efSearch each control? M: links per node — memory and base graph quality, fixed at build. efConstruction: build-time beam width — graph quality vs build time, fixed at build. efSearch: query-time beam width — the live recall/latency dial, must be ≥ k.

Your HNSW recall is 85% and you need 97%. What do you do? First raise efSearch (no rebuild) and measure the recall/latency curve. If the ceiling is too low, the graph is the problem: rebuild with higher M/efConstruction. Also check for tombstone buildup from deletes and for aggressive quantization without rescoring.

HNSW vs IVF — when each? HNSW: best recall/latency, incremental inserts, RAM-hungry — default for online serving. IVF(-PQ): cheaper memory, fast builds, natural for batch/offline or billion-scale with PQ compression, but needs training and nprobe tuning, and recall is more fragile.

How does product quantization actually compress a vector? Split the d-dim vector into m sub-vectors; k-means each sub-space to 256 centroids; store each sub-vector as its centroid's 1-byte ID. A 768-d float32 vector (3072 B) becomes m bytes (e.g. 96). Distances are approximated by summing precomputed query-to-centroid lookup tables.

What is binary quantization and why does it work at all? Keep only the sign of each dimension — 1 bit — and compare with Hamming distance (XOR + popcount, extremely fast). In high dimensions sign patterns preserve enough angular information, especially for models trained with quantization in mind; used as a coarse filter with float rescoring, it retains ~95%+ recall at 32× less memory.

What does rescoring/refinement mean in a quantized index? Over-fetch from the compressed index (top-100 for a top-10 need), then re-rank that shortlist with full-precision vectors. The compressed pass provides speed/memory; the rescore pass restores accuracy.

100M vectors, 1536-d, tight budget — sketch the index. 1536 × 4 B × 100M ≈ 600 GB float32 — pure HNSW in RAM is off the table. Options: Matryoshka-truncate to 512-d (≈200 GB), int8 (÷4), binary (÷32 → ~19 GB) with disk-backed rescoring, or IVF-PQ, or a DiskANN-style NVMe index. Realistic: truncation + scalar/binary quantization + rescoring, recall-validated against a flat baseline on sampled queries.

Production concerns

• Measure recall on your data — run flat search as ground truth over a sampled query set, compute recall@k of the ANN config, tune efSearch/nprobe to the knee of the recall-latency curve. Vendors' defaults are a starting point, not an answer. Evaluation mindset: evals and testing.
• Memory is the HNSW bill: RAM ≈ (d × 4 + ~2M × 4) bytes × N × replicas before quantization. This — not latency — is usually what forces quantization or disk-based indexes. See also scaling and operations.
• Deletes and churn: HNSW handles inserts incrementally but deletes are tombstoned — the graph keeps routing through dead nodes, degrading recall and latency until a rebuild/compaction. High-churn corpora need scheduled reindexing.
• IVF drift: centroids trained once go stale as data shifts; recall decays silently. Monitor and retrain.
• Filtered search interacts badly with ANN: post-filtering ANN results can return < k items when the filter is selective; graph traversal under heavy filters loses its shortcuts. See filtering and metadata for pre/post-filter strategies.
• Build time and cold start: HNSW with high efConstruction over 100M vectors is hours of CPU — plan index builds as offline jobs with blue/green swap, not inline mutations. Reliability patterns: reliability.
• Latency tail: p99 matters; graph search latency varies with query difficulty, and efSearch bounds the worst case better than the average. See latency.

Test yourself

Go deeper

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — Malkov & Yashunin — the HNSW paper.
• Hierarchical Navigable Small Worlds — Pinecone (FAISS series) — the best walkthrough of HNSW mechanics and parameter effects, with FAISS code.
• Product Quantization — Pinecone (FAISS series) — PQ mechanics and measured memory/recall tradeoffs.
• FAISS wiki — index catalog and the practical "which index should I use" guidance.
• HNSW for Vector Search Explained and Implemented with Faiss — James Briggs — widely-watched video building HNSW intuition then code.

Where this connects

• Vector database landscape — which stores expose HNSW/IVF/quantization and what they default to.
• Filtering and metadata — why selective filters interact badly with ANN recall.
• Hybrid search — ANN is the dense arm; BM25 is the other; fusion needs both candidate lists.
• Rerankers — ANN maximizes recall into a shortlist; the cross-encoder buys precision on that shortlist.