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

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.