A vector index built with the HNSW algorithm returns the top-k most similar vectors to a query in a few milliseconds even when the index holds tens of millions of vectors, but occasionally misses a vector that an exhaustive, compare-against-everything search would have found. What best explains this trade-off?
- HNSW is an approximate nearest-neighbor algorithm: it searches a multi-layer navigable graph structure to reach a good answer quickly, accepting a small chance of missing the true nearest neighbor in exchange for search times far faster than comparing the query against every stored vector
- HNSW deletes any vector it judges to be a near-duplicate of another vector already in the index, so the missed vector was likely removed while the index was being built
- HNSW indexes only a random sample of the uploaded vectors and ignores the rest, so vectors outside that sample can never be returned by any query
- HNSW rounds every vector's coordinates to a lower numeric precision before storing them, and the missed vector's true nearest neighbor was lost during that rounding step
Why A? And why not the others?
Correct answer: A. HNSW is an approximate nearest-neighbor algorithm: it searches a multi-layer navigable graph structure to reach a good answer quickly, accepting a small chance of missing the true nearest neighbor in exchange for search times far faster than comparing the query against every stored vector
HNSW builds a multi-layer graph in which higher layers provide long-range shortcuts and lower layers refine the search locally, letting a query traverse from a coarse starting point down to a close neighborhood in far fewer comparisons than checking every stored vector; this graph-based shortcut is what makes HNSW fast at large scale, and it is also exactly why the algorithm is described as approximate -- the greedy graph traversal can settle on a good-enough neighborhood without ever comparing against every vector, so it occasionally misses the single closest one that an exhaustive search would have found. The option about deleting near-duplicates is wrong because HNSW does not remove vectors it judges similar to others; every inserted vector remains a node in the graph. The option about indexing only a random sample is wrong because HNSW builds its graph over all inserted vectors, not a subset chosen in advance. The option about rounding coordinates describes vector quantization, a separate, optional compression technique that is not what defines HNSW's fundamental speed-versus-recall trade-off.
Source: Malkov & Yashunin, 'Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs' (2016), arXiv:1603.09320