Finding the nearest stored vector is easy if you compare the query with every vector. The problem is that the work grows with the index. HNSW builds a graph so the search can reach a good answer without measuring everything.
Published ·Updated
01 / 08
A vector turns similarity into distance. A model can turn a song, photo or sentence into a list of numbers called a vector. It is trained so that similar things tend to end up with vectors that are close together. Once the data is in that form, finding something similar becomes a distance question. The closest stored vector is the nearest neighbor. On the map, the ring is your query and the dark green dot is its nearest neighbor. Drag the ring and the answer follows.
02 / 08
The simplest exact search measures every stored vector. Measure the distance from the query to each stored vector and keep the closest one. Because none are skipped, the true nearest stored vector must be among the points you measured. Each measurement is one distance check, i.e. a distance computation. The counter on this page counts a stored vector once per search even if a graph search reaches it again later. Press Check every vector and the counter reaches exactly 500. Raise Points in the index and run it again. The number of checks rises with the number of stored vectors. Ten times more vectors means ten times more checks.
03 / 08
Now turn the stored vectors into a graph. For each vector, measure its distance to the other stored vectors and choose the closest few. Draw a link to each one. The points and links together form a graph. Each point is a node, and the nodes linked to it are its neighbors. Links per vector controls how many of the closest vectors each node chooses. This demo makes every link work both ways, so a node can end up with more links than it chose itself because other nodes chose it too. Press Build the links and watch the connections appear. These distances are used to build the graph. The query has not been searched yet.
04 / 08
The graph gives the search somewhere to move. Start at one node and measure how far that node is from the query. Then measure every neighbor of that node. If any neighbor is closer to the query than the current node, move to the closest one and repeat. If none is closer, stop. The search can make that decision because it checks every neighbor of the node before choosing the next move. The fixed starting node is the entry point. This is a greedy search, i.e. it takes the best move available now without planning a route ahead. Press Advance one hop to make one decision at a time, or Run to the end. For this query at 4 links, the walk takes 29 hops and 80 checks instead of the 500 checks from a full scan.
05 / 08
Greedy search can stop in the wrong place. If every neighbor of the current node is farther from the query, greedy search stops. A closer vector can still exist elsewhere in the graph. That false ending is a local minimum, i.e. a point that looks best from the current position but is not the true nearest. With only one candidate in hand, the search has nowhere else to continue. HNSW keeps several of the best points it has found instead. Beam width is the number it keeps, i.e. the parameter the HNSW paper calls ef. If one route stalls, another promising point is still available to explore. The search stops when nothing left to explore can beat the worst point already being kept. A larger beam usually costs more checks and makes a miss less likely. This query is chosen so a beam width of 1 fails. Raise Beam width and watch the green rings. Each ring is one of the best points the search is still keeping.
06 / 08
Local links are good for small moves but slow for crossing the graph. If every link stays nearby, a search that starts far from the query may need many short hops to reach the right region. Add a few long links and the search can cross a larger distance in one move, then use local links again when it gets close. This toy spreads those long links across distance scales. Some are short, some medium and some very long, with each doubling of distance getting about the same share. A 2000 result for a two-dimensional lattice showed why that distribution helps greedy routing. This figure borrows the idea, but it is not a graph HNSW actually builds. The links here work both ways, so when each point draws 1 long link, each point ends up with about 2 extra long links on average because other points can link back to it. Slide Long links drawn per vector, then press Run the walk. HNSW gets a similar range of link lengths differently.
07 / 08
HNSW gets long-range movement from a hierarchy. Every vector appears on the ground layer. A random draw lets some vectors also appear one layer higher, fewer appear above that, and so on. In this index, roughly 1 in M reaches each next layer. Each layer builds its own graph among the vectors that appear there. The upper layers are sparse, so their nearby points tend to be farther apart and their links cover larger distances. The ground layer is dense, so its links handle the smaller moves. Search starts at the top, moves greedily until no neighbor is closer, then drops a layer and continues from the point it reached. On the ground layer, the beam search from step 5 does the final search. M caps each stored neighbor list, with up to M neighbors on the upper layers and 2M on the ground layer. This demo keeps the plain nearest candidates when it builds links. Production HNSW usually applies a diversity rule when choosing which links survive. Slide Links per vector, M and press Run the search.
08 / 08
The search cost grows much more slowly than a full scan. Averaged over 400 query positions, this index uses 33.2 distance checks with 100 vectors and 48.2 with 1,500. The index is 15 times larger, while the measured search work is about 1.5 times larger. A full scan would rise from 100 checks to 1,500. HNSW saves that work by leaving most vectors unvisited, which is also why it can miss. Recall is how often the search returns the true nearest vector. Beam width trades more checks for a better chance of finding it, while Points in the index and Links per vector, M rebuild the index itself. Pick an experiment, guess the answer, then run it.
Two simplifications set the scope of the numbers here. The vectors have two dimensions so the search can be drawn on a map. Real embeddings often have hundreds of dimensions, so these counts show how the work changes in this toy rather than predicting a production index. The demo also stops at 1,500 vectors, while production indexes can hold millions.
Every average on the page uses the same 20 by 20 grid of 400 query positions and the same fixed entry point. A single query can move in either direction as a setting changes. With 500 vectors, the step 7 query costs 45 checks at an M of 6 and 81 at an M of 7 even though the 400-query average rises steadily across that range. Treat one run as an example and the grid average as the trend.
The counter reports unique vectors measured. A vector's distance to the query is computed once per search and cached even if the search reaches that vector again on another layer. The third experiment therefore shows 46 measured vectors. The same run would make 83 distance calls if the distance were recomputed on every visit.
Step 6 redraws the long links with a fresh seed whenever Long links drawn per vector changes. Every vector draws the selected number of long links. Because the links work both ways, a setting of 1 produces 2.00 extra incident links per vector on average in this graph. The HNSW build also uses the plain nearest candidates when it chooses neighbors, while the paper prefers a diversity heuristic.
At 100 vectors, the layered search still averages 33.2 distance checks, about a third of the index. The work on one layer stays fairly limited while the number of layers grows slowly. Across the 100 to 1,500 range, the total search work therefore rises much less than a full scan does.