The median latency of an HNSW index is rarely the problem. It is the high percentiles that break an SLA, and their causes differ from the ones driving the median.
The parameter that governs the trade-off
At query time, HNSW descends the graph layers then explores the base layer while maintaining a dynamic queue of size efSearch holding the best neighbours seen so far. That parameter is the main lever: raising it widens the exploration, improves recall and lengthens the search roughly in proportion. Returns diminish — recall plateaus well before cost stops climbing.
Two build parameters act upstream. M sets how many neighbours each node keeps, and efConstruction the quality of the graph built at insertion time. A graph built with too low an efConstruction produces mediocre neighbourhoods, which you then have to compensate for at query time with a higher efSearch. Put another way, you pay on every query what you saved once at build time.
Why the tail diverges
The median reflects a typical query on a well-connected graph. The high percentiles aggregate quite different situations.
Metadata filtering is the first cause. When a predicate is highly selective, graph traversal mostly encounters rejected nodes and has to keep exploring well beyond efSearch to gather k valid results. Cost blows up precisely on the most restrictive queries. Two mitigations: keep separate indexes per partition when the attribute has low cardinality and is stable — tenant, for example — and switch to an exhaustive scan of the subset once the predicate drops below a selectivity threshold, since a linear sweep over a few thousand vectors beats a graph traversal fighting the filter.
Page faults come next. As long as the index fits in memory, every graph hop is a memory access. Once it spills, hops become disk reads at poorly predictable addresses, and a traversal accumulates dozens of them. Occupancy close to the limit does not visibly degrade the median but noticeably thickens the tail.
Garbage collection pauses and lagging replicas round out the picture, with a sharper effect when the same node serves queries and absorbs writes.
The cost of writes
HNSW accepts incremental inserts, but adding a node modifies existing neighbour lists and takes a lock. Under heavy write load, those locks show up directly in read latency. Deletes are worse: they are usually logical, with the node staying in the graph as a waypoint marked deleted. The graph then fills with nodes that cost something to traverse without ever appearing in results.
The answer is periodic rebuilding. You rebuild the index offline from the live vectors, validate it against a frozen evaluation set, then switch traffic over. Separating read replicas from the node that absorbs writes also keeps ingestion spikes from propagating into queries.
How to measure
Measure latency server side and client side: the gap reveals queueing and serialization, often far from negligible when the response carries the vectors. Segment percentiles by filter selectivity rather than aggregating them, otherwise the main cause stays invisible. Finally, always plot recall and latency together: a p99 halved by lowering efSearch is not a win if recall fell with it.