The Probabilistic Shortcut

You’ve been told that to find the most similar vector in a database, you need a better distance metric. That’s a lie. You can have the most sophisticated Manhattan distance or dot product implementation on Earth, and it won't matter once your dataset hits ten million records. The bottleneck isn't the math of the distance; it's the geometry of the search. If you’re still thinking in terms of linear scans, you’re trying to find a needle in a haystack by burning the whole field down one straw at a time.

To search high-dimensional spaces efficiently, we have to stop trying to be perfectly right and start being "probably" right. This is the world of Approximate Nearest Neighbor (ANN) search, and specifically, the Hierarchical Navigable Small World (HNSW) graph.

The Curse of Dimensionality is a Wall

Most developers start their vector journey with a simple numpy array and a loop. It looks clean, it’s readable, and it works perfectly for 1,000 vectors.

import numpy as np

def brute_force_search(query, library, k=5):
    # Calculate Euclidean distance for every single item
    distances = np.linalg.norm(library - query, axis=1)
    # Sort them all
    indices = np.argsort(distances)[:k]
    return indices, distances[indices]

# This works fine for small N, but O(N) is a death sentence

When you move from 1,000 to 100,000,000 vectors—each with 1,536 dimensions (the standard for OpenAI’s embeddings)—you hit the wall. The "Curse of Dimensionality" isn't just a spooky name; it's a mathematical reality where the volume of the space increases so fast that the available data becomes sparse. In high-dimensional space, everything is far away from everything else.

If you want to find the nearest neighbor in a billion-dimensional space, and you have to check every point, your latency will be measured in seconds or minutes, not milliseconds. We need a shortcut.

The Small World Phenomenon

In the 1960s, Stanley Milgram conducted an experiment that led to the "six degrees of separation" theory. He found that any two people in the US could be connected by a short chain of intermediate acquaintances. This is the "Small World" property: a graph where most nodes are not neighbors, but the neighbors of any given node are likely to be neighbors of each other, and most nodes can be reached from every other node by a small number of hops.

In vector databases, we use this to our advantage. If we can build a graph where "close" vectors are connected, we can navigate that graph to find our target.

But there’s a catch. If you only connect local neighbors, you might get stuck in a "local minimum." You’re in a neighborhood in Brooklyn trying to get to a specific house in Los Angeles, but you only know how to walk to the next house over. You’ll never get there. You need long-range connections.

Enter the Skip List

Before we talk about graphs, we have to talk about Skip Lists. If you understand Skip Lists, HNSW is easy.

Imagine a linked list. To find the 50th element, you have to hop 50 times. A Skip List adds layers. The bottom layer has every element. The layer above it skips every other element. The layer above that skips even more.

# Conceptual Skip List Structure
# Layer 2: [1] ----------------------> [40] ----------------------> [80]
# Layer 1: [1] --------> [20] --------> [40] --------> [60] --------> [80]
# Layer 0: [1]->[10]->[20]->[30]->[40]->[50]->[60]->[70]->[80]->[90]

To find 60, you start at Layer 2. You go from 1 to 40. 80 is too far, so you drop down to Layer 1 at node 40. Then you hop to 60. You found it in three hops instead of six. That’s logarithmic time complexity.

HNSW: The Hierarchical Navigable Small World

HNSW takes the Skip List concept and applies it to a proximity graph. Instead of a linear list, we have a multi-layered graph.

1. The Bottom Layer (Layer 0): Contains every single vector in your database. These are connected in a dense web of "Small World" relationships.
2. Upper Layers: Contain a fraction of the vectors. These act as "express lanes."

When you query an HNSW index, you start at the very top layer at a pre-defined entry point. You look at the neighbors of that point and move to the one closest to your query vector. You keep doing this until you can't get any closer in that layer. Then, you drop down to the next layer and repeat the process.

Why it works

By the time you reach Layer 0, you are already in the "neighborhood" of your target. You’ve used the upper layers to skip millions of irrelevant vectors.

The probability of a node being included in a higher layer is determined by a random distribution—usually an exponential decay function. This ensures that the highest layers are very sparse, while the bottom layers are very dense.

Building it: The Code

While you'd rarely write a production HNSW from scratch (you'd use faiss, hnswlib, or a managed DB like Pinecone or Weaviate), understanding the implementation via hnswlib clarifies the trade-offs.

import hnswlib
import numpy as np

dim = 128
num_elements = 10000

# Generating sample data
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)

# Declaring index
# space can be 'l2', 'cosine' or 'ip' (Inner Product)
p = hnswlib.Index(space='l2', dim=dim) 

# Initializing index 
# max_elements - maximum number of elements in the index
# ef_construction - controls index time/accuracy trade-off
# M - the number of bi-directional links created for every new element during construction
p.init_index(max_elements=num_elements, ef_construction=200, M=16)

# Adding data to index
p.add_items(data, ids)

# Setting query parameters
# ef - the size of the dynamic list for the nearest neighbors (used during search)
p.set_ef(50) 

# Querying
query_data = np.float32(np.random.random((1, dim)))
labels, distances = p.knn_query(query_data, k=3)

