Vector Indexes: The Recall-vs-Latency Trade-off of HNSW and IVF

Semantic retrieval rests on a simple idea: encode text as a vector so that meaning becomes geometry, and finding relevant documents becomes finding nearby points. The trouble is that finding the truly nearest points among hundreds of millions of vectors, exactly, means comparing the query against every one of them, and that linear scan is far too slow to sit in the path of a live request. Approximate nearest-neighbour search resolves this by giving up exactness on purpose: it returns the true neighbours most of the time, and in exchange it runs orders of magnitude faster. How often it is right is called recall, how long it takes is latency, and every vector index is fundamentally a machine for trading one against the other. Understanding that trade, and the two index families that dominate it, is the whole game.

The problem and its exact cost

State the task precisely. Given a database of N vectors in d dimensions and a query vector, return the k database vectors closest to the query under a distance such as Euclidean distance or cosine similarity. This is the k-nearest-neighbour problem, and the embeddings themselves come from models such as the transformer (Vaswani et al., 2017), which map text to vectors whose geometric proximity approximates semantic similarity.

The exact solution is a brute-force scan: compute the distance from the query to all N vectors and keep the smallest k. Each distance is order d work, so a single query costs order N times d operations. At a hundred million vectors of a thousand dimensions that is a hundred billion multiply-adds per query, which no interactive service can afford. The exactness is not the problem; the linear dependence on N is.

Approximate nearest-neighbour search breaks that linear dependence by not looking at every vector. It builds an index once, offline, that lets a query examine only a small, cleverly chosen subset of the database, at the price of occasionally missing a true neighbour.

Recall and latency, defined

The correctness metric is recall at k. Let the true set of k nearest neighbours be known (computed by exact search on a sample). Recall at k is the fraction of that true set that the approximate index actually returns. A recall of 0.95 means that, on average, nineteen of every twenty true neighbours are found; the twentieth is replaced by something slightly farther away. Recall is a property of the whole query distribution, so it is always reported as an average over a representative query set.

The cost metric is latency: the wall-clock time to answer one query, which in these indexes is dominated by the number of database vectors whose distance the search actually computes. Call that the number of candidates examined; latency is essentially that count times the per-distance cost d, plus index-traversal overhead.

The central fact is that these two move together. Every index has a parameter that, when increased, makes the search examine more candidates: recall rises toward one, and latency rises with it. You are never choosing recall or latency in isolation; you are choosing a point on a curve that relates them.

IVF: partition, then probe a few cells

The inverted file index reduces candidates by geography. Offline, cluster the database vectors into a set of cells, typically by running k-means to find a number of centroids; each vector is assigned to its nearest centroid, forming an inverted list per cell. At query time, compute the distance from the query to the centroids, pick the few nearest cells, and scan only the vectors in those cells. The number of cells you probe is the knob, conventionally called n_probe.

The cost model is direct. With the database split into roughly equal cells, each cell holds about N over the number-of-cells vectors, so probing n_probe cells examines about n_probe times that many candidates. Latency therefore scales linearly with n_probe. Recall rises with n_probe too, because a true neighbour is found only if its cell is among those probed; probe more cells and you are less likely to miss the cell a neighbour lives in.

The failure this exposes is the boundary problem: a true neighbour that happens to sit just across a cell boundary from the query is missed unless you probe its neighbouring cell. That is exactly why recall climbs with n_probe, and why IVF alone rarely reaches the very highest recalls without probing so many cells that its speed advantage erodes.

HNSW: walk a small-world graph

The hierarchical navigable small-world graph (Malkov & Yashunin, 2018) reduces candidates by navigation instead of partition. It builds a proximity graph in which each vector is a node linked to a bounded number of near neighbours, and it stacks several such graphs in layers: a sparse top layer for long jumps and progressively denser layers below, ending in a bottom layer that contains every vector. A search enters at the top, greedily walks toward the query until it can get no closer, drops a layer, and repeats.

The layered structure is what gives the method its speed. The long-range links in the upper layers let the search cross the space in a few hops, so the expected number of steps grows only logarithmically with the database size, echoing the small-world property that any two nodes are connected by a short path. The knob is the search beam width, conventionally efSearch: the number of best candidates the greedy walk keeps as it explores. A wider beam explores more of the graph, finds more true neighbours, and costs proportionally more.

So HNSW and IVF arrive at the same trade from opposite directions: IVF widens the search by probing more cells, HNSW by keeping a wider beam. Both dials increase candidates examined, and both push recall and latency up together.

The Pareto frontier

