Hierarchical Navigable Small World (HNSW)

What does HNSW mean, and how is it defined?

Hierarchical Navigable Small World, or HNSW, is a graph-based algorithm for approximate nearest neighbor search: it stores every vector in a dataset as a node in a multi-layer graph, then answers a query by starting at a sparse top layer and descending through progressively denser layers until it lands on a small set of vectors that are close to the query. Instead of comparing a query against every vector in a collection one by one, HNSW follows edges toward better candidates, which is what lets it search collections of millions or billions of vectors in milliseconds rather than seconds.

How does HNSW work?

At a glance: HNSW builds its graph across several stacked layers, sparse at the top and dense at the bottom, and answers a query by starting at a fixed entry point in the top layer, greedily moving to whichever connected neighbor is closest to the query, and dropping down one layer each time no closer neighbor can be found — until it reaches the bottom layer, where it does one final, wider search among nearby candidates and returns the closest matches. Building that graph runs the same process in reverse: each new vector is randomly assigned a layer to reach, then connected to a handful of already-existing nearby vectors at every layer it belongs to, using a selection rule that favors spreading connections in different directions rather than only picking the single closest points.

That’s the mechanism in outline. The rest of this page works through why that particular structure was needed in the first place, what happens at each step in more detail, which parameters control its behavior, how it stacks up against other approximate search techniques, and where it actually gets used — starting with the problem it exists to solve.

Why can’t nearest neighbor search just compare a query against every vector?

That description explains what HNSW does, but not yet why a layered graph was the right thing to build in the first place. To see why, it helps to start from the simplest possible way to search, and from where that simplest way breaks down.

The most literal way to find the closest vectors to a query is a linear scan: measure the distance from the query to every single vector in the collection, then sort and keep the closest ones. This works correctly, but its cost grows directly with the size of the collection. A search over a million vectors takes roughly a thousand times longer than a search over a thousand vectors, and a search over a billion vectors becomes impractical for anything that needs to respond in real time. To make that concrete: comparing a query against 10 million 768-dimensional vectors means well over ten billion floating-point operations for that one query, and in practice the bottleneck usually isn’t even the arithmetic — it’s loading tens of gigabytes of vector data through memory for every single search, which is why linear scan latency at that scale typically lands in the hundreds of milliseconds to low seconds rather than staying instant.

Exact data structures such as k-d trees and R-trees were built to avoid this by partitioning space so that large parts of the dataset can be skipped during a search. They work well in two or three dimensions, but their advantage collapses as the number of dimensions grows. In high-dimensional spaces, the distances between points tend to become similar to one another, so the partitioning that these trees rely on stops being useful. This effect is often called the curse of dimensionality, and it is the reason vector search — where a single embedding might have hundreds or thousands of dimensions — needed a different kind of solution.

That solution is approximation. Instead of guaranteeing the exact closest vectors every time, an approximate method returns vectors that are very likely to be among the closest, in exchange for a large reduction in search time. Locality-sensitive hashing and product quantization are two well-known approximate techniques, and HNSW belongs to a third family: graph-based search, which is where its speed comes from.

Where does the idea of a “small world” come from, and what is NSW?

That graph-based family didn’t begin with HNSW, and the two words sitting inside HNSW’s own name — small world — point directly at where it came from. The idea traces back to a famous, non-technical observation: the small-world phenomenon, first tested experimentally by the sociologist Stanley Milgram in 1967, who found that arbitrary pairs of strangers in the United States were typically connected by a chain of only about six acquaintances, despite nobody in that chain having any global map of the social network. The phrase “six degrees of separation” itself is older than Milgram’s experiment — the Hungarian writer Frigyes Karinthy speculated about the same idea in a 1929 short story, and the phrase only became widely known outside academia decades later, through John Guare’s 1990 play of the same name.

Milgram’s result was an observation about real people, not a mathematical explanation. That explanation arrived in 1998, when Duncan Watts and Steven Strogatz showed what actually produces this effect: start with a network made almost entirely of local connections — think of everyone only knowing their immediate neighbors — and rewire just a small fraction of those connections at random into long-range links. The result keeps almost all of the tight local clustering of the original network while collapsing the typical path length between any two distant nodes, and the collapse happens abruptly, with only a handful of rewired long-range links needed to shrink path lengths across the entire network. Watts and Strogatz called this combination of high local clustering and short global path length a small-world network, and gave each half of that combination a formal measure: the average shortest path length, usually written L, and the clustering coefficient, usually written C. A network needs a low L and a high C at the same time to qualify as small-world, which is a harder balance to strike than it sounds — purely random graphs get a low L but a low C, since their connections are scattered with no local structure, while purely regular, lattice-like graphs get a high C but a high L, since every connection is local and nothing shortens the long trips. It turned out to describe far more than social acquaintances — power grids, neural wiring, and citation networks all show the same pattern.

That same topology matters beyond simply connecting nodes efficiently; it also shapes how things move through a network once it’s connected. Researchers studying game theory and the spread of cooperation on networks found that small-world structure changes how strategies and behavior propagate through a population: tight local clustering supports the kind of repeated, close-range interaction that sustains cooperative strategies in a coordination game, while the same small number of long-range links that shorten social chains also let a successful strategy, a piece of information, or a contagion jump between otherwise-isolated clusters far faster than a purely local network would allow. That dual role — a network that is both easy to search and structured to spread things efficiently — is precisely what made small-world graphs worth borrowing for nearest-neighbor search, where the goal is likewise to reach a distant, relevant point quickly using only local decisions.

Short paths existing is not the same as being able to find them without a map. A network can technically have a six-step path between two people while still being useless for passing a message along it, if nobody partway through the chain knows which neighbor to hand it to next. Jon Kleinberg’s work on this question showed that greedy, purely local decision-making — always move to whichever neighbor looks closest to the target — only reliably finds those short paths when long-range links are distributed across distance scales in a specific way, rather than scattered randomly. That distinction, between a graph merely having short paths and a graph being navigable by a simple local rule, is exactly the property nearest-neighbor search needs, since a search algorithm has no global view of the dataset either.

Applying that idea to nearest-neighbor search produced Navigable Small World graphs, or NSW, which is HNSW’s direct predecessor. An NSW graph is built by inserting vectors one at a time and connecting each new vector to a handful of its closest neighbors already present in the graph. Because early insertions have very few existing points to connect to, their connections tend to span long distances across the dataset; later insertions, arriving into an already dense graph, mostly form short, local connections instead. The result, without any explicit planning, is a single graph that mixes exactly the kind of long-range shortcuts and local detail that made Milgram’s social network navigable.

NSW worked, but a single flat graph built this way runs into a specific, measurable problem as the dataset grows, not just a vague sense of slowdown. The first few vectors inserted tend to accumulate a disproportionate number of connections over time, turning into hub nodes that a greedy search passes through again and again as the graph gets bigger. That creates two effects that compound each other: the number of hops a search needs grows with the size of the network, and the degree of the hub nodes sitting on the search path also grows with the size of the network, and since total search cost is roughly hops multiplied by degree-per-hop, two quantities that each scale logarithmically combine into a polylogarithmic cost overall rather than a purely logarithmic one — concretely, a scaling close to log(n) squared rather than log(n), which is the specific gap HNSW’s own inventors have described the layered design as fixing. HNSW’s central change directly targets that multiplication: by separating links according to their length scale into distinct layers, a search only has to evaluate a fixed, bounded portion of each node’s connections at any given layer, regardless of how large the overall network gets, which is what restores logarithmic rather than polylogarithmic scaling. Splitting long-range navigation and local refinement into separate, explicit layers is the structure the rest of this page is about.

How does a layered graph turn search into a sequence of shortcuts?

HNSW keeps NSW’s basic method of connecting each vector to a handful of nearby vectors, forming a graph where an edge represents proximity rather than an explicit relationship, but it no longer leaves the mix of long-range and local connections to chance based on insertion order alone. Searching this graph means starting somewhere and repeatedly moving to whichever connected neighbor is closer to the query than the current position — a strategy known as greedy navigation, tracked with a small priority queue so the search always expands its most promising candidate next rather than exploring every neighbor at the same level first, the way a breadth-first search would. On its own, a single flat graph like this still requires many small hops to cross a large dataset, similar to walking city streets to get from one side of a country to the other.

HNSW fixes this by stacking several graphs on top of each other, borrowing the same idea that makes a skip list fast for ordered data: build a sparse structure of long-range shortcuts above a dense structure of local detail. That resemblance isn’t just a loose comparison — collapse this same layered construction down to a single dimension, where “nearby” simply means “adjacent on a number line,” and the neighbor-selection rule described further down this page reduces exactly to a sorted linked list with occasional shortcut pointers, which is a skip list in every meaningful sense. The bottom layer contains every vector in the dataset. Each layer above it contains a smaller, randomly chosen subset of those vectors, with the topmost layer holding only a handful. Concretely, a single query moves through the graph in a fixed sequence of steps:

1. Start at a fixed entry point in the topmost layer, where connections are sparse and span long distances across the dataset.
2. Greedily move to whichever connected neighbor is closer to the query than the current position — similar to walking up to a library’s entrance directory, which only lists broad subject areas rather than individual titles, and heading straight for the one section that matches what you’re after.
3. Once no closer neighbor can be found in that layer, drop down one level and repeat the same greedy movement there, now using shorter, more local edges — the equivalent of leaving that subject-area directory behind and following a narrower sign once you’re standing inside the right section, pointing you to a specific range of shelves.
4. Repeat that descend-and-search step at each layer down to the bottom layer, arriving already close to the right neighborhood by the time local, dense connections take over.
5. At the bottom layer, explore a wider set of nearby candidates rather than stopping at the first local optimum, and return the closest ones found as the final result.

That last step matters more than it might look: stopping too early at the base layer is one of the more common ways a graph-based search misses a true nearest neighbor, which is exactly what the exploration-width parameter described later on this page exists to control.

What actually happens mechanically when a new vector is added to the index?

The layered structure just described has to be built one vector at a time, and the way it’s built is what determines how well it searches later. When a new vector is inserted, HNSW first decides how high it will reach into the layers. This is chosen randomly using a probability that drops off exponentially, which is why most vectors only ever exist in the bottom layer and only a small fraction reach the higher ones — the same shape that keeps the upper layers sparse and fast to traverse.

Once a layer is assigned, the algorithm searches the existing graph, starting from the current entry point at the top and descending layer by layer, to find a set of candidate neighbors close to the new vector. At each layer the new vector will belong to, it connects to a limited number of those candidates rather than all of them, adding each connection in both directions at once — from the new vector to its chosen neighbor, and from that neighbor back to the new vector — and it does so using a selection rule that favors spreading connections across different directions instead of clustering them all toward the single nearest point. This diversity matters: a graph where every node’s neighbors point in the same direction is easy to construct but bad at answering queries that fall in an unexplored direction, so the neighbor-selection heuristic is a large part of why HNSW graphs stay navigable as they grow. The idea itself has a longer history than HNSW: closely related pruning rules for building navigable proximity graphs appear in work on spatial approximation trees from the early 1990s, including a 1993 paper by Sunil Arya and David Mount — a reminder that this kind of “keep only the diverse, useful edges” heuristic has been independently rediscovered more than once because it’s close to the only reasonable answer to the problem. Because each insertion only needs to read and modify the small part of the graph near the new vector, this process can also be parallelized across multiple threads to speed up building large indexes, though doing so safely requires care over which parts of the graph two threads are allowed to touch at the same time.

Which settings should you tune when speed, memory, and accuracy start to conflict?

This construction process exposes a small number of parameters, and almost every practical decision about running HNSW comes down to how these are set. The first, usually called M, controls how many connections each vector keeps per layer. A higher M produces a denser, more accurate graph at the cost of more memory and slower construction, while a lower M saves memory but risks missing true neighbors during search.

The second, efConstruction, controls how many candidate neighbors are considered while building the graph. Raising it produces a higher-quality graph — better positioned edges, more accurate neighbor selection — but makes indexing slower, and this cost is paid once, at build time. The third, usually called efSearch or a similar name depending on the implementation, controls the same kind of candidate list but at query time — and unlike M and efConstruction, which shape the whole graph, efSearch only affects the final, wider search that happens at the bottom layer, since the upper layers always use plain greedy descent regardless of how it’s set. Raising it makes that base-layer search more thorough and more accurate, at the direct cost of query latency. As a starting point, values of M between roughly 12 and 48, and an efConstruction in the low hundreds, produce reasonable graphs for most datasets; efSearch is the dial most worth adjusting later, since it can be changed per query without rebuilding the index, letting you trade recall for speed on the fly depending on how demanding a particular request is.

How does this speed-accuracy trade-off compare with other approximate search techniques?

HNSW is not the only way to make nearest neighbor search approximate, and the parameters above only make sense in contrast to the alternatives. Inverted file indexes divide the vector space into clusters and search only the clusters closest to the query, which builds quickly and uses little memory but tends to lose accuracy when a query falls near a cluster boundary. Product quantization compresses each vector into a short code, trading a large reduction in memory for a corresponding loss in precision, and is often layered on top of another method rather than used by itself. Locality-sensitive hashing maps similar vectors into the same hash buckets, which is simple to implement but generally needs many hash tables to reach accuracy levels that a graph-based method achieves with a single structure.

Benchmarks that compare these approaches consistently find that HNSW sits near the top of the recall-versus-latency curve — for a given search speed, it tends to return more of the true nearest neighbors than clustering or hashing-based methods manage. The cost is memory: because every vector carries a set of graph connections, an HNSW index typically uses more memory per vector than a compressed, quantization-based index. In practice, many systems combine the two, using HNSW for the graph structure and product quantization to compress what each node stores, which is why you’ll often see both techniques mentioned together rather than treated as competitors.

There’s a second cost that no amount of parameter tuning removes, and it’s structural rather than a simple memory-per-vector number: searching the graph means jumping between whatever nodes happen to be closest to the query, which are scattered unpredictably across memory rather than sitting next to each other. That random-access pattern is exactly what RAM is good at and exactly what spinning or even solid-state disk is bad at, so HNSW performs best when the entire index fits in memory; once it has to spill to disk, the random page faults erode most of its speed advantage, unlike index structures that were designed from the start around sequential disk access. This is one of the main reasons disk-oriented graph index designs exist as a separate line of work for datasets too large to fit in RAM. Within memory, though, HNSW’s layout plays to the hardware’s strengths rather than against them: each node’s neighbor list is typically stored as a short, contiguous run of IDs, so visiting a node and then its neighbors tends to stay inside the CPU’s cache rather than triggering a fresh trip to main memory, which is part of why graph-based search generally has friendlier cache behavior than tree-based methods that jump around memory less predictably.

There’s also a cost that only shows up after the index has been live for a while: HNSW graphs don’t maintain themselves the way self-balancing trees do. Removing a vector is harder than it sounds, because that vector’s connections might be the only bridge between two otherwise-distant regions of the graph — deleting it outright can leave nearby vectors stranded, reachable only through many more hops than before, or not reliably reachable at all. A properly rewired deletion — one that repairs the graph rather than just hiding the gap — costs roughly as much as several tens of ordinary insertions, which is why most implementations avoid it: they mark a vector as deleted and skip it during search while leaving its edges in place, which works but means graph quality slowly erodes as deleted vectors accumulate, eventually requiring a full rebuild. A related problem shows up on the insertion side: if a large batch of new vectors arrives from a meaningfully different distribution than the data the graph was originally built on, the existing long-range connections — tuned for the old distribution — may not serve the new region well, and the graph has no built-in mechanism to notice or fix this on its own. Periodic full rebuilds are the usual answer to both problems, which is a real operational cost worth planning for rather than something the algorithm handles for you.

Where does HNSW actually show up in systems people use today?

None of these trade-offs between memory, build time, and recall are academic — they’re exactly what a team weighs when they pick an index for a real workload, and the choice tends to make a lot more sense once you see what that workload actually is. Any application that needs to find “things similar to this thing” tends to end up needing exactly what HNSW provides. Semantic search is the clearest example: text is converted into embedding vectors, and a search query becomes a nearest-neighbor lookup against those vectors instead of a keyword match, which is what lets a search return conceptually related results even when the exact words don’t match. Recommendation systems work the same way in reverse, matching a user’s embedding against a large catalog of item embeddings to surface the closest matches. Image and audio similarity search follow the identical pattern with embeddings drawn from visual or acoustic models instead of text.

A newer and increasingly common use is retrieval-augmented generation, or RAG, where a language model answers a question using passages pulled from a document collection rather than relying only on what it learned during training. Building a RAG pipeline means splitting documents into passages, embedding each passage into a vector, and indexing all of those vectors with HNSW; when a user asks a question, the question itself is embedded and HNSW retrieves the passages whose vectors are closest to it, and those passages are inserted into the model’s prompt as context before it generates a response. Both sides of the trade-off already discussed on this page matter directly here: latency matters because retrieval runs on every single request before the model can even start responding, and recall matters because a missed passage isn’t just a slightly worse search result — it’s context the model never sees, which can show up downstream as an incomplete or fabricated answer. Document collections behind a RAG system also tend to keep growing as new content is added, which is exactly the kind of steady insertion workload HNSW handles well, even though — as covered above — removing or replacing outdated documents later is the harder half of that maintenance story.

This combination of low latency, tunable recall, and reasonable support for a growing collection is why HNSW has become a default indexing option inside vector database systems rather than something most teams implement from scratch. Weaviate, for example, uses HNSW as its core index for approximate nearest neighbor search, exposing the same M, efConstruction, and ef parameters described above so that the trade-off between speed, memory, and recall can be tuned to the workload rather than left fixed.

What does actually implementing HNSW involve, beyond the algorithm itself?

Everything described so far is the algorithm in the abstract, but turning it into something that runs fast in production raises engineering questions the algorithm alone doesn’t answer. Tracking candidates during search, as covered earlier, needs a priority queue rather than a plain list, since the whole point is to always expand the most promising unexplored option next. Storing each node’s neighbor list as a short, contiguous run of IDs — rather than scattering it across memory — is what gives the graph the cache-friendly access pattern discussed above, and it’s a deliberate layout decision rather than something that happens automatically. Because insertion only touches the small part of the graph near the new vector, construction can also be parallelized across threads, though only with care over which parts of the graph two threads are allowed to touch at once, since the graph itself is being modified as it’s built rather than assembled once and left alone.

There’s one more practical concern that hasn’t come up yet: building a large HNSW graph takes real, non-trivial time, so a production system generally can’t afford to rebuild it from scratch every time the process restarts. That means the graph needs to be serialized to disk and loaded back in, and doing this correctly is its own small engineering problem — the on-disk format has to capture every connection at every layer precisely enough to reconstruct the exact same graph, since a slightly wrong reload can silently produce a structurally different index than the one that was actually tested and tuned.

If you want to go deeper from here, the most useful next step depends on what you’re trying to do. If you’re choosing between indexing strategies for a real system, read through a direct comparison of HNSW against inverted-file and quantization-based methods before committing to one. If you’re already using HNSW and trying to get better recall or lower latency, the parameter-tuning guide on this site works through concrete values for M, efConstruction, and efSearch across different dataset sizes. If you want to see the algorithm rather than just read about it, try implementing a minimal version yourself — insert a few hundred random vectors, run a greedy search by hand, and the layered-shortcut idea described above will make a lot more sense than it does on the page. And if you want the formal underpinnings, including the proofs behind why the neighbor-selection heuristic keeps the graph navigable, the original 2016 paper by Yury Malkov and Dmitry Yashunin lays out the algorithm in full and is worth reading directly.

If you’d rather hear it explained directly by the person who built it, Yury Malkov joined Weaviate’s team for a recorded conversation about HNSW’s design and the thinking behind it — a useful complement to the paper for hearing the reasoning in his own words rather than through a secondary explanation like this page.