Inside Vector Search: How HNSW Makes Similarity Search Fast

Behind every RAG app and semantic search is the same question: given a query vector, find the closest vectors among millions. The naive way — compare the query to every single vector — is exact but hopelessly slow at scale. The algorithm almost everyone actually uses instead is HNSW, and understanding it demystifies what your vector database is really doing.

HNSW stands for Hierarchical Navigable Small World. The name is a mouthful, but the idea is intuitive once you see it: build a graph you can navigate toward the answer, with express lanes on top for covering big distances fast. It trades a guarantee of the exact nearest neighbor for being hundreds of times faster — an approximation that is almost always worth it.

Why brute force does not scale

Comparing a query against every vector is called exact or brute-force search. It always finds the true nearest neighbors, but its cost grows linearly with the number of vectors and the dimensions, so at millions of embeddings every query becomes expensive. Approximate nearest neighbor (ANN) algorithms like HNSW exist to escape that linear wall.

• Brute force is exact but linear. Double your data and you double the work on every query, forever.
• Most apps do not need exact. Returning the 9 closest of the true top 10 is indistinguishable in a search or RAG result.
• ANN trades a little accuracy for huge speed. Accepting near-perfect recall buys you sub-linear query time.
• HNSW is the dominant ANN method, the default index in Pinecone, Weaviate, Qdrant, pgvector, and most others.

A graph with express lanes

HNSW organizes vectors into a graph where each vector is connected to its neighbors, and crucially, into multiple layers. The bottom layer holds every vector with dense local connections. Each layer above is a sparse sample of the one below — fewer nodes, longer links — like an express highway network sitting over local streets.

To search, you start at the top, sparse layer and greedily hop toward the query: at each node, move to whichever neighbor is closest to the query, until you cannot get closer. Then you drop down a layer and repeat with its denser connections, refining the result. The top layers cover huge distances in a few hops; the bottom layer nails the precise neighborhood. The whole walk takes on the order of log-many steps instead of scanning everything.

Building and querying it

In a library like hnswlib the two knobs that matter show up right away — graph degree at build time, and search effort at query time:

# HNSW: a layered, navigable graph for fast approximate nearest-neighbor search.
import hnswlib

index = hnswlib.Index(space="cosine", dim=768)
index.init_index(max_elements=1000000, M=16, ef_construction=200)  # M = links per node
index.add_items(vectors, ids)                  # build the multi-layer graph

index.set_ef(64)                               # ef = search effort: higher = better recall, slower
labels, distances = index.knn_query(query_vector, k=10)  # ~log(n) hops, not a full scan

That is the whole interface most of the time. M controls how connected (and how large) the graph is; ef_construction controls how carefully it is built; and ef at query time is the dial between recall and speed. Everything else your vector database does sits on top of these.

Brute-force search reads the whole library to find one book. HNSW builds a map with highways and side streets, then drives straight to the shelf — slightly less certain it is the exact closest, vastly faster to arrive.

The trade-offs to tune

• Recall versus speed. Raising ef (and M) finds the true neighbors more often but slows queries — tune it to the recall your app actually needs.
• Memory is the cost. The graph links live in RAM on top of the vectors, so HNSW indexes are memory-hungry at scale.
• Building is not free. Higher M and ef_construction make a better graph but a slower, heavier build and index.
• Updates are awkward. HNSW handles inserts well but deletes poorly; heavy churn usually means periodic rebuilds.
• It is approximate by design. If you truly need the exact nearest neighbor every time, HNSW is the wrong tool — but you rarely do.

The bottom line

HNSW is the engine under nearly every vector search you run: a layered, navigable graph that finds near-neighbors in roughly logarithmic time by hopping along express lanes before refining at street level. You give up the guarantee of the exact closest vector and get back orders-of-magnitude faster queries — a trade almost every search and RAG system should make.

You do not have to implement it, but knowing how it works changes how you operate it: budget RAM for the graph, treat ef as your recall-versus-latency dial, and plan for rebuilds if your data churns. The black box is not so opaque — it is just a clever map you walk toward the answer.