HNSW doesn't always scale? (daily search tip)

Published about 1 month ago • 1 min read

In previous tips I talked about tail latency

Your search cluster becomes as slow as the slowest node
A wide per-node latency distribution results in an even wider per-cluster distribution

The higher the scale, the more sharded your data becomes, the more small node latency problems exaggerate cluster latencies.

So when I think about graph-based vector retrieval at scale, like HNSW, I get nervous.

With HNSW you’re:

Navigating a non-deterministic graph, depending on the order graph is constructed
Constructed from a non-deterministic set of points specific to this node
Jumping around to different areas of memory, destroying any memory locality

All the non-determinism here worries me. Some nodes will quickly converge on nearest neighbors. Other nodes will take more work.

The cluster’s latency becomes the latency of those nodes that take more work.

Since benchmarks like ANN benchmarks all happen in nicely warmed memory, on one system, they’ll miss these issues.

So search carefully and measure your cluster behavior, not just single node behavior!

-Doug

Events · Consulting · Training (use code search-tips)

You're subscribed to Doug Turnbull's daily search tips where I share tips, blog articles, events, and more. You can always manage your profile:

Vector search means query understanding!? (daily search tip)

Good vector search means more than embeddings. Embeddings don’t know when a result matches / doesn’t match. Similarity floors don’t work consistently - a cutoff that works for one query might be disastrous for another. Even worse: your embedding usually can’t capture every little bit of meaning from your corpus. You need to efficiently pick the best top N candidates from your vector database. What do you need? Query Understanding - translating the query to domain language (categories, colors,...

about 19 hours ago • 1 min read

Use RRF sparingly in hybrid search

Reciprocal Rank Fusion merges one system’s search ranking with another’s (ie lexical + embedding search). RRF scores a document with ∑1/rank of each underlying system. I’ve found RRF is not enough. Here’s the typical pattern I see on teams: A mature lexical solution exists. It’s pretty good, The team wants to add untuned, embedding based retrieval, They deploy a vector DB, and RRF embedding results with the mature system, Disaster ensues! The poor embedding results drag down the lexical...

3 days ago • 1 min read

Blog post on Bayesian BM25

Just sharing my post on Bayesian BM25 and other ways of normalizing BM25 scores. Enjoy! https://softwaredoug.com/blog/2026/03/06/probabilistic-bm25-utopia Do you have any thoughts on normalizing BM25 scores? -Doug Events · Consulting · Training (use code search-tips) You're subscribed to Doug Turnbull's daily search tips where I share tips, blog articles, events, and more. You can always manage your profile:

4 days ago • 1 min read