Vector search internals

The problem and why it is hard

Given a query vector, find the k nearest vectors among millions. Exact search is trivial to write and linear in corpus size, which stops being acceptable somewhere around a few hundred thousand vectors under a real latency budget.

The reason you cannot simply use a tree — as you would for one-dimensional or low-dimensional data — is the curse of dimensionality. In high dimensions, space-partitioning structures degrade until they examine nearly everything, and distances between points concentrate: the ratio between the nearest and farthest neighbour approaches 1, so "nearest" becomes barely distinguishable from "average."

The reason vector search works anyway is that real embeddings do not fill their nominal space. They lie on a much lower-dimensional manifold, and the quantity that governs how hard your search is is that intrinsic dimensionality — a property of your corpus and your embedding model, not of the index.

This is why recall numbers do not transfer between systems. Two deployments with identical index parameters can differ by many recall points on different corpora, and any figure quoted without the corpus attached is close to meaningless.

So approximate nearest neighbour search gives up exactness for speed, and the entire discipline is choosing where on that trade-off to sit — deliberately, with a measurement.

Flat: the honest baseline

Compare the query against every vector. For normalised vectors this is one matrix multiply, which modern hardware does extremely well.

scores = matrix @ query        # [n, d] @ [d] -> [n]
top_k  = argpartition(-scores, k)[:k]

Perfect recall by construction, no build step, no parameters, no staleness. Perfectly adequate up to a few hundred thousand vectors, and people abandon it far earlier than they need to.

Keep a flat index over a sample even after you move on. It is your ground truth. Measuring the recall of an approximate index requires knowing the exact answer, and a flat index over 50,000 sampled vectors gives you that for almost nothing. Without it, every recall claim you make is a guess.

IVF: partition the space

Inverted file indexing clusters the vectors — typically with k-means — and assigns each to its nearest centroid. At query time, find the closest few centroids and search only within those partitions.

# build: cluster into nlist partitions (needs a training sample)
centroids = kmeans(sample, nlist=4096)
for v in vectors:
    lists[nearest(centroids, v)].append(v)

# query: search only the nprobe nearest partitions
candidates = concat(lists[c] for c in nearest_n(centroids, q, nprobe))
return top_k(candidates, q)

# nprobe = nlist  is exact search with extra steps.
# nprobe = 1      is fast and misses a lot.

nprobe is the recall dial and it is adjustable at query time without rebuilding, which is genuinely useful — you can raise it for a high-stakes query path and lower it for a cheap one.

The characteristic failure mode is a boundary effect: a query near the edge of a partition has true neighbours sitting in the adjacent one, and with a low nprobe you never look there. This is why recall improves so sharply over the first few increments of nprobe and then flattens.

IVF needs a training step over a representative sample, which means it does not handle a corpus whose distribution shifts substantially over time without periodic retraining. Vectors added after training are assigned to existing centroids, and if the new data occupies a different region the partitions become badly unbalanced.

Product quantisation

IVF reduces how many vectors you compare against. Product quantisation reduces the cost of each comparison and, more importantly, how much memory the vectors occupy.

Split each vector into m sub-vectors. Cluster each sub-space independently into 256 centroids. Store each sub-vector as the single byte identifying its nearest centroid.

# 768-dim float32 vector = 3,072 bytes
# split into m = 96 sub-vectors of 8 dimensions each
# store 96 centroid ids, one byte each = 96 bytes
#
# 32x compression.

# Distances are computed from a precomputed lookup table:
# for each sub-space, the distance from the query's sub-vector
# to all 256 centroids. Then a distance is 96 table lookups
# and an addition — no multiplication at all.

The compression is what makes billion-scale search possible on hardware you can afford: 32× fewer bytes means 32× more vectors resident in memory, and memory residency is the difference between microseconds and milliseconds.

The cost is precision. You are no longer comparing against the vectors, you are comparing against their compressed approximations, and the error is real. The standard mitigation is rescoring: use the compressed index to retrieve a generous candidate set, then re-rank those candidates with the full-precision vectors fetched from disk or a separate store. You get most of the memory saving and most of the accuracy, at the cost of one extra fetch.

IVF-PQ combines both: partition to narrow the search, compress to make each comparison cheap. It is the standard answer at very large scale and overkill below it.

HNSW: navigate a graph

Hierarchical navigable small world is the default for most production systems under roughly fifty million vectors, and its structure is worth understanding because its parameters follow directly from it.

Build a graph where each vector is a node connected to its approximate neighbours. Searching means starting somewhere and greedily walking toward the query. The problem with a single such graph is that a greedy walk from a random start takes many hops to cross the space.

The hierarchy fixes that. Nodes are assigned to layers with exponentially decreasing probability, so the top layer is sparse with long-range links and the bottom layer contains everything with short-range links. A search enters at the top, greedily descends toward the query, drops a layer, and repeats — coarse navigation first, fine refinement last.

M — connections per node. More links means more paths to the right answer and better recall, and a larger graph. Memory scales with it directly, and since the graph itself is often comparable in size to the vectors, this is the parameter that determines whether HNSW fits in memory at all. Production values typically sit between 16 and 64; beyond that you buy very little recall for a lot of memory.