print(f"Nearest neighbor IDs: {labels}")
print(f"Distances: {distances}")

The "M" and "ef" Levers

This is where the "shortcut" becomes a series of engineering decisions.

- M: This is the number of edges we create for each node. If $M$ is high, the graph is more "connected," which means better accuracy but higher memory usage and slower build times. For most cases, 16–64 is the sweet spot.
- ef_construction: This determines how many neighbors we explore when building the index. If you set this low, the index builds fast, but the "Small World" isn't very navigable. You might miss the best path.
- ef (search): This is my favorite parameter. You can change this *at query time*. If you need a result in 2ms and don't care if it's 100% accurate, set ef low. If you have 100ms and need high precision, crank it up.

The Probabilistic Nature of the Beast

The "Probabilistic" part of the title isn't just marketing. HNSW doesn't guarantee the nearest neighbor. It guarantees that it will find a very good neighbor with a high degree of probability.

In a traditional SQL database, if you search for WHERE ID = 500, you get 500 or nothing. In an HNSW index, if you search for the neighbor of Vector A, you might get the true neighbor 98% of the time. The other 2% of the time, you get the 2nd or 3rd nearest neighbor because the greedy search algorithm got "stuck" or the right bridge wasn't built in the upper layers.

For LLMs and RAG (Retrieval-Augmented Generation), this doesn't matter. If you are retrieving context for a prompt, the difference between the #1 most similar document and the #2 most similar document is usually negligible.

Practical Gotcha: Memory usage

I’ve seen teams get blindsided by HNSW memory consumption. Unlike a simple flat index or an IVF (Inverted File) index, HNSW stores a lot of extra metadata—all those pointers and graph edges.

A rule of thumb:
Each vector in an HNSW index costs (dim * 4) + (M * 2 * 4) bytes.
If you have 1,536 dimensions and $M=16$:
- Vector data: $1536 \times 4 = 6144$ bytes
- Edge data: $16 \times 2 \times 4 = 128$ bytes
This doesn't seem like much, but when you factor in the overhead of the hierarchy and the object pointers, it adds up. For 10 million vectors, you're looking at ~70GB of RAM just to keep the index "hot."

If you are running out of memory, you have to move to Product Quantization (PQ). PQ "compresses" the vectors into smaller codes, but that's a whole different rabbit hole.

Why not just use a simpler graph?

You might wonder why we need the layers. Why not just a single-layer Navigable Small World (NSW) graph?

I tried this once for a small side project. The problem is "long-range dependencies." In a single-layer graph, the search starts at a random node. To get across the "world," you have to make hundreds of hops through local neighbors. The search time becomes $O(N^{1/x})$, which is better than linear but still feels sluggish as $N$ grows.

The hierarchy makes it $O(\log N)$. That's the difference between your app feeling like a snappy AI assistant and feeling like a loading spinner.

Heuristics and Edge Cases

The actual HNSW algorithm (as defined by Malkov and Yashunin) includes a specific heuristic for selecting neighbors. It’s not just "pick the $M$ closest points."

Instead, it tries to pick neighbors that are in different "directions." If you have 10 neighbors but they are all clustered in one corner, they don't help you navigate the rest of the space. The algorithm intentionally picks a diverse set of neighbors to ensure the graph spreads out across the high-dimensional manifold.

# Pseudo-logic for neighbor selection in HNSW
def select_neighbors(new_node, candidates, M):
    neighbors = []
    # Sort candidates by distance to new_node
    candidates = sorted(candidates, key=lambda x: distance(new_node, x))
    
    for c in candidates:
        if len(neighbors) >= M:
            break
        # Only add candidate if it's closer to new_node 
        # than it is to any already-selected neighbor.
        # This ensures 'diversity' and prevents redundant edges.
        if all(distance(c, new_node) < distance(c, n) for n in neighbors):
            neighbors.append(c)
    return neighbors

This diversity is what makes the graph "Navigable." Without it, you end up with "hubs" that are hard to leave and "islands" that are hard to reach.

The Trade-off Matrix

When you're deploying this in production, you're constantly balancing a three-way scale:

1. Latency: How fast is the knn_query?
2. Recall: How often do we find the *actual* nearest neighbor?
3. Throughput/Memory: How many queries can we handle per second, and can we afford the RAM?

If you're building a recommendation engine for a retail site, you might favor latency over recall. It doesn't matter if you show the 4th most similar pair of shoes instead of the 1st. But if you're doing medical image similarity, you might want to crank ef and M to the max, regardless of the cost.

Summary of the Shortcut

The jump from $O(N)$ to $O(\log N)$ is the reason the current AI boom is even possible. If we had to scan every embedding every time someone typed a message into ChatGPT, the compute costs would have bankrupted the industry months ago.

The "Probabilistic Shortcut" of HNSW isn't a compromise; it's a realization that in high-dimensional space, connectivity is more valuable than precision. By layering our data into a hierarchy of small worlds, we can traverse millions of points in a dozen hops.

Next time you query a vector database, remember: you're not actually searching the whole database. You're just taking the highway until you find the right exit, then following the local roads until you see the right house. It's not perfect, but it's fast enough to feel like magic.