HNSW

Modern search systems don’t compare words, but lists of numbers. Every text, every image, and every piece of music is translated into a long list of numbers. Similar content receives similar lists of numbers in the process. A search then means: find the lists that lie closest to the query. With millions of entries, it would be too slow to check each one individually. HNSW is a method that drastically shortens this search by first linking the data into a network of neighborhood connections.

Why similarity search without a shortcut is too slow

The simple approach is called brute force: you calculate the distance to the query for every stored entry. The result is perfect, but the computation time grows with the amount of data. With ten million entries and a thousand numbers per entry, that’s billions of computational steps per query. For a website that’s supposed to respond within milliseconds, this is unusable.

HNSW therefore belongs to the methods for approximate nearest neighbor search. “Approximate” means: the result is usually, but not guaranteed to be, the best one. Typically, a well-tuned HNSW index finds over 95 percent of the truly nearest neighbors. In exchange, it is often a hundred times faster than a complete search. This trade-off is called the balance between hit rate and speed.

This is especially important for AI applications that look things up before responding. A chatbot that searches through company documents needs the matching text passages immediately. If the search is slow, the entire AI appears slow, no matter how good the language model is.

The multi-layered network of neighbors

The name describes the structure. “Graph” means: every entry is a point, and lines connect it to a few similar points. Instead of scanning through everything, you then travel along the lines, always moving to the neighbor that lies closer to the query. As soon as no neighbor is any better, you’ve reached the target.

What’s special is the hierarchy, meaning the layers. The topmost level contains only a few points with very long jumps. Each level below becomes denser, with the bottom level containing all the data. The search starts at the top and covers coarse distances there. Then it drops down a level and continues searching more finely.

A good comparison here: traveling from Hamburg to a specific street in Munich. First you take the highway, then country roads, and finally the residential streets. Nobody drives the whole route on small streets. It’s precisely this mix of wide and fine steps that makes HNSW fast. The price is memory: the graph with all its connections sits in memory in addition to the data, and inserting new points takes time because suitable neighbors have to be searched for.

HNSW in vector databases and AI products

You mostly encounter the term in connection with vector databases. These are databases that specifically store and search such lists of numbers. Well-known systems like Pinecone, Weaviate, Qdrant, Milvus, or the library FAISS offer HNSW as a search method. Even classic systems like PostgreSQL can use it via an extension. Product announcements will then state, for example, that a service supports “HNSW indexes.”

In practice, you encounter this method without noticing it. It’s behind recommendations for similar products in online shops and behind image search, where you upload a photo. Likewise behind chatbots that look things up in a knowledge base before answering. Music services also use it to find tracks that sound similar to one another.

A common misconception: that HNSW understands the content. It does not. The meaning lies solely in the lists of numbers that an AI model has previously generated. HNSW is merely the signpost that quickly finds these lists relative to one another. Anyone wanting to know which settings matter should pay attention to two values: the number of connections per point and the breadth of the search. More of both brings better results, but costs memory and time.