efConstruction — how many candidates the builder considers when linking a new node. Higher produces a better-connected graph and a slower build. It is a one-time cost, so err high: a build that takes twice as long and permanently improves recall is an obviously good trade.

efSearch — how many candidates each query keeps in flight. This is the runtime recall/latency dial and the only one adjustable without rebuilding. It must be at least k, and raising it improves recall with diminishing returns and roughly linear latency cost.

HNSW's practical weaknesses are worth knowing: the graph is large, builds are slow, and deletions are awkward. Most implementations mark nodes as deleted rather than removing them, because removing a node from a graph means repairing the links of everything that pointed at it. Over time a high-churn index accumulates tombstones that consume memory and degrade traversal, and the fix is a periodic rebuild. If your corpus turns over rapidly, budget for that.

Tuning against a measured target

The mistake is tuning by feel — raising efSearch until results "look good." Recall is measurable and the measurement is cheap.

# 1. Ground truth from a flat index over a sample.
truth = {q: flat_search(q, k=10) for q in real_queries}

# 2. Sweep the runtime dial and measure both axes.
for ef in [16, 32, 64, 128, 256, 512]:
    index.set_ef(ef)
    hits, t0 = 0, time.perf_counter()
    for q in real_queries:
        hits += len(set(index.search(q, 10)) & set(truth[q]))
    recall = hits / (10 * len(real_queries))
    p50    = (time.perf_counter() - t0) / len(real_queries)
    print(ef, round(recall, 3), round(p50 * 1000, 2))

# The curve has a knee. Sit just past it — beyond that you
# are paying linear latency for fractional recall.

Three things about this procedure matter.

Use real queries. Random vectors from your corpus are not distributed like user queries, and they will give you a recall figure that does not hold in production. If your queries are embedded differently from your documents — as they are with asymmetric models — this matters a great deal.

Decide the recall target from the application. A RAG system with a reranker over 50 candidates does not need recall@10 of 0.99, because the reranker will reorder anyway. A legal discovery system where a missed document is a liability might. Setting a target makes the tuning decidable.

Re-measure after any change to the embedding model, the chunking, or the corpus size. Recall degrades as an index grows at fixed parameters, and that degradation is invisible without this measurement — it presents as "answers got worse" months later with no code change to blame.

Why filtered search is hard

"Nearest neighbours, but only documents this user can see, from last year, in English" is the most common production requirement and the one that breaks ANN indexes. The difficulty is structural, not an implementation gap.

Post-filtering — search, then discard results failing the predicate — fails when the filter is selective. If a user can see 1% of the corpus, the global top-100 may contain nothing they are permitted to see while relevant material sits at rank 400. The system returns an empty or thin result set and the model says it does not know. It fails quietly, which is what makes it dangerous: nothing errors, quality just degrades for a subset of users.

Pre-filtering — restrict to the permitted set, then search — is correct but destroys the structure the index depends on. HNSW navigates by walking through neighbours; if most nodes are excluded the walk cannot find its way and recall collapses. IVF degrades similarly, since a partition may contain no permitted vectors at all.

What production systems actually do:

Partition by the filter. If the predicate is coarse — per tenant, per workspace, per language — give each value its own index. The filter becomes routing and search is unfiltered within the partition. This is by far the most robust answer where it fits, and it has the additional property of making cross-partition leakage structurally impossible rather than a matter of getting every query right. It should be your first consideration, not your last.

Filtered traversal. Modern implementations evaluate the predicate during graph traversal, traversing through excluded nodes for connectivity while only collecting permitted ones as results, and over-searching to compensate. Effective, with a latency cost that rises as the filter becomes more selective.

Adaptive strategy. Estimate the filter's selectivity first, then choose: brute-force over the permitted set when it is small, filtered traversal in the middle, post-filtering when the filter barely excludes anything. This is what mature vector databases do internally, and it is why their filtered performance varies so much with selectivity.

Choosing an index

The decision is mostly determined by scale and by whether memory or recall is your binding constraint.

Under ~100k vectors: flat. Exact, no parameters, no staleness, no surprises. People move off it far too early and inherit a tuning problem they did not have.

100k to ~10M: HNSW, with M around 16–32 and efConstruction generous. Measure efSearch against a recall target. This covers the overwhelming majority of real applications.

10M to ~100M: HNSW if the memory fits, which is a real question because the graph is large — compute it before committing. Otherwise IVF with scalar quantisation, or IVF-PQ with full-precision rescoring.

Beyond 100M: IVF-PQ or a disk-based index designed for the regime. At this scale memory is the dominant cost of the entire system and the architecture is chosen around it.

Two orthogonal considerations that often decide it regardless of scale:

Update pattern. High churn favours indexes that handle deletion gracefully, or a design where you rebuild partitions on a schedule. HNSW's tombstones make it a poor fit for a corpus that turns over weekly unless you plan the rebuilds.

Filtering. If you have selective filters, this often matters more than raw scale, and partitioning by the filter may determine your layout before any of the above applies.