What does HNSW stand for, and at a high level, how does it achieve sub-linear approximate nearest-neighbor search?

HNSW stands for Hierarchical Navigable Small World. It is the default approximate nearest-neighbor (ANN) index in Qdrant. The name is two ideas glued together. Navigable Small World is the property that a graph can be built so that greedy routing between any two nodes takes a number of hops that grows logarithmically with the number of nodes - you do not need a globally optimal routing table, just a graph where each node has a few long-range links and several short-range ones. Hierarchical is the trick that makes greedy routing actually work in practice: instead of one flat graph, you keep a stack of graphs at decreasing density, and you use the sparse top layers as an express lane to get close to the query region before you start doing expensive fine-grained work at the bottom.

Mechanically, every point is assigned a maximum level drawn from a geometric distribution, so the expected number of points at level l shrinks by a constant factor as l increases. Layer 0 contains every point; each higher layer contains a random subset of the layer below. A search starts at the single entry point at the top layer and performs greedy descent: from the current node it repeatedly jumps to the neighbor closest to the query, stopping when no neighbor improves the distance. It then drops to the next layer down and repeats, using the node it just converged on as the new entry point. This is why search is sub-linear: on each sparse upper layer a single greedy walk covers a large fraction of the metric space in O(log N) hops, and by the time you reach layer 0 you are already in the right neighborhood, so the layer-0 traversal only has to explore a small local region. Layer 0 itself is not pure greedy - it is a best-first search over a candidate priority queue bounded by ef, which is what lets it escape local minima and return a good top-k rather than a single nearest neighbor. The critical detail that most people miss is the neighbor-selection heuristic used at build time: HNSW does not simply connect each node to its M nearest neighbors. It applies a diversity heuristic that keeps an edge only if the candidate is closer to the node than to any already-selected neighbor, which deliberately preserves long-range links and prevents the graph from collapsing into disconnected clusters. Without that heuristic, recall degrades badly on clustered or high-dimensional data.

The trade-off you are always making is recall and latency against memory and build time. Raising m makes the graph denser and typically raises recall, but it increases memory linearly and can hurt latency once the graph stops fitting in CPU cache - that is the point where more edges turns into more cache misses rather than fewer hops. Raising ef_construct improves graph quality at build time and costs build throughput, not query latency. Raising ef at query time buys recall for latency, per request, with no rebuild - that is the knob you reach for first when someone reports bad results. The main alternative to HNSW is IVF-style indexing, typically combined with product quantization (IVF-PQ), which uses far less memory and builds much faster but generally gives worse recall at the same latency; it is the right choice when the corpus is huge and memory-constrained rather than latency-constrained. Brute force (or Qdrant exact search) is the right choice below roughly ten thousand vectors, which is why Qdrant has a full_scan_threshold that switches small collections to a linear scan automatically. The most common misconception from less experienced engineers is that ef_construct affects query speed - it does not, it only affects index quality and build time, so tuning it to fix a latency problem is wasted effort and a re-index. The second most common is treating HNSW output as ground truth; in a retrieval system, ANN recall and reranker quality are two independent error sources and you have to measure them separately. A third, subtler one: assuming a higher m is always better. Past a certain point, extra edges mostly add memory and cache pressure with negligible recall gain.

Version-dependent notes worth flagging in an interview rather than stating as universal truth: the client API here is qdrant-client 1.10+, where query_points replaced the older search/search_batch calls - the old names still work but are deprecated, so pin your client version. The exact default values of m, ef_construct and full_scan_threshold have changed across Qdrant releases and differ per vector size, so read the collection config at runtime instead of hardcoding assumptions. Recent Qdrant releases also added on-disk HNSW with quantized vectors stored inline in the graph nodes, which changes the memory/latency calculus significantly for large on-disk collections; if you are on an older minor version, that option does not exist and your sizing math will be wrong. Finally, setting m to 0 on a named vector disables graph construction entirely for that vector, which is intentional for reranking-only vectors and is not the same as having a broken index.