Vector indexes

Problem

Similarity search turns retrieval into "find the k stored vectors closest to this query vector". Done exactly, that is a matrix-vector product over the whole collection: for 100,000,000 vectors of 768 float32 values it reads 307.2 GB of memory per query. A retrieval system behind a chat assistant or a recommender has to answer in milliseconds, for many queries at once, often on machines that cannot hold that much RAM.

Approximate nearest-neighbour (ANN) search gives up the guarantee of the exact top k. Its quality is measured by recall@k, the fraction of the true k nearest neighbours that the index returns. Every index design is a point in a three-way trade between recall, latency (how many vectors a query touches) and memory (how many bytes each vector costs), plus how long the index takes to build and whether it can accept new vectors.

Intuition

There are two ways to do less work per query, and production indexes combine them.

• Look at fewer vectors. Partition the space so a query only searches the regions near it (IVF: "check the post office districts nearest your address"), or link every vector to its neighbours so a query can walk toward its answer (HNSW: "ask for directions, hopping from person to person, with a few long-distance express routes on top").
• Make each vector cheaper. Replace a vector of floats with a short code that still lets you estimate distances (PQ: describe a face as "nose type 13, eyes type 5, mouth type 1" from small catalogues of each part).

Both introduce misses: the true neighbour may sit just across a partition boundary, the walk may stop at a local minimum, the codes may blur two vectors together. Each method has a knob that buys recall back with more work: nprobe, ef, or the number of candidates re-ranked with exact distances.

The query is closer to one centroid but its nearest neighbour lives in the next cell. IVF's misses are always of this kind, and nprobe is how many cells you search to catch them.

Mechanics

IVF: inverted lists over k-means cells

An inverted file index (IVF) trains k-means with nlist centroids on a sample of the data, the coarse quantizer, and stores each vector in the list of its nearest centroid. The cells are the Voronoi regions of the centroids. A query computes its distance to all nlist centroids, picks the nprobe nearest, and scans only those lists exactly. With balanced lists the work per query is about nlist + nprobe · n / nlist distances, minimized near nlist ≈ √n; production systems with a billion vectors use tens of thousands of lists or more.

Recall rises with nprobe and reaches the exact answer when nprobe = nlist. Lists are never perfectly balanced, since dense regions get bigger cells, so latency varies by query. New vectors can be added by assigning them to a cell, but if the data drifts the centroids go stale and the index needs retraining.

Product quantization

Jégou, Douze and Schmid split each d-dimensional vector into m sub-vectors of d/m dimensions and train a separate k-means codebook of k_s centroids for each slot. A vector is stored as m centroid ids, m · log₂ k_s bits: with the usual k_s = 256, one byte per slot. The m codebooks together describe k_s^m possible reconstructions (256⁸ ≈ 1.8 × 10¹⁹ with 8 bytes) while storing only m · k_s centroids.

Search uses asymmetric distance computation (ADC): the query stays exact. For each slot j, precompute a table of the squared distance from the query's j-th sub-vector to all k_s centroids. The estimated distance to any stored code is then m table lookups and additions:

d̂(q, x)² = Σ_j=1..m T_j[code_j(x)] , T_j[c] = ‖q^(j) − μ_j,c‖²

That is exactly the squared distance from q to x's reconstruction, so the error comes only from quantizing x. Because the estimates are biased and noisy, systems fetch the top R candidates by d̂ and re-rank them with exact distances, when the full vectors are available somewhere (on disk, say). IVF-PQ combines both ideas: PQ-encode the residual x − centroid within each cell, which has smaller spread than x itself, so the same bytes buy more accuracy. Optimized PQ rotates the space first to balance the variance across slots, and scalar quantization (int8 or 4-bit per value) is the simpler alternative when memory pressure is milder.

HNSW graphs

Malkov and Yashunin's hierarchical navigable small world graph links every vector to a few near neighbours and searches by greedy walking: from an entry point, repeatedly move to whichever neighbour is closest to the query. A flat graph needs many hops to cross the dataset, so HNSW stacks layers like a skip list. Each inserted vector draws a top level ℓ = ⌊−ln(U) · m_L⌋ with U uniform in (0, 1] and m_L = 1/ln M, so each layer has about 1/M as many nodes as the one below; it appears in every layer from ℓ down to 0.

• Search: start at the single entry point on the top layer, walk greedily to the closest node, drop to the next layer and continue from there. On layer 0 run a best-first search that keeps the ef closest nodes seen so far and stops when the nearest unexpanded candidate is farther than the worst of them; return the best k.
• Insert: search for the new vector itself with ef_construction candidates on each of its layers, connect it to up to M of them, and add the reverse links, pruning any neighbour list that grows past M (2M on layer 0).
• Neighbour selection heuristic: take candidates nearest first, and keep one only if it is closer to the new node than to every neighbour already kept. That skips redundant links into a cluster you already reach and keeps links that point in new directions, which is what lets greedy walks escape between clusters.

Search cost grows roughly logarithmically with n. HNSW gives the best recall for a given latency on most in-memory benchmarks, at the price of storing full vectors plus about 2M links per node, a build that does an ef_construction search per insert, and deletes that need tombstones or repair.

The upper layers are sparse, so a few long hops cover most of the distance; layer 0 is dense and only has to polish the answer. Greedy routing here reached the true neighbour, but on harder data it can stall, which is what a larger ef protects against.

Worked example

Benchmarks of real indexes draw exactly this plot, usually with queries per second instead of distance counts, and compare curves rather than single points: a method is better only if it is higher at the same cost.

Implementation

import numpy as np
from sklearn.cluster import KMeans

def build_ivf_pq(X, nlist=1024, m=16, ks=256, seed=0):
    coarse = KMeans(nlist, n_init=1, random_state=seed).fit(X)    # coarse quantizer
    cell = coarse.labels_
    R = X - coarse.cluster_centers_[cell]                         # residuals
    d = X.shape[1] // m
    books = [KMeans(ks, n_init=1, random_state=seed).fit(R[:, j*d:(j+1)*d]) for j in range(m)]
    codes = np.stack([b.labels_ for b in books], 1).astype(np.uint8)   # (n, m), 1 byte per slot
    lists = [np.flatnonzero(cell == c) for c in range(nlist)]
    return coarse, books, codes, lists

def search(q, coarse, books, codes, lists, k=10, nprobe=16):
    d = len(q) // len(books)
    near = np.argsort(((coarse.cluster_centers_ - q) ** 2).sum(1))[:nprobe]
    ids, est = [], []
    for c in near:
        r = q - coarse.cluster_centers_[c]                        # query residual for this cell
        T = np.stack([((b.cluster_centers_ - r[j*d:(j+1)*d]) ** 2).sum(1)
                      for j, b in enumerate(books)])              # ADC tables (m, ks)
        cand = lists[c]
        est.append(T[np.arange(len(books)), codes[cand]].sum(1))  # m lookups per vector
        ids.append(cand)
    ids, est = np.concatenate(ids), np.concatenate(est)
    top = np.argsort(est)[:k]                                     # re-rank here if raw vectors are kept
    return ids[top], est[top]

In practice you use a library: FAISS (IndexIVFFlat, IndexIVFPQ, IndexHNSWFlat, with nprobe and efSearch as the search knobs), hnswlib, ScaNN, or a vector database built on one of them. The sketch above is what they do, minus the SIMD, batching and memory layout that make it fast. Tune with a held-out query set and exact ground truth: fix the recall you need (0.9 or 0.95 at k = 10 is common), then pick the cheapest setting that reaches it.

• IVF: nlist around √n to 16√n, trained on 30 to 256 points per centroid; then raise nprobe until recall is met.
• PQ: m sets bytes per vector; d/m between 2 and 8 dimensions per slot works well; k_s = 256 keeps codes byte-aligned. Re-rank if you can afford to keep or fetch raw vectors.
• HNSW: M = 16 to 64 (higher for high-dimensional data and high recall), ef_construction 100 to 500 (build time for graph quality), then ef ≥ k raised until recall is met. ef can change per query; M and ef_construction cannot without a rebuild.

Tradeoffs

• Recall is not the end goal. Retrieval feeds a re-ranker or a language model; a recall drop from 0.99 to 0.95 often changes end-task quality very little, while halving latency or memory changes the bill a lot. Measure the end task.
• Filters break assumptions. "Nearest neighbours where language = fr" can leave a graph walk stranded among filtered-out nodes or empty most probed cells; systems pre-filter, post-filter with a larger k, or build filter-aware indexes.
• Distance choice matters. For cosine similarity, normalize vectors and use inner product or Euclidean distance, which then rank identically (see similarity search).
• Disk-based graphs (DiskANN and relatives) keep compressed vectors in RAM and the graph plus full vectors on SSD, for collections too big for HNSW in memory.

Connections

Clustering supplies IVF's cells and PQ's codebooks; similarity search defines the metrics and the exact baseline; nearest neighbours covers k-NN as a model and the tree indexes that work in low dimensions.

References

• Malkov and Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI 2018. arXiv:1603.09320
• Jégou, Douze and Schmid. Product Quantization for Nearest Neighbor Search. IEEE TPAMI 2011. doi:10.1109/TPAMI.2010.57
• Sivic and Zisserman. Video Google: A Text Retrieval Approach to Object Matching in Videos. ICCV 2003 (inverted files over k-means visual words).
• Ge, He, Ke and Sun. Optimized Product Quantization. IEEE TPAMI 2014.
• Johnson, Douze and Jégou. Billion-Scale Similarity Search with GPUs. 2017. arXiv:1702.08734
• Subramanya, Devvrit, Kadekodi, Krishnaswamy and Simhadri. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
• Aumüller, Bernhardsson and Faithfull. ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems 2020. arXiv:1807.05614
• scikit-learn 1.9.1: KMeans, MiniBatchKMeans, NearestNeighbors.