Vector Search From First Principles: Navigable Small World Graphs

In the previous article, we moved from exact nearest-neighbor search to Approximate Nearest Neighbor search.

ANN gave us an important freedom: we no longer have to examine every vector in the dataset.

But that immediately creates another problem. If we are going to ignore most of the dataset, how do we decide which vectors are worth examining?

We need some structure that can guide the search toward promising parts of the vector space without first calculating the distance to everything.

One surprisingly intuitive solution is:

Turn the vectors into a graph, and navigate through that graph toward the query.

Instead of asking: Which of these millions of vectors is closest to my query?

we can begin asking: From where I currently am, which neighboring vector moves me closer to the query?

This is the idea behind graph-based ANN search, and one of its earliest influential forms is the Navigable Small World graph, or NSW.

Turning vector search into graph navigation

Consider a small collection of two-dimensional vectors:

A = [1.0, 1.0]
B = [1.2, 1.1]
C = [2.0, 1.8]
D = [6.0, 5.8]
E = [7.0, 6.5]
F = [8.0, 7.0]

Plotted in vector space, these would simply appear as scattered points.

But instead of leaving the vectors independent, suppose we connect nearby vectors to one another.

We now have a proximity graph:

• each vector becomes a node;
• an edge connects one vector to another vector considered nearby.

From vectors to graph navigation: nearby vectors form a proximity graph, allowing greedy search to move through the space toward the query instead of examining every vector.

The graph now contains information about the geometry of the dataset. If we are currently at A and want to move toward the region around C, we do not need to inspect every vector in the database.

The graph already gives us a possible route:

A → B → C

Vector search has now become a routing problem.

We no longer need to examine every vector directly. Instead, we need a graph that gives the search useful routes through the dataset.

Greedy graph search

Suppose the query vector is Q = [7.4, 6.7], and imagine that our search begins at A.

From A, we compute its distance to the query and then look at A’s neighbors. If one of those neighbors — say B — is closer to the query than A is, we move to B.

We then repeat the same process: from B, we inspect its neighbors, and if C is closer to the query, we move again.

Greedy graph search: at each step, the search evaluates the current node’s neighbors, ignores those that do not improve the distance to the query, and continues only along the most promising path.

At each step, it chooses the next node by asking a simple question: Which neighbor looks closest to the query?

This is the basic intuition behind greedy graph search. The algorithm does not try to understand the whole graph at once. It only uses local information — the current node, its neighbors, and which of those neighbors seems to move the search in the right direction.

This simple rule gives us a way to move through the graph without examining every vector.

But how useful that search is now depends heavily on what connections the graph contains.

A graph can have perfectly valid edges and still be painfully slow to navigate.

The first obvious construction exposes why.

A graph containing only local neighbours has a problem

The first attempt seems obvious: Connect every vector only to its nearest neighbors.

Our graph might look something like:

●──●──●──●──●──●──●──●──●──●──●

This gives us excellent local connectivity: once the search is in roughly the right region, it can easily move between nearby vectors and refine its answer.

But local connectivity does not necessarily give us global navigability. If the query lies on the other side of the vector space, the search may have to follow many short edges just to get there.

Our query lies near the right side:

start                           query
  ↓                                ↓

  ●──●──●──●──●──●──●──●──●──●──●──●

If every connection is short, we may need many hops to cross the graph.

That starts looking suspiciously similar to the problem we were trying to avoid.

Instead of comparing the query with every vector, we may now be walking through a large number of vectors one short hop at a time.

The data structure changed, but we still have not solved the problem of moving quickly across the dataset.

We need another kind of connection.

Long-range connections change the graph

Suppose we keep the local connections but introduce a few longer ones.

Now the graph contains two kinds of connections, each useful at a different stage of the search.

Short connections

These connect very similar vectors. They are useful when the search is already near the query and needs to refine its location.

Long connections

These can jump between distant regions of the vector space. They are useful when the search is still far from the query.

Local vs. long-range navigation: short connections provide precise local movement, while occasional long-range links let the search cross the vector space in far fewer hops.

Together, they solve two different parts of the navigation problem:

Long links help us move quickly across the space.

Short links help us search precisely once we get there.

This is where the idea of a small world enters vector search.

The small-world idea

The term comes from network science.

A social network gives us a useful intuition. Most people have many connections within relatively local communities, creating tightly connected clusters. But a smaller number of relationships cross between otherwise distant communities.

Small-world intuition: most connections stay within local communities, while a few long-range links connect distant groups and dramatically shorten paths across the network.

Those occasional long-range connections can dramatically reduce the number of steps required to move through the network.

That gives us exactly the combination we want for vector search:

• Locally: many short connections
• Globally: a smaller number of long-range connections

The result is a graph where nearby points remain easy to explore, while distant parts of the graph can still be reached in relatively few hops.

But where do the long-range connections come from?

We now know what we want from the graph:

• short connections that help us navigate precisely within a neighborhood;
• longer connections that let us move quickly between distant regions.

But do we actually need to decide in advance which edges should be local and which should become long-range shortcuts?

NSW gets this mixture in a much more interesting way.

It does not explicitly create separate short-range and long-range edges.

Instead, both kinds of connections emerge from the way the graph is constructed.

Building a Navigable Small World graph

NSW builds the graph incrementally.

Vectors arrive one at a time, and each new vector must make its connections using the graph that exists at that moment.

Suppose our vectors are arranged in space like this:

A    B    C    D    E    F

But they are inserted in a random order:

D → A → F → B → E → C

When a new vector is inserted, NSW searches the graph that already exists, finds approximately its nearest existing vectors, and connects the new vector to them.

The important detail is that the new vector can only choose among the points that have already been inserted.

Incremental graph construction: each new vector can connect only to vectors already present in the graph. As the graph grows, connections created early can persist even after much closer vectors are inserted later.

Consider what happens early in construction. Suppose only D and A have been inserted:

A ─────────── D

A and D may be quite far apart in the final dataset.

But at this moment, there are very few alternatives. Among the vectors that currently exist, they may still be among each other’s closest available neighbors.

So the connection is created.

As more vectors arrive, the graph becomes denser. Newly inserted vectors now have more nearby existing points to choose from, so their connections tend to become shorter.

An old connection becomes a shortcut

When A ─ D was first created, it was not deliberately designed as a shortcut. At that moment, there were simply very few alternatives.

But after more vectors are inserted between them, the graph might eventually look more like:

A ── B ── C ── E ── D
 \_________________/
       old edge

What began as a reasonable connection in a sparse graph has become a long-range shortcut in the denser graph.

And this can happen repeatedly as the graph grows.

Old connections can become shortcuts simply because newer vectors fill the space around them.

This is how NSW can naturally end up with a mixture of short and long connections without explicitly deciding which edges should belong to each category.

But how many connections should we create?

So far we have been saying: Connect the new vector to its nearest existing vectors.

But we skipped an important question: How many of them?

This is where a parameter usually written as **M** enters the picture.

If M = 2, a newly inserted vector creates at most two connections.

If M = 16, it can connect to many more existing vectors, giving the graph more possible routes.

At first, increasing M sounds obviously better.

More connections give the search more alternatives. If one route is unhelpful, another edge may still lead toward a better part of the graph.

So increasing connectivity can make the graph easier to navigate.

But those additional routes are not free.

More edges require more memory.

For N vectors, increasing the average number of stored connections increases graph storage roughly with:

N × number of connections

A graph where every node keeps 32 neighbors needs roughly twice as many neighbor references as one keeping 16.

More edges also mean more work during search

Suppose the search arrives at a node with four neighbors. It may need to calculate four distances to decide which candidates look promising. If the node has 40 neighbors, there are potentially far more distances to evaluate.

So M creates a fundamental trade-off:

More connections give the search more possible routes, but increase both graph storage and the amount of work required when nodes are explored.

The connectivity trade-off: increasing M gives the search more possible routes through the graph, but requires more graph memory and more work each time a node is expanded.

Even a good graph does not guarantee that search finds the right path

There is one more source of approximation.

At any point in the search, the algorithm can only make decisions using the part of the graph it can currently see. It prefers the next step that appears to move it closest to the query.

But there is an important limitation:

The best-looking next step is not necessarily on the best path to the true nearest neighbor.

Suppose, from its current position, the search can continue through either B or D.

D is currently closer to the query, so it looks like the better choice:

distance(D, Q) < distance(B, Q)

A purely greedy search would continue through D.

But the graph behind B might contain a connection to a region much closer to the query.

Greedy search cannot see that yet.

From its current perspective, D looks better, so that is the route it prefers.

This is where the approximation enters: greedy search makes the best decision it can with the information currently visible to it.

The search therefore faces another trade-off.

If it follows only the single best-looking route, it performs very little work — but it can miss a better region of the graph.

If it keeps more alternative candidates alive, it has a better chance of discovering those regions — but it must explore more nodes.

Once again, the ANN trade-off appears: more exploration can improve recall, but it also increases search work.

NSW solves one problem — and exposes the next one

NSW has now given us something powerful.

A single sparse graph can contain both:

• short connections, which help refine the search locally; and
• long-range shortcuts, which help move quickly across the dataset.

But NSW still leaves us with two related problems.

First, all connection scales live inside the same graph. Short local edges, medium-range connections, and long-range shortcuts are all mixed together.

Second, search still has to decide how many alternative routes it is willing to explore. Exploring fewer routes means less work, while keeping more alternatives alive can improve recall at the cost of additional exploration.

This suggests a natural question: What if we organized the different connection scales instead of mixing all of them into one graph?

What if search could first use a sparse set of long-range connections to move quickly across the dataset, and then switch to progressively denser, more local connections as it gets closer to the query?

Instead of putting every connection scale into one graph, we could organize them into a hierarchy.

That idea gives us:

Hierarchical Navigable Small World graphs — HNSW.