What is HNSW?

The previous chapter established that vectors get pre-organized ahead of time so search can skip the vast majority of a collection rather than checking everything. What it didn’t explain is the specific structure most modern vector databases actually use to accomplish that skipping, a layered graph called HNSW. Understanding how this particular structure works concretely, rather than treating “pre-organization” as an abstract idea, makes clear exactly why vector search stays fast even as a memory store keeps growing for years.

What Does “Hierarchical Navigable Small World” Actually Describe?

HNSW builds a graph where similar vectors are connected to each other, but it doesn’t build just one flat layer of connections. It builds several layers stacked on top of each other, with every vector guaranteed to appear in the bottom layer, and progressively fewer vectors appearing as the layers get higher. The top layer holds only a small handful of vectors, connected by long-range links that span large distances across the overall space. Each layer below that adds more vectors and shorter, more local connections, until the bottom layer holds every single vector with dense, close-range connections between neighbors.

This layered structure is the “hierarchical” part of the name, and it’s the entire reason the structure is fast: a search doesn’t have to wade through dense, local connections from the very first step, it can start by taking a few large jumps across the sparse top layer before narrowing down through progressively denser layers toward the actual answer.

How Does a Search Actually Move Through These Layers to Find an Answer?

A search begins at the top, sparsest layer, where only a few long-range connections exist, and quickly finds whichever of those few vectors is closest to the query. That result becomes the starting point for the next layer down, which has more vectors and shorter connections, and the search repeats the same process, finding the closest vector to the query among this layer’s slightly denser set. This continues, layer by layer, each pass refining the search closer to the actual best answer, until it reaches the bottom layer holding every single vector, where a final, local search among densely connected close neighbors produces the actual result.

This is often compared to planning a long trip: a long-haul flight covers most of the distance quickly in one big jump, a train covers the remaining regional distance, and a short local walk covers the last few blocks. Each stage of the journey uses a transportation method suited to the distance actually remaining, rather than walking the entire route from the very first step.

Why Does Skipping Most of the Data This Way Actually Work Correctly?

Because the top layer’s long-range connections were built specifically to represent the overall shape of the vector space, landing near the right general region at the top layer reliably puts the search in the correct neighborhood before it ever has to deal with dense, local detail. The search never needs to consider vectors far outside the region it’s already converging toward, because the layered structure itself steers it away from irrelevant regions early, well before the more expensive, fine-grained comparison work of the bottom layer ever begins.

This is exactly why HNSW achieves both speed and strong accuracy at the same time, rather than forcing a stark tradeoff between the two. The upper layers do cheap, coarse work quickly; the lower layers spend more careful effort, but only on the small, already-narrowed-down region that actually matters.

Does Adding New Data to an HNSW Graph Disrupt Its Structure?

Inserting a new vector follows essentially the same process as searching: the new vector’s position gets located by descending through the layers the same way a query would, and once its correct place is found, it gets connected to its nearest neighbors at whichever layers it’s assigned to appear in. This means an HNSW graph can be built up incrementally, one new memory at a time, without needing to be rebuilt from scratch every time something new gets added, which matters enormously for a system like a memory store that keeps growing continuously rather than being built once from a fixed, unchanging dataset.

How Does Weaviate Engram Benefit From HNSW Specifically When Speed Genuinely Matters?

Weaviate Engram’s memory search runs on top of Weaviate’s HNSW implementation, meaning even a memory store that has accumulated years of history still returns results in milliseconds, because the layered graph structure means a query never has to traverse anywhere close to the full collection to find its answer. Consider an emergency-dispatch call-triage assistant helping dispatchers quickly identify whether an incoming call resembles a pattern of past incidents at the same address, where genuine speed isn’t a convenience, it’s the entire point:

from engram import EngramClient

client = EngramClient(api_key=os.environ["ENGRAM_API_KEY"])

client.memories.add(
    "Multiple prior calls from this address involved a resident with a known mobility impairment who has previously requested medical assistance be routed to the rear entrance due to a blocked front stairwell.",
    properties={"address_id": "dispatch-zone-14-unit-2207"},
)

When a new call comes in from the same address months later, the dispatcher’s assistant needs an answer in a fraction of a second, not after scanning years of accumulated incident history one entry at a time:

relevant_history = client.memories.search(
    query="Are there any known access issues or special considerations for this address?",
    properties={"address_id": "dispatch-zone-14-unit-2207"},
    retrieval_config=HybridRetrieval(limit=5),
)

This search returns nearly instantly regardless of how many years of dispatch history the underlying zone has accumulated, precisely because HNSW’s layered structure lets it converge on the correct address’s relevant history through a handful of large jumps followed by a small, local search, rather than scanning through every incident ever logged for the entire dispatch zone. In a context where every second matters, this isn’t an abstract performance benefit, it’s what makes real-time memory retrieval usable at all in exactly the moment it’s needed most.

HNSW explains how a graph structure makes searching for similar vectors fast. A separate, equally important question is how “similar” actually gets measured mathematically once the search has narrowed down to a small set of candidates worth comparing directly. Our next chapter, What are cosine, dot product, and Euclidean distance?, takes up exactly that measurement.