Optimizing Vector Search at Scale

Vector search is fast until it is not. The transition is abrupt, it happens the first time the index stops fitting in memory, and no amount of query tuning gets you back across it. This is a note about recognising that boundary early enough that crossing it is a capacity decision rather than an incident.

The index is the working set

An HNSW index is a navigable small-world graph, and traversing it is a random-access workload. Each hop lands somewhere unrelated to the last. That is the worst possible access pattern for a disk and an unfriendly one even for a page cache.

So the useful question is never "how large is my dataset" but "how much of the graph does a single query touch, and is that portion resident". Once you frame it that way, the tuning knobs sort into two groups: the ones that shrink the bytes a hop costs, and the ones that reduce the number of hops.

• Quantize, then re-rank the shortlist against full-precision vectors.
• Prune edges the graph is not actually traversing.
• Memory-map the index rather than reading it.
• Pin the entry-point layers — they are small and every query touches them.
• Measure P99, not the mean. The mean hides the queries people complain about.

Quantization without regret

Scalar quantization to int8 typically costs a point or two of recall and returns roughly a fourfold memory reduction. That is usually the right trade, because the recall is recoverable and the memory is not.

Recovering it is the easy part: retrieve a shortlist using the quantized vectors, then re-score those candidates against the full-precision originals. The shortlist is small, so re-scoring is cheap.

Pruning is a recall budget

HNSW builds more edges than most workloads need. Construction parameters are chosen to be safe across query distributions, and your query distribution is not "all of them". Sampling real traffic and dropping edges that no traversal has used in a representative window is unglamorous and effective.

The discipline that matters is treating this as a budget rather than an open-ended optimization. Decide in advance what recall you are willing to spend — a point, two points — and prune until you have spent it. Without that number, there is always one more edge to drop.

Let the kernel do the tiering

It is tempting to build an explicit hot/cold tier: keep the frequently-hit portion of the graph in memory, fetch the rest on demand. Before writing that, try memory-mapping the index and letting the page cache decide.

It is doing the same job, it has better information than you do about system-wide memory pressure, and it is already written and debugged.

Most hand-rolled caching tiers are an attempt to out-guess the page cache with less information and more bugs.

The exception is when the index lives on network storage, where a page fault costs milliseconds instead of microseconds. There, explicit residency control earns its complexity — but that is a decision to make with a profile in hand.

Report recall with every latency number

Recall and latency are a pair. A latency figure without its recall is meaningless, because any system can be made arbitrarily fast by returning worse answers.

Track recall against a fixed, versioned ground-truth set and re-measure every time you touch a build parameter. The failure mode is not a sudden collapse; it is a slow drift nobody notices until someone asks why search "feels worse" and there is no baseline to compare against.