HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor algorithm for searching dense vectors. It trades some accuracy for faster, more space-efficient retrieval than comparing a query with every vector, making it useful as a dense-vector equivalent of an inverted index. section 13.5.3
During indexing, HNSW incrementally builds multiple proximity-graph layers over nested subsets of stored vectors. Similar vectors become neighbors, while edges between neighborhoods make the graph navigable. Search follows these connections instead of scanning the full corpus, balancing recall and query throughput. section 13.5.3
A practical pipeline normalizes stored embeddings, adds them to an HNSW index, creates the index, encodes and normalizes each query, then retrieves the k nearest vectors. A similarity threshold can filter weak matches, with a fallback result when none qualify. section 13.5.4
Semantic autocomplete
An HNSW index containing 12,375 concept embeddings returns terms related to “bag,” including “bag ratings,” “bag liner,” “garbage bags,” and “tea bags.” For “mountain hike,” it returns “mountain hiking,” “mountain trail,” and “mountain guide,” supporting more precise suggestions than literal prefix matching alone. section 13.5.4
Listing 13.14 ANN search using NMSLIB
import nmslib
concepts_index = nmslib.init(method="hnsw", #1
space="negdotprod") #1
normalized_embeddings = list(map(normalize_embedding, embeddings))
concepts_index.addDataPointBatch(normalized_embeddings) #2
concepts_index.createIndex(print_progress=True) #3
ids, _ = concepts_index.knnQuery( #4
normalized_embeddings[25], k=10) #4
matches = [labels[phrases[i]].lower() for i in ids] #5
display(matches)
The listing shows a minimal NMSLIB implementation: initialize HNSW with a distance space, batch-add normalized embeddings, create the index, and query nearest neighbors. section 13.5.4
