ANN Indexes

Approximate nearest-neighbour index structures (HNSW, IVF, PQ and other quantizers, DiskANN) that trade a little recall for orders-of-magnitude faster vector search, and how to tune them.

Contents

An approximate nearest-neighbour (ANN) index is a data structure that finds vectors close to a query without comparing it against every stored vector. It gives up a little accuracy (recall: the fraction of the true top-k it returns) in exchange for sublinear search time and, with compression, much less memory. Every vector database is built on one or more of these families: graphs (HNSW, Vamana/DiskANN), inverted files (IVF), and vector compression (scalar, product, binary, rotational quantization). The design space has four axes: speed, memory, accuracy, plus build time and I/O in some settings (Faiss).

Exact search first

A flat index compares the query with every vector: perfect recall at 4 × d bytes per vector (Faiss wiki). Non-exhaustive search starts to pay off above roughly 10k vectors (Faiss). Flat search is also the right answer when a filter leaves only a small subset, which is why Qdrant, Weaviate and Milvus fall back to it for very selective filters (Qdrant, Weaviate, Milvus).

HNSW (Hierarchical Navigable Small World)

Structure. A stack of proximity graphs over nested subsets of the data. Each inserted element draws a top layer floor(-ln(U) × mL), an exponentially decaying distribution with recommended mL = 1/ln(M), so upper layers are sparse long-range “express lanes”, like a skip list. Layer 0 contains every element (HNSW).

Search. Greedy descent from the top-layer entry point to layer 1, then a best-first search on layer 0 keeping a candidate list of size ef. Complexity scales roughly logarithmically (HNSW).

Insert. Search for the new element’s neighbours with list size efConstruction, then link up to M of them per layer (Mmax0 = 2M on layer 0). A heuristic prefers neighbours in diverse directions rather than just the closest ones, which helps on clustered data (HNSW).

flowchart TB
  Q["Query"] --> L2["Layer 2: few nodes<br/>greedy hop to closest"]
  L2 --> L1["Layer 1: more nodes<br/>greedy hop to closest"]
  L1 --> L0["Layer 0: all nodes<br/>best-first search, list size ef"]
  L0 --> R["Top-k from candidate list"]
ParameterEffectTypical defaults
M (links per node)Higher gives better recall at high dimension, more memory, slower build. The paper suggests 5 to 48pgvector 16; Qdrant 16
efConstructionBuild-time list; higher gives a better graph and a slower build. Aim for near-1 recall during buildpgvector 64; Qdrant 100
ef / ef_searchQuery-time list; the main recall/latency knob. Must be ≥ kpgvector 40; Qdrant defaults to ef_construct; Weaviate supports dynamic ef from the query limit

Sources: HNSW, pgvector, Qdrant, Weaviate.

Costs and limits. Graph links add about 60 to 450 bytes per element on top of the vectors (HNSW). Milvus estimates 1M 128-dim vectors at 640 MB, 128 MB of it graph (Milvus). Faiss’s HNSW supports incremental adds but not removal (Faiss). Builds are memory-hungry: pgvector warns when the graph outgrows maintenance_work_mem (pgvector). Graphs are best when memory is not a constraint, and build time becomes limiting beyond about 10M vectors on one node (Faiss).

IVF (inverted file)

Mechanism. k-means trains nlist centroids; each vector is stored in its nearest centroid’s list. A query scores the centroids and scans only the nprobe closest lists (Faiss).

Tuning. Distance computations are minimized near nlist ≈ sqrt(nprobe × N); Faiss suggests nlist of about C × sqrt(N) (Faiss, Faiss wiki). pgvector suggests lists = rows/1000 up to 1M rows and sqrt(rows) beyond, with probes starting at sqrt(lists). probes = lists is exact search (pgvector).

Trade-offs. IVF is cheaper to build and smaller than HNSW but slower at equal recall (pgvector). It needs representative data to train (build after loading). It handles large top-k and heavy filtering better than graphs (Milvus), and with compression it is the standard at very large scale (Faiss). Synthesis: clusters trained on old data drift as the distribution shifts, so periodically rebuild.

Compression: SQ, PQ, binary, RQ

MethodHowSize vs float32Notes
Scalar (SQ8)Each dimension to 8 bits using trained min/max4x smallerAbout 97% retrieval kept; about 99% with rescoring
Product (PQ)Split into M sub-vectors, replace each by a codebook centroid IDe.g. 768 floats to 128 bytes (about 24x)Needs training data; asymmetric distance via per-query lookup tables
Binary (BQ)Keep the sign bit, compare with Hamming distance32x smallerAbout 92 to 96% kept on robust models; some models collapse
Rotational (RQ, Weaviate)Random rotation, then 8, 4 or 1-bit quantizationabout 4x, 8x, close to 32x at high dimensionNo training; 8-bit reported at 98 to 99% recall, 4-bit about 94 to 95% before rescoring
Half precisionfloat162x smallerpgvector halfvec raises indexable dims to 4,000

Sources: Faiss, Faiss wiki, HF, Weaviate, pgvector.

PQ’s asymmetric distance computation keeps the query in full precision and sums precomputed sub-vector distances from lookup tables, so stored codes are never decompressed (Faiss). Additive quantizers (residual, LSQ) are more accurate per bit but cost more to train and encode (Faiss).

Compression composes with a structure: IVF-PQ, HNSW-PQ/SQ, and IVF-PQ plus a refiner. For 1M 128-dim vectors, IVF-PQ needs about 11 MB against 515 MB for IVF-FLAT (Milvus). Compression always pairs with refinement: over-fetch candidates with compressed distances, then re-score them with full vectors from RAM or flash (Faiss, HF, Weaviate). Matryoshka truncation is a related trick: shortlist with short prefixes, re-rank with full vectors (MRL).

DiskANN / Vamana: indexes on SSD

DiskANN serves a billion vectors from one machine with 64 GB of RAM and an SSD (DiskANN):

  • Vamana graph. A flat graph with max degree R, built in two passes with candidate list L and a pruning factor alpha. alpha > 1 keeps long-range edges, giving fewer hops. HNSW and NSG implicitly use alpha = 1.
  • Memory layout. PQ codes (e.g. 32 bytes per point) stay in RAM to steer traversal. Each point’s full vector and neighbour list sit together on SSD, so re-ranking with exact distances needs no extra reads.
  • BeamSearch. Each round fetches W frontier nodes in parallel; W of 2 to 8 balances latency and SSD load.
  • Results. On SIFT1B: over 5,000 QPS, under 3 ms mean latency, 95%+ 1-recall@1. Comparable-memory IVF-PQ methods plateaued near 50%.

Milvus recommends DiskANN when raw data lives on SSD and about a quarter of it fits in RAM, with disk IOPS as the bottleneck to watch (Milvus). Weaviate’s HFresh is another disk-based option: inspired by SPFresh, it keeps a compact centroid index in RAM and posting lists on disk, accepting latencies in the hundreds of milliseconds (preview in v1.36, GA in v1.38) (Weaviate).

Filtered ANN

Filters break the assumption that every visited node is a valid result. Post-filtering an HNSW result of ef_search = 40 with a 10%-selective filter leaves about 4 rows (pgvector). The fixes:

  • Keep scanning: pgvector iterative scans (pgvector).
  • Make the graph filter-aware: Qdrant’s per-value extra edges (Qdrant).
  • Skip non-matching nodes in distance computations and add multi-hop neighbour expansion: ACORN in Weaviate and Qdrant (Weaviate, Qdrant).
  • Switch to brute force on the matching subset when it is small. Milvus suggests graph indexes under 85% filtered out, IVF at 85 to 95%, and FLAT at the extreme (over 98% in its prose, over 95% in its decision matrix) (Milvus).

Choosing and tuning

SituationIndex
Under ~10k vectors, or a tiny filtered subsetFlat (exact)
Fits in RAM, low latency, high recall, small kHNSW
Very large, memory-bound, large k or heavy filtersIVF + PQ/SQ (+ refine)
Raw data on SSD, RAM about 1/4 of the dataDiskANN
Recall above 99% requiredFlat, ideally GPU

Sources: Faiss, Milvus.

Tuning loop (Synthesis, consistent with Faiss’s Pareto-sweep approach in Faiss):

  1. Compute exact top-k for a few hundred real queries with a flat index; this is ground truth.
  2. Sweep the query-time knob (ef_search or nprobe) and plot recall@k against p95 latency.
  3. Pick the cheapest point that meets the recall target (often 0.95+). Raise M or efConstruction only if ef alone cannot reach it.
  4. Re-measure with production filters and after bulk deletes and updates.
  5. Measure end-to-end answer quality too (LLM evaluation): ANN recall is rarely the weakest link next to chunking and reranking.

Sources

Suggest changes →