Hierarchical Navigable Small World (HNSW) is an approximate nearest-neighbor algorithm for searching vector collections without comparing a query against every vector. It uses a multilayer graph: sparse upper layers guide the search toward promising regions, then denser lower layers refine it. This structure enables logarithmic-time search rather than linear scanning. section 4.5.1
Figure 4.7 HNSW indexes vectors in multiple layers. The search path demonstrates how queries efficiently traverse from sparse upper layers to dense lower layers.
The layered diagram illustrates how search moves from sparse upper levels to denser lower levels. section 4.5.1
Tune the index for the workload. M limits connections per node; efConstruction controls how thoroughly the index is built. Higher values can improve accuracy but increase memory use and indexing time. One example uses M=16 and efConstruction=100; its FAISS configuration also sets efSearch=64. HNSW favors query latency when its memory overhead is acceptable, while IVF may suit frequent additions or tight memory budgets. Benchmark alternatives on the target workload. section 4.5.1 section 4.5.2
import faiss
import numpy as np
dimension = 128 #1
num_vectors = 10000 #1
vectors = np.random.random((num_vectors, dimension)).astype('float32') #1
M = 16 #2
index = faiss.IndexHNSWFlat(dimension, M) #2
index.hnsw.efConstruction = 100 #3
index.hnsw.efSearch = 64 #4
index.add(vectors) #5
query = np.random.random((1, dimension)).astype('float32') #6
k = 5 #7
distances, indices = index.search(query, k)
print(f"Found {len(indices[0])} nearest neighbors")
print(f"Indices: {indices[0]}")
print(f"Distances: {distances[0]}")
The FAISS example builds an HNSW index, sets construction and search parameters, adds vectors, and retrieves nearest neighbors. section 4.5.2
HNSW can also operate behind a vector database’s search API. In a healthcare policy assistant, Pinecone applies it to query embeddings, with top_k controlling the number of returned results and metadata filters narrowing the search. section 4.5.4