Sweep the knob of any one index and you trace a curve of recall against latency. That curve is a Pareto frontier: for a given index and dataset, it is the best recall achievable at each latency, and no setting lets you beat it on both axes at once. Comparing indexes means comparing frontiers, not single points; one index dominates another only if its whole curve sits above and to the left.

The frontier is concave and saturating. Early on, spending a little more latency buys a lot of recall, because the first extra candidates examined are the ones most likely to contain missed neighbours. As recall approaches one, the curve flattens: the remaining misses are the genuinely hard cases, neighbours hidden across a cell boundary or behind a poor graph link, and dislodging each one costs a disproportionate number of extra candidates. The last few points of recall are the most expensive latency you will ever buy.

This shape is why the right question is never 'what is the fastest index' or 'what is the most accurate' but 'what recall does the application actually need, and what is the cheapest latency that reaches it'. A retrieval-augmented system that tolerates a 95 percent recall can run many times faster than one that insists on 99.9.

Memory is the third axis

Recall and latency are the visible trade, but memory is a silent third axis that often decides the choice. HNSW stores an explicit graph: every node keeps links to a bounded number of neighbours, so the index adds memory proportional to that degree times the number of vectors, on top of the vectors themselves. That overhead is what buys its excellent frontier, and it is why HNSW is memory-hungry at billion-vector scale.

IVF stores only cell assignments and centroids, so its index overhead is small, but it is frequently paired with vector compression to shrink the vectors themselves. Product quantization replaces each vector with a compact code, cutting memory by an order of magnitude at the cost of approximate distances. This is the same lossy-compression trade studied for model weights, where post-training quantization such as AWQ (Lin et al., 2023) trades a controlled numerical error for a large memory saving; here the error lands in the distance estimates and therefore in recall, an equivalence I draw as my own synthesis rather than a claim from that work.

The practical consequence is that the index decision is three-dimensional. In systems where memory is plentiful, HNSW usually offers the best recall-latency frontier; where memory is the binding constraint, IVF with compression trades some frontier quality for a much smaller footprint, and the serving stack (Kwon et al., 2023, on memory-efficient LLM serving) has to budget for whichever index it chooses alongside the model.

When it breaks

First, the saturation wall. Because the frontier flattens near recall one, any requirement for near-perfect recall forces latencies that approach the exact scan you were trying to avoid. If an application genuinely needs every true neighbour, approximate search is the wrong tool and exact or hybrid methods should be considered instead.

Second, dimensionality. As d grows, distances between points concentrate and the geometric signal that both partitioning and graph navigation rely on weakens, the familiar curse of dimensionality. Very high-dimensional embeddings make cells less discriminative and graph links less informative, pushing every index's frontier downward; dimensionality reduction before indexing is often the real fix.

Third, distribution shift and structure. The index is built from the database distribution, so queries that fall in sparse regions, or a database with strong hubness where a few vectors are everyone's neighbour, degrade recall unpredictably. And the frontier is measured on a query sample: if production queries differ from that sample, the recall you validated is not the recall you get. The defensive posture is to measure recall continuously on live-like queries and to choose the knob from the application's true recall requirement, not a default.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

truth = exact_knn(queries, database, k)        # offline ground truth
for knob in knob_values:            # n_probe for IVF, efSearch for HNSW
    index.set_search_param(knob)
    t0 = now(); results = index.search(queries, k); t = now() - t0
    recall = mean(overlap(results[i], truth[i]) / k for i in queries)
    report(knob, recall, latency = t / len(queries))
# choose the smallest knob whose recall >= target

Glossary

Approximate nearest-neighbour search

Finding the closest database vectors to a query while allowing a controlled chance of missing some, in exchange for far lower cost than an exact scan.

Recall at k

The fraction of the true k nearest neighbours that an approximate search actually returns, averaged over queries.

IVF (inverted file index)

An index that clusters vectors into cells and, at query time, scans only the few cells nearest the query.

n_probe

The number of IVF cells a query scans; raising it increases both recall and latency.

HNSW

A hierarchical navigable small-world graph index that searches a layered proximity graph in roughly logarithmic hops.

efSearch

The beam width of an HNSW search; a wider beam explores more of the graph, raising recall and latency.

Pareto frontier

The set of best recall values achievable at each latency for a given index and dataset; comparing indexes means comparing frontiers.

References

1. Malkov & Yashunin (2018), Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (IEEE TPAMI)
2. Vaswani et al. (2017), Attention Is All You Need (NeurIPS)
3. Lin et al. (2023), AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration
4. Kwon et al. (2023), Efficient Memory Management for LLM Serving with PagedAttention (SOSP